第6期 王书舟，等：支持向量机的训练算法综述 ·469· mal optimization,SMO)算法[]是分解算法工作集的 是在线采集的，就必须使用增量式学习算法或在线 个数等于2的特殊情形，即SM0把一个大的优化问 学习算法]，增量学习是机器学习系统在处理新 题分解成一系列只含两个变量的优化问题.两个变 增样本时，能够只对原学习结果中与新样本有关的 量的最优化问题可以解析求解，因而不需要迭代地 部分进行增加、修改或删除操作，与之无关的部分则 求解二次规划问题.对分类SMO算法，Keerthi等 不被触及，增量训练算法的一个突出特点是支持向 人【8]修正了优化条件，并针对经验方法提出两个改 量机的学习不是一次离线进行的，而是一个数据逐 进措施，以保证算法收敛和减少迭代次数.随后 一加入反复优化的过程.文献[40]的算法改进是基 Keerthi等人[91提出了广义SMO(generalized SMO, 于Cauwenberghs提出的用于模式识别的增量减量 GSMO)算法，利用违反对的概念确定工作集，指出 式学习方法，这种算法的目的是防止训练过程中有 前面两种改进都是GSM0的特例，并证明，Ht>0, 用支持向量的丢失.考虑了增加或减少一个训练样 以r违反对为工作集，则GSMO算法有限终止，得到 本对拉格朗日系数和SVM的影响.在减少一个样本 优化问题的r近似优化解.Lin2o对SM0算法的渐 时，给出了模型选择算法留一法的形象解释.增量型 进收敛性进行了证明， 支持向量机训练算法可以用于实时在线训练，如 起初SM0算法主要用于模式分类问题，后来 Ma4提出了用于函数回归问题的增量型在线SVM Smola21]等人进行类比扩展，提出了一种训练回归 训练算法.序贯训练算法是样本数据序贯加入的训 SVM的SMO算法.这种算法选取两对变量a、a、 练方法，也是在线训练方法的一种.人们提出一种 ajag,在每个迭代步，类似Platt的SM0的策略，按 Kernel Adatron算法[2]对SVM进行分类的序贯训 照所选变量不同取值的4种情况，对QP子问题进 练，这种方法的基本思想是借助感知机中的Adatron 行解析求解.Shevade(1指出Smola的更新阈值b方 算法的原理来改变拉格朗日系数，具体来说通过序 法并不是很有效，提出利用双阈值方法改进，同时还 贯加入的样本的预测误差来修改SVM样本的系数， 提出了一种按照违反KKT优化条件的程度选择变 其本质上是一个爬山的寻优算法，通过反复的修改 量的新方法.Fake等人[2a]针对SVM回归问题，指 序贯加入样本的系数，使训练过程最终收敛.后来将 出通过设置B:△-a,i=1,…,l,2l变量的QP问 上述算法改进，使其不但适合分类而且也适合回归. 题可以转化为1个变量的QP问题，并改进了经验方 Vojislav2]证明了Kernel Adatron与SM0算法的等 法以提高缓存的利用效率.Michael[24]针对不需要计 价性.用于回归的Kernel Adatron和SMO的系数更 算偏置项b的情况，分别对SMO的分类和回归算法 新公式分别为 进行了改进.Keerthi2]提出了用于最小二乘SvM 「C:←a:-a-7:(E:+e), 的SM0算法.Zeng26]等人提出了基于SM0算法的 (4) 稀疏最小二乘剪枝算法.Norikazu[79]对SM0的中 a←-a-+n:(E:-6)； 止条件进了严格的证明.Cao303门提出了训练SVM (E:+e) a,←-a-K, 的并行SM0算法.Chen32]等人对SM0类型的分解 (5) 算法进行了研究.Bo1对最小二乘SVM的SM0算 (E:-e) a←a-a+Kx) 法的工作集的选择进行了研究.此外还有其他针对 SMO的分类和回归的改进算法[34)] 取n:=1/K(x:,x:),则容易看出式(4)与(5)算法的 SMO算法是分解算法中选取工作集为2的特 等价性.Yaakov[4]在Kernel Adatron算法的基础上， 殊情形，SMO将工作集的规模减到最小，一个直接 结合支持向量的精确缩减，并把它们用于在线学习 的后果就是迭代次数的增加.与分解算法相比，尽管 的框架，提出一种稀疏在线贪婪(sparse online 它可能需要更多的迭代步，但是由于每步只需要很 greedy,SOG)SVR算法， 少的计算量，SMO算法通常表现出整体快速收敛的 Smola4提出了一种在再生核Hibert空间采用 性质.另外该算法还具有不需要储存核矩阵、没有矩 随机梯度下降的在线算法，可以用于支持向量机的 阵运算、容易实现等重要特点.但是分解算法、SMO 分类、回归和新奇性检测.Smale[5]提出在再生核空 算法，都是只能够离线应用的训练算法 间和一般的Hibert空间的在线算法，给出了随机梯 2.3 增量及在线训练算法 度算法的一般形式和可能的收敛界.Yig6]提出了 如果学习机的样本是随着时间序列获得的，或 一种在再生核Hibert空间中，基于一般凸正则损失