了解支持向量机（三）SMO算法

在支持向量机模型的求解中，我们用到了SMO算法来求解向量α。那么什么是SMO算法？在讲SMO算法之前，我们需要先了解以下坐标上升法。
1、坐标上升法
假设有优化问题：

W是α向量的函数。利用坐标上升法（当然，求目标函数的最小时即为坐标下降法）求解问题最优的过程如下：

算法的思想为：每次只考虑一个变量进行优化，将其他变量固定。这时整个函数可以看作只关于该变量的函数，可以对其直接求导计算。然后继续求其他分变量的值，整个内循环下来就得到了α的一组值，若该组值满足条件，即为我们求的值，否则继续迭代计算直至收敛。一个示意图如下：

如图为一个二次椭圆曲线的等高线，变量维数为2，初始值在点（2，-2），可见其优化路径为折线式前进，因为算法每次只在一个方向上对函数进行优化。

2、SMO算法
在讲支持向量机求目标函数最优时，通过求解对偶问题转换为求解目标函数对α的极大值，如下：

其中C为惩罚系数，α为要求的变量，每个分量α_i 对应一个样本点(x_i,y_i),变量数为样本点容量N。
可以看到优化问题与上面提到的坐标上升法很相似，参考上面讲到的坐标上升法，我们也可以选择向量α的一个变量，将其他变量固定进行优化。但与上面不同的是，该处优化问题包含了约束条件，
变量必须满足等式约束，所以考虑每次选择两个变量进行优化。
不失一般性，将设选择的两个变量为α_1，α_2，其他变量α_i (i=3,4,…,N)是固定的。
于是优化问题的子问题可以写作：
因为我们选择除α_1，α_2以外的变量固定，故可令，
则约束条件改写为：
其中，y为类标签，值为±1，所以α_1 与α_2可以表示为：
以为例，目标函数的约束域如下：

直线被约束条件0≤α_i≤C约束在了一个C×C的正方形中。
从图中可以看出，最优问题的子问题是求在正方形内的线段上的最优值。这使得两个变量的最优化问题成为了实质上的单变量的最优化问题，不妨设为变量α_2的最优化问题，由不等式约束可得α_2的取值范围：

L,H分别为正方形区域内线段的端点值。
引入符号：
表示对输入x_i的预测值和真实输出y_i之差

φ(x)是输入空间到特征空间的映射。

由条件：

将α_1代入最优子问题的目标函数，得到只包含α_2的函数，对α_2求偏导并令其为0 ，可得的值，

new,unc表示求偏导后还没加取值范围[L,H]时的值，称为未剪辑值。

加上取值范围约束进而得到 的值，再而得到。α_2，α_1 的更新值如下：

其中，new表示更新后的值，old表示更新前的值。
若α值满足停止条件，则α即为我们求的近似解。否则重新扫描选择两个变量继续迭代计算直至满足停止条件。

3、变量的选择
现在的问题就是如何选择两个变量构造最优子问题。SMO采用启发式选择方法选择变量。所谓启发式，即每次选择拉格朗日乘子时，优先选择前面样本系数中满足条件0<α_i < C的
α_i作优化，不考虑约束条件中相等的情况是因为在界上的样例对应的系数α_i 一般都不会改变。
通过启发式搜索找到第一个变量，那么第二个应该如何选取呢？因为要考虑算法的收敛性，第二个变量显然不是随便选的。实际上由Osuna定理，只要选择的两个变量中有一个违背KKT条件，那么目标函数在一步迭代后值就会减小,并且我们希望找到的α_2 在更新后能够有足够大的变化。
由上面 的公式可以看出，其值依赖于，当α_1 确定后E_1也就确定了，因此在给定第一个变量的初始值α_i=0后，对输入样例循环遍历，找出违背KKT条件中使最大的样例点的系数作为α_2。

在特殊情况下，通过以上选择的α_2 不能使目标函数有足够的下降，那么采用以下启发式规则继续选择α_2：
遍历在间隔边界上的支持向量点，依次将其对应的变量作为α_2 试用，直到目标函数有足够的下降。若找不到合适的α_2，那么再遍历训练数据集寻找
若仍未找到，则放弃第一个α_1，重新选择α_1 。

在α_1，α_2 完成一次更新后，还需要对阈值b进行更新，b的更新可以通过KKT约束条件：

计算得出。

以上介绍了SMO算法的思路和大概流程，没有对算法的推导及实现上的细节做详细的介绍，大家有兴趣想要深入了解SMO的话，可以看Andrew ng的支持向量机视频和John C.Platt的《Sequential Minimal Optimization A Fast Algorithm for Trainning Support Vector Machines》。