序列最小优化算法

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

## 問題定義

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}$ 的值以確認這個值落在約束區間之內。

### 算法框架

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
```

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

　
: : $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}}$

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

### 優化向量選擇方法

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

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

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

### 終止條件

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

　
: : ${\frac {W(\alpha ^{t+1})-W(\alpha ^{t})}{W(\alpha ^{t})}}<T$

## 參考資料

## 參見

* 支持向量機
* 核機器
* 費希爾核
* 多項式核函數
* 預測分析