3 非線性支持向量機、SMO算法
理論上，KKT條件可以解出SVM，但是當訓練集容量很大時，這種方法顯得異常低效，甚至無法使用。SMO（sequential minimal optimization）算法為解決這一難題提供了一種思路。
SMO算法是一種啟發(fā)式算法，先選擇兩個變量（在這里變量就是對偶變量alpha），要求一個是違反KKT條件最嚴重的一個，另一個由約束條件生成，其余變量固定；然后不斷優(yōu)化變量的兩兩組合，直到所有變量滿足KKT條件；再計算得到原問題的解w和b。
3.1 假設空間
3.2 目標函數(shù)變形（對偶函數(shù)顯式化）
到這里，目標函數(shù)進一步變形的關(guān)鍵就是通過求極值顯式的呈現(xiàn)出對偶函數(shù)最小化的表達式。
3.3 優(yōu)化算法（SMO）
回顧感知機中的優(yōu)化算法，我們是直接使用隨機梯度下降進行迭代，而這里動用SMO的SVM要復雜得多：
（1）、設置參數(shù)初始值 a = 0, b = 0
（2）、執(zhí)行外循環(huán)，即搜索違反KKT條件的樣本點，優(yōu)先選擇支持向量點（0<a1<C），定為a1
（3）、執(zhí)行內(nèi)循環(huán)，取 max|E1-E2| 的點（即更新幅度最大），定為a2
（4）、從目標函數(shù)中剝離出a1和a2，并建立二者的線性關(guān)系，如下所示：
（5）、消元&優(yōu)化：消元去掉a1，此時目標函數(shù)中只剩下一個變量a2，對a2求導計算a2的未剪輯值（代碼中只需關(guān)注最后一步）：
（6）、邊界截斷：根據(jù)約束條件，裁剪得到a2的更新值。此處要考慮y1和y2同號和異號兩種情況，在同號的情況下，a1y1 + a2y2 的直線斜率為負，a2的上確界和下確界如下所示：
在異號的情況下，a1y1 + a2y2 的直線斜率為正，a2的上確界和下確界如下所示：
（7）、至此，可以計算出a1和w
（8）、計算 b（代碼中需關(guān)注后三步）：
（9）、實時保存更新過的Ei
（10）、迭代，直至在精度eps內(nèi)滿足停止條件
