文档介绍：支持向量机算法
Colin Campbell对SVM的训练算法作了一个综述，主要介
绍了以SVM为代表的分解算法、Platt的SMOffi Kerrthi的近邻
算法，但没有详细介绍各算法的特点，并且没有包括算法的最新进展。以下对各这
也是终止条件。2）工作集中训练样本的选择算法，应能保证分
解算法能快速收敛，且计算费用最少。 3）分解算法收敛的理论
证明，Osuna等证明了一个定理：如果存在不满足 Kohn-Tucker
条件的样本，那么在把它加入到上一个子问题的集合中后，优化这重新个子问题，则可行点（Feasible Point）依然满足约束条件，且性能严格地改进。因此，如果每一步至少加入一个不满足
Kohn-Tucker条件的样本，一系列铁二次子问题可保证最后单调收敛。Cha ng C.- na的证明不严密，并详尽地分析了
分解算法的收敛过程及速度，该算法的关键在于选择一种最优的工作集选择算法，Osu。2的工作集的选择算法也并不是最优的，
但是Osuna的这一工作应该说是开创性的，础。
并为后来的研究奠定了基
在分解算法基础上，微软研究院的John C. Platt等人提
出并且改进了 SMO(SequentialMinimal Optimization )算法。
这种算法将工作样本集的规模减到了最小一一两个样本。之所以需要两个样本是因为等式线性约束的存大使得同时至少有两个变量，而且应用等式约束可以将其中一个变量用另一个变量线性表示出来，所以迭代过程中每一步的子问题的最优解可以直接用解析的方法求出来，无需使用数值分析中的二次规划软件包，提高了子问题的运算速度；此外Platt还设计了一个两层嵌循环分别选择进入工作样本集的两个样本，外层循环选择第一个样本，内层循环选择第二个样本。外层循环首先在整个样本空间循环一遍，决定哪些样本违反了 Kohn-Tucker条件。如果找到了不满足
Kohn-Tucker条件的样本，它即被选作进入工作集的第一个样本。
然后根据第二个启发式规则选择第二个样本。最后用解析的方法快速对选定的样本进行优化。为了加快算法的运行速度，环不总是每次检
查所有训练样本。每次在所有样本上循环一遍以后，外层循环只外层循在Lagrange乘数大于零和小于C的样本上进行
循环，直到所有Lagrange乘数大于零和小于C的样本都满足了最优化所应该满足的Kohn-Tucker条件，然后再在整个样本空间循环一遍。这样，外层循环是交替地在整个样本空间和Lagrange
乘数大于零且小于C的样本上循环。内层循环选择第二个进入工
作集的样本，选择的原则是使目标函数靠近最优点的速度达到最快。这种启发式的样本选择策略大大加快了算法的收敛速度。
准样本集的实验结果证明，SMO表现出在速度方面的良好性能。
SMO方法可以看作是分解算法的一个特例，它将子问题了规
模减少到了最小。子问题的规模和迭代的次数是一对矛盾，将工作样SMO 本集的规模减少到两个样本，一个直接的后果就是迭代次数的增加。所以 SMC实际上是将求解子问题的耗费转嫁到迭代上，然后在迭代上寻求快速算法。
Chih-Wei Hsu 和 Chih-Jen Lin 综合 S. S .Keerthi 中