SVM-3

SMO(Sequential minimal optimization)序列最小化

前面章节中，我们使用了核函数的软间隔支持向量机的优化模型为：

$\begin{align*} & \max_{\alpha} \sum_{i=1}^m\alpha^{(i)} - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha^{(i)} \alpha^{(j)} y^{(i)} y^{(j)} \kappa(x^{(i)}, x^{(j)}) \\ \mbox{s.t.} \quad & \sum_{i=1}^m \alpha^{(i)} y^{(i)} = 0, \\ & 0 \leq \alpha^{(i)} \leq C, \quad i=1,2,3,...,m \end{align*} \tag{1}$

式 (1) 需要满足的 KKT 条件为：

$\begin{equation} \alpha^{(i)}=0\Leftrightarrow y^{(i)}f(x^{(i)})\geq1,\\ 0<\alpha^{(i)}<C\Leftrightarrow y^{(i)}f(x^{(i)})=1,\\ \alpha^{(i)}=C\Leftrightarrow y^{(i)}f(x^{(i)})\leq 1. \end{equation} \tag{2}$

在 SMO（序列最小化）方法出现之前，人们依赖于二次规划求解工具来解决上述的优化问题，训练 SVM。这些工具需要具有强大计算能力的计算机进行支撑，实现也比较复杂。1998 年，微软研究院的 John Platt 提出了 SMO 算法将优化问题分解为容易求解的若干小的优化问题，来训练 SVM。简言之，SMO 仅关注 $ alpha $ 对和偏置 $ b$ 的求解更新，进而求解出权值向量 $ w $ ，得到决策边界（分割超平面），从而大大减少了运算复杂度。

算法介绍

SMO 会选择一对 $\alpha^{(i)}$ 及 $\alpha^{(j)}$ ，并固定住其他参数，即将其他参数认为是常数，则式（1）中的约束条件就可写为：

$\begin{align*} & \alpha^{(i)} y^{(i)} + \alpha^{(j)} y^{(j)} = k, \\ & 0 \leq \alpha^{(i)} \leq C, \\ & 0 \leq \alpha^{(j)} \leq C, \end{align*} \tag{3}$

其中：
$k = -\sum_{k \neq i,j}\alpha^{(k)}y^{(k)} \tag{4}$
那么，式 (1) 的优化问题可以推导：

$\begin{align*} & \max_{\{\alpha^{(i)}, \alpha^{(j)}\}} (\alpha^{(i)} + \alpha^{(j)}) - [\frac{1}{2}K_{ii}(\alpha^{(i)})^2 + \frac{1}{2}K_{jj}(\alpha^{(j)})^2 + y^{(i)}y^{(j)}K_{ij}\alpha^{(i)}\alpha^{(j)}] \\ & \quad - [y^{(i)}\alpha^{(i)}\sum_{k=3}^my^{(k)}\alpha^{(k)}K_{ki} + y^{(j)}\alpha^{(j)}\sum_{k=3}^my^{(k)}\alpha^{(k)}K_{kj}] \\ \mbox{s.t.} \quad & \alpha^{(i)} y^{(i)} + \alpha^{(j)} y^{(j)} = -\sum_{k \neq i,j}\alpha^{(k)}y^{(k)} = k, \\ & 0 \leq \alpha^{(i)} \leq C, 0 \leq \alpha^{(j)} \leq C \\ \end{align*} \tag{5}$