一種改進序貫最小優化算法的方法

摘 要： 序貫最小優化算法（SMO）是支持向量機（SVM）訓練算法中一種十分有效的改進方法，但針對大規模樣本數據時，SMO訓練速度仍比較慢。為了提高訓練速度，在基本保持訓練精度的前提下，提出了一種改進優化策略：即跳過部分與精度無關的向量集、提前結束循環、松弛KKT條件以便收縮工作集。經過幾個著名的數據集的試驗結果表明，此策略可以大幅縮短SMO的訓練時間，并且精度沒有明顯變化。

關鍵詞： 支持向量機； 序貫最小優化算法； 去除無關向量； 收縮工作集

中圖分類號： TN911?34； TP312 文獻標識碼： A 文章編號： 1004?373X（2013）08?0017?03

0 引 言

支持向量機（Support Vector Machine，SVM）[1]是1995年由 Cortes和Vapnik首先提出的一種新的分類回歸方法。它是建立在統計機器學習的VC維理論和結構風險最小化的理論基礎之上。在模式識別、數據挖掘、分類、回歸等問題領域都表現出許多特有的優勢，因而獲得了良好的應用。

給定輸入空間的l個訓練樣本[（xi，yi），i=1，2，…，][l，xi∈Rd，yi∈{-1，1}]， SVM的實質是尋找最優分類超平面。將尋找的過程轉化為求解一個二次規劃問題[2]，式子最終變為：

[min： f（α）=12αTQα-eTαs.t yTαi=0， 0≤αi≤C， i=1，2，…，l]

式中：[e]為全1向量；C為一個重要的參數，從本質上說是平衡經驗風險和置信風險的，C越大置信風險越大，經驗風險越小，并且所有的[α]都限制在邊長為C的正方形范圍內；[Q]為l×l的Hessian半正定矩陣，[Qij=][yiyjK（xi，xj）]，而[K（xi，xj）]為核函數。經典的二次規劃算法無法處理數據集過大的問題。因此，[Q]陣的存儲和計算成為訓練SVM急需解決的問題。

早期研究中，Vapnik提出了Chunking算法；Osuna等人提出了工作集固定的分解算法；Joachim將Zoutendijk的可行方向法、Shrinking法、Kernel Cache技術相結合實現了SVMLight軟件；……