ML學習心得（4）----SVM支援向量機 之一

0、前言

網上有好多大神關于SVM的部落格，在Reference中都有提及。而Andrew Ng從另外的角度引出了SVM，簡單的

闡述了SVM的工作原理，具體的可以看看他的公開課。我這裡打算1、介紹SVM和其dual優化；2、SVM和核函數以及

其松弛變量處理outliers；3、SMO算法。感覺工作量有些大，不知道自己能不能很清楚的理清自己的思路。

1、什麼是Support Vector Machine(SVM)

SVM一直被認為是效果最好的現成可用的分類算法之一。這裡"現成可用"幾個字說的，其實是SVM在理論領域和實際應用

領域有很好效果，兩邊都混得開。那麼到底什麼是SVM呢？作為分類算法，我們當然要從線性分類器開始說起。

假設x是一個n維的資料，對應的類别y取值為{-1,1}，我們希望有一個超平面，能夠把不同類别的點全部都分割

開來，令

,當f（x）=0的時候即為其分割超平面，當f(x)<0，y=-1，f(x)>0 y=1。然而，從數值的

角度上看，當f(x)值很小的時候，因為誤差的存在，我們很難確定自己準确判斷它所屬的類别。那麼很自然，我們希望

我們分類所依憑的f(x)的值能夠足夠大，大到我們很準确的進行分類；從幾何的角度看，離超平面越近的點，我們越難

進行分類，反之 則相反。

我們定義function margin 為

（這裡就展現出來我們y取+-1的好處了，可以保證距離是正的）

對于geometrical margin，我們可以從下面的圖來看看

w是超平面的法向量，這點大家以前的知識應該就能了解，我們要求x點到超平面的距離：

而f(x0)=0,是以等式兩邊乘以w加b，可得：

,為了保證他是正的乘以y，可得geometrical margin為

兩者差了||w||的倍數。

像上面提到的那樣，我們希望我們的margin最大，那麼我們的分類就更加準确，顯然我們要找到的超平面

是最大化geometrical margin，因為function margin可以在超平面位置不變的情況下（同倍增大縮小w和b），導緻

值不能确定，而幾何距離就沒這個問題。是以我們的svm就可以定義為：

固定function margin為1，那麼我們的優化方程可以改為：

s.t.不變

至此，我們就初步的了解了什麼是SVM，就是使得margin最大，使得我們分類的confidence最大，大家可以很明顯

地看到，confidence的确定是依賴于幾個f(x)絕對值等于1的點。下面我們就看看，怎麼利用凸優化的知識求解這個問題。

2、SVM的求解——拉格朗日對偶問題

上面的等價的優化方程的拉格朗日函數為

于是我們現在的目标函數變為：

調換min和max可以得到

我們可以得知d一定永遠小于等于p，我們就可以利用其KKT條件求解。

KKT：

1、

2、

3、

為了求其極小值，我們求偏導可得

帶入拉格朗日函數可以得到我們的對偶優化方程

上面整個的推導過程最好能自己去推導一下，便于加深記憶。

得到上面的式子，我們就有很好的方法SMO來求解，整個方法我們在後續的文章中會提及。

另外，我們來看看上述優化方程的某些特性吧。進而引出下篇文章核函數的内容

上面我們得到了w的表達式，帶入拉格朗日函數，可以得到：

其中<x,y>表示内積。

讓我們關注下alpha，從拉格朗日函數中，當我們的xi在邊界上時，

是為0的

也就是我們的support vector，那麼不在邊界上的點，其值是大于0的，而alpha有事大于等于0的，我們的拉格朗日函數

要使其最大化，若alpha不為0，那麼其值就是正無窮的。是以不在邊界上的點起alph的值時等于0的。也就是說我們的SVM

的邊界其實就是幾個support vector 所決定的

截止目前，我們的SVM隻能針對線性分類。而基于上面内積的特點，我們下一章就會介紹到

核函數，進而使得我們的SVM更加強大。

3、Reference

Free Mind支援向量機系列

JerryLead支援向量機系列