序列最小優化演算法

序列最小優化演算法（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 - \frac12 \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 - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(x_i, x_j) \alpha_i \alpha_j \\ <pre> &=&\alpha_1+\alpha_2-\frac12 K_{11} \alpha_1^2 - \frac12 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} \, </pre> \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_1C$，$s = y_1 y_2 \,$）。取$\alpha_2 \,$為優化變量，則上式又可寫成

$$\begin{array}{lcl} W(\alpha_2) &=&\gamma - s \alpha_2 + \alpha_2 - \frac12 K_{11} (\gamma - s \alpha_2)^2 - \frac12 K_{22} \alpha_2^2 \\ <pre> & &- s K_{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} </pre>$$

對$\alpha_2 \,$求偏導以求得最大值，有

$$\begin{array}{lcl} \frac{\partial W(\alpha_2)}{\partial \alpha_2} &=& -s + 1 + s K_{11} \gamma - K_{11} \alpha_2 - K_{22}\alpha_2 + 2K_{12}\alpha_2 -s K_{12} \gamma\\& & + y_2v_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 随机数初始化向量权重<math>\alpha_i \,</math>，并计算偏移<math>b</math>
2 初始化误差项<math>E_i \,</math>
3 选取两个向量作为需要调整的点
4 令<math>\alpha_2^{new} = \alpha_2^{old} + \frac{y_2(E_1-E_2)}{K}</math>
5 如果<math>\alpha_2^{new} > V</math>
6     令<math>\alpha_2^{new} = V</math>
7 如果<math>\alpha_2^{new} < U</math>
8     令<math>\alpha_2^{new} = U</math>
9 令<math>\alpha_1^{new} = \alpha_1^{old}+y_1 y_2 (\alpha_2^{old} - \alpha_2^{new})</math>
10 利用更新的<math>\alpha_1^{new}</math>和<math>\alpha_2^{new}</math>修改<math>E_i \,</math>和<math>b</math>的值
11 如果达到终止条件，则停止算法，否则转3
```

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

$$U= \begin{cases} \max{\left\{0, \alpha_2^{old} - \alpha_1^{old}\right\}} & y_1y_2 = -1 \\ \max{\left\{0, \alpha_1^{old} + \alpha_2^{old} - C \right\}} & y_1y_2 = 1 \end{cases}, V= \begin{cases} \min{\left\{C, C + \alpha_2^{old} - \alpha_1^{old}\right\}} & y_1y_2 = -1 \\ \min{\left\{C, \alpha_2^{old} + \alpha_1^{old}\right\}} & y_1y_2 = 1 \end{cases}$$

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

### 優化向量選擇方法

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

$$y_if(\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$

## 基本資料

- 車輛類別：訓練支持向量機的優化演算法
- 時間：O(n³)