序列最小最优化(SMO)算法

【概述】

序列最小最优化（Sequential Minimal Optimization，SMO）算法，是用于快速求解凸二次规划问题的算法，其主要针对于支持向量机的对偶问题

对于凸优化问题：

$$\begin{matrix} \min\limits_{\mathbf{x}} && f(\mathbf{x}) \\ s.t. && g_i(\mathbf{x})\leq 0 ,&& i=1,2,\cdots,k \\ && h_i(\mathbf{x}) = 0, && i=1,2,\cdots,l \end{matrix}$$

其中，目标函数 $f(\mathbf{x})$ 和约束函数 $g_i(\mathbf{x})$ 都是 $\mathbb{R}^n$ 上的连续可微的凸函数，约束函数 $h_i(\mathbf{x})$ 是 $\mathbb{R}^n$ 上的仿射函数，即满足 $f(\mathbf{x}) = \mathbf{a}\cdot \mathbf{x} + b$，其中，$\mathbf{a}\in \mathbb{R}^n,b\in \mathbb{R},\mathbf{x}\in \mathbb{R}^{n}$

当目标函数 $f(\mathbf{x})$ 是二次函数且约束函数 $g_i(\mathbf{x})$ 是仿射函数时，上述的凸优化问题即凸二次规划问题（Convex Quadratic Programming）

【SMO 算法的基本思想】

对于容量为 $n$ 的样本集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_n,y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(m)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}=\{-1,+1\}$

SMO 算法要对如下的凸二次规划的对偶问题进行求解：

$$\begin{matrix} \min\limits_{\boldsymbol{\alpha}} && \frac{1}{2} \sum\limits_{i=1}^n \sum\limits_{j=1}^n \alpha_i\alpha_j y_i y_j K (\mathbf{x}_i,\mathbf{x}_j) - \sum\limits_{i=1}^n \alpha_i \\ s.t. && \sum\limits_{i=1}^n\alpha_i y_i= 0 \\ && 0\leq \alpha_i \leq C ,\quad i=1,2,\cdots,n \end{matrix}$$

其中，$\boldsymbol{\alpha}=(\alpha_1,\alpha_2,\cdots,\alpha_n)^T$ 为拉格朗日乘子向量，一个变量 $\alpha_i$ 对应于一个样本点 $(\mathbf{x}_i,y_i)$

SMO 算法是一种启发式算法，其基本思路是：

若所有变量的解均满足最优化问题的 KKT 条件，由于 KKT 条件是最优化问题的充分必要条件，那么这个最优化问题的解就得到了

否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划子问题，并进行解析求解，直到所有变量满足 KKT 条件为止

由于构建的二次规划子问题会使得原始二次规划问题的目标函数值更小，因此关于这两个变量的解会更接近原始二次规划问题的解

对于选择的两个变量，一个是违反 KKT 条件最严重的那个，另一个是由约束条件自动确定的，假设 $\alpha_1$ 和 $\alpha_2$ 是选择的两个变量，$\alpha_3,\alpha_4,\cdots,\alpha_n$ 固定，那么通过上述的凸二次规划的对偶问题的等式约束 $\sum\limits_{i=1}^n\alpha_i y_i=0$，可得：

$$\alpha_1 = -y_1\sum_{i=2}^n \alpha_i y_i$$

如此一来，如果 $\alpha_2$ 确定，那么 $\alpha_1$ 也随之确定，因此，可以将原问题不断分解为子问题，并对子问题进行求解时同时更新两个变量，直到得到子问题的解，进而达到求解原问题的目的

综上所述，整个 SMO 算法包括两个部分：求解两个变量二次规划的解析方法、选择变量的启发式方法

注：关于 KKT 条件，详见 拉格朗日乘子法与对偶性

【两个变量二次规划的求解方法】

最优化问题的子问题

假设选择的两个变量是 $\alpha_1$ 和 $\alpha_2$，固定其他变量 $\alpha_i,i=3,4,\cdots,n$

于是，SMO 的最优化问题的子问题的优化目标函数可写为：

$$\begin{align*} W(\alpha_1,\alpha_2) =& \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha_1+\alpha_2) \\ &+ y_1\alpha_1\sum\limits_{i=3}^n y_i\alpha_iK_{i1} + y_2\alpha_2\sum\limits_{i=3}^n y_i\alpha_iK_{i2} \end{align*}$$

故，SMO 的最优化问题的子问题为：

$$\begin{matrix} \min\limits_{\alpha_1,\alpha_2} && W(\alpha_1,\alpha_2) \\ s.t. && \alpha_1y_1 + \alpha_2y_2 = -\sum\limits_{i=3}^n y_i\alpha_i = \varsigma \\ && 0\leq \alpha_i \leq C ,\quad i=1,2 \end{matrix}$$

其中，$K_{ij} = K(\mathbf{x}_i,\mathbf{x}_j)$，$\varsigma$ 为常数，同时，最优化目标函数式中省略了不含 $\alpha_1,\alpha_2$ 的常数项

约束条件的分析

为求解上述的两个变量的二次规划子问题，首先分析约束条件，然后在该约束条件下求极小

由于只有两个变量 $\alpha_1,\alpha_2$，约束条件可以用二维空间中的图形来表示

对于不等式约束 $0\leq \alpha_i \leq C$，其使得 $\alpha_1,\alpha_2$ 在 $[0,C]\times[0,C]$ 内，对于等式约束 $\alpha_1y_1 + \alpha_2y_2 = -\sum\limits_{i=3}^n y_i\alpha_i = \varsigma$，其使得 $\alpha_1,\alpha_2$ 在平行于 $[0,C]\times[0,C]$ 的对角线的直线上

因此，要求的实际上是目标函数在一条平行于对角线的线段上的最优值，这使得对这两个变量的最优化问题成为了单变量的优化问题

单变量的最优化问题

不妨将上述的单变量优化问题假设为对变量 $\alpha_2$ 的最优化问题，同时，假设二次规划子问题的初始可行解为 $\alpha_1^{\text{old}}$ 和 $\alpha_2^{\text{old}}$，最优解为 $\alpha_1^{\text{new}}$ 和 $\alpha_2^{\text{new}}$，并且假设在沿着约束方向未经剪辑时 $\alpha_2$ 的最优解为 $\alpha_2^{\text{new,unc}}$

由于最优解 $\alpha_2^{\text{new}}$ 需要满足不等式约束 $0\leq \alpha_i \leq C$，因此最优解 $\alpha_2^{\text{new}}$ 的取值范围要满足：

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

其中，$L$ 与 $H$ 是 $\alpha_2^{\text{new}}$ 所在的对角线端点的界

若 $y_1\neq y_2$，则：

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

若 $y_1 = y_2$，则：

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

最优化问题子问题的解

记：

$$g(\mathbf{x}) = \sum_{i=1}^n \alpha_i y_i K(\mathbf{x}_i,\mathbf{x}) +\theta$$

那么，有：

$$\begin{align*} v_i &= \sum_{j=3}^n \alpha_j y_j K_{ij} \\ &= g(\mathbf{x}_i) - \sum_{j=1}^2 \alpha_j y_j K_{ij} -\theta,\quad i=1,2 \end{align*}$$

于是，优化的目标函数可写为：

$$\begin{align*} W(\alpha_1,\alpha_2) =& \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha_1+\alpha_2) \\ &+ y_1\alpha_1\sum\limits_{i=3}^n y_i\alpha_iK_{i1} + y_2\alpha_2\sum\limits_{i=3}^n y_i\alpha_iK_{i2} \\ =& \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha_1+\alpha_2) \\ &+ y_1\alpha_1v_1 + y_2\alpha_2v_2 \end{align*}$$

根据等式条件约束 $\alpha_1y_1 + \alpha_2y_2 = \varsigma$ 与 $y_i^2= 1$ 有：

$$\alpha_1 = \frac{1}{y_1}(\varsigma -\alpha_2 y_2)=y_1(\varsigma -\alpha_2 y_2)$$

将其带回目标函数 $W(\alpha_1,\alpha_2)$，可得只是 $\alpha_2$ 的函数的目标函数，即：

$$\begin{align*} W(\alpha_2) =& \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha_1+\alpha_2) \\ &+ y_1\alpha_1v_1 + y_2\alpha_2v_2 \\ =& \frac{1}{2}K_{11}(\varsigma -\alpha_2 y_2)^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_2K_{12}(\varsigma -\alpha_2 y_2)\alpha_2 \\ &- (\varsigma -\alpha_2 y_2)y_1 -\alpha_2 + (\varsigma -\alpha_2 y_2)v_1 + y_2\alpha_2v_2 \end{align*}$$

对 $W(\alpha_2)$ 求关于 $\alpha_2$ 的偏导数，有：

$$\begin{align*} \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 + y_1y_2 -1 - v_1y_2+v_2y_2 \end{align*}$$

令 $\frac{\partial W}{\partial{\alpha_2}}=0$，有：

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

令：

$$E_i = g(\mathbf{x}_i)-y_i = \big(\sum_{j=1}^n \alpha_j y_j K_{ji}+\theta\big)-y_i ,\quad i=1,2$$

为函数 $g(\mathbf{x})$ 对输入 $\mathbf{x}_i$ 的预测值与真实输入 $y_i$ 的差，并将 $\varsigma = \alpha_1^{\text{old}}y_1 + \alpha_2^{\text{old}}y_2$ 带入，则有：

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

令 $\eta = K_{11}+K_{22}-2K_{12}$，则有：

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

即沿着约束方向未经剪辑的 $\alpha_2$ 的解，也就是不考虑不等式约束 $0\leq \alpha_i \leq C$ 的最优解 $\alpha_2^{\text{new,unc}}$

那么，经剪辑后 $\alpha_2$ 的解为：

$$\alpha_2^{\text{new}} = \left\{ \begin{align*} H, && \alpha_2^{\text{new,unc}}>H \\ \alpha_2^{\text{new,unc}}, && L\leq \alpha_2^{\text{new,unc}} \leq H\\ L, && \alpha_2^{\text{new,unc}}<L \end{align*} \right.$$

进而，根据等式约束 $\alpha_1y_1 + \alpha_2y_2 = \varsigma$ 可得 $\alpha_1^{\text{new}}$ 为：

$$\alpha_1^{\text{new}} = \alpha_1^{\text{old}} + y_1y_2(\alpha_2^{\text{old}}-\alpha_2^{\text{new}})$$

于是，对于 SMO 的最优化问题子问题的解为 $(\alpha_1^{\text{new}},\alpha_2^{\text{new}})$

【变量的选择方法】

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

外层循环

SMO 称选择第一个变量的过程为外层循环，其在训练样本中选择违反 KKT 条件最严重的样本点，并将其对应的变量作为第一个变量

具体来说，会检验样本点 $(\mathbf{x}_i,y_i)$ 是否满足 KKT 条件，即：

$$\begin{gather*} \alpha_i = 0 \Leftrightarrow y_ig_i(\mathbf{x}_i) \geq 1 \\ 0 < \alpha_i < C \Leftrightarrow y_ig_i(\mathbf{x}_i) = 1 \\ \alpha_i = C \Leftrightarrow y_ig_i(\mathbf{x}_i) \leq 1 \\ \end{gather*}$$

其中，$g(\mathbf{x}_i) = \sum\limits_{j=1}^n \alpha_j y_j K_{ij} +\theta$

该检验是在 $\varepsilon$ 范围内进行的，在检验过程中，外层循环首先遍历所有满足条件 $0\leq \alpha_i <C$ 的样本点，即间隔边界上的支持向量点，经检查它们是否满足 KKT 条件

若间隔边界上的样本点均满足 KKT 条件，那么继而会遍历整个训练集，检验它们是否满足 KKT 条件

内层循环

SMO 称选择第二个变量的过程为内层循环，假设在外层循环已经找到第一个变量 $\alpha_1$，要在内存循环中寻找到第二个变量 $\alpha_2$，其选择的标准是希望能够使 $\alpha_2$ 有足够大的变化

根据 $\alpha_2$ 沿着约束方向未经剪辑时的解：

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

以及经过剪辑后 $\alpha_2$ 的解：

$$\alpha_2^{\text{new}} = \left\{ \begin{align*} H, && \alpha_2^{\text{new,unc}}>H \\ \alpha_2^{\text{new,unc}}, && L\leq \alpha_2^{\text{new,unc}} \leq H\\ L, && \alpha_2^{\text{new,unc}}<L \end{align*} \right.$$

可知，$\alpha_2^{\text{new}}$ 是依赖于 $|E_1-E_2|$ 的，为加快计算速度，一种简单的方式是选择使其对应的 $|E_1-E_2|$ 最大的 $\alpha_2$，也就是说，由于 $\alpha_1$ 已经确定，那么 $E_1$ 就确定了，如果 $E_1$ 是正的，那么就选择最小的 $E_i$ 作为 $E_2$，如果 $E_1$ 是负的，那么就选择最大的 $E_i$ 作为 $E_2$

特殊情况下，如果内层循环通过以上方法选择的 $\alpha_2$ 不能使目标函数有足够的下降，那么可以采用如下的启发式规则来继续选择 $\alpha_2$：

1. 遍历间隔边界上的支持向量点，依次将其对应的变量作为 $\alpha_2$ 试用，直到目标函数有足够的下降
2. 若找不到合适的 $\alpha_2$，那么就遍历整个训练集
3. 若仍找不到合适的 $\alpha_2$，那么就放弃第一个 $\alpha_1$，再通过外层循环寻求另外的 $\alpha_1$

阈值与差值的计算

在每次完成两个变量的优化后，都要重新计算阈值 $\theta$

当 $0<\alpha_1^{\text{new}}<C$ 时，由 KKT 条件 $0 < \alpha_i < C \Leftrightarrow y_ig_i(\mathbf{x}_i) = 1$ 可知：

$$\sum_{i=1}^n \alpha_i y_i K_{i1} +\theta = y_1$$

于是，有：

$$\theta_1^{\text{new}} = y_1 - \sum_{i=3}^n \alpha_i y_i K_{i1} - \alpha_1^{\text{new}} y_1 K_{11} - \alpha_2^{\text{new}}y_2 K_{21}$$

根据 $E_1$ 的定义式 $E_1 = \big(\sum\limits_{j=1}^n \alpha_j y_j K_{j1}+\theta\big)-y_1$，有：

$$E_1 = \sum_{i=3}^n \alpha_i y_i K_{i1} + \alpha_1^{\text{old}} y_1 K_{11} + \alpha_2^{\text{old}}y_2K_{21}+\theta^{\text{old}}-y_1$$

于是，对于 $\theta_1^{\text{new}}$ 的前两项，有：

$$y_1 - \sum_{i=3}^n \alpha_i y_i K_{i1} = -E_1 + \alpha_1^{\text{old}} y_1 K_{11} + \alpha_2^{\text{old}}y_2K_{21} + \theta^{\text{old}}$$

带回 $\theta_1^{\text{new}}$，有：

$$\theta_1^{\text{new}} = -E_1 - y_1K_{11}(\alpha_1^{\text{new}}-\alpha_1^{\text{old}})-y_2K_{21}(\alpha_2^{\text{new}}-\alpha_2^{\text{old}}) + \theta^{\text{old}}$$

同理，若 $0<\alpha_2^{\text{new}}<C$，那么有：

$$\theta_2^{\text{new}} = -E_2 - y_1K_{12}(\alpha_1^{\text{new}}-\alpha_1^{\text{old}})-y_2K_{22}(\alpha_2^{\text{new}}-\alpha_2^{\text{old}}) + \theta^{\text{old}}$$

如果 $\alpha_1^{\text{new}}$ 和 $\alpha_2^{\text{new}}$ 同时满足条件 $0<\alpha_i^{\text{new}}<C,i=1,2$，那么

$$\theta_1^{\text{new}} = \theta_2^{\text{new}}$$

如果 $\alpha_1^{\text{new}}$ 和 $\alpha_2^{\text{new}}$ 都是 $0$ 或都是 $C$，那么 $\theta_1^{\text{new}}$ 和 $\theta_2^{\text{new}}$ 以及它们之间的数都是满足 KKT 条件的阈值，此时选择它们的中点作为 $\theta^{\text{new}}$，即：

$$\theta^{\text{new}} = \frac{1}{2}(\theta_1^{\text{new}}+\theta_2^{\text{new}})$$

此外，在每次完成两个变量的优化后，还需更新对应的差值 $E_i$，并将它们保存在一个列表中，以便能够快速的完成内层循环

$E_i$ 的更新需要用到 $\theta^{\text{new}}$ 值，以及所有支持向量对应的 $\alpha_j$，即：

$$E_i^{\text{new}} = \sum_{\mathbf{x}_j\in S} y_j \alpha_j K_{ij} + \theta^{\text{new}} -y_i$$

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

【SMO 算法流程】

下面给出 SMO 算法的算法流程

输入：对于容量为 $n$ 的样本集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_n,y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(m)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}=\{-1,+1\}$，精度 $\varepsilon$

输出：凸二次规划的对偶问题的近似解 $\hat{\boldsymbol{\alpha}}$

算法步骤：

Step1：取初值 $\boldsymbol{\alpha}^{(0)}$，并令 $k=0$

Step2：选择优化变量 $\alpha_1^{(k)}$ 与 $\alpha_2^{(k)}$，计算 SMO 的最优化问题的子问题的优化目标函数：

$$\begin{align*} W(\alpha_1,\alpha_2) =& \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 -(\alpha_1+\alpha_2) \\ &+ y_1\alpha_1\sum\limits_{i=3}^n y_i\alpha_iK_{i1} + y_2\alpha_2\sum\limits_{i=3}^n y_i\alpha_iK_{i2} \end{align*}$$

并解析求解两根变量的最优化问题：

$$\begin{matrix} \min\limits_{\alpha_1,\alpha_2} && W(\alpha_1,\alpha_2) \\ s.t. && \alpha_1y_1 + \alpha_2y_2 = -\sum\limits_{i=3}^n y_i\alpha_i = \varsigma \\ && 0\leq \alpha_i \leq C ,\quad i=1,2 \end{matrix}$$

求得最优解 $\alpha_1^{(k+1)},\alpha_2^{(k+1)}$，并将 $\boldsymbol{\alpha}$ 更新为 $\boldsymbol{\alpha}^{(k+1)}$

Step3：若在精度 $\varepsilon$ 范围内，满足停机条件

$$\begin{gather*} \sum_{i=1}^n \alpha_i y_i = 0 \\ 0\leq \alpha_i \leq C, & i=1,2,\cdots,n \\ y_i\cdot g(\mathbf{x}_i) = \left\{\begin{array}{rl} \geq 1, & \{\mathbf{x}_i | \alpha_i = 0\} \\ =1, & \{\mathbf{x}_i | 0<\alpha_i<C \} \\ \leq 1, & \{\mathbf{x}_i|\alpha_i =C\} \end{array}\right. \end{gather*}$$

其中，$g(\mathbf{x}_i) = \sum\limits_{j=1}^n \alpha_j y_j K_{ji} +\theta$

则转 Step4，否则，令 $k=k+1$，转 Step2

Step4：令 $\hat{\boldsymbol{\alpha}}=\boldsymbol{\alpha}^{(k+1)}$