SMO-序列最小优化

SMO-序列最小最优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题，这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。序列最小最优化算法就是其中一种。

序列最小最优化算法（sequential minimal optimization，SMO）是一种启发式算法，其基本思路：如果所有变量的解都满足此问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
整个SMO算法包括两部分：

• 求解两个变量二次规划的解析方法；
• 选择变量的启发式方法。

在支持向量机中，SMO算法要解决如下的凸二次规划的对偶问题：

$$\begin{align} & \min_{\pmb{\alpha}} \quad \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(\pmb{x}_i, \pmb{x}_j) - \sum_{i=1}^N \alpha_i \nonumber \\ & s.t. \quad \sum_{i=1}^N \alpha_i y_i = 0 \nonumber \\ & \qquad \quad 0 \leq \alpha_i \leq C, \quad i=1,2,\cdots,N \nonumber \end{align}$$

1. 两个变量二次规划的求解问题

假设选择的两个变量是$\alpha_1,\alpha_2$，其他变量$\alpha_i(i=3,4,\cdots,N)$是固定的。于是SMO要解决的对偶问题的子问题可以写成：

$$\begin{align} & \min_{\alpha_1, \alpha_2} \quad W(\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 - (\alpha_1 + \alpha_2) \\ & \qquad \qquad \qquad \qquad + y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i2} \nonumber \\ & s.t. \qquad \alpha_1y_1 + \alpha_2y_2 = - \sum_{i=3}^N y_i \alpha_i = \varsigma \\ & \qquad \qquad 0 \leq \alpha_i \leq C, \quad i=1,2 \end{align}$$

其中，$K_{ij} = K(\pmb{x}_i, \pmb{x}_j), i,j=1,2,\cdots,N$，$\varsigma$为常数，由于目标函数式中不含$\alpha_1$和$\alpha_2$的项为常数，因此省略。
由于只有两个变量$(\alpha_1,\alpha_2)$，约束可以用二维空间中的图形表示：

对偶问题中的不等式约束使得$(\alpha_1,\alpha_2)$在盒子$[0,C] \times [0,C]$内，等式约束使$(\alpha_1,\alpha_2)$在平行于盒子$[0,C] \times [0,C]$的对角线的直线上。因此要求的是目标函数在一条平行于对角线的线段上的最优值。这使得两个变量的最优化问题成为实质上的单变量的最优化问题，我们可以考虑为变量$\alpha_2$的最优化问题。
假设原对偶问题的初始可行解为$\alpha_1^{old}, \alpha_2^{old}$，最优解为$\alpha_1^{new}, \alpha_2^{new}$，并且假设在沿着约束方向未经剪辑时$\alpha_2$的最优解为$\alpha_2^{new,unc}$。
由于$\alpha_2^{new}$需要满足不等式约束，所以其取值范围为

$$L \leq \alpha_2^{new} \leq H$$

其中，$l$与$H$是$\alpha_2^{new}$所在的对角线段端点的界：
如果$y_1 \neq y_2$，则

$$L = \max(0,\alpha_2^{old} - \alpha_1^{old}), \quad H = \min(C, C + \alpha_2^{old} - \alpha_1^{old})$$

如果$y_1 = y_2$，则

$$L = \max(0, \alpha_2^{old} + \alpha_1^{old} - C), \quad H = \min (C,\alpha_2^{old} + \alpha_1^{old})$$

首先求解沿着约束方向未经剪辑即未考虑不等式约束时$\alpha_2$的最优解$\alpha_2^{new,unc}$；然后再求剪辑后$\alpha_2$的解$\alpha_2^{new}$。为了叙述简单，记

$$g(\pmb{x}) = \sum_{i=1}^N \alpha_i y_i K(\pmb{x}_i, \pmb{x}) + b$$

令

$$E_i = g(\pmb{x}_i) - y_i = (\sum_{j=1}^N \alpha_j y_j K(\pmb{x}_j,\pmb{x}_i)+b)-y_i, \quad i=1,2$$

当$i=1,2$时，$E_i$为函数$g(\pmb{x})$对输入$\pmb{x}_i$的预测值与真实输出$y_i$之差。

定理：最优化问题$(1) \sim (3)$沿着约束方向向未经剪辑时的解是

$$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}$$

其中

$$\eta = K_{11} + K_{22} - 2 K_{12} = ||\phi(\pmb{x}_1) - \phi(\pmb{x}_2)||^2$$

$\phi(\pmb{x})$是输入空间到特征空间的映射。
经剪辑后$\alpha_2$的解是

$$\alpha_2^{new} = \begin{cases} H, \qquad \qquad \alpha_2^{new,unc} > H \\ \alpha_2^{new,unc}, \quad L \leq \alpha_2^{new,unc} \leq H \\ L, \qquad \qquad \alpha_2^{new,unc} < L \end{cases}$$

由$\alpha_2$求得$\alpha_1^{new}$是

$$\alpha_1^{new} = \alpha_1^{old} + y_1 y_2 (\alpha_2^{old} - \alpha_2^{new})$$

证明：引进记号

$$v_i = \sum_{j=3}^N \alpha_j y_j K(\pmb{x}_i,\pmb{x}_j) = g(\pmb{x}_i) - \sum_{j=1}^2 \alpha_j y_j K(\pmb{x}_i,\pmb{x}_j) - b, \quad i=1,2$$

目标函数可写成

$$W(\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 - (\alpha_1 + \alpha_2) + y_1 v_1 \alpha_1 + y_2 v_2 \alpha_2$$

由$\alpha_1 y_1 = \varsigma - \alpha_2 y_2$及$y_i^2 = 1$，可将$\alpha_1$表示为

$$\alpha_1 = (\varsigma - y_2 \alpha_2) y_1$$

带入目标函数，得到只是$\alpha_2$的函数的目标函数：

$$\begin{align} W(\alpha_2) = & \frac{1}{2} K_{11} (\varsigma - \alpha_2 y_2)^2 + \frac{1}{2} K_{22} \alpha_2^2 + y_2 K_{12} (\varsigma - \alpha_2 y_2) \alpha_2 - (\varsigma - \alpha_2 y_2) y_1 - \alpha_2 \nonumber \\ & + v1(\varsigma - \alpha_2 y_2) + y_2 v_2 \alpha_2 \nonumber \end{align}$$

对$\alpha_2$求导数

$$\frac{\partial W}{\partial \alpha_2} = K_{11} \alpha_2 + K_{22} \alpha_2 - 2K_{12} \alpha_2 - K_{11} \varsigma y_2 + K_{12} \varsigma y_2 -1 - v_1 y_2 + y_2 v_2$$

令其为0，得到

$$\begin{align} (K_{11}+K_{22}-2K_{12}) \alpha_2 & = y_2(y_2 - y_1 + \varsigma K_{11} - \varsigma K_{12} + v_1 - v_2) \nonumber \\ &= y_2 [y_2 - y_1 + \varsigma K_{11} - \varsigma K_{12} + (g(\pmb{x}_1) - \sum_{j=1}^2 y_j \alpha_j K_{1j} - b) \nonumber \\ & \quad - (g(\pmb{x}_2) - \sum_{j=1}^2 y_j \alpha_j K_{2j} - b)] \nonumber \end{align}$$

将$\varsigma = \alpha_1^{old} y_1 + \alpha_2^{old} y_2$带入，得到

$$\begin{align} (K_{11} + K_{22} - 2K_{12}) \alpha_2^{new,unc} &= y_2((K_{11} + K_{22} - 2K_{12})\alpha_2^{old}y_2 + y_2 - y_1 + g(\pmb{x}_1) - g(\pmb{x}_2)) \nonumber \\ &= (K_{11} + K_{22} - 2K_{12}) + y_2(E_1 - E_2) \nonumber \end{align}$$

将$\eta = K{11} + K{22} - 2K_{12}$代入，得到

$$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}$$

由等式约束得到$\alpha_1^{new}$。

2. 变量的选择方法

SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。

2.1. 第一个变量的选择

SMO称选择第一个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第一个变量。具体地，检验训练样本点$(\pmb{x}_i,y_i)$是否满足KKT条件，即

$$\begin{equation} \alpha_i = 0 \Leftrightarrow y_i g(\pmb{x}_i) \geq 1 \nonumber \\ 0 < \alpha_i < C \Leftrightarrow y_i g(\pmb{x}_i) = 1 \nonumber \\ \alpha_i = C \Leftrightarrow y_i g(\pmb{x}_i) \leq 1 \nonumber \end{equation}$$

其中，$g(\pmb{x}i) = \sum{j=1}^N \alpha_j y_j K(\pmb{x}_i,\pmb{x}_j) + b$。
在检验过程中，外层循环首先遍历所有满足条件$0 < \alpha_i < C$的样本点，即在间隔边界上的支持向量点，检验它们是否满足KKT条件。如果这些样本点都满足KKT条件，那么遍历整个训练集，检验它们是否满足KKT条件。

2.2. 第二个变量的选择

SMO算法称选择第二个变量的过程为内层循环。假设在外层循环中已经找到第一个变量$\alpha_1$，现在要在内层循环中找到第二个变量$\alpha_2$。第二个变量选择的标准是希望能使$\alpha_2$有足够大的变化。
由定理可知，$\alpha_2^{new}$是依赖于$|E_1 - E_2|$的，为了加快计算速度，一种简单的做法是选择$\alpha_2$使其对应的$|E_1 - E_2|$最大。由于$\alpha_1$已经确定，因此$E_1$也确定了。如果$E_1$是正的，那么选择最小的$E_i$作为$E_2$；如果$E_1$是负的，那么选择最大的$E_i$作为$E_2$。为了节省计算时间，可将所有的$E_i$值保存在一个列表中。
在特殊情况下，如果内层循环通过以上方法选择的$\alpha_2$不能使目标函数有足够的下降，那么采用以下启发式规则继续选择$\alpha_2$。遍历在间隔边界上的支持向量点，依次将其对应的向量作为$\alpha_2$试用，直到目标函数有足够的下降。若找不到合适的$\alpha_2$，那么遍历训练数据集；若仍找不到合适的$\alpha_2$，则放弃第一个$\alpha_1$，再通过外层循环寻找另外的$\alpha_1$。

2.3. 计算阈值$b$和差值$E_i$

在每次完成两个变量的优化后，都要重新计算阈值$b$。当$0 < \alpha_1^{new} < C$时，由KKT条件可知：

$$\sum_{i=1}^N \alpha_i y_i K_{i1} + b = y_1$$

于是

$$b_1^{new} = y_1 - \sum_{i=3}^N \alpha_i y_iK_{i1} - \alpha_1^{new} y_1 K_{11} - \alpha_2^{new} y_2 K_{21} \tag{4}$$

由$E_1$的定义式有

$$E_1 = \sum_{i=3}^N \alpha_i y_i K_{i1} + \alpha_1^{old} y_1 K_{11} + \alpha_2^{old} y_2 K_{21} + b^{old} - y_1$$

式$(4)$的前两项可写成：

$$y_1 - \sum_{i=3}^N \alpha_i y_i K_{i1} = - E_1 + \alpha_1^{old} y_1 K_{11} + \alpha_2^{old} y_2 K_{21} + b^{old}$$

带入式$(4)$可得

$$b_1^{new} = - E_1 - y_1 K_{11} (\alpha_1^{new} - \alpha_1^{old}) - y_2 K_{21} (\alpha_2^{new} - \alpha_2^{old}) + b^{old}$$

同样，如果$0<\alpha_2^{new} < C$，那么

$$b_2^{new} = - E_2 - y_1 K_{12} (\alpha_1^{new} - \alpha_1^{old}) - y_2 K_{22} (\alpha_2^{new} - \alpha_2^{old}) + b^{old}$$

如果$\alpha_1^{new}, \alpha_2^{new}$同时满足条件$0<\alpha_i^{new} < C, \quad i=1,2$，那么$b_1^{new} = b_2^{new}$。如果$\alpha_1^{new}, \alpha_2^{new}$是$0$或者$C$，那么$b_1^{new}$和$b_2^{new}$以及它们之间的数都是符合KKT条件的阈值，这时选择它们的中点作为$b^{new}$。
在每次完成两个变量的优化之后，还必须更新对应的$E_i$值，并将它们保存在列表中。$E_i$值的更新要用的$b^{new}$值，以及所有支持向量对应的$\alpha_j$：

$$E_i^{new} = \sum_{S} y_j \alpha_j K(\pmb{x}_i, \pmb{x}_j) + b^{new} - y_i$$

其中，$S$是所有支持向量$\pmb{x}_j$的集合。