基于改進(jìn)停機(jī)準(zhǔn)則的SMO算法

韓順成，馬小晴，陳進(jìn)東，潘豐

江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫 214122

◎理論研究、研發(fā)設(shè)計◎

基于改進(jìn)停機(jī)準(zhǔn)則的SMO算法

韓順成，馬小晴，陳進(jìn)東，潘豐

江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫 214122

在序列最小優(yōu)化（Sequential Minimal Optimization，SMO）算法訓(xùn)練過程中，采用標(biāo)準(zhǔn)的KKT（Karush-Kuhn-Tucker）條件作為停機(jī)準(zhǔn)則會導(dǎo)致訓(xùn)練后期速度下降。由最優(yōu)化理論可知，當(dāng)對偶間隙為零時，凸二次優(yōu)化問題同樣可以取得全局最優(yōu)解。因此本文將對偶間隙與標(biāo)準(zhǔn)KKT條件同時作為SMO算法的停機(jī)準(zhǔn)則，從而提出了改進(jìn)停機(jī)準(zhǔn)則的SMO算法。在保證訓(xùn)練精度的情況下，提高了SMO算法的訓(xùn)練速度。通過對一維和二維函數(shù)的兩個仿真實(shí)驗(yàn)，驗(yàn)證了改進(jìn)SMO算法的有效性。

支持向量機(jī)回歸；序列最小優(yōu)化算法；對偶間隙；KKT條件；停機(jī)準(zhǔn)則

1 引言

支持向量機(jī)（Support Vector Machine，SVM）由V.Vapnik等人提出，是一種以統(tǒng)計學(xué)理論、結(jié)構(gòu)風(fēng)險最小原則和Wolfe對偶化理論為基礎(chǔ)的機(jī)器學(xué)習(xí)方法[1]。目前SVM已被廣泛應(yīng)用于模式識別、回歸估計、概率密度估計等各個領(lǐng)域。SVM可分為支持向量分類（Support Vector Classification，SVC）和支持向量回歸（Support Vector Regression，SVR）[2]。

常見的SVM算法有選塊算法、分解算法、SMO算法等，其中Platt提出的SMO算法[3]是目前SVM處理大規(guī)模數(shù)據(jù)較為有效的訓(xùn)練方法。SMO算法起初主要用于模式分類問題，后來得到擴(kuò)展并應(yīng)用于回歸問題，本文主要針對SMO算法在SVR訓(xùn)練中的問題展開。

在SVR訓(xùn)練過程中，SMO算法一般采用KKT條件作為停機(jī)準(zhǔn)則[4]。經(jīng)研究發(fā)現(xiàn)，采用KKT條件作為停機(jī)準(zhǔn)則，SMO算法在訓(xùn)練剛開始時目標(biāo)函數(shù)變化很快，但訓(xùn)練后期則變化緩慢，從而導(dǎo)致了訓(xùn)練的速度下降[5-6]。由最優(yōu)化理論可知：在對偶間隙為零時，凸二次優(yōu)化問題也將取得全局最優(yōu)解。因此，本文從停機(jī)準(zhǔn)則出發(fā)，將對偶間隙與標(biāo)準(zhǔn)KKT條件同時使用作為SMO算法的停機(jī)準(zhǔn)則。在訓(xùn)練后期，當(dāng)對偶間隙小于設(shè)定精度時，算法即可中止，從而減少后期的迭代次數(shù)，解決SVR訓(xùn)練后期訓(xùn)練速度下降的問題。

2 支持向量機(jī)回歸和KKT停機(jī)準(zhǔn)則

SVR可表示為對給定的訓(xùn)練集：T={(xi，yi)，i=1，2，…，l}，xi∈RN，和yi∈R，非線性映射Φ將數(shù)據(jù)xi映射到高維特征空間F，可構(gòu)造非線性回歸函數(shù)[7]：

通過求解優(yōu)化函數(shù)（1），可以得到w和b。

式中，C為懲罰系數(shù)；l為訓(xùn)練集T中樣本個數(shù)；ε為不敏感系數(shù)；ξ、ξ*為松弛變量的上限與下限。為了便于求解上述優(yōu)化函數(shù)，將式（2）轉(zhuǎn)化為相應(yīng)的對偶問題：

引入拉格朗日乘子，則對偶問題（3）的最優(yōu)問題求解可轉(zhuǎn)化為：

式中，β，β*，β**，γ和γ*為相應(yīng)的拉格朗日乘子。式（5）可看做關(guān)于ai、的函數(shù)，分別對ai、依次求導(dǎo)，并令其為0，則相應(yīng)的KKT條件可表示為：

KKT條件是判斷優(yōu)化函數(shù)取最優(yōu)解的重要判定條件，也是算法終止的標(biāo)志。SMO算法一般采用式（7）所示的KKT條件來判斷算法是否結(jié)束。

3 算法設(shè)計與實(shí)現(xiàn)

3.1 對偶間隙

對偶間隙用來表述原問題與對偶問題的目標(biāo)函數(shù)值的關(guān)系。對于原始問題和對偶問題分別有最優(yōu)解的問題，可以通過強(qiáng)對偶定理來限定。

強(qiáng)對偶定理[7，9]：考慮連續(xù)可微的凸最優(yōu)化問題

式中，f和ci都是連續(xù)可微的凸函數(shù)，若原始問題和對偶問題分別有可行解，則這兩個可行解分別為原始問題和對偶問題的最優(yōu)解的充要條件是它們相對應(yīng)的原始問題和對偶問題的函數(shù)值相等。

由強(qiáng)對偶定理可知，對于原始問題：

由此可以看出，當(dāng)對偶間隙δ為零時，原始問題和對偶問題都取得最優(yōu)解，所以對偶間隙可以作為一個有用的停機(jī)準(zhǔn)則。在實(shí)際應(yīng)用中，對偶間隙并不一定要為零時，SMO算法才終止，只需事先設(shè)定值μ，當(dāng)δ小于μ時，算法即可中止。

3.2 SMO算法

SMO算法是分解算法[11]工作集個數(shù)等于2的特殊情形，即SMO算法把一個大的優(yōu)化問題分解成一系列只含兩個變量的優(yōu)化問題。因此SMO算法主要包括兩個初始訓(xùn)練點(diǎn)的選取、兩個變量優(yōu)化問題的解析求解。

首先，兩個訓(xùn)練點(diǎn)的選取。SMO算法采用兩層循環(huán)（外部、內(nèi)部）的啟發(fā)式策略選擇訓(xùn)練點(diǎn)。

3.3 改進(jìn)的SMO算法

由于樣本的個數(shù)直接影響算法的訓(xùn)練速度，隨著樣本數(shù)目的增多，采用標(biāo)準(zhǔn)的KKT停機(jī)準(zhǔn)則會導(dǎo)致迭代后期訓(xùn)練速度下降。停機(jī)準(zhǔn)則標(biāo)志SMO算法的終止，是影響訓(xùn)練時間的關(guān)鍵因素。由強(qiáng)對偶定理可知當(dāng)對偶間隙為零時，凸二次優(yōu)化問題也取得全局最優(yōu)解，因此可以將對偶間隙作為一個檢驗(yàn)算法中止的準(zhǔn)則，但不能定性地直接將對偶間隙應(yīng)用到停機(jī)準(zhǔn)則中。

綜上所述，基于改進(jìn)停機(jī)準(zhǔn)則的SMO算法的訓(xùn)練步驟：

步驟4計算相應(yīng)Fd，按照相應(yīng)的Fd的值判斷是否計算δ。

步驟5當(dāng)所有樣本均滿足式（7）的KKT條件，或δ小于給定的精度，結(jié)束循環(huán)。

步驟6如果不滿足KKT條件或δ大于給定的精度，則Nd←Nd+1，轉(zhuǎn)向步驟2。

4 實(shí)驗(yàn)仿真

為了驗(yàn)證改進(jìn)SMO算法的性能，分別選取一維和二維樣本數(shù)據(jù)進(jìn)行訓(xùn)練和測試。仿真計算機(jī)為Intel?Celeron?CPUE330，1 024 MB內(nèi)存，仿真軟件為MALABR2010a。

表1 算法檢測結(jié)果

表2 一維MSMO與SMO的比較

圖1 MSMO對測試樣本的逼近

訓(xùn)練精度表示在實(shí)驗(yàn)中采用真實(shí)目標(biāo)函數(shù)與逼近值的均方偏差，由下式計算。

通過仿真結(jié)果可以看出，MSMO算法比SMO算法減少了迭代次數(shù)，提高了訓(xùn)練速度。且隨著樣本數(shù)目的增加，訓(xùn)練時間的縮短更為明顯，一維和二維數(shù)據(jù)樣本的情況相似，這主要是因?yàn)镸SMO算法改進(jìn)了停機(jī)條件，以對偶間隙來確定算法的終止條件，減小了優(yōu)化迭代的次數(shù)，從而加快了算法訓(xùn)練速度。

圖2 MSMO對測試樣本的逼近誤差

表3 二維MSMO與SMO的比較

5 結(jié)論

SMO是目前SVM處理大規(guī)模數(shù)據(jù)較為有效的方法，但是采用KKT條件作為停機(jī)準(zhǔn)則導(dǎo)致這種算法在迭代優(yōu)化的后期訓(xùn)練速度減慢。針對這個問題，本文對SMO的停機(jī)準(zhǔn)則進(jìn)行了改進(jìn)，提出了一種改進(jìn)的SMO算法。仿真結(jié)果表明，這種改進(jìn)的優(yōu)化算法在保證預(yù)測精度的前提下，大大減少了迭代次數(shù)，提高了SVM訓(xùn)練的速度。對今后SVM處理大規(guī)模數(shù)據(jù)，提高算法運(yùn)算收斂速度具有一定參考價值。

[1]Hearst M.Support Vector Machines[J].IEEE Transaction on Intelligent Systems，1998：13（4）：18-28.

[2]Vapnik V N.Statistical learning theory[M].New York：Wiley，1998.

[3]Platt J C.Support Vector Machines[M]//Sch?lkopf B，Burges C，Smola A.Fast training of support vector machines using sequential minimal optimization.Advances in Kernel Methods.[S.l.]：M IT-Press，1998.

[4]Lin C J.A formal analysis of stopping criteria of decomposition methods for support vector machines[J].IEEE Transactions on Neural Networks，2002，13（5）：1045-1052.

[5]Lin Yih-Lon，Jeng Jyh-Horng.Three-parameter sequential minimal optimization for support[J].Neurocomputing，2011，74：3467-3475.

[6]Lin Zuo，Zhang Yi.An improved working sets election for SMO-type decomposition method[J].Real World Applications 2010，17（11）：3834-3841.

[7]鄧乃揚(yáng)，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機(jī)[M].北京：科學(xué)出版社，2004.

[8]Smola A J.Learning with Kernels[D].GMD，Birlinghoven，Germany，1998.

[9]Takahashi N，Guo J，Nishi T.Global Convergence of SMO algorithm for Support Vector Rgression[J].IEEE Trans on Neural Networks，2008，19（6）：971-982.

[10]Burachik R S，Rubinov A M.On the absence of duality gap for lagrange-type function[J].Industrial Management and Optim，2005，24（1）：33-38.

[11]Chen P-H，F(xiàn)an R-E，Lin C-J.A study on SMO-type decomposition methods for support vector machines[J]. IEEE Trans on Neural Netw rok，2006，17（12）：893-908.

[12]Flake G W，Law rence S.Efficient SVM regression training with SMO[J].Machine Learning，2002，46（7）：271-290.

HAN Shuncheng,MA Xiaoqing,CHEN Jindong,PAN Feng

Key Laboratory of Advanced Process Control for Light Industry（Ministry of Education）,Jiangnan University,Wuxi,Jiangsu 214122,China

In SMO training process,standard KKT stopping criteria w ill lead to training speed declining along with training progress.According to the optimum theory,if the dual gap is zero,convex quadratic optimization problem will also obtain global optimal solution.Therefore,an improved stopping criteria of SMO is proposed in this paper,it combines the duality gap and standard KKT condition as the stopping criteria.This algorithm can improve the training speed without training accuracy decrease.Two cases experimental simulating results corroborate the efficiency of this algorithm.

Support Vector Regression;Sequential Minimal Optimization（SMO）;duality gap;Karush-Kuhn-Tucker （KKT）;Stopping Criteria

A

TP301.6

10.3778/j.issn.1002-8331.1208-0471

HAN Shuncheng,MA Xiaoqing,CHEN Jindong,et al.Improved stopping criteria based SMO algorithm.Computer Engineering and Applications,2014,50（16）：31-34.

國家高技術(shù)研究發(fā)展計劃（863）（No.2009AA 05Z203）；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目。

韓順成（1987—），男，碩士研究生，研究方向?yàn)楣I(yè)過程的建模與優(yōu)化控制；潘豐（1963—），男，教授，博導(dǎo)，研究領(lǐng)域?yàn)檫^程控制、建模等研究。E-mail：hanshuncheng@126.com

2012-09-04

2012-10-26

1002-8331（2014）16-0031-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-11-21,http://www.cnki.net/kcm s/detail/11.2127.TP.20121121.1103.042.htm l