基于牛頓梯度優(yōu)化的彈性多核學(xué)習(xí)*

何佳佳，陳秀宏，田 進(jìn)，萬(wàn) 月

(江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122)

0 引 言

多核學(xué)習(xí)(multiple kernel learning，MKL)[1]是機(jī)器學(xué)習(xí)領(lǐng)域的熱門(mén)研究課題，已成功應(yīng)用于生物信息學(xué)[2]、計(jì)算機(jī)視覺(jué)[3]、數(shù)據(jù)挖掘等方向。與利用單一核的核方法相比，MKL通過(guò)組合多個(gè)基本核函數(shù)代替單一核函數(shù)，使得核函數(shù)的應(yīng)用更為靈活；由于其不依賴(lài)樣本數(shù)據(jù)，故具有更強(qiáng)的可解釋性和可擴(kuò)展性。

本文提出了一種基于牛頓梯度優(yōu)化方法的彈性MKL (Newton gradient optimization method for elastic MKL，NO-EMKL)算法，根據(jù)彈性理論，將混合范數(shù)作為正則化項(xiàng)加入目標(biāo)函數(shù)，使得MKL在實(shí)現(xiàn)自適應(yīng)目的的同時(shí)能平衡解的稀疏性，采用二階牛頓梯度下降法提高M(jìn)KL的效率。結(jié)果表明:以上方法能計(jì)算多核學(xué)習(xí)的黑塞(Hessian)矩陣，獲得的下降方向比快速下降法更好，進(jìn)一步減少了算法的迭代次數(shù)。

1 MKL框架

給定數(shù)據(jù)集{(xi,yi)}ni=1，xi∈χ，χ為輸入空間；yi表示數(shù)據(jù)xi的標(biāo)簽，對(duì)二分類(lèi)問(wèn)題，yi∈{+1,-1}。核方法通過(guò)映射φ:χ→h將數(shù)據(jù)變換到Hilbert空間h中，核函數(shù)定義為h中的內(nèi)積，表明可通過(guò)核函數(shù)k(x,z)隱式地計(jì)算映射函數(shù)φ在h中的內(nèi)積k(x,z)=〈φ(x),φ(z)〉，避免了維數(shù)災(zāi)難。在MKL中，核函數(shù)通常表示為多個(gè)基本核函數(shù)的加權(quán)相加或相乘。

根據(jù)Bach分塊理論[4]，MKL即為尋找以下問(wèn)題的最優(yōu)解

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

?i∈{1,…,n}

(1)

MKL的決策函數(shù)為

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

(2)

式中μm為核函數(shù)的加權(quán)系數(shù)，可通過(guò)求解問(wèn)題(1)的對(duì)偶形式獲得。MKL分塊階段的l1范數(shù)將導(dǎo)致ω的稀疏性。

2 NO-EMKL

2.1 EMKL

多元線性回歸的Lasso模型為

(3)

式中 ‖·‖為l2范數(shù);‖·‖為l1范數(shù)。目標(biāo)函數(shù)(3)第二項(xiàng)為正則化項(xiàng)，用來(lái)控制參數(shù)的稀疏性。Zou H等人[5]將式(3)中的正則項(xiàng)用混合范數(shù)代替以達(dá)到自適應(yīng)調(diào)整稀疏性的目的，即考慮以下彈性?xún)?yōu)化模型

(4)

該模型通過(guò)正則化參數(shù)(λn,μn)調(diào)節(jié)l1范數(shù)項(xiàng)和l2范數(shù)項(xiàng)。

根據(jù)l1范數(shù)項(xiàng)的變分公式[6,7]，并引入混合范數(shù)的正則項(xiàng)的彈性思想，得到以下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)

文獻(xiàn)[6]指出，僅需用簡(jiǎn)單的梯度下降法即可解決該凸優(yōu)化問(wèn)題，且收斂較快。本文在快速梯度下降的基礎(chǔ)上引入二階牛頓優(yōu)化來(lái)求解問(wèn)題(9)以進(jìn)一步提高收斂速度。

記問(wèn)題(7)的目標(biāo)函數(shù)為J(α,d)，對(duì)d和α使用交替法求解。對(duì)于給定的d，式(7)即為標(biāo)準(zhǔn)SVM式(8)，設(shè)其解為α*，相應(yīng)的支持向量集為sv；求解式(9)，計(jì)算J(α*,d)關(guān)于d的梯度

(10)

為了獲得二階信息，在對(duì)gm求導(dǎo)時(shí)需計(jì)算?α*/?dm。由于所有支持向量均處于最大間隔邊界面上[9]，故有

(11)

(12)

(13)

(14)

(15)

(16)

約束項(xiàng)保證了任何解都落在區(qū)間[d,d+s]中，從而滿足原始約束式(9)。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文NO-EMKL方法的有效性，與標(biāo)準(zhǔn)核SVM和基于快速梯度下降法的Simple MKL進(jìn)行了實(shí)驗(yàn)比較。

3.1 參數(shù)設(shè)置和實(shí)驗(yàn)數(shù)據(jù)

Simple MKL和NO-EMKL實(shí)驗(yàn)中所使用的基本核函數(shù)包括：10個(gè)高斯核函數(shù)，其帶寬σ,分別取0.5，1，2，5，7，10，12，15，17，20；3個(gè)多項(xiàng)式核函數(shù)，其中a=1，指數(shù)b的取值分別為1，2，3。對(duì)每個(gè)基本核函數(shù)分別計(jì)算核矩陣。通常核SVM中用到的單核為高斯核函數(shù)，其帶寬σ取10；超參數(shù)C=100。本文討論的是二分類(lèi)問(wèn)題，選取加州大學(xué)歐文分校提供的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集(University of California,Irvine,UCI)中8種2類(lèi)別數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，這些數(shù)據(jù)集的構(gòu)成如表1所示。

表1 UCI數(shù)據(jù)集

3.2 正則項(xiàng)參數(shù)θ選取

根據(jù)本文NO-EMKL算法，采用5折交叉驗(yàn)證的方法為表2中的8個(gè)UCI數(shù)據(jù)集分別選取合適的正則項(xiàng)參數(shù)θ。θ的取值分別為{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}；將每個(gè)數(shù)據(jù)集中的樣本數(shù)據(jù)分別分成5組，輪流將其中4組作為訓(xùn)練集而另外1組作為測(cè)試集，并分別計(jì)算分類(lèi)精度，取5次實(shí)驗(yàn)結(jié)果的均值作為對(duì)應(yīng)θ的分類(lèi)結(jié)果，其對(duì)應(yīng)關(guān)系如表2所示。對(duì)最高分類(lèi)精確度進(jìn)行標(biāo)粗，如果不同的θ值對(duì)應(yīng)著相同的最高分類(lèi)精確度，選擇其中一個(gè)標(biāo)粗。

表2 數(shù)據(jù)分類(lèi)精確度與θ關(guān)系 %

從表2可以看出，不同的θ值影響著NO-EMKL算法的分類(lèi)精度，且不同數(shù)據(jù)集的最高分類(lèi)精度對(duì)應(yīng)的θ值一般也不相同，說(shuō)明每個(gè)數(shù)據(jù)集均具有最合適的θ值。NO-EMKL算法可以根據(jù)數(shù)據(jù)集調(diào)節(jié)到最合適的θ值，使模型的分類(lèi)效果達(dá)到最好。

3.3 分類(lèi)精確度比較

根據(jù)表2，分別為8個(gè)UCI數(shù)據(jù)集選取最合適的θ值用于NO-EMKL算法，8個(gè)數(shù)據(jù)集Sonar，Thyroid，Liver，Ionosphere，Breast，Blood，Diabetis及Image對(duì)應(yīng)的θ取值分別為0.3，0.6，0.8，0.6，0.5，0.2，0.7及0.3。隨機(jī)選取8個(gè)UCI數(shù)據(jù)集中50 %的數(shù)據(jù)作為訓(xùn)練集，剩下的數(shù)據(jù)作為測(cè)試集；訓(xùn)練數(shù)據(jù)歸一化為均值0及單位方差的數(shù)據(jù)，測(cè)試數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)的均值和方差進(jìn)行歸一化。每種算法在每個(gè)數(shù)據(jù)集上運(yùn)行10次求平均；對(duì)于Simple MKL和NO-EMKL，選擇對(duì)偶間隙小于0.01或迭代次數(shù)大于500次作為終止條件；最后得到的3種算法對(duì)數(shù)據(jù)集的平均分類(lèi)精度如表3所示，對(duì)分類(lèi)精度最高的數(shù)據(jù)進(jìn)行標(biāo)粗。

表3 3種算法的分類(lèi)精度比較 %

從表3中可以看出，單核的SVM分類(lèi)結(jié)果較差，本文提出的NO-EMKL算法在大部分的數(shù)據(jù)集上(除了數(shù)據(jù)集Diabetis)相較其他兩種算法有較好的分類(lèi)精度，Simple MKL的分類(lèi)結(jié)果處于兩者之間。

3.4 迭代次數(shù)比較

Simple MKL和NO-EMKL在8個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并比較當(dāng)達(dá)到停止迭代條件時(shí)迭代次數(shù)和對(duì)偶間隙的關(guān)系，如圖1所示?？梢钥闯觯涸陂_(kāi)始階段，Simple MKL的對(duì)偶間隙較NO-EMKL算法下降快，但是接近最優(yōu)解時(shí)，收斂速度明顯低于NO-EMKL，甚至出現(xiàn)了振蕩，并導(dǎo)致迭代次數(shù)大幅度增加，從而增加了計(jì)算成本。由此可見(jiàn)，采用二階牛頓梯度下降法的效果明顯好于快速梯度下法。

圖1 NO-EMKL和 Simple MKL收斂速度

3.5 訓(xùn)練時(shí)間比較

所考慮的訓(xùn)練時(shí)間不包含核矩陣的生成時(shí)間。由于標(biāo)準(zhǔn)SVM不需要對(duì)核系數(shù)進(jìn)行學(xué)習(xí)，所以,NO-EMKL和Simple MKL 2種算法在8個(gè)數(shù)據(jù)集上的訓(xùn)練時(shí)間，在各數(shù)據(jù)集上運(yùn)行10次后的平均訓(xùn)練時(shí)間如表4所示，正則項(xiàng)參數(shù)θ的選取根據(jù)表2確定。因此，Simple MKL算法相對(duì)于NO-EMKL長(zhǎng)，尤其當(dāng)數(shù)據(jù)集較大時(shí)，訓(xùn)練時(shí)間的差異更明顯，這主要是因?yàn)樵谟?jì)算權(quán)系數(shù)時(shí)，兩種方法所采用的梯度下降法不同，導(dǎo)致收斂速度不同，進(jìn)一步說(shuō)明了NO-EMKL算法的性能更優(yōu)。

表4 訓(xùn)練時(shí)間 s

4 結(jié)束語(yǔ)

針對(duì)稀疏多核學(xué)習(xí)算法在產(chǎn)生權(quán)系數(shù)和收斂速度上的問(wèn)題，提出了NO-EMKL算法。該算法根據(jù)彈性理論而在目標(biāo)函數(shù)中引入彈性項(xiàng)，使得多個(gè)基本核函數(shù)能自適應(yīng)地融合，從而能更好地保留有用信息；而在算法優(yōu)化階段，算法采用二階牛頓梯度下降法，使算法在更少的迭代次數(shù)內(nèi)即可達(dá)到收斂。實(shí)驗(yàn)結(jié)果表明：NO-EMKL算法相對(duì)于Simple MKL和SVM不僅具有更好的分類(lèi)精度，還具有較快的收斂速度。

[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.