3 非线性支持向量机、SMO算法
理论上，KKT条件可以解出SVM，但是当训练集容量很大时，这种方法显得异常低效，甚至无法使用。SMO（sequential minimal optimization）算法为解决这一难题提供了一种思路。
SMO算法是一种启发式算法，先选择两个变量（在这里变量就是对偶变量alpha），要求一个是违反KKT条件最严重的一个，另一个由约束条件生成，其余变量固定；然后不断优化变量的两两组合，直到所有变量满足KKT条件；再计算得到原问题的解w和b。
3.1 假设空间
3.2 目标函数变形（对偶函数显式化）
到这里，目标函数进一步变形的关键就是通过求极值显式的呈现出对偶函数最小化的表达式。
3.3 优化算法（SMO）
回顾感知机中的优化算法，我们是直接使用随机梯度下降进行迭代，而这里动用SMO的SVM要复杂得多：
（1）、设置参数初始值 a = 0, b = 0
（2）、执行外循环，即搜索违反KKT条件的样本点，优先选择支持向量点（0<a1<C），定为a1
（3）、执行内循环，取 max|E1-E2| 的点（即更新幅度最大），定为a2
（4）、从目标函数中剥离出a1和a2，并建立二者的线性关系，如下所示：
（5）、消元&优化：消元去掉a1，此时目标函数中只剩下一个变量a2，对a2求导计算a2的未剪辑值（代码中只需关注最后一步）：
（6）、边界截断：根据约束条件，裁剪得到a2的更新值。此处要考虑y1和y2同号和异号两种情况，在同号的情况下，a1y1 + a2y2 的直线斜率为负，a2的上确界和下确界如下所示：
在异号的情况下，a1y1 + a2y2 的直线斜率为正，a2的上确界和下确界如下所示：
（7）、至此，可以计算出a1和w
（8）、计算 b（代码中需关注后三步）：
（9）、实时保存更新过的Ei
（10）、迭代，直至在精度eps内满足停止条件
