SVM中的線性分類器

線性分類器：

    首先給出一個非常非常簡單的分類問題（線性可分），我們要用一條直線，将下圖中黑色的點和白色的點分開，很顯然，圖上的這條直線就是我們要求的直線之一（可以有無數條這樣的直線）

    剛剛說了，我們令黑色白色兩類的點分别為+1, -1，是以當有一個新的點x需要預測屬于哪個分類的時候，我們用sgn(f(x))，就可以預測了，sgn表示符号函數，當f(x) > 0的時候，sgn(f(x)) = +1, 當f(x) < 0的時候sgn(f(x)) = –1。

    但是，我們怎樣才能取得一個最優的劃分直線f(x)呢？下圖的直線表示幾條可能的f(x)

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022055574369.png"></a>

    一個很直覺的感受是，讓這條直線到給定樣本中最近的點最遠，這句話讀起來比較拗口，下面給出幾個圖，來說明一下：

    第一種分法：

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022055573224.png"></a>

    第二種分法：

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022055585350.png"></a>

    這兩種分法哪種更好呢？從直覺上來說，就是分割的間隙越大越好，把兩個類别的點分得越開越好。就像我們平時判斷一個人是男還是女，就是很難出現分錯的情況，這就是男、女兩個類别之間的間隙非常的大導緻的，讓我們可以更準确的進行分類。在SVM中，稱為Maximum Marginal，是SVM的一個理論基礎之一。選擇使得間隙最大的函數作為分割平面是由很多道理的，比如說從機率的角度上來說，就是使得置信度最小的點置信度最大（聽起來很拗口），從實踐的角度來說，這樣的效果非常好，等等。這裡就不展開講，作為一個結論就ok了，:)

    上圖被紅色和藍色的線圈出來的點就是所謂的支援向量(support vector)。

    這裡直接給出M的式子：（從高中的解析幾何就可以很容易的得到了，也可以參考後面Moore的ppt）

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022056009056.png"></a>

    另外支援向量位于wx + b = 1與wx + b = -1的直線上，我們在前面乘上一個該點所屬的類别y（還記得嗎?y不是+1就是-1），就可以得到支援向量的表達式為：y(wx + b) = 1，這樣就可以更簡單的将支援向量表示出來了。

    當支援向量确定下來的時候，分割函數就确定下來了，兩個問題是等價的。得到支援向量，還有一個作用是，讓支援向量後方那些點就不用參與計算了。這點在後面将會更詳細的講講。

    在這個小節的最後，給出我們要優化求解的表達式：

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022056002611.png"></a>

    ||w||的意思是w的二範數，跟上面的M表達式的分母是一個意思，之前得到，M = 2 / ||w||，最大化這個式子等價于最小化||w||, 另外由于||w||是一個單調函數，我們可以對其加入平方，和前面的系數，熟悉的同學應該很容易就看出來了，這個式子是為了友善求導。

    這個式子有還有一些限制條件，完整的寫下來，應該是這樣的：（原問題）

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022056018433.png"></a>

    s.t的意思是subject to，也就是在後面這個限制條件下的意思，這個詞在svm的論文裡面非常容易見到。這個其實是一個帶限制的二次規劃(quadratic programming, QP)問題，是一個凸問題，凸問題就是指的不會有局部最優解，可以想象一個漏鬥，不管我們開始的時候将一個小球放在漏鬥的什麼位置，這個小球最終一定可以掉出漏鬥，也就是得到全局最優解。s.t.後面的限制條件可以看做是一個凸多面體，我們要做的就是在這個凸多面體中找到最優解。這些問題這裡不展開，因為展開的話，一本書也寫不完。如果有疑問請看看wikipedia。

二、轉化為對偶問題，并優化求解:

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022056015020.png"></a>

    首先讓L關于w，b最小化，分别令L關于w，b的偏導數為0，得到關于原問題的一個表達式

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022056032314.png"></a>

    将兩式帶回L(w,b,a)得到對偶問題的表達式

    新問題加上其限制條件是（對偶問題）:

<a href="http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201105/201105022056041691.png"></a>

    這個就是我們需要最終優化的式子。至此，得到了線性可分問題的優化式子。

摘自：http://www.cnblogs.com/LeftNotEasy/archive/2011/05/02/basic-of-svm.html

<b></b>

<b>本文轉自張昺華-sky部落格園部落格，原文連結：http://www.cnblogs.com/bonelee/p/7053108.html</b><b>，如需轉載請自行聯系原作者</b>