APP下载

基于牛顿梯度优化的弹性多核学习*

2018-01-27何佳佳陈秀宏

传感器与微系统 2018年2期
关键词:范数集上正则

何佳佳,陈秀宏,田 进,万 月

(江南大学 数字媒体学院,江苏 无锡 214122)

0 引 言

多核学习(multiple kernel learning,MKL)[1]是机器学习领域的热门研究课题,已成功应用于生物信息学[2]、计算机视觉[3]、数据挖掘等方向。与利用单一核的核方法相比,MKL通过组合多个基本核函数代替单一核函数,使得核函数的应用更为灵活;由于其不依赖样本数据,故具有更强的可解释性和可扩展性。

本文提出了一种基于牛顿梯度优化方法的弹性MKL (Newton gradient optimization method for elastic MKL,NO-EMKL)算法,根据弹性理论,将混合范数作为正则化项加入目标函数,使得MKL在实现自适应目的的同时能平衡解的稀疏性,采用二阶牛顿梯度下降法提高MKL的效率。结果表明:以上方法能计算多核学习的黑塞(Hessian)矩阵,获得的下降方向比快速下降法更好,进一步减少了算法的迭代次数。

1 MKL框架

给定数据集{(xi,yi)}ni=1,xi∈χ,χ为输入空间;yi表示数据xi的标签,对二分类问题,yi∈{+1,-1}。核方法通过映射φ:χ→h将数据变换到Hilbert空间h中,核函数定义为h中的内积,表明可通过核函数k(x,z)隐式地计算映射函数φ在h中的内积k(x,z)=〈φ(x),φ(z)〉,避免了维数灾难。在MKL中,核函数通常表示为多个基本核函数的加权相加或相乘。

根据Bach分块理论[4],MKL即为寻找以下问题的最优解

w.r.t.ω=(ω1,…,ωM)∈Rk1×…×RkM,

∀i∈{1,…,n}

(1)

MKL的决策函数为

f(z)=〈ω,z〉+b

(2)

式中μm为核函数的加权系数,可通过求解问题(1)的对偶形式获得。MKL分块阶段的l1范数将导致ω的稀疏性。

2 NO-EMKL

2.1 EMKL

多元线性回归的Lasso模型为

(3)

式中 ‖·‖为l2范数;‖·‖为l1范数。目标函数(3)第二项为正则化项,用来控制参数的稀疏性。Zou H等人[5]将式(3)中的正则项用混合范数代替以达到自适应调整稀疏性的目的,即考虑以下弹性优化模型

(4)

该模型通过正则化参数(λn,μn)调节l1范数项和l2范数项。

根据l1范数项的变分公式[6,7],并引入混合范数的正则项的弹性思想,得到以下EMKL模型

ω=(ω1,…,ωM)∈Rk1×…×RkM,

ξi∈Rn,b∈R

(5)

式中θ为变量,0<θ<1,用于平衡稀疏性。

2.2 EMKL的牛顿梯度法

本文EMKL框架考虑的合成核K(xi,xj)是一些基本核km(xi,xj)的线性组合

(6)

(7)

(8)

(9)

文献[6]指出,仅需用简单的梯度下降法即可解决该凸优化问题,且收敛较快。本文在快速梯度下降的基础上引入二阶牛顿优化来求解问题(9)以进一步提高收敛速度。

记问题(7)的目标函数为J(α,d),对d和α使用交替法求解。对于给定的d,式(7)即为标准SVM式(8),设其解为α*,相应的支持向量集为sv;求解式(9),计算J(α*,d)关于d的梯度

(10)

为了获得二阶信息,在对gm求导时需计算∂α*/∂dm。由于所有支持向量均处于最大间隔边界面上[9],故有

(11)

(12)

(13)

(14)

(15)

(16)

约束项保证了任何解都落在区间[d,d+s]中,从而满足原始约束式(9)。

3 实验与结果分析

为了验证本文NO-EMKL方法的有效性,与标准核SVM和基于快速梯度下降法的Simple MKL进行了实验比较。

3.1 参数设置和实验数据

Simple MKL和NO-EMKL实验中所使用的基本核函数包括:10个高斯核函数,其带宽σ,分别取0.5,1,2,5,7,10,12,15,17,20;3个多项式核函数,其中a=1,指数b的取值分别为1,2,3。对每个基本核函数分别计算核矩阵。通常核SVM中用到的单核为高斯核函数,其带宽σ取10;超参数C=100。本文讨论的是二分类问题,选取加州大学欧文分校提供的标准测试数据集(University of California,Irvine,UCI)中8种2类别数据集进行实验,这些数据集的构成如表1所示。

表1 UCI数据集

3.2 正则项参数θ选取

根据本文NO-EMKL算法,采用5折交叉验证的方法为表2中的8个UCI数据集分别选取合适的正则项参数θ。θ的取值分别为{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9};将每个数据集中的样本数据分别分成5组,轮流将其中4组作为训练集而另外1组作为测试集,并分别计算分类精度,取5次实验结果的均值作为对应θ的分类结果,其对应关系如表2所示。对最高分类精确度进行标粗,如果不同的θ值对应着相同的最高分类精确度,选择其中一个标粗。

表2 数据分类精确度与θ关系 %

从表2可以看出,不同的θ值影响着NO-EMKL算法的分类精度,且不同数据集的最高分类精度对应的θ值一般也不相同,说明每个数据集均具有最合适的θ值。NO-EMKL算法可以根据数据集调节到最合适的θ值,使模型的分类效果达到最好。

3.3 分类精确度比较

根据表2,分别为8个UCI数据集选取最合适的θ值用于NO-EMKL算法,8个数据集Sonar,Thyroid,Liver,Ionosphere,Breast,Blood,Diabetis及Image对应的θ取值分别为0.3,0.6,0.8,0.6,0.5,0.2,0.7及0.3。随机选取8个UCI数据集中50 %的数据作为训练集,剩下的数据作为测试集;训练数据归一化为均值0及单位方差的数据,测试数据使用训练数据的均值和方差进行归一化。每种算法在每个数据集上运行10次求平均;对于Simple MKL和NO-EMKL,选择对偶间隙小于0.01或迭代次数大于500次作为终止条件;最后得到的3种算法对数据集的平均分类精度如表3所示,对分类精度最高的数据进行标粗。

表3 3种算法的分类精度比较 %

从表3中可以看出,单核的SVM分类结果较差,本文提出的NO-EMKL算法在大部分的数据集上(除了数据集Diabetis)相较其他两种算法有较好的分类精度,Simple MKL的分类结果处于两者之间。

3.4 迭代次数比较

Simple MKL和NO-EMKL在8个数据集上进行实验,并比较当达到停止迭代条件时迭代次数和对偶间隙的关系,如图1所示。可以看出:在开始阶段,Simple MKL的对偶间隙较NO-EMKL算法下降快,但是接近最优解时,收敛速度明显低于NO-EMKL,甚至出现了振荡,并导致迭代次数大幅度增加,从而增加了计算成本。由此可见,采用二阶牛顿梯度下降法的效果明显好于快速梯度下法。

图1 NO-EMKL和 Simple MKL收敛速度

3.5 训练时间比较

所考虑的训练时间不包含核矩阵的生成时间。由于标准SVM不需要对核系数进行学习,所以,NO-EMKL和Simple MKL 2种算法在8个数据集上的训练时间,在各数据集上运行10次后的平均训练时间如表4所示,正则项参数θ的选取根据表2确定。因此,Simple MKL算法相对于NO-EMKL长,尤其当数据集较大时,训练时间的差异更明显,这主要是因为在计算权系数时,两种方法所采用的梯度下降法不同,导致收敛速度不同,进一步说明了NO-EMKL算法的性能更优。

表4 训练时间 s

4 结束语

针对稀疏多核学习算法在产生权系数和收敛速度上的问题,提出了NO-EMKL算法。该算法根据弹性理论而在目标函数中引入弹性项,使得多个基本核函数能自适应地融合,从而能更好地保留有用信息;而在算法优化阶段,算法采用二阶牛顿梯度下降法,使算法在更少的迭代次数内即可达到收敛。实验结果表明:NO-EMKL算法相对于Simple MKL和SVM不仅具有更好的分类精度,还具有较快的收敛速度。

[1] Lanckriet G R G,Cristianini N,Bartlett P,et al.Learning the kernel matrix with semidefinite programming[J].The Journal of Machine Learning Research,2004,5:27-72.

[2] Damoulas T,Girolami M A.Probabilistic multi-class multi-kernel learning:On protein fold recognition and remote homology detection[J].Bioinformatics,2008,24(10):1264-1270.

[3] Duan L,Tsang I W,Xu D,et al.Domain transfer svm for video concept detection[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2009:1375-1381.

[4] Bach F R,Lanckriet G R G,Jordan M I.Multiple kernel lear-ning,conic duality,and the SMO algorithm[C]∥Proceedings of the twenty-first International Conference on Machine Learning,ACM,2004:6.

[5] Zou H,Hastie T.Regularization and variable selection via the elastic net[J].Journal of the Royal Statistical Society:Series B(Sta-tistical Methodology),2005,67(2):301-320.

[6] Alain R,Francis R B,Phane C,et al.Simple MKL[J].Journal of Machine Learning Research,2008,9:2491-2521.

[7] Schölkopf B,Smola A J.Learning with kernels:Support vector machines,regularization, optimization,and beyond[M].Boston:MIT Press,2002.

[8] Bousquet O,Herrmann D J L.On the complexity of learning[C]∥Advances in Neural Information Processing Systems 15:Procee-dings of the 2002 Conference,MIT Press,2003:415.

[9] Chapelle O,Rakotomamonjy A.Second order optimization of kernel parameters[C]∥Proc of the NIPS Workshop on Kernel Learning:Automatic Selection of Optimal Kernels,2008:87.

猜你喜欢

范数集上正则
J-正则模与J-正则环
π-正则半群的全π-正则子半群格
Virtually正则模
向量范数与矩阵范数的相容性研究
Cookie-Cutter集上的Gibbs测度
链完备偏序集上广义向量均衡问题解映射的保序性
分形集上的Ostrowski型不等式和Ostrowski-Grüss型不等式
剩余有限Minimax可解群的4阶正则自同构
基于加权核范数与范数的鲁棒主成分分析
含零阶齐次核的Hilbert型奇异重积分算子的有界性及范数