支持向量机之SMO算法

前面我们讲到SVM的基本理论，现在就涉及到SVM的实现，这里就不得不提到SMO算法

SMO算法

1996年，John Platt 发布了一个称为SMO的强大算法，用于训练SVM，SMO表示表示序列最小优化(Sequential Minimal Optimization)。Platt的SMO算法是将大优化问题分解成为许多个小优化问题来求解。这些小优化问题往往很容易求解，并且对他们进行顺序求解的结果与将他们作为整体求解的结果完全一致，在结果完全相同的情况下，SMO算法的求解时间短很多。

目标

SMO算法的目标就是求出一些列的 $α$ 和 $b$ ，一旦求出了这些 $α$ ，就很容易求出权值向量 $w$ ，并且得到分割超平面

SMO算法的具体做法

SMO的算法原理：每次循环中选择两个 $α$ 进行优化。一旦找到一対合适的 $α$ 就增大其中一个同时减小另外一个。“合适”指的是这两个 $α$ 必须在间隔边界之外，并且没有进行过区间化或者不在边界上。

数学推导

前面我们得到了一个对偶问题：

W (α) = m i n \sum_{i = 1}^{N} \sum_{j = 1}^{N} a_{i} a_{j} y_{i} y_{j} x_{i} x_{j} - \sum_{i = 1}^{N} a_{i}

s . t \sum_{i = 1}^{N} a_{i} y_{i} = 0, i = 1, 2, 3... N

0 \leq a_{i} \leq C, i = 1, 2, 3... N

我们现在要解决的问题是在参数

(a_{1}, a_{2}, a_{3} . . . . a_{n})

上面求

W

的最大值的问题，

x_{i}, y_{i}

都是已知，而

C

是我们预先设定的，所以也是已知数、
我们按照坐标上升的思路，一次性选择两个参数

α_{1}

和

α_{2}

，将其他参数固定，这时

α_{2}

可以用

α_{1}

表示出来，这样代回到

W

中，

W

就是关于

α_{1}

的函数，这样我们就可以求解。

主要步骤

SMO算法的主要步骤：
第一步选取一对 $α_{i}$ 和 $α_{j}$ ，选取方法使用启发式方法。第二步，固定除 $α_{i}$ 和 $α_{j}$ 之外的其他参数，确定W极值条件下的 $α_{i}$ ， $α_{j}$ 由 $α_{i}$ 表示。

具体做法

假设我们选取的初始值 $(α_{1}, α_{2}, α_{3} . . . . α_{n})$ 满足前面我们所提到的约束条件，我们固定 $(α_{3}, α_{4}, α_{5} . . . . α_{n})$ 的值
这样 $W$ 就是 $α_{1}$ 和 $α_{2}$ 的函数，并且 $α_{1}$ 和 $α_{2}$ 满足：

a_{1} y_{1} + a_{2} y_{2} = - \sum_{i = 3}^{N} a_{i} y_{i} (1)

由于我们将其他值设定成了固定值，所以可以设等式右边为常数

ζ

所以有

a_{1} y_{1} + a_{2} y_{2} = ζ (2)

如果

y_{1} 和 y_{2}

是异号，我们设

y_{1} = 1, y_{2} == - 1

，因此

a_{1} - a_{2} = ζ

函数如图所示

由于

α_{1}

和

α_{2}

的关系被限定在矩阵里面的直线上，所以有我们设H和L分别表示

a_{2}

的上界和下界，所以有两个变量的优化问题实际上变成了一个变量的优化问题。我们不妨假设最终是

α_{2}

的优化问题，由于我们上一轮采用的是启发式的迭代法，我们上一轮得到的是

α_{1}^{o l d}, α_{2}^{o l d}

，假设沿着

α_{2}

方向我们得到未剪辑的

α_{2}^{n e w}

。本轮迭代完成之后我们的带的解为

α_{1}^{n e w}

和

α_{2}^{n e w}

，并且所有的

α_{2}

满足

L \leq α_{2} \leq H (3)

根据前面的公式(2)我们有:

α_{1}^{n e w} + α_{2}^{n e w} = α_{1}^{o l d} + α_{2}^{o l d} = ζ (4)

根据上面的直线
若

ζ > 0

，则有

α_{2}^{n e w} \in [0, C - ζ]

若

ζ < 0

，则有

α_{2}^{n e w} \in [- ζ, C]

所以

L = m a x (0, - ζ) (5.1)

H = m i n (C - ζ, C) (5.2)

同理如果

y_{1} 与 y_{2}

是同号，

a_{1} + a_{2} = ζ

，则有：

L = m a x (0, ζ - C) (5.3)

H = m i n (ζ, C) (5.4)

所以我们通过求导所得到的

α_{2}^{n e w}

的结果最终为：

α_{2}^{n e w} = {\begin{aligned} H & α_{2}^{n e w} > H \\ α_{2}^{n e w} & L < α_{2}^{n e w} < H \\ L & α_{2}^{n e w} < L \end{aligned}

接下来我们开始求

α_{2}^{n e w}

的值，具体做法就是将目标函数对

α_{2}

求偏导
首先整理我们的目标函数：
设

α^{*} = {α_{1}^{*}, α_{2}^{*} . . ., α_{n}^{*}}

是对偶问题的最优解。
设函数

f (x^{*}) = \sum_{i = 1}^{N} a_{i}^{*} y_{i} K (x_{i}, x) + b (6)

所以有误差Ei为：

E i = f (x_{i}) - y_{i} = \sum_{j = 1}^{N} a_{i}^{*} y_{i} K (x_{i}, x_{j}) + b - y_{i} (7)

我们定

K_{i, j}

表示为

K (x_{i}, x_{j}) = ϕ (x_{i}) ϕ (x_{j})

所以原来的对偶问题又可以被我们写成关于 $α_{1} 和 α_{2}$ 的函数

W (α_{i}, α_{2}) = m i n \frac{1}{2} K_{11} α_{1}^{2} + \frac{1}{2} K_{22} α_{2}^{2} + y_{1} y_{2} a α_{1} α_{2} - (α_{1} + α_{2}) + y_{1} α_{1} \sum_{i = 3}^{N} α_{i} y_{i} K_{i 1} + α_{2} y_{2} \sum_{i = 3}^{N} α_{i} y_{i} K_{i 2} - \sum_{i = 3}^{N} α_{i} + \sum_{i = 3}^{N} \sum_{j = 3}^{N} α_{i} α_{j} y_{i} y_{j} K_{i j} (8)

s . t α_{1} y_{1} + α_{2} y_{2} = - \sum_{i = 3}^{N} α_{i} y_{i} = ζ

0 \leq α_{i} \leq C, i = 1, 2

由于其他数都是常数：
定义一个常量

ψ

ψ = \sum_{i = 3}^{N} \sum_{j = 3}^{N} α_{i} α_{j} y_{i} y_{j} K_{i j} - \sum_{i = 3}^{N} α_{i}

所以可以将式(8)化简得：

W (α_{1}, α_{2}) = \frac{1}{2} α_{1}^{2} K_{11} + \frac{1}{2} α_{2}^{2} K_{22} + α_{1} α_{2} y_{1} y_{2} K_{12} - (α_{1} + α_{2}) + y_{1} α_{1} \sum_{i = 3}^{N} α_{i} y_{i} K_{i 1} + y_{2} α_{2} \sum_{i = 3}^{N} α_{i} y_{i} K_{i 2} + ψ (9)

引进标记

v_{i}

，根据公式(6)

v_{i} = \sum_{j = 3}^{N} α_{j} y_{j} K_{i j} = f (x_{i}) - \sum_{j = 1}^{2} a_{j} y_{j} K i j - b (10)

由此我们可以将式子(9)简化成:

W (α_{1}, α_{2}) = \frac{1}{2} α_{1}^{2} K_{11} + \frac{1}{2} α_{2}^{2} K_{22} + α_{1} α_{2} y_{1} y_{2} K_{12} - (α_{1} + α_{2}) + y_{1} α_{1} v_{1} + y_{2} α_{2} v_{2} + ψ (11)

有前面我们的假设可以得到 $α_{1} y_{1} + α_{2} y_{2} = ζ$ 并且有 $y_{i}^{2} = 1$ ，因此我们可以得到

α_{1} = y_{1} (ζ - α_{2} y_{2}) (12)

所以现在我们可以将函数化成与

α_{2}

有关的函数：

W (α_{2}) = \frac{1}{2} K_{11} (ζ - α_{2} y_{2})^{2} + \frac{1}{2} K_{22} α_{2}^{2} + α_{2} y_{2} K_{12} (ζ - α_{2} y_{2}) - y_{1} (ζ - α_{2} y_{2}) - α_{2} + (ζ - α_{2} y_{2}) v_{1} + α_{2} y_{2} v_{2}

化简：
然后我们将函数

W

对

α_{2}

求偏导

\frac{\partial W}{\partial α_{2}} = K_{11} α_{2} + K_{22} α_{2} - 2 K_{12} a_{2} + y_{1} y_{2} - 1 + y_{2} v_{2} - y_{1} v_{2} - K_{11} ζ y_{2} + K_{12} ζ y_{2} = 0

(K_{11} + K_{22} - 2 K_{12}) α_{2} = y_{2} (v 1 - v 2 + y_{2} - y_{1} + K_{11} ζ - K_{12} ζ)

(K_{11} + K_{22} - 2 K_{12}) α_{2} = y_{2} (y_{2} - y_{1} + ζ K_{11} - ζ K_{12} + v 1 - v 2)

(K_{11} + K_{22} - 2 K_{12}) α_{2} = y_{2} (y_{2} - y_{1} + (α_{1} y_{1} + α_{2} y_{2}) K_{11} - (α_{1} y_{1} + α_{2} y_{2}) K_{12} + (f (x_{1}) - b - \sum_{j = 1}^{2} a_{j} y_{j} K_{j 1}) - (f (x_{2}) - b - \sum_{j = 1}^{2} a_{j} y_{j} K_{j 2}))

(K_{11} + K_{22} - 2 K_{12}) α_{2} = y_{2} ((K_{11} + K_{22} - 2 K_{12}) α_{2} y_{2} + y_{2} - y_{1} + f (x_{1}) - f (x_{2}))

(K_{11} + K_{22} - 2 K_{12}) α_{2} = y_{2} ((K_{11} + K_{22} - 2 K_{12}) α_{2} y_{2} + (f (x_{1}) - y_{1}) - (f (x_{2}) - y_{2}))

(K_{11} + K_{22} - 2 K_{12}) α_{2} = (K_{11} + K_{22} - 2 K_{12}) α_{2} + y_{2} (E_{1} - E_{2})

将

η = K_{11} + K_{22} - 2 K_{12}

带入，则有:

α_{2}^{n e w} = α_{2}^{o l d} + \frac{y_{2} (E_{1} - E_{2})}{η}

此时根据迭代关系是就可以将

α_{1}

求出来

变量选择方法

第一个变量的选择

SMO称选择第一个变量的循环为外循环。外循环再训练样本中选择违反KKT条件最严重的点，将其作为第一个样本点。检验训练样本点是否满足KKT条件：

α_{i} = 0 \Leftrightarrow y_{i} (f (x_{i})) \geq 0

0 \leq α_{i} \leq C \Leftrightarrow y_{i} f (x_{i}) = 1

α_{i} = C \Leftrightarrow y_{i} f (x_{i}) \leq 1

其中

f (x_{i}) = \sum_{j = 1}^{N} α_{j} y_{j} K (x_{i} . x_{j}) + b

第二变量的选择

SMO称选择第二个变量的过称为内层循环。假设已经在外层找到一个变量 $α_{1}$ ，要在内层循环找到变量 $α_{2}$ 。第二个参数的选择标准是希望 $α_{2}$ 有足够大的变化。
而 $α_{2}$ 是依赖于 $| E 1 - E 2 |$ ，所以为了加快计算速度，简单的做法是选择 $α_{2}$ ，使得其对应的 $| E_{1} - E_{2} |$ 最大。在外层循环确定了 $α_{1}$ 的情况下，E1也是确定值，所以如果E1为正数，那么要选取最小的Ei作为E2，如果E1为负数，那么则要选择最大的Ei作为E2

计算阈值b和差值Ei

每次完成两个变量的优化，都要重新计算阈值b， $0 \leq a_{1}^{n e w} \leq C$

\sum_{i = 1}^{N} a_{i} y_{i} K_{i 1} + b = y_{1}

所以有

b_{1}^{n e w} = y_{1} - \sum_{i = 3}^{N} a_{i} y_{i} K_{i 1} - a_{1}^{n e w} y_{1} K_{11} - a_{2}^{n e w} y_{2} K_{21}

根据Ei的定义有

E_{1} = \sum_{i = 3}^{N} a_{i} y_{i} K_{i 1} + b^{o l d} + a_{1}^{o l d} y_{1} K_{11} + a_{2}^{o l d} y_{2} K_{21} - y_{1}

所以有

b_{1}^{n e w} = - E_{1} - y_{1} K_{11} (a_{1}^{n e w} - a_{1}^{o l d}) - y_{2} K_{22} (a_{2}^{n e w} - a_{2}^{o l d}) + b^{o l d}

更新完b之后还有更新Ei

E_{i}^{n e w} = \sum_{s} y_{j} a_{j} K (x_{i}, x_{j}) + b^{o l d} - y_{i}

SMO的代码实现

SVM原理大致介绍完毕，通过近10天的痛苦的学习，对于SVM里面的数学思想基本上有了一个大致的认识，不过依然存在很多不理解的地方，这一段时间的学习有点痛苦，但是好在收获也不少。分享以前看过的一句话共勉：越是觉得痛苦的时候越是成长得最快的时候。

参考资料

李航《统计学习方法》
机器学习实战
Sequential Minimal Optimization论文
Jerrylead的博客
pinard的博客
pluskid的博客