求解互補支持向量機的非單調(diào)信賴域算法*

高雷阜，于冬梅，趙世杰

(遼寧工程技術大學優(yōu)化與決策研究所，遼寧 阜新 123000)

摘要：求解支持向量機的核心問題是對一個大規(guī)模凸二次規(guī)劃問題進行求解?；谥С窒蛄繖C的修正模型，得到一個與之等價的互補問題，利用Fischer-Burmeister互補函數(shù)，從一個新的角度提出了求解互補支持向量機的非單調(diào)信賴域算法。新算法避免了求解Hesse矩陣或矩陣求逆運算，減少了工作量，提高了運算效率。在不需要任何假設的情況下，證明算法具有全局收斂性。數(shù)值實驗結果表明，對于大規(guī)模非線性分類問題，該算法的運行速度比LSVM算法和下降法快，為求解SVM優(yōu)化問題提供了一種新的可行方法。

關鍵詞：支持向量機；信賴域方法；互補函數(shù)；非單調(diào)策略

中圖分類號：TP301.6 文獻標志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.016

收稿日期：*2014-04-14;修回日期：2014-08-11

基金項目：教育部高校博士學科科研基金聯(lián)合資助項目(20132121110009)

作者簡介:

通信地址：123000 遼寧省阜新市遼寧工程技術大學理學院

Address:College of Science,Liaoning Technical University,Fuxin 123000,Liaoning,P.R.China

A non-monotonic trust region algorithm for solving complementary support vector machine

GAO Lei-fu,YU Dong-mei,ZHAO Shi-jie

(Research Institute of Optimization and Decision,Liaoning Technical University,Fuxin 123000,China)

Abstract:Solving a large-scale convex quadratic programming problem is the core of the support vector machine. An equivalence complementarity problem can be obtained based on an amended model of the surpport vector machine(SVM), therefore we propose a non-monotonic trust region algorithm for solving the complementarity problem based on the Fischer-Burmeister complementarity function. The new algorithm need not compute any Hesse or the inverse matrix, thus reducing the amount of computational work. Global convergence of the algorithm is proved without any assumptions. Numerical experiments show that the running speed of the algorithm is faster than that of the LSVM algorithm and the descent algorithm when solving large-scale nonlinear classification problems and thus it provides a feasible method for solving SVM.

Key words:support vector machine；trust-region method；complementarity function；non-monotonic strategies

1引言

支持向量機SVM(Support Vector Machine)是由Vapnik V[1,2]基于統(tǒng)計學理論中的結構風險極小化原則提出的，它是一種有監(jiān)督的機器學習，是模式識別中分類、函數(shù)近似和回歸估計的有效工具。在二分類問題模型中，支持向量機模型采用結構風險極小化原則和核函數(shù)方法來構造分類模型，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并推廣應用到函數(shù)擬合等其他研究領域中，例如圖像處理[3]、信用風險評估[4]、股指期貨預測[5]等方面的應用。SVM模型采用極大間隔的方法和結構風險最小化原則對分類函數(shù)進行學習，其模型是一個二次規(guī)劃QP(Quadratic Programming)問題，隨著數(shù)據(jù)規(guī)模的增大，模型的求解變得越來越復雜。因此，尋求可行的算法成為人們研究的熱點。常用求解算法的思想是通過一系列子二次規(guī)劃問題的求解得到原問題的解，如塊算法、分解算法和增量算法等[6]，這些算法在一定程度上節(jié)省了計算機內(nèi)存，提高了計算效率，但算法的設計和實現(xiàn)比較復雜。對于大規(guī)模非線性分類問題，Mangasarian O L 等人[7]對SVM模型進行優(yōu)化，提出了Lagrangian支持向量機(LSVM)模型，并提出了LSVM算法。但是，算法中仍然存在矩陣的求逆運算，特別是對于非線性的高維數(shù)據(jù)，高階矩陣的求逆運算直接影響了算法的訓練速度。

針對LSVM的缺陷，張襄松等人[8]提出互補支持向量機的下降算法，但下降法不穩(wěn)定，對微小擾動敏感。為了克服LSVM算法和下降算法的缺陷，本文提出了求解互補支持向量機的非單調(diào)信賴域方法，并給出了算法的具體實現(xiàn)過程和算法的收斂性證明。最后，通過數(shù)值實驗驗證了算法的可行性和有效性。

2問題的提出

假設訓練:

(1)

其中，參數(shù)e=(1,1,…,1)T。

對二次規(guī)劃問題(1)，通常轉化為它的對偶問題[9]求解：

(2)

利用式(2)的KKT(Karush-Kuhn-Tucker)充要條件及互補問題的等價形式，可以得到式(2)的等價形式[9]：

(3)

MangasarianOL等人給出了式(3)的等價形式:

(4)

并利用:

(5)

提出了一個簡單的迭代算法(LSVM算法)。該算法中存在求逆矩陣的運算，對線性分類問題可以使用等式Sherman-Morrison-Wood-bury(SMW)來計算矩陣，從而提高運算效率。但是，對于非線性分類問題，高階矩陣的求逆運算直接影響了算法的訓練速度，因此該方法只適用于求解中小規(guī)模非線性分類問題。

3問題的轉化

求解支持向量機的二次規(guī)劃問題等價于求解一個互補問題(3)。因此，本文基于Fischer-Burmeister[10]互補函數(shù)，并且該函數(shù)可以推廣到矩陣域中[10]，將其轉化為一個無約束最優(yōu)化問題進行求解。

定義1對?a,b∈R2，映射Ψ:R2→R，如果該映射Ψ滿足

(6)

則映射Ψ為一個互補函數(shù)。

定義2

(7)

對?λ∈RN，令q(λ)=Hλ-e，則由互補函數(shù)可將式(3)轉化為如下方程組:

(8)

上式等價于求解無約束最優(yōu)化問題:

(9)

(10)

令Fk=F(λk),記dk是問題(10)式的解，令目標函數(shù)的預估下降量為:

(11)

目標函數(shù)的真實下降量為:

則真實下降量與預估下降量的比值rk為:

(12)

信賴域算法求解時若rk≥c，其中c∈(0,1)，則接受dk，λk+1=λk+dk，信賴域半徑增加或者不變；否則信賴域半徑減少，求新的dk和rk。重復以上過程即可求得無約束優(yōu)化問題的最優(yōu)解。下面引入非單調(diào)自適應策略，令迭代過程中gk=▽F(λk)，Gk=dT▽F(λk)▽F(λk)Td，Gk為正定矩陣。

定義3

(13)

其中，l(k)=min{t(k-1)+1,T}，T是非負整數(shù)，t(0)=0。

引入?yún)?shù)θk的目的是，如果選取的搜索點恰好處于峽谷附近，那么，它在搜索時就會沿著峽谷緩慢前進，在搜索時出現(xiàn)鋸齒現(xiàn)象，搜索到的最優(yōu)解很可能是局部最優(yōu)解。通過引入一個參數(shù)，使得信賴域半徑的校正條件適當放寬，進而跳出峽谷，搜索到全局最優(yōu)解。

則接受λk+1=λk+dk。

4非單調(diào)信賴域算法求解二次規(guī)劃問題

以下給出非單調(diào)信賴域算法的具體實現(xiàn)過程：

步驟3求解無約束優(yōu)化問題的信賴域子問題式(10)，利用式(12)得到求Fl(k)。

步驟5校正信賴域半徑:

步驟6修正gk+1，k=k+1，轉步驟2。

5算法收斂性分析

引理1設dk是信賴域子問題(10)的解，則必有：

(14)

最早關于不等式(14)的證明由PowellMJD[12]給出，對于上式的詳細證明見文獻[12]。

證明假設上述結論不成立，即算法中步驟2到步驟4間的內(nèi)循環(huán)不在有限步終止。令Si是在dk處第i次的內(nèi)循環(huán)，故rk(i)≤c0,i=1,2,…，且當i→∞時，Δk(0)→0。

由引理1和引理2可知:

□

(15)

(16)

可以證明對任意k都有：

(17)

當k→∞時，有：

由式(17)可知，當k充分大時，

□

證明由假設條件可以得到：

其中，γ為常數(shù)[15～17]。

由于B(λ)是非奇異的，則存在ε>0，k0>0，對?k>k0都有:

故，

又由于

□

6數(shù)值實驗

經(jīng)過對實驗數(shù)據(jù)進行剔除異常值和通過數(shù)據(jù)擬合確定缺失值，以及去量綱、歸一化處理操作后得到待分析數(shù)據(jù)集。分別采用LSVM算法[7]、下降法[8]和本文中的非單調(diào)信賴域算法將隨機選擇的數(shù)據(jù)集作為實驗數(shù)據(jù)進行實驗，三種方法分類性能比較見表1。同時，在同樣的參數(shù)設置情況下，隨機選擇兩個數(shù)據(jù)集Balance Scale和Statlog作為實驗數(shù)據(jù)，得到如圖1和圖2所示的分類正確率情況比較。文中SVM的核函數(shù)選用的是徑向基核函數(shù)。

Table 1　Comparison of the numerical results of the three algorithms

表1中字母D表示相應實際數(shù)據(jù)集的屬性數(shù)目；Train表示SVM訓練數(shù)據(jù)個數(shù)；Test表示SVM測試數(shù)據(jù)個數(shù)；CPU-Time表示相應算法的CPU運行時間，單位為s；Err%表示算法對應的測試數(shù)據(jù)的錯分率。

Figure 1　Comparson results of the three algorithms on liver disorders data sets 圖1　三種算法在數(shù)據(jù)集liver disorders上的對比結果

Figure 2　Comparison results of the three algorithms on Statlog data sets 圖2　三種算法在數(shù)據(jù)集Statlog上的對比結果

由表1實驗結果可以看出，在數(shù)據(jù)集規(guī)模增大時，非單調(diào)信賴域算法的運行時間并未明顯增加，并保持相當?shù)臄?shù)據(jù)錯分率。在數(shù)據(jù)錯分率相當?shù)那闆r下，非單調(diào)信賴域算法的CPU運行時間較短，顯現(xiàn)出了較好的優(yōu)勢，且訓練正確率相當，甚至更好。隨機選擇兩個數(shù)據(jù)集Balance Scale和Statlog作為實驗數(shù)據(jù)，通過圖1和圖2可以看出，非單調(diào)信賴域算法(N-T-R Algorithm)與LSVM算法(LSVM Algorithm)和下降法(Decent method)相比，非單調(diào)信賴域算法提高了支持向量機的分類正確率，說明非單調(diào)信賴域算法對于求解互補支持向量機模型是可行的。

7結束語

本文基于互補支持向量機問題，利用Fischer-Burmeister互補函數(shù)將其轉化為無約束優(yōu)化問題并構造該問題的信賴域子問題，給出了求解互補支持向量機的非單調(diào)信賴域算法。新算法通過修正信賴域半徑的校正條件和自適應調(diào)整信賴域半徑搜索最優(yōu)解，克服了在求解大規(guī)模非線性分類問題時需要計算Hesse矩陣及矩陣求逆運算的缺陷，算法過程簡單，易于實現(xiàn)并具有線性收斂性。數(shù)值實驗結果表明，非單調(diào)信賴域算法求解互補支持向量機比LSVM算法和下降點算法優(yōu)越。將半定規(guī)劃與互補支持向量機問題融合將是今后的研究重點。

參考文獻:

[1]Cortes C, Vapnik V.Support-Vector Networks[J]. Machine Learning,1995,20,273-297.

[2]Vapnik V. The nature of statistical learning theory[M].New York:Springer,1998.

[3]Wu Peng,Song Wen-long.An improved SVM-based image edge detection method[J]. Pattern Recognition and Simulation,2012,31(4):65-68.(in Chinese)

[4]Yao Xiao,Yu Le-an.A fuzzy proximal support vector machine model and its application to credit risk analysis[J]. Systems Engineering-Theory & Practice,2012,32(3):549-554.(in Chinese)

[5]Sai Ying,Zhang Feng-ting,Zhang Tao. Research of Chinese stock index futures regression prediction based on support vector machines[J].Chinese Journal of Management of Science,2013,21(3):35-39.(in Chinese)

[6]Ding Shi-fei, Qi Bing-juan, Tan Hong-yan. An overview on theory and algorithm of support vector machines[J]. Journal of University of Electronic Science and Technology of China,2011,40 (1):2-10.(in Chinese)

[7]Mangasarian O L,Musicant D R.Lagrangian support vector machines[J].Journal of Machine Learning Research,2001,3(1):161-177.

[8]Zhang Yang-song, Liu San-yang.Complementarity support vector machines[J].Computer Science,2010,37 (2):165-166.(in Chinese)

[9]Mangasarian O L.Successive over relaxation for support vector machines[J].IEEE Transactions on Neural Networks,1999,10(5):1032-1037.

[10]Fischer A.A special newton-type optimization methods[J].Optimization:A Journal of Mathematical Programming and Operations Research, 1992,24(3):269-284.

[11]Yuan Ya-xiang,Sun Wen-yu. Optimazation theory and method[M].Beijing:Science Press,1997.(in Chinese)

[12]Powell M J D,Yuan Y.A trust region algorithm for equality constrained optimization[J]. Mathematical Programming,1990,49(3):189-211.

[13]Fu J H,Sun W.Nonmonotone adaptive trust-region method for unconstrained optimization problems[J].Applied Mathematics and Compuation,2005,163(5):489-504.

[14]Wang Jian-ping,Lv Yi-bin,Zhang Xiao-peng.A new nonmonotone trust region algorithm of unconstrained optimization[J]. Science Technology and Engineering,2012,12(14):3291-3294.(in Chinese)

[15]Chua C B,Yi P.A continuation method for nonlinear complementarity problems over symmetric cones[J]. SIAM Journal on Optimization,2010,20(5):2560-2583.

[16]Fang L,He G P,Hu Y H. A new smoothing Newton-type method for second-order cone programming problems[J].Applied Mathematics and Computation,2009,215.1020-1029.

[17]Li Gai-di. A trust region method with automatic determination of the trust region radius[J].Journal of Engineering Mathematics,2006,23(5):843-848.(in Chinese)

參考文獻：附中文

[3]吳鵬,宋文龍.一種改善的基于支持向量機的圖像邊緣檢測算法[J].模式識別與仿真,2012,31(4):65-68.

[4]姚瀟,余樂安.模糊近似支持向量機模型及其在信用風險評估中的應用[J].系統(tǒng)工程理論與實踐,2012,32(3):549-554.

[5]賽英,張鳳廷,張濤. 基于支持向量機的中國股指期貨回歸預測研究[J].中國管理科學,2013,21(3):35-39.

[6]丁世飛,齊丙娟,譚紅艷.支持向量機理論與算法研究綜述[J].電子科技大學學報,2011,40(1):2-10.

[8]張襄松,劉三陽.互補支持向量機[J].計算機科學,2010,37(2):165-166.

[11]袁亞湘,孫文瑜.最優(yōu)化理論與方法[M].北京：科學出版社,1997.

[14]王劍平,呂毅斌,張曉鵬.無約束優(yōu)化的一類新的非單調(diào)信賴域算法[J].科學技術與工程,2012,12(14):3291-3294.

[17]李改弟. 一個自動確定信賴域半徑的信賴域方法[J].工程數(shù)學學報,2006,23(5):843-848.

高雷阜(1963-),男,遼寧阜新人，博士，教授，研究方向為最優(yōu)化理論與應用和非線性動力系統(tǒng)預測。E-mail:gaoleifu-@163.com

GAO Lei-fu,born in 1963,PhD,professor,his research interests include optimization theory and application，and nonlinear dynamic system prediction.

于冬梅(1986-),女,遼寧鞍山人，博士生，研究方向為最優(yōu)化理論與應用和錐優(yōu)化。E-mail:yudongmei1113@163.com

YU Dong-mei,born in 1986,PhD candidate,his research interests include optimization theory and application,and cone optimization.

趙世杰(1987-),男,山東五蓮人，博士生，研究方向為最優(yōu)化理論與應用。E-mail:zhao2008shijie@126.com

ZHAO Shi-jie,born in 1987,PhD candidate,his research interests include optimization theory and application.