SVM及其魯棒性研究

吉衛(wèi)衛(wèi)，譚曉陽(yáng)

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

支持向量機(jī)(SVM)是借助于最優(yōu)化方法解決數(shù)據(jù)挖掘中若干問題的有力工具，所得分類器的復(fù)雜度可采用支持向量的個(gè)數(shù)，而不是變換空間的維數(shù)來刻劃，因此它在一定程度上克服了“維數(shù)災(zāi)難”和“過學(xué)習(xí)”等傳統(tǒng)困難。并在諸多領(lǐng)域有成功的應(yīng)用［1］。

文中針對(duì)圖像中含有類別噪聲［2］的人臉識(shí)別問題，證明SVM本身對(duì)噪聲具備一定的魯棒性。通過調(diào)節(jié)目標(biāo)函數(shù)中的正則化參數(shù)，能夠盡量減少噪聲的影響。丟棄部分被判定為噪聲的樣本將進(jìn)一步改善性能。PubFig數(shù)據(jù)集上的實(shí)驗(yàn)證明，當(dāng)噪聲率低于約40%時(shí)，算法仍有效。

1 SVM方法及其魯棒性

文中的目標(biāo)類別識(shí)別為二分類問題:給定一個(gè)測(cè)試圖像x，預(yù)測(cè)其目標(biāo)類別的概率。用SVM作為分類器模型，訓(xùn)練一個(gè)支持向量機(jī)的目標(biāo)是找到一個(gè)具有最大間隔的分隔平面。支持向量是那些到平面距離最近的模式。非線性情況下SVM的目標(biāo)函數(shù)如下:

其Lagrange函數(shù)為

分別對(duì)W和ξ求導(dǎo)

將 W、αi代入L(W，ξ)得其對(duì)偶表示為

KKT條件

通過討論SVM的部分KKT條件，以考察非線性可分情況下SVM的抗噪性。

文中所提的“管道壁”是指SVM中“最大間隔”的邊緣，而“管道”是指最大間隔之間的部分。

(1)αi=0?γi=C?ξi=0，代入 yi(w·xi+b) －1+ξi＞0?yi(w·xi+b)＞1?樣本位于“管道壁”外，為非支持向量。

(2)αi=C?γi=0?ξi＞0，代入 yi(w·xi+b) －1+ξi=0?yi(w·xi+b)=1－ξi＜1?樣本位于“管道壁”里，為支持向量。

(3)0 ＜αi＜ =C?γi＞0?ξi=0，?yi(w·xi+b)=1?樣本位于“管道壁”上，為支持向量。

從以上分析可見，當(dāng)樣本位于“管道壁”外及“管道壁”上時(shí)，ξi的值均為0，這時(shí)樣本只會(huì)影響投影方向W。而當(dāng)樣本位于“管道壁”里時(shí)，ξi＞0，即這些樣本決定SVM的目標(biāo)函數(shù)的第二部分。當(dāng)樣本被正確分類時(shí)，0＜ξi＜1，否則 ξi＞1。當(dāng)樣本被正確分類但卻含有噪聲時(shí)，使本來應(yīng)介于0和1之間的ξi變得＞1，顯然會(huì)使目標(biāo)函數(shù)值變大，背離了最小化目標(biāo)函數(shù)的原則，不利于分類器改善。

討論“管道”的寬度對(duì)SVM的影響。直觀上講，當(dāng)“管道”越寬時(shí)，進(jìn)入其中的樣本數(shù)量越多，即支持向量個(gè)數(shù)越多。因?yàn)镾VM服從聚類假設(shè)，當(dāng)管道寬時(shí)，“管道壁”距離兩類中心的距離越近，支持向量的個(gè)數(shù)就可能越多，這些支持向量中噪聲的所占的比例就越低，即噪聲對(duì)W的方向起到的作用就越少，這是其有利的方面;不利的方面是支持向量多了，原本對(duì)分類無(wú)影響的非支持向量的個(gè)數(shù)就減少，尤其當(dāng)噪聲數(shù)據(jù)由非支持向量變?yōu)橹С窒蛄繒r(shí)，可能減弱分類器的性能。

當(dāng)“管道”越窄時(shí)，進(jìn)入其中的樣本數(shù)量就越少。原本是噪聲的支持向量可能因“管道”變窄而成為非支持向量，對(duì)分類器不再產(chǎn)生影響，這是其有利方面;不利方面是“管道”越窄，距離兩類中心的距離越遠(yuǎn)，樣本數(shù)量越少，支持向量的個(gè)數(shù)也會(huì)相應(yīng)少，這時(shí)若支持向量中有噪聲，可能會(huì)大大影響W的方向，使分類器不再具有良好的判斷能力。

綜上所述，“管道”的寬窄各有利弊，研究的目標(biāo)就是在“管道”寬度和進(jìn)入管道的樣本數(shù)量之間找到最佳值，即保證投影方向不會(huì)發(fā)生很大變化，又使錯(cuò)誤率盡量降低。

2 實(shí)驗(yàn)結(jié)果

2.1 PubFig數(shù)據(jù)集

在PubFig數(shù)據(jù)集上隨機(jī)選出的100個(gè)名人數(shù)據(jù)集上評(píng)估算法性能。PubFig數(shù)據(jù)集包含了200個(gè)公眾人物的58797張圖片，每個(gè)人有大量不同姿勢(shì)、光照條件和表情的圖片。圖1(c)展示了一個(gè)人的所有圖像［3］。PubFig分為一個(gè)60人的發(fā)展集和一個(gè)140人的估計(jì)集，見圖1(a)和圖1(b)。通常網(wǎng)站中給出的是圖像的URL鏈接，經(jīng)批量下載后得到圖像，但由于網(wǎng)絡(luò)等原因，所有的人臉不能全部下載成功，因此，實(shí)驗(yàn)中的圖像是能夠下載成功的部分。從所有圖片中隨機(jī)選取了100個(gè)不同的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。對(duì)于每個(gè)名人數(shù)據(jù)集，作為正類，其他隨機(jī)選出的數(shù)量相同的圖像作為負(fù)類，進(jìn)行100次實(shí)驗(yàn)，取平均值作為最后結(jié)果。圖2是一組類別噪聲數(shù)據(jù)的舉例，在沒有噪聲的數(shù)據(jù)中，正類為Bush的圖像，負(fù)類為其他的人臉圖像;含噪聲的數(shù)據(jù)中，Bush圖像中包含了其他的人臉圖像，而其他人臉圖像中也可能包含了Bush的圖像。實(shí)驗(yàn)中對(duì)圖像的處理采取以下方式:(1)定位圖像中的人臉;(2)提取每張人臉的眼睛坐標(biāo);(3)將所有定位好的人臉圖像根據(jù)眼睛坐標(biāo)歸一化，處理好的結(jié)果如圖3所示，作為學(xué)習(xí)器的輸入。

文中用到3個(gè)數(shù)據(jù)集:原始訓(xùn)練集、增量集與測(cè)試集，由隨機(jī)劃分的方式產(chǎn)生。對(duì)任一數(shù)據(jù)集而言，隨機(jī)挑選30%的樣本作為原始訓(xùn)練集、30%樣本作為增量集，其余40%作為測(cè)試集。然后，根據(jù)一定的噪聲率隨機(jī)地將增量集中樣本的類別標(biāo)記取反，作為噪聲。為模擬真實(shí)問題中噪聲率的不同比例，分別采用了4種不同的噪聲率，分別是10%，20%，30%和40%。在數(shù)據(jù)劃分過程中，原始訓(xùn)練集、增量集和測(cè)試集中樣本的分布保持一致［4］。為得到更加精確的結(jié)果，每種噪聲都進(jìn)行了20遍實(shí)驗(yàn)，將它們的均值作為最后的結(jié)果。值得注意的是，這個(gè)噪聲率只與增量數(shù)據(jù)集相關(guān)，而與標(biāo)記完全正確的原始數(shù)據(jù)無(wú)關(guān)。

2.2 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中，所有的原始數(shù)據(jù)標(biāo)簽均正確，增量數(shù)據(jù)的標(biāo)簽隨不同噪聲率而有所不同。值得注意的兩點(diǎn):一是隨著樣本數(shù)目的增多，分類器的識(shí)別率會(huì)提高;二是隨噪聲率的不斷增加，分類器識(shí)別率會(huì)降低。文中比較了以下方法:標(biāo)準(zhǔn)SVM，在其上訓(xùn)練的所有數(shù)據(jù)標(biāo)簽都是正確的，即沒有任何噪聲;增量數(shù)據(jù)分別含4種不同噪聲率時(shí)的標(biāo)準(zhǔn)SVM;第3種方法是對(duì)前者的稍加改進(jìn)，用原始數(shù)據(jù)來對(duì)增量數(shù)據(jù)賦一個(gè)置信度，根據(jù)置信度的高低來刪除一部分被判定為噪聲的數(shù)據(jù)，然后將刪除后的數(shù)據(jù)與原始數(shù)據(jù)混合進(jìn)行學(xué)習(xí)，分別嘗試了刪除10%～40%的數(shù)據(jù)后的學(xué)習(xí)方法。

圖4和圖5分別是原始數(shù)據(jù)識(shí)別率為67%時(shí)4種不同噪聲率時(shí)PubFig數(shù)據(jù)集上Bush圖像為正類的性能評(píng)估結(jié)果。以圖4為例，介紹評(píng)估結(jié)果:SVM是指標(biāo)號(hào)全部正確的SVM;noisy:10%withoutmissing是增量數(shù)據(jù)噪聲率為10%時(shí)的標(biāo)準(zhǔn)SVM;noisy:10%with 10%missing是去掉10%數(shù)據(jù)后的方法;noisy:10%with 20%missing－noisy:10%with 40%missing是相應(yīng)的去掉20%～40%數(shù)據(jù)后的改進(jìn)方法。從中可見，噪聲率較低時(shí)的SVM與標(biāo)簽全部正確時(shí)的標(biāo)準(zhǔn)SVM性能相當(dāng)，證明了SVM具有抗噪能力。但由圖4和圖5可見，隨噪聲率的不斷增加，這種抗噪能力越來越弱。對(duì)SVM進(jìn)行適當(dāng)?shù)母倪M(jìn)，即去掉一定比例的樣本后，分類性能有了明顯提高，比完全無(wú)噪聲的標(biāo)準(zhǔn)SVM高幾個(gè)百分點(diǎn)。

由上得出結(jié)論:在噪聲率低于一定水平時(shí)，噪聲對(duì)SVM沒有太大影響，充分證明了SVM具備抗噪能力;且對(duì)SVM進(jìn)行一定的改進(jìn)，刪除部分?jǐn)?shù)據(jù)后，性能有了明顯的提高，對(duì)噪聲的魯棒性也有所提高。

圖4 噪聲率為10%和20%時(shí)，去掉不同比率樣本的結(jié)果

圖5 噪聲率為30%和40%時(shí)，去掉不同比率樣本的結(jié)果

3 結(jié)束語(yǔ)

介紹了SVM并討論了其抗噪性能。通過調(diào)節(jié)正則化參數(shù)，SVM可在最大化間隔和經(jīng)驗(yàn)風(fēng)險(xiǎn)之間找到最佳值，在保證訓(xùn)練集錯(cuò)誤率低的情況下提升了泛化能力。實(shí)驗(yàn)結(jié)果表明:在增量數(shù)據(jù)中含有噪聲的情況下，SVM仍能夠有效利用增量數(shù)據(jù)來提高學(xué)習(xí)器的性能并具備一定的抗噪能力。

改進(jìn)的SVM方法失去了一定比例的訓(xùn)練樣本，提高了整個(gè)數(shù)據(jù)集的質(zhì)量，學(xué)習(xí)器的最終性能也可能有所改善。但如前面所述，這種方法性能好的前提是原始數(shù)據(jù)集的質(zhì)量要好，能否放寬對(duì)原始數(shù)據(jù)的限制，使分類器在不受約束的條件下改進(jìn)性能是進(jìn)一步研究的重點(diǎn)。

［1］鄧乃揚(yáng)，田英杰.支持向量機(jī) －理論、算法與拓展［M］.北京:科學(xué)出版社，2009.

［2］ZHU X，WU X，CHEN S.Eliminating class noise in large datasets［C］.Washington D.C:Proceedings of the 20th ICML International Conference on Machine Learning，2003:920 －927.

［3］NEERAJ K，ALEXANDER C B，PETER N B，et al.Describable visual attributes for face verification and image search［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(10):1962 －1977.

［4］THEODOROS E，MASSIMILIANO P，TOMASO P.Statistical learning theory ［J］.International Journal of Computer Vision，1998，38(1):9 －13.

［5］候雪梅.一種SVM多類分類算法用于抗噪語(yǔ)音識(shí)別［J］.西安郵電學(xué)院學(xué)報(bào)，2009，5(5):106 －108，141.

［6］呂卓，謝松云，趙金，等.基于SVM及其改進(jìn)算法的fMRI圖像分類性能研究［J］.電子設(shè)計(jì)工程，2011，19(16):30－33.