基于自適應步長的支持向量機快速訓練算法

摘要：支持向量機訓練問題實質上是求解一個凸二次規劃問題。當訓練樣本數量非常多時， 常規訓練算法便失去了學習能力。為了解決該問題并提高支持向量機訓練速度，分析了支持向量機的本質特征，提出了一種基于自適應步長的支持向量機快速訓練算法。在保證不損失訓練精度的前提下，使訓練速度有較大提高。在UCI標準數據集上進行的實驗表明，該算法具有較好的性能，在一定程度上克服了常規支持向量機訓練速度較慢的缺點、尤其在大規模訓練集的情況下，采用該算法能夠較大幅度地減小計算復雜度，提高訓練速度。

關鍵詞：支持向量機; 序貫最小化； 機器學習； 自適應步長

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2008)06－1679－03

支持向量機是近幾年出現的一種具有良好性能的學習機器。其理論最早由Vapnik[1]提出，是一種基于統計學習理論中VC維理論和結構風險最小理論的通用學習方法。它可以解決小樣本學習問題，而且對數據的維數、多變性不敏感，能夠較好地進行模型選擇。與傳統的人工神經網絡相比，它不僅結構簡單，而且泛化能力明顯提高。目前已經在許多智能信息獲取與處理領域取得了成功的應用。

SVM的訓練算法需求解一個凸二次規劃問題。在最優化理論中，許多求解凸二次規劃問題的算法需要利用整個海森(Hessian)矩陣。然而受到計算機容量和運算速度的限制，很難用傳統的SVM訓練算法求解數據規模較大的問題。因此，急需提出一種高效的SVM訓練算法來處理大規模數據問題。

1支持向量機原理

支持向量機最初用于數據分類問題的處理。下面針對訓練樣本集，即兩類線性、兩類非線性，分別加以討論。

從表2可以看出，DSMO算法的測試精度與經典SMO相比沒有大的損失。因此可以得出結論，DSMO算法在保證訓練精度的同時，大幅縮短了訓練時間。

5結束語

本文首先介紹了SMO算法，并分析了D.Lai提出的ESMO算法。通過分析發現其中的不足，提出了自適應步長SMO(DSMO)算法。實驗表明，這種方法可以明顯提高SMO的算法效率，縮短SVM分類器的訓練時間。

參考文獻：

［1］VAPNIK V. The nature of statistical learning theory[M].New York：Springer，1995.

[2]OSUNA E， FREUND R，GIROSI F. Training support vector machines: an application to face detection[C]//Proc ofCVPR’97. Puerto Rico: IEEE Computer Society， 1997:130－136.

[3]PLATT J. Fast training of support vector machines using sequential minimal optimization[C]//SCHLKOPF B， BURGES C， SMOLA A. Advances in Kernel Methods－Support Vector Learning.Cambridge， MA: MIT Press， 1999:185－208.

[4]KEERTHI S， GILBERT E. Convergence of a generalized SMO algorithm for SVM classifier design[J].Machine Learning，2002，46(1/3):351－360.

[5]LIN C J. Asymptotic convergence of an SMO algorithm without any assumptions[J].IEEE Trans on Neural Networks， 2002，13(1): 248－250.

[6]LAI D， MANI N， PALANISWARNI M. Increasing the step of the Newtonian decomposition method for support vector machines， Technical Report MECSE－29－2003[R].Australia: Dept. of Electrical and Computer Systems Engineering， Monash University， 2003.

[7]HOOKE R， JEEVES T A. Direct search solution of numerical and statistical problems[J].Journal of ACM，1961，8(4):212－229.

[8]CHEN P H， FAN Rong－en， LIN C J. A study on SMO－type decomposition methods for support vector machines[J].IEEE Trans on Neural Networks， 2006，17(4):893－908.

[9]KEERTHI S， SHEVADE S， BHATTCHARYYA C，et al. Improvements to Platt’s SMO algorithm for SVM classier design[J].Neural Computation，2001，13(3): 637－649.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文