【机器学习】对抗样本三元组约束的度量学习算法

第16卷第1期 智能系统学报 Vol.16 No.1 2021年1月 CAAI Transactions on Intelligent Systems Jan.2021 D0:10.11992tis.202009050 对抗样本三元组约束的度量学习算法 王鑫，郭鑫垚，魏巍2，梁吉业口 (1.山西大学计算机与信息技术学院，山西太原030006：2.山西大学计算智能与中文信息处理教育部重点实 验室，山西太原030006) 摘要：针对已有三元组约束的度量学习算法大多利用先验知识构建约束，一定程度上制约了度量学习算法性 能的问题，本文借鉴对抗训练中样本扰动的思想，在原始样本附近学习对抗样本以构造对抗三元组约束，基于 对抗三元组和原始三元组约束构建了度量学习模型，提出了对抗样本三元组约束的度量学习算法(metric learn- ing algorithm with adversarial sample triples constraints,ASTCML)。实验结果表明，提出的算法既克服了已有固定约 束方法受先验知识影响大的问题，也提高了分类精度，说明区分更加难以区分的三元组约束能够提升算法的性能。 关键词：机器学习：度量学习；三元组约束：对抗训练；马氏距离；样本扰动：凸优化：梯度下降 中图分类号：TP181文献标志码：A文章编号：1673-4785(2021)01-0030-08 中文引用格式：王鑫，郭鑫垚，魏巍，等.对抗样本三元组约束的度量学习算法.智能系统学报，2021,16(1)：30-37. 英文引用格式：WANG Xin,,GUO Xinyao,,WEI Wei,et al.Metric learning algorithm with adversarial sample triples constraints. CAAI transactions on intelligent systems,2021,16(1):30-37. Metric learning algorithm with adversarial sample triples constraints WANG Xin',GUO Xinyao',WEI Wei2,LIANG Jiye2 (1.School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China) Abstract:Most of the existing metric learning algorithms with triple constraints use prior knowledge to construct con- straints,which restricts the performance of metric learning algorithms to a certain extent.To solve this problem,the met- ric learning algorithm with adversarial sample triple constraints,named ASTCML,is proposed based on the idea of sample perturbation in adversarial training,in which the adversarial sample is learned near the original sample to con- struct adversarial triple constraints.The metric learning model is constructed on the basis of adversarial triples and ori- ginal triples constraints.Experimental results show that the proposed algorithm overcomes the effect of prior knowledge that is problematic for existing fixed constraint methods and improves the classification accuracy.This shows that distin- guishing triple constraints that are more difficult to distinguish can improve the performance of the algorithm. Keywords:machine learning:metric learning;triplet constraints;adversarial training;Mahalanobis distance;sample perturbation:convex optimization:gradient descent 度量学习作为机器学习领域的重要分支，已 在度量学习中，样本之间的相似性通常用马 广泛应用于多个领域，如图像检索、目标检测刀、 氏距离进行度量，即dw(x,x)=(c,-x)FMx,-x, 亲属关系验证⑧、音乐推荐四等，目的是学习数据 其中M要求为半正定矩阵，以保证距离的有效 间的相似性关系使相似样本间距离尽可能小，不 性。Xig等o使用所有样本构成二元组约束，首 相似样本间距离尽可能大o。 次提出了关于马氏距离的度量学习算法，但当样 本规模较大时，约束数量呈爆炸式增长，导致算 收稿日期：2020-09-30. 基金项目：国家自然科学基金项目(62006147.61876103. 法效率降低。为了提高算法效率，Ying等u将 61772323)片山西省重点研发计划项目(201903D121162: 山西省1331工程项目. 学习度量的过程转化为特征值优化问题，提出基 通信作者：魏巍.E-mail:weiwei(@sxu.edu.cn 于特征值优化的距离度量学习算法(distance met-

DOI: 10.11992/tis.202009050 对抗样本三元组约束的度量学习算法 王鑫1 ，郭鑫垚1 ，魏巍1,2，梁吉业1,2 （1. 山西大学 计算机与信息技术学院，山西 太原 030006; 2. 山西大学 计算智能与中文信息处理教育部重点实 验室，山西 太原 030006） 摘 要：针对已有三元组约束的度量学习算法大多利用先验知识构建约束，一定程度上制约了度量学习算法性 能的问题，本文借鉴对抗训练中样本扰动的思想，在原始样本附近学习对抗样本以构造对抗三元组约束，基于 对抗三元组和原始三元组约束构建了度量学习模型，提出了对抗样本三元组约束的度量学习算法 (metric learn￾ing algorithm with adversarial sample triples constraints，ASTCML)。实验结果表明，提出的算法既克服了已有固定约 束方法受先验知识影响大的问题，也提高了分类精度，说明区分更加难以区分的三元组约束能够提升算法的性能。 关键词：机器学习；度量学习；三元组约束；对抗训练；马氏距离；样本扰动；凸优化；梯度下降 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2021)01−0030−08 中文引用格式：王鑫, 郭鑫垚, 魏巍, 等. 对抗样本三元组约束的度量学习算法 [J]. 智能系统学报, 2021, 16(1): 30–37. 英文引用格式：WANG Xin, GUO Xinyao, WEI Wei, et al. Metric learning algorithm with adversarial sample triples constraints[J]. CAAI transactions on intelligent systems, 2021, 16(1): 30–37. Metric learning algorithm with adversarial sample triples constraints WANG Xin1 ，GUO Xinyao1 ，WEI Wei1,2 ，LIANG Jiye1,2 (1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China; 2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006, China) Abstract: Most of the existing metric learning algorithms with triple constraints use prior knowledge to construct con￾straints, which restricts the performance of metric learning algorithms to a certain extent. To solve this problem, the met￾ric learning algorithm with adversarial sample triple constraints, named ASTCML, is proposed based on the idea of sample perturbation in adversarial training, in which the adversarial sample is learned near the original sample to con￾struct adversarial triple constraints. The metric learning model is constructed on the basis of adversarial triples and ori￾ginal triples constraints. Experimental results show that the proposed algorithm overcomes the effect of prior knowledge that is problematic for existing fixed constraint methods and improves the classification accuracy. This shows that distin￾guishing triple constraints that are more difficult to distinguish can improve the performance of the algorithm. Keywords: machine learning; metric learning; triplet constraints; adversarial training; Mahalanobis distance; sample perturbation; convex optimization; gradient descent 度量学习作为机器学习领域的重要分支，已 广泛应用于多个领域，如图像检索[1-4] 、目标检测[5-7] 、 亲属关系验证[8] 、音乐推荐[9] 等，目的是学习数据 间的相似性关系使相似样本间距离尽可能小，不 相似样本间距离尽可能大[10]。 dM(xi , xj) = (xi − xj) TM(xi − xj) 在度量学习中，样本之间的相似性通常用马 氏距离进行度量，即 ， 其中 M 要求为半正定矩阵，以保证距离的有效 性。Xing 等 [10] 使用所有样本构成二元组约束，首 次提出了关于马氏距离的度量学习算法，但当样 本规模较大时，约束数量呈爆炸式增长，导致算 法效率降低。为了提高算法效率，Ying 等 [11] 将 学习度量的过程转化为特征值优化问题，提出基 于特征值优化的距离度量学习算法 (distance met- 收稿日期：2020−09−30. 基金项目：国家自然科学基金项 目 (62006147， 61876103， 61772323)；山西省重点研发计划项目 (201903D121162)； 山西省 1331 工程项目. 通信作者：魏巍. E-mail：weiwei@sxu.edu.cn. 第 16 卷第 1 期 智 能 系 统 学 报 Vol.16 No.1 2021 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2021

第1期 王鑫，等：对抗样本三元组约束的度量学习算法 ·31· ric learning witheigenvalue optimization,DML-eig), 优解。基于三元组约束的度量学习大都通过设置 该算法每次迭代只关注最近的不相似样本。为减 不同的损失函数来学习度量。 少约束的规模，Davis等2随机选择二元组，提出 基于三元组约束的度量学习通常依据先验知 关于度量参数正则化的信息理论度量学习算法 识，采用不同策略构建固定约束。随着迭代次数 (information-theoretic metric learning,ITML), 的增加，部分三元组在训练中不产生作用，于是， 由于随机选择约束，该算法的结果不稳定；Za- 一些动态选择三元组的算法被提出。Mei等P提 deh等)随机选择约束，在相似样本与不相似样 出了使用三元组的基于Logdet散度的度量学习 本中使用不同的度量方法提出几何平均度量学习 (logdet divergence based metric learning with 算法(geometric mean metric learning,.GMML,该算 triplet constraints,.LDMLT),该算法在每次迭代中 法存在闭式解，当样本规模较大时，随着迭代次 选择有效的约束进行度量学习，降低了先验知识 数的增加，部分样本对在训练中不产生作用。针 对度量学习的影响，但是构成三元组约束的样本 对该问题，Omara等提出了动态生成二元组的 都是在原始样本中选择，不能充分利用数据蕴含 算法。然而，当二元组样本间的相似性或相异性 的三元约束。针对这一问题，研究人员将对抗训 存在较大差异时，也将相同阈值应用于所有约 练与度量学习进行结合，在度量学习中通过产生 束。因此，Weinberger等s-1%基于样本与其最近 对抗样本增强算法性能。Chen等P提出对抗度 的同类样本间的距离和不同类样本之间尽可能以 量学习算法(adversarial metric learning,AML),通 一个间隔分开的原则，提出了大间隔近邻分类算 过产生对抗样本对用于混淆学得的度量，提高度 (distancemetric learning for large margin nearest 量学习算法鲁棒性。 neighbor classification,,LMNN)。Yang等m将自适 基于二元组约束的对抗度量学习受参数和样 应地选择近邻个数引入到目标函数中，提出了自 本对间相似性差异的影响，使得对所有二元组约 适应大间隔近邻分类算法(adaptive large margin 束产生对抗样本对是很难实现的，而三元约束解 nearest neighborclassification algorithm.ALMNN), 决了样本对间差异性的问题，同时考虑类间样本 但该算法受参数影响较大。Song等u利用特征 和类内样本的关系，可以将三元约束与对抗训练 空间中样本的几何信息对LMNN算法进行改进， 进行结合。基于三元组约束的度量学习与对抗训 提出了只关注距离最近的不同类样本对的无参大 练进行结合的关键问题是如何生成对抗样本。本 间隔最近邻度量学习算法(parameter free large 文借鉴对抗训练中样本扰动的思想，在原始样本 margin nearest neighbor for distance metric learning, 附近产生对抗样本以构建对抗三元组约束，提出 PFLMNN),该算法不需要调参，且考虑的约束相 一种新的三元组约束的构造方法，并构建对抗样 对较少。Lu等提出一种新的约束构建方法， 本三元组约束的度量学习模型。本文的贡献主要有： 依据样本的先验信息，针对所有目标样本，只选 1)通过在三元组中的入侵样本附近学习对抗 与其同类距离远的样本及不同类距离近的样本生 样本，构造了间隔更小的对抗样本三元组约束； 成固定的三元组，该算法受先验知识影响较大。 2)构造的对抗样本学习优化模型具有闭式解： Capitaine2ol利用损失的加权选择约束，关注较难 3)实验结果表明提出算法的性能优于代表性 区分的区域或类重叠区域，适用于小样本度量学 的三元组度量学习算法。 习。为了减少约束数量，Perrot等2提出回归虚 1 约束构建的相关算法 拟度量学习算法(regressive virtual metric learning, RVML),该算法中每个样本逼近先验定义的虚拟 1.1三元组约束构建 点，可以在线性时间内学习度量，但算法受数据 三元组的构建是基于三元组约束的度量学习 分布的影响。由于三元约束与支持向量机出发点 关键问题之一。Lu等通过选择位于类边界的 一致，都是采用大间隔思想，鉴于支持向量机 样本构建三元组约束，提出了一种有效的三元组 (support vector machine,.SVM)成熟的求解方式， 约束构建方法。该论文利用任意样本、与其欧氏 Wang等四提出了距离度量学习的一种核分类框 距离最大的同类样本和与其欧氏距离最小的异类 架，所提出的框架可以使用标准支持向量机 样本构造三元组约束，并随机选择其中的一部分 (SVM)求解器有效地实现，但不能得到全局最优 约束用于度量学习，这些约束一旦构造和选择将 解。Zuo等P1将三元组约束形式用SVM表示，提 在整个度量学习的过程中固定不变。然而，这些 出了新的度量学习算法，该算法可以得到全局最 基于欧氏距离构造并随机选择的三元组约束并不

ric learning witheigenvalue optimization, DML-eig)， 该算法每次迭代只关注最近的不相似样本。为减 少约束的规模，Davis 等 [12] 随机选择二元组，提出 关于度量参数正则化的信息理论度量学习算法 (information-theoretic metric learning, ITML)， 由于随机选择约束，该算法的结果不稳定；Za￾deh 等 [13] 随机选择约束，在相似样本与不相似样 本中使用不同的度量方法提出几何平均度量学习 算法 (geometric mean metric learning, GMML)，该算 法存在闭式解，当样本规模较大时，随着迭代次 数的增加，部分样本对在训练中不产生作用。针 对该问题，Omara 等 [14] 提出了动态生成二元组的 算法。然而，当二元组样本间的相似性或相异性 存在较大差异时，也将相同阈值应用于所有约 束。因此，Weinberger 等 [15-16] 基于样本与其最近 的同类样本间的距离和不同类样本之间尽可能以 一个间隔分开的原则，提出了大间隔近邻分类算 法 (distancemetric learning for large margin nearest neighbor classification, LMNN)。Yang 等 [17] 将自适 应地选择近邻个数引入到目标函数中，提出了自 适应大间隔近邻分类算法 (adaptive large margin nearest neighborclassification algorithm, ALMNN)， 但该算法受参数影响较大。Song 等 [18] 利用特征 空间中样本的几何信息对 LMNN 算法进行改进， 提出了只关注距离最近的不同类样本对的无参大 间隔最近邻度量学习算法 (parameter free large margin nearest neighbor for distance metric learning, PFLMNN)，该算法不需要调参，且考虑的约束相 对较少。Liu 等 [19] 提出一种新的约束构建方法， 依据样本的先验信息，针对所有目标样本，只选 与其同类距离远的样本及不同类距离近的样本生 成固定的三元组，该算法受先验知识影响较大。 Capitaine[20] 利用损失的加权选择约束，关注较难 区分的区域或类重叠区域，适用于小样本度量学 习。为了减少约束数量，Perrot 等 [21] 提出回 归虚 拟度 量 学习 算法 (regressive virtual metric learning, RVML)，该算法中每个样本逼近先验定义的虚拟 点，可以在线性时间内学习度量，但算法受数据 分布的影响。由于三元约束与支持向量机出发点 一致，都是采用大间隔思想，鉴于支持向量机 (support vector machine, SVM) 成熟的求解方式， Wang 等 [22] 提出了距离度量学习的一种核分类框 架，所提出的框架可以使用标准支持向量 机 (SVM) 求解器有效地实现，但不能得到全局最优 解。Zuo 等 [23] 将三元组约束形式用 SVM 表示，提 出了新的度量学习算法，该算法可以得到全局最 优解。基于三元组约束的度量学习大都通过设置 不同的损失函数来学习度量。 基于三元组约束的度量学习通常依据先验知 识，采用不同策略构建固定约束。随着迭代次数 的增加，部分三元组在训练中不产生作用，于是， 一些动态选择三元组的算法被提出。Mei 等 [24] 提 出了使用三元组的基于 Logdet 散度的度量学习 算法 (logdet divergence based metric learning with triplet constraints, LDMLT)，该算法在每次迭代中 选择有效的约束进行度量学习，降低了先验知识 对度量学习的影响，但是构成三元组约束的样本 都是在原始样本中选择，不能充分利用数据蕴含 的三元约束。针对这一问题，研究人员将对抗训 练与度量学习进行结合，在度量学习中通过产生 对抗样本增强算法性能。Chen 等 [25] 提出对抗度 量学习算法 (adversarial metric learning, AML)，通 过产生对抗样本对用于混淆学得的度量，提高度 量学习算法鲁棒性。 基于二元组约束的对抗度量学习受参数和样 本对间相似性差异的影响，使得对所有二元组约 束产生对抗样本对是很难实现的，而三元约束解 决了样本对间差异性的问题，同时考虑类间样本 和类内样本的关系，可以将三元约束与对抗训练 进行结合。基于三元组约束的度量学习与对抗训 练进行结合的关键问题是如何生成对抗样本。本 文借鉴对抗训练中样本扰动的思想，在原始样本 附近产生对抗样本以构建对抗三元组约束，提出 一种新的三元组约束的构造方法，并构建对抗样 本三元组约束的度量学习模型。本文的贡献主要有： 1) 通过在三元组中的入侵样本附近学习对抗 样本，构造了间隔更小的对抗样本三元组约束； 2) 构造的对抗样本学习优化模型具有闭式解； 3) 实验结果表明提出算法的性能优于代表性 的三元组度量学习算法。 1 约束构建的相关算法 1.1 三元组约束构建 三元组的构建是基于三元组约束的度量学习 关键问题之一。Liu 等 [19] 通过选择位于类边界的 样本构建三元组约束，提出了一种有效的三元组 约束构建方法。该论文利用任意样本、与其欧氏 距离最大的同类样本和与其欧氏距离最小的异类 样本构造三元组约束，并随机选择其中的一部分 约束用于度量学习，这些约束一旦构造和选择将 在整个度量学习的过程中固定不变。然而，这些 基于欧氏距离构造并随机选择的三元组约束并不 第 1 期 王鑫，等：对抗样本三元组约束的度量学习算法 ·31·

·32· 智能系统学报 第16卷 能很好地指导不断更新的度量学习，制约了算法 相对较近的对抗样本对来增强算法的鲁棒性。然 的性能。为了解决这一问题，Mei等提出了一 而，由于需要为每一个二元约束构建对抗样本对， 种面向度量学习的三元组动态选择策略，使每次 仅用单个参数来控制对抗样本的学习，使其参数难 迭代都能有效地利用约束进行度量学习。该方法 以调整，且构建的对抗样本对绝大多数是无效的。 基于当前（第1次迭代）的马氏矩阵M,计算样本 的距离矩阵和相似矩阵，根据当前度量下的近邻 2对抗样本三元组约束的度量学习 与先验目标近邻的偏离程度定义了样本的混乱 现有的方法基于欧氏距离构建三元组约束， 度，并依据样本混乱度选择三元组约束，用于学 并随机选择部分三元组约束用于度量学习。虽然 习下一次(+1次)迭代时度量矩阵M+1。 有一些方法提出了动态构造三元组约束的方法， 尽管LDMLT算法在每次迭代时动态选择混 但大多都是从数据中选择或强调部分约束，并没 乱度高的约束，可以提升度量学习算法的性能， 有构造新的约束，受对抗度量学习(AML)的启 但并不能充分挖掘数据蕴含的相似性关系。 发，本文提出一种三元对抗约束的构造方法。 12对抗度量学习 2.1模型构建 对抗度量学习(AML)算法2基于对抗样本 通过调整参数动态构建三元组，提出了对抗 构造二元组约束，用于提高度量学习算法的鲁棒 样三元组约束的度量学习算法(metric learning al-- 性。AML算法包括2个阶段：混淆阶段和区分阶 gorithm with adversarial sample triples constraints, 段。在混淆阶段，通过对每个约束的2个端点产 ASTCML)。算法分为2个阶段：对抗阶段和区分 生样本扰动，即学习对抗样本对，不断放大或者 阶段。 缩小当前对抗样本的距离，使得在当前度量下该 对抗阶段，生成对抗样本。初始三元组构建 样本对难以区分，如图1所示。同类样本生成的 参考文献[15]，针对每个样本x,选择与其距离最 对抗样本对（即Ⅱs)的2个样本彼此相距甚远，其 近的K个样本x,及不同类的所有样本x构成三 描述对抗样本对为同类的极端情况。类似地，生 元组。当(，x,x)三元组约束间的距离不满足约 成的异类样本的2个对抗样本对（即Ⅱ。）变得非 束关系dM(c,x)-dw(c,x)≥1时，样本x为人侵 常相似，其描述了对抗样本对仍为异类的极端情 样本，三元组(x,x,x)为违反约束关系的三元 况。在区分阶段，实现学得的度量尽可能地区分 组。对初始三元组中违反约束关系的三元组构建 对抗样本对。 对抗三元组，在入侵样本x的附近生成对抗样本 π，使(x,π)间的距离尽可能小，(x,x,π)之间更 加难以区分，如图2所示。通过式()中的损失函 数计算对抗样本。 间隔为1 (a)相似样本的对抗对生成 对抗 样本目标样本 样本 (b)不相似样本的对抗对生成 图1对抗样本示意 Fig.1 Schematic illustration of adversarial samples 近邻样本 图1中S为相似样本，D为不相似样本，Rs表 图2对抗过程示意 示相似样本对，Ⅱ表示相似样本对产生的对抗样 Fig.2 Schematic illustration of adversarial processes 本对，R。表示不相似样本对，Ⅱ。表示不相似样本 min∑dux,xa)+a∑dm(ra,x) (1) 对产生的对抗样本对。 (i.j.DEN (i.j.hEN AML算法通过对同类样本生成同类彼此相 式中：W表示初始三元组中违反约束关系的三 距甚远的对抗样本对，而异类样本生成异类彼此 元组；α为调控因子，控制πH是否为对抗样本

Mt+1 能很好地指导不断更新的度量学习，制约了算法 的性能。为了解决这一问题，Mei 等 [24] 提出了一 种面向度量学习的三元组动态选择策略，使每次 迭代都能有效地利用约束进行度量学习。该方法 基于当前 (第 t 次迭代) 的马氏矩阵 Mt 计算样本 的距离矩阵和相似矩阵，根据当前度量下的近邻 与先验目标近邻的偏离程度定义了样本的混乱 度，并依据样本混乱度选择三元组约束，用于学 习下一次 (t+1 次) 迭代时度量矩阵 。 尽管 LDMLT 算法在每次迭代时动态选择混 乱度高的约束，可以提升度量学习算法的性能， 但并不能充分挖掘数据蕴含的相似性关系。 1.2 对抗度量学习 ΠS ΠD 对抗度量学习 (AML) 算法[25] 基于对抗样本 构造二元组约束，用于提高度量学习算法的鲁棒 性。AML 算法包括 2 个阶段：混淆阶段和区分阶 段。在混淆阶段，通过对每个约束的 2 个端点产 生样本扰动，即学习对抗样本对，不断放大或者 缩小当前对抗样本的距离，使得在当前度量下该 样本对难以区分，如图 1 所示。同类样本生成的 对抗样本对 (即 ) 的 2 个样本彼此相距甚远，其 描述对抗样本对为同类的极端情况。类似地，生 成的异类样本的 2 个对抗样本对 (即 ) 变得非 常相似，其描述了对抗样本对仍为异类的极端情 况。在区分阶段，实现学得的度量尽可能地区分 对抗样本对。 RD ΠD RS ΠS (a) 相似样本的对抗对生成 (b) 不相似样本的对抗对生成 图 1 对抗样本示意 Fig. 1 Schematic illustration of adversarial samples ΠS ΠD 图 1 中 S 为相似样本，D 为不相似样本，RS 表 示相似样本对， 表示相似样本对产生的对抗样 本对，RD 表示不相似样本对， 表示不相似样本 对产生的对抗样本对。 AML 算法通过对同类样本生成同类彼此相 距甚远的对抗样本对，而异类样本生成异类彼此 相对较近的对抗样本对来增强算法的鲁棒性。然 而，由于需要为每一个二元约束构建对抗样本对， 仅用单个参数来控制对抗样本的学习，使其参数难 以调整，且构建的对抗样本对绝大多数是无效的。 2 对抗样本三元组约束的度量学习 现有的方法基于欧氏距离构建三元组约束， 并随机选择部分三元组约束用于度量学习。虽然 有一些方法提出了动态构造三元组约束的方法， 但大多都是从数据中选择或强调部分约束，并没 有构造新的约束，受对抗度量学习 (AML) 的启 发，本文提出一种三元对抗约束的构造方法。 2.1 模型构建 通过调整参数动态构建三元组，提出了对抗 样三元组约束的度量学习算法 (metric learning al￾gorithm with adversarial sample triples constraints, ASTCML)。算法分为 2 个阶段：对抗阶段和区分 阶段。 xi xj xl (xi , xj , xl) dM(xi , xl)− dM(xi , xj) ⩾ 1 xl (xi , xj , xl) xl πil (xi ,πil) (xi , xj ,πil) 对抗阶段，生成对抗样本。初始三元组构建 参考文献 [15]，针对每个样本 ，选择与其距离最 近的 K 个样本 及不同类的所有样本 构成三 元组。当 三元组约束间的距离不满足约 束关系 时，样本 为入侵 样本，三元组 为违反约束关系的三元 组。对初始三元组中违反约束关系的三元组构建 对抗三元组，在入侵样本 的附近生成对抗样本 ，使 间的距离尽可能小， 之间更 加难以区分，如图 2 所示。通过式 (1) 中的损失函 数计算对抗样本。 间隔为1 入侵 样本 对抗 样本 目标样本 近邻样本 xl xi xj πu 图 2 对抗过程示意 Fig. 2 Schematic illustration of adversarial processes min ∑ (i, j,l)∈N dM(xi ,πil)+α ∑ (i, j,l)∈N dM(πil, xl) (1) N α πil 式中： 表示初始三元组中违反约束关系的三 元组； 为调控因子，控制 是否为对抗样本。 ·32· 智 能 系 统 学 报 第 16 卷

第1期 王鑫，等：对抗样本三元组约束的度量学习算法 ·33· 区分阶段，学到的度量尽可能区分对抗三元 (x:-x)x,-x)T,初始三元组中不相似样本间距离 组。将生成的对抗样本代入初始违反约束关系的 小于相似样本间距离[]+=1，反之[].=0。为 三元组中，通过调整参数动态生成新的三元组。 在新的三元组(cx,π)中，使相似样本(x,x)间 了便于调整参数，令8=。详细过程如算法 1所示。 距离尽可能小，相似样本与不相似样本之间以一 算法1对抗样本三元组约束的度量学习算法。 定的间隔分离开。引人非负的松弛变量，构建 输入X:样本集；Y:样本标签集；B:调控参 如式(2)所示的损失函数进行度量学习： 数；4：权衡因子。 min1-m∑dux,x)+r∑∑1-yasn 输出M。 ij-i st.dm(c,πa)-du(x,x,)≥1-E≥0 (2) 初始化Mo=I。 M≥0 根据式(3)计算对抗样本，代入初始三元组中。 式中：最小化损失函数中的前者表示近邻损失， 迭代计算： 后者表示三元组损失；“为权衡因子，调节近邻损 1)根据式（⑤）计算梯度G。 失与三元组损失在损失函数中的比重；当= 2)更新梯度M+1=M,-AVG。 时，H=1,否则，ya=0;第1约束条件为三元组约 3)将M+1进行分解，得到U,V,。 束条件，使相似样本与不相似样本之间以一定的 4)M+1=UrVU。 间隔分离开；第2约束条件m≥0表示违反了三 5)直到收敛。 元组约束条件的间隔；第3约束条件M≥0以保 假定样本个数为N,共有C类且每个类的样 证距离的有效性。 本数相同，B和4的取值个数分别为p和q,t为 2.2优化问题求解 迭代次数。由式(2)构建的三元组约束个数大致 该模型的目标函数是一个凸优化问题，可以 为KW2(1-1/C),并计算每个三元组约束间的距 利用梯度下降方式进行求解。根据式(1)可以得 离，对违反约束的三元组进行梯度下降。为取得 到对抗样本的闭式解： 较高的分类精度，选取合适的B和μ值进行分 =+a分i0eN 1 类，算法所需次数为2 pqtKN2(1-1/C)。所以算法 (3) 1的时间复杂度为ON2)。 将对抗样本代入违反约束的初始三元组中。 区分阶段的损失函数也可以表示为 3实验分析 L=(1-四)dwx,x)+ 本节在12个数据集上（如表1所示），对提出 μ∑∑1-yal+dm(xx-dnl, 的ASTCML算法与目前几个代表性算法进行比 (4) 较，并分析了实验中参数的灵敏度与提出算法的 利用式(4)得到M的梯度： 收敛性。 aL -I-w2X 3.1实验数据与设计 本文提出的ASTCML算法与与K近邻算法 “-《÷广-1+小x (5) (K-nearest neighbor,KNN)、ITML算法2] GMML算法BI、LMNN算法I、PFLMNN算法I 式中：了表示以对抗样本构成的三元组中违反约 RVML算法P、LDMLT算法P和AML算法2进 束条件间隔的三元组；=(x:一xx:-),xH= 行了对比。 表1 数据描述 Table 1 Data sets description Balance Dermatology Diabetes German lonosphere Wine Zoo Segment Waveform-21 Corel_5k Satellite Wilt 样本数 625 366 768 1000 351 178101 2310 2746 5000 64354839 特征 4 34 20 34 1316 19 21 423 36 5 类别 6 2 2 7 > 50 6 2 实验中，对表1数据中的Corl5k数据集，先 PCA)进行降维，保留的数据信息大于95%，除 用主成分分析(principal component analysis, Satellite和Wilt数据集外，对其他数据集进行预处

(xi , xj ,πil) (xi , xj) ξi jl 区分阶段，学到的度量尽可能区分对抗三元 组。将生成的对抗样本代入初始违反约束关系的 三元组中，通过调整参数动态生成新的三元组。 在新的三元组 中，使相似样本 间 距离尽可能小，相似样本与不相似样本之间以一 定的间隔分离开。引入非负的松弛变量 ，构建 如式 (2) 所示的损失函数进行度量学习： min(1−µ) ∑ i, j∼i dM(xi , xj)+µ ∑ i, j∼i ∑ l (1−yil)ξi jl s.t. dM(xi ,πil)− dM(xi , xj) ⩾ 1−ξi jl ⩾ 0 M ⩾ 0 (2) µ yi = yl yil = 1 yil = 0 ξi jl ⩾ 0 M ⩾ 0 式中：最小化损失函数中的前者表示近邻损失， 后者表示三元组损失； 为权衡因子，调节近邻损 失与三元组损失在损失函数中的比重；当 时， ，否则， ；第 1 约束条件为三元组约 束条件，使相似样本与不相似样本之间以一定的 间隔分离开；第 2 约束条件 表示违反了三 元组约束条件的间隔；第 3 约束条件 以保 证距离的有效性。 2.2 优化问题求解 该模型的目标函数是一个凸优化问题，可以 利用梯度下降方式进行求解。根据式 (1) 可以得 到对抗样本的闭式解： πil = 1 α+1 xi + α α+1 xl ,(i, j,l) ∈ N (3) 将对抗样本代入违反约束的初始三元组中。 区分阶段的损失函数也可以表示为 L =(1−µ) ∑ i, j∼i dM(xi , xj)+ µ ∑ i, j∼i ∑ l (1−yil)[1+ dM(xi , xj)− dM(xi ,πil)]+ (4) 利用式 (4) 得到 M 的梯度： ∂L ∂M =(1−µ) ∑ i, j∼i Xi j+ µ ∑ (i, j,l)∈J Xi j − ((( α α+1 )2 −1 ) [ξ ori i jl] + +1 ) Xil (5) J xi j = (xi − xj)(xi − xj) T xil = 式中： 表示以对抗样本构成的三元组中违反约 束条件间隔的三元组； ， (xi − xl)(xi − xl) T [ξ ori i jl]+ = 1 [ξ ori i jl]+ = 0 β = α α+1 ，初始三元组中不相似样本间距离 小于相似样本间距离 ，反之 。为 了便于调整参数，令 ，详细过程如算法 1 所示。 算法 1 对抗样本三元组约束的度量学习算法。 X Y β µ 输入 ：样本集； ：样本标签集； ：调控参 数； ：权衡因子。 输出 M。 初始化 M0 = I。 根据式 (3) 计算对抗样本，代入初始三元组中。 迭代计算： 1) 根据式 (5) 计算梯度 ∇Gt。 2) 更新梯度 Mt+1 = Mt −λ∇Gt。 3) 将 Mt+1 进行分解，得到 U,V+。 Mt+1 = U T 4) V+U。 5) 直到收敛。 N C β µ p q t KN2 (1−1/C) β µ 2pqtKN2 (1−1/C) O(N 2 ) 假定样本个数为 ，共有 类且每个类的样 本数相同， 和 的取值个数分别为 和 ， 为 迭代次数。由式 (2) 构建的三元组约束个数大致 为 ，并计算每个三元组约束间的距 离，对违反约束的三元组进行梯度下降。为取得 较高的分类精度，选取合适的 和 值进行分 类，算法所需次数为 。所以算法 1 的时间复杂度为 。 3 实验分析 本节在 12 个数据集上 (如表 1 所示)，对提出 的 ASTCML 算法与目前几个代表性算法进行比 较，并分析了实验中参数的灵敏度与提出算法的 收敛性。 3.1 实验数据与设计 本文提出的 ASTCML 算法与与 K 近邻算法 (K-nearest neighbor, KNN)、 ITML 算法[ 1 2 ] 、 GMML 算法[13] 、LMNN 算法[16] 、PFLMNN 算法[18] 、 RVML 算法[21] 、LDMLT 算法[24]和 AML 算法[25] 进 行了对比。 表 1 数据描述 Table 1 Data sets description 数据集 Balance Dermatology Diabetes German Ionosphere Wine Zoo Segment Waveform-21 Corel_5k Satellite Wilt 样本数 625 366 768 1 000 351 178 101 2 310 2 746 5 000 6 435 4 839 特征 4 34 8 20 34 13 16 19 21 423 36 5 类别 3 6 2 2 2 3 7 7 3 50 6 2 实验中，对表 1 数据中的 Corel_5k 数据集，先 用主成分分析 (principal component analysis, PCA) 进行降维，保留的数据信息大于 95%，除 Satellite 和 Wilt 数据集外，对其他数据集进行预处 第 1 期 王鑫，等：对抗样本三元组约束的度量学习算法 ·33·

·34· 智能系统学报 第16卷 理操作，对处理后的数据集进行划分，其中80% 性能。当样本数大于或等于4500时，μ的取值范 的数据为训练集，20%的数据为测试集。采用5 围为{0.1,0.3,0.5,0.7,0.9}，且当数据集为Corel5k 折交叉验证的方法进行实验，将训练集随机分为 时，B的取值范围为{0.2,0.4,0.6,0.8}，同时采用 5部分，轮流作为验证集，并对5次实验结果求平 3折进行交叉验证。 均，选择在验证集上达到最高分类精度的参数，3.2实验结果与分析 在测试集上进行测试。Satellite数据集由4435个 实验结果在表2中列出，表2中粗体表示最 训练样本和2000个测试样本组成，Wit数据集 高的分类正确率，在次高的分类正确率下划横 是由4339个训练样本和500个测试样本组成，针 线。当数据集为Corel5k时，AML算法运行时间 对这2个数据集，首先对训练集进行预处理操作， 相对较长，不参与算法比较。实验结果显示本文 记录下训练集的归一化方法，将该方法应用于测 算法普遍优于代表性的度量学习方法，相比于动 试集进行预处理，在所有参数实验结果中选择分 态构建三元组的LDMLT算法，除在German数据 类精度最高的精度，即为当前数据集的分类精 集上取得次高的分类精度，在其他数据集上的分 度。初始化度量矩阵M=I,参数B的取值范围 类精度明显提高；与LMNN算法相比，提出算法 为{0.1,02，…，0.9}，μ的取值范围为{0.1,02，…，1}。 的分类精度最低与其保特一致；相比基于对抗训练的AM 此外，由式(8)可以得到，当B取值为1时，算法 算法，分类精度普遍较高。可以得出，本文算法 精度与LMNN算法的结果相同或相近。使用 在一定程度上说明区分更加难以区分的三元组约 KNN分类器的分类正确率评价度量学习算法的 束能够提升算法的性能。 表2分类精度的对比 Table 2 Comparisons of classification accuracy 数据集 KNN ITML GMML RVML LDMLT LMNN PFLMNN AML ASTCML Balance 0.8080 0.9280 0.8000 0.8080 0.7840 0.8240 0.8000 0.8080 0.9760 Dermatology 0.9324 0.9595 0.9324 0.9324 0.9459 0.9730 0.9324 0.9459 0.9730 Diabetes 0.6883 0.6818 0.6883 0.6883 0.6688 0.6948 0.7273 0.7078 0.7273 German 0.6850 0.7100 0.6850 0.6850 0.7200 0.6900 0.7100 0.7050 0.7150 lonosphere 0.8592 0.8873 0.8592 0.8592 0.7887 0.9296 0.9014 0.8592 0.9437 Wine 0.9722 1.0000 0.9722 0.9722 0.9722 0.9722 0.9722 0.9722 1.0000 Z00 0.8571 0.9048 0.8571 0.8571 0.8571 0.9048 0.8571 0.8571 0.9524 Segment 0.9416 0.9675 0.9416 0.9416 0.9610 0.9589 0.9567 0.9545 0.9654 Waveform-21 0.7709 0.7564 0.7709 0.7709 0.6873 0.7909 0.7891 0.7764 0.8400 Corel 5k 0.2680 0.2630 0.2680 0.2680 0.2560 0.2930 0.2660 0.2980 Satellite 0.9065 0.8880 0.9065 0.9065 0.8270 0.9085 0.9155 0.9065 0.9105 Wilt 0.6780 0.7640 0.6780 0.6780 0.8020 0.8220 0.8040 0.7140 0.8260 Mean 0.7806 0.8092 0.7799 0.7806 0.7725 0.8135 0.8026 0.8439 3.3参数的灵敏度分析 确率的变化情况。从图3、4可以看出，当测试集 在本文提出的算法中，超参数B和μ的设置 上取得最高分类正确率时，验证集上的分类正确 对实验结果会产生一定的影响，其中参数B控制 率也最高：在不同的参数设置下，验证集上分类 在入侵样本附近产生对抗样本，参数“为权衡因 准确率的变化幅度相对较小，而测试集上变化幅 子，调节三元组损失在整个损失中的比重。在不 度相对较大。 同数据集下，只以最高的验证集分类正确率设置 3.4收敛性分析 超参数B和4，通过固定其中的一个超参数，调整 在对抗样本三元组约束的度量学习算法迭代 另一个超参数，观察在验证集与测试集上分类正 优化的过程中，若相邻2次损失值的差小于设定

M = I β µ β 理操作，对处理后的数据集进行划分，其中 80% 的数据为训练集，20% 的数据为测试集。采用 5 折交叉验证的方法进行实验，将训练集随机分为 5 部分，轮流作为验证集，并对 5 次实验结果求平 均，选择在验证集上达到最高分类精度的参数， 在测试集上进行测试。Satellite 数据集由 4 435 个 训练样本和 2 000 个测试样本组成，Wilt 数据集 是由 4 339 个训练样本和 500 个测试样本组成，针 对这 2 个数据集，首先对训练集进行预处理操作， 记录下训练集的归一化方法，将该方法应用于测 试集进行预处理，在所有参数实验结果中选择分 类精度最高的精度，即为当前数据集的分类精 度。初始化度量矩阵 ，参数 的取值范围 为{0.1, 0.2, ···, 0.9}， 的取值范围为{0.1, 0.2, ···, 1}。 此外，由式 (8) 可以得到，当 取值为 1 时，算法 精度与 LMNN 算法的结果相同或相近。使用 KNN 分类器的分类正确率评价度量学习算法的 µ β 性能。当样本数大于或等于 4 500 时， 的取值范 围为{0.1, 0.3, 0.5, 0.7, 0.9}，且当数据集为 Corel_5k 时， 的取值范围为{0.2, 0.4, 0.6, 0.8}，同时采用 3 折进行交叉验证。 3.2 实验结果与分析 实验结果在表 2 中列出，表 2 中粗体表示最 高的分类正确率，在次高的分类正确率下划横 线。当数据集为 Corel_5k 时，AML 算法运行时间 相对较长，不参与算法比较。实验结果显示本文 算法普遍优于代表性的度量学习方法，相比于动 态构建三元组的 LDMLT 算法，除在 German 数据 集上取得次高的分类精度，在其他数据集上的分 类精度明显提高；与 LMNN 算法相比，提出算法 的分类精度最低与其保持一致；相比基于对抗训练的AML 算法，分类精度普遍较高。可以得出，本文算法 在一定程度上说明区分更加难以区分的三元组约 束能够提升算法的性能。 表 2 分类精度的对比 Table 2 Comparisons of classification accuracy 数据集 KNN ITML GMML RVML LDMLT LMNN PFLMNN AML ASTCML Balance 0.8080 0.9280 0.800 0 0.808 0 0.784 0 0.824 0 0.8000 0.808 0 0.976 0 Dermatology 0.9324 0.9595 0.932 4 0.932 4 0.945 9 0.973 0 0.9324 0.945 9 0.973 0 Diabetes 0.6883 0.6818 0.688 3 0.688 3 0.668 8 0.694 8 0.7273 0.707 8 0.727 3 German 0.6850 0.7100 0.685 0 0.685 0 0.720 0 0.690 0 0.7100 0.705 0 0.715 0 Ionosphere 0.8592 0.8873 0.859 2 0.859 2 0.788 7 0.929 6 0.9014 0.859 2 0.943 7 Wine 0.9722 1.0000 0.972 2 0.972 2 0.972 2 0.972 2 0.9722 0.972 2 1.000 0 Zoo 0.8571 0.9048 0.857 1 0.857 1 0.857 1 0.904 8 0.8571 0.857 1 0.952 4 Segment 0.9416 0.9675 0.941 6 0.941 6 0.961 0 0.958 9 0.9567 0.954 5 0.965 4 Waveform-21 0.7709 0.7564 0.770 9 0.770 9 0.687 3 0.790 9 0.7891 0.776 4 0.840 0 Corel_5k 0.2680 0.2630 0.268 0 0.268 0 0.256 0 0.293 0 0.2660 — 0.298 0 Satellite 0.9065 0.8880 0.906 5 0.906 5 0.827 0 0.908 5 0.9155 0.906 5 0.910 5 Wilt 0.6780 0.7640 0.678 0 0.678 0 0.802 0 0.822 0 0.8040 0.714 0 0.826 0 Mean 0.7806 0.8092 0.779 9 0.780 6 0.772 5 0.813 5 0.8026 — 0.843 9 3.3 参数的灵敏度分析 β µ β µ β µ 在本文提出的算法中，超参数 和 的设置 对实验结果会产生一定的影响，其中参数 控制 在入侵样本附近产生对抗样本，参数 为权衡因 子，调节三元组损失在整个损失中的比重。在不 同数据集下，只以最高的验证集分类正确率设置 超参数 和 ，通过固定其中的一个超参数，调整 另一个超参数，观察在验证集与测试集上分类正 确率的变化情况。从图 3、4 可以看出，当测试集 上取得最高分类正确率时，验证集上的分类正确 率也最高；在不同的参数设置下，验证集上分类 准确率的变化幅度相对较小，而测试集上变化幅 度相对较大。 3.4 收敛性分析 在对抗样本三元组约束的度量学习算法迭代 优化的过程中，若相邻 2 次损失值的差小于设定 ·34· 智 能 系 统 学 报 第 16 卷