丁 躍

(重慶大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 401331)

0 引 言

支持向量機(jī)[1](Support Vector Machine)是建立在核函數(shù)基礎(chǔ)上的機(jī)器學(xué)習(xí)算法,在模式識(shí)別、機(jī)器學(xué)習(xí)等領(lǐng)域有著廣泛的應(yīng)用.不同的核函數(shù)，同一核函數(shù)不同核參數(shù),對(duì)于支持向量機(jī)泛化能力的影響是顯著的[2],在一些復(fù)雜的問(wèn)題中,特別是數(shù)據(jù)具有異構(gòu)性,樣本分布不平坦,單一核函數(shù)已經(jīng)難以滿足問(wèn)題的需要,為此Lanckriet提出來(lái)多核學(xué)習(xí)算法。多核學(xué)習(xí)算法通過(guò)將這些核函數(shù)組合起來(lái)學(xué)習(xí),得到更高的泛化能力。

關(guān)于多核學(xué)習(xí)算法的主要研究成果有Lanckriet等[3]首先使用了半正定規(guī)劃技術(shù),完成了對(duì)于核矩陣的學(xué)習(xí)問(wèn)題，但是其在大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)的學(xué)習(xí)上面，學(xué)習(xí)效率較低Sonnenburg 等[6]在多核函數(shù)錐組合的基礎(chǔ)上,提出了一種通用而更有效的多核學(xué)習(xí)算法。 該方法將多核學(xué)習(xí)問(wèn)題改寫(xiě)為一種半無(wú)限線性規(guī)劃(Semi-infinite linear program, SILP) 形式, 新的規(guī)劃形式可以在標(biāo)準(zhǔn)的SVM 應(yīng)用問(wèn)題中,利用成熟的線性規(guī)劃方法進(jìn)行求解. Rakotomamonjy等提出的簡(jiǎn)單多核學(xué)習(xí) (SimpleMKL)[7]，引入新的混合范數(shù)將候選核函數(shù)的權(quán)系數(shù)包含在標(biāo)準(zhǔn)支持向量機(jī)的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化中，目標(biāo)函數(shù)轉(zhuǎn)化為凸的、且光滑函數(shù)，在權(quán)系數(shù)的確定中，使用梯度下降算法，SimpleMKL，相比于其他算法獲得更高的效率。

以上的多核學(xué)習(xí)算法對(duì)于所有輸入樣本，核函數(shù)的權(quán)系數(shù)是一樣的，這無(wú)形中對(duì)樣本進(jìn)行了一種平均處理，局部多核學(xué)習(xí)算法(LMKL)利用選通函數(shù)，局部的選用了合適的核函數(shù)，但是，LMKL有以下的不足：LMKL算法所選用的選通函數(shù)有嚴(yán)重的參數(shù)參數(shù)沉余，其使用選通函數(shù)l1范數(shù)的形式，提高了核函數(shù)間的稀疏性，但是削弱了核函數(shù)間的“互補(bǔ)”作用。為此，本文提出了改進(jìn)的局部多核學(xué)習(xí)算法(ILMKL),針對(duì)選通函數(shù)的參數(shù)沉余的問(wèn)題，在其目標(biāo)函數(shù)中加入正則項(xiàng)，并且使用選通函數(shù)的lp范數(shù)形式。

1 局部多核學(xué)習(xí)算法

(1)

其核函數(shù)Km的權(quán)系數(shù)不再是常數(shù)，而是依賴于輸入空間的樣本數(shù)據(jù)，此時(shí)對(duì)應(yīng)的判別函數(shù)為

(2)

(3)

(4)

2 改進(jìn)的局部多核學(xué)習(xí)算法(ILMKL)

在式(1)的合成核構(gòu)造中，定義新的選通函數(shù)ηm(x)為

(5)

其中vm≥0為參數(shù)，這里選用的是選通函數(shù)的lp范數(shù)形式,有助于增強(qiáng)各個(gè)核函數(shù)間的“互補(bǔ)”作用,提高識(shí)別率。但是，不論是是式(3)還是式(5)中的選通函數(shù)都有參數(shù)“冗余”，可以看出，對(duì)于優(yōu)化問(wèn)題式(4),若v是上述問(wèn)題的解，那么對(duì)于任意的常數(shù)v0,v+v0還是上述問(wèn)題的解.所以它們都有參數(shù)“冗余”，為此，ILMKL算法在目標(biāo)函數(shù)中加入了正則項(xiàng)||v||F,這里使用的是Frobenius范數(shù).根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則。其學(xué)習(xí)問(wèn)題可以表示為

(6)

為繼承傳統(tǒng)多核學(xué)習(xí)中不斷迭代標(biāo)準(zhǔn)支持向量機(jī)代碼的優(yōu)勢(shì)，將上述優(yōu)化問(wèn)題表示為

(7)

其中

這里參數(shù)u是用來(lái)平衡參數(shù)“冗余”和J(v)的值，對(duì)于固定參數(shù)v，將J(v)轉(zhuǎn)化為其拉格朗日對(duì)偶形式：

(9)

(10)

在給定參數(shù)v下，由于W(v)的解α*存在并且是唯一的[1]，于是W(v)對(duì)參數(shù)v的梯度向量存在，且等于如下形式：

2.1 ILMKL算法描述

ILMKL算法以T(v)前后兩次迭代的值小于設(shè)定的值ε或者迭代次數(shù)達(dá)到最大值為停機(jī)準(zhǔn)則，算法具體描述如下：

1) 設(shè)選定候選核函數(shù)K1,K2,…,KM和參數(shù)u和p，參數(shù)v初始值v0，最大迭代次數(shù)G，迭代停止條件ε，迭代次數(shù)k=0；利用v0計(jì)算選通函數(shù)ηm(x)m=1,2，…，M，進(jìn)而得到初始合成核K0；

2) 求解以Kk為核函數(shù)的標(biāo)準(zhǔn)支持向量機(jī)，計(jì)算目標(biāo)函數(shù)值Tk(v)，梯度向量：

3) 線性搜索最優(yōu)步長(zhǎng)μk∈[0,+∞]；

4) 迭代vk+1=vk-μk*Dk(v)；

5) 計(jì)算Tk+1(v)，若|Tk+1(v)-Tk(v)|≤ε，或者k=G，則算法停止，否則，k=k+1，轉(zhuǎn)到步驟2)。

2.2 ILMKL算法復(fù)雜度分析

ILMKL算法的的時(shí)間復(fù)雜度主要來(lái)源于以下幾個(gè)方面：所使用標(biāo)準(zhǔn)支持向量機(jī)的復(fù)雜度，算法的迭代次數(shù).本文使用的的是SMO算法[13]，其算法復(fù)雜度為在O(n1.2)與O(n2.2)之間，而其迭代次數(shù)受樣本數(shù)據(jù)和迭代步長(zhǎng)的選擇的影響，假設(shè)迭代次數(shù)為k,所以算法的復(fù)雜度介于O(kn1.2)與O(kn2.2)之間。

3 實(shí)驗(yàn)分析

3.1 模擬數(shù)據(jù)實(shí)驗(yàn)

為驗(yàn)證ILMKL算法的有效性，本文模擬4個(gè)二元正態(tài)分布，從每個(gè)正態(tài)分布中產(chǎn)生100個(gè)數(shù)據(jù)，4個(gè)二元正態(tài)分布的均值分別為(-3,1)，(-1,-2.5)，(1,1)，(3,-2.5)，協(xié)方差矩陣分別為(0.8,0,0,2)，(0.8,0,0,4)，(0.8,0,0,2)，(0.8,0,0,4)，將第1和第3個(gè)二元正態(tài)分布作為一類(lèi)，第1和第3個(gè)二元正態(tài)分布作為另一類(lèi).這里使用典型的傳統(tǒng)多核學(xué)習(xí)算法SimpleMKL、局部多核學(xué)習(xí)算法LMSVM、和本文提出的ILMKL算法，分別對(duì)兩類(lèi)數(shù)據(jù)進(jìn)行分類(lèi)學(xué)習(xí)。選用3個(gè)線性核(KL-KL-KL),ILMKL算法選取參數(shù)u=(0,0.1,1),選取p=(1,2,3)，由于知道數(shù)據(jù)的真實(shí)分布，所以貝葉斯分類(lèi)器是最優(yōu)得分類(lèi)器[14]。分別繪制了個(gè)算法的分類(lèi)界面與貝葉斯分類(lèi)器比較。

圖1 簡(jiǎn)單多核學(xué)習(xí)

圖2 局部多核學(xué)習(xí)

圖3 改進(jìn)的局部多核學(xué)習(xí)

圖1、圖2、圖3中，虛線表示貝葉斯分別類(lèi)界面，實(shí)線表示各個(gè)算法的分類(lèi)界面，黑點(diǎn)表示支持向量。將圖2和圖3與圖1比較，明顯地顯示了局部多核學(xué)習(xí)的優(yōu)勢(shì)。由于選用的核函數(shù)是3個(gè)線性核，傳統(tǒng)多核學(xué)習(xí)算法SimpleMKL做出的類(lèi)界面只是單純的直線，局部多核學(xué)習(xí)可以通過(guò)選通函數(shù)局部的結(jié)合3個(gè)線性核，達(dá)到非線性分類(lèi)的能力.比較圖3和圖2，ILMKL分類(lèi)界面與虛線擬合的更好，從儲(chǔ)存支持向量的個(gè)角度，ILMKL算法和LMKL算法的支持向量的個(gè)數(shù)最少。

表1 實(shí)驗(yàn)所采用的數(shù)據(jù)集

3.2 UCI數(shù)據(jù)實(shí)驗(yàn)

將ILMKL算法、單核SVM[1]、LMKL算法[4]、SimpleMKL[7]算法應(yīng)用到UCI數(shù)據(jù)庫(kù)上，驗(yàn)證ILMKL算法的有效性，實(shí)驗(yàn)選取 9個(gè)UCI數(shù)據(jù)集，數(shù)據(jù)集的信息如表1所示。

實(shí)驗(yàn)所選用的核函數(shù)是線性核函數(shù)KL，二項(xiàng)式核函數(shù)Kp(x,x′)=(1+xTx′)2，高斯核函數(shù)KG,其中單核SVM分別使用上面的3個(gè)核函數(shù)計(jì)算，高斯核函數(shù)的參數(shù)σ采用以下方式估計(jì)：計(jì)算每一個(gè)樣本與其他樣本的最小歐式距離，將所有這些歐氏距離的平均作為核參數(shù)σ。采用交叉驗(yàn)證確定單核SVM、ILMKL、LMKL、SimpleMKL算法的懲罰系數(shù)C值，其中C∈{0.1,1,10}，選取ILMKL中參數(shù)μ∈{0.01,0.1,1,10},p∈{1,2,3,4,5,6,7,8}，表2記錄了10重交叉驗(yàn)證的平均準(zhǔn)確率，和多核支持向量機(jī)存儲(chǔ)的平均支持向量數(shù)，所有實(shí)驗(yàn)結(jié)果，都是重復(fù)10次的平均結(jié)果。

表2 實(shí)驗(yàn)結(jié)果

從分類(lèi)精度的角度，LMKL，SimpleMKL算法基本相同，ILMKL算法分類(lèi)精度最高，其中ILMKL(p>1)要比ILMKL(p=1)分類(lèi)精度更高，這是因?yàn)楹撕瘮?shù)間不同的核映射有“互補(bǔ)”的作用，而使用1范數(shù)(p=1)會(huì)提高核函數(shù)間的稀疏性，這樣會(huì)消弱核函數(shù)間的“互補(bǔ)”作用，進(jìn)而影響分類(lèi)精度。與單核SVM比較，ILMKL算法在這些數(shù)據(jù)集上都高于精度最高的單核SVM，SimpleMKL算法在除Heart，Iris數(shù)據(jù)集以外，其他數(shù)據(jù)集上都要高于精度最高的單核SVM，LMKL算法在除Iris Ionosphere數(shù)據(jù)集以外，其他數(shù)據(jù)集上都要高于精度最高的單核SVM，這點(diǎn)也表明多核學(xué)習(xí)算法有更好的分類(lèi)精度。從存儲(chǔ)的支持向量上來(lái)看，ILMKL算法存儲(chǔ)的支持向量最少。

4 結(jié) 論

本文提出改進(jìn)的局部多核學(xué)習(xí)算法，針對(duì)LMKL算法中選通函數(shù)的參數(shù)沉余的問(wèn)題，在其目標(biāo)函數(shù)中加入正則項(xiàng)，并且使用選通函數(shù)的p范數(shù)形式。對(duì)比實(shí)驗(yàn)結(jié)果表明：ILMKL有更高的泛化能力和存儲(chǔ)更少的支持向量.未來(lái)的工作，將進(jìn)一步提升該算法的泛化才能和效率，并將考慮將該方法推廣到多分類(lèi)或回歸等其他領(lǐng)域。

參考文獻(xiàn)：

[1] VAPNIK V. The Nature of Statistical Learning Theory[M]. NewYork：Springer-Verlag, 1995

[2] LANCKRIET C, VAPNIK V,BOUSQUET O, Choosing multipleparameters for supp-ort vector machines[J]. Machine Learning, 2002,46(1): 131-159

[3] LANCKRIET G, CRISTIANINI N, BARTKETT P, GHAOUI L,JORDAN M. Learning the kern-el matrix with semi-definite programming[J].Machine LearningResearch,2004,5(1): 27-72

[5] BACH F, Lanckriet G G, Jordan M I. Multiple kernel learning, conic duality, andthe SMO algorithm[C]. In: Proceedings of the 21st International Conference on Machine Learning Ban, Canada: ACM, 2004. 41-48

[6] SONNENBURG S, RATSCH G, SCHAFER C. A general and efficient multiple kernel learning algorithm[J]. Advances in Neural Information Processing Systems. 2006,18(1):1 273-1 280

[7] RAKOTOMAMONJY A, BACH F, CANU S, GRANDVALET Y.Simple MKL[J].Machine Learnin-g Research, 2008, 9(11): 2491-2521

[8] 汪洪橋,孫富春. 多核學(xué)習(xí)方法[J]. 自動(dòng)化學(xué)報(bào),2010,26(8):1037-1050