機器學習技法筆記1：線性支持向量機（SVM）

02-28

題目：如下三條直線中，哪一條看似最好：

大家肯定是選第三個，為什麼呢？

一般情況下，訓練樣本外的測量數據應該分布在訓練樣本附近，但與訓練樣本的位置有一些偏差。若要保證對未知的測量數據也能進行正確分類，最好讓分類直線距離正類負類的點都有一定的距離。這樣能讓每個樣本點附近的圓形區域是「安全」的。圓形區域越大，表示分類直線對測量數據誤差的容忍性越高，也就越安全。

如上圖所示，左邊的點距離分類直線的最小距離很小，它的圓形區域很小。那麼，這種情況下，分類線對測量數據誤差的容忍性就很差，測量數據與樣本數據稍有偏差，很有可能就被誤分。而右邊的點距離分類直線的最小距離更大一些，其圓形區域也比較大。這種情況下，分類線對測量數據誤差的容忍性就相對來說大很多，不容易誤分。也就是說，左邊分類線和右邊分類線的最大區別是對這類測量誤差的容忍度不同。

我們把對圓形區域轉換成對分割線的「胖瘦」：

定義分類線有多胖，就是看距離分類線最近的點與分類線的距離，我們把它用margin（邊界）表示。分類線由權重w決定，我們的目標就是找到使margin最大時對應的w值。

計算最大邊界

首先，我們將之前表示的權重向量w(w0,w1,?,wd)中的w0拿出來，用b表示。同時省去x0項。這樣，假設函數就變成了h(x)=sign(wx+b)。

如上圖所示，平面上有兩個點：x和x。因為這兩個點都在分類平面上，所以它們都滿足： $w^Tx+b=0\ w^Tx+b=0\ Rightarrow w^T(x′′?x′)=w^Tx′′?w^Tx′=?b?(?b)=0$

(x-x)是平面上的任一向量，(x-x)與w內積為0，表示(x-x)垂直於w，那麼w就是平面的法向量。

現在，若要計算平面外一點x到該平面的距離，做法是只要將向量(x-x)投影到垂直於該平面的方向（即w方向）上就可以了。那麼，令(x-x)與w的夾角為 $heta$ ，距離就可以表示為：

因為分割線將所有點分類正確，則對於每個點(xn,yn)有 $y_n(w^Tx_n+b)>0$ ，則我們可以改寫上式，去掉絕對值符號：

那我們的目標就可以改寫為：

我們還可以再次簡化：因為w和b同時縮放所代表的那個平面（超平面）不變，所以我們縮放w和b，使得距離面最近的那個點滿足 $y_n(w^Tx_n+b)=1$ ，目標就可以簡化為（同時可以去掉一個大於0的限制）：

爆炸性的又來了！我們假設一種有限制條件的問題求解，現在為了方便求解我們將該限制放寬，雖然看上去得出的解可能不對，但是如果能證明放寬後得出解仍然在原限制條件內，或者能證明解若在限制條件外則目標(max)又不正確，那麼該限制條件的放寬也就沒有影響。（有點拗口，但其實不難理解）仔細看下圖：

所以，目標又可以簡化為：

但是，你以為這就足夠簡化了嗎，當然不是！我們運用幾個小方法可以將目標再次簡化：

max => min， $frac{1}{|w|}Rightarrow |w|$
$|w|Rightarrow |w|^2=w^Tw$
再乘1/2（為了方便求解）

所以，我們得出一個最終簡化的目標（我們用了十幾分鐘講解，先驅們其實用了幾年）：

手撕SVM

首先，假設平面上有如下四個點：

四個點坐標為：

設w向量為 $(w_i,w_2)^T$ ，將不同的坐標點代入限制條件得：

為什麼叫支撐向量機Support Vector Machine(SVM)呢？如下圖：

這是因為分類面僅僅由分類面的兩邊距離它最近的幾個點決定的，其它點對分類面沒有影響。決定分類面的幾個點稱之為支持向量（Support Vector），好比這些點「支撐」著分類面。而利用Support Vector得到最佳分類面的方法，稱之為支持向量機（Support Vector Machine）。

一般化求解svm

這是一個典型的二次規劃問題，即Quadratic Programming（QP）。因為SVM的目標是關於w的二次函數，條件是關於w和b的一次函數，所以，它的求解過程還是比較容易的，可以使用一些軟體（例如Matlab）自帶的二次規劃的庫函數來求解。下圖給出SVM與標準二次規劃問題的參數對應關係：

對於我這種線代忘記10年的渣渣來說就必須得繼續手撕才能看明白： $b=k quad overrightarrow {w}=egin{pmatrix} 1 \ 2 \ 3 end{pmatrix}quad overrightarrow {u}=egin{pmatrix} k \ 1 \ 2 \ 3 end{pmatrix}\ Q=egin{bmatrix} 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 end{bmatrix}=egin{bmatrix} 0 & 0^{T}_{d} \ 0_{d} & I_d end{bmatrix}\ u^{T}Qu=egin{bmatrix} k & 1 & 2 & 3 end{bmatrix} Qegin{pmatrix} k \ 1 \ 2 \ 3 end{pmatrix}\ =egin{bmatrix} 0 & 1 & 2 & 3 end{bmatrix}egin{pmatrix} k \ 1 \ 2 \ 3 end{pmatrix}\Leftrightarrowegin{bmatrix} 1 & 2 & 3 end{bmatrix} egin{pmatrix} 1 \ 2 \ 3 end{pmatrix}=w^{T}w$

總結一般化求解思路

計算對應的二次規劃參數Q，p，A，c
根據二次規劃庫函數，計算b，w
將b和w代入 $g_{SVM}$ ，得到最佳分類面

這種方法稱為Linear Hard-Margin SVM Algorithm。 Hard-Margin表示訓練集不能有錯誤，不同類的點一定是分開的；如果是非線性的，例如包含x的高階項，那麼可以使用我們之前在《機器學習基石》課程中介紹的特徵轉換的方法。

*二次規劃

#todo

參考：支持向量機通俗導論（理解SVM的三層境界） - 結構之法演算法之道 - CSDN博客

題圖：xxxx 2017年11月9日00:01:38