SVM及其魯棒性研究

吉衛衛，譚曉陽

(南京航空航天大學計算機科學與技術學院，江蘇 南京 210016)

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

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

1 SVM方法及其魯棒性

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

其Lagrange函數為

分別對W和ξ求導

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

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?樣本位于“管道壁”上，為支持向量。

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

討論“管道”的寬度對SVM的影響。直觀上講，當“管道”越寬時，進入其中的樣本數量越多，即支持向量個數越多。因為SVM服從聚類假設，當管道寬時，“管道壁”距離兩類中心的距離越近，支持向量的個數就可能越多，這些支持向量中噪聲的所占的比例就越低，即噪聲對W的方向起到的作用就越少，這是其有利的方面;不利的方面是支持向量多了，原本對分類無影響的非支持向量的個數就減少，尤其當噪聲數據由非支持向量變為支持向量時，可能減弱分類器的性能。

當“管道”越窄時，進入其中的樣本數量就越少。原本是噪聲的支持向量可能因“管道”變窄而成為非支持向量，對分類器不再產生影響，這是其有利方面;不利方面是“管道”越窄，距離兩類中心的距離越遠，樣本數量越少，支持向量的個數也會相應少，這時若支持向量中有噪聲，可能會大大影響W的方向，使分類器不再具有良好的判斷能力。

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

2 實驗結果

2.1 PubFig數據集

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

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

2.2 實驗結果

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

圖4和圖5分別是原始數據識別率為67%時4種不同噪聲率時PubFig數據集上Bush圖像為正類的性能評估結果。以圖4為例，介紹評估結果:SVM是指標號全部正確的SVM;noisy:10%withoutmissing是增量數據噪聲率為10%時的標準SVM;noisy:10%with 10%missing是去掉10%數據后的方法;noisy:10%with 20%missing－noisy:10%with 40%missing是相應的去掉20%～40%數據后的改進方法。從中可見，噪聲率較低時的SVM與標簽全部正確時的標準SVM性能相當，證明了SVM具有抗噪能力。但由圖4和圖5可見，隨噪聲率的不斷增加，這種抗噪能力越來越弱。對SVM進行適當的改進，即去掉一定比例的樣本后，分類性能有了明顯提高，比完全無噪聲的標準SVM高幾個百分點。

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

圖4 噪聲率為10%和20%時，去掉不同比率樣本的結果

圖5 噪聲率為30%和40%時，去掉不同比率樣本的結果

3 結束語

介紹了SVM并討論了其抗噪性能。通過調節正則化參數，SVM可在最大化間隔和經驗風險之間找到最佳值，在保證訓練集錯誤率低的情況下提升了泛化能力。實驗結果表明:在增量數據中含有噪聲的情況下，SVM仍能夠有效利用增量數據來提高學習器的性能并具備一定的抗噪能力。

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

［1］鄧乃揚，田英杰.支持向量機 －理論、算法與拓展［M］.北京:科學出版社，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多類分類算法用于抗噪語音識別［J］.西安郵電學院學報，2009，5(5):106 －108，141.

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