SVM 英文名為 Support Vector Machine，叫支援向量機，SVM 是一個二分類模型。
感知機學習演算法會因為初始值不同而得到不同的超平面，而 SVM 試圖尋找一個最佳超平面，來劃分資料，怎麼才算最佳呢？我們自然能想到，距離樣本點距離儘可能的遠，模型的泛化效能和魯棒性更強為最好，而且可以找到一條唯一的超平面。
如下圖可以看出，感知機的超平面可以有無數條，SVM只要找到一條距離樣本點最大間隔的超平面即可。
SVM 目標
我們知道，感知機是一個現在網上已經有很多最初被提出是為了解決二分類問題，假設如下有正負樣本。
由此，我們知道，SVM 的目標就是要找到一條間隔最大化的超平面，使得樣本點距離超平面儘可能的遠，那麼，我們如何找到間隔最大的超平面呢？
首先，我們要先想到，間隔最大，即是求
樣本點到超平面的距離
。
而現在，我們有 N 個樣本點，則我們可能有 N 個距離，那我們最終想要的就是，離超平面距離最小的樣本點的最大值。
既然是最大間隔分類器，我們拆開來解釋：
最大
：找到距離樣本點最大的間隔
間隔
：N 個樣本點距離超平面的最小值
分類器
：既然是二分類問題，那麼我們的超平面就是要將樣本分開，對於超平面 y=w^Tx+b 而言，我們可以假設有兩條超平面，一條是 w^Tx + b > 0 和 w^Tx + b < 0，我們可以引入函式 yi = {-1， +1}，將兩個超平面用一個函式表示，如圖。
現在就需要我們想辦法計算樣本點到超平面的距離，如下圖，表示點 （x_i，y_i） 到超平面 y = w^Tx + b 的距離的計算，最終將目標轉化為找到 N 個樣本點距離超平面的最小距離。
將 min-distance（w，b，x） 代入 max-margin（w，b），條件是 yi = w^Txi + b > 0，並且是恆大於 0，由此，我們可以將下圖的式子轉換一下，將模去掉。
並且我們還能看出，1/||w|| 與 xi 無關，我們可以將它提到前面去。
這樣一來，我們的問題就轉化成求解一個帶約束的最佳化問題。對於條件 yi（w^Txi + b） > 0 而言，一定存在一個 γ，使得 min（yi（w^Txi + b） > 0） = γ，為了簡化計算，我們可以令 yi（w^Txi + b） = γ。
假設令 γ=1，則我們可以得到最終的式子只與 W 有關，我們要求損失函式，則將其轉化成最小化問題。
可能有的人會疑惑，為什麼 γ=1可行，我們知道，y = w^Tx + b 和 y = 2w^Tx + 2b 表示的是同一個超平面，我們如果將 2-範數 固定下來，這樣去指定 y = w^Tx + b 的值是可以確定下來，否則有無窮多個，因為可以隨機縮放，因為 γ > 0，所以無論 γ 等於多少，都可以任意比例縮放成 1，對整個等式無影響。
我們可以看到，目標函式是二次的，約束條件是線性的，所以它是一個帶約束的凸二次規劃問題，這個問題可以用現成的 QP 最佳化包進行求解，一言以蔽之：在一定約束下，目標最優，損失最小。
引入拉格朗日乘子
透過拉格朗日乘子，我們已經將帶約束的原問題轉化成了無約束的問題。
那麼什麼是拉格朗日對偶性呢？簡單來講，透過給每個約束條件加上拉格朗日乘子 λ，定義拉格朗日函式 （透過拉格朗日函式將約束條件融合到目標函式中，從而只用一個函式表示式便能清楚的表達出我們的問題）。
我們可以看到，原式子是一個關於 w 的凸二次函式，約束條件是 N 個關於 x 的不等式。透過引入拉格朗日乘子之後，我們可以將有約束問題轉化為一個無約束的，只與 λ 有關的式子。
我們可以簡單的理解一下，為什麼可以這樣定義，假設如下是關於 w，b 的集合，我們可以將其表示為兩個部分，一部分是 △>0，一部分是 △<=0。
當 △>0 時，即 1 - yi（w^Txi + b） > 0，顯然 max L（w，b，λ） = 1/2（w^Tw） + ∞ = ∞，此時，對於我們求解無意義，我們也得不到最小化的值。
當 △<=0 時，即 1 - yi（w^Txi + b） <= 0，顯然 max L（w，b，λ） = 1/2（w^Tw） + 0 = 1/2（w^Tw），我們可以看到，與原問題相符。
所以，當我們談到滿足最最佳化的條件時，通常情況都是 △<=0 的情況。
此外，由於這個問題的特殊結構，還可以透過拉格朗日對偶性變換到對偶變數的最佳化問題，即透過求解與原問題等價的對偶問題得到原始問題的最優解，這就是線性可分條件下支援向量機的對偶演算法，這樣做的優點在於：一是對偶問題往往更容易求解，二是可以自然的引入核函式進而推廣到非線性分類問題。
對偶問題與原問題
這裡用 p^* 表示原問題的最優解，且和最初的問題是等價的。如果直接求解，那麼一上來便得面對 w，b 兩個引數，而 λ 又是不等式約束，這個求解過程不好做。不放把最小和最大的位置交換下。
交換以後的新問題是原問題的對偶問題，對偶問題的最優解用 d^* 來表示，而且有 d^* <= P^* ，在滿足某些條件的情況下，這兩者相等，這個時候，口可以透過求解對偶問題來間接求解原問題。
換言之，之所以從 min max 原始問題 p^* 轉化為 max min 的對偶問題 d^，一者是因為 d^ 是 p^* 是近似解，二者，轉化成對偶問題更容易求解。
下面可以先求 L 對 w，b 的極小，再求 L 對 λ 的極大。
KKT
上面提到 d^* <= P^* 在滿足某些條件的情況下，兩者相等，某些條件就是 KKT 條件。
對偶問題求解的 3 個步驟
1，
固定 λ，讓 L 關於 w,b 最小化
，對 w，b 求偏導，令 δL/δw = 0 和 δL/δb = 0。
將以上結果代入 L，最終結果我們可以看到，最終的結果只與 x 有關。
如何理解這一結果呢？我們可以看看 KKT 條件中的其中一個。
當 λ=0 時，此時的 L 只與 w 有關，對超平面無限制。
當 λ>0 時，此時 1 - yi（w^Txi + b） = 0，因為 yi={-1， +1}，此時，L 與在邊界上的點有關，即只與支援向量有關。
2， 對 λ 求極大，即是關於對偶問題的最最佳化問題，經過上面的第一個步驟的求 w 和 b，得到拉格朗日函式式子已經沒有了變數 w，b，只有 λ。
並且我們也在之前求導過程中求出了 w。
將上述式子代入 L 中，可以求出 w 和 b
最終，我們可以得到新的分類決策函式。
3， 在求得 L（w，b，λ） 關於 w 和 b 最小化，以及對 λ 極大之後，最後一步便是利用
SMO 演算法求解
對偶問題中的拉格朗日乘子 λ。
我們的拉格朗日函式中，在 λi = {λ1，λ2，。。。，λn} 上求上述目標函式的最小值，為了求解這些乘子，每次從中任意抽取兩個乘子 λ1， λ2，然後固定 λ1， λ2 以外的乘子 λi = {λ3，λ4，。。。，λn}，使得目標函式只關於 λ1， λ2 的函式，這樣，不斷的從一堆乘子中任意抽取兩個求解，不斷的迭代求乘子問題，最終達到求解原問題的目的。
