支持向量機Part4—SMO演算法

前面SVM系列三篇文章對SVM的理論進行了詳細的推導，得到了SVM演算法的求解框架；對於具體的求解過程，喝杯咖啡，好好聊聊。

1.SVM演算法框架

前三篇文章所有的努力就是為了得到以下SVM演算法求解框架：

1.1構造優化問題（選擇核函數K與懲罰係數C）：

1.2根據上述優化問題求；

1.3求b：

求出所有支持向量（滿足的樣本點(Xs,Ys)）對應的b，得到b的平均值，即為最終的b值。

1.4得到分類超平面：

2.SMO演算法求

是含有m個變數的向量值，我們無法根據優化問題直接求解。而SMO演算法每次只對兩個變數進行優化（比如），將其他變數看成常數（），這樣就將m個變數的優化問題轉換為兩個變數的優化問題（由於必須滿足，因此每次需取兩個變數進行優化）。定義，並且將常量去除，轉化為兩個變數的優化問題表示如下：

2.1如何求

需要在約束條件下進行求解，由於y1、y2取值只能為1/-1，因此y1/y2組成的約束條件如下：

Step1：假設上一輪迭代得到；

Step2：本輪迭代對目標函數求偏導，得到未經剪輯的；

Step3：本輪迭代得到經過剪輯的:

Step4：根據的線性關係求出。

2.2如何求

將目標函數對求偏導即可。下面進一步簡化目標函數，並對求偏導，得到：

2.3如何選擇

現在我們已經知道SMO演算法每次需要選擇兩個變數進行優化，那這兩個變數該如何選擇？

2.3.1第一個變數：

第一個變數為外層循環，選擇違反KKT條件最嚴重的點。（在「分類模型」支持向量機Part2—線性支持向量機中我們知道了KKT條件。）

2.3.2第二個變數：

第二個變數為內層循環，在選定的情況下（E1也隨之確定），應該選擇讓|E2-E1|有足夠大變化的。如果找不到滿足條件的，可以跳出內層循環重新選擇。

3.求b

SMO演算法計算完之後，計算b。

計算出b後更新Ei，為下一次迭代做準備：

(其中，S為所有支持向量的集合）

勝利在望，SVM演算法原理介紹完了，下文就基於Python實現它！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！