摘 要:  在机器学习领域,核方法是解决非线性模式识别问题的一种有效手段.目前,用多核学习方法代替传统的单核学习已经成为一个新的研究热点,它在处理异构、不规则和分布不平坦的样本数据情况下,表现出了更好的灵活性、可解释性以及更优异的泛化性能.结合有监督学习中的多核学习方法,提出了基于 L p 范数约束的多核半监督支持向量机(semi-supervised support vector machine,简称 S 3 VM)的优化模型.该模型的待优化参数包括高维空间的决策函数f m 和核组合权系数  m .同时,该模型继承了单核半监督支持向量机的非凸非平滑特性.采用双层优化过程来优化这两组参数,并采用改进的拟牛顿法和基于成对标签交换的局部搜索算法分别解决模型关于 f m 的非平滑及非凸问题,以得到模型近似最优解.在多核框架中同时加入基本核和流形核,以充分利用数据的几何性质.实验结果验证了算法的有效性及较好的泛化性能.

关键词:  半监督;支持向量机;拟牛顿法;多核学习;半监督

支持向量机在传统的监督学习中,分类器通过对大量有标记的训练样本进行学习,从而建立模型用于预测未知数据的标记.在实际应用中,如文本文类、 图像检索等等,收集大量未标记的样本很容易,但对这些样本进行正确的标记,则需要花费很大的代价,这使得监督学习受到一定的限制.近年来,结合了监督学习和无监督学习特点的半监督学习方法得到了广泛关注.半监督学习主要研究样本在只有少量被标记的情况下,通过使用大量未标记样本来获得具有理想性能和推广能力的学习器.它通常基于两种假设 [1] :  一是聚类假设,即同一聚类中的样本点很可能具有同样的类别标记.这个假设要求决策边界所穿过的应当是数据点较为稀疏的区域.  二是流形假设,即高维中的数据存在着低维的特性.它要求处于一个很小的局部邻域内的样本具有相似的性质,反映了决策函数的局部平滑性.半监督学习对于减少标注代价、提高分类器泛化性能具有非常重大的实际意义.半监督支持向量机(semi-supervised support vector machine,简称 S 3 VM)是一种基于聚类假设的半监督学习方法,其优化目标是利用已标记和未标记的样本构建分类器,使其包含的分类间隔能够最大地分隔原始已标记和未标记样本,新找到的最优分类边界满足对原始未标记样本的分类具有最小泛化误差.S 3 VM 最初是应用于文本分类的直推式支持向量机 TSVM [2] .

它实际上是一个非凸非平滑函数的优化问题.为了解决这一问题,研究者提出了各种各样的方法 [3] ,常见的有:局部组合搜索法 [2] 、梯度下降法 [4] 、凹凸法 [5] 、确定性退火方法 [6] 、连续优化方法 [7] 、半定规划方法 [8] 、分支定界法 [9] 等等.这些算法根据参数特点的不同可以分为两大类:一种是基于组合的 S 3 VM,另一种是连续方法的 S 3 VM.当样本数据为非线性可分时,需要使用核技巧(kernel trick),通过一个非线性映射  :XH 把输入数据映射到高维再生核希尔伯特特征空间 H,然后在新的特征空间里寻找线性决策边界.核函数把非线性映射和特征空间中两个向量的内积两者结合起来,使得非线性映射  不需要明确指定,而高维空间中的线性超平面可以由所有训练样本与测试样本在特征空间中的内积的线性组合表示,从而有效避免了维数灾难 [10] .这种采用核技巧的方法是解决非线性模式识别问题的一种有效方法.自从支持向量机(support vectormachine,简称 SVM)学习方法被提出来以后,核方法已经成功地应用到模式识别的诸多方面,如回归估计 [11] 、概率密度估计 [12] 、模式分类 [13] 以及子空间分析 [14] 等等.但是这些方法绝大多数都是基于单个特征空间映射的单核方法.在不同的应用场合,核函数的选择和参数的设置不同,往往使得模型的性能表现有很大的差异;并且对于高维、包含有异构信息、分布不平坦以及不规则的样本数据,采用单核进行映射对样本的处理不一定合适.于是,一些学者提出了基于核组合的多核学习算法 [1518] .构造多核学习模型首先要考虑多核组合方法,常见的有线性组合方法 [13] 、扩展合成方法 [19] 、非平稳组合方法 [16] 及局部多核学习方法 [20] 等等,其中,线性凸组合多核学习是最常见的一种.大量研究结果表明,多核学习方法是一种灵活性更强的基于核的学习方法,用它代替传统的单核学习,可以大幅度提高模型的可解释性和泛化性能 [21] .多核线性组合学习过程就是求取核组合权系数的过程.针对如何获取核组合的权系数,目前已经有了多种有效的学习手段,如 Boosting 多核组合模型学习方法 [22] 、超核学习方法 [17] 、半定规划多核学习方法 [23] 、二次约束型二次规划多核学习方法 [21] 以及简单多核学习方法 [15] 等等.以上的所有多核学习方法对权系数的约束条件都是||  ||≤1(即 L 1 约束),最终得到的是权系数的稀疏解,即核组合中多数核的权系数为 0.稀疏核组合的好处是模型易于解释,易于处理.它表明:不相关的或代价较大的核应该从模型中去掉,以减少冗余,提高运算效率.但稀疏解可能会导致模型有用信息的丢失和泛化性能变差.

有研究表明,稀疏核组合在性能上很可能还不如直接使用非加权和核组合mmK K   的标准 SVM [24] .因此,Kloft 等人提出了一种非稀疏的多核学习方法 [25] ,通过对权系数施加 L 2 范数约束,得到权系数的非稀疏解.相对于 L 1 约束, L 2 约束的多核学习有更强的抗噪声能力和更好的鲁棒性.随后,Kloft 等人又将 L 2 范数约束推广到任意 L p 范数约束 [26,27] ,其中, p >1,以进一步增强模型的泛化性能,并对 L p 范数约束的收敛特性进行了讨论 [28] .S 3 VM 学习算法是基于聚类假设的,通常在具有这种结构的数据集上表现有较好的分类精度,但是对于具有流形结构特征的数据集以及数据包含有多个子类的问题,考虑了数据几何性质的 LapSVM [29] 往往表现更为出色.

事实上,任何一种半监督学习算法都是在特定假设条件下有较好的性能,没有证据表明,基于一种假设的算法就一定优于基于另外一种假设的算法.而组合两种假设,在 S 3 VM 中考虑数据本身的几何特征,可以使算法得到一定的改善 [3,30] .本文结合传统的 S 3 VM 学习以及多核学习的理论和方法,提出了基于 L p 范数约束的多核 S 3 VM 学习模型( L p -MKL-S 3 VM),在多核框架中同时学习基本核和流形核,以实现两种假设的结合.通过对核组合系数  施加 p范数约束,得到  的非稀疏解,以提高 S 3 VM 的可解释性和泛化性能.本文的模型继承了 S 3 VM 的非凸非平滑特性.我们采用一种改进的拟牛顿法 [31] 和成对标签交换的局部搜索法来解决其非凸非平滑问题,并将提出的算法应用在二分类问题上,在人工数据集和真实数据集上进行仿真,通过实验证明了算法的有效性和较好的泛化性能.

本文第 1 节概要介绍 S 3 VM 的基本形式.第 2 节介绍一种改进的拟牛顿法(用于解决模型非平滑问题).第 3节提出基于 L p 范数约束的多核 S 3 VM( L p -MKL-S 3 VM)的优化模型.第 4 节推导出 L p -MKL-S 3 VM 的求解过程.第 5 节是本文算法与其他算法的实验分析.最后是结论和展望.

1 半监督支持向量机(S 3 VM)

为了引导出 L p -MKL-S 3 VM 模型,首先介绍 S 3 VM 的优化问题.考虑二分类问题,输入数据集为 D ={ x 1 , x 2 ,…, x l+u },不失一般性,设数据集的前 l 个为已标记样本1{ , } li ix y ,y i =1, 紧接着是 u 个未标记样本 , 其中 ,l<<u,l+u=n 且 x i R d . 通常 ,S 3 VM 解决如下目标函数的最小化问题 :2 *1 1( , ) || || ( , ( )) (| ( )|)2l l uH i i ii i lJ f b f C V y g x C U g x     (1)公式 (1) 右边第 1 项定义了一个标准 SVM, 超参数 C 和 C * 用于平衡已标记样本和未标记样本的拟合误差 .为避免出现将所有未标记样本分配到同一类的极端情况 , 最小化公式 (1) 需要满足平衡约束条件 :11max(0, ) ,nii ly ru 其中 ,r 为未标记数据中正样本所占比例 . 对于未标记数据而言 ,r 是未知的 , 通常通过已标记数据中正样本所占的比例进行计算 , 也可以利用具体分类问题的先验知识来设置 .式 (1) 中 ,y i =sign(g(x i )) 表示第 i 个样本的类别标签 , 取值为 +1 或 1.U 和 V 通常采用如下的损失函数 :(1) V(y i ,g(x i ))=max(0,1y i g(x i )), 用于度量已标记样本的真实类别标签 y i 与计算值 g(x i ) 之间的偏差 ;(2)1 | ( )|, | ( )| 1(| ( )|) ,0,i iig x g xU g x   其他用于对未标记样本被错误分类后实施惩罚 .决策函数定义为 g(x)=f(x)+b, 其中 , 标量 b 为偏差项 , 为了简化计算 , 本文中省略了该项 ;f 是再生核希尔伯特空间 H 中的函数 . 对于非线性可分的样本数据 , 首先通过 “ 核技巧 ” 将数据映射到髙维再生核希尔伯特空间 H 中 ,然后在 H 中构建线性决策边界 . 设  :XH 为一个映射 ,k(x,y)=  (x) T  (y) 为 H 对应的核 , 一旦采用了适当的核 k, 就隐含定义了原始样本到髙维空间 H 的映射函数  , 根据再生核希尔伯特空间的再生属性 , 有 :f(x i )=f,k(x i ,),于是 , 公式 (1) 可写成2 *1 1( ) || || ( , ( , )) (| ( , )|) 函数 V 和 U 的函数曲线图分别如图 1(a) 和图 1(b) 所示 . 由图可知 , 目标函数 (2) 是非凸 ( 图 1(a)) 、非平滑 ( 图1(b)) 的 .Fig.1 Characteristics of loss functions V and U图 1 损失函数 V 和 U 的特征2 一种改进的拟牛顿法 subBFGS第 3 节推导出的 L p -MKL-S 3 VM 的优化函数继承了公式 (2) 的非凸非平滑特性 .

本文采用文献 [31] 中提出的一种改进拟牛顿法 (subBFGS) 来解决函数的非平滑问题 , 这里首先对该方法做简要介绍 .拟牛顿法是一种求解非线性优化问题的有效方法 , 具有超线性收敛性 , 用不包含二阶导数的矩阵来近似牛顿法中 Hessian 矩阵的逆 . 根据构造近似矩阵的方法不同 , 有不同的拟牛顿法 , 常见的有 BFGS 公式和 LBFGS公式 .拟牛顿法只能优化平滑的目标函数 , 但是在机器学习领域 , 很多目标函数在某些点是非平滑的 , 如公式 (2) 中的损失函数 V 在 yf(x)=1 处是非平滑的 ( 如图 1(a) 所示 ), 但是目标函数在这些点的次梯度 g 总是存在 . 对于平滑函数 , 负梯度方向始终是函数的下降方向 ; 但是对于非平滑函数 , 在非平滑点的任意负次梯度方向不一定是函数的下降方向 , 从而导致拟牛顿法失效 . 文献 [31] 提出的 subBFGS 方法通过利用束方法 (bundle method) 的束搜索(bundle search) 产生下降方向 p 的迭代过程 , 以寻找非平滑点确切的下降方向 . 其基本思想如下 :给定一个平滑目标函数 J:R d R 及当前迭代  t R d , 构造一个局部二次型 :11( ) ( ) ( )2T Tt t t tQ p J p B p J p     (3)其中 , 正定矩阵 B t  0 是函数 J 的 Hessian 矩阵的近似 ,J 是 J 的梯度 . 将二次型公式 (3) 改为如下形式 :Q t (p)=J(  t )+M t (p)  (4)1( )1( ) sup2tT Tt tg JM p p B p g p  (5)通过最小化 Q t (p) 可以导出  t 的迭代公式 , 这等价于最小化 M t (p), 即1( )1min ( ) min sup2dtT Tt tp Rg JM p p B p g p    (6)通过一个迭代过程 , 最小化 M t (p) 的凸下界来渐进逼近 M t (p). 第 i 次迭代时 ,M t (p) 的凸下界为( ) 1 ( )1( ) sup2i T i Tt tj iM p p B p g p ≤(7)其中 ,i,jN,g (i) J(  t ). 给定一个迭代 p (i) , 公式 (7) 的下界通过计算( 1) ( )( )argsupti T ig Jg g p 而逐渐收紧 , 使得( ) ( 1)( ) ( ) ( ),i i dt t tM p M p M p p R  ≤ ≤ 成立       ≤ ≤(8)则( ) ( ) 111argmin ( ) argmin2s.t. ,..., ( ),d di i Tt t tp R p RTk t ip M p p B pg g J g p          ≤(9)我们的目标是寻找一个次梯度方向 p,使得g 1 ,…,g k J(  t ),有 0Tig p≤ 成立,subBFGS 从当前迭代的任意次梯度 g 和给定的下降方向 p(最开始不一定是真实的下降方向)开始,产生 p 的迭代过程,最终找到确切的下降方向,具体算法见文献[31].3 基于 L p 范数约束的多核 S 3 VM(L p -MKL-S 3 VM)本文考虑多核线性组合形式,给定 M 个不同特征映射  m :XH m ,m=1,…,M,H m 对应的再生核为 k m ,我们的目标是学习这 M 个核的线性组合,即1( , ) ( , ),Mi j m m i jmk x x k x x   M 是基本核总个数,  m 为第 m 个核的权系数,是待优化参数.在多核学习情况下,决策函数定义为1( ) ( )Mmmf x f x  (10)则目标函数公式(2)在多核学习的情况下定义为如下形式:2*1 1 1 1 1( , ) || || , ( , ) ( , )2mM l M l u Mm m m H i m m i m m im i m i l mJ f f C V y f k x C U f k x                            (11)当 f m =0 时 , 公式 (11) 右边的第 1 项是不可微的 , 非平滑部分包含了第 1 项和第 3 项 , 根据文献 [26] 提出的基于L p 范数约束的监督学习优化代价函数 , 将公式 (11) 简化为如下形式 :( )2 *1 1 1 1 11 11( , ) || || , ( ,.) ( ,.)20, 0 1s.t. ,, 0mm iM l M l u Mm m m H i m m i m m im i m i l mml u MTmi l mJ f f C V y f k x C U f k xt tK f ru                            约定其他(12)本文对  m 施加了 L p 范数约束 , 即 1/11,pMpmm≤ p ≥ 1,  m ≥ 0. 当 p=1 时 , 得到的是  m 稀疏解 ; 当 p>1 时 , 得到的是  m 非稀疏解 .

我们称该优化模型为 L p -MKL-S 3 VM.4 优化 L p -MKL-S 3 VM 模型直接优化目标函数 J(f m ,  m ) 很难收敛 , 本文采用了双层优化过程对参数进行交替优化 [26,30,3234] . 把参数分成两组 : 第 1 组为 f m , 第 2 组为核混合系数  m . 首先固定  m , 则目标函数是关于 f m 的非凸非平滑函数 , 本文采用subBFGS 算法、退火方法和成对标签交换的局部搜索算法分别解决非平滑和非凸问题 ; 然后固定 f m , 目标函数是关于  m 的非线性单调函数 , 在 L p 范数约束条件下 , 我们采用一阶导数求极值方法进行求解 . 这两个过程交替进行 , 直到满足事先设定的收敛准则 . 下面介绍具体的求解过程 .4.1 求解f m固定  m , 目标函数是关于 f m 的最小化问题 minJ(f m ). 为了使用 subBFGS 算法 , 首先设 E,R,W 分别表示样本集中被错误分类、被分在边界区域和被正确分类的样本的下标集合 , 即1{1,2,..., }:1 ( , ) 0Mi m m imE i l u y f k x               (14)1{1,2,..., }:1 ( , ) 0Mi m m imW i l u y f k x        (15)则关于 f m 的导数 ( 次微分 ) 为* *( ) ( ) ( ) ( )1 1 1, 1,l l u l l uT T T Tm i i m i i i m i i i m i i i m ii i l i i R i l i Rm mJf C y K C y K w C y K C y Kf                       (16)其中 ,*( ) ( )1, 1,1,, [0,1],0,l l uT Tm i i m i i i m i ii i E i l i Emi Ew f C y K C y K i Ri W                 ,K m 表示第 m 个核对应的核矩阵 ,K m(i) 表示 K m 的第 i 列 .在 subBFGS 算法中 , 对于给定的下降方向 p, 需要计算该方向与次微分内积的上确界 , 即*( ) ( )( )1, 1,sup sup inf( )mTl l uT T T Ti i m i i i m ig J fi i R i l i RmJg p p w p C y K C y K pf                   (17)对于一个给定的方向 p, 当 iR 时 , 有  i [0,1], 因此可以通过下面的约定得到( )sup :mTg J fg p( )( )0, 01, 0Ti m ii Ti m iy K py K p  ≥(18)得到了确切的下降方向 p 以后 , 需进行一维线性搜索确定最佳的步长  , 通过求解下面的最小化问题得到 :0 0argmin ( ) argmin ( )mJ f p        (19)下面给出求解 f m 的算法描述 .算法 1 .  求解 f m .输入 : 样本集 (x 1 ,y 1 ),…,(x l ,y l ),(x l+1 ),…,(x n ); 参数  ,C,*ˆ, C  m ,Hessian 矩阵 B m =I, 当前的 f m .输出 :f m .算法步骤 :1.* 5 *ˆ10 ; C C2. WHILE* *ˆC C ≤2.1.  针对已标记和未标记的样本 , 利用 subBFGS 求解函数 J(f m );2.2. t=1;2.3. WHILE (t ≤ u/2)IF  在未标记样本中 ,x i ,x j 满足临时标签互换的条件则交换两个样本 i,j 的临时标签 , 并且 t=t+1;ELSE BREAK;END IFEND WHILE2.4. C * =10C * ;END WHILE3. RETURN f m ;公式 (12) 中的超参数 C * 需要事先设定 , 用于反映未标记样本在优化模型中的重要性 . 目标函数的非凸性质使得拟牛顿法得到的 f m 将陷入局部最优解 .S 3 VM 的求解本身是一个 NP 问题 , 因此我们的目标是要获取全局次优解 .

在算法 1 中 , 首先让 C * 从一个比较小的值开始逐步增长 , 目的是避免目标函数在优化过程中过快陷入局部最优解 , 同时 , 第 2.3 步循环实现的是针对当前的局部最优解 f m , 通过成对标签交换方法进行局部搜索 , 在未标记样本集合中 , 如果存在一对临时标签分别为 +1 和 1 的样本 x i ,x j , 则互换这对临时标签后可以降低目标函数的值 ,即满足如下条件 :      ( ) ( )( ) ( )1 11 11, 1,1, 1,m i m jm i m jM MT Ti m j mm mM MT Ti m j mm mLoss y K f Loss y K fLoss y K f Loss y K f             (20)则将这两个样本的临时标签互换 , 通过这种成对临时标签互换的局部搜索算法可得到目标函数的次优解 .4.2 求解   m对于  m , 本文采用与文献 [26] 相同的求解方法 .固定 f m , 此时要求解的是如下关于  m 函数的最小化问题 : 2 *1 1 1 1 11/11( ) || || , ( , ) ( , )2s.t. 1,  0mM l M l u Mm m H i m m i m m im i m i l mmpMpm mmJ f C V y f k x C U f k x                       ≤ ≥(21)最小化公式 (21) 等价于 : 21/2 *1: 01 1 1 1 11min || || , ( ) ( )2 2mm mM l M l u MpMpm H i m i m i iim i m i l mmf C V y f x C U f x                                   ≥(22)其中 ,  >0. 对  m 求导并令其等于 0, 得到 : 22 12 1|| || 0,  1,...,2mpMp pm H m iimf m M     (23)进一步将上式转化为如下的优化条件 :2/( 1), 1,..., :mpm mHm M f        (24)由于 f m 0, 1/11.pMpii≤ 当 1/11pMpii时 , 能得到 minJ(  m ) 的最优解 . 将公式 (24) 带入 1/11,pMpii得到 :2 /( 1)1ipp pMiiHf     (25)将公式 (25) 代入公式 (24), 得到 :    1/2/( 1) 2 /( 1)1|| || || ||m ipMp p pm m H i Hif f  (26)4.3 算法描述最后 , 我们得到 L p -MKL-S 3 VM 的算法描述如下 :算法 2 . L p -MKL-S 3 VM 优化算法 .输入 : 样本集 (x 1 ,y 1 ),…,(x l ,y l ),(x l+1 ),…,(x n ).输出 :f m ,  m .算法步骤 :1.  初始化 :M= 核的个数 ,f m =O, 1/ ;pmM  2.  利用已标记样本学习多核线性组合的 SVM, 得到初始的 f m ,  m ,m=1,…,M;3.  对于未标记的样本集 X u (X u =x l+1 ,…,x n ), 计算( )1,MTm i mmK f并按降序进行排序 ;4.  按正负样本的比例 r 给未标记样本赋值临时标签 +1 或 1;5. REPEAT固定  m , 利用算法 1 计算 f m , 直到 f m 收敛固定 f m , 利用公式 (26) 计算  m ;UNTIL   m 收敛或者满足其他收敛条件 .4.4 时间复杂度分析算法 1 、 算法 2 之间是属于嵌套关系 , 算法 1 可以在很少迭代次数内得到确切的下降方向 , 算法 2 的循环也可以在较少的次数内使  m 收敛 . 因此 , 算法 2 的时间复杂度体现在算法 1 的运算上 , 而算法 1 的时间复杂度体现在两个嵌套的循环 , 即时间复杂度为3S VM-subLBGFS( ( ))u switchesO n n n  , 其中 ,n u 为算法 1 中第 1 个循环的次数 ,n switches为成对标签互换次数 , 最多为 u/2 次 ,3S VM-subLBGFSn 为用 subLBGFS 算法求解 f m 的迭代次数 .

另外 , 在进行标签互换和计算 f m 时 , 都需要做( ) 1 m iMTmmK f运算 , 因此 , 总的时间复杂度还与核的个数 M 、输入样本集大小 l + u 有关 , 总的时间复杂度约为 O ( M ( l + u ) 3 ).文献 [30] 提出了一种基于 L 1 约束的多核半监督学习算法 , 并将该算法成功运用到 BCI 的数据分析 . 作者采用了 DC Programming 过程解决目标函数的非凸非平滑问题 , 通过对偶问题和梯度下降法求解核的组合系数 .函数 U 为 U (| g ( x i )|)= R s ( g ( x i ))+ R s ( g ( x i ))(1 s ), 其中 , R s ( g ( x i ))=max(0,1 y i g ( x i ))+max(0, s  y i g ( x i )). 这直接导致目标函数关于未标记样本被计算了 2 次 , 相当于未标记样本增加了 1 倍 , 从而算法的计算复杂度最坏情况下为O ( M ( l +2 u ) 3 ). 另外 , 该算法还增加了一个超参数 s .5 实验分析为了验证算法的性能 , 实验分别与一些有代表性的半监督学习算法进行比较 , 包括 S 3 VM light[2] ,LapSVM [29] ,S 3 VM CCCP[5] 及 TSVM-MKL [30] , 除 TSVM-MKL 外 , 其余的都是单核半监督学习算法 .S 3 VM light 通过解决一系列的SVM 问题来优化目标函数 , 利用成对标签交换来改善优化结果 , 每次迭代交换两个样本的标签 , 以满足所施加的正负样本平衡约束 .LapSVM 是一种基于流形学习的 SVM 扩展方法 . 它将基于图的拉普拉斯作为正则化项应用到半监督学习中 , 以此提高分类的准确性 .S 3 VM CCCP 使用 CCCP(concave-convex procedure) 方法来优化目标函数 , 将目标函数分解为一个凸函数和一个非凸函数 , 再通过迭代优化这两个函数 , 最终达到优化目标函数的目的 .TSVM-MKL 是一个半监督多核学习框架 , 采用与 S 3 VM CCCP 相同的方法来解决目标函数的非凸非平滑问题 ,该算法对权系数施加的是 L 1 约束 , 因此得到的是核组合的稀疏解 .我们分别在 3 组人工数据集 2MOONS,G241C,G241D 及 3 组真实数据集 COIL100,USPST,TEXT 上进行实验 . 其中 , 后 5 种数据集来自文献 [1]: G241C:241 维 , 该数据集具有聚类假设的结构 , 每类样本为 750 个 , 分别来自具有各向同性、 单位方差的两个高斯分布 . 在一个随机方向上 , 设置这两个高斯分布的中心点之间的距离为 2.5, 即 ||  1   2 ||=2.5, 在这个随机方向上的二维投影图如图 2(a) 所示 . G241D:241 维 , 具有易产生误导的聚类假设结构 , 从两个各向同性、单位方差的高斯分布中分别产生375 个点 ( 共 750 个点 ), 并且在一个随机方向上 , 两个高斯分布的中心点的距离为 6, 这些点构成 +1 类 ;1 类的产生方式和 +1 类相同 , 两类在另一个随机方向上的高斯分布中心点之间的距离为 2.5. 在两个随机方向上的二维投影图如图 2(b) 所示 . COIL100: 来自 COIL-100 图形数据库 , 该数据库共有 100 个对象 , 每个对象从 0~360 的水平方向旋转 ,每隔 5 度采集一副图片 , 则每个对象包含 72 副图像 , 图片大小为 128128 像素 . 先从 100 个对象中随机选择 24 个对象 ( 共 2472=1728 副图片 ), 划分为 +1 和 1 两类 , 每类 12 个对象 . 然后将图片按比例压缩为1616 像素 , 并随机删除每类中的 114 副图片 . 最后 , 随机选择 241 列并做一定的图像模糊处理 . USPST: 来自于美国邮政的手写数字 (0~9) 数据集 , 随机选择每个数字的 150 副图片 ,“2” 和 “5” 被分为 +1类 , 其余的为 1 类 , 与 COIL00 数据集类似 , 对该数据集进行了模糊处理 . 该数据集是非平衡的 , 同时具有聚类假设和流形假设的结构 .

 TEXT 数据集 : 用于文本分类的新闻组数据集 , 数据项是 0 或 1, 具有髙维稀疏的特性 . 实验中随机选择了5.1 参数设置超参数  =1, C = C * , 并在 [0 10 100 500] 上采用格点搜索选取最优参数 , r 取值为表 1 中实际正负样本的比例 ,LapSVM 算法的超参数  A 和  I 采用了文献 [1] 中的设置 . 实验使用的是高斯核 K ( x 1 , x 2 )=exp(|| x 1  x 2 || 2 /2 2 ),  的取值见表 2. 对于单核学习算法 , 采用 10 折交叉验证选择最优的  作为参数 . 为了利用样本数据分布的几何特征 , 两个多核学习算法中同时加入了带高斯权重的流形核 , 采用如下公式生成 :1( , ) ( , ) ( ) ,i jTi j i j x xk x x k x x K I MK MK  其中 , M =(  I /  A ) L p , L = D  W 为一个拉普拉斯矩阵 . 如果 x i 和 x j 为 K 近邻 (TEXT 的 K 取值为 50, 其余的为 5), 则W ij =exp(|| x i  x j || 2 /2 2 ); 否则 , Wij =0. D ii = W ij 为一个对角矩阵 . 核的总数为 6, 基本核和流形核各 3 个 .Table 1 Characteristics of datasets表 1 数据集的特征数据集  维数  样本 n  r  数据集  维数  样本 n  r2MOONS  2  200  0.5  COIL100  241  1 500  0.5G241C  241  1 500  0.5  USPST  241  1 500  0.2G241D  241  1 500  0.5  TEXT  11 960  1 000  0.5Table 2 Settings of parameter  表 2  参数设置数据集   取值  数据集   取值2moons  (0.1,0.5,1)  COIL100  (0.5,2,4)G241C  (0.5,1,2)  USPST  (0.1,0.5,2)G241D  (0.5,1,2)  TEXT  (0.1,0.5,2)当约束范数 p 的取值为 1 时 , 部分权系数趋近于 0, 得到的是  的最稀疏解 ; 当 p 趋于  时 , 目标函数是关于mmK K   的非加权和多核学习 . 文献 [26,28] 通过实验表明 , 最优的性能通常介于两者之间 . 本文的实验中 p 最终取值为 5, 这样 ,  既有一定的稀疏度 , 又可以使较好的核能够保留较高的权系数 .5.2 实验结果(1) Transductive 实验训练集包含 l + u = n 个样本 , 通过预测未标记样本的标签来评估算法的性能 . 实验时 , l 分别取值为训练集的5% 和 10%. 将数据集分为 l / n 折 , 每次选取一折作为已标记样本 , 采用交叉验证统计各算法的平均误分类情况 , 最后一折已标记样本不足的 , 采用从训练集中随机选择补足 . 表 3 是平均误分类率及标准差(2) Inductive 实验将数据集分成训练集和测试集两部分 , 利用训练集中已标记和未标记样本训练分类器 , 以预测测试集样本标签的精度来评估算法的性能 . 其中 , 训练集和测试集参数设定见表 4, 训练集和测试集随机生成在这个实验中 , 我们选取了 3 种算法与本文的算法进行比较 , 已标记样本 l 分别取值为训练集的 5%,10%,15% 及 20%, 采用 l / n 折交叉验证训练分类器 , 最后一折已标记样本不足的 , 采用从训练集中随机选择补足 . 图3(a)~ 图 3(f) 是各算法在测试集上的分类情况从两种实验的结果可以看出 : 大多数情况下 , 本文提出的算法比其他算法具有有更好的分类精度 . 本算法通过在多核框架中加入流形核共同学习 , 避免了单一假设算法的局限 , 在一定程度上提高了算法在具有流形结构数据集上的学习性能 . 由于采用了相同的优化方法 ,S 3 VM CCCP 和 TSVM-MKL 的结果比较接近 ,TSVM-MKL 要略微优于 S 3 VM CCCP .LapSVM 算法在 G241C,G241D 以及 Text 上表现较差 , 但在两个图像数据集上表现却比较突出 , 这表明 LapSVM 适合处理具有流形结构特征的数据集 .在非平衡数据集 USPST 上 , 本文的算法要稍差于 LapSVM, 特别是在 l 较小的情况下 , 这种差距比较明显 .但是当 l 增加到 120 时 , 基本上达到了 LapSVM 的分类精度 . 这可能是流形核在 l 较小的情况下没有起到改善的作用 . 但本文的算法明显比 S 3 VM CCCP 和 TSVM-MKL 要好 .稀疏解会导致模型有用信息的丢失 , 这是因为  m 多数为 0 或者系数很低 , 从而使得可能有用的核 , 如混合的流形核被从模型中去掉 , 失去了其应有的改善作用 , 从而导致泛化性能变差 . 因此 , 实验数据表明 , L 1 范数约束的TSVM-MKL 算法在个别情况下出现了不如单核学习算法 S 3 VM CCCP 和 LapSVM 的情况 .相反的是 , 非稀疏解能够尽可能地保留模型中的有用核 , 模型倾向于选择最好的核 , 但对模型有改善作用的核也能够以一定的系数得到保留 , 从而提高了算法的性能 . 因此 , 本文提出的算法能够表现出比其他算法更好的分类性能 .

6 结论和展望

过去的相关研究主要集中在学习多核的凸组合及如何提高算法的执行效率 , 稀疏的核组合在实际应用中并不一定表现得比单核的要好 . 因此 , 本文结合传统的半监督支持向量机学习以及多核学习的理论和方法 , 提出了基于 L p 范数约束的多核半监督支持向量机学习模型 L p -MKL-S 3 VM, 并采用了一种改进的拟牛顿法和成对标签交换的局部搜索法来优化模型 . 在多核学习框架中 , 我们同时加入了基本核和流形核 , 以在学习过程中利用数据的几何属性 , 这样可以改善单一假设算法的局限 , 使算法在具有流行假设结构或聚类假设结构的数据集上都表现出较好的性能 . 人工数据集和真实数据集上的仿真实验结果验证了算法的有效性和较好的分类精度 . 将来可以把该算法扩展到多类问题上 , 研究流形核嵌入对算法性能的影响 . 另外 , p 的取值与数据集大小、数据的稀疏性、数据的几何性质以及核个数之间的关系 , 也是值得研究的内容 .

References :[1] Chapelle O, Scholkopf B, Zein A. Semi-Supervised Learning. London: MIT Press, 2006.[2] Joachims T. Transductive inference for text classification using support vector machines. In: Bratko I, Dzeroski S, eds. Proc. of the16th Int’l Conf. on Machine Learning (ICML’99). Morgan Kaufmann Publishers, 1999. 200209. http://www.informatik.uni-trier.de/~ley/db/conf/icml/icml1999.html[3] Chapelle O, Sindhwani V, Keerthi SS. Optimization techniques for semi-supervised support vector machines. Journal of MachineLearning Research, 2008,9:203233.[4] Chapelle O, Zent A. Semi-Supervised classification by low density separation. In: Cowell R, Ghahramani Z, eds. Proc. of the 10thInt’l Workshop on Artificial Intelligence and Statistics. Society for Artificial Intelligence and Statistics, 2005. 5764.http://eprints.pascal-network.org/archive/00001144/01/aistats2005.pdf[5] Collobert R, Sinz F, Weston J, Bottou L. Large scale transductive SVMs. Journal of Machine Learning Research, 2006,7(8):16871712.[6] V Sindhwani, S Keerthi, O Chapelle. Deterministic annealing for semi-supervised kernel machines. In: Cohen WW, Moore A, eds.Proc. of the 23rd Int’l Conf. on Machine Learning. ACM, 2006. 841848. http://dblp.uni-trier.de/rec/bibtex/conf/icml/SindhwaniKC06 [doi: 10.1145/1143844.1143950][7] Chapelle O, Chi M, Zien A. A continuation method for semi-supervised SVMs. In: Cohen WW, Moore A, eds. Proc. of the 23rdInt’l Conf. on Machine Learning. ACM, 2006. 185192. http://dblp.uni-trier.de/rec/bibtex/conf/icml/ChapelleCZ06 [doi: 10.1145/1143844.1143868] [8] De Bie T, Cristianini N. Semi-Supervised learning using semi-definite programming. In: Chapelle O, Schöelkopf B, Zien A, eds.Semi-supervised Learning. MIT Press, 2006.[9] Chapelle O, Sindhwani V, Keerthi S. Branch and bound for semi-supervised support vector machine. In: Schölkopf B, Platt J,Hoffman T, eds. Proc. of the 20th Annual Conf. on Neural Information Processing Systems. Cambridge: MIT Press, 2006. 217224.http://nips.cc/Conferences/2006/Committees/[10] Wang HQ, Sun FC, Cai YN, Chen N, Ding LG. On multiple kernel learning methods. Acta Automatica Sinica, 2010,36(8):10371050 (in Chinese with English abstract). [doi: 10.3724/SP.J.1004.2010.01037][11] Smola AJ, Scholkopf B. A tutorial on support vector regression. Statistics and Computing, 2004,14(3):199222. [doi: 10.1023/B:STCO.0000035301.49549.88][12] Kerm PV. Adaptive kernel density estimation. Stata Journal, 2003,3(2):148156.[13] Burges CJC. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1998,2(2):121167. [doi: 10.1023/A:1009715923555][14] SchÄolkopf B, Mika S, Smola A, Ratsch G, Muller KR. Kernel PCA pattern reconstruction via approximation pre-images. In: Proc.of the Int’l Conf. on Artificial Neural Networks. IEEE, 1998. 147152. http://openlibrary.org/books/OL367885M/ICANN_98[15] Rakotomamonjy A, Bach F, Canu S, Grandvalet Y. SimpleMKL. Journal of Machine Learning Research, 2008,9(11):24912521.[16] Lewis DP, Jebara T, Noble WS. Nonstationary kernel combination. In: Cohen WW, Moore A, eds. Proc. of the 23rd Int’l Conf. onMachine Learning. ACM, 2006. 553560. http://dblp.uni-trier.de/rec/bibtex/conf/icml/LewisJN06 [doi: 10.1145/1143844.1143914][17] Ong CS, Smola AJ, Williamson RC. Learning the kernel with hyperkernels. Journal of Machine Learning Research, 2005,6(7):10431071.[18] Yuan Y, Shao J, Wu F, Zhuang YT. Image annotation by the multiple kernel learning with group sparsity effect. Ruan Jian XueBao/Journal of Software, 2012,23(9):25002509 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4154.htm[doi: 10.3724/SP.J.1001.2012.04154][19] Lee WJ, Verzakov S, Duin RP. Kernel combination versus classifier combination. In: Haindl M, Kittler J, Roli F, eds. Proc. of the7th Int’l Workshop on Multiple Classifier Systems. LNCS 4472, Springer-Verlag, 2007. 2231. http://www.informatik.uni-trier.de/~ley/db/conf/mcs/mcs2007.html [doi: 10.1007/978-3-540-72523-7_3][20] GÄonen M, Alpaydm E. Multiple kernel machines using localized kernels. In: Proc. of the 4th Int’l Conf. on Pattern Recognition inBioinformatics. Sheffield: University of Sheffield, 2009. 110. http://www.springer.com/computer/bioinformatics/book/978-3-642-04030-6[21] Lanckriet BG, Jordan M. Multiple kernel learning, conic duality, and the SMO algorithm. In: Brodley CE, ed. Proc. of the 21stInt’l Conf. on Machine Learning. ACM, 2004. 4148. http://dblp.uni-trier.de/rec/bibtex/conf/icml/BachLJ04[22] Bennett KP, Momma M, Embrechts MJ. MARK: A boosting algorithm for heterogeneous kernel models. In: Proc. of the 8th ACM-SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Edmonton: New York: ACM, 2002. 2431. http://dl.acm.org/citation.cfm?id=775047&picked=prox&CFID=254452625&CFTOKEN=75751662 [doi: 10.1145/775047. 775051][23] Lanckriet GRG, Cristianini N, Bartlett P, Ghaoui LE, Jordan MI. Learning the kernel matrix with semi-definite programming. TheJournal of Machine Learning Research, 2004,5(1):2772.[24] Cortes C, Gretton A, Lanckriet G, Mohri M, Rostamizadeh A. Automatic selection of optimal kernels. In: Proc. of the NIPSWorkshop on Kernel Learning: Automatic Selection of Optimal Kernels. 2008. http://www.cs.nyu.edu/learning_kernels[25] Kloft M, Brefeld U, Laskov P, Sonnenburg S. Non-Sparse multiple kernel learning. In: Proc. of the NIPS Workshop on KernelLearning: Automatic Selection of Kernels. MIT Press, 2008. 14. http://eprints.pascal-network.org/archive/00004977/[26] Kloft M, Brefeld U, Sonnenburg S, Laskov P, Muller KR, Zien A. l p -Norm multiple kernel learning. Journal of Machine LearningResearch, 2011,12(5):953997.[27] Kloft M, Brefeld U, Sonnenburg S, Laskov P, Muller KR, Zien A. Efficient and accurate l p -norm multiple kernel learning. In:Bengio Y, Schuurmans D, Lafferty J, Williams CKI, Culotta A, eds. Proc. of the Conf. on Neural Information Processing Systems.MIT Press, 2009. 9971005. http://books.nips.cc/nips22.html[28] Kloft M, Blanchard G. On the convergence rate of l p -norm multiple kernel learning. Journal of Machine Learning Research, 2012,13(8):24652501. [29] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeledexamples. Journal of Machine Learning Research, 2006,6(11):23992434.[30] Tian XL, Gasso G, Canu S. A multiple kernel framework for inductive semi-supervised SVM learning. Neurocomputing, 2012(90):4658. [doi: 10.1016/j.neucom.2011.12.036][31] Yu J, Vishwanathan SVN, Gunter S, Schraudolph NN. A quasi-Newton approach to nonsmooth convex optimization problems inmachine learning. Journal of Machine Learning Research, 2010,11(5):11451200.[32] Chapelle O, Rakotomamonjy A. Second order optimization of kernel parameters. In: Proc. of the NIPS Workshop on KernelLearning: Automatic Selection of Kernels. 2008. http://www.citeulike.org/user/m8j/article/9501849[33] Xu Z, Jin R, King I, Lyu M. An extended level method for efficient multiple kernel learning. Advances in Neural InformationProcessing Systems, 2009,21:18251832.[34] Nath JS, Dinesh G, Ramanand S. On the algorithmics and applications of a mixed-norm based kernel learning formulation.Advances in Neural Information Processing Systems, 2009,22:844852.