第6期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·845· 式中：d,(x,x)表示第k对成对约束的第i个距离 将拉格朗日函数式(5)分别对ω：Bp、专、入求 分量，为了便于表示，本文在后续的介绍中将使用符 偏导，并令其等于0得到 号d来代替d,(x。,x)。此外，y为该约束对的类 aL 标，C为惩罚因子，C值大时对训练错误的惩罚增 =w:- dw, A04A=0 大，0为已知参数，B为阀值，最大间隔为P aL wⅡ =29- ar=0 在优化的过程中最大化p,最小化‖wⅡ2，并使训 aL =-9+∑a4=0 (5) 练误差专.最小化，其中k≥0。 ap =1 本文的目标是通过优化该目标函数求得距离分 aL 量的权值ω：，下面将具体介绍求解ω：的方法。为 a店 =2C吃k-a4=0 了求解上述优化问题，将它作为原始最优化问题，应 用拉格朗日对偶性，通过求解对偶问题得到原始问 1 名=0 题的最优解。接下来将介绍具体求解过程。 进而得到 首先，构建拉格朗日函数如式(3)： (6) k=1 =1 B= (7) 26=1 i=1 -名 =∑a4 (8) (3) k=1 Q: 式中：a=【a,a…a,】T、A均为拉格朗日乘子。 5:-2C (9) 如果此时考虑式(2)中ω：≥0的约束条件，并 (10) 将该条件加入拉格朗日函数，则得到 将式(6)代入式(10)得到 L'=L- 名m (11) 将该拉格朗日函数分别对ω：Bp、专：、入求偏 A=-文ad 导，并令其等于0得到 进而，将式(11)代入式(6)得到 aL' =w:- dw. 2d4-A-9,=0 k=1 aL' 将式(7)~(10)、(12)代入拉格朗日函数(3) aβ =2B- a=0 中，即得 k=1 aL' =-0+】 (4) ap 4=0 =1 aL' =2C54-ak=0 (名三ad)P- a店 OL' =1- 2(店42ax4)+ a入 2,=0 i= 显然由方程组(4)无法求得ω：，因此本文先暂 喜，京ax 时不考虑ω：≥0的约束条件，使用式(3)进行后续 即 的求解。 根据拉格朗日对偶性，原始问题的对偶问题是 (w,B,5,a,)=写 B,5 极大极小问题： max minL(w,B,5,a,入) .8,E 所以，需要先求L(w,B,专，x,入)对于ω、入的 极小值。式中： ｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） 表示第 ｋ 对成对约束的第 ｉ 个距离 分量，为了便于表示，本文在后续的介绍中将使用符 号 ｄｉ．ｋ 来代替 ｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） 。 此外， ｙｋ 为该约束对的类 标， Ｃ 为惩罚因子， Ｃ 值大时对训练错误的惩罚增 大， θ 为已知参数， β 为阈值，最大间隔为 ρ ‖ω‖ 。 在优化的过程中最大化 ρ ，最小化 ‖ω‖２ ，并使训 练误差 ξ ｋ 最小化，其中 ξ ｋ ≥ ０。 本文的目标是通过优化该目标函数求得距离分 量的权值 ωｉ， 下面将具体介绍求解 ωｉ 的方法。 为 了求解上述优化问题，将它作为原始最优化问题，应 用拉格朗日对偶性，通过求解对偶问题得到原始问 题的最优解。 接下来将介绍具体求解过程。 首先，构建拉格朗日函数如式（３）： Ｌ ＝ １ ２ ∑ ｐ ｉ ＝ １ ω ２ ｉ ＋ Ｃ∑ ｎ ｋ ＝ １ ξ ２ ｋ ＋ β ２ － θρ ＋ ∑ ｎ ｋ ＝ １ αｋ ρ － ξｋ － ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ，ｋ ( ( － β) ) ＋ λ １ － ∑ ｐ ｉ ＝ １ ( ωｉ) （３） 式中：α ＝ α１ α２ … αｎ [ ] Ｔ 、λ 均为拉格朗日乘子。 如果此时考虑式（２）中 ωｉ ≥ ０ 的约束条件，并 将该条件加入拉格朗日函数，则得到 Ｌ′ ＝ Ｌ － ∑ ｐ ｉ ＝ １ φｉωｉ 将该拉格朗日函数分别对 ωｉ、β、ρ、ξ ｋ、λ 求偏 导，并令其等于 ０ 得到 ∂Ｌ′ ∂ωｉ ＝ ωｉ － ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ － λ － φｉ ＝ ０ ∂Ｌ′ ∂β ＝ ２β － ∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∂Ｌ′ ∂ρ ＝ － θ ＋ ∑ ｎ ｋ ＝ １ αｋ ＝ ０ ∂Ｌ′ ∂ξｋ ＝ ２Ｃξｋ － αｋ ＝ ０ ∂Ｌ′ ∂λ ＝ １ － ∑ ｐ ｉ ＝ １ ωｉ ＝ ０ ì î í ï ï ï ï ï ï ï ï ï ï ï ï ï ï （４） 显然由方程组（４）无法求得 ωｉ ，因此本文先暂 时不考虑 ωｉ ≥ ０ 的约束条件，使用式（３）进行后续 的求解。 根据拉格朗日对偶性，原始问题的对偶问题是 极大极小问题： ｍａｘ α ｍｉｎ ω，β，ξ Ｌ（ω，β，ξ，α，λ） 所以，需要先求 Ｌ（ω，β，ξ，α，λ） 对于 ω、λ 的 极小值。 将拉格朗日函数式（５）分别对 ωｉ、β、ρ、ξ ｋ、λ 求 偏导，并令其等于 ０ 得到 ∂Ｌ ∂ωｉ ＝ ωｉ － ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ － λ ＝ ０ ∂Ｌ ∂β ＝ ２β － ∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∂Ｌ ∂ρ ＝ － θ ＋ ∑ ｎ ｋ ＝ １ αｋ ＝ ０ ∂Ｌ ∂ξｋ ＝ ２Ｃξｋ － αｋ ＝ ０ ∂Ｌ ∂λ ＝ １ － ∑ ｐ ｉ ＝ １ ωｉ ＝ ０ ì î í ï ï ï ï ï ï ï ï ï ï ï ï ï ï （５） 进而得到 ωｉ ＝ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ λ （６） β ＝ １ ２ ∑ ｎ ｋ ＝ １ αｋ ｙｋ （７） θ ＝ ∑ ｎ ｋ ＝ １ αｋ （８） ξｋ ＝ αｋ ２Ｃ （９） １ － ∑ ｐ ｉ ＝ １ ωｉ ＝ ０ （１０） 将式（６）代入式（１０）得到 λ ＝ １ ｐ １ － ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) （１１） 进而，将式（１１）代入式（６）得到 ωｉ ＝ １ ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ （１２） 将式（７） ～ （１０）、（１２） 代入拉格朗日函数（３） 中，即得 Ｌ ＝ １ ２ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ － １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) ＋ ∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ 即 ｍｉｎ ω，β，ξ Ｌ（ω，β，ξ，α，λ） ＝ １ ２ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ － １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) ＋ 第 ６ 期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·８４５·