机器学习之SMO算法

2019-03-23 本文已影响16人 Vophan

SMO算法

什么是SMO算法

SMO(Sequential Minmal Optimization)序列最小化算法，是一种对SVM的高效的优化算法。

坐标上升法

在SMO算法之前，还是需要总结下坐标上升算法（Coordinate Ascent），因为SMO算法的思想与坐标上升算法的思想类似。

Content:

坐标上升算法每次通过更新多元函数中的一维，经过多次迭代直到收敛来达到优化函数的目的。简单的讲就是不断地选中一个变量做一维最优化直到函数达到局部最优点。

img

也就是说，每次只对一个维度进行调整，从而使目标函数在这一维度的范围内达到最优（局部）。

举个例子：

如果我们要优化一个二元函数：
$arg minf(x_1, x_2) = -x_1^2-3x_2^2+2x_1x_2+6$
我们先给一个初值 $(x_1, x_2)$ ,然后开始迭代

我们先固定住 $x_1$ , 对 $x_2$ 求偏导，等于零来得到相对最小值：
$$
\frac{\partial f}{\partial x_1} = -2x_1 + 2x_2 = 0\

x_1 = x_2
$$

然后，固定 $x_2$ , 对 $x_1$ 求偏导，等于零：
$\frac{\partial f}{\partial x_2} = -6x_2 + 2x_1 = 0\\ x_2 = \frac{1}{3}x_1$

持续迭代，直至收敛

通过下面的图就可以看出，优化的过程，因为每次只优化一个变量，每次迭代的方向都是沿着坐标轴方向的。

img

因为每次只是做一维优化，所以每个循环中的优化过程的效率是很高的, 但是迭代的次数会比较多。

SMO算法

SMO的思想类似坐标上升算法，我们需要优化一系列的α的值，我们每次选择尽量少的 $\alpha$ 来优化，不断迭代直到函数收敛到最优值。

但是怎么证明他的正确性：

因为最优解一定满足KKT条件，所以，我们只需要让所有的样本都满足KKT条件，我们就一定可以找到最优解.

我们回到SVM的对偶问题上：
$max \sum_{i=1}^N\alpha_i - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Ny_iy_j\alpha_i\alpha_j<x_i,x_j>\\ s.t.\quad \alpha_i\geq0,\sum_{i=1}^N\alpha_iy_i = 0$
看到求和符号，我们知道如果我们要直接优化的话，我们需要优化 $\alpha_1,\alpha_2,\alpha_3...\alpha_n$ ，n个变量，但是我们使用platt提出的SMO算法我们可以高效的求解上面的对偶问题，SMO把N个规划问题分解成多个二次规划算法求解，每个子问题只需要求解两个参数，节省了时间成本。

但是，与坐标上升法不同的是：

我们在SMO算法中我们每次需要选择一对变量 $(\alpha_i, \alpha_j)$ 。而且SVM中我们的 $\alpha$ 并不是独立的，因为具有约束的：
$\sum_{i=1}^N\alpha_iy_i = 0$
所以，一个 $\alpha$ 改变，另一个也要随之变化以满足条件。
$W(\alpha_{1}, \alpha_{2}) = \alpha_{1} + \alpha_{2} - \frac{1}{2}K_{1,1}y_{1}^{2}\alpha_{1}^{2} - \frac{1}{2}K_{2,2}y_{2}^{2}\alpha_{2}^{2} - K_{1,2}y_{1}y_{2}\alpha_{1}\alpha_{2} - y_{1}\alpha_{1}\sum_{i=3}^{N}\alpha_{i}y_{i}K_{i,1} - y_{2}\alpha_{2}\sum_{i=3}^{N}\alpha_{i}y_{i}K_{i, 2} + C$
于是就变成了一个二元函数的优化:
$arg \max \limits_{\alpha_{1}, \alpha_{2}} W(\alpha_{1}, \alpha_{2})$

然后，根据我们之前的约束条件，我们可以将这个二元函数在转换成一元函数：
$s.t.\quad\sum^N_{i=0}y_i\alpha_i = 0\\ \alpha_1y_1+\alpha_2y_2 = -\sum^N_{i=3}y_i\alpha_i = \zeta\\ \alpha_1 = \zeta y_i - \alpha_2y_2\\ W(\alpha_1,\alpha_2) = W(\alpha_2)$
这里为了方便表示，设：
$v_1 = \sum^N_{i=3}\alpha_iy_ik_{i,1}\\ v_2 = \sum^N_{i=3}\alpha_jy_jk_{1,j}$
同时带入，得：
$W(\alpha_{2}) = -\frac{1}{2}K_{1, 1}(\zeta - \alpha_{2}y_{2})^{2} - \frac{1}{2}K_{2, 2}\alpha_{2}^{2} - y_{2}(\zeta - \alpha_{2}y_{2})\alpha_{2}K_{1, 2} - v_{1}(\zeta - \alpha_{2}y_{2}) - v_{2}y_{2}\alpha_{2} + \alpha_{1} + \alpha_{2} + C$
然后，求导，等于0：
$\frac{\partial{W(\alpha_{2})}}{\partial{\alpha_{2}}} = -(K_{1, 1} + K_{2, 2} - 2K_{1, 2})\alpha_{2} + K_{1, 1}\zeta y_{2} - K_{1, 2}\zeta y_{2} + v_{1}y_{2} - v_{2}y_{2} - y_{1}y_{2} + y_{2}^{2} = 0$
变化成迭代形式：
$f(x) = \sum_{i=1}^{N}\alpha_{i}y_{i} K(x_{i}, x) + b\\ v_{1} = \sum_{i=3}^{N}\alpha_{i}y_{i}K_{1, i} = f(x_{1}) - \alpha_{1}y_{1}K_{1, 1} - \alpha_{2}y_{2}K_{1, 2} - b\\ v_{2} = \sum_{i=3}^{N}\alpha_{i}y_{i}K_{2, i} = f(x_{2}) - \alpha_{1}y_{1}K_{1, 2} - \alpha_{2}y_{2}K_{2, 2} - b\\ v_{1} - v_{2} = f(x_{1}) - f(x_{2}) - K_{1, 1}\zeta + K_{1, 2}\zeta + (K_{1, 1} + K_{2, 2} - 2K_{1, 2})\alpha_{2}y_{2}\\ \frac{\partial{W(\alpha_{2})}}{\partial{\alpha_{2}}} = -(K_{1, 1}) + K_{2, 2} - 2K_{1, 2})\alpha_{2}^{new} +(K_{1, 1}) + K_{2, 2} - 2K_{1, 2})\alpha_{2}^{old} + y_{2}\left[ y_{2} - y_{1} + f(x_{1}) - f(x_{2}) \right]\\ E_{i} = f(x_{i}) - y_{i}\\ \eta = K_{1, 1} + K_{2, 2} - 2K_{1, 2}\\ \frac{\partial{W(\alpha_{2})}}{\partial{\alpha_{2}}} = -\eta \alpha_{2}^{new} + \eta \alpha_{2}^{old} + y_{2}(E_{1} - E_{2}) = 0\\ \alpha_{2}^{new} = \alpha_{2}^{old} + \frac{y_{2}(E_{1} - E_{2})}{\eta}$
但是，显然我们没有考虑约束条件，所以：
$s.t.\quad \alpha_{1}y_{1} + \alpha_{2}y_{2} = -\sum_{i=3}^{N}\alpha_{i}y_{i} = \zeta\\ 0\leq a_i\leq C$

img

这个约束条件就是方形约束，这个是SMO论文中的图，但是，我第一次看看的是一脸懵逼。这里，我简单地说一下，然后给大家推荐一个博客

首先，我们知道 $y_i = 1 or -1$ ，所以只有那么几种情况：

$\alpha_1+\alpha_2 = \zeta$
$\alpha_1 - \alpha_2 = \zeta$
$\alpha_1 + \alpha_2 = -\zeta$
$\alpha_1 - \alpha_2 = -\zeta$

然后，根据 $\zeta$ 的大小，我们可以得到最终的可行域：

img

其实，我们不光要考虑可行域，还得考虑二次项系数。

具体的请参考这篇博客：博客

最后，我们还需要更新b的值，为了让 $\alpha_{new}$ 满足KKT条件。

当 $0 < \alpha_1^{new} < C$ 时:
$b_1^{new} = -E_1-y_1K_{11}(\alpha_1^{new} - \alpha_1^{old}) - y_2K_{21}(\alpha_2^{new}-\alpha_2^{old}) + b^{old}$
同理，当 $0 < \alpha_2^{new} < C$ :
$b_2^{new} = -E_2-y_1K_{12}(\alpha_1^{new} - \alpha_1^{old}) - y_2K_{22}(\alpha_2^{new}-\alpha_2^{old}) + b^{old}$
如果同时满足条件 $b_1^{new} = b_2^{new}$ , $b = b_1^{new}$