機器學習技法是機器學習基石的提升，在此系列中我們将讨論各類機器學習典型算法，包括支援向量機、決策樹、随機森林、GBDT等等。
歡迎大家點贊、分享我的文章，關注我的微信公衆号。你們的支援就是我創作的動力！
還等什麼？開始吧～
1Large-Margin Separating Hyperplane
回顧一下我們之前介紹了線性分類（linear classification），對于線性可分的情況，我們可以使用PLA/pocket算法在平面或者超平面上把正負類分開。
例如對平面2D這種情況，我們可以找到一條直線，能将正類和負類完全分開。但是，這樣的直線通常不止一條，如下圖所示。那麼，下圖中的三條分類線都能将資料分開，但是哪條線更好呢？
這三條直線都是由PLA/pocket算法不斷修正錯誤點而最終産生的，整個确定直線形狀的過程是随機的。單從分類效果上看，這三條直線都滿足要求，而且都滿足VC bound要求，模型複雜度Ω(H)是一樣的，即具有一定的泛化能力。但是，如果要選擇的話，憑第一感覺，我們還是會選擇第三條直線，感覺它的分類效果更好一些。那這又是為什麼呢？
先給個簡單解釋，一般情況下，訓練樣本外的測量資料應該分布在訓練樣本附近，但與訓練樣本的位置有一些偏差。若要保證對未知的測量資料也能進行正确分類，最好讓分類直線距離正類負類的點都有一定的距離。這樣能讓每個樣本點附近的圓形區域是“安全”的。圓形區域越大，表示分類直線對測量資料誤差的容忍性越高，越“安全”。
如上圖所示，左邊的點距離分類直線的最小距離很小，它的圓形區域很小。那麼，這種情況下，分類線對測量資料誤差的容忍性就很差，測量資料與樣本資料稍有偏差，很有可能就被誤分。而右邊的點距離分類直線的最小距離更大一些，其圓形區域也比較大。這種情況下，分類線對測量資料誤差的容忍性就相對來說大很多，不容易誤分。也就是說，左邊分類線和右邊分類線的最大差別是對這類測量誤差的容忍度不同。
那麼，如果每一筆訓練資料距離分類線越遠的話，就表示分類型可以忍受更多的測量誤差（noise）。我們之前在《機器學習基石》中介紹過，noise是造成過拟合（overfitting）的主要原因，而測量誤差也是一種noise。是以，如果分類線對測量誤差的容忍性越好的話，表示這是一條不錯的分類線。那麼，我們的目标就是找到這樣一條最“健壯”的線，即距離資料點越遠越好。
上面我們用圓形區域表示分類線能夠容忍多少誤差，也就相當于計算點到直線的距離。距離越大，表示直線越“胖”，越能容忍誤差；距離越小，表示直線越“瘦”，越不能容忍誤差。越胖越好（像楊貴妃那樣的哦~）。
如何定義分類線有多胖，就是看距離分類線最近的點與分類線的距離，我們把它用margin表示。分類線由權重w決定，目的就是找到使margin最大時對應的w值。整體來說，我們的目标就是找到這樣的分類線并滿足下列條件：
2Standard Large-Margin Problem
要讓margin最大，即讓離分類線最近的點到分類線距離最大，我們先來看一下如何計算點到分類線的距離。
(x”-x’)是平面上的任一向量，(x”-x’)與w内積為0，表示(x”-x’)垂直于w，那麼w就是平面的法向量。
現在，若要計算平面外一點x到該平面的距離，做法是隻要将向量(x-x’)投影到垂直于該平面的方向（即w方向）上就可以了。那麼，令(x”-x’)與w的夾角為θ，距離就可以表示為：
那麼，我們的目标形式就轉換為：
這樣，目标形式就簡化為：
3Support Vector Machine
現在，條件和目标變成：
Support Vector Machine(SVM)這個名字從何而來？為什麼把這種分類面解法稱為支援向量機呢？這是因為分類面僅僅由分類面的兩邊距離它最近的幾個點決定的，其它點對分類面沒有影響。決定分類面的幾個點稱之為支援向量（Support Vector），好比這些點“支撐”着分類面。而利用Support Vector得到最佳分類面的方法，稱之為支援向量機（Support Vector Machine）。
這種方法稱為Linear Hard-Margin SVM Algorithm。如果是非線性的，例如包含x的高階項，那麼可以使用我們之前在《機器學習基石》課程中介紹的特征轉換的方法，先作zn=Φ(xn)的特征變換，從非線性的x域映射到線性的z域空間，再利用Linear Hard-Margin SVM Algorithm求解即可。
下面介紹SVM的一般求解方法。先寫下我們的條件和目标：
這是一個典型的二次規劃問題，即Quadratic Programming（QP）。因為SVM的目标是關于w的二次函數，條件是關于w和b的一次函數，是以，它的求解過程還是比較容易的，可以使用一些軟體（例如Matlab）自帶的二次規劃的庫函數來求解。下圖給出SVM與标準二次規劃問題的參數對應關系：
那麼，線性SVM算法可以總結為三步：
- 計算對應的二次規劃參數Q，p，A，c
- 根據二次規劃庫函數，計算b，w
- 将b和w代入gSVMgSVM，得到最佳分類面
4Reasons behind Large-Margin Hyperplane
從另一方面來看，Large-Margin會限制Dichotomies的個數。這從視覺上也很好了解，假如一條分類面越“胖”，即對應Large-Margin，那麼它可能shtter的點的個數就可能越少：
之前的《機器學習基石》課程中介紹過，Dichotomies與VC Dimension是緊密聯系的。也就是說如果Dichotomies越少，那麼複雜度就越低，即有效的VC Dimension就越小，得到Eout≈Ein，泛化能力強。
5總結
本節課主要介紹了線性支援向量機（Linear Support Vector Machine）。我們先從視覺角度出發，希望得到一個比較“胖”的分類面，即滿足所有的點距離分類面都盡可能遠。然後，我們通過一步步推導和簡化，最終把這個問題轉換為标準的二次規劃（QP）問題。二次規劃問題可以使用Matlab等軟體來進行求解，得到我們要求的w和b，确定分類面。這種方法背後的原理其實就是減少了dichotomies的種類，減少了有效的VC Dimension數量，進而讓機器學習的模型具有更好的泛化能力。