【分类战车SVM】第六话：SMO算法（像smoke一样简单！）
分类战车SVM
（第六话：SMO算法）
查看本《分类战车SVM》系列的内容：
第一话：开题话
第二话：线性分类
第三话：最大间隔分类器
第四话：拉格朗日对偶问题（原来这么简单！）
第五话：核函数（哦，这太神奇了！）
第六话：SMO算法（像Smoke一样简单！）
附录：用Python做SVM模型
转载请注明来源
我有一双神奇的解题小手，不断的化简——代入——化简——代入，不断的迭代——搜索——迭代——搜索，咦，答案出来了！！！
本集大纲：
1.回顾
2.处理奇葩值
3.SMO算法
1. 回顾
第2-4话中，我们介绍了如何去拟合一个SVM模型，第5话我们假设把这个SVM模型拟合好了，讨论如何去实现它，前几话的逻辑关系如下图所示：
看到上面的图，你已经明白，本集第六话要讲的，就是SVM模型的拟合过程——SMO序列最小优化算法。
2. 处理奇葩值
第五话中，我们说到，有一些无法用线性分类器分开的情况，其解决办法是映射到高维。映射到高维是可以解决，但是计算要复杂了，所以我们又用核函数简化计算。这是第五话的内容。但是，看看下面这个例子，你建不建议用映射的办法？
我勒个去！！！
如果把它当做非线性问题，那么要用下面左图的办法（映射+核函数），但是不是觉得太亏了，就因为一个点，计算量要复杂很多，而且这个点非常有可能是噪音！
因此，在实际建模中，我们应该考虑到这样的情况，允许个别离群点的存在。把心放宽一点，用下图右边的方法去解决。
当然，把心放多宽，那要你自己把握了，万一你是处女座……
那么具体到数学表达上，怎么个容忍法呢？我用下面的对照图来说明：
下面这幅图一步一步不用去推，这么展示有两个目的：一是想要说明，加了松弛变量的推导其实也就多了那么个小尾巴ξ，在最后要使用的那个对偶问题里，也就是对偶变量a多了一个上线C；二是正好让大家也复习一下前面的推导过程，忘记的同学可以对照着翻看一下前面五话。
3. SMO算法
前面我们用那么多篇幅，一步步推导，把要解决的问题打造成如下形式：
为了方便下面的说明，我们给这个问题起个代号吧，就叫“终极问题”和“终极约束”！
现在我们就用SMO序列最小优化算法来解决这个“终极问题”。
还记得梯度上下降法吗？算了还是不把事情搞复杂了，感兴趣的在公众号“数说工作室”（微信号shushuojun）中回复“得到”查看。
这里我们的解决思路，简单来说，就是固定a1以外的所有参数，然后在a1上求极值。
这样可以吗？不可以，因为我们这题多了一个
也就是说，当我固定a1以外的所有参数时，a1的值也就定下来了：
所以固定一个参数是不行的，我们要一次选取两个参数做优化。那么我们选取a1，a2，其他变量ai（i=3,4,…）是固定的。
好了，我们现在开始解，思路如下图：
好了，我们先化简“终极约束”
- 化简“终极约束”
由于我们是固定除了a1，a2所有的参数，因此有：
这里D我们用一个常数表示，是被我们固定了的。我们就可以利用这个来表示a1：
其实，y的取值要么是1，要么是-1，所以上式等价于：
这是我们化简得到的第一个信息。别忘了我们还有，
以上是我们直接得到的两个信息，把这两个信息合并，我们还能进一步缩小参数a1，a2的取值范围：
1. 当y1和y2异号的时候，有
这个时候两个参数a1和a2怎么取值的呢？我们用下面这个图直观的看出来：
此时ai（i=1,2）的取值范围一定是正方形内的紫色线或红色线段。
（1）以a2为例，我们来看一下它的上限：
它的上限要么是点1的C，要么是点2的C-D。这个很明显吧，如果a2<a1，那么上限就是红色线段的点2的C-D，如果a2>a1，那么上限就是紫色线段的点1的C，整理一下（上限用H表示）：
如果a2<a1，H=C-D=C+a2-a1；
如果a2>a1，H=C；
把这两个总和一下，用一个式子表示就是，H=min(C , C+a2-a1)，想一想，是不是这样的？
（2）我们再来看一下a2的下限：
它的下限要么是点3的-D，要么是点4的0。如果a2<a1，那么下限就是红色线段的点4的0，如果a2>a1，那么下限就是紫色线段的点3的-D，整理一下（上限用L表示）：
如果a2<a1，L=0；
如果a2>a1，L=-D=a2-a1；
把这两个总和一下怎么表示？这个时候我建议你把下面的答案盖着，自己写一下，你写出来的一定是——
L=max(0 , a2-a1)
总结起来，当y1和y2异号的时候，有
L=max(0, a2-a1) <= a2 <= H=min(C , C+a2-a1)
2. 当y1和y2同号的时候，有
同与（1）相同的方法，可以推出a2的取值范围是
L=max(0, a2+a1-C) <= a2 <= H=min(C , a1+a2)
这同时也是a1的取值范围，好了，这是我们化简“终极约束”后，得到的三个“究极约束”。
- 化简“终极问题”
复习一下，终极问题是这样的：
现在我们来化简它，我们把a1，a2专门拿出来，给“终极进化”做一个等价变形：
这个式子，不建议推导，知道就好。
我们再接着化简，引用记号：
代入到上式中去，终极问题化简为
=究极问题J(a1,a2)
l “究极约束”代入到“究极问题”中去——解“究极问题”
我们首先将“究极约束”
代入到“究极问题”中去，有：
究极问题J(a2)=
对a2求导，使其为0，得
另外，
，（
，还记得吧，SVM的模型，可别忘了）代入进去，有：
好了，式子出来了，我们下面代入实际值进行迭代求解。
- 迭代求值
迭代求值不用多说，给定一个初始值，然后进行迭代更新。
给定a2和a1的初始值aold2，aold1，有
D= aold2+ aold1
代入到最终解里去，得到
a2上面的unc是什么？别忘了a2还要满足L<= a2 <= H，我们暂且不考虑这个范围，故用unc表示，考虑了这个范围，再把这个小尾巴unc去掉。
令
，原式等价于
，迭代得到：
现在把小尾巴unc去掉，
本集完，下一集将介绍如何用软件实现SMO算法，训练出一个俊美的SVM模型。