机器学习实战——支持向量机

【简易版——SMO算法】

• 第一变量的选择
  • 寻找第1变量的过程位外层循环— outloop
    • 线性搜索违反kkt的alpha1
• 第二变量的选择
  • 寻找第2变量的过程，位内循环— innerloop
  • 随机寻找一个与第1变量不重复的变量
• 调优

【SMO算法】

• 第一变量的选择

  • 寻找第1变量的过程位外层循环— outloop
    • 寻找违反KKT条件最严重的样本点

• 第二变量的选择

  • 寻找第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论文