第3卷第6期 智能系统学报 Vol.3 No.6 2008年12月 CAAI Transactions on Intelligent Systems Dec.2008 支持向量机的训练算法综述 王书舟，伞冶 (哈尔滨工业大学控制与仿真中心，黑龙江哈尔滨150001) 摘要：支持向量机(SVM)是在统计学习理论基础上发展起来的新方法，其训练算法本质上是一个二次规划的求解 问题.首先简要概述了SVM的基本原理，然后对SVM训练算法的国内外研究现状进行综述，重点分析SVM的缩减 算法和具有线性收敛性质的算法，对这些算法的性能进行比较，并且对SVM的扩展算法也进行简单介绍.最后对该 领域存在的问题和发展趋势进行了展望， 关键词：统计学习理论；支持向量机；训练算法 中图分类号：TP391.9文献标识码：A文章编号：1673-4785(2008)06046709 A survey on training algorithms for support vector machine WANG Shu-zhou,SAN Ye (Control Simulation Centre,Harbin Institute of Technology,Harbin 150001,China) Abstract:Support vector machines (SVMs)use new methods that originated in statistical learning theory.Training of an SVM can be formulated as a quadratic programming problem.The principles of SVM have been summarized briefly in this paper.The latest developments in SVM training algorithms in domestic and overseas research were re- viewed,especially reduction algorithms and algorithms with linear convergence properties.The performance of these algorithms was then compared,and a brief introduction to a proposed extension of them was given.Finally some problems and potential directions for future research are discussed. Keywords:statistical learning theory;support vector machine;training algorithms 支持向量机(support vector machine,.SVM)是近对SVM本身的特点提出了许多算法，本文对这些算 年发展起来的一种通用机器学习新方法.它不但具 法进行综述，包括块算法、分解算法、序贯最小优化 有坚实的理论基础、简洁的数学形式、直观的几何解 算法、增量与在线训练算法、缩减算法、具有线性收 释，而且能够较好地解决小样本、非线性、维数灾和 敛性质的算法，以及SVM的扩展算法. 局部极小等问题12，因此在模式分类[34)、回归问 题56等很多领域得到了广泛的应用。 1支持向量机 训练SVM的算法归结为求解一个受约束的凸 SVM最初是在模式分类中提出的，其基本思想 二次优化问题.对于小规模的二次优化问题，利用牛 是：通过非线性变换中(·)将输入空间映射到一个 顿法、内点法等成熟的经典最优化算法就可以很好 高维特征空间，在这个特征空间中求取最大间隔分 地求解.但这些算法通常需要利用整个Hessian矩 类超平面f(x)=w中(x)+b,其中w、b分别是这个 阵，内存占用过多，从而导致训练时间过长.当训练 超平面的权值和阈值.特征空间的维数可能是非常 集很大，特别是支持向量数目也很大时，求解二次优 高的，通常导致计算非常复杂.SVM算法通过核函 化问题的经典方法不再可行.因此设计适用于大量 数K(x,y)巧妙地解决了这个问题.SVM不直接计算 样本的训练算法成为SVM研究的重要内容.目前针 复杂的非线性变换中(·)，而是计算非线性变换 收稿日期：2008-06-30. 中(·)的内积K(r,y),即核函数K(x,y)=中(x)· 基金项目：国家自然科学基金资助项目(60474069) 中(y）,从而大大简化了计算.核函数K(x,y)的利用 通信作者：王书舟.E-mail:seek2000@163.com, 是由于在原空间和高维特征空间只用到了内积运算
·468. 智能系统学报 第3卷 的缘故. 代方式逐步排除非支持向量.块算法将矩阵的规模 类似用于模式分类的SVM,回归SVM(support 从训练样本数的平方减少到具有非零Lagrange乘 vector regression,SVR)的基本思想是，通过非线性 子的样本数的平方，从而降低了训练过程对存储容 变换中(·)，将输人空间映射到一个高维特征空 量的要求 间，并在这个特征空间用线性函数f(x)= Osuna等人提出的分解算法(decomposition al- w中(x)+b拟合样本数据，同时保证能得到较好的 gorithm)21,是目前有效解决大规模问题的主要方 泛化能力.设x:∈R,y:∈R,i=1,…,l,l为观测样 法.分解算法将二次规划问题分解成一系列规模较 本，R"代表输人空间，SVR问题可以表示为线性约 小的二次规划子问题，进行迭代求解.在每次迭代 束二次规划的优化问题： 中，选取拉格朗日乘子分量的一个子集做为工作集， m吃11+号容+g1, 利用传统优化算法求解一个二次规划的子问题. Joachims在上述分解算法的基础上做了几点重要改 r（(w·)+b)-y≤6+6， (1) 进.第一，采用类似Zoutendijk可行方向法的策略确 8.t.{y:-(w·)+b)≤e+g, 定工作集B,即求解一个线性规划问题，得到可行 5,5≥0. 下降方向，把该方向中的非零分量作为本次迭代的 其中C>0是函数复杂度和损失误差之间的一个平 工作集，该线性规划存在高效算法，其核心是一个排 衡量.由优化问题(1)的Lagrange函数相对于变量 序问题.第二，提出shrinking方法，估计出有界支持 、b5、5:的偏导数为0，可得优化问题(1)的对偶 向量和非支持向量，有效地减小QP问题的规模.最 问题： 后，利用KernelCache来减少矩阵中元素的计算次 数.Joachims利用这些方法实现的SVMlight,.是目前 min 设计SVM分类器的重要软件， 且x(a-a Lin7]和Takahashi9等人分析并证明了分解 (a +ai) (2) 算法的收敛性.Lino]对-SVM和多类SVM的停 机准则进行了分析，并针对多类SVM证明了分解算 8.t. a,-)=0, 法的渐进收敛性.Hu得到了鲁棒SVM的KKT条 0≤a,a≤l,i=1,…,1. 件和分解算法，利用预选取技术提高分解算法的收 这个约束最优化问题的解是核函数的线性组合，具 敛速度.Dong2]引进并行优化算法来快速剔除非支 有如下的形式： 持向量，用对角块矩阵逼近原核矩阵，从而原始问题 分解为易于求解的子问题.Qiao131提出一种工作集 )=召(a,-a)K)+b (3) 选择规则，使分解算法具有多项式收敛的性质。 这个用作函数回归的学习机器就是支持向量 块算法的目标是找出所有的支持向量，因而最 机，支持向量就是使表达式(3)中系数(a:-a:)不 终需要存储相应的核函数矩阵，对于支持向量数很 为零的训练样本，在使用SVM解决实际问题时，首 大的问题，块算法十分复杂，与块算法不同，分解算 先需要把它转化为一个可以用SVM求解的数学模 法的目的不是找出所有的支持向量，而是每次只针 型，这一工作称为模型选择，它包括训练集的选择、 对很小的训练子集来求解，即使支持向量的个数超 SVM类型的选择、核函数的选择、SVM中自由参数 过工作集的大小，也不改变工作集的规模.各种分解 的选择等.对已经进行了模型选择的最优化问题 算法的区别在于工作集的大小和工作集生成原则的 (1)或(2)，其求解方法就是SVM的训练算法. 不同.工作集的选择对于分解算法的收敛与否和收 敛速度至关重要，因此开发新的工作集选择算法是 2支持向量机的基本算法 提高分解算法性能的重要途径， 2.1块算法与分解算法 除了分解算法，还有Huber近似算法[4、多拉 块算法(chunking algorithm)[21最早是由Boser 格朗日乘子协同优化算法1s]、剪枝算法「16等SVM 等人提出来的.它的出发点是，删除矩阵中对应于 的求解方法. Lagrange乘子为零的行和列不会对最终结果产生影 2.2序贯最小优化算法 响.对于给定的样本，块算法的目标就是通过某种迭 由Platt提出的序列最小优化(sequential mini-
第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空间中，基于一般凸正则损失
470 智能系统学报 第3卷 函数的在线分类算法.Bianchi?41基于独立同分布 时，需要保存的样本也很多.Crammer's71引入一个称 的训练数据，给出对任意在线训练方法所取得具有 为Budget的量，他以Rosenblatt的感知机为基础，增 的最小风险的假设： 加一个样本的插入和删除过程，从而达到控制支持 增量减量算法[3941、基于Kemel Adatron的算 向量个数的目的.令I为样本索引的集合，II表示 法2)、在线算法4都可用于在线学习，但是增 集合所含元素的个数，则此方法可以描述如下： 量减量算法比较复杂，需要存储核矩阵，因此训练速 初始化：设置e,n,:=0,wo=0,l为空 度较慢.而基于Kernel Adatron的算法原理简单，每 Fort=1,2,…,T 次更新的运算量小，需要的内存也不大.然而这种训 取得一个新样本x∈R”,及其标签y:,并做预测： 练算法随着每次新样本的加入，都会引起其他样本 y=sig(y,(x,·w-1)). 系数的改变，需要不断地进行反复优化.在线算 fy(x,·w-1)≤e 法]可以采用基于随机梯度下降的方法，算法比 1)f1L:I=n,删除一个样本： 较简单，而且对风险的界和收敛性等都有较严格的 a.i=argmaxien ly;(w:-1-ay) 理论分析和证明.另外，这些在线学习方法的缺点是 b.更新：w-1-w-1-Cy 需要考虑所有的历史数据，无法控制支持向量的个 c.删除第i个样本：Ik-I/{. 数.只有考虑到SVM解的稀疏性，才有可能减小计 End 算量，缩短计算时间. 2)插入新样本：I,-1-1U{t. 2.4支持向量缩减算法 3)令a4=1. 支持向量的数量的下界与训练样本数成线性关 4)计算w,-w-1+yax 系【，这表明支持向量的数量至少随训练样本的加 End 入而线性地增加.对具有大量训练样本的优化问题， End 支持向量的数量是影响在线训练和预测速度的主要 输出f代x)=igm(w·x). 因素.因此，减少预测函数中包含支持向量的数量， Westons]指出上述以间隔的大小作为删除样 成为提高SVM在线训练速度和预测速度的目标.文 本的度量准则，具有噪声敏感的缺点，进而提出一种 献[50]提出一种内积矩阵分解的算法，来提高SVM 改进算法，以选定的样本子集的误差作为度量准则， 的分类速度.内积矩阵分解算法的思想是通过优化 具有更好的鲁棒性.Deke9]通过收缩系数中，选 的方式，适当地变换特征空间中的内积矩阵，并进一 取，删除的是最旧的样本，得到了具有严格限制的支 步变换分类函数的形式，既减少分类函数中支持向 持向量和相关错误界.Dekl[o]用插值模代替标准 量的数量，又能将全部支持向量的信息保留在分类 SVM中的任意模，实现对支持向量个数的控制.并 函数中，达到不损失分类精度，又提高分类速度的目 证明了：p插值范数和∞范数，近似等价于限制为样 的.Wus1]通过在标准支持向量上附加更多的限制 本前t个绝对值最大的元素的p插值范数；特别地， 条件，直接得到稀疏大间隔分类器.Nguyen52s1提 当p=1时，1-∞插值范数等价于对样本t个绝对 出了一种bottom-up的方法，其缩减过程迭代地选择 值最大的元素进行绝对值求和.在此文献中还改进 属于同一类的两个最近的支持向量，然后用一个新 标准的SMO算法以适应这种框架下的求解. 向量代替.新向量的构建只需要计算一个单变量函 上述缩减算法大多考虑了SVM解的稀疏性，但 数在(0,1)内的惟一最大值点，因此可以有效减少 却又回到了更复杂的解决方法上，如通过核函数构 支持向量的数量.Keerthis4提出用贪婪算法选择基 成的矩阵的逆计算所有支持向量，计算新的优化问 向量，来逼近原支持向量，从而减小分类函数的复杂 题等，实际上没能做到减少运算量， 度.「s5]基于向量相关准则和贪婪算法的思想，提 2.5具有线性收敛性质的算法 出了一种特征向量选择的自适应缩减方法。 训练SVM的常用方法，如分解方法、SMO方法 Sumeet's6利用Span概念进行支持向量的启发式缩 等，结果收敛所需要的时间对样本数来说通常是 减，并提出了一种支持向量机在线训练算法。 超线性的.因此这些方法在应用于大数据集时失去 支持向量缩减方法可以用于在线学习，但是这 有效性.Joachims61对线性支持向量机提出了SVM- 些方法的缺点是需要考虑所有的历史数据，没有遗 Perf方法，这种方法在每一迭代步计算当前解的梯 忘机制，无法控制支持向量的个数.当样本增加较多 度并把它加到优化问题中，使训练SVM所用的时间
第6期 王书舟，等：支持向量机的训练算法综述 471· 与样本数呈线性关系.SVMPerf以精度e在时间 因为一次泰勒逼近是逼近函数的下界，则 O(md/(A&2))内求得解.这个界被Shwartz提出 Rp（w）≥max,, 的Pegasos方法改进为以精度e,以置信度1-6，在 定义Rp和J的下界为 时间O(1/(A8e)内得到解.Pegasos实质上是执行 R.(w)max a,w>+b, 随机次梯度下降，把解返回并投影到以1/√入半径的 J(w):=A2(w)+R(w). L,球面上 且对所有t≤t构造R,≤R,≤Rmp,J,≤J,≤J,通过 Smola6]针对正则风险最小化问题，提出了一 定义： 种统一框架的全局收敛方法，可以应用于任何导致 w=argmin/(w）,w,=argmin,（w), 凸优化问题的正则风险最小化问题.其基本思想是： Y=J(,）-J(w,）,t=mi(w,）-J(w,) 在正则化函数中，正则项不变，用经验风险的下界， 则可得到如下结论，对所有≤t有如下关系成立： 即经验风险的一次泰勒逼近，代替经验风险，进行最 J(w）≤J,(w:)≤J(w）≤J(w,)=J+(w) 优化求解.Smola指出SVMPerf是这种方法的一个 进而，6，是单调减的且 特例，并给出了更紧的收敛界，即对ε精度，对一般 E:-6+1≥J+1(w41）-J,(w,)≥0. 的凸优化问题在0(1/ε)步内收敛，对连续可微问 另外ε，为到最优点距离的上界： 题在0(1lg(1/ε))步内收敛.这个方法的另一个重 要特点是，它可以自动利用优化问题的光滑性，它的 Y.≥E:≥minsJ(w,）-J(w) 在主空间支持向量机的线性算法可简单描述如 一个改进是无需求解二次规划问题而拥有同样的收 下： 敛速度。 这种方法一个关键技术点是次梯度.次梯度是 初始化：t=0,州o=0,a6=0,b=0,J(w)=入2(w) 凸函数梯度的一个推广，其中凸函数可以是非光滑 While s,≤e 的.假设"是凸函数F的一个函数值有限点，那么 取得最小值w,:=argmin J,(w) 次梯度是在w点F的任何正切支撑超平面的标准 计算次梯度a,+1和偏移量b+1 法向量.确切地被称为F在点的次梯度，当且 t←t+1 仅当 End Yw',F(w')>F(w)+, 此外，Smola]还给出了在对偶空间SVM的线 F在一点w的所有次梯度的集合称为F在这点的 性算法，并由经验数据得出结论：在对偶空间执行精 次微分，表示为8F(w).若这个集合非空，那么称F 确的线性搜索，则在主空间的目标函数有更快的收 在”点次可微.若这个集合只有一个元素，称F在 敛速度， w点可微.用x∈X,y∈Y分别表示训练样本的输人 3支持向量机的扩展算法 模式和输出标签，l(x,y,w)是凸损失函数且w∈W, W是再生核希尔伯特空间.对给定的一组观测样本 随着对SVM研究的深入，人们提出了一些SVM x:∈R",y:∈R,i=1,…,l,正则风险最小化函数可表 的扩展算法.这些扩展算法主要是通过增加函数项、 示为 变量或系数等方法使公式变形，产生出有某一方面 优势，或者有一定应用范围的算法，如-SVM646s]】 J(w）=Rp(w)+入2(w), 广义SVM(generalized SVM,CSVM)[s6,最小二乘 R(w):=12105,,m). SVM(least-square SVM,LS-SVM)[63-691.-SVM ma 法中用参数)取代C,v是间隔错误样本的个数所占 2(w)是光滑的凸正则项，入>0是正则系数，：=表 总样本点数的份额的上界，也是支持向量的个数所 示按定义等于， 占总样本点数的份额的下界.参数v对于各种噪声 令"：∈W表示在每次迭代中w的取值，并且令 具有较好的鲁棒性，易于选择，并且可用以控制支持 a,∈W,b.∈R,w0=0,a0=0,bo=0,则Rp[w.]的 向量的数目和误差，广义SVM直接以优化系数和核 泰勒展开系数为 矩阵构造出一个不等式约束的非线性优化问题，其 a+l=anRm（w:）, 对偶形式与标准SVM对偶形式等价.但广义SVM bit Ramp(w:)- 并不是直接求解此优化问题或其对偶形式，而是构
·472 智能系统学报 第3卷 造出若干特例：光滑SVM、近似SVM、简化SVM等， 着理论的不断发展和完善，SVM在模式识别、回归 LS-SVM算法主要是为了解决计算复杂性问题，它 分析、生物信息技术、医学研究以及其他一些领域， 采用二次损失函数，并用等式约束来代替标准SVM 必将得到更加广泛的应用. 算法中的不等式约束，把标准SVM算法的二次规划 问题转变成了线性方程组来求解。 参考文献： 此外还有加权SVM(weighted SVM)[o1模糊 [1]VAPNIK V.The nature of statistical learing theory M]. SVM（fuz四SVM)Im1、鲁棒SVM（robust New York:Springer Verlag,2000. SVM)[41,积极学习SVM(active SVM)[6]、中心 [2]CRISTIANINI N,SHAWE T J.An introduction to support sVM(center SVM)m,并行SVM(parallel vector machine[M].New York:Cambridge University Press,2000. SVM)i]、多类SVM(muli-class SVM)【91、几何 SVM(geometric SVM)[o1、转导半监督SVM((trans- [3]DOUMPOS M,ZOPOUNIDIS C.Additive support vector machines for pattern classification[J].IEEE Trans on Sys- ductive semi-supervised SVM)[a1-2l等】 tems,Man,and Cybernetics:Part B,2007,37(3):540- 550. 4结束语 [4]JAYADEVA,KHEMCHANDANI R,CHANDRA S.Twin 统计学习理论系统地研究了机器学习问题，尤 support vector machines for pattern classification[J].IEEE 其是在有限样本情况下的统计学习问题.这一理论 Trans on Pattern Analysis and Machine Intelligence,2007, 框架下产生的SVM是一种通用的机器学习新方法， 29(5):905-910. [5]WU Zhili,LI Chunhung,JOSEPH K,et al.Location esti- 在理论和实际应用中表现出很多优越的性能.SVM mation via support vector regression[J].IEEE Trans on 算法的理论与应用均取得了长足的进步，但在处理 Mobile Computing,2007,6(3):311-321. 有大量训练数据的实际应用中，仍然存在计算速度 [6]HAO Peiyi,CHIANG J H.Fuzzy regression analysis by 和存储容量等问题.该领域需要进一步发展和完善， support vector leaming approach[J].IEEE Trans on Fuzzy 研究方向包括： Sy9tems,2008,16(2):428-441. 1)更高效的算法.训练算法的收敛速度和计算 [7]CHANG CC,HSU C W,LIN C J.The analysis of decom- 所需内存是SVM发展的瓶颈，设计更快、更小的高 position methods for support vector machines[J].IEEE 效算法一直是SVM算法研究的主要目标. Trans on Neural Networks,2000,11 (4):1003-1008. [8]LIN C J.On the convergence of the decomposition method 2)更符合实际情况的假设.现有方法基本上是 for support vector machines[J].IEEE Trans on Neural Net- 基于数据的独立同分布假设，而很多实际情况，如非 work8,2001,12(6):1288-1298. 线性动态系统的建模，显然不满足这个条件.开发非 [9]NORIKAZU T,TETSUO N.Global convergence of decom- 独立同分布假设情况下的算法，将具有更大的实用 position learning methods for support vector machines[J]. 价值. IEEE Trans on Neural Networks,2006,17 (6):1362- 3)统一框架的建立.SVM的各种在线算法之 1369. 间，以及SVM与Logistic回归、条件随机域、Lsso类 [10]LIN C J.A Formal analysis of stopping criteria of decomp- 方法估计P范数方法、稀疏表示等方法之间的内在 osition methods for support vector machines[J].IEEE Trans on Neural Networks,2002,13(5):1045-1052. 联系是怎样的，如何建立统一的模型和研究理论体 [11]HU W J,SONG Q.An accelerated decomposition algo- 系也是值得研究的方向. rithm for robust support vector machines[J].IEEE Trans 当前的SVM缩减方法基本上是采用一步优化 on Circuits and Systems,2004,51(5):234-240. 策略的贪婪算法，这不但增加了算法的计算量，而且 [12]DONG Jianxiong,ADAM K,CHING Y S.Fast SVM 难以得到整体最优解.基于基寻踪原理的稀疏表示， training algorithm with decomposition on very large data 是一种采用p范数作为度量函数的全局竞争优化算 sets[J].IEEE Trans on Pattern Analysis and Machine In- telligence,2005,27(4):603618. 法，在一定条件下稀疏表示获得的解是最稀疏的解， 同时也是待逼近函数的本质驱动源.另外，次梯度在 [13 ]QIAO Hong,WANG Yanguo,ZHANG Bo.A simple de- composition algorithm for support vector machines with pol- 训练过程中表现出良好的收敛速度，且不要求目标 ynomial-time convergence[J].Pattern Recognition,2007, 函数可微.因此，基于次梯度和稀疏表示的方法可望 40(9):2543-2549 在进一步提高SVM训练速度方面发挥重要作用.随 [14]周水生，詹海生，周利华.训练支持向量机的Huber近
第6期 王书舟，等：支持向量机的训练算法综述 ·473· 似算法[J].计算机学报，2005,28(10)：1664-1670. [26]ZENG Xiangyan,CHEN Xuewen.SMO-based pruning ZHOU Shuisheng,ZHAN Haisheng,ZHOU Lihua.A Hu- methods for sparse least squares support vector machines ber approximation method for training the support vector [J].IEEE Trans on Neural Networks,2005,16 (6): machines[J].Chinese Journal of Computers,2005,28 1541-1546. (10):1664-1670. [27]NORIKAZU T,TETSUO N.Rigorous proof of termination [15]业宁，孙瑞样，董逸生.多拉格朗日乘子协同优化的 of SMO algorithm for support vector machines[J].IEEE SVM快速学习算法研究[J].计算机研究与发展， Trans on Neural Networks,2005,16(3):774-776. 2006,43(3):442-448. [28]GUO J,TAKAHASHI N,NISHI T.A novel sequential YE Ning,SUN Ruixiang,DONG Yisheng.SVM fast train- minimal optimization algorithm for support vector regression ing algorithm research based on multi-lagrange multiplier [C]//Proceedings of the 13th International Conference on [J].Joumal of Computer Research and Development, Neural Information Processing.Hong Kong,China,2006, 2006,43(3):442-448. 4234:827-836. [16]杨晓伟，路节，张广全.一种高效的最小二乘支持向 [29]TAKAHASHI N,GUO J,NISHI T.Global convergence of 量机分类器剪枝算法[J].计算机研究与发展，2007， SMO algorithm for support vector regression[J].IEEE 44(7):1128-1136. Trans on Neural Networks,2008,19(6):971-982. YANG Xiaowei,LU Jie,ZHANG Guangquan.An effec- [30]CAO L J,KEERTHI S S,ONG C J.Developing parallel tive pruning algorithm for least squares support vector ma- sequential minimal optimization for fast training support chine classifier[J].Journal of Computer Research and De- vector machine[J].Neurocomputing,2006,70(3):93- velopment,2007,44(7):1128-1136. 104. [17]PLATT J C.Fast training of support vector machines using [31]CAO L J,KEERTHI SS,ONG C J,et al.Parallel se- sequential minimal optimization[C//Advances in Kemnel quential minimal optimization for the training of support Methods-Support Vector Learning.Cambridge,MA:MIT vector machines J].IEEE Trans on Neural Networks, Press,1999:185-208. 2006,17(4):1039-1049. [18]KEERTHI S,SHEVADE S.BHATTCHARYYA C.et al. [32]CHEN P H,FAN R E,LIN C J.A study on SMO-type Improvements to Platt's SMO algorithm for SVM classifier decomposition methods for support vector machines[J]. design[J].Neural Computation,2001,13(3):637-649. IEEE Trans on Neural Networks,2006,17(4):893-908. [19]KEERTHI S,GILBERT E.Convergence of a generalized [33 ]BO Liefeng,JIAO Licheng,WANG Ling.Working set se- SMO algorithm for SVM classifier design J].Machine lection using functional gain for LS-SVM[J].IEEE Trans Learning,2002,46(1/2/3):351-360. on Neural Networks,2007,18(5):1541-1544. [20]LIN C J.Asymptotic convergence of an SMO algorithm [34]孙剑，郑南宁，张志华.一种训练支撑向量机的改进 without any assumptions[J].IEEE Trans on Neural Net- 贯序最小优化算法[J].软件学报，2002,13(10)： work3,2002,13(1):248-250. 2007-2012. [21]SMOLA A,SCHOLKOPF B.A tutorial on support vector SUN Jian,ZHENG Nanning,ZHANG Zhihua.An im- regressions[J].Statistics and Computing,2004,14(8): proved sequential minimization optimization algorithm for 199-222. support vector machine training[J].Joumnal of Software, 22]SHEVADE S K,KEERTHI SS,BHATTACHARYYA C. 2002,13(10):2007-2012. Improvements to SMO algorithm for SVM regression[J]. [35]李建民，张钹，林福宗.序贯最小优化的改进算法 IEEE Trans on Neural Networks,2000,11 (5):1188- [J].软件学报，2003,14(5)：918-924. 1193. LI Jianmin,ZHANG Bo,LIN Fuzong.An improvement al- [23]FLAKE G W,LAWRENCE S.Efficient SVM regression gorithm to sequential minimal optimization[J].Journal of training with SMO[J].Machine Learning,2002,46(1/ Software,2003,14(5):918-924. 2/3):271-290. [36]张浩然，韩正之回归支持向量机的改进序列最小优 [24]VOGT M.SMO algorithms for support vector machines 化学习算法[J].软件学报，2003,14(12)：2006 without bias term[R].Darmstadt,Germany:Institute of 2013. Automatic Control Laboratory for Control Systems and ZHANG Haoran,HAN Zhengzhi.An improved sequential Process Automation,Technische Univ.Darmstadt,2002. minimal optimization learning algorithm for regression sup- [25]KEERTHI SS,SHEVADE S K.SMO algorithm for least port vector machine[J].Journal of Software,2003,14 squares SVM formulations J].Neural Computation, (12):2006-2013. 2003,15(2):487-507. [37]朱齐丹，张智，邢卓异.支持向量机改进序列最小优
474 智能系统学报 第3卷 化学习算法[J].哈尔滨工程大学学报，2007,28(2)： on-line algorithms[J].IEEE Trans on Information Theory, 183-188. 2008,54(1):386-390. ZHU Qidan,ZHANG Zhi,XING Zhuoyi.Improved SMO [49]STEINWART I.Sparseness of support vector machines learing method of support vector machine [J].Joural of [J].Journal of Machine Learn Research,2003,4(3): Harbin Engineering University,2007,28(2):183-188. 1071-1105. [38]张浩然，汪晓东.回归最小二乘支持向量机的增量和 [50]刘向东，陈兆乾。一种快速支持向量机分类算法的研 在线式学习算法[J].计算机学报，2006,29(3)：400- 究[J刀.计算机研究与发展，2004,41(8)：1327-1332. 406. LIU Xiangdong,CHEN Zhaoqian.A fast classification al- ZHANG Haoran,WANG Xiaodong.Incremental and on- gorithm of support vector machines[J].Journal of Comput- line leaming algorithm for regression least squares support er Research and Development,2004,41 (8):1327- vector machine[J].Chinese Journal of Computers,2006, 1332. 29(3):400-406. [51]WU M,SCHOLKOPF B,BAKIR G.A direct method for [39]杨静，张健沛，刘大昕.基于多支持向量机分类器的 building sparse kemnel learning algorithms[J].Joural of 增量学习算法研究[J].哈尔滨工程大学学报，2006,27 Machine Learning Research,2006,7(4):603-624. (1):103-106. [52]NGUYEN D,HO T.An efficient method for simplifying YANG Jing,ZHANG Jianpei,LIU Daxin.Research on in- support vector machines[C]//International Conference on cremental leaming algorithm with multiple support vector Machine Learning.Bonn,Germany,2005:617-624. machine classifiers [J].Journal of Harbin Engineering U- [53 ]NGUYEN D.HO T.A bottom-up method for simplifying niversity,2006,27(1）:103-106. support vector solutions [J].IEEE Trans on Neural Net- [40]汪辉.增量型支持向量机回归训练算法及在控制中 woks,2006,17(3):792-796. 的应用[D].杭州：浙江大学，2006. [54]KEERTHI SS,CHAPELLE O,DECOSTE D.Building WANG Hui.Incremental support vector machine regression support vector machines with reduced classifier complexity training algorithm and its application in control [D].Hang- [J].Journal of Machine Learning Research,2006,7 zhu:zhejiang University,2006. (7):1493-1515. [41]MA J H,THEILER J,PERKINS S.Accurate on-line sup- [55]LI Qing,JIAO Licheng,HAO Yingjuan.Adaptive simpli- port vector regression[J].Neural Computation,2003,15 fication of solution for support vector machine[J].Patter (11):2683-2703. Recognition,2007,40(3):972-980. [42]VOJISLAV K,MICHAEL V,HUANG Teming.On the e- [56 ]SUMEET A,SARADHI VV,HARISH K.Kemel-based quality of kemel AdaTron and sequential minimal optimiza- online machine learning and support vector reduction[J]. tion in classification and regression tasks and alike algo- Neurocomputing,2008,71(9）:1230-1237. rithms for kemnel machines[C]//European Symposium on [57]CRAMMER K,KANDOLA J,SINGER Y.Online classifi- Artificial Neural Networks.Bruges,Belgium:D-side Publi- cation on a budget[C]//Advances in Neural Information cations,2003:215-222. Processing Systems.Whistler,Canada,2003:225-232. [43]YAAKOV E,SHIE M,RON M.Sparse online greedy sup- [58 ]WESTON J,BORDES A,BOTTOU L.Online and off- port vector regression [C]//Machine learning:ECMI line)on an even tighter budget[C]//Proceedings of the 2002.Berlin:Springer-Verlag,2002:84-96. Tenth Interational Workshop on Artificial Intelligence and [44]KIVINEN J,SMOLA A J,WILLIAMSON R C.Online Statistics.Barbados,2005:413-420. leaming with kemels[J].IEEE Trans on Signal Process- [59]DEKEL O,SHWARTZ SS,SINGER Y.The forgetron:A ing,2004,52(8):2165-2176. kemnel-based perceptron on a fixed budget[Cl//Advances [45]SMALE S,YAO Y.Online learning algorithms[J].Foun- in Neural Information Processing Systems.Vancouver,Can- dations of Computational Mathematics,2006,6(3):145- ada,2005:259-266. 170. [60]OFER D,YORAM S.Support vector machines on a budget [46]YING Yiming,ZHOU Dingxuan,Online regularized classi- [C]//Advances in Neural Information Processing Sys- fication algorithms[J].IEEE Trans on Information Theo- tems.Whistler,Canada,2006:345-352. y,2006,52(11):47754788. [61]JOACHIMS T.Training linear SVMs in linear time[C]// [47]BIANCHI N C,CONCONI A,GENTILE C.On the gener- International Conference on Knowledge Discovery and Data alization ability of on-line leaming algorithms[J].IEEE Mining(KDD).New York,USA,2006:217-226. Trans on Information Theory,2004,50(9):2050-2057. [62]SHWARTZ S S,SINGER Y,SREBRO N.Pegasos:Pri- [48]BIANCHI N C,GENTILE C.Improved risk tail bounds for mal estimated sub-gradient solver for SVM[C]//Proceed-
第6期 王书舟，等：支持向量机的训练算法综述 475。 ings of the Twenty-Fourth International Conference on Ma- [75]TRAFALIS T B,GILBERT R C.Robust classification and chine Learning(ICML2007)):Corvalis,USA,2007:807- regression using support vector machines [J].European 814. Journal of Operational Research,2006,173(3))::893- [63]SMOLA A J,VISHWANATHAN SV N,QUOC V L.Bu- 909. ndle methods for machine leaming[C]l//Advances in Neu- [76]MITRA P,MURTHY C A,PAL S K.A probabilistic ac- ral Information Processing Systems.Vancour,Canada, ive support vector learning algorithm[J].IEEE Trans on 2008. Pattern Analysis and Machine Intelligence,2004.26(3)): [6].CHEN PH,LIN CJ,SCHLKOPF B.A tutorial on v-sup- 413-418. port vector machines [J].Applied Stochastic Models in [77]TSANG I W,KWOKJT,ZURADA J M.Generalized Business and Industry,2005,21(2)):111-136. core vector machines[J]l.IEEE Trans on Neural Net- [65]]KAZUSHI I.Effects of kernel function on v-support vector works,.2006,17(5)）:1126-1140. machines in extreme cases[J].IEEE Trans on Neural Net- [78]ZANNI L.SERAFINI T.ZANGHIRATI G.Parallel soft- works,2006,17(1),:1-9. ware for training large scale support vector machines on [66]MANGASARIAN O L,WILD E W.Multisurface proximal multiprocessor systems[J].Journal of Machine Learning support vector machine classification via generalized eigen- Research,2006,7(7):1467-1492. values[J]..IEEE Trans on Pattern Analysis and Machine [赵春晖，陈万海，郭春燕.多类支持向量机方法的研究 Intelligence,2006,28(1)1:69-74 现状与分析[刀1.智能系统学报，2007,2(4)：11-17. [67]LEE Y J,HUANG S Y.Reduced support vector ma- ZHAO Chunhui,CHEN Wanhai,GUO Chunyan.Re- chines:a statistical theory[J].IEEE Trans on Neural Net- search and analysis of methods for multiclass support vector works,2007,18(1)):1-13. machines[J].CAAI Transactions on Intelligent Systems, [68]ANTHONY K,PHILIPPE D W.Comments on"pruning 2007,2(4)311-17. error minimization in least squares support vector ma- [80]THEODORIDIS S,MAVROFORAKIS M.Reduced convex chines"[J].IEEE Trans on Neural Network,2007,18 hulls::a geometric approach to support vector machines ②)：606609. ]IEEE Signal Processing Magazine,2007,24(3)): [60]JIAO Licheng BO Liefeng WANG Ling Fast sparse ap- 119-122. proximation for least squares support vector machine[J]. [81]BRUZZONE L,CHI M.MARCONCINI M.A novel trans- IEEE Trans on Neural Network,2007,18(3)):685-697. ductive SVMs for semi-supervised classification of remote- [70]]WANG Defeng,DANIEL S Y,ERIC CC T,Weighted ensing images[J]].IEE Trans on Geoscience and Re- mahalanobis distance kernels for support vector machines ote Sensing,2006,44(11)):3363-3373. I.IEEE Trans on Neural Networks,2007,18(5): 8]ASTORINO A,FUDULI A.Nonsmooth optimization tech- i453-1462. niques for semisupervised classification[J]].IEEE Trans [71]DU Shuxin,CHEN Shengtan.Weighted support vector ma- on Pattern Analysis and Machine Intelligence,2007.29 chine for classifications[C]//IEEE International Confer- 12:2135-2142.. ence on Systems,Man and Cybernetics.Hawaii,USA, 作者简介： 2005,4::3866-3871. 王书舟，男，1972年生，博士研究 [72]CAWLEY G C.An empirical evaluation of the fuzzy kemel 生，主要研究方向为支持向量机建模、 perceptron[J].IEEE Trans on Neural Networks,2007, 直升机控制与仿真.发表学术论文多 18(3))÷935-937 篇，6篇被EI检索。 [73]]HAO P Y,CHIANG J H.Fuzy regression analysis by support vector learning approach[J].IEEE Trans on Fuzzy Systems,2008,16(2)):428-441. 伞治，男，1951年生，教授，博士 [74]]CHUANG CC,SU SF,JENGJT,et al.Robust support 生导师.中国系统仿真学会理事.主要 ector regression networks for function approximation with 研究方向为复杂大系统的系统控制与 outliers[J].IEEE Trans on Neural Networks,2002,13 仿真.获国家科技进步二等奖2项，三 6:1322-1330 等奖1项，省部级科技进步奖多项.发 表学术论文多篇，40余篇被EI收录
[76] MITRA P,MURTHY C A,PAL S K. A probabilistic acive support vector learning algorithm[J] . IEEE Trans on Pattern Analysis and Machine Intelligence,2004,26(3) : 413-418. [68] ANTHONY K,PHILIPPE D W. Comments on"pruning error minimization in least squares support vector machines"[J]. IEEE Trans on Neural Network,2007,18 (2) : 606-609. [63] SMOLA A J,VISHWANATHAN SV N,QUOC V L. Bundle methods for machine learning[ C] //Advances in Neural Information Processing Systems. Vancour, Canada, 2008. 伞 冶,男,1951年生,教授,博士 [81] BRUZZONE L,CHI M,MARCONCINI M. A novel transductive SVMs for semi-supervised classification of remoteensing images[J] . IEE Trans on Geoscience and Remote Sensing,2006,44(11) :3363-3373. ings of the Twenty-Fourth International Conference on Machine Learning(ICML2007) :Corvalis,USA,2007: 807- 814. [75] TRAFALIS T B,GILBERT R C. Robust classification and regression using support vector machines [J] . European Journal of Operational Research,2006,173(3) : 893- 909. [70] WANG Defeng,DANIEL S Y,ERIC C C T,Weighted mahalanobis distance kernels for support vector machines [J] . IEEE Trans on Neural Networks,2007,18(5) : i453-1462. [69]JIAO Licheng,BO Liefeng,WANG Ling. Fast sparse approximation for least squares support vector machine[J]. IEEE Trans on Neural Network,2007,18(3) :685-697. [71] DU Shuxin,CHEN Shengtan. Weighted support vector machine for classifications[C] //IEEE International Conference on Systems,Man and Cybernetics. Hawaii,USA, 2005,4: 3866-3871. [64] CHEN PH,LIN CJ, SCHLKOPF B. A tutorial on v-support vector machines [J] . Applied Stochastic Models in Business and Industry,2005,21(2) :111-136 [78] ZANNI L, SERAFINI T,ZANGHIRATI G. Parallel software for training large scale support vector machines on multiprocessor systems[J] . Journal of Machine Learning Research,2006,7(7) : 1467-1492. [77] TSANG I W,KWOKJT,ZURADA J M. Generalized core vector machines[J] . IEEE Trans on Neural Networks,2006,17(5) :1126-1140. [80] THEODORIDIS S,MAVROFORAKIS M. Reduced convex hulls: a geometric approach to support vector machines [J] . IEEE Signal Processing Magazine,2007,24(3) : 119-122. [79] 赵春晖,陈万海,郭春燕.多类支持向量机方法的研究 现状与分析[J] .智能系统学报,2007,2(4) :11-17. ZHAO Chunhui,CHEN Wanhai,GUO Chunyan. Research and analysis of methods for multiclass support vector machines[ J] . CAAI Transactions on Intelligent Systems, 2007,2(4) :11-17. [74] CHUANG C C,SU SF,JENGJT,et al. Robust support ector regression networks for function approximation with outliers[J]. IEEE Trans on Neural Networks,2002,13 (6) : 1322-1330 [73] HAO P Y, CHIANG J H. Fuzy regression analysis by support vector learning approach[ J]. IEEE Trans on Fuzzy Systems,2008,16(2) :428-441. 王书舟,等: 支持向量机的训练算法综述 [66] MANGASARIAN O L,WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J] . IEEE Trans on Pattern Analysis and Machine Intelligence,2006,28(1) :69-74. [67] LEE Y J,HUANG S Y. Reduced support vector machines: a statistical theory[J]. IEEE Trans on Neural Networks,2007,18(1) : 1-13. 第6期 [72] CAWLEY G C. An empirical evaluation of the fuzzy kemel perceptron[ J]. IEEE Trans on Neural Networks,2007, 18(3) :935-937. 作者简介: 475。 [82] ASTORINO A,FUDULI A. Nonsmooth optimization techniques for semisupervised classification[J] . IEEE Trans on Pattern Analysis and Machine Intelligence,2007,29 (12) :2135-2142. 王书舟,男,1972年生,博士研究 生,主要研究方向为支持向量机建模、 直升机控制与仿真.发表学术论文多 篇,6 篇被EI检索. [65] KAZUSHI I. Effects of kernel function on v-support vector machines in extreme cases[J]. IEEE Trans on Neural Networks,2006,17(1) : 1-9. 生导师.中国系统仿真学会理事.主要 研究方向为复杂大系统的系统控制与 仿真.获国家科技进步二等奖2项,三 等奖1项,省部级科技进步奖多项.发 表学术论文多篇,40余篇被EI收录