梁萬路

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

1 引言

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

傳統(tǒng)的實現(xiàn)方法由于算法復(fù)雜、存儲要求大、收斂速度慢等弊端無法滿足實際應(yīng)用的要求。支持向量機(jī)優(yōu)化問題具有對支持向量的分類等價于對整個樣本集的分類,優(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)化兩個樣本點(diǎn)的最小子集。但是這些方法對支持向量數(shù)目的約減并未過多關(guān)注,算法的稀疏性[9]有待進(jìn)一步提高。

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

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

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

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

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

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

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

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

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

2.3 稀疏SMO算法

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

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

3 實驗結(jié)果及分析

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

表1 部分benchmark數(shù)據(jù)庫實驗結(jié)果

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

4 結(jié)語

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

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

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

[3]邊肇祺.張學(xué)工,等.模式識別[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