一種基于FoBa算法思想的支持向量機(jī)稀疏SMO算法研究*

梁萬路

(解放軍炮兵學(xué)院5系43隊(duì) 合肥 230031)

1 引言

支持向量機(jī)[1～2](SVM)是由Vapnik所領(lǐng)導(dǎo)的貝爾實(shí)驗(yàn)室在1963年提出的一種非常有潛力的分類技術(shù),主要應(yīng)用于模式識(shí)別[3]領(lǐng)域。近年來,已取得了巨大的發(fā)展,成為機(jī)器學(xué)習(xí)領(lǐng)域一個(gè)標(biāo)準(zhǔn)的學(xué)習(xí)算法。當(dāng)前的研究主要集中在算法本身的改進(jìn)、拓展和算法實(shí)現(xiàn)上。隨著計(jì)算機(jī)技術(shù)的日益發(fā)展以及互聯(lián)網(wǎng)的日益普及,大規(guī)模,海量數(shù)據(jù)的處理能力成為分類器算法得以實(shí)現(xiàn)的現(xiàn)實(shí)要求。

傳統(tǒng)的實(shí)現(xiàn)方法由于算法復(fù)雜、存儲(chǔ)要求大、收斂速度慢等弊端無法滿足實(shí)際應(yīng)用的要求。支持向量機(jī)優(yōu)化問題具有對(duì)支持向量的分類等價(jià)于對(duì)整個(gè)樣本集的分類,優(yōu)化問題的解是樣本點(diǎn)的線性組合等特點(diǎn)?；谶@些特點(diǎn)人們提出了解析方法,主要包括分塊算法、分解算法、SMO[5～6]算法,共同的思想是循環(huán)迭代:將原來較大的二次優(yōu)化問題分解為若干規(guī)模較小的子二次優(yōu)化問題,按照某種優(yōu)化策略,通過反復(fù)優(yōu)化子問題,最終使結(jié)果收斂到原問題的最優(yōu)解。SMO算法是將分解算法的思想推向極致,每次迭代僅優(yōu)化兩個(gè)樣本點(diǎn)的最小子集。但是這些方法對(duì)支持向量數(shù)目的約減并未過多關(guān)注,算法的稀疏性[9]有待進(jìn)一步提高。

支持向量機(jī)的分類速度與支持向量的數(shù)目成正比。因此對(duì)支持向量數(shù)目進(jìn)行約減可以提高算法的分類速度。本文將FoBa算法[10]對(duì)特征進(jìn)行約減的思想引入SMO算法中,對(duì)訓(xùn)練產(chǎn)生的作用甚微的支持向量進(jìn)行約減,提出了稀疏SMO算法,在海量數(shù)據(jù)的處理上取得了很好的效果。

2 支持向量機(jī)的稀疏SMO算法

2.1 求解支持向量機(jī)的SMO算法

目前求解SVM最常用的策略的是SMO[3～4]。SMO的主要思想可以分為兩步:1)選擇包含兩個(gè)樣本點(diǎn)的工作樣本集;2)計(jì)算兩點(diǎn)解析解。

工作樣本集選則:當(dāng)且僅當(dāng)所有樣本點(diǎn)對(duì)應(yīng)的Lagrange乘子都符合KKT條件時(shí),α才為最優(yōu)解,所以SMO算法每次迭代挑選的兩個(gè)樣本點(diǎn)必須為破壞KKT條件最嚴(yán)重的。

在破壞KKT條件的點(diǎn)對(duì)上優(yōu)化問題能夠降低目標(biāo)函數(shù)值,且破壞程度越嚴(yán)重,目標(biāo)函數(shù)值下降的就越快。在 Rong-En Fan et.al方法[7～8]中使用二階梯度信息來求取最大化違法點(diǎn)對(duì),要求求解包含兩個(gè)樣本點(diǎn)的子問題。

兩點(diǎn)解析解:由于工作樣本集中只含有兩個(gè)樣本點(diǎn)且符合線性約束,故利用等式約束可以將其中一個(gè)用另一個(gè)表示出來,所以迭代過程中每一步的子問題的最優(yōu)解可以直接用解析的方法求出來。解析解如下:

2.2 自適應(yīng)FoBa算法思想

國(guó)內(nèi)知名學(xué)者 T.zhang在NIPS2008發(fā)表的文章[10]詳細(xì)分析了前向貪婪算法和反向貪婪算法在特征選擇方面的優(yōu)劣,認(rèn)為前向貪婪算法每次迭代都會(huì)增加一個(gè)使目標(biāo)函數(shù)減小最快的特征向量,保證能夠盡快迭代出全局最優(yōu)值,主要缺陷在于不能自行糾正前期運(yùn)算的錯(cuò)誤,反向貪婪算法把所有特征向量作為模型開始運(yùn)算,然后逐個(gè)刪除符合條件的特征向量,當(dāng)維數(shù)遠(yuǎn)大于樣本個(gè)數(shù)時(shí),計(jì)算代價(jià)非常高。在此基礎(chǔ)上,T.zhang提出了一種新的自適應(yīng)算法—FoBa算法。算法適當(dāng)使用反向貪婪算法消除前向算法中所犯的錯(cuò)誤,同時(shí)確保有用特征沒有被刪除。

2.3 稀疏SMO算法

通過對(duì)Foba算法的分析我們發(fā)現(xiàn),FoBa算法在每次前向步驟中都是尋找一個(gè)使目標(biāo)函數(shù)減少最快的特征并添加到特征集合中,這與SMO算法中尋找破壞KKT條件最嚴(yán)重的點(diǎn)對(duì),即使目標(biāo)函數(shù)值下降最快的點(diǎn)對(duì)并添加到支持向量集中相類似,它們的更新策略一致,只是目標(biāo)函數(shù)不同,解決的問題不同而已。借鑒 T.zhang提出的FoBa算法思想我們提出稀疏SMO算法,對(duì)訓(xùn)練產(chǎn)生的作用甚微的支持向量進(jìn)行約減,從而使算法具有更好的稀疏性,能夠更加快捷的處理海量數(shù)據(jù)問題。與FoBa算法不同的是,這里的稀疏指的是支持向量的稀疏而不是特征的稀疏。下面給出稀疏SMO算法的流程:

算法流程顯示只有當(dāng)目標(biāo)函數(shù)的增長(zhǎng)量不再大于前向步驟中目標(biāo)函數(shù)減小量的υ倍時(shí),反向步驟才得以運(yùn)行。這就意味著如果我們進(jìn)行了l次前向運(yùn)算,那么不管反向步驟運(yùn)行了多少次,此時(shí)目標(biāo)函數(shù)減少量至少為 lε/2,算法最多運(yùn)行2f(0)/ε,從而說明了算法程序是高效運(yùn)算。

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

實(shí)驗(yàn)計(jì)算機(jī)硬件環(huán)境為,CPU:英特爾(雙核)2.83GHz,內(nèi)存 4GB,WindowsXP操作系統(tǒng)。Benchmark數(shù)據(jù)庫(kù)是國(guó)際上驗(yàn)證機(jī)器學(xué)習(xí)算法性能的標(biāo)準(zhǔn)數(shù)據(jù)樣本集合,主要用于二分類、多分類、ONE-CLASS和聚類等算法的驗(yàn)證。本文選用Benchmark 數(shù)據(jù)庫(kù)中的 Banana、heart、Breast-Cancer、Thyroid、Titanic、German 作為驗(yàn)證稀疏SMO算法求解二分類SVM的數(shù)據(jù)庫(kù)。

表1 部分benchmark數(shù)據(jù)庫(kù)實(shí)驗(yàn)結(jié)果

所有的核函數(shù)均取為RBF核函數(shù)。采用交叉驗(yàn)證策略最優(yōu)化參數(shù)。每個(gè)實(shí)驗(yàn)交叉檢驗(yàn)100次。所謂交叉檢驗(yàn)就是將樣本按比例分為訓(xùn)練樣本和測(cè)試樣本,每次按固定比例從整個(gè)樣本集中抽取部分樣本進(jìn)行訓(xùn)練,剩余的用來測(cè)試,共進(jìn)行n次,稱為n次交叉檢驗(yàn),可以提高模型的魯棒性。文獻(xiàn)[11]中提出用核調(diào)用次數(shù)作為驗(yàn)證SVM算法性能的評(píng)價(jià)指標(biāo)。由于支持向量方法測(cè)試時(shí)間僅與內(nèi)積有關(guān),故可用核運(yùn)算代替內(nèi)積運(yùn)算,每進(jìn)行一次核運(yùn)算必進(jìn)行一次內(nèi)積運(yùn)算,因此可用核調(diào)用次數(shù)作為SMO算法性能的評(píng)價(jià)指標(biāo),這一指標(biāo)已被確認(rèn)為核算法研究的指標(biāo)性數(shù)據(jù)。Benchmark數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)表明稀疏SMO算法的訓(xùn)練錯(cuò)誤率與SMO算法基本上差不多,測(cè)試錯(cuò)誤率與SMO算法相比略有上升,而測(cè)試速度卻有顯著提高,因此我們有理由相信稀疏SK算法能夠解決海量數(shù)據(jù)的SVM分類問題。

4 結(jié)語(yǔ)

實(shí)驗(yàn)表明對(duì)于二分類SVM 問題,稀疏SMO算法與SMO算法相比訓(xùn)練錯(cuò)誤率不相上下,測(cè)試錯(cuò)誤率下降很少,而訓(xùn)練時(shí)間卻有明顯的降低。所以Sparsity SMO算法可以約減作用不大的支持向量,提高算法的稀疏性,從而提高算法的預(yù)測(cè)速度,在解決海量數(shù)據(jù)問題時(shí)具有一定的競(jìng)爭(zhēng)力。

[1]張學(xué)工.統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào),2000

[2]Cortes C,Vapnik.V.Support vector networks.Machine Learning,1995,20:273～297

[3]邊肇祺.張學(xué)工,等.模式識(shí)別[M].第二版.北京:清華大學(xué)出版社,2000

[4]Duda R O,Stork D G,ha rt P E.Pattern Classification(2nd)[M].New York.Wiley,2001

[5]Chih-Wei Hsu,Chih-Chung Chang,Chih-Jen Lin.A Pratical Guide to Support Vector Machines

[6]Chih-Chung Chang,Chih-Jen Lin.LIBSVM:a library for support vector machines,2001

[7]Pai-Hsuen chen,Rong-En Fan,Chih-Jen-Lin.A study on SMO-type decomposition method for support vector machines.Technical report,Department of Computer Science,National Taiwan University,2005

[8]Rong-En Fan,Pai-Hsuen chen,Chih-Jen-Lin.Working Set Selection Using Second Order Information for Training Support Vector Machines.Technical report,Department of Computer Science,National Taiwan U-niversity,2005

[9]Antoni B.Chan,Nuno Vasconcelos,Gert R.G.Lanckriet.Direct Convex Relaxations of Sparse SVM[C]//Proceedings of the 24 th International Conference on Machine Learning,Corvallis,OR,2007

[10]T.Zhong.Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models,NIPS,2008

[11]B.F.Mitchell,V.F.Dem'yanov,V.N.Malozemov.Finding the point of a polyhedron closet to the oringin.SIAM J.Contr,1974,12:19～26