# 1 -- Linear Support Vector Machine
關于臺灣大學林軒田老師的《機器學習基石》課程，我們已經總結了16節課的筆記。這里附上基石第一節課的博客地址：
[臺灣大學林軒田機器學習基石課程學習筆記1 – The Learning Problem](http://blog.csdn.net/red_stone1/article/details/72899485)
本系列同樣分成16節課，將會介紹《機器學習基石》的進階版《機器學習技法》，更深入地探討機器學習一些高級算法和技巧。
### **Large-Margin Separating Hyperplane**
回顧一下我們之前介紹了linear classification，對于線性可分的情況，我們可以使用PLA/pocket算法在平面或者超平面上把正負類分開。
例如對平面2D這種情況，我們可以找到一條直線，能將正類和負類完全分開。但是，這樣的直線通常不止一條，如下圖所示。那么，下圖中的三條分類線都能將數據分開，但是哪條線更好呢？
這三條直線都是由PLA/pocket算法不斷修正錯誤點而最終產生的，整個確定直線形狀的過程是隨機的。單從分類效果上看，這三條直線都滿足要求，而且都滿足VC bound要求，模型復雜度是一樣的，即具有一定的泛化能力。但是，如果要選擇的話，憑第一感覺，我們還是會選擇第三條直線，感覺它的分類效果更好一些。那這又是為什么呢？
先給個簡單解釋，一般情況下，訓練樣本外的測量數據應該分布在訓練樣本附近，但與訓練樣本的位置有一些偏差。若要保證對未知的測量數據也能進行正確分類，最好讓分類直線距離正類負類的點都有一定的距離。這樣能讓每個樣本點附近的圓形區域是“安全”的。圓形區域越大，表示分類直線對測量數據誤差的容忍性越高，越“安全”。
如上圖所示，左邊的點距離分類直線的最小距離很小，它的圓形區域很小。那么，這種情況下，分類線對測量數據誤差的容忍性就很差，測量數據與樣本數據稍有偏差，很有可能就被誤分。而右邊的點距離分類直線的最小距離更大一些，其圓形區域也比較大。這種情況下，分類線對測量數據誤差的容忍性就相對來說大很多，不容易誤分。也就是說，左邊分類線和右邊分類線的最大區別是對這類測量誤差的容忍度不同。
那么，如果每一筆訓練資料距離分類線越遠的話，就表示分類型可以忍受更多的測量誤差（noise）。我們之前在《機器學習基石》中介紹過，noise是造成overfitting的主要原因，而測量誤差也是一種noise。所以，如果分類線對測量誤差的容忍性越好的話，表示這是一條不錯的分類線。那么，我們的目標就是找到這樣一條最“健壯”的線，即距離數據點越遠越好。
上面我們用圓形區域表示分類線能夠容忍多少誤差，也就相當于計算點到直線的距離。距離越大，表示直線越“胖”，越能容忍誤差；距離越小，表示直線越“瘦”，越不能容忍誤差。越胖越好（像楊貴妃那樣的哦~）。
如何定義分類線有多胖，就是看距離分類線最近的點與分類線的距離，我們把它用margin表示。分類線由權重w決定，目的就是找到使margin最大時對應的w值。整體來說，我們的目標就是找到這樣的分類線并滿足下列條件：
* **分類正確，即**
* **margin最大化**
### **Standard Large-Margin Problem**
要讓margin最大，即讓離分類線最近的點到分類線距離最大，我們先來看一下如何計算點到分類線的距離。
首先，我們將權重中的拿出來，用b表示。同時省去項。這樣，hypothesis就變成了。
下面，利用圖解的方式，詳細推導如何計算點到分類平面的距離：
如上圖所示，平面上有兩個點：x’和x”。因為這兩個點都在分類平面上，所以它們都滿足：
同時可以得到：，，則有：
(x”-x’)是平面上的任一向量，(x”-x’)與w內積為0，表示(x”-x’)垂直于w，那么w就是平面的法向量。
現在，若要計算平面外一點x到該平面的距離，做法是只要將向量(x-x’)投影到垂直于該平面的方向（即w方向）上就可以了。那么，令(x”-x’)與w的夾角為，距離就可以表示為：
代入，可得：
點到分類面（Separating Hyperplane）的距離已經算出來了。基于這個分類面，所有的點均滿足：，表示所有點都分類正確，則distance公式就可以變換成：
那么，我們的目標形式就轉換為：
對上面的式子還不容易求解，我們繼續對它進行簡化。我們知道分類面和其實是一樣的。也就是說，對w和b進行同樣的縮放還會得到同一分類面。所以，為了簡化計算，我們令距離分類滿最近的點滿足。那我們所要求的margin就變成了:
這樣，目標形式就簡化為：
這里可以省略條件：，因為滿足條件必然滿足大于零的條件。我們的目標就是根據這個條件，計算的最大值。
剛剛我們講的距離分類滿最近的點滿足，也就是說對所有的點滿足。另外，因為最小化問題我們最熟悉也最好解，所以可以把目標最大化轉化為計算的最小化問題。
如上圖所示，最終的條件就是，而我們的目標就是最小化值。
### **Support Vector Machine**
現在，條件和目標變成：
現在，舉個例子，假如平面上有四個點，兩個正類，兩個負類：
不同點的坐標加上條件，可以得到：
最終，我們得到的條件是：
而我們的目標是：
目標最小值為1，即，那么這個例子就得到了最佳分類面的解，如圖所示，且。分類面的表達式為：
最終我們得到的矩的表達式為：
Support Vector Machine(SVM)這個名字從何而來？為什么把這種分類面解法稱為支持向量機呢？這是因為分類面僅僅由分類面的兩邊距離它最近的幾個點決定的，其它點對分類面沒有影響。決定分類面的幾個點稱之為支持向量（Support Vector），好比這些點“支撐”著分類面。而利用Support Vector得到最佳分類面的方法，稱之為支持向量機（Support Vector Machine）。
下面介紹SVM的一般求解方法。先寫下我們的條件和目標：
這是一個典型的二次規劃問題，即Quadratic Programming（QP）。因為SVM的目標是關于w的二次函數，條件是關于w和b的一次函數，所以，它的求解過程還是比較容易的，可以使用一些軟件（例如Matlab）自帶的二次規劃的庫函數來求解。下圖給出SVM與標準二次規劃問題的參數對應關系：
那么，線性SVM算法可以總結為三步：
* **計算對應的二次規劃參數Q，p，A，c**
* **根據二次規劃庫函數，計算b，w**
* **將b和w代入，得到最佳分類面**
這種方法稱為Linear Hard-Margin SVM Algorithm。如果是非線性的，例如包含x的高階項，那么可以使用我們之前在《機器學習基石》課程中介紹的特征轉換的方法，先作的特征變換，從非線性的x域映射到線性的z域空間，再利用Linear Hard-Margin SVM Algorithm求解即可。
### **Reasons behind Large-Margin Hyperplane**
從視覺和直覺的角度，我們認為Large-Margin Hyperplane的分類效果更好。SVM的這種思想其實與我們之前介紹的機器學習非常重要的正則化regularization思想很類似。regularization的目標是將最小化，條件是；SVM的目標是最小化，條件是，即保證了。有趣的是，regularization與SVM的目標和限制條件分別對調了。其實，考慮的內容是類似的，效果也是相近的。SVM也可以說是一種weight-decay regularization，限制條件是。
從另一方面來看，Large-Margin會限制Dichotomies的個數。這從視覺上也很好理解，假如一條分類面越“胖”，即對應Large-Margin，那么它可能shtter的點的個數就可能越少：
之前的《機器學習基石》課程中介紹過，Dichotomies與VC Dimension是緊密聯系的。也就是說如果Dichotomies越少，那么復雜度就越低，即有效的VC Dimension就越小，得到，泛化能力強。
下面我們從概念的角度推導一下為什么dichotomies越少，VC Dimension就越少。首先我們考慮一下Large-Margin演算法的VC Dimension，記為。與數據有關，而我們之前介紹的與數據無關。
假如平面上有3個點分布在單位圓上，如果Margin為0，即，這條細細的直線可以很容易將圓上任意三點分開（shatter），就能得到它的。如果，這條粗粗的線無論如何都不能將圓上的任一三點全完分開（no shatter），因為圓上必然至少存在兩個點的距離小于，那么其對應d的。
那么，一般地，在d維空間，當數據點分布在半徑為R的超球體內時，得到的滿足下列不等式：
之前介紹的Perceptrons的VC Dimension為d+1，這里得到的結果是Large-Margin演算法的。所以，由于Large-Margin，得到的dichotomies個數減少，從而VC Dimension也減少了。VC Dimension減少降低了模型復雜度，提高了泛化能力。
### **總結**
本節課主要介紹了線性支持向量機（Linear Support Vector Machine）。我們先從視覺角度出發，希望得到一個比較“胖”的分類面，即滿足所有的點距離分類面都盡可能遠。然后，我們通過一步步推導和簡化，最終把這個問題轉換為標準的二次規劃（QP）問題。二次規劃問題可以使用Matlab等軟件來進行求解，得到我們要求的w和b，確定分類面。這種方法背后的原理其實就是減少了dichotomies的種類，減少了有效的VC Dimension數量，從而讓機器學習的模型具有更好的泛化能力。
**_注明：_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16（完結） -- Finale