支持向量機(Support Vector Machine, SVM)(一) Hard-margin

SVM是眾多監督式學習方法中十分出色的一種，基本原理就是找到一個分界線，能將數據進行有效的分類，同時保證分界線兩邊的樣本儘可能遠的距離這個分界線。
而SVM又有兩種不同的算法，分別是hard-margin、soft-margin

Hard-margin

首先我們要先定義一個判別條件:

前面有提到我們希望margin盡可能的寬，而這個"寬"的計算方式如下:

最大化上方這個式子，又可以看成

所以我們可以得到hard-margin SVM就是要在限制条件下，找到合適的參數(w,b)使得上面這個式子最小。

這是一個基於KKT條件的二次規劃問題，在這裡我們需要引入拉格朗日乘數(lagrange multiplier)來求得這個最佳解

所以我們所要求的是

整理過後

上方這個式子是一個二次規劃的問題，可以透過smo演算法得到每一個 λ 的值。
根據KKT條件

λ非零向量我們稱為support vector（支撐向量），我們預測的時候只會用到這些點，剩下的全部不會用到。而又因為support vector的 λ 大於零，因此上方條件中紅框的部分必定等於零，我們就可以以此去算出 b 出來。

接著我們的分類邊界就求出來了(其正負值對應二元分類)

最後整理一下hard-margin SVM的流程:

• 先把L(w,b,λ)對 w 與 b 偏微分，並且令其為零，然後代回L(w,b,λ)，可以順便求出w*
• 以smo算出 λ ，便可得到 support vector
• 利用support vector，並根據KKT條件來計算 b*
• 得到我們的分類邊界