Sequential Minimal Optimization论文笔记

 我们知道，支持向量机的学习问题可以形式化为求解凸二次规划问题，凸二次规划问题有全局最优解。这篇论文主要提出了一个高效实现支持向量机学习的算法:(sequential minimal optimization , SMO)算法。具体地，SMO算法要解决下面的凸二次规划的对偶问题：
论文比较长，这里只记录SMO算法这一部分的要点。

1. SMO算法将全局的凸二次规划问题，分解成局部规划子问题，根据Qsuna的定理，能保证算法的收敛性；
2. 在算法的每一步，SMO算法尝试尽可能地解决最简单最小的子问题。由于上面问题的约束中含有等式约束，所以一次优化至少要包含两个拉格朗日乘子。所以每次循环，SMO算法都会选择两个拉格朗日乘子进行优化，同时还要优化SVM相关变量(阈值b,误差E等)来适应这些值的改变；
3. SMO算法的优势在于解决只含两个拉格朗日乘子的最优化问题可以解析的求出，数值优化可以完全的避免。每次只优化两个拉格朗日乘子可能对使得子问题的数量大大增加，但每个子问题的解决是如此快速，以至于总体来讲SMO算法仍然是快于其他算法的。
4. SMO算法不涉及矩阵的存储问题，所以对硬件的容量要求不高。
5. SMO算法主要由两部分构成：一个是解决两个拉格朗日乘子的解析方法，另外一个是选择哪两个拉格朗日乘子的启发式方法，主要是为了尽可能快的收敛；
6. 第一个拉格朗日乘子的选择构成了SMO算法的外循环，外循环在两种循环之间来回交替知道整个训练集在以的误差范围内遵循KKT条件:第一种循环是在整个训练集上的单次循环，另一个是在非边界集(的那些样本点)的反复循环直到所有的非边界样本点在以的误差范围内遵循KKT条件；
7. 第一个拉格朗日乘子一旦选定，就要选择第二个拉格朗日乘子，其标准是第二个拉格朗日乘子的变动幅度要尽可能的大。为了节约时间，的变动幅度用近似，其中是SVM的预测值和实际标签的差值。为了避免重复计算，SMO用一个缓存误差值列表来存储这些误差。