第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,<a,w>, 的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)+<w'-w,u>, 此外，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:)-<at+l,W:> 并不是直接求解此优化问题或其对偶形式，而是构