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

梁萬路

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

1 引言

支持向量機[1～2](SVM)是由Vapnik所領導的貝爾實驗室在1963年提出的一種非常有潛力的分類技術,主要應用于模式識別[3]領域。近年來,已取得了巨大的發展,成為機器學習領域一個標準的學習算法。當前的研究主要集中在算法本身的改進、拓展和算法實現上。隨著計算機技術的日益發展以及互聯網的日益普及,大規模,海量數據的處理能力成為分類器算法得以實現的現實要求。

傳統的實現方法由于算法復雜、存儲要求大、收斂速度慢等弊端無法滿足實際應用的要求。支持向量機優化問題具有對支持向量的分類等價于對整個樣本集的分類,優化問題的解是樣本點的線性組合等特點。基于這些特點人們提出了解析方法,主要包括分塊算法、分解算法、SMO[5～6]算法,共同的思想是循環迭代:將原來較大的二次優化問題分解為若干規模較小的子二次優化問題,按照某種優化策略,通過反復優化子問題,最終使結果收斂到原問題的最優解。SMO算法是將分解算法的思想推向極致,每次迭代僅優化兩個樣本點的最小子集。但是這些方法對支持向量數目的約減并未過多關注,算法的稀疏性[9]有待進一步提高。

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

2 支持向量機的稀疏SMO算法

2.1 求解支持向量機的SMO算法

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

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

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

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

2.2 自適應FoBa算法思想

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

2.3 稀疏SMO算法

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

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

3 實驗結果及分析

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

表1 部分benchmark數據庫實驗結果

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

4 結語

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

[1]張學工.統計學習理論與支持向量機[J].自動化學報,2000

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

[3]邊肇祺.張學工,等.模式識別[M].第二版.北京:清華大學出版社,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