统计学习方法-7 支持向量机-3

3 非线性支持向量机、SMO算法
3.1 目标函数继续变形
理论上，KKT条件可以解出SVM，但是当训练集容量很大时，这种方法显得异常低效，甚至无法使用。SMO（sequential minimal optimization）算法，首先继续优化目标函数，关键点是通过求极值提炼出对偶函数的最小化表达式：

3.2 SMO算法
SMO算法是一种启发式算法，选择两个变量（在这里变量就是对偶变量alpha），要求一个是违反KKT条件最严重的一个，另一个由约束条件生成，其余变量固定；不断优化两两组合的变量直到所有变量满足KKT条件；再计算得到原问题的解w和b。

a1和a2的求解思维如下，从目标函数中剥离出一组a1和a2，建立二者的线性关系（公式写到眼瞎）：

消元去掉a1，优化得到a2的未剪辑值：

再根据约束条件，得到a2的更新值，此处要考虑y1和y2同号和异号两种情况，在同号的情况下，a1y1 + a2y2 的直线斜率为负，a2的上确界和下确界如下所示：

在异号的情况下，a1y1 + a2y2 的直线斜率为正，a2的上确界和下确界如下所示：

综上，得到a2的更新值，a2有了，a1的更新值也就有了，此时 w 亦可求，关键还要求 b：

求解 b：

3.3 如何挑选a1和a2
步骤：
（1）、选取初始值a = 0，b = 0，计算所有的 Ei 并保存为列表

（2）、外循环：选取违反KKT条件最严重的样本点，定为a1
（2.1）、首先检查支持向量，遍历所有满足 0<a1<C 的点（即在间隔边界上的支持向量），如果出现点违反KKT条件，定为a1
（2.2）、如果（2.1）都满足，再遍历整个训练集，检查是否违反KKT，定为a1

（3）、内循环：当a1确定后，选取a2
（3.1）、取 max|E1-E2| 的点（即更新幅度最大）
（3.2）、若存在多个 max|E1-E2|，取 0<a2<C 的点（支持向量）
（3.3）、如果没有，依次取其他点
（3.4）、如果还是没有，放弃a1，重复（2）

（4）、更新a1, a2, b, Ei
（5）、迭代，直至在精度eps内满足停止条件

未完待续