基于ramp損失函數(shù)的原空間支持向量機

袁玉萍，安增龍

（1.黑龍江八一農(nóng)墾大學(xué) 信息與計算科學(xué)系，黑龍江 大慶163319；2.黑龍江八一農(nóng)墾大學(xué) 經(jīng)濟管理系，黑龍江 大慶163319）

基于ramp損失函數(shù)的原空間支持向量機

袁玉萍1，安增龍2

（1.黑龍江八一農(nóng)墾大學(xué) 信息與計算科學(xué)系，黑龍江 大慶163319；2.黑龍江八一農(nóng)墾大學(xué) 經(jīng)濟管理系，黑龍江 大慶163319）

針對傳統(tǒng)支持向量機對噪聲敏感的問題，給出一種基于不對稱形式的二次不敏感控制型ramp損失函數(shù)的支持向量回歸機，采用凹凸過程優(yōu)化和光滑技術(shù)算法，將非凸優(yōu)化問題轉(zhuǎn)化為連續(xù)且二次可微的凸優(yōu)化問題，利用有限步終止的Amijo-Newton優(yōu)化算法，求解所建立的優(yōu)化模型，并分析了算法的收斂性.該算法不僅可以保持支持向量的稀疏性，而且還可以控制訓(xùn)練樣本中的異常值.實驗結(jié)果表明，該模型保持了很好的泛化能力，無論對模擬數(shù)據(jù)還是標準數(shù)據(jù)都具有一定的擬合精度，與標準支持向量機模型相比，不僅能夠降低噪聲和孤立點的影響，而且也具有較強的魯棒性.

支持向量回歸機；異常值；損失函數(shù)；凹凸過程

0　引言

由于標準支持向量機對所有輸入樣本同等對待，在訓(xùn)練時從中選取部分樣本，利用支持向量機來構(gòu)造最終的決策函數(shù)，同時標準支持向量機對異常值也非常敏感，在確定決策超平面時所起到的作用非常大，降低了支持向量機的泛化能力和推廣能力.因此當樣本中含有噪聲時，建立支持向量機的魯棒性模型是非常重要的.

為了抑制支持向量機對噪聲或野點的影響，提高模型的泛化能力，很多學(xué)者在此方面做了大量工作［1-4］.減少或限制噪聲樣本損失的方法基本分為兩類.一類是將模糊技術(shù)應(yīng)用到支持向量機中.臺灣學(xué)者Lin等在2002年提出了模糊支持向量機方法（Fuzzy Support Vector Machine，F(xiàn)SVM）［5-6］，將模糊技術(shù)應(yīng)用于支持向量機中，根據(jù)不同輸入樣本對訓(xùn)練的貢獻不同賦以不同的隸屬度，對噪聲或野點賦以較小的隸屬度以減小它們對模型的影響，對噪聲樣本乘以較小的模糊因子，使得在構(gòu)造目標函數(shù)時，不同的樣本有不同的貢獻，從而達到降低或者消除噪聲樣本的目的.文獻［7］通過估計訓(xùn)練樣本為噪聲點的可能性大小來調(diào)節(jié)隸屬度，如果一個訓(xùn)練樣本點更接近不屬于自己的另一類，則將該點以較高的概率被看做噪聲；另一類是通過構(gòu)造新的損失函數(shù)以減少或者限制噪聲樣本的損失［8-9］.2006年Xu和Crammer等人建立了基于截斷的Hinge損失的魯棒支持向量機模型［10］，是對Hinge損失函數(shù)的一個很好的替代，該模型是一個非凸非光滑的優(yōu)化問題，利用光滑ramp損失函數(shù)和凹凸過程優(yōu)化算法進行求解.2008年Wang等人提出兩分類問題的魯棒支持向量機，利用非凸的不可微的ramp損失函數(shù)構(gòu)造優(yōu)化模型，采取concave-convex procedure（CCCP）凹凸過程將非凸優(yōu)化問題轉(zhuǎn)化為凸優(yōu)化問題，再利用經(jīng)典的牛頓算法求解［11］.在同一年，Zhao等人在上述方法的基礎(chǔ)上，提出了基于不敏感損失函數(shù)的控制型損失函數(shù)，將基于控制型損失函數(shù)應(yīng)用到魯棒支持向量回歸機問題［12］.Xu等人針對hinge控制型損失函數(shù)提出了針對異常值剔除的魯棒支持向量機，并且將優(yōu)化問題轉(zhuǎn)化為一個半定規(guī)劃問題［13］.

綜合上述分析，文獻［12］是針對兩分類問題提出的ramp損失函數(shù)，文獻［13］提出了基于不敏感的控制型一次損失函數(shù).由于二次不敏感損失函數(shù)在一定范圍內(nèi)函數(shù)變化較快，在二次方區(qū)域內(nèi)對符合高斯分布的噪聲具有較強的抑制作用，并且具有稀疏性，在底部的光滑性比一次不敏感損失函數(shù)好等優(yōu)點，因此，本文提出基于二次不敏感控制型ramp損失函數(shù)的不對稱形式魯棒支持向量回歸機，弱化異常值的干擾，其分段損失函數(shù)對落在不同區(qū)間的誤差項采用不同的懲罰函數(shù)形式.

1　Ramp不對稱形式魯棒支持向量回歸機

1.1原空間支持向量回歸機

原空間魯棒支持向量回歸機模型∶對于隨機產(chǎn)生的訓(xùn)練樣本回歸問題其中xi∈Rn是輸入指標，yi是相對應(yīng)的函數(shù)值.基于ε-不敏感損失函數(shù)支持向量機算法為∶

使得

這里，C是調(diào)節(jié)模型的復(fù)雜性和訓(xùn)練的錯誤的一個折中，在（1）中消去松弛變量1,2,···,N,得到無約束優(yōu)化問題∶

選取二次不敏感控制型ramp損失函數(shù)不對稱形式Hθ（zi）=min（θ2,HA（zi））,其中，

zi=w·xi+b-yi,ε1＜ε2.綜合上式提出的ramp損失函數(shù)為∶

即損失函數(shù)的值在（0,θ2）這個區(qū)間內(nèi)，θ為參數(shù)，顯然限制了樣本的損失.為了簡單起見，在不影響模型的泛化性能情況下先不討論偏執(zhí)b項，同時引入核函數(shù)策略及轉(zhuǎn)化到希爾伯特空間H，得到優(yōu)化問題∶

由表現(xiàn)定理［14］，（3）式的優(yōu)化函數(shù)f可以表示為∶

將（4）式代入（3）式，得∶

令β=［β1,β2,···,βN］T，K為核矩陣，其中Kij=k（xi,xj）,i,j=1,2,···,N，可將（5）式變形為∶

1.2光滑非凸損失函數(shù)的建立

由于Hθ（z）函數(shù)既不光滑也不是凸函數(shù)，難以應(yīng)用凸優(yōu)化方法對相應(yīng)的支持向量回歸機模型求解，因此，需要將其進一步轉(zhuǎn)化為光滑且凸的損失函數(shù)，構(gòu)造兩個huber損失函數(shù)不對稱形式∶

其中zi=-yi,i=1,2,···,N.對于（7）式，不能直接使用凸優(yōu)化技術(shù)解決.所建立的光滑非凸的損失函數(shù)見圖1.

圖1　光滑非凸的損失函數(shù)Fig.1　Smooth non-convex loss function

1.3利用凹凸過程將非凸函數(shù)轉(zhuǎn)仁為凸函數(shù)

凹凸過程（Concave-Convex Procedure，CCCP）［15］是用于求解非凸形式的優(yōu)化問題.假設(shè)目標函數(shù)E（θ）可以寫成一個凹函數(shù)Ecav（θ）和一個凸函數(shù)Evex（θ）的和式，即E（θ）= Ecav（θ）+Evex（θ），求E（θ）的最小值.凹凸過程如下∶

（i）初始化變量θ；

（ii）計算θi+1=argminθ（Evex（θ）+（θi）·θ），直到θi收斂；

（iii）輸出θ=θi.

為了利用CCCP過程，將式（7）分解為凸函數(shù)和凹函數(shù)兩部分∶

其中βn是前一次CCCP迭代中獲得的解，而是Lcav（β）對變量β的一階導(dǎo)數(shù)在βn點的值.

利用CCCP算法，將（7）式轉(zhuǎn)化為在原空間一個凸的、光滑的優(yōu)化問題（10）式，這樣對于（10）式就可以利用比較成熟的凸優(yōu)化方法來解決.

2　Amijo-Newton算法實現(xiàn)及收斂性分析

2.1有限步終止的Amijo-Newton算法［16］

（1）樣本點位于-ε1＜zi＜ε2區(qū)域的訓(xùn)練樣本稱為非支持向量，樣本集合為NSV區(qū)域，樣本數(shù)記為|NSV|；

（2）樣本點位于ε2＜zi＜ε2+θ+h或-ε1-θ-h＜zi＜-ε1的訓(xùn)練樣本稱為支持向量.具體地，可將上述集合分為4個子集合∶樣本點位于ε2＜zi＜ε2+θ，或-ε1-θ＜zi＜-ε1，區(qū)域的訓(xùn)練樣本分別稱為支持向量SV1、SV2，樣本數(shù)記為|SV1|、|SV2|；

樣本點位于ε2+θ＜zi＜ε2+θ+h，或-ε1-θ-h＜zi＜-ε1-θ，區(qū)域的訓(xùn)練樣本分別稱為支持向量SV3、SV4，樣本數(shù)記為|SV3|、|SV4|；

（3）樣本點位于zi＞ε2+θ+h或zi＜-ε1-θ-h的訓(xùn)練樣本分別稱為錯誤支持向量ESV1、ESV2，樣本數(shù)為|ESV1|、|ESV2|.

為了方便，根據(jù)上述的七個區(qū)域?qū)⒂?xùn)練樣本按照SV1,SV2,SV3,SV4,ESV1,ESV2,NSV的順序排列，定義均為N×N的對角矩陣，表示階的單位矩陣，表示|SV2|階 0矩陣.同理，定義

對目標函數(shù)（10）式求關(guān)于β的梯度表達式?L（β）及Hesse矩陣H∶

搜索方向為∶

迭代公式為∶

λ為搜索步長，即可得到（10）式的最優(yōu)解.但是，如果當樣本點的個數(shù)N比較大時，每步都直接計算的逆矩陣，要占計算機很大的空間，大大影響運算效率，因此，重新改寫它的形式為∶

該矩陣的逆矩陣是個稀疏矩陣.

由（14）式得到最優(yōu)解βn+1，其分量的最優(yōu)解即位于這兩個區(qū)域的異常值和非支持向量對決策函數(shù)沒有任何影響，得到?jīng)Q策函數(shù)∶

因此，原空間的魯棒支持向量回歸機在求解過程中，保持對異常值的不敏感性，從而具有更優(yōu)的泛化能力.采取有限步終止的Amijo-Newton算法求解（10）式，具體算法如下∶

Step 2.根據(jù)|z0|=|f0（x）-y|區(qū)域的大小將訓(xùn)練樣本分成七類∶SV1,SV2,SV3,SV4, ESV1,ESV2,NSV；

Step 3.計算梯度?nL（β），若‖?nL（β）‖≤ρ，則停止計算，否則轉(zhuǎn)下一步；

Step 4.令λk=max｛1,1/2,1/4,···｝為Amijo步長，且使得不等式L（βk）-L（βk+成立；

Step 5.根據(jù)（14）式計算βn+1，由（15）式得到函數(shù)fn+1（x），轉(zhuǎn)step 2.

2.2算法收斂性

命題1由有限步終止的Amijo-Newton算法對目標函數(shù)（10）式求解，所得到的序列βn是單調(diào)遞減的.

證明由（7）式，minβ其中是凸部分，是凹部分.若βn+1是該算法對目標函數(shù)（10）式的第n次迭代時得到的最優(yōu)解，則有∶

又根據(jù)凹函數(shù)的性質(zhì)，有

說明該算法是單調(diào)下降的.又由于目標函數(shù)L（β）≥0，即有下界，故該算法收斂.

3　數(shù)據(jù)試驗

為了驗證提出的魯棒支持向量回歸機的有效性，分別對模擬數(shù)據(jù)和標準的UCI數(shù)據(jù)集進行數(shù)值試驗.將本文算法與標準支持向量回歸機進行比較，通過試驗可以看出本文算法能夠有效地抑制異常值對決策超平面的影響.對于非線性回歸問題文中采用高斯核函數(shù)（RBF）∶

在試驗中有6個參數(shù)ε1,ε2,θ,C,σ,h，最優(yōu)參數(shù)（C,σ）采取網(wǎng)格搜索獲得，搜索區(qū)間為｛2-5,2-4,···,24,25｝×｛2-5,2-4,···,24,25｝.參數(shù)h表示光滑ramp損失函數(shù)因子，取值較?。沪仁菓土P函數(shù)的上界，一般數(shù)值設(shè)置在0.1∽10之間.如果θ值取得較大，容易將異常值視為支持向量，增加支持向量的個數(shù)，導(dǎo)致運行速度減慢.如果θ值取得較小，容易將正常值視為異常值，使一些正常值不能參與訓(xùn)練，導(dǎo)致算法降低泛化能力.

采用均方根誤差（RMSE）衡量回歸算法性能的評價指標.實驗環(huán)境為Matlab 7.0，Windows XP，內(nèi)存2 GB，主頻2.99 GHz.

3.1人工數(shù)據(jù)集試驗

設(shè)樣本集T=｛（x1,y1）,（x2,y2）,···,（x300,y300）｝，其中，xi,i=1,2,···,300，均勻分布在區(qū)間［-4,4］，yi=sin（3xi）/（3xi）+γi,i=1,2,···,300,γi∽N（0,0.12），任意選取200個樣本點為訓(xùn)練點，其余的為測試點.將上述數(shù)集進行兩次測試，分別利用最小二乘支持向量機（LS-SVR）和本文算法進行訓(xùn)練和預(yù)測，預(yù)測結(jié)果如圖2、圖3.

圖2　最小二乘（LS-SVR）算法Fig.2　The algorithm of least square support vector regression（LS-SVR）

圖3　本文算法Fig.3　Algorithm in this paper

由圖中可以看出，這兩種支持向量機算法都可以較準確地反映函數(shù)yi=sin（3xi）/（3xi）的整體趨勢.由于本文提出的算法對異常值所造成的損失設(shè)置了懲罰上界，抑制異常值對模型的影響，因此在預(yù)測過程中表現(xiàn)出比最小二乘法具有更高的預(yù)測精度.兩種算法的實驗結(jié)果如表1.另外，最小二乘支持向量機所有的樣本均為支持向量，而本文提出算法異常值被區(qū)分開，不參與最終決策函數(shù)的構(gòu)成，因此在運行時間上也提高了運算效率.

表1　人工數(shù)據(jù)集高斯噪聲的試驗結(jié)果Tab.1　The experimental results on artificial data sets

3.2標準的UCI數(shù)據(jù)集的試驗

為了進一步檢驗本節(jié)提出的算法性能，選取標準數(shù)據(jù)庫中的數(shù)據(jù)集作為試驗數(shù)據(jù)集，實驗數(shù)據(jù)來源于UCI數(shù)據(jù)庫（http∶//archive.ics.uci.edu/ml/）、StatLib數(shù)據(jù)庫（http∶//lib.stat.cmu. edu/datasets/）.數(shù)據(jù)集的統(tǒng)計信息見表2.

表2　數(shù)據(jù)集的統(tǒng)計信息Tab.2　Statistical information on data set

為了比較算法的性能，將本文算法、NP-RSVR-NCLF（N-R-N）算法［10］及LS-SVR算法的試驗結(jié)果進行比較，比較結(jié)果見表3.

表3　NP-RSVR-NCLF算法、LS-SVR算法和本文算法的標準UCI數(shù)據(jù)集的試驗結(jié)果對比Tab.3　Comparison of the experimental results of standard UCI data set with NP-RSVR-NCLF algorithm，LS-SVR algorithm and the algorithm in this paper

表3中數(shù)據(jù)結(jié)果是10次試驗的平均值，由試驗結(jié)果可以看到本文算法在各數(shù)據(jù)集上的誤差率比LS-SVR算法小很多，與NP-RSVR-NCLF算法誤差率相當.另外，一個算法的效率也是非常重要的，可以看出本文提出的算法所對應(yīng)的衡量預(yù)測精度指標均小于LS-SVR，而且具有較好的穩(wěn)定性，支持向量的個數(shù)比較少，提高了運行速度，運行的時間同時也明顯減少.

4　結(jié)論

本文提出了原空間非凸不對稱形式損失函數(shù)魯棒支持向量機，利用CCCP過程將非凸優(yōu)化問題轉(zhuǎn)化為連續(xù)可微的凸優(yōu)化問題，利用帶步長的Armijo-Newton算法進行求解.該非凸損失函數(shù)不僅保持了支持向量回歸機的稀疏性，而且在一定程度上控制了訓(xùn)練點中的異常值，從而可以增強泛化性能，在對性能影響很小的情況下，最大程度減少支持向量的冗余程度.通過模擬和真實的標準數(shù)據(jù)集上的實驗，驗證了本文所提出的算法的有效性.

［1］TSUJINISHI D，ABE S.Fuzzy least squares support vector machines for multiclass problems［J］.Neural Networks，2003，16（5/6）：785-792.

［2］XIU F J，ZHANG Y，JIAN C L.Fuzzy SVM with a new fuzzy membership function［J］.Neural Computing and Application，2006（15）：268-276.

［3］LIU Y H，CHEN Y T.Face recongnition using total margin-based adaptive fuzzy support vector machines［J］. IEEE Trans on Neural Networks，2007，18（1）：178-192.

［4］YU S，YANG X W，HAO Z F，et al.An adaptive support vector machine learning algorithm for large classification problem［J］.Lecture Notes in Computer Science，2006，3971：981-990.

［5］LIN C F，WANG S D.Fuzzy support vector machines［J］.IEEE Transactions on Neural Networks，2002，3（2）：464-471.

［6］JIN B，ZHANG Y Q.Classifying very large data sets with minimum enclosing ban based support vector machine［C］//Proceedings of the 2006 IEEE International Conference on Fuzzy Systems.Vancouver BC，2006：364-368.

［7］BO L，WANG L，JIAO L.Recursive finite Newton algorithm for support vector regression in the primal［J］. Neural Computation，2007，19（4）：1082-1096.

［8］CHEN X B，YANG J，LIANG J，et al.Recursive robust least squares support vector regression based on maximum correntropy criterion［J］.Neurocomputing，2012，97：63-73.

［9］楊俊燕，張優(yōu)云，朱永生.不敏感損失函數(shù)支持向量機分類性能研究［J］.西安交通大學(xué)學(xué)報，2007，4l（11）：1315-1320.

［10］HUANG H，LIU Y.Fuzzy support vector machines for pattern recognition and data mining［J］.International Journal of Fuzzy Systems，2002，4（3）：3-12.

［11］WANG L，JIA H，LI J.Training robust support vector machine with smooth ramp loss in the primal space［J］Neurocomputing，2008，71（13/14/15）：3020-3025.

［12］ZHAO Y，SUN J.Robust support vector regression in the primal［J］.Neural Networks，2008，21（10）：1548-1555.

［13］YANG S H，HU B G.A stagewise least square loss function for classfication［C］//Proceedings of the SIAM International Conference on Data Mining.2008，120-131.

［14］KIMELDORF G S，WAHBA G.A correspondence between Bayesian estimation on stochastic processes and smoothing by splines［J］.Annals of Mathematical Statistics，1970，41（2）：495-502.

［15］YUILLE A L，RANGARAJAN A.The concave-convex procedure（CCCP）［J］.Neural Computation，2003，15（4）：915-936.

［16］FUNG G，MANGASARIAN O L.Finite Newton method for Lagrangian support vector machine classification［J］.Neurocomputing，2003，55（1/2）：39-55.

（責任編輯：林磊）

Support vector machine in the primal space based on the ramp loss function

YUAN Yu-ping1，AN Zeng-long2
（1.College of Sciences，Heilongjiang Bayi Agricultural University，Daqing Heilongjiang 163319，China；2.College of Economics&Management，Heilongjiang Bayi Agricultural University，Daqing Heilongjiang163319，China）

Aiming at the problem of standard support vector machine being sensitive to the noise，a new method of support vector regression（SVR）machine based on dissymmetry quadratic and controlled-insensitive loss function is proposed.Using the concave and convex process optimization and the smooth technology algorithm，the problem of non-convex optimization is transformed into the problem of the continuous and twice diferentiable convex optimization.Using the Amijo-Newton optimized algorithm of finiteiteration termination，the established optimization model is solved，and the convergence of the algorithm is analyzed.The algorithm can not only keep the sparse nature of support vector，but also control the abnormal values of the training sample.The results of the experiment showed that the support vector regression machine model proposed kept good generalization ability，and the model could fit better both the simulated data and the standard data.Compared with the standard support vector machine（SVM）model，the proposed model not only can reduce the efects of noise and outliers，but also has stronger robustness.

support vector regression；outliers；loss function；concave-convex procedure

TP181；TP391

A

10.3969/j.issn.1000-5641.2016.02.003

1000-5641（2016）02-0020-10

2015-03

高等學(xué)校博士學(xué)科點專項科研基金（20112305110002）；黑龍江八一農(nóng)墾大學(xué)博士科研啟動基金（XDB2015-23）；黑龍江農(nóng)墾總局科研資助項目（HNK11A-14-07）

袁玉萍，女，博士，研究方向為運籌學(xué)與優(yōu)化.E-mail：byndyyps@sina.com.

安增龍，男，教授，研究方向為人力資源管理.E-mail：anzl@2001@163.com.