我所理解的 SVM（支持向量機）- 1

01-26

眾所周知 SVM 是非常強大的一種分類演算法，有著媲美神經網路的分類效果，實現過程卻簡單得多。受限於我的能力，這篇文章不會系統地介紹 SVM（因為我並不是線性代數、凸優化等方面的專家），而是以一個學習者的角度描述 SVM 產生的過程，由於內容較長，計劃分成三到四篇。

1. 一個好的分類是怎麼樣的

圖中的兩組數據，顯然它們是線性可分（linear separable）的，圖裡給出的三條分界線都可以準確區分這兩類數據，它們是不是一樣好？如果不是，哪一條看起來更加合適？

直覺告訴我們是 a。相比之下，b 和 c 離個別點太近了，我們很難拍著胸脯說「這個點在分界線下面，所以絕對是 X"，因為分界線稍微挪一挪就可以改變這些點的屬性，我們想要的是一個相對自信的分界線，使靠近分界線的點與分界線的距離足夠大，上圖中的分界線 a 就符合我們的需求。

接下來我們畫出 a 的兩條平行線，距離分界線 a 最近的點（兩種點都有）會落在這兩條平行線上，而我們的分界線 $l$ 就在 $a_1$ 和 $a_2$ 中間，這三條線看起來就像一條公路，這條路把不同的點分隔在路的兩旁， $a_1$ 和 $a_2$ 之間的距離就是路寬，分類的過程就好比在這塊地上修一條公路把不同類型的點分開，並且這條路越寬越好， SVM 要做的就是建好這條最寬的路。

ps. 這裡所說的分界線嚴格來說是 decision boundary，decision boundary 在二維空間是一條線，在三維空間是一個平面，更高維的空間里稱作超平面，為了方便本文都用分界線來代表 decision boundary。

2. 進入向量的世界

你或許已經注意到 SVM 的全稱是 Support Vector Machine（支持向量機），在推導 SVM 公式過程中，我們幾乎都是在和向量打交道。剛接觸 SVM 的時候我對這個名字非常詫異，SVM 很強是沒錯，但是名字也太「隨意」了吧？希望寫完這篇文章以後我能理解為什麼這種演算法叫做支持向量機。

如果你之前沒有接觸過向量，建議花一個小時左右的時間熟悉一下向量的概念和基本性質。我們先把空間上的點用向量來表示（以原點為起點的向量）：

$vec{x^{(i)}}in mathbb{R}^n, i=1,2...m$

$m$ 表示點的數量， $mathbb{R}^n$ 表示的是 $n$ 維空間，分界線可以用下式來表示： $vec{w^T} cdot {overrightarrow{x}}+b=0$

出於美觀和方便的考慮，我傾向於去掉箭頭符號，在心裡記住 $w,x$ 都是向量， $b$ 是常數：

$w^T cdot x+b=0$

雖然寫成了向量的形式，其實並沒有什麼大不了的，我們可以把它和初中時候學過的直線表達式聯繫起來：

$egin{split}w^T cdot x+b&=0\egin{bmatrix}w_1 & w_2end{bmatrix}cdotegin{bmatrix}x_1\x_2end{bmatrix}+b&=0\w_1x_1+w_2x_2+b&=0\x_2=-frac{w_1}{w_2}x_1&-bquaddots quad (w_2 eq0)end{split}$

顯然向量的形式更加簡潔，特別是在高維空間的情況下，還有一個好處就是，矢量的形式下 $w$ 剛好與分界線垂直，這個性質會在後面用到。 $w^T cdot x+b=0$ 表示的是分界線上所有的點，當 $w^T cdot x+b>0$ 時，表示的是分界線上方的區域，反之則是分界線下方的區域：

對於 SVM 來說僅僅這樣是不夠的，還記得嗎我們要修一條路出來，我們得確保在一條足夠寬的路裡面沒有數據點：

我又把路畫上去了，因為兩條排水渠（暫且把路的兩邊叫做排水渠吧）與分界線等距，就相當於在分界線的表達式里加上/減去同樣的截距 $delta$ ，實際上引入新的變數 $delta$ 是沒有必要的，因為 $bpmdelta$ 也僅僅表示截距而已，不妨把 $delta$ 換成1（換成2,3,4...都可以，換成1更方便，僅此而已），現在我們有了新的判別條件：

$egin{cases}w^T cdot x+bleqslant1quaddotsigcirc \ w^T cdot x+bgeqslant-1 dots imesend{cases}$

數學總是追求簡潔的形式，在這裡引入 $y^{(i)}$ ，表示的是對象的屬性：

$egin{equation}y^{(i)}=egin{cases} 1,quad x^{(i)}=igcirc\-1,quad x^{(i)}= imes end{cases}end{equation}$

這樣前面的式子就可以寫成更為簡潔的形式：

$y^{(i)}(w^T cdot x^{(i)}+b)geqslant1$

ps. 要證明 $w$ 與分界線垂直，只需要將 $w$ 與分界線的方向向量相乘即可：

$egin{split}vec{w}cdotvec{k}&=w^Tcdot k\&=egin{bmatrix}w_1 & w_2end{bmatrix}cdotegin{bmatrix}1\-frac{w_1}{w_2}end{bmatrix}\&=w_1-w_1\&=0\end{split}$

3. 什麼是支持向量

通過上面一節，我們得到了一個限制條件： $y^{(i)}(w^T cdot x^{(i)}+b)geqslant1$ ，這是我們修路時要遵循的原則，以此為依據修一條儘可能寬的路！那麼路寬該怎麼表示？

在兩條排水渠上各取一點 $(x_-, x_+)$ 連接成向量 $overrightarrow{x_-x_+}$ ，根據向量的知識求得路寬並不難，只需將 $overrightarrow{x_-x_+}$ 投影到分界線的單位法向量即可，在第二節里我們已經知道 $w$ 與分界線垂直，容易得到：

$egin{split}width &=overrightarrow{x_-x_+}cdot frac{vec{w}}{||vec{w}||}\&=frac{1}{||vec{w}||}[w^Tcdot(x_+-x_-)]\&=frac{1}{||vec{w}||}[w^Tcdot x_+-w^Tcdot x_-]\&=frac{1}{||vec{w}||}[1-b-(-1-b)]\&=frac{2}{||vec{w}||}end{split}$

我們發現路寬的表達式僅與 $||w||$ （ $w$ 的長度）有關，要讓修的路最寬，意味著 $||w||$ 要最小，即 $frac{1}{2}||w||^2$ 最小（為了後續公式推導方便），讓我們明確一下新的目標：

在限制條件 $y^{(i)}(w^T cdot x^{(i)}+b)geqslant1$ 下，找到合適的參數 $(w, b)$ 使 $frac{1}{2}||w||^2$ 最小

這是一個基於 KKT 條件的二次規劃問題，優化原理的內容超出了這篇文章的範疇，如果有興趣可以點擊這個鏈接：拉格朗日乘子法和KKT條件。在這裡我們只要知道拉格朗日乘數法可以求得這個最優解，引入新的係數 $alpha _i$ :

$egin{equation}alpha_{i}=egin{cases} 0,quadquadquad quad y^{(i)}(w^T cdot x^{(i)}+b)>1\geqslant0, quadquad quad y^{(i)}(w^T cdot x^{(i)}+b)=1end{cases}end{equation}$

這樣問題轉化成選取合適的參數 $alpha$ 最小化 $mathcal{L}$ :

$min mathcal{L}=frac{1}{2}||w||^2-sum_{k=1}^malpha_i[y^{(i)}(w^T cdot x^{(i)}+b)-1]\sum_{k=1}^malpha_i[y^{(i)}(w^T cdot x^{(i)}+b)-1]=0$

即使你完全不知道凸優化和拉格朗日乘數法也沒有關係，你可以試著這麼理解， $mathcal{L}$ 和原來的目標是一致的，因為 $sum=0$ ，同時我們又把限制條件加入到了表達式當中，接下來分別對 $w$ 和 $b$ 求偏導數：

$egin{split}frac{partial mathcal{L}}{partial b} &= -sum_{k=1}^malpha_iy^{(i)}\frac{partial mathcal{L}}{partial w} &=w -sum_{k=1}^malpha_iy^{(i)}x^{(i)}\end{split}$

令以上兩式為0，我們可以得到：

$egin{split}sum_{k=1}^malpha_iy^{(i)}=0\w =sum_{k=1}^malpha_iy^{(i)}x^{(i)}\end{split}$

因為 $alpha _i$ 只有當 $y^{(i)}(w^T cdot x^{(i)}+b)=1$ 時（位於排水渠上的點）才能取到非零的值，所以 $w$ 只依賴於邊界上的矢量，換句話說，正是位於邊界上的這些向量支撐起了分界線（超平面），所以這些向量被叫做支持向量，這也是支持向量機名字的由來。

戳右邊了解更多 ?? 我所理解的 SVM（支持向量機）