一、簡介
SVM是一種二分類模型
目的：尋找一個超平面對樣本進行分割
分割原則：間隔最大化
問題求解方法：将模型轉換為一個凸二次規劃問題
由簡至繁的模型包括：
1、當訓練樣本線性可分時，通過硬間隔最大化，學習一個線性可分支援向量機；
2、當訓練樣本近似線性可分時，通過軟間隔最大化，學習一個線性支援向量機；
3、當訓練樣本線性不可分時，通過核技巧和軟間隔最大化，學習一個非線性支援向量機；
二、線性可分支援向量機
本節先介紹線性可分支援向量機
1、間隔最大化和支援向量
如果一個線性函數（超平面）能夠将樣本分開，稱這些資料樣本是線性可分的。
Here is a 簡單的二維空間例子：
顯然有不隻一條直線可以将樣本分開（有無數條）。我們說的線性可分支援向量機就對應着能将資料正确劃分且間隔最大的直線（唯一）。關鍵詞：正确劃分資料、間隔最大。
引出兩個問題：1、why間隔最大？ 2、how間隔最大？
About Q1：
一般來說，一個點距離分離超平面的遠近可以表示分類預測的确信度。如上圖中的點A、B，B被預測為正類的确信度要大于A點。故，不必考慮所有的樣本點，隻需讓求得的超平面使得離它近的點間隔最大。
About Q2:
首先，劃分超平面可通過如下線性方程來描述:
我們現在假設超平面能将訓練樣本正确的分類，即對于訓練樣本(xi,yi)，滿足以下公式：
該公式稱為最大間隔假設，yi=+1 表示樣本為正樣本，yi=−1 表示樣本為負樣本，式子前面選擇大于等于+1，小于等于-1隻是為了計算友善，原則上可以是任意常數，但無論是多少，都可以通過對 w 的變換使其為 +1 和 -1 。接着将該公式左右都乘上yi，得到：
等價為：
訓練集中所有樣本都應該滿足該公式。如下圖所示，距離超平面最近的這幾個樣本點滿足：，它們被稱作**“支援向量”。虛線稱作邊界**，兩條虛線之間的距離成為間隔。
PS：在決定分離超平面時，隻有支援向量起作用，而其他的執行個體點并不起作用。如果移動支援向量将改變改變所求的解，但是如果在間隔邊界以外移動其他執行個體點，甚至去掉這些點，則解是不會改變的。
至此，我們求得了間隔，而SVM的求解思想是使得間隔最大化，即最終的目标為：
為了簡化運算，可将該公式轉化成：
該公式即為支援向量機的基本型。這是一個凸二次規劃問題。
解出對應的W和b之後，即得到了分離超平面Wx+b=0和分類決策函數f(x)=sign(Wx+b)
三、學習的對偶算法
對于凸二次規劃問題，可以通過一些現成的QP的優化工具來得到最優解。
但是，該算法通過拉格朗日對偶性變換之後，可以找到一種更加有效的方法來進行求解。于是，應用拉格朗日對偶性，通過求解對偶問題得到最優解，這就是線性可分條件下支援向量機的對偶算法。
這樣做的優點：對偶問題往往更容易求解；可以自然引入核函數，進而推廣到非線性分類問題。（核函數的一個作用就是可以将一個低維的非線性資料映射成為高維的線性資料）
1、對偶問題簡介
在限制最優化問題中，常常利用拉格朗日對偶性将原始問題轉換為對偶問題，通過求解對偶問題而得到原始問題的解。首先對對偶問題進行簡要介紹：
對于一個優化問題：
這是一個帶等式限制的優化問題。首先建構拉格朗日函數，為此，對每一個不等式限制，引入拉格朗日乘子：
然後我們将拉格朗日函數對x求極值，即對x求導，導數為0，就可以得到α關于x的函數，然後再代入拉格朗日函數就變成：
這時候，帶等式限制的優化問題就變成隻有一個變量α（多個限制條件就是向量）的優化問題，這時候的求解就很簡單了。同樣是求導另其等于0，解出α即可。需要注意的是，我們把原始的問題叫做primal problem，轉換後的形式叫做dual problem。需要注意的是，原始問題是最小化，轉化為對偶問題後就變成了求最大值了。對于不等式限制，其實是同樣的操作。簡單地來說，通過給每一個限制條件加上一個 Lagrange multiplier（拉格朗日乘子），我們可以将限制條件融和到目标函數裡去，這樣求解優化問題就會更加容易。
2、SVM的對偶算法
對應的，對于SVM的primal problem是：
首先引入拉格朗日乘子，可以得到如下的拉格朗日函數（1）：
然後對L(w, b, α)分别求w和b的極值。也就是L(w, b,α)對w和b的梯度為0：∂L/∂w=0和∂L/∂b=0，還需要滿足α>=0。
求解這裡導數為0的式子可以得到：
将其帶入拉格朗日函數（1），可得：
于是，原問題轉換成了僅關于 α 的問題，即dual problem：
解出 α之後根據公式可以求得 w ， 進而求得 b，進而得到模型：
（2）
三、支援向量分析
上述過程的KKT條件為：（KKT條件的介紹可參考《統計學習方法P227》）
我們分析一下，對于任意的訓練樣本 (xi,yi)
若 αi=0，則其不會在最終模型公式（2）中的求和項中出現，也就是說，它不影響模型的訓練；
若 αi>0，則
也就是
即該樣本一定在邊界上，是一個支援向量。
可得出結論：隻有支援向量的αi不為0，如下圖所示：
這裡顯示出了支援向量機的重要特征：當訓練完成後，大部分樣本都不需要保留，最終模型隻與支援向量有關。有了αi，我們不需要求出w，隻需将新來的樣本和訓練資料中的所有樣本做内積和即可。