3 SMO算法

对偶问题为

$$\newcommand{\w}{\boldsymbol w} \newcommand{\a}{\boldsymbol \alpha} \newcommand{\x}{\boldsymbol x} \begin{aligned} &\max_\a\left(\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_iy_i\x_i^T\alpha_jy_j\x_j\right)\newline &\text{s.t. }\sum_{i=1}^m\alpha_iy_i=0,\quad \a≽0 \end{aligned}$$

因为原问题有不等式约束，所以要求满足 KKT 条件，即 $$ \begin{aligned} (1)&\alpha_i\ge0\newline (2)&y_if(\x_i)-1\ge 0\newline (3)&\alpha_i[y_if(\x_i)-1]=0 \end{aligned} $$ 其中 $f(\x)=\w^T\x+b$，上面三个式子说明，$\alpha_i$ 对应的样本 $(\x_i,y_i)$ 要么 $\alpha_i=0$，要么 $y_if(\x_i)=1$，说明支持向量机解有稀疏性：训练完成后，大部分的训练样本都不需保留在模型中（$\alpha_i=0$），最终模型仅与支持向量（$y_if(\x_i)=1$）有关。

怎么求解对偶问题？

问题在于问题规模正比于样本数 $m$，使用现成的二次规划算法开销很大，所以需要利用问题本身的特性来解决。

SMO 算法

通过序列最小优化（SMO）求解最优的 $\boldsymbol{\alpha}$

基本思路：不断执行如下两个步骤直至收敛

• 选取一对需更新的变量 $α_i$ 和 $α_j$

• 固定 $α_i$ 和 $α_j$以外的参数，求解上面所说的对偶问题，以更新 $α_i$ 和 $α_j$

即：（记 $\x_i^T\x_j=K_{ij},\quad g(x)$ 是对偶问题 $\max$ 后的函数）

$$g\left(\alpha_i, \alpha_j\right)=\alpha_i+\alpha_j-\frac{1}{2}\left(\alpha_i^2 K_{i i}+\alpha_j^2 K_{j j}+2 \alpha_i \alpha_j y_i y_j K_{i j}+a_i y_i \sum_{k \neq i, j} a_k y_k K_{i k}+\alpha_j y_j \sum_{k \neq i, j} a_k y_k K_{j k}\right)$$

约束条件变为：

$$\alpha_i y_i+\alpha_j y_j=-\sum_{k \neq i, j}^m \alpha_i y_i=\zeta \quad \Rightarrow \quad \alpha_i=\left(\zeta-\alpha_j y_j\right) y_i$$

在两个变量上的优化问题是有闭式解的，不需要调用其他算法。

为什么两个变量就可以？[Osuna et al. 1997] 证明了：若 $α_i$ 和 $α_j$ 有一个违反了 KKT 条件，目标函数就会在迭代后增大。KKT 条件违背的程度越大，则变量更新后可能导致的目标函数值增幅越大。

如何选择这两个变量？第一个变量：选取违背KKT条件程度最大的变量；第二个变量：选取与第一个变量的间隔最大的变量（这是一个启发式，认为这样选取的变量代表的样本与第一个变量代表的样本有很大差异）。

如何确定偏移量 $b$？对于任意的支持向量 $\boldsymbol{x}_i \in S$， 均满足 $\boldsymbol{w}^{\top} \boldsymbol{x}_i+b=y_i$ ，则 $$ b^{\star}=\frac{1}{|S|} \sum_{i \in S}\left(y_i-\boldsymbol{x}_{\boldsymbol{i}}^{\top} \boldsymbol{w}^{\star}\right) $$

本文阅读量