基于Rescaled Hinge損失函數(shù)的多子支持向量機(jī)

李 卉，楊志霞

（新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊 830046）

（?通信作者電子郵箱yangzhx@xju.edu.cn）

0 引言

分類問題是機(jī)器學(xué)習(xí)中研究的熱點(diǎn)問題之一，針對(duì)此問題Vapink 在VC（Vapnik-Chervonenkis）維和統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上提出支持向量機(jī)（Support Vector Machine，SVM）［1］。與其他機(jī)器學(xué)習(xí)方法（例如人工神經(jīng)網(wǎng)絡(luò)［2］）相比，支持向量機(jī)具有許多優(yōu)勢(shì)。首先，支持向量機(jī)解決一個(gè)凸二次規(guī)劃問題，確保一旦獲得最佳解，它就是唯一解。其次，支持向量機(jī)通過(guò)最大化兩個(gè)類之間的間隔來(lái)得出模型，并基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，而不是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則。目前，支持向量機(jī)已應(yīng)用于不同領(lǐng)域，例如疾病診斷［3-4］、文本分類［5］和企業(yè)信用等級(jí)［6］等。

鑒于支持向量機(jī)優(yōu)越的性能，迄今為止它的擴(kuò)展版本得到了長(zhǎng)足發(fā)展。2007 年，Jayadeva 等［7］提出一種基于非平行分劃超平面思想的雙支持向量機(jī)（TWin Support Vector Machine，TWSVM）。雙支持向量機(jī)與廣義特征值中心支持向量機(jī)［8］的想法相似，都針對(duì)給定訓(xùn)練集生成兩個(gè)非平行超平面解決二分類問題，但優(yōu)化問題的構(gòu)造不同。由于這兩個(gè)方法都是基于非平行超平面的思想構(gòu)造最終的決策函數(shù)，從而使得學(xué)習(xí)機(jī)具有更好的靈活性和泛化能力。最近，雙支持向量機(jī)的一些擴(kuò)展算法也被不斷提出，如文獻(xiàn)［9-10］。然而，在現(xiàn)實(shí)生活中有許多需要解決的問題為多分類問題，如圖像分類［11］、疾病分類［12］、蛋白質(zhì)折疊識(shí)別［13］等。以雙支持向量機(jī)為基礎(chǔ)，文獻(xiàn)［14］提出多子支持向量機(jī)（Multiple Birth Support Vector Machine，MBSVM）解決多分類問題。多子支持向量機(jī)通過(guò)求解K 個(gè)小規(guī)模二次規(guī)劃問題來(lái)得到?jīng)Q策函數(shù)，從而有較低的計(jì)算復(fù)雜度，針對(duì)多分類問題具有一定的優(yōu)越性。

另一方面，在現(xiàn)實(shí)生活中，收集到的數(shù)據(jù)往往帶有噪聲，或者標(biāo)簽記錯(cuò)，這樣的數(shù)據(jù)稱之為異常值。多分類算法在遇到異常值的情況下，算法的性能會(huì)有所下降。有很多研究處理異常值都是通過(guò)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，直接剔除異常值；然而直接剔除異常值會(huì)出現(xiàn)信息丟失等問題。因此，在不刪除異常值的前提下，提出魯棒的分類方法成為熱門的研究。例如，文獻(xiàn)［15］提出求解有噪聲數(shù)據(jù)的二分類方法，稱作基于Rescaled Hinge損失函數(shù)的魯棒支持向量機(jī)（Robust Support Vector Machines based on Rescaled Hinge loss function，RSVM-RHHQ）。

為了提高多分類方法對(duì)異常值的魯棒性，本文提出基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)（Multiple Birth Support Vector Machine based on Rescaled Hinge loss function，RHMBSVM）。該方法通過(guò)將有界、非凸的Rescaled Hinge 損失函數(shù)引入多子支持向量機(jī)的優(yōu)化問題中，從而得到魯棒的優(yōu)化問題。事實(shí)上，該方法是一個(gè)加權(quán)多子支持向量機(jī)。給每個(gè)點(diǎn)不同的懲罰，從而可識(shí)別異常值，提高魯棒性。其次，針對(duì)K 個(gè)非凸優(yōu)化問題，通過(guò)共軛函數(shù)理論將問題進(jìn)行等價(jià)轉(zhuǎn)換，利用變量交替策略構(gòu)造迭代算法，使問題得到了有效求解。本文方法主要的優(yōu)勢(shì)和特點(diǎn)可總結(jié)為如下3個(gè)方面：

1）針對(duì)多類分類問題，本文方法使用了非平行分劃超平面的思想，所構(gòu)建的優(yōu)化模型只需求解K 個(gè)小規(guī)模的二次規(guī)劃問題，主要求解對(duì)偶問題的未知量個(gè)數(shù)只與第k 類樣本點(diǎn)的個(gè)數(shù)有關(guān)，有效降低了計(jì)算復(fù)雜度。

2）針對(duì)帶異常值的多類分類問題，本文方法通過(guò)將Rescaled Hinge 損失函數(shù)引入到多子支持向量機(jī)中，給每個(gè)樣本點(diǎn)不同的懲罰，從而減弱異常值對(duì)模型性能的影響。

3）針對(duì)線性情形和非線性情形的多類分類問題，本文方法分別給出了具體的優(yōu)化模型和求解算法。具體地，當(dāng)多類分類問題只需超平面就可分劃時(shí)，使用線性情形的算法；否則，就使用引入核函數(shù)的非線性情形的算法。值得注意的是，當(dāng)非線性情形選擇的是線性核時(shí)，算法即可退化為線性情形。

數(shù)值實(shí)驗(yàn)結(jié)果表明，在無(wú)異常值的UCI數(shù)據(jù)集中，本文方法的正確率比現(xiàn)有的多分類方法高。在有異常值的UCI數(shù)據(jù)集中，本文方法的魯棒性優(yōu)于現(xiàn)有的多分類方法。

1 準(zhǔn)備知識(shí)

本章介紹了多子支持向量機(jī)和Rescaled Hinge損失函數(shù)。給定訓(xùn)練集：

1.1 多子支持向量機(jī)

多子支持向量機(jī)的思想是針對(duì)訓(xùn)練集T（1）尋找K個(gè)超平面，第k個(gè)超平面具體形式如下：

多子支持向量機(jī)通過(guò)求解K個(gè)小規(guī)模二次規(guī)劃問題來(lái)得到式（2）所示的超平面。其原理是第k類樣本點(diǎn)離第k個(gè)超平面盡可能遠(yuǎn)，其余K -1 類樣本點(diǎn)離第k 個(gè)超平面盡可能近，從而可構(gòu)造多子支持向量機(jī)的第k個(gè)小規(guī)模二次規(guī)劃問題：

1.2 Rescaled Hinge損失函數(shù)

在本節(jié)中，簡(jiǎn)單介紹一下Rescaled Hinge損失函數(shù)［15］。在文獻(xiàn)［16］中，用Correntropy［17］得到的損失函數(shù)C-loss為：

其中σ 是窗寬，常數(shù)當(dāng)z=0 時(shí)，lC(0)=1。若定義最小二乘損失函數(shù)lls(z)=(1-z)2［18］，損失函數(shù)C-loss可寫為：

其中l(wèi)hinge(z)=max(0，1-z)，當(dāng)z=0時(shí)，lrhinge(0)=1。

圖1［15］展示了Hinge 損失函數(shù)和不同η 的Rescaled Hinge損失函數(shù)的直觀幾何圖像。

圖1 Hinge損失函數(shù)和不同η值Rescaled Hinge 損失函數(shù)Fig.1 Hinge loss function and Rescaled Hinge loss function with different η

從圖像可看出Hinge 損失函數(shù)和Rescaled Hinge 損失函數(shù)都是單調(diào)函數(shù)，而Hinge損失函數(shù)是凸函數(shù)，Rescaled Hinge損失函數(shù)是非凸函數(shù)。從圖中也可看出，η 的值越接近0，Rescaled Hinge損失函數(shù)就越接近Hinge損失函數(shù)。

2 模型的提出

針對(duì)帶有異常值的多分類問題，本文提出基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)（RHMBSVM）。該方法包括線性情形和非線性情形：線性情形針對(duì)超平面能夠分劃的多類分類問題提出，最終的決策函數(shù)由K 個(gè)超平面構(gòu)成；否則，本文通過(guò)引入核函數(shù)，構(gòu)造非線性情形的優(yōu)化模型，從而可得到K 個(gè)超曲面來(lái)構(gòu)造最終的決策函數(shù)。值得注意的是，當(dāng)非線性情形時(shí)，如果選擇線性核函數(shù)，模型可退化為線性情形。

2.1 線性情形

現(xiàn)給出直觀的線性情形的優(yōu)化模型和求解過(guò)程。給定訓(xùn)練集T（1），構(gòu)造如下K個(gè)超平面：

為了得到上述超平面，構(gòu)造如下原始優(yōu)化問題：

其中ck≥0 是懲罰參數(shù)。優(yōu)化問題（9）中，目標(biāo)函數(shù)的第一項(xiàng)表示除了第k類樣本以外的K -1類樣本離第k個(gè)超平面盡可能近，第二項(xiàng)表示第k類樣本離第k個(gè)超平面盡可能地遠(yuǎn)。為了使不同的樣本賦予不同的權(quán)重，這里使用了有界、非凸的Rescaled Hinge損失函數(shù)。

現(xiàn)在給出求解優(yōu)化問題（9）的求解過(guò)程，由于β 是常數(shù)，對(duì)優(yōu)化問題（9））沒有影響，因此優(yōu)化問題（9）等價(jià)于下面的優(yōu)化問題：

由于引入非凸的Rescaled Hinge 損失函數(shù)，導(dǎo)致優(yōu)化問題（10）為一個(gè)非凸的優(yōu)化問題，不方便求解，因此，通過(guò)共軛函數(shù)理論對(duì)優(yōu)化問題（10）進(jìn)行等價(jià)轉(zhuǎn)換，再采用變量交替策略得到優(yōu)化問題（10）解(wk，bk)。具體地，引入輔助函數(shù)h(v)=-v ln(-v)+v(v ＜0)，根據(jù)共軛函數(shù)理論［19］，h(v)的共軛函數(shù)為：

接下來(lái)，將共軛函數(shù)理論應(yīng)用到需要求解的非凸優(yōu)化問題（10）中。

由于求解式（18）的上界，等價(jià)于求解式（18）的最大值。因此，優(yōu)化問題（10）等價(jià)為如下形式：

此時(shí)，式（20）第二項(xiàng)中損失函數(shù)的系數(shù)可統(tǒng)一寫成一個(gè)關(guān)于的函數(shù)的形式因此，優(yōu)化問題（20）可寫成：

從優(yōu)化問題（21）看出，與多子支持向量機(jī)的優(yōu)化問題不同之處是懲罰參數(shù)是關(guān)于的函數(shù)，從而給予每個(gè)樣本不同的懲罰，由此可降低異常值的影響。優(yōu)化問題（21）的解可通過(guò)求解其對(duì)偶問題得到。通過(guò)引入拉格朗日乘子向量αk，構(gòu)造拉格朗日函數(shù)，利用KKT（Karush-Kuhn-Tucker）條件，可得優(yōu)化問題（21）的對(duì)偶問題［14］：

采用變量交替策略求解優(yōu)化問題（19）的第二步，當(dāng)?shù)玫絻?yōu)化問題（21）的解(wk，bk)時(shí)，則優(yōu)化問題（19）的目標(biāo)函數(shù)第一項(xiàng)為常數(shù)，不影響優(yōu)化問題的解。因此，優(yōu)化問題（19）等價(jià)于：

根據(jù)共軛函數(shù)理論中的式（17）和v 與r的關(guān)系式，得到解的關(guān)系式由解的關(guān)系知式（24）的解析解為：

將預(yù)測(cè)點(diǎn)x代入決策函數(shù)，可得相應(yīng)的類別標(biāo)簽。

綜上，歸納線性基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)算法步驟如下：

1）初始化參數(shù)。選擇合適的參數(shù)η ＞0和懲罰參數(shù)ck，迭代收斂精度δ。設(shè)置s=0和=-1(i=1，2，…，lk)。

2.2 非線性情形

不難想象，很多情況下多類分類問題不能用K 個(gè)超平面來(lái)構(gòu)造決策函數(shù)，此時(shí)可使用核映射將樣本點(diǎn)映射到Hilbert空間中，在Hilbert 空間中可實(shí)現(xiàn)線性分劃，此時(shí)在原空間中即是非線性分劃。將針對(duì)非線性情形，尋找如下帶有核函數(shù)的K個(gè)超曲面：

其中E 是由所有樣本點(diǎn)構(gòu)成的矩陣，ET=[A1，A2，…，AK]T，K(?，?)是核函數(shù)。注意到，當(dāng)核函數(shù)被選取為線性核函數(shù)時(shí)，上述超曲面可退化為超平面。為得到式（27）所示的超曲面，構(gòu)造如下的優(yōu)化問題：

其中ck≥0是懲罰參數(shù)。

現(xiàn)在，給出優(yōu)化問題（28）的求解過(guò)程。與線性情形的求解過(guò)程相似，用共軛函數(shù)理論將優(yōu)化問題（28）作等價(jià)變換。令代入共軛函數(shù)理論得到式

（14），則優(yōu)化問題（28）可用下面的形式表示：

采用變量交替策略求解優(yōu)化問題（29）的第二步，將(uk，bk)代入優(yōu)化問題（29）中，可得：

同理，根據(jù)共軛函數(shù)理論，可知式（33）的解析解為：

綜上，歸納非線性基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)算法步驟如下：

1）初始化參數(shù)。選擇合適的核函數(shù)K(?，?)，參數(shù)η ＞0，核參數(shù)p 和懲罰參數(shù)ck，迭代收斂精度δ。設(shè)置s=0 和

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

本章用基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)（RHMBSVM）與多子支持向量機(jī)（MBSVM）［14］、基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機(jī)（RSVM-RHHQ）［15］進(jìn)行比較。其中，由于基于Rescaled Hinge損失函數(shù)的魯棒支持向量機(jī)只能求解二分類問題，所以本文使用該方法時(shí)利用了“一對(duì)余”策略解決多分類問題，并在Matlab中編輯其代碼。按照多子支持向量機(jī)和基于Rescaled Hinge損失函數(shù)的多子支持向量機(jī)的算法，在Matlab軟件中編輯相應(yīng)的代碼。為了方便計(jì)算，設(shè)參數(shù)η ∈{0.2，0.5，1，2，3，4}，懲罰參數(shù)c=c1=c2=…=ck選自集合{2-8，2-4，2-1，21，24，28}。選用高斯核函數(shù)K(x，x')=其中的參數(shù)p 選自集合{1，3，5，7，9}。用五折交叉驗(yàn)證［20］選擇參數(shù)，并計(jì)算各種方法的正確率。實(shí)驗(yàn)環(huán)境：內(nèi)存為4.00 GB，64 位的Windows 7 操作系統(tǒng)中用軟件Matlab R2016b運(yùn)行得到。

為了檢驗(yàn)本文提出的方法的有效性，在UCI 數(shù)據(jù)庫(kù)中選取了6 組數(shù)據(jù)集，它們分別是：iris、wine、glass、vowel、vehicle、svmguide2。表1給出了6組數(shù)據(jù)集的詳細(xì)信息。

表1 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集Tab.1 UCI datasets used in the experiment

本文采用正確率（Accuracy，AC）來(lái)衡量分類性能。為了表明本文方法性能，針對(duì)6 個(gè)UCI 數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，并與多子支持向量機(jī)和基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機(jī)進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表2所示。

表2 各方法在無(wú)噪聲數(shù)據(jù)集上的正確率和標(biāo)準(zhǔn)差 單位：%Tab.2 Accuracy and standard deviation of different methods on noise-free datasets unit：%

表2中對(duì)最高正確率進(jìn)行加粗，由表2可看出本文方法在6個(gè)數(shù)據(jù)集中有4個(gè)數(shù)據(jù)集的正確率都比對(duì)比方法高，并且本文的方法對(duì)于數(shù)據(jù)集glass 和vehicle 計(jì)算的正確率也和對(duì)比方法的結(jié)果差不多。從表2 的最后一行可以看出，在對(duì)不加噪聲的UCI數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)中，本文方法正確率比MBSVM平均提升1.11個(gè)百分點(diǎn)，比RSVM-RHHQ 平均提升0.74個(gè)百分點(diǎn)。因此，表明本文方法比現(xiàn)有的兩種多分類方法具有更高的正確率。

為了表明基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)的魯棒性，分別選取6 個(gè)UCI 數(shù)據(jù)集25%或50%的特征，加入均值為0，方差為0.01 或0.05 的高斯白噪聲，并與多子支持向量機(jī)和基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機(jī)進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表3所示。

由表3 可看出，加入不同的噪聲，本文方法的性能優(yōu)于多子支持向量機(jī)和基于Rescaled Hinge 損失函數(shù)的魯棒支持向量機(jī)，且噪聲對(duì)算法的影響較小。從標(biāo)準(zhǔn)差可知，本文方法的結(jié)果更穩(wěn)定。從表3 中各方法計(jì)算的平均值可看出，在對(duì)加噪聲UCI數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)中，本文方法正確率比MBSVM 提升2.10 個(gè)百分點(diǎn)，比RSVM-RHHQ 提升1.47 個(gè)百分點(diǎn)，體現(xiàn)出本文方法與其他兩種多分類方法相比，對(duì)有噪聲的數(shù)據(jù)集具有更好的魯棒性。

分類的結(jié)果與參數(shù)的選擇有很大的關(guān)系，圖2 展示了本文 方法 在 參數(shù)c ∈{2-8，2-4，2-1，21，24，28}和p ∈{1，3，5，7，9}時(shí)，分別繪制正確率的三維柱狀圖，柱狀圖中的每一個(gè)都是由一對(duì)參數(shù)c和p確定。

如圖2 所示，在所有數(shù)據(jù)集中，對(duì)參數(shù)c 和p 的變化敏感度最低的是wine數(shù)據(jù)集，敏感度較高的有vehicle和svmguide2數(shù)據(jù)集。在選擇參數(shù)時(shí)，可看出這六個(gè)數(shù)據(jù)集中的大部分?jǐn)?shù)據(jù)集選擇的參數(shù)在p=1，c=21。

表3 各方法在有噪聲數(shù)據(jù)集上的正確率和標(biāo)準(zhǔn)差 單位：%Tab.3 Accuracy and standard deviation of different methods on datasets with noise unit：%

圖2 在參數(shù)c和p不同值時(shí)，RHMBSVM在UCI數(shù)據(jù)集上的正確率Fig.2 Accuracy of RHMBSVM on UCI datasets with different values of parameters c and p

4 結(jié)語(yǔ)

在本文中，對(duì)多分類問題中存在異常值這一現(xiàn)象，本文將Rescaled Hinge 損失函數(shù)引入傳統(tǒng)的多子支持向量機(jī)中，提出了基于Rescaled Hinge 損失函數(shù)的多子支持向量機(jī)。在求解過(guò)程中發(fā)現(xiàn)，本文方法實(shí)際上是一個(gè)加權(quán)的多子支持向量機(jī)，給每個(gè)點(diǎn)不同的懲罰，使異常值對(duì)決策函數(shù)產(chǎn)生更小的影響。本文方法只需求解K 個(gè)小規(guī)模的二次規(guī)劃問題，有相對(duì)低的計(jì)算復(fù)雜度。對(duì)UCI 數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，并與多子支持向量機(jī)和基于Rescaled Hinge損失函數(shù)的魯棒支持向量機(jī)的“一對(duì)余”策略進(jìn)行了實(shí)驗(yàn)比較，表明了在多子支持向量機(jī)中，引入Rescaled Hinge 損失函數(shù)，進(jìn)一步提高了算法的準(zhǔn)確性和魯棒性。接下來(lái)可以探索如何降低異常值對(duì)支持向量機(jī)推廣到多分類算法的影響，并且文中參數(shù)較多，也可對(duì)參數(shù)的分析和選擇進(jìn)行更深入探究。