機器學習_學習筆記系列(15)：支撐向量機(Support Vector Machine)
在前幾個章節中，我們主要介紹的都是簡單的回歸方法，而我們今天要來介紹另外一個機器學習架構：支撐向量機，Support Vector Machine (SVM)
Support Vector Machine
對於支撐向量機，我們通常可以把他用在分類問題上，而其實這個方法也可以用在解決回歸問題，叫做(Support Vector Regression)。而我們今天要來探討的是支撐向量機在分類問題上。
在介紹支撐向量機前，我們回顧一下之前的感知器(perceptron)，我們的演算法
是在所有的點裡面隨機找一個點，如果這個點沒有分類錯誤，就繼續找下一個點，如果有的話，我們就以這個分類錯誤的點來更新我們的感知器的權重。
而在支撐向量機裡面，我們可以把他粗淺說，我們要最大化，兩個類別之間的距離
最後上面那張圖片的虛線，在我們分類問題上，是我們最想找到的一條線，而我們知道這條線滿足
所以我們今天假設在這條線上有兩個點分別為x’和x’’，其滿足
所以
現在我們想要做的就是最大化實線到虛線的距離。我們知道我們的權重向量w垂直於我們的分類線向量。所以若實線上有個點x其到虛線的距離為
而在感知器的章節中我們知道
這個式子的意思就是，如果我們類別標記為1，則其滿足wx+b>0，所以相乘一定會大於0，若我們標記資料為-1，則滿足wx+b<0，所以相乘也一定大於0。所以我們可以把我們的式子改寫成
而我們知道對於分割線同乘一個常數a
其一樣會等於0，所以為了方便計算，我們設定
所以
也就是我們現在的問題變成
所以我們現在可以反過來把我們的問題改寫成(這裡我們去調根號，並乘上1/2)
而在這裡對於離虛線最近的數據點(在實線上)，我們就叫做Support Vector且滿足
所以對於任意一個點滿足
總結一下我們支撐向量機的分類問題可以寫成
而這個式子就和二次規劃(Quadratic programming)的最佳化問題非常類似
對於Quadratic programming(QP)其為
所以把SVM的問題放到QP裡面，假設我們的輸入資料有N筆，每筆資料中有M個特徵，則
對於x就是我們想要知道的權重矩陣其長度為1+M。而Q為一個大小為1+M乘1+M的矩陣，其斜對角除了第一個元素，其他都為1。在G矩陣中則是我們標記資料y和輸入資料x的乘積，右下標代表資料序號，右上標代表特徵序號，而b為一個長度為N的矩陣，裡面的每個元素都為1。
如此一來我們就可以套入二次規劃
求解出我們的權重w值。
在這邊我們就不講解QP詳細求解的過程，有興趣的人可以去看凸優化(Convex Optimization)裡面有關於二次規劃(QP)的章節。
而對於SVM最大畫Margin的方法，我們可以拿來跟Regularization來比較。在Regularization當中，我們希望在w.T*w<C的條件下最小化E_in，而SVM做的事情是在y(w.T*x+b)>=1的條件下最小化w.T*w，其方法即保證了E_in=0。把他近一步畫成表格，可以寫成
從另一個芳來看，我們也可以發現對於SVM其可以shatter的點，會比Perceptron還要少，我們可以用下圖簡單的例子給大家看
因為Perceptron為單單一條分割線，所以對於3個點的分類問題是可以被shatter的，但是我們可以看到在SVM下，相同寬度的margin在，也就是我們的虛線部分，有些情況是無法分類的。
所以也就是說SVM相對於Perceptron其可以shatter的點變少，也就是其VC dimension變少，降低的模型的複雜度，讓我們的模型有更好的泛化能力。
Python Sample Code:
Github:
Reference:
[1] Coursera, 機器學習技法, 林軒田 教授
