一種改進的局部多核學習算法

丁 躍

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

0 引 言

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

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

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

1 局部多核學習算法

(1)

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

(2)

(3)

(4)

2 改進的局部多核學習算法(ILMKL)

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

(5)

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

(6)

為繼承傳統(tǒng)多核學習中不斷迭代標準支持向量機代碼的優(yōu)勢，將上述優(yōu)化問題表示為

(7)

其中

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

(9)

(10)

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

2.1 ILMKL算法描述

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

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

2) 求解以Kk為核函數(shù)的標準支持向量機，計算目標函數(shù)值Tk(v)，梯度向量：

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

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

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

2.2 ILMKL算法復雜度分析

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

3 實驗分析

3.1 模擬數(shù)據(jù)實驗

為驗證ILMKL算法的有效性，本文模擬4個二元正態(tài)分布，從每個正態(tài)分布中產生100個數(shù)據(jù)，4個二元正態(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個二元正態(tài)分布作為一類，第1和第3個二元正態(tài)分布作為另一類.這里使用典型的傳統(tǒng)多核學習算法SimpleMKL、局部多核學習算法LMSVM、和本文提出的ILMKL算法，分別對兩類數(shù)據(jù)進行分類學習。選用3個線性核(KL-KL-KL),ILMKL算法選取參數(shù)u=(0,0.1,1),選取p=(1,2,3)，由于知道數(shù)據(jù)的真實分布，所以貝葉斯分類器是最優(yōu)得分類器[14]。分別繪制了個算法的分類界面與貝葉斯分類器比較。

圖1 簡單多核學習

圖2 局部多核學習

圖3 改進的局部多核學習

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

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

3.2 UCI數(shù)據(jù)實驗

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

實驗所選用的核函數(shù)是線性核函數(shù)KL，二項式核函數(shù)Kp(x,x′)=(1+xTx′)2，高斯核函數(shù)KG,其中單核SVM分別使用上面的3個核函數(shù)計算，高斯核函數(shù)的參數(shù)σ采用以下方式估計：計算每一個樣本與其他樣本的最小歐式距離，將所有這些歐氏距離的平均作為核參數(shù)σ。采用交叉驗證確定單核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重交叉驗證的平均準確率，和多核支持向量機存儲的平均支持向量數(shù)，所有實驗結果，都是重復10次的平均結果。

表2 實驗結果

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

4 結 論

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

參考文獻：

[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] 汪洪橋,孫富春. 多核學習方法[J]. 自動化學報,2010,26(8):1037-1050