序列最小最优化（Sequential Minimal Optimization, SMO）算法的推导、理解
近期做了关于 SMO 算法的汇报，对这个算法理解了不少，也手推了一遍，记录一下这个小小的劳动成果。
内容大多是汇报的 ppt 截图，有需要的小伙伴可以去 下载，也可以给我留言，看到会回复的。
文章目录
前言
1998 年，John Platt 提出了序列最小最优化算法 (SMO) 算法用于训练 SVM 分类器。SMO 算法是一种启发式算法，其基本思路是：一次迭代只优化两个变量而固定剩余的变量。
SMO 要解如下凸二次规划的对偶问题
其实就是训练 SVM 分类器
算法过程
精度
ϵ
\epsilon
ϵ指 KKT 条件的容错率 toler。
部分 KKT 条件：
比如第二个条件，不要求严格等于 1 ，在容错率范围内都是可以接收的。原文内容如下：
SMO 算法主要有两个部分组成：
- 选取两个 α \alpha α进行优化；
- 求解两个 α \alpha α的解析解。
先说第二个内容
求解 α \alpha α的解析解
子问题
假设选择的变量是
α
1
,
α
2
\alpha_1,\alpha_2
α1,α2，其余变量
α
i
(
i
=
3
,
⋯
,
N
)
\alpha_i (i=3,\cdots,N)
αi(i=3,⋯,N)是固定的，则 SMO 的最优化问题的子问题如下，其中
K
(
x
i
,
x
j
)
=
K
i
j
K(x_{i},x{j})=K_{ij}
K(xi,xj)=Kij
首先分析约束条件，重新定义
α
2
\alpha_2
α2的取值范围
取值范围
根据约束条件得到 α 2 \alpha_2 α2的表达式，然后分情况讨论，并根据 α 1 ∈ [ 0 , C ] \alpha_1 \in [0,C] α1∈[0,C]进行放缩
还可以将约束条件用图形表示出来，也可以得到相同的结果
解析解
目标函数是含 α 1 n e w , α 2 n e w \alpha_1^{new},\alpha_2^{new} α1new,α2new两个变量的二次函数，为了方便求解，我们利用等式约束，将目标函数转化成只含 α 2 n e w \alpha_2^{new} α2new的函数，然后求极小值，并与之前求得的取值范围进行比较，确定 α 2 n e w \alpha_2^{new} α2new最终的表达式，最后根据等式约束也可以得到 α 1 n e w \alpha_1^{new} α1new.
将已知的量用
ν
i
\nu_i
νi替换，其中
f
(
x
i
)
=
∑
j
=
1
N
y
j
α
j
n
e
w
K
i
j
+
b
f(x_{i})=\sum_{j=1}^{N}y_{j}\alpha_{j}^{new}K_{ij}+b
f(xi)=j=1∑NyjαjnewKij+b
下一步转化成只含
α
2
n
e
w
\alpha_{2}^{new}
α2new的函数
对目标函数求导，并令其等于
0
0
0
定义一些等式，使表达式更简洁
得到的极值点不一定在
α
2
n
e
w
\alpha_{2}^{new}
α2new的取值范围里，所以需要剪辑，则最终的
α
1
n
e
w
,
α
2
n
e
w
\alpha_{1}^{new},\alpha_{2}^{new}
α1new,α2new的表达式如下
更新 b , E i b,E_{i} b,Ei
根据 KKT 条件得到相应的等式，然后求解就可以了。
之前一直不明白当
α
i
\alpha_{i}
αi都在边界上时
b
n
e
w
b^{new}
bnew的取值为什么要取中点，试着推导，恍然大悟 。
可以看出，当四种
y
i
y_{i}
yi的情况放在一起时，
b
n
e
w
b^{new}
bnew只能取中点。
其他在边界的情况也可以推导出相同的结论，同时关于
b
n
e
w
b^{new}
bnew其他情况的取值也清晰了。
选取 α 1 , α 2 \alpha_{1},\alpha_{2} α1,α2
多次遍历
α
i
∈
[
0
,
C
]
\alpha_{i}\in[0,C]
αi∈[0,C]的样本点，个人的理解是因为：根据 KKT 条件，这时
这样的样本点很容易违背 KKT 条件，对它们进行判断更新可以加快求解速度。
SMO 算法的理论推导就到这里了，最后贴一下李航老师《统计学习方法》里的算法流程。
算法实现
关于算法的实现，可以参考
支持向量机|SMO算法实现
如有错误，请指正，谢谢
参考资料
[1] 李航. 统计学习方法[M]. 清华大学出版社, 2012.
[2]https://www.jianshu.com/p/436d429ce91b