韓順成，馬小晴，陳進東，潘豐

江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫 214122

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

基于改進停機準則的SMO算法

韓順成，馬小晴，陳進東，潘豐

江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫 214122

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

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

1 引言

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

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

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

2 支持向量機回歸和KKT停機準則

SVR可表示為對給定的訓練集：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為訓練集T中樣本個數(shù)；ε為不敏感系數(shù)；ξ、ξ*為松弛變量的上限與下限。為了便于求解上述優(yōu)化函數(shù)，將式（2）轉(zhuǎn)化為相應的對偶問題：

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

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

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

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

3.1 對偶間隙

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

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

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

由強對偶定理可知，對于原始問題：

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

3.2 SMO算法

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

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

3.3 改進的SMO算法

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

綜上所述，基于改進停機準則的SMO算法的訓練步驟：

步驟4計算相應Fd，按照相應的Fd的值判斷是否計算δ。

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

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

4 實驗仿真

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

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

表2 一維MSMO與SMO的比較

圖1 MSMO對測試樣本的逼近

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

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

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

表3 二維MSMO與SMO的比較

5 結(jié)論

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

[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]鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機[M].北京：科學出版社，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)勢學科建設(shè)工程資助項目。

韓順成（1987—），男，碩士研究生，研究方向為工業(yè)過程的建模與優(yōu)化控制；潘豐（1963—），男，教授，博導，研究領(lǐng)域為過程控制、建模等研究。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