SMO演算法是幹什麼的?有什麼作用?不要純概念

01-27

SMO(Sequential Minimal Optimization)是針對求解SVM問題的Lagrange對偶問題，一個二次規劃式，開發的高效演算法。傳統的二次規劃演算法的計算開銷正比於訓練集的規模，而SMO基於問題本身的特性（KKT條件約束）對這個特殊的二次規劃問題的求解過程進行優化。對偶問題中我們最後求解的變數只有Lagrange乘子 ${vec alpha }$ 向量，這個演算法的基本思想就是每次都只選取一對 $left( {{alpha _i},{alpha _j}} ight)$ ，固定 ${vec alpha }$ 向量其他維度的元素的值，然後進行優化，直至收斂。

SMO幹了什麼？

首先，整個對偶問題的二次規劃表達如下：

$egin{align} mathop {max }limits_{vec alpha } quad sumlimits_{i = 1}^n {{alpha _i}} - frac{1}{2}sumlimits_{i = 1}^n {sumlimits_{j = 1}^n {{alpha _i}{alpha _j}{y_i}{y_j}{f{x}}_i^T{{f{x}}_j}} } \ s.t. quad sumlimits_{i = 1}^n {{alpha _i}{y_i}} = 0 \ quad {alpha _i} ge 0, quad i = 1,2, ldots ,n end{align}$

SMO在整個二次規劃的過程中也沒幹別的，總共幹了兩件事：

選取一對參數 $left( {{alpha _i},{alpha _j}} ight)$
固定 ${vec alpha }$ 向量的其他參數，將 $left( {{alpha _i},{alpha _j}} ight)$ 代入上述表達式進行求最優解獲得更新後的 $left( {{alpha _i},{alpha _j}} ight)$

SMO不斷執行這兩個步驟直至收斂。

因為有約束 $sumlimits_{i = 1}^n {{alpha _i}{y_i}} = 0$ 存在，實際上 $[{{alpha _i}}]$ 和 $[{{alpha _j}}]$ 的關係也可以確定。 ${alpha _i}{y_i} + {alpha _j}{y_j} = C$ 這兩個參數的和或者差是一個常數。

所以雖然宣傳上說是選擇了一對 $left( {{alpha _i},{alpha _j}} ight)$ ，但還是選擇了其中一個，將另一個寫作關於它的表達式代入目標函數求解。

為什麼SMO跑的那麼快，比提出之前的演算法不知道高到哪裡去了？

正如上面提到的，在固定其他參數以後，這就是一個單變數二次規劃問題，僅有的約束也是這個變數 $alpha _i ge 0$ ，顯然有閉式解。不必再調用數值優化演算法。

KKT條件是對偶問題最優解的必要條件：

$egin{cases} {{alpha _i} ge 0}\ {{y_i}fleft( {{{f{x}}_i}} ight) - 1 ge 0}\ {{alpha _i}left( {{y_i}fleft( {{{f{x}}_i}} ight) - 1} ight) = 0} end{cases}$

除了第一個非負約束以外，其他約束都是根據目標函數推導得到的最優解必須滿足的條件，如果違背了這些條件，那得到的解必然不是最優的，目標函數的值會減小。

所以在SMO迭代的兩個步驟中，只要 $left( {{alpha _i},{alpha _j}} ight)$ 中有一個違背了KKT條件，這一輪迭代完成後，目標函數的值必然會增大。Generally speaking，KKT條件違背的程度越大，迭代後的優化效果越明顯，增幅越大。

怎樣跑的更快？

和梯度下降類似，我們要找到使之優化程度最大的方向（變數）進行優化。所以SMO先選取違背KKT條件程度最大的變數，那麼第二個變數應該選擇使目標函數值增大最快的變數，但是這個變數怎麼找呢？比較各變數優化後對應的目標函數值的變化幅度？這個樣子是不行的，複雜度太高了。

SMO使用了一個啟發式的方法，當確定了第一個變數後，選擇使兩個變數對應樣本之間最大的變數作為第二個變數。直觀來說，更新兩個差別很大的變數，比起相似的變數，會帶給目標函數更大的變化。間隔的定義也可以借用偏差函數

$[{E_i} = max left( {{y_i}fleft( {{{f{x}}_i}} ight) - 1,0} ight)]$

我們要找的也就是使對於 $alpha_i$ 來說使 $left| {{E_i} - {E_j}} ight|$ 最大的 $alpha_j$

很慚愧，只做了一點微小的工作。

References

[1] Platt, John. "Sequential minimal optimization: A fast algorithm for training support vector machines." (1998).

最近剛看完smo演算法的代碼，所以試著回答題主的問題。

解決svm首先將原始問題轉化到對偶問題，而對偶問題則是一個凸二次規劃問題，理論上你用任何一個解決凸二次規劃的軟體包都可以解決，但是這樣通常來說很慢，大數據情況下尤其不實際，smo是微軟研究院的大神發明的解決svm對偶問題的優化演算法，可以更快找到好的解。通常而言分簡化版和優化版smo演算法。

簡化版:每次迭代隨機選取alpha_i和alpha_j,當然其中要有一個違反kkt條件，通常先選一個違反kkt條件的alpha_i，然後隨機選擇一個alpha_j,然後用類似坐標上升(下降)的演算法來優化目標函數，具體細節題主可以看相關代碼，推薦《machine learning in action》的svm部分，但是這樣的優化方式並不是最快的；

優化版:用啟發式的演算法選擇alpha_j,即選擇alpha_j,使得|Ei-Ej|最大，至於為什麼，因為變數的更新步長正比於|Ei-Ej|,也就是說我們希望變數更新速度更快，其餘的和簡化版其實區別不大；

應該還有其他版本的smo，沒看過不做評論，希望對題主有用。

wiki: https://en.wikipedia.org/wiki/Sequential_minimal_optimization

@司徒功源。，答主，你好，你上面的回答中提到simpleSMO中在選擇alpha_時，要使其違反KKT條件，這點我表示贊同，但有一事不解，還請題主解答，《machine learning in action》中對於這個條件的判別是怎樣體現這一思想的呢？先貼上部分代碼：

fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b Ei = fXi - float(labelMat[i])#if checks if an example violates KKT conditions if ((labelMat[i]*Ei &< -toler) and (alphas[i] &< C)) or ((labelMat[i]*Ei &> toler) and (alphas[i] &> 0)): j = selectJrand(i,m) fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b Ej = fXj - float(labelMat[j])

先說下我的理解：

請問你是怎麼理解的？先行謝謝了。

用於求解svm的對偶問題的最優解的方法，就是smo

svm的一個高效實現

是用來求解出SVM的帶約束的優化問題的對偶問題的最優解的二次規劃方法，通過求解出對偶問題的最優解，從而得到原始問題的最優解。

這種方法通過不斷地將對偶問題的二次規劃問題分解成為只有兩個變數的二次規劃問題，並對子問題求解，通過不斷地更新，迭代找出所有約束變數值。

SMO演算法的具體步驟如下：

1.確定非線性支持向量機的優化目標：

$min frac{1}{2}sum_{i=1}^{m}{sum_{j=1}^{m}{alpha_{i}alpha_{j}y^{i}y^{j}K(X^{i}.X^{j})-sum_{i=1}^{m}{alpha_{i}}}}$

$s.t. sum_{i=1}^{m}{alpha_{i}y^{i}}=0$

$0le alpha_{i}leq C$

2.選擇出兩個變數 $alpha_{1} ，alpha_{2}$ ，將優化問題轉化成

$min frac{1}{2}K_{11}alpha_{1}^{2}+frac{1}{2}K_{22}alpha_{2}^{2}+y^{(1)}y^{(2)}K_{12}alpha_{1}alpha_{2}-(alpha_{1}+alpha_{2})+y^{(1)}alpha_{1}sum_{k=3}^{m}{y^{(k)}alpha_{k}K_{k1}} +y^{(2)}alpha_{2}sum_{k=3}^{m}{y^{(k)}alpha_{k}K_{k2}}+M_{1}$