第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·