·846. 智能系统学报 第10卷 表示无法使w,取正值的i的集合，2个集合p和p 的大小分别使用lp|和p|来表示。 求minL(w,B,专，a,入)对x的极大，即得对偶问题： B,5 至此完成求解距离分量权值ω：的目标，求解集 合p和pˉ的算法描述将在下一小节给出。 max 2印p台台 最大几何间隔0中的p亦可在求解权值 ω：的过程中求得。与原始SVM类似，目标函数(3) 的分商超平面为名如4。一B)=p.即可得最大 ain=0 函数间隔p=y (∑a,ds一B)。在求得最优解后 立4=0 由式(9)可得B的最优解B·= ay进而可得 ak≥0，k=1,2,…,n (13) 将式(13)的目标函数由求极大转换为求极小， 最大函数同隔p=名如，d。一B产)。 就得到下面与之等价的对偶最优化问题： 2.2算法描述 本节将给出求解距离分量权值ω：的具体算法 步骤。 为了便于表示，将式(14)简化： 0,i E p (15) Ue'I +CV:,i∈p aav-g 式中： 含=0 k=1 由式(16)观察可得，若想满足®，为正值，则V: a4≥0，k=1,2,…,n 需要足够大，且当V:越大，ω：为正值的几率就越大。 如此，可以通过二次规划的求解方法得到最优 因此，求解集合p和p的算法总结如下。 解a·=[a1a…a]T,进而代人式(12)得 算法1求解集合p和p。 到w,的最优解： 1)初始化：P。=☑，P={1,2,…,p,h=0: =-ad+4 pp i=ik=1 2)h=h+1,P=P,+{i计，P%=pP-,-i,其 可以明显地观察到，即使成功的优化得到最优 中，i=arg maxi{V}; 解，也不能保证w:完全满足式(2)中ω：≥0的约束 3)通过式(14)计算w。并判断其是否大于0。 条件，受P℉℃算法[的启发，在之前的基础上对ω， 其中，g=arg min,ex{V}。如果w,>0则回到2)， 做如下修改： 否则设置p*=PP=P-1并终止。 下面将介绍学习距离函数中权值ω：的算法，其 0:= 中ω，将采用如下方法初始化：在式(1)中ω：的约束 0,i∈p 条件下，令ω0=ω)=…=ω0，因此有ω0= 1/P。 算法2学习距离函数。 (14) 输入： 式中： 1)数据矩阵：X∈Rw; p={i:w:=0明 2)成对约束：(xy)其中，y={+1,-1: p={i:ω：>0} 3)参数：C、0: p表示所有使得ω：取正值的i的集合，相对应的p 输出：距离权值：ω；∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ 求 ｍｉｎ ω，β，ξ Ｌ（ω，β，ξ，α，λ） 对 α 的极大，即得对偶问题： ｍａｘ α １ ２ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ － １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) ＋ ∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ ｓ．ｔ．∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∑ ｎ ｋ ＝ １ αｋ ＝ θ αｋ ≥ ０，ｋ ＝ １，２，…，ｎ （１３） 将式（１３）的目标函数由求极大转换为求极小， 就得到下面与之等价的对偶最优化问题： ｍｉｎ α － １ ２ｐ ＋ １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ － １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ ＋ １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) － ∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ ｓ．ｔ．∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∑ ｎ ｋ ＝ １ αｋ ＝ θ αｋ ≥ ０，ｋ ＝ １，２，…，ｎ 如此，可以通过二次规划的求解方法得到最优 解 α ∗ ＝ ［α ∗ １ α ∗ ２ … α ∗ ｎ ］ Ｔ ，进而代入式（１２）得 到 ωｉ 的最优解： ω ∗ ｉ ＝ １ ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ ＋ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ 可以明显地观察到，即使成功的优化得到最优 解，也不能保证 ωｉ 完全满足式（２）中 ωｉ ≥ ０ 的约束 条件，受 ＰＦＣ 算法［１１ ］的启发，在之前的基础上对 ωｉ 做如下修改： ωｉ ＝ ０，ｉ ∈ ｐ － １ ｐ ＋ － １ ｐ ＋ ∑ ｊ∈ｐ ＋∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｊ，ｋ ＋ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ，ｉ ∈ ｐ ＋ ì î í ï ï ïï （１４） 式中： ｐ － ＝ ｛ｉ：ωｉ ＝ ０｝ ｐ ＋ ＝ ｛ｉ：ωｉ ＞ ０｝ ｐ ＋ 表示所有使得 ωｉ 取正值的 ｉ 的集合，相对应的 ｐ － 表示无法使 ωｉ 取正值的 ｉ 的集合，２ 个集合 ｐ ＋ 和 ｐ － 的大小分别使用 ｐ ＋ 和 ｐ － 来表示。 至此完成求解距离分量权值 ωｉ 的目标，求解集 合 ｐ ＋ 和 ｐ － 的算法描述将在下一小节给出。 最大几何间隔 ρ ‖ω‖ 中的 ρ 亦可在求解权值 ωｉ 的过程中求得。 与原始 ＳＶＭ 类似，目标函数（３） 的分离超平面为 ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ，ｋ － β） ＝ ρ ，即可得最大 函数间隔 ρ ＝ ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ，ｋ － β） 。 在求得最优解后 由式（９）可得 β 的最优解 β ∗ ＝ １ ２ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋ 进而可得 最大函数间隔 ρ ＝ ｙｋ（∑ ｐ ｉ ＝ １ ωｉ ∗ ｄｉ，ｋ － β ∗ ） 。 ２．２ 算法描述 本节将给出求解距离分量权值 ωｉ 的具体算法 步骤。 为了便于表示，将式（１４）简化： ωｉ ＝ ０，ｉ ∈ ｐ － １ ｐ ＋ ＋ ＣＶｉ，ｉ ∈ ｐ ＋ ì î í ï ï ïï （１５） 式中： Ｖｉ ＝ － １ ｐ ＋ ∑ ｊ∈ｐ ＋∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｊ，ｋ ＋ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ （１６） 由式（１６）观察可得，若想满足 ωｉ 为正值，则 Ｖｉ 需要足够大，且当 Ｖｉ 越大， ωｉ 为正值的几率就越大。 因此，求解集合 ｐ ＋ 和 ｐ － 的算法总结如下。 算法 １ 求解集合 ｐ ＋ 和 ｐ － 。 １）初始化： ｐ ＋ ０ ＝ ∅，ｐ － ０ ＝ ｛１，２，…，ｐ｝，ｈ ＝ ０； ２） ｈ ＝ ｈ ＋ １，ｐ ＋ ｈ ＝ ｐ ＋ ｈ－１ ＋ ｛ｉ｝，ｐ － ｈ ＝ ｐ － ｈ－１ － ｛ｉ｝， 其 中， ｉ ＝ ａｒｇ ｍａｘｉ∈ｐ － ｈ－１ ｛Ｖｉ｝ ； ３）通过式（１４） 计算 ωｇ 并判断其是否大于 ０。 其中， ｇ ＝ ａｒｇ ｍｉｎｉ∈ｐ ＋ ｈ ｛Ｖｉ｝ 。 如果 ωｇ ＞ ０ 则回到 ２）， 否则设置 ｐ ＋ ＝ ｐ ＋ ｈ－１ ，ｐ － ＝ ｐ － ｈ－１ 并终止。 下面将介绍学习距离函数中权值 ωｉ 的算法，其 中 ωｉ 将采用如下方法初始化：在式（１）中 ωｉ 的约束 条件下，令 ω （０） １ ＝ ω （０） ２ ＝ … ＝ ω （０） ｐ ，因此有 ω （０） ｉ ＝ １ ／ ｐ。 算法 ２ 学习距离函数。 输入： １）数据矩阵： Ｘ ∈ Ｒ ｄ×Ｎ ； ２）成对约束： ｘ ｋ ａ，ｘ ｋ ａ，ｙｋ ( ) 其中， ｙｋ ＝ ｛ ＋ １， － １｝； ３）参数： Ｃ、θ ； 输出：距离权值： ω ； ·８４６· 智 能 系 统 学 报 第 １０ 卷