上次詳細的介紹了用最小二乘法求解結(jié)構(gòu)風(fēng)險最小化問題的分類支持向量機网严，并在文章最后給出了求解對偶問題的序列最小優(yōu)化(Sequential Minimal Optimization, ?SMO)算法解的形式萝挤，但是并未提到其具體的解法。今天我將參考由John C. Platt 在1998年發(fā)表的一片名為《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》的論文中提到的比較快的二次規(guī)劃優(yōu)化算法币叹，特別針對SVM和數(shù)據(jù)稀疏時性能更優(yōu).
OK,接下來，讓我們一起了解這天才的想法是如何提煉出來的ba!!!
在開始之前贷掖，讓我們首先定義特征到結(jié)果輸出函數(shù)為：
這個u 與我們之前定義的f(x) = wTx + b 實質(zhì)是一樣的七兜。接著，咱們重新定義咱們原始的優(yōu)化問題钙蒙，權(quán)當重新回顧：
類似地茵瀑，采用Lagrange 乘數(shù)法可以得到;
j將上式引入核函數(shù)κ(·, ·) 可以得到：
此時，和前面類似可以得到：
引入松弛變量之后得到：
最終的優(yōu)化目標為：
根據(jù)KKT條件可以得出a的取值意義為：
1. (1)式表明是正常分類躬厌，在邊界內(nèi)部马昨，我們知道正確分類的點yif(xi) ≥ 0。
2. (2)式表明了是支持向量扛施，在邊界上鸿捧。
3. (3)式表明了是在兩條邊界之間。
而最優(yōu)解需要滿足KKT 條件疙渣，即上述3 個條件都得滿足笛谦，以下幾種情況出現(xiàn)將會出現(xiàn)不滿足：
所以要找出不滿足KKT 條件的這些αi，并更新這些αi昌阿，但這些αi 又受到另外一個約束：
因此饥脑，我們通過另一個方法，即同時更新αi 和αj懦冰，要求滿足下式灶轰，就能保證和為0 的約束。
消去αi刷钢，可得到一個關(guān)于單變量αj 的一個凸二次規(guī)劃問題笋颤，不考慮其約束0 ≤ αj ≤ C,可以得其解為：
然后考慮約束0 ≤ αj ≤ C 可以得到αi 的解析解為：
把SMO 中對于兩個參數(shù)求解過程看成線性規(guī)劃來理解來理解的話，那么下圖所表達式的辨識内地。
根據(jù)yi和yj 同號或異號伴澄，可得出兩個上、下界分別為：
對于αi阱缓，有;
那么如果和求得αi 和αj 呢非凌？對于αi，可以通過剛剛說的那3 種不滿足KKT 的條件來找荆针；而對于αj敞嗡，可以通過max |Ei ? Ej | 求得颁糟；而b 的更新則是:
每次更新完αi 和αj 后，都需要再重新計算b喉悴，及對應(yīng)的Ei 和Ej棱貌。
SMO算法的計算步驟：
SMO 的主要步驟下圖所示。其中迭代的兩步是：
(1) 選擇接下來要更新的一對αi 和αj：采用啟發(fā)式的方法進行選擇箕肃，以使目標函數(shù)最大程度地接近其全局最優(yōu)值
(2) 將目標函數(shù)對αi 和αj 進行優(yōu)化婚脱，保持其它所有的αk(k ?= i, j) 不變
假定在某一次迭代中，需要更新α1 和α2勺像，那么優(yōu)化目標可以寫成：
而更新α1 和α2 的步驟如下：
綜上起惕，SMO 算法的基本思想是將Vapnik 在1982 年提出的Chunking 方法推到極致，SMO 算法每次迭代只選出兩個分量αi 和αj 進行調(diào)整咏删，其它分量則保持固定不變惹想，在得到解αi 和αj 之后，再用αi 和αj 改進其它分量督函。與通常的分解算法比較嘀粱，盡管它可能需要更多的迭代次數(shù)，但每次迭代的計算量比較小辰狡，所以該算法表現(xiàn)出整理的快速收斂性锋叨，且不需要存儲核矩陣，也沒有矩陣運算宛篇。
