基于預備工作集的最小序列優(yōu)化算法

摘要：為了提高支持向量機求解大規(guī)模問題的訓練速度，提出了一種新的工作集選擇策略——預備工作集策略：在SMO中，利用可行方向策略提取最大違反對的同時，從核緩存cache中提取違反KKT條件程度最大的一系列樣本組成預備工作集，為此后歷次SMO迭代優(yōu)化提供工作集。該方法提高了核緩存的命中率，減少了工作集選擇的代價。理論分析和實驗結(jié)果表明，預備工作集策略能夠很好地勝任待優(yōu)化的工作集，加快了支持向量機求解大規(guī)模問題的訓練速度。

關鍵詞：支持向量機；預備工作集；工作集選擇；核緩存

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

文章編號：1001-3695(2007)10-0037-04

0引言

支持向量機是在統(tǒng)計學習理論基礎上發(fā)展起來的機器學習算法，其訓練過程在本質(zhì)上是一個二次規(guī)劃問題[1]。為了提高SVM的計算速度，研究人員先后提出了塊算法(chunking)、分解算法(decomposition)和序貫最小優(yōu)化算法(sequential minimal optimization，SMO)[2]等SVM訓練方法。這些算法均是將大規(guī)模的原問題分解為若干小規(guī)模的子問題。當前較為流行的SVMlight[3]、Libsvm[4]等算法都采用了分解法或SMO，結(jié)合可行方向策略進行工作集選擇，并引入核緩存cache和shrinking兩種加速策略，使得SVM的速度得到了很大的提高。然而這些方法在SVM的工作集選擇中需花費較大的代價。SVMlight在對當前工作集進行優(yōu)化后，需要重新歷遍整個訓練集以選擇新的工作集；Libsvm采用SMO算法，每一次迭代都需要重新遍歷整個活動集尋找下一次優(yōu)化的最大違反對樣本，其迭代次數(shù)必然很大。

由優(yōu)化理論可知，在SVM的迭代優(yōu)化中，違反KKT條件程度最大的樣本對目標函數(shù)下降的貢獻最大，在SMO中即為最大違反對中的樣本。通常情況下，違反KKT條件程度較大的樣本有多個，利用可行方向策略[3]提取這些違反KKT條件較大的一系列樣本，為SVM提供備選的優(yōu)化樣本。對于SMO算法，當最大違反對優(yōu)化后，其他樣本在接下來的聯(lián)合優(yōu)化時仍然具有較大違反性。如果將這些樣本作為接下來數(shù)次迭代時的工作集，仍然可以產(chǎn)生較好的效果，并且節(jié)省了數(shù)次工作集的選擇步驟。基于這種思想，本文提出了基于預備工作集的SMO算法。

1現(xiàn)有SVM訓練算法的分析

Joachims[3，5]提出了基于分解算法的SVMlight訓練算法，采用Zoutendijk可行方向法選擇工作集，是當前最有效的工作集選擇方法。其主要思想是在每次迭代中找出最陡的可行下降方向來使得目標函數(shù)向最小值逼近。但是，SVMlight也存在一些不足。SVMlight算法在對子集進行全局優(yōu)化時迭代耗費太大。在優(yōu)化子集的過程中，為了使子集在整體上達到一個較高的優(yōu)化精度，需要大量的迭代步驟；特別是在子集優(yōu)化后期，優(yōu)化精度距離目標精度相差不大，但還是需要大量的迭代步驟來進行純粹的精度調(diào)整，此時迭代的步長越來越小，目標函數(shù)甚至會出現(xiàn)反彈。這部分迭代步數(shù)占了整個子集優(yōu)化過程的很大部分。這樣的優(yōu)化步驟對下一次子集優(yōu)化并沒有切實的效果，并且它們對整個訓練集的優(yōu)化所起的作用微乎其微。

C.C.Chang等人[4]結(jié)合SVMlight和SMO算法，提出了Libsvm算法。Libsvm算法將SVMlight的工作集大小設置為2，則相當于將分解法換成了SMO算法；工作集的選擇采用了最速可行方向下降法，使得SMO的迭代步下降方向最陡，步長最大，從而加速了算法的收斂。其他算法[6~9]都以SMO為突破口。由于SMO迭代中核函數(shù)Qi、Qj更新太頻繁，cache機制的命中率低。這些算法的基本思想就是優(yōu)先選取被核緩存的乘子，以提高核緩存的命中率。雖然充分利用了核緩存策略，但這樣所獲得的工作集在迭代中使得目標函數(shù)下降較為緩慢，從而導致迭代次數(shù)增多。

為避免上述算法的缺點，本文提出了基于預備工作集的SMO算法。該算法提取出當前違反程度最大的一系列樣本組成子集。這個子集類似于SVMlight中的待優(yōu)化子集，但并沒有將它們完全優(yōu)化，因為在優(yōu)化過程中對一定規(guī)模的子集進行完全優(yōu)化是徒勞的；接著提取出該子集包含于核緩存中的樣本，稱這些樣本為預備工作集；預備工作集為此后歷次SMO迭代優(yōu)化提供了工作集。該算法大大減少了工作集選擇的次數(shù)，又最大限度地利用了核緩存機制。

2基于預備工作集的SMO算法

2．1理論基礎

在SMO算法中，當最大違反對優(yōu)化后，直接從違反對的預備工作集中提取違反對作為工作集，直到將預備工作集提取完，再對活動集重新進行gt的排列。由定理1可知，將這些預備工作集中的違反對作為歷次迭代的工作集是完全可行的。其收益在于避免了多次重復地重新計算并排序gt，節(jié)省了多次選擇工作集的巨大耗費，提高了核緩存的命中率；而代價是函數(shù)目標值的下降量有所減小，但相比于最大違反對，下降量差距不大。

預備工作集的收益受其自身規(guī)模大小的影響。當預備工作集規(guī)模較大時，計算所產(chǎn)生的收益就會更多。核緩存cache影響著預備工作集的大小，核緩存越大，預備工作集越大，收益越多。只要核緩存中的樣本能夠使目標函數(shù)的下降量超過一定的幅度，就可以被選進預備工作集。

2．3基于預備工作集的SMO算法（RWSSMO）

3實驗結(jié)果與分析

3．1實驗數(shù)據(jù)

為驗證本文所提RWSSMO算法的有效性，將選取Libsvm算法作對比實驗。兩種算法都屬于SMO算法，不同之處在于工作集策略不同。Libsvm中，SMO的工作集選擇方法為WSS1策略[10]，即選取最大違反對為當前工作集（下文稱Libsvm算法為WSS1SMO算法）。為了保證可比性，實驗采用相同SVM參數(shù)。實驗數(shù)據(jù)選自UCI公共測試數(shù)據(jù)庫中的ijcnnl和acoustic數(shù)據(jù)集。為了驗證訓練集規(guī)模對RWSSMO算法的影響，以隨機方式分別從選取的數(shù)據(jù)集中抽取五個子集作為訓練集，子集的規(guī)模逐步增大。其統(tǒng)計特性如表1所示。實驗中核緩存的規(guī)模分別取20和40 MB。

當cache的容量增大時，之前所選的q個樣本就有更大的概率進入預備工作集。預備工作集策略的一個優(yōu)勢在于提高緩存的利用率，從而可以大大減少總的計算量。在圖2中，比較了訓練數(shù)據(jù)集ijcnn11時采用cache=20 MB和cache=40 MB兩條件下預備工作集的規(guī)模，顯然cache=40 MB預備集的規(guī)模大得多。從表2中可以找出，cache=40 MB對應的是高緩存命中率和低運行時間。緩存的增大對運算速度的提高有根本的幫助。

3．3結(jié)果與分析

表2列出了RWSSMO和WSS1SMO的實驗結(jié)果。從表2中可見，對于RWSSMO，盡管迭代次數(shù)比WSS1SMO多，但核緩存的命中率較高，核函數(shù)總的計算次數(shù)偏少，因而表現(xiàn)為RWSSMO的運行時間短；在RWSSMO算法中，核緩存40 MB比核緩存只有20 MB時核函數(shù)的命中率提高不少，運行時間也變小了，盡管迭代次數(shù)增大了。隨著訓練集規(guī)模的增大，RWSSMO的速度優(yōu)勢表現(xiàn)得更明顯。

RWSSMO算法采用了預備工作集為優(yōu)化對象。一方面，預備工作集來源于核緩存，保證了RWS策略具有很高的核緩存命中率；另一方面，在工作集選擇的代價方面，一個預備工作集同時涵蓋了數(shù)次乃至數(shù)十次的待優(yōu)化工作集，避免了WSS1策略中的每一次迭代都需要進行工作集選取。因而總體上RWS策略具有較小的代價。因此，在RWS策略中，工作集選擇和核緩存命中率所得到的收益超過了更多迭代步驟所帶來的計算代價，使得RWSSMO的運行時間總體較小。

此外，在兩組實驗中，隨著訓練集規(guī)模的增大，RWSSMO顯示出了比WSS1SMO更快的速度優(yōu)勢。圖3是acoustic數(shù)據(jù)的各子集上，兩種算法在相同核緩存條件下的運行時間。當訓練集規(guī)模較小時，RWSSMO與WSS1SMO的訓練時間比較接近；當訓練集規(guī)模逐漸變大時，RWSSMO的運行時間明顯小于WSS1SMO，并且兩者運行時間的差距越來越大，RWSSMO的速度優(yōu)勢越來越明顯。ijcnn1數(shù)據(jù)集的實驗結(jié)果同樣如此。RWS策略節(jié)省工作集選擇的次數(shù)，避免重復計算并排序gt。因而只有在處理大規(guī)模的數(shù)據(jù)時，RWSSMO的收益才表現(xiàn)的更明顯，相對于其他算法才具有較短的運行時間。

實驗表明RWS策略有助于提高SMO的運算速度，從而驗證了基于預備工作集SMO算法的有效性。得出結(jié)論：當預備工作集的規(guī)模越大，RWSSMO的運行速度就越快；當訓練樣本越多，該算法的優(yōu)勢越明顯。

4結(jié)束語

較大KKT違反樣本在優(yōu)化后仍然具有相當?shù)倪`反KKT條件的程度。保留這些樣本并進行優(yōu)化，同樣可以產(chǎn)生較大的目標函數(shù)下降。據(jù)此本文提出了一種運行代價更低的SMO工作集選擇方法——預備工作集策略。在核緩存中提取當前違反程度較大的一系列樣本組成預備工作集，并作為此后歷次迭代優(yōu)化的工作集。該策略最大限度地利用了核緩存，減少了核函數(shù)的計算，同時也節(jié)省了數(shù)次工作集選取以及更新排序的代價。理論分析和實驗結(jié)果均表明，實施預備工作集策略的SMO算法相比經(jīng)典SMO算法對于大規(guī)模數(shù)據(jù)集樣本具有較大的優(yōu)越性。

參考文獻：

［1］VAPNIK V.The nature of statistical learning theory [M].New York:SpringerVerlag，1995:35-54. [2]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.

[3]JOACHIMS T.Text categorization with support vector machines:learning with many relevant features[C]//Proc of the 10th European Conference on Machine Learning. Chemnitz， DE:[s.n.]，1998:137－142.

[4]CHANG C C，LIN C J.Libsvm:a library for support vector machines (version2.3)[EB/OL].(2001).http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf.

[5]JOACHIMS T. Making largescale SVM learning practical[C]//SCHLKOPF B，BURGRS C，SMOLA A.Advances in Kernel Methods—Support Vector Learning.Cambridge， MA: MIT Press， 1998:169184.[6] FLAKE G，LAWRENCE S. Efficient SVM regression training with SMO[J].Machine Learning，2002，46(1/3):271-290. 

[7]LI Jianmin，ZHANG Bo，LIN Fuzong.A new strategy for selecting working sets applied in SMO[C]//Proc of the 16th International Conference on Pattern Recognition (ICPR 2002).[S.l.]:IEEE，2002:427-430.

[8]李建民，張鈸，林福宗. 序貫最小優(yōu)化的改進算法[J]. 軟件學報， 2003，14(5):918-924.

[9]ZENG Zhiqiang，GAO Ji.A new working set selection for SMOtype decomposition methods[C]//Proc of the 4th International Conference on Machine Learning and Cybernetics.Guangzhou:IEEE，2005:18-21. [10]FAN Rongen，CHEN PH，LIN C J.Working set selection using second order information for training support vector machines[J].Journal of Machine Learning Research，2005，6:1889-1918.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”