支持向量机的SMO算法
1. SVM优化目标函数
优化目标函数表达式为：
其中，是SVM核函数的通用表示方法，如果使用的是线性核函数，也就是两个向量的内积。
函数的解要满足KKT条件的对偶互补条件为：
根据这个KKT条件的对偶互补条件，则有：
由于
我们令
则有
2. SMO算法的基本思想
上面的优化式子比较复杂，里面有m个变量组成的向量α需要在目标函数极小化的时候求出。直接优化是很难的。SMO算法采用了一种启发式的方法。它每次只优化两个变量，将其它变量都视为常数。由于，假如将
固定，那么
之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两个变量的优化问题。
为了后面表示方便，我们定义。
由于都成了常量，所有的常量我们都从目标函数中去除，这样前面的优化目标函数变成了：
3. SMO算法目标函数的优化
为了求解上面含有两个变量的目标优化问题，我们首先分析约束条件，所有的都要满足约束条件，然后在约束条件下求最小。
根据上面的约束条件，又由于
均只能取值为1或者-1, 这样
在[0,C]和[0,C]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说
的关系直线平行于[0,C]和[0,C]形成的盒子的对角线，如下图所示：
由于的关系被限制在盒子里的一条线段上，所以两个变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是
的优化问题。由于我们采用的是启发式的迭代法，假设我们上一轮迭代得到的解是
，假设沿着约束方向
未经剪辑的解是
。本轮迭代完成后的解为
。
由于必须满足上图中的线段约束。假设L和H分别是上图中
所在的线段的边界。那么很显然我们有：L≤
≤H
而对于L和H，我们也有限制条件。如果是上面左图中的情况，则有
如果是上面右图中的情况，则有：
也就是说，假如我们通过求导得到的，则最终的
应该为：
那么如何求出呢？很简单，我们只需要将目标函数对
求偏导数即可。
首先我们整理下我们的目标函数。
为了简化叙述，我们令
其中g(x)就是我们在第一节里面提到的
我们令
这样我们的优化目标函数进一步简化为：
由于，并且
，可以得到用
表示
的式子为：
将上式带入我们的目标优化函数，就可以消除，得到仅仅包含
的式子。
接下来我们终于可以开始求了，现在我们通过求偏导数来得到
。
整理上式有：
将带入上式，则：
上面推导过程中用到了，在第2节我们定义了
，
因此有和
，又因为
和
进行点乘得到的是数值，所以
。
我们终于得到了的表达式：
利用上面讲到的和
的关系式，我们就可以得到新的
了。利用
和
的线性关系，我们也可以得到新的
。
4. SMO算法两个变量的选择
SMO算法需要选择合适的两个变量做迭代，其余的变量做常量来进行优化，那么怎么选择这两个变量呢？
4.1 第一个变量的选择
SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点，要满足的KKT条件我们在第一节已经讲到了：
一般来说，我们首先选择违反这个条件的点。如果这些支持向量都满足KKT条件，再选择违反
和
的点。
4.2 第二个变量的选择
SMO算法称选择第二个变量为内层循环，假设我们在外层循环已经找到了, 第二个变量
的选择标准是让
有足够大的变化。由于
定了的时候，
也就确定了，所以要想
最大，只需要在
为正时，选择最小的
作为
， 在
为负时，选择最大的
作为
，可以将所有的
保存下来加快迭代。
如果内层循环找到的点不能让目标函数有足够的下降， 可以采用遍历支持向量点来作，直到目标函数有足够的下降， 如果所有的支持向量作
都不能让目标函数有足够的下降，可以跳出循环，重新选择
。
4.3 计算阈值b和差值
在每次完成两个变量的优化之后，需要重新计算阈值b。当时，我们有
于是新的为：
计算出为：
可以看到上两式都有，因此可以将
用
表示为：
同样的，如果，那么有：
最终的为：
得到了我们需要更新
:
其中，S是所有支持向量的集合。
好了，SMO算法基本讲完了，我们来归纳一下SMO算法。
5. SMO算法总结
输入是m个样本，其中x为n维特征向量，y为二元输出，值为1或者-1，精度为e。
输出是近似解α
1) 取初值。
2) 按照4.1节的方法选择，接着按照4.2节的方法选择
，求出新的
。
3) 按照下式求出
4) 利用和
的关系求出
5) 按照4.3节的方法计算和
6) 在精度范围内检查是否满足如下的终止条件：
7) 如果满足则结束，返回，否则转到步骤2)。