SMO算法

参考资料: 吴恩达CS229 机器学习

1.Coordinate ascent

为解决SVM的对偶问题，John Platt提出了SMO(顺序最小优化)算法。为了引出SMO算法，让我们先讨论coordinate ascent algorithm（坐标上升算法）。

我们已经学过两种优化算法，gradient ascent和Newton’ method。我们现在学习的新算法叫做coordinate ascent。考虑一个无约束优化问题：

$$\max _{\alpha} W\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{m}\right)$$

Loop until convergence: {
    For i = 1,...,m, {
        αi := argmax_{αˆi} W(α1,...,αi−1,αˆi,αi+1,...,αm).
    }
}

最内层的循环每次只更新一个参数，来最大化 $W\left(\alpha{1}, \alpha{2}, \ldots, \alpha_{m}\right)$ ，不停循环，直到收敛。
coordinate ascent的实际运行效果如图所示：

2. SMO

在支持向量机的课程中，加入 $\ell_{1} \text{ norm regularization} $ 后的dual optimization problem为：

$$\begin{aligned} \max _{\alpha} \quad& W(\alpha)=\sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{m} y^{(i)} y^{(j)} \alpha_{i} \alpha_{j}\left\langle x^{(i)}, x^{(j)}\right\rangle . \\ \text { s.t. } \quad & 0 \leq \alpha_{i} \leq C, \quad i=1, \ldots, m \\ & \sum_{i=1}^{m} \alpha_{i} y^{(i)}=0 \end{aligned}$$

由于约束 $\sum{i=1}^{m} \alpha{i} y^{(i)}=0$ 的存在，让我们以优化 $\alpha_{1}$ 为例。因为，

$$\alpha_{1} y^{(1)}=-\sum_{i=2}^{m} \alpha_{i} y^{(i)}$$

等式两边同时乘以 $y^{(1)}$ ，因为 $y^{(1)} \in{-1,1}, \Rightarrow \left(y^{(1)}\right)^{2}=1$

$$\alpha_{1}=-y^{(1)} \sum_{i=2}^{m} \alpha_{i} y^{(i)}$$

所以，如果保持 $\alpha{2}, \ldots, \alpha{m}$ 不变， $\alpha{1}$ 是不可能变动的。所以我们只能同时更新至少两个变量，才能满足约束条件 $\sum{i=1}^{m} \alpha_{i} y^{(i)}=0$ 。这就是SMO算法：

Repeat till convergence {
    1. Select some pair αi and αj to update next (using a heuristic that tries to
       pick the two that will allow us to make the biggest progress towards the 
       global maximum).
    2. Reoptimize W(α) with respect to αi and αj, while holding all the other αk’s
       (k != i, j) fixed.
}

SMO sequential minimal optimization，minimal代表什么含义呢？就是在一次更新中，选择最小数量的参数 $\alpha_{i}$ 去更新。

让我们先以更新 $\alpha{1},\alpha{2}$ 为例，保持 $\alpha{3}, \ldots, \alpha{m}$ 不变。根据约束 $\sum{i=1}^{m} \alpha{i} y^{(i)}=0$ 。我们有：

$$\alpha_{1} y^{(1)}+\alpha_{2} y^{(2)}=-\sum_{i=3}^{m} \alpha_{i} y^{(i)}=\zeta$$

上式等式右手边是常数 $\zeta$ ，因为 $\alpha{3}, \ldots, \alpha{m}$ 不变。

根据加入 $\ell{1} \text{ norm regularization} $ KKT对偶条件 $0 \leq \alpha{i} \leq C$ 。以及 $\alpha{1} y^{(1)}+\alpha{2} y^{(2)}=\zeta$

这是一种box constraints， $\alpha{1},\alpha{2}$ 既要在 $[0, C] \times[0, C]$ 这个方形区域内，也要在 $\alpha{1} y^{(1)}+\alpha{2} y^{(2)}=\zeta$ 这条直线上。根据 $\alpha{1} y^{(1)}+\alpha{2} y^{(2)}=\zeta$ ，我们有：

$$\alpha_{1}=\left(\zeta-\alpha_{2} y^{(2)}\right) y^{(1)} \\$$

把这个代入 $W(\alpha)$ ， $W$ 是一个凸函数：

$$W\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{m}\right)=W\left(\left(\zeta-\alpha_{2} y^{(2)}\right) y^{(1)}, \alpha_{2}, \ldots, \alpha_{m}\right)$$

上式是一个关于 $\alpha{2}$ 的一元二次函数： $a \alpha{2}^{2}+b \alpha{2}+c$ 。这就是一个简单的初中就学过的二次函数求极值的问题。求出 $\alpha{2}^{n e w}$ 之后，再代回等式 $\alpha{1}=\left(\zeta-\alpha{2} y^{(2)}\right) y^{(1)}$ 就求出 $\alpha_{1}^{n e w}$ 。