一種改進(jìn)序貫最小優(yōu)化算法的方法

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

關(guān)鍵詞： 支持向量機(jī)； 序貫最小優(yōu)化算法； 去除無(wú)關(guān)向量； 收縮工作集

中圖分類號(hào)： TN911?34； TP312 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）08?0017?03

0 引 言

支持向量機(jī)（Support Vector Machine，SVM）[1]是1995年由 Cortes和Vapnik首先提出的一種新的分類回歸方法。它是建立在統(tǒng)計(jì)機(jī)器學(xué)習(xí)的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化的理論基礎(chǔ)之上。在模式識(shí)別、數(shù)據(jù)挖掘、分類、回歸等問題領(lǐng)域都表現(xiàn)出許多特有的優(yōu)勢(shì)，因而獲得了良好的應(yīng)用。

給定輸入空間的l個(gè)訓(xùn)練樣本[（xi，yi），i=1，2，…，][l，xi∈Rd，yi∈{-1，1}]， SVM的實(shí)質(zhì)是尋找最優(yōu)分類超平面。將尋找的過程轉(zhuǎn)化為求解一個(gè)二次規(guī)劃問題[2]，式子最終變?yōu)椋?/p>

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

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

早期研究中，Vapnik提出了Chunking算法；Osuna等人提出了工作集固定的分解算法；Joachim將Zoutendijk的可行方向法、Shrinking法、Kernel Cache技術(shù)相結(jié)合實(shí)現(xiàn)了SVMLight軟件；Platt的SMO算法[3]將工作集固定為最小規(guī)模，從而可以獲得解析解；Keerthi提出了SMO的改進(jìn)算法GSMO；孫劍等人運(yùn)用緩存機(jī)制，減少對(duì)BSV核函數(shù)的計(jì)算來縮減訓(xùn)練時(shí)間[4]；李建民等人提出了考慮目標(biāo)函數(shù)下降量和計(jì)算代價(jià)，提高緩存效率的收益代價(jià)平衡的工作集選擇算法[5]；張浩然等人提出的策略使得所選取的優(yōu)化變量能夠使目標(biāo)函數(shù)的下降最多， 優(yōu)化步長(zhǎng)更大[6]。近些年來，改進(jìn)和優(yōu)化主要涉及到讓更多的樣本同時(shí)得到優(yōu)化[7]、增加步長(zhǎng)加速收斂速度[8]、綜合考慮迭代次數(shù)和緩存效率[9]、考慮非正定核的運(yùn)用[10]、運(yùn)用聚類的方法等的方面，并且都取得了一些成效。

本文在分析SMO算法的基礎(chǔ)上，針對(duì)分類向量集過于龐大、算法后期工作集的選取策略、停機(jī)條件的設(shè)置等方面的問題進(jìn)行了適當(dāng)?shù)母倪M(jìn)。通過對(duì)著名數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)，發(fā)現(xiàn)此項(xiàng)改進(jìn)在縮短測(cè)試時(shí)間的基礎(chǔ)上，算法的精度沒有很大的變化，仍能達(dá)到滿意的效果。

1 標(biāo)準(zhǔn)SMO算法

SMO是將大的QP問題分解成最小規(guī)模的QP問題，算法在固定其他參數(shù)的條件下，每次僅選擇兩個(gè)Lagrange乘子[α1，α2]進(jìn)行更新，由于Lagrange乘子的線性約束條件，所以可以解析出這兩個(gè)乘子所滿足條件的最優(yōu)值，不斷的優(yōu)化所有的乘子，最終能夠解決這個(gè)二次規(guī)劃問題。

具體做法是首先遍歷非邊界樣本選擇一個(gè)違反KKT條件的樣本[α1]，尋找非邊界樣本[α2]，如果沒有非邊界樣本可以調(diào)整，就遍歷所有樣本；其次是尋找違反KKT條件的邊界樣本[α1]，尋找非邊界樣本[α2]，如果沒有可以優(yōu)化的樣本就遍歷所有樣本。尋找的依據(jù)是使[E1-E2η]（[Ei]為第i個(gè)樣本的輸出錯(cuò)誤）取得最大值。

SMO算法在選擇兩個(gè)乘子配對(duì)優(yōu)化時(shí)，耗時(shí)主要是花費(fèi)在優(yōu)化選擇和迭代次數(shù)上。SMO 除了在處理線性SVM和具有稀疏二進(jìn)制的數(shù)據(jù)時(shí)訓(xùn)練速度較快之外，對(duì)一般數(shù)據(jù)是非常慢的。

2 改進(jìn)SMO的策略

一方面，對(duì)于凸優(yōu)化問題，在實(shí)現(xiàn)時(shí)需要適當(dāng)?shù)耐Ｖ箺l件來結(jié)束優(yōu)化過程，停止條件可以是：

（1）目標(biāo)函數(shù)[W（α）]的增長(zhǎng)率，即[W（αt+1）-W（α）W（α）]小于某個(gè)容忍值就可以停止，這個(gè)條件是最簡(jiǎn)單的；

（2）原問題的KKT條件，對(duì)于凸優(yōu)化來說它是收斂的充要條件，由于KKT條件本身是比較苛刻的，所以也可以設(shè)定一個(gè)容忍值，即所有樣本在容忍值范圍內(nèi)滿足KKT條件則認(rèn)為訓(xùn)練可以停止；

（3）可行間隙，即原目標(biāo)函數(shù)值[O（w，b）]和對(duì)偶目標(biāo)函數(shù)值[W（α）]的間隙，凸二次優(yōu)化問題的間隙是零。當(dāng)[O（w，b）-W（α）O（w，b）]小于某個(gè)容忍值就可以停止。

恰當(dāng)?shù)耐Ｖ箺l件可以使得算法提早結(jié)束訓(xùn)練，從而節(jié)省訓(xùn)練的時(shí)間。其實(shí)，從本質(zhì)上來說可以推廣到尋找經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信風(fēng)險(xiǎn)之間的平衡。

另一方面，對(duì)于算法所依賴的物理?xiàng)l件而言，優(yōu)化可以從以下方面：

（1）緩存的恰當(dāng)運(yùn)用，能用緩存的地方盡量用緩存，這樣可以減少重復(fù)計(jì)算的次數(shù)，提高運(yùn)行效率，但會(huì)增加算法的空間復(fù)雜度。

（2）關(guān)注可以并行計(jì)算的地方，將其分成若干部分并行計(jì)算，從部分最優(yōu)尋找到全局最優(yōu)。

2.1 跳過部分非支持向量

在優(yōu)化過程中，考慮到只有部分樣本會(huì)成為支持向量，可以將明顯不是支持向量的樣本跳過來刪減大規(guī)模訓(xùn)練集，從而減少樣本訓(xùn)練的時(shí)間，提高訓(xùn)練效率。但修剪的精度不容易掌握，對(duì)于邊界支持向量較多時(shí)，可能修剪的過于粗糙，對(duì)于較少時(shí)，可能誤刪了部分支持向量。因此可以計(jì)算樣本x到分類超平面H的距離d，若[d≤ξ]，則保留此樣本，否則就跳過。[ξ]是一個(gè)可以調(diào)節(jié)的量，用它來控制刪減的力度。具體到算法中：

（1）當(dāng)樣本的Lagrange乘子兩次小于[ξ]時(shí)，下次循環(huán)選擇乘子優(yōu)化跳過此樣本而選擇其他樣本進(jìn)行優(yōu)化；

（2）當(dāng)樣本的Lagrange乘子兩次趨近于[C-ξ]時(shí)，下次循環(huán)選擇乘子優(yōu)化跳過此樣本而選擇其他樣本進(jìn)行優(yōu)化。

也就是說最優(yōu)分類面大致確定下來后，由Lagrange乘子的大小直接判斷是否跳過該樣本。這樣操作簡(jiǎn)便易行，它跳過了已經(jīng)是正確分類的樣本和分內(nèi)面之間的樣本，這樣大幅度的消減對(duì)分類沒有太大影響的待訓(xùn)練的樣本個(gè)數(shù)，從而提高訓(xùn)練速度。

2.2 提前結(jié)束無(wú)意義的循環(huán)

在SMO算法中，程序經(jīng)過兩層循環(huán)不斷的尋找可以優(yōu)化配對(duì)的一些Lagrange乘子。從開始的大量需要優(yōu)化Lagrange乘子迅速下降到只有很少部分的Lagrange乘子能配對(duì)優(yōu)化。在少部分能配對(duì)成功的乘子中，由于程序的選取機(jī)制不變，導(dǎo)致內(nèi)外層循環(huán)在這幾對(duì)乘子之間來回優(yōu)化，這無(wú)疑增加了循環(huán)次數(shù)，耗費(fèi)了訓(xùn)練時(shí)間。

因此，在保證分類精度的前提下，可以松弛這個(gè)條件，提前結(jié)束循環(huán)以免浪費(fèi)尋優(yōu)時(shí)間。雖然并沒有找出全部不滿足KKT條件的乘子以優(yōu)化所有的樣本，但改進(jìn)的算法在后期尋優(yōu)策略上與快速找出最優(yōu)分類面目標(biāo)是一致的。具體的方法是在程序的訓(xùn)練過程中，置數(shù)據(jù)改變量numChanged一個(gè)閾值，當(dāng)算法小于這個(gè)值時(shí)，就可以提前結(jié)束循環(huán)，節(jié)省配對(duì)優(yōu)化的時(shí)間。在實(shí)驗(yàn)中發(fā)現(xiàn)，這樣的策略對(duì)于訓(xùn)練的精度并沒有減少太多，但訓(xùn)練的速度卻有著很大提高。

2.3 收縮工作集

基于松弛KKT條件的思想，發(fā)現(xiàn)在SMO算法中，由于每次計(jì)算一對(duì)Lagrange乘子必然要涉及到w值的變化，w值的變化反應(yīng)到分類圖中是最優(yōu)分類面的微調(diào)。如果當(dāng)w的值在變化小于一個(gè)閾值時(shí)，松弛不滿足KKT條件的[α]，使得很少一部分違反KKT條件的數(shù)據(jù)樣本在下次選擇優(yōu)化時(shí)，被判為無(wú)需優(yōu)化的樣本，從而跳過訓(xùn)練的過程，這樣就可以加快訓(xùn)練速度，節(jié)省訓(xùn)練時(shí)間。其實(shí)這些數(shù)據(jù)樣本對(duì)于尋找最優(yōu)分類面是沒有太大進(jìn)展的，它們所對(duì)應(yīng)的向量是在最優(yōu)分類面附近的樣本向量。具體做法是在程序中，當(dāng)[Δw]小于某個(gè)閾值時(shí)，擴(kuò)大源程序中tol變量的值，將tol的值乘以一個(gè)很小的倍數(shù)來收縮工作集，收縮部分需優(yōu)化的Lagrange乘子[α]，這樣處理后使得有部分的乘子在下次選擇優(yōu)化時(shí)被跳過，從而節(jié)省優(yōu)化時(shí)間。實(shí)驗(yàn)結(jié)果表明，在處理數(shù)據(jù)時(shí)，算法也能快速定位分類面，且分類精度沒有顯著的變化，特別是數(shù)據(jù)集大的數(shù)據(jù)，效果很好。

3 實(shí)驗(yàn)結(jié)果和分析

在SMO源程序（VC++ 6.0）的基礎(chǔ)上進(jìn)行修改，并選取了UCI兩個(gè)數(shù)據(jù)集Segment集和Satellite集進(jìn)行測(cè)試，實(shí)驗(yàn)的CPU為i3?380處理器，內(nèi)存為2 GB。選用的核函數(shù)為RBF徑向基函數(shù)，Segment集有2 200個(gè)訓(xùn)練樣本和110個(gè)測(cè)試樣本，類別有7類，[σ]調(diào)為10，C調(diào)為1.0。Satellite集有4 435個(gè)訓(xùn)練樣本和2 000個(gè)測(cè)試樣本，類別有6類，[σ]調(diào)為15，C調(diào)為1。實(shí)驗(yàn)中采用了標(biāo)準(zhǔn)SMO，去掉向量的SMO（RV?SMO），改變numchanged的SMO（CN?SMO）閾值取3，收縮工作集的SMO（SW?SMO）。分別進(jìn)行訓(xùn)練和測(cè)試。如表1所示。

表1 實(shí)驗(yàn)結(jié)果比較

從表中可以清楚的發(fā)現(xiàn)，文章中提出的策略相比標(biāo)準(zhǔn)SMO的用時(shí)有很大的縮減，且運(yùn)行的精度并沒用衰減多少，對(duì)于規(guī)模較大的數(shù)據(jù)集更是明顯。可見對(duì)于跳過部分向量、結(jié)束不必要的循環(huán)、松弛KKT條件的思路是可行的，能縮小搜索空間，提高SMO的性能。

4 總結(jié)與展望

針對(duì)標(biāo)準(zhǔn)SMO算法處理大規(guī)模數(shù)據(jù)集的耗時(shí)過長(zhǎng)的問題，運(yùn)用刪減部分支持向量，提前結(jié)束循環(huán)、松弛KKT條件的策略。該策略能有效的使得SMO的訓(xùn)練時(shí)間大幅減少，并且SMO 的測(cè)試精度沒有很大變化，特別是處理大規(guī)模數(shù)據(jù)集時(shí)，該策略十分有效。接下來的工作將把該策略和其他的算法相結(jié)合，借鑒其他算法的思想進(jìn)一步優(yōu)化SMO算法和擴(kuò)大該策略運(yùn)用的范圍，運(yùn)用到其他算法中解決實(shí)際問題。

參考文獻(xiàn)

[1] VAPNIK V N. Statistical learning theory [M].New York：John Wiley Sons， 1998.

[2] VAPNIK V N. The nature of statistical learning theory [M]. New York： Springer Verlag， 1995.

[3] OSUNA E， FREUND R， GIROSI F. An improved training algorithm for support vector machines [C]// IEEE Workshop on Neural Networks and Signal Processing. Amelia Island： IEEE Press， 1997： 276?285.

[4] 孫劍，鄭南寧，張志華.一種訓(xùn)練支持向量機(jī)的改進(jìn)序貫最小優(yōu)化算法[J].軟件學(xué)報(bào)，2002，13（10）：2007?2012.

[5] 李建民，張鈸，林福宗.序貫最小優(yōu)化的改進(jìn)算法[J].軟件學(xué)報(bào)，2003，14（5）：918?924.

[6] 張浩然，韓正之.回歸支持向量機(jī)的改進(jìn)序列最小優(yōu)化算法[J].軟件學(xué)報(bào)，2003，14（12）：2006?2013.

[7] 業(yè)林，孫瑞祥，董逸生.多拉格朗日乘子協(xié)同優(yōu)化的SVM快速學(xué)習(xí)算法研究[J].計(jì)算機(jī)研究與發(fā)展，2006，43（3）：442?448.

[8] 姚全珠，田元，王季，等.基于自適應(yīng)步長(zhǎng)的支持向量機(jī)快速訓(xùn)練算法[J].計(jì)算機(jī)應(yīng)用研究，2008，25（6）：1679?1681.

[9] 曾志強(qiáng)，吳群，廖備水，等.改進(jìn)工作集選擇策略的序貫最小優(yōu)化算法[J].計(jì)算機(jī)研究與發(fā)展，2009，46（11）：1925?1933.

[10] 周曉劍，馬義中，朱嘉鋼.SMO算法的簡(jiǎn)化及其在非正定核條件下的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展，2010，47（11）：1962?1969.