作者 | Ray
介紹
支持向量機(Support Vector Machine,以下簡稱SVM)，作為傳統機器學習的一個非常重要的分類算法，它是一種通用的前饋網絡類型，最早是由Vladimir N.Vapnik 和 Alexey Ya.Chervonenkis在1963年提出，目前的版本（soft margin）是Corinna Cortes 和 Vapnik在1993年提出，1995年發表。深度學習（2012）出現之前，如果不考慮集成學習的算法，不考慮特定的訓練數據集，在分類算法中的表現SVM說是排第一估計是沒有什麼異議的。
SVM本來是一種線性分類和非線性分類都支持的二元分類算法，但經過演變，現在也支持多分類問題，也能應用到了迴歸問題。本篇文章重點講解線性支持向量機的模型原理和目標函數優化原理。
目錄
- 感知機模型
- 理解線性支持向量機
一、感知機模型
在講解SVM模型之前，我們可以先簡單瞭解感知機模型的原理，因為這兩個模型有一些相同的地方。在二維平面中，感知機模型是去找到一條直線，儘可能地將兩個不同類別的樣本點分開。同理，在三維甚至更高維空間中，就是要去找到一個超平面。定義這個超平面為wTx+b=0（在二維平面中，就相當於直線w_1*x+w_1*y+b=0），而在超平面上方的點，定義為y=1，在超平面下方的點，定義為y=-1。而這樣的超平面可能是不唯一的，那麼感知機是怎麼定期最優超平面呢？從感知機模型的目標函數中，我們瞭解到它是希望讓所有誤分類的點(定義為M)到超平面的距離和最小。其目標函數如下：
(注：加入y_i是因為點若在超平面下，w*x_i+b為負數，需要乘上對應的y)
當w和b成比例增加了之後，比如都擴大N倍，會發現，分子和分母都會同時擴大N倍，這對目標函數並不影響。因此，當我們將W擴大或縮小一定倍數使得，||w||=1，分子也會相應的擴大或縮小，這樣，目標函數就能簡化成以下形式：
這個思想將會應用到支持向量機的目標函數優化上，後文將會詳細講解。
二、理解線性支持向量機
2.1 線性支持向量機思想
正如上文所說，線性支持向量機的思想跟感知機的思想很相似。其思想也是對給定的訓練樣本，找到一個超平面去儘可能的分隔更多正反例。不同的是其選擇最優的超平面是基於正反例離這個超平面儘可能遠。
線性支持向量機模型
從上圖可以發現，其實只要我們能保證距離超平面最近的那些點離超平面儘可能遠，就能保證所有的正反例離這個超平面儘可能的遠。因此，我們定義這些距離超平面最近的點為支持向量（如上圖中虛線所穿過的點）。並且定義正負支持向量的距離為Margin。
2.2 函數間隔和幾何間隔
對SVM思想有一定理解之後，設超平面為wTx+b=0。我們講解一下函數間隔和幾何間隔的區別。
給定一個樣本x，|wTx+b|表示點x到超平面的距離。通過觀察wTx+b和y是否同號，我們判斷分類是否正確。所以函數間隔定義γ’為：
而函數間隔不能正常反應點到超平面的距離，因為當我們等比例擴大w和b的時候，函數間隔也會擴大相應的倍數。因此，我們引入幾何間隔。
幾何間隔就是在函數間隔的基礎下，在分母上對w加上約束（這個約束有點像歸一化），定義為γ：
其實參考點到直線的距離，我們可以發現幾何間隔就是高維空間中點到超平面的距離，才能真正反映點到超平面的距離。
2.3 SVM目標函數及優化
根據SVM的思想，我們可以知道是要取最大化支持向量到超平面的幾何間隔，所以目標函數可以表示為：
在感知機模型最後，我們知道當同時擴大w和b，分子分母都會同樣擴大，對目標函數不影響，所以在這裡我們將分子(支持向量到超平面的函數間隔)擴大或壓縮等於1，則目標函數可以轉化為：
但是上式並不是凸函數，不好求解，再進一步轉化為：
上式就是一個凸函數，並且不等式約束為仿射函數，因此可以使用拉格朗日對偶去求解該問題。
根據拉格朗日乘子法，引入拉格朗日乘子α，且α≥0我們可以知道，先不考慮min，(2)問題等價於：
然後再考慮min，則有：
應用拉格朗日對偶性，通過求解對偶問題得到最優解，則對偶問題的目標函數為：
這就是線性可分條件下支持向量機的對偶算法。這樣做的優點在於：
- 一是原問題的對偶問題往往更容易求解
- 二者可以自然的引入核函數，進而推廣到非線性分類問題。
從(4)中，我們可以先求目標函數對於w和b的極小值，再求拉格朗日乘子α的極大值。
首先，分別對w和b分別求偏導數，並令為0：
將(5)和(6)代入(4)得到：
對(7)取反得到：
只要我們可以求出(8)中極小化的α向量，那麼我們就可以對應的得到w和b，而求解α需要使用SMO算法，由於該算法比較複雜，我們將在下一篇文章專門講解。假設我們現在已經使用SMO算法得到了最優的α值，記為α_ *
再求b：
對於任一樣本(x_s, y_s)有：
注意到任一樣本都有y_s^2=1，則將右式的1用y_s^2代：
將(9)代入上式，可以得到：
這樣，我們就能夠求解得到線性支持向量機的目標函數的各個參數，進而得到最優的超平面，將正負樣本分隔開。但是在上文中我們沒有講解求α向量的SMO算法，在下篇文章，將會詳細講解SMO算法，歡迎繼續關注。
對深度學習感興趣，熱愛Tensorflow的小夥伴，歡迎關注我們的網站！http://www.panchuang.net 我們的公眾號：磐創AI。
閱讀更多 人工智能遇見磐創 的文章
