文章引自pluskid于2010年發(fā)表于“Machine Learning”板塊，本文僅做編輯。

1.回顧

在最開始討論支持向量機(jī)的時(shí)候，我們就假定，數(shù)據(jù)是線性可分的，亦即我們可以找到一個(gè)可行的超平面將數(shù)據(jù)完全分開。后來為了處理非線性數(shù)據(jù)，使用 Kernel 方法對(duì)原來的線性 SVM 進(jìn)行了推廣，使得非線性的的情況也能處理。雖然通過映射??(?)?將原始數(shù)據(jù)映射到高維空間之后，能夠線性分隔的概率大大增加，但是對(duì)于某些情況還是很難處理。例如可能并不是因?yàn)閿?shù)據(jù)本身是非線性結(jié)構(gòu)的，而只是因?yàn)閿?shù)據(jù)有噪音。對(duì)于這種偏離正常位置很遠(yuǎn)的數(shù)據(jù)點(diǎn)，我們稱之為 outlier ，在我們?cè)瓉淼?SVM 模型里，outlier 的存在有可能造成很大的影響，因?yàn)槌矫姹旧砭褪侵挥猩贁?shù)幾個(gè) support vector 組成的，如果這些 support vector 里又存在 outlier 的話，其影響就很大了。例如下圖：

用黑圈圈起來的那個(gè)藍(lán)點(diǎn)是一個(gè) outlier ，它偏離了自己原本所應(yīng)該在的那個(gè)半空間，如果直接忽略掉它的話，原來的分隔超平面還是挺好的，但是由于這個(gè) outlier 的出現(xiàn)，導(dǎo)致分隔超平面不得不被擠歪了，變成途中黑色虛線所示（這只是一個(gè)示意圖，并沒有嚴(yán)格計(jì)算精確坐標(biāo)），同時(shí) margin 也相應(yīng)變小了。當(dāng)然，更嚴(yán)重的情況是，如果這個(gè) outlier 再往右上移動(dòng)一些距離的話，我們將無法構(gòu)造出能將數(shù)據(jù)分開的超平面來。

2.松弛變量

為了處理這種情況，SVM 允許數(shù)據(jù)點(diǎn)在一定程度上偏離一下超平面。例如上圖中，黑色實(shí)線所對(duì)應(yīng)的距離，就是該 outlier 偏離的距離，如果把它移動(dòng)回來，就剛好落在原來的超平面上，而不會(huì)使得超平面發(fā)生變形了。具體來說，原來的約束條件

yi(wTxi+b)≥1,i=1,…,n

現(xiàn)在變成

yi(wTxi+b)≥1?ξi,i=1,…,n

其中?ξi≥0?稱為松弛變量 (slack variable) ，對(duì)應(yīng)數(shù)據(jù)點(diǎn)?xi?允許偏離的 functional margin 的量。當(dāng)然，如果我們運(yùn)行?ξi?任意大的話，那任意的超平面都是符合條件的了。所以，我們?cè)谠瓉淼哪繕?biāo)函數(shù)后面加上一項(xiàng)，使得這些?ξi?的總和也要最小：

min12∥w∥2+C∑i=1nξi

其中?C?是一個(gè)參數(shù)，用于控制目標(biāo)函數(shù)中兩項(xiàng)（“尋找 margin 最大的超平面”和“保證數(shù)據(jù)點(diǎn)偏差量最小”）之間的權(quán)重。注意，其中?ξ?是需要優(yōu)化的變量（之一），而?C?是一個(gè)事先確定好的常量。完整地寫出來是這個(gè)樣子：

mins.t.,12∥w∥2+C∑i=1nξiyi(wTxi+b)≥1?ξi,i=1,…,nξi≥0,i=1,…,n

用之前的方法將限制加入到目標(biāo)函數(shù)中，得到如下問題：

L(w,b,ξ,α,r)=12∥w∥2+C∑i=1nξi–∑i=1nαi(yi(wTxi+b)?1+ξi)–∑i=1nriξi

分析方法和前面一樣，轉(zhuǎn)換為另一個(gè)問題之后，我們先讓?L?針對(duì)?w、b?和?ξ?最小化：

?L?w=0?L?b=0?L?ξi=0?w=∑i=1nαiyixi?∑i=1nαiyi=0?C?αi?ri=0,i=1,…,n

將?w?帶回?L?并化簡(jiǎn)，得到和原來一樣的目標(biāo)函數(shù)：

maxα∑i=1nαi–12∑i,j=1nαiαjyiyj?xi,xj?

不過，由于我們得到?C?αi?ri=0?，而又有?ri≥0?（作為 Lagrange multiplier 的條件），因此有?αi≤C?，所以整個(gè) dual 問題現(xiàn)在寫作：

maxαs.t.,∑i=1nαi–12∑i,j=1nαiαjyiyj?xi,xj?0≤αi≤C,i=1,…,n∑i=1nαiyi=0

和之前的結(jié)果對(duì)比一下，可以看到唯一的區(qū)別就是現(xiàn)在 dual variable?α?多了一個(gè)上限?C?。而 Kernel 化的非線性形式也是一樣的，只要把??xi,xj??換成?κ(xi,xj)?即可。這樣一來，一個(gè)完整的，可以處理線性和非線性并能容忍噪音和 outliers 的支持向量機(jī)才終于介紹完畢了。?

總結(jié)

以上是生活随笔為你收集整理的SVM熟练到精通4：偏离点与松弛变量的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。