序列最小優化算法

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

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

問題定義

主條目：支持向量機 § 原型

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

${\displaystyle 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},}$

滿足：

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

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

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

算法

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

數學推導

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

因此，可以得到

${\displaystyle \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}}}}$

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

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

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

算法框架

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

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

其中，${\displaystyle U}$和${\displaystyle V}$為${\displaystyle \alpha _{2}^{new}}$的下界和上界。特別地，有

${\displaystyle U={\begin{cases}\max {\left\{0,\alpha _{2}^{old}-\alpha _{1}^{old}\right\}}&y_{1}y_{2}=-1\\\max {\left\{0,\alpha _{1}^{old}+\alpha _{2}^{old}-C\right\}}&y_{1}y_{2}=1\end{cases}},V={\begin{cases}\min {\left\{C,C+\alpha _{2}^{old}-\alpha _{1}^{old}\right\}}&y_{1}y_{2}=-1\\\min {\left\{C,\alpha _{2}^{old}+\alpha _{1}^{old}\right\}}&y_{1}y_{2}=1\end{cases}}}$

這一約束的意義在於使得${\displaystyle \alpha _{1}^{new}}$和${\displaystyle \alpha _{2}^{new}}$均位於矩形域${\displaystyle [0,C]\times [0,C]}$中。^[5]

優化向量選擇方法

可以採用啟發式的方法選擇每次迭代中需要優化的向量。第一個向量可以選取不滿足支持向量機KKT條件的向量，亦即不滿足

${\displaystyle y_{i}f(\mathbf {x} _{i}){\begin{cases}>1&\alpha _{i}=0\\=1&0<\alpha _{1}<C\\<1&\alpha _{i}=C\end{cases}}}$

的向量。而第二個向量可以選擇使得${\displaystyle |E_{1}-E_{2}|\,}$最大的向量。^[5]

終止條件

SMO算法的終止條件可以為KKT條件對所有向量均滿足，或者目標函數${\displaystyle W(\alpha )\,}$增長率小於某個閾值，即

${\displaystyle {\frac {W(\alpha ^{t+1})-W(\alpha ^{t})}{W(\alpha ^{t})}}<T}$^[5]