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

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

高雷阜，于冬梅，趙世杰

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

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A

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

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

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

作者簡介:

通信地址：123000 遼寧省阜新市遼寧工程技術(shù)大學(xué)理學(xué)院

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引言

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

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

2問題的提出

假設(shè)訓(xùn)練:

(1)

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

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

(2)

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

(3)

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

(4)

并利用:

(5)

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

3問題的轉(zhuǎn)化

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

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

(6)

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

定義2

(7)

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

(8)

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

(9)

(10)

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

(11)

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

則真實(shí)下降量與預(yù)估下降量的比值rk為:

(12)

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

定義3

(13)

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

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

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

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

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

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

步驟5校正信賴域半徑:

步驟6修正gk+1，k=k+1，轉(zhuǎn)步驟2。

5算法收斂性分析

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

(14)

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

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

由引理1和引理2可知:

□

(15)

(16)

可以證明對任意k都有：

(17)

當(dāng)k→∞時(shí)，有：

由式(17)可知，當(dāng)k充分大時(shí)，

□

證明由假設(shè)條件可以得到：

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

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

故，

又由于

□

6數(shù)值實(shí)驗(yàn)

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

Table 1　Comparison of the numerical results of the three algorithms

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

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

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

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

7結(jié)束語

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

參考文獻(xiàn):

[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)

參考文獻(xiàn)：附中文

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

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

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

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

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

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

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

[17]李改弟. 一個(gè)自動(dòng)確定信賴域半徑的信賴域方法[J].工程數(shù)學(xué)學(xué)報(bào),2006,23(5):843-848.

高雷阜(1963-),男,遼寧阜新人，博士，教授，研究方向?yàn)樽顑?yōu)化理論與應(yīng)用和非線性動(dòng)力系統(tǒng)預(yù)測。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àn)樽顑?yōu)化理論與應(yīng)用和錐優(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àn)樽顑?yōu)化理論與應(yīng)用。E-mail:zhao2008shijie@126.com

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