序列最小優化算法

序列最小優化算法
序列最小優化算法
概況
類別	訓練支持向量機的優化算法
複雜度
最壞時間複雜度	O(n³)
相關變量的定義

序列最小優化算法（英語：Sequential minimal optimization, SMO）是一種用於解決支持向量機訓練過程中所產生優化問題的算法。SMO由微軟研究院的約翰·普萊特（英語：John Platt）於1998年發明^[1]，目前被廣泛使用於SVM的訓練過程中，並在通行的SVM庫LIBSVM中得到實現。^[2]^[3] 1998年，SMO算法發表在SVM研究領域內引起了轟動，因為先前可用的SVM訓練方法必須使用複雜的方法，並需要昂貴的第三方二次規劃工具。而SMO算法較好地避免了這一問題。^[4]

問題定義

SMO算法主要用於解決支持向量機目標函數的最優化問題。考慮數據集 $(\mathbf {x_{1}} ,y_{1}),\ldots ,(\mathbf {x_{n}} ,y_{n})$ 的二分類問題，其中 $\mathbf {x_{i}}$ 是輸入向量， $y_{i}\in \{-1,1\}$ 是向量的類別標籤，只允許取兩個值。一個軟間隔支持向量機的目標函數最優化等價於求解以下二次規劃問題的最大值：

W=\max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},

滿足：

0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots ,n,

\sum _{i=1}^{n}y_{i}\alpha _{i}=0,

其中， $C$ 是SVM的參數，而 $K(\mathbf {x_{i}} ,\mathbf {x_{j}} )$ 是核函數。這兩個參數都需要使用者制定。

算法

SMO是一種解決此類支持向量機優化問題的迭代算法。由於目標函數為凸函數，一般的優化算法都通過梯度方法一次優化一個變量求解二次規劃問題的最大值，但是，對於以上問題，由於限制條件 $\sum _{i=1}^{n}y_{i}\alpha _{i}=0$ 存在，當某個 $\alpha _{i}\,$ 從 $\alpha _{i}^{old}$ 更新到 $\alpha _{i}^{new}$ 時，上述限制條件即被打破。為了克服以上的困難，SMO採用一次更新兩個變量的方法。

數學推導

假設算法在某次更新時更新的變量為 $\alpha _{1}\,$ 和 $\alpha _{2}\,$ ，則其餘變量都可以視為常量。為了描述方便，規定

K_{ij}=K(\mathbf {x_{i}} ,\mathbf {x_{j}} ),f(\mathbf {x_{i}} )=\sum _{j=1}^{n}y_{j}\alpha _{j}K_{ij}+b,

v_{i}=f(\mathbf {x_{i}} )-\sum _{j=1}^{2}y_{j}\alpha _{j}K_{ij}-b

因而，二次規劃目標值可以寫成

{\begin{array}{lcl}W(\alpha _{1},\alpha _{2})&=&\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j}\\&=&\alpha _{1}+\alpha _{2}-{\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}\\&&-y_{1}\alpha _{1}v_{1}-y_{2}\alpha _{2}v_{2}+{\text{constant}}\,\end{array}}

由於限制條件 $\sum _{i=1}^{n}y_{i}\alpha _{i}=0$ 存在，將 $\alpha _{3},\ldots ,\alpha _{n},y_{3},\ldots ,y_{n}$ 看作常數，則有 $\alpha _{1}y_{1}+\alpha _{2}y_{2}=C\,$ 成立（ $C\,$ 為常數）。由於 $y_{i}\in \{-1,1\}\,$ ，從而 $\alpha _{1}=\gamma -s\alpha _{2}\,$ （ $\gamma \,$ 為變量 $y_{1}C$ ， $s=y_{1}y_{2}\,$ ）。取 $\alpha _{2}\,$ 為優化變量，則上式又可寫成

{\begin{array}{lcl}W(\alpha _{2})&=&\gamma -s\alpha _{2}+\alpha _{2}-{\frac {1}{2}}K_{11}(\gamma -s\alpha _{2})^{2}-{\frac {1}{2}}K_{22}\alpha _{2}^{2}\\&&-sK_{12}(\gamma -s\alpha _{2})\alpha _{2}-y_{1}(\gamma -s\alpha _{2})v_{1}-y_{2}\alpha _{2}v_{2}+{\text{constant}}\end{array}}

對 $\alpha _{2}\,$ 求偏導以求得最大值，有

{\begin{array}{lcl}{\frac {\partial W(\alpha _{2})}{\partial \alpha _{2}}}&=&-s+1+sK_{11}\gamma -K_{11}\alpha _{2}-K_{22}\alpha _{2}+2K_{12}\alpha _{2}-sK_{12}\gamma \\&&+y_{2}v_{1}-y_{2}v_{2}=0\end{array}}

因此，可以得到

\alpha _{2}^{new}={\frac {y_{2}(y_{2}-y_{1}+y_{1}\gamma (K_{11}-K_{12})+v_{1}-v_{2})}{K_{11}+K_{22}-2K_{12}}}

規定誤差項 $E_{i}=f(\mathbf {x} _{i})-y_{i}$ ，取 $\gamma =\alpha _{1}^{old}+s\alpha _{2}^{old}$ ，並規定 $K=K_{11}+K_{22}-2K_{12}\,$ ，上述結果可以化簡為

\alpha _{2}^{new}=\alpha _{2}^{old}+{\frac {y_{2}(E_{1}-E_{2})}{K}}

再考慮限制條件 $0\leqslant \alpha _{i}\leqslant C$ ， $(\alpha _{1},\alpha _{2})\,$ 的取值只能為直線 $\alpha _{1}y_{1}+\alpha _{2}y_{2}=\gamma \,$ 落在 $[0,C]\times [0,C]$ 矩形中的部分。因此，具體的SMO算法需要檢查 $\alpha _{2}^{new}$ 的值以確認這個值落在約束區間之內。^[1]^[5]

算法框架

SMO算法是一個迭代優化算法。在每一個迭代步驟中，算法首先選取兩個待更新的向量，此後分別計算它們的誤差項，並根據上述結果計算出 $\alpha _{2}^{new}$ 和 $\alpha _{1}^{new}$ 。最後再根據SVM的定義計算出偏移量 $\mathbf {b}$ 。對於誤差項而言，可以根據 $\alpha _{1}^{new}$ 、 $\alpha _{2}^{new}$ 和 $b$ 的增量進行調整，而無需每次重新計算。具體的算法如下：

1 随机数初始化向量权重 $\alpha _{i}\,$ ，并计算偏移 $b$ 
2 初始化误差项 $E_{i}\,$ 
3 选取两个向量作为需要调整的点
4 令 $\alpha _{2}^{new}=\alpha _{2}^{old}+{\frac {y_{2}(E_{1}-E_{2})}{K}}$ 
5 如果 $\alpha _{2}^{new}>V$ 
6     令 $\alpha _{2}^{new}=V$ 
7 如果 $\alpha _{2}^{new}<U$ 
8     令 $\alpha _{2}^{new}=U$ 
9 令 $\alpha _{1}^{new}=\alpha _{1}^{old}+y_{1}y_{2}(\alpha _{2}^{old}-\alpha _{2}^{new})$ 
10 利用更新的 $\alpha _{1}^{new}$ 和 $\alpha _{2}^{new}$ 修改 $E_{i}\,$ 和 $b$ 的值
11 如果达到终止条件，则停止算法，否则转3