【简易版——SMO算法】
- 第一变量的选择
- 寻找第1变量的过程位外层循环— outloop
- 线性搜索违反kkt的alpha1
- 寻找第1变量的过程位外层循环— outloop
- 第二变量的选择
- 寻找第2变量的过程，位内循环— innerloop
- 随机寻找一个与第1变量不重复的变量
- 调优
【SMO算法】
-
第一变量的选择
- 寻找第1变量的过程位外层循环— outloop
- 寻找违反KKT条件最严重的样本点
- 寻找第1变量的过程位外层循环— outloop
-
第二变量的选择
- 寻找第2变量的过程，位内循环— innerloop
- 选择标准：希望能使alpha2有足够大的变化
- alpha2_new 依赖|E1-E2|
- 为了加快算法，一种方式就是选择第二变量，是的|E1-E2|足够大
- 可以将Ei保存在一个列表中
- 特殊情况下，上述方法找的alpha2不能是的目标函数有足有的下降，那么采用启发式规则选择alpha2
- 变量间边界上的支持向量点，
- 依次将其对应的变量作为alpha2试用，直到目标函数有足够的下降，
- 若找不到就遍历训练集数据，
- 再找不到就放弃第一个alpha1,通过外层寻求另外的alpha2
-
计算阈值b和差值Ei
- 计算b1_new
- 计算b2_new
- 计算b
SMO中拉格朗日乘子的启发式选择方法
终于到了最后一个问题了，所谓的启发式选择方法主要思想是每次选择拉格朗日乘子的时候，优先选择样本前面系数的作优化（论文中称为无界样例），因为在界上（为0或C）的样例对应的系数一般不会更改。这条启发式搜索方法是选择第一个拉格朗日乘子用的，比如前面的。那么这样选择的话，是否最后会收敛。可幸的是Osuna定理告诉我们只要选择出来的两个中有一个违背了KKT条件，那么目标函数在一步迭代后值会减小。违背KKT条件不代表，在界上也有可能会违背。是的，因此在给定初始值=0后，先对所有样例进行循环，循环中碰到违背KKT条件的（不管界上还是界内）都进行迭代更新。等这轮过后，如果没有收敛，第二轮就只针对的样例进行迭代更新。
在第一个乘子选择后，第二个乘子也使用启发式方法选择，第二个乘子的迭代步长大致正比于，选择第二个乘子能够最大化。即当为正时选择负的绝对值最大的，反之，选择正值最大的。
最后的收敛条件是在界内（）的样例都能够遵循KKT条件，且其对应的只在极小的范围内变动。
至于如何写具体的程序，请参考John C. Platt在论文中给出的伪代码。
【参考材料】：
- 李航：《统计学习方法》p124-131
- PATT论文
