支持向量机算法综述

1、文章编号:100220411(2002012045206支持向量机训练算法综述刘江华程君实陈佳品(上海交通大学信息存储研究中心上海200030摘要:本文介绍统计学习理论中最年轻的分支支持向量机的训练算法,主要有三大类:以SVM2 ligh t为代表的分解算法、序贯分类方法和在线训练法,比较了各自的优缺点,并介绍了其它几种算法及多类分类算法.最后指出了支持向量机具体实现的方向及其在模式识别、数据挖掘、系统辨识与控制等领域中的应用.a关键词:支持向量机;训练算法;统计学习理论中图分类号:T P391.4文献标识码:BSUPPORT VECT OR M ACH INE TRA IN ING AL G

2、 OR ITH M:A REV IE WL I U J iang2huaCH EN G Jun2sh iCH EN J ia2p in(Inf or m ation S torag e R esearch Center,S hang hai J iaotong U niversity,S hang hai200030Abstract:T h is article in troduced the train ing algo rithm fo r the new est b ranch of statistic learn ing theo2 ry,SVM(Suppo rt V ecto r M

3、 ach ine,w h ich can be classified in to th ree catego ries:the first is the D ecompo si2 ti on A lgo rithm,w ho se delegate is SVM ligh t2,the second is sequence algo rithm,the th ird is on line train ing algo rithm.A ll the th ree k inds of algo rithm sadvan tages and disadvan tages w ere analysed

4、.A nd o ther algo2 rithm s and m u lti2class algo rithm s are in troduced too.T he fu tu re directi on and app licati on of SVM in pattern recogn iti on and data m in ing,and so on w ere in troduced.Keywords:suppo rt vecto r m ach ine,train ing algo rithm,statistical learn ing theo ry1引言(I n troduct

5、ion统计学习理论是目前针对小样本统计估计和预测学习的最佳理论,它从理论上系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题,而支持向量机作为统计学习理论的实现方法,受到广大的研究者的注意.统计学习理论因为对有限样本情况下模式识别中的一些根本性问题进行了系统的理论研究,在很大程度上解决了模型选择与过学习问题、非线性和维数灾问题、局部极小点问题等,因此成为研究的热点24,22.24、43分别对支持向量机的原理作了简要的介绍,并和神经网络作了比较,本文则对支持向量机的训练算法进行详细讨论.V ap n ik6将支持向量机问题归

6、结为一个二次型方程求解问题.V ap n ik通过对线性不可分的两类问题的最优分类形式提出的.即使两类无错误地分开,并使两类的分类间隙(M argin最大.问题的数学形式为:U(w,N=12(ww+Cli=1N is.t.y i(wx i+b1-N i,i=1,lN i0,i=1,l.通过求其对偶问题,归结为一个二次函数极值问题:W(A=li=1A i-12li,j=1y i y j A i A j K(x i,x js.t.0A iC,i=1,lli=1A i y i=0分类判别函数为:f(x=sign(li=1A i y i K(x,x i+b对于这个二次规划问题,经典的解法有积极方第31

7、卷第1期2002年2月信息与控制Info rm ati on and Con tro lV o l.31,N o.1Feb.,2002a收稿日期:2001-06-05集法、对偶方法、内点算法28等,但是当训练样本增多时,这些算法便面临着维数灾,或者由于内存的限制,而导致无法训练,无法应用SVM进行模式分类和函数估计.所以如何训练大训练集的SVM便成为SVM实际应用的瓶颈问题.2各种训练算法介绍及比较(I n troduction to d ifferen t tra i n i ng a lgor ith m s and com-par ison between themm in V(d=g(

8、A(tT ds.t.y T d=0;d i0fo r i:A i=0;d i0fo r i:A i=C;-1d1;ßd i:d i0ß=q;解上述最优问题即得工作集.在实现细节上, Joach i m s对常用的参数进行缓存(Cache,并对Q P 问题进行Sh rink ing,从而使算法能较好地处理大规模的训练集问题.Ch ih2W ei H su11通过改变SVM的提法提出了一种类似1中的简单训练算法B SVM.主要是针对SVM得到一种不同的数学提法,从而使算法简单易行.Ch ih2W ei H su和Ch ih2Jen L in综合S.S. Keerth i10中的

9、修改过的S M O和SVM ligh t中的工作集选择算法,用C+实现一个库L I B SVM,可以说是使用最方便的SVM训练工具.L I B SVM供用户选择的参数少,用训练特大训练集时,还是使用灵64信息与控制31卷活的SVM light或S M O.第二类是序贯分类法,基本思想是考虑训练样本序贯加入,同时考虑其对支持向量有何影响.46基于感知机中的A datron算法,对L agrange系数和支持向量机.特点是训练样本序贯进入,L agrange 系数的改变采用梯度法.47提出了将另一种梯度序贯算法,特点是将SVM原问题中的偏置b也看作系数,从而使该梯度算法适合软间隔(Soft m a

10、r2 gin和回归情形.Scho b lkop f18,19提出了一个新的SVM分类器v2SVM,将待优化问题变为:m in 12wT w-vp+1lli=1N is.t.y i(w T U(x i+bQ-N i,N i0,i=1,l,Q0其中,x i是训练样本向量,y i=1o r-1表示对应的类.x i被函数映射到一个高维空间.M ing_H suan Yang40提出了训练支持向量机的几何方法.主要是利用了训练集中的集合信息,提出了“卫向量”(Guard vecto r的概念,“卫向量”即为通过该向量能使输入空间线性可分的向量.所有的“支持向量”都是“卫向量”,但反之不成立.当训练集合较

11、大时,可以先找出“卫向量”,再以“卫向量”构成传统的Q P问题求出“支持向量”.“卫向量”的求解是通过判断其对偶空间中的线性规划问题的可行性而不是求其解,从而使问题大大简化.试验表明该算法求得的最优分类面和传统Q P问题一样,但速度要快30倍,内存要求为传统的14.主要原因是“卫向量”只是“支持向量”的20倍左右.m inw,b,eJ=12wT w+C12Nk=1e2k,s.t.y kw T U(x k+b=1-e k,k=1,N定义L agrange函数L=J-Nk=1A ky kw T U(x k+b-1+e k其中A k为L agrange乘子,根据KT T最优条件:5L5w=0w=Nk

12、=1A k y k U(x k,5L5b=0w=Nk=1A k y k=0,5L5e k=0A k=Ce k,5L5e k=0y kw T U(x k+b-1+e k=0对于k=1,N上式消去w和e,得到如下线性系统:741期刘江华等:支持向量机训练算法综述YTYZ Z T+C -1 I bA=1其中,Z =U (x 1T y 1;U (x N T y N ,Y =y 1;y N ,1=1;1,e =e 1;e N ,A =A 1;A N 上述线性系统用最小二乘法即可解.44提出了SO R 方法,通过在原目标函数中加一项b 2,从而对偶问题多了一项,而约束条件少了一项等式约束,变为边界约束条件

13、下二次规划问题,适合迭代求解.同时应用矩阵分解技术,每次只需更新L agrange 乘子的一个分量,从而不需将所有样本载入内存,提高了收敛速度.以上的算法,大部分都是针对两类问题,那么对于多类问题,SVM 的算法有以下几种.标准算法7是,对于N 类问题构造N 个两类分类器,第i 个SVM 用第i 类中的训练样本作为正的训练样本,而将其它的样本作为负的训练样本.这个算法称为12a 2r (12agin st 2rest .最后的输出是两类分类器输出为最大的那一类(此时,两类分类器的判决函数不用取符号函数sgn .其缺点是它的推广误差无界.另外一个算法是由Knerr 17提出,该算法在N 类训练样

14、本中构造所有可能的两类分类器,每类仅仅在N 类中的2类训练样本上训练,结果共构造K =N (N -12个分类器,我们称该算法为12a 21(12agin st 21.组合这些两类分类器很自然地用到了投票法,得票最多(M ax W in s 的类为新点所属的类.U .K re B el18用该方法训练多类SVM 取得了很好的结果.12a 21算法的缺点是:1如果单个两类分类器不规范化,则整个N 类分类器将趋向于过学习;2推广误差无界;3分类器的数目N (N -12随类数N 急剧增加,导致在决策时速度很慢.J .W eston 12提出了两种新的多类SVM 算法.其一是qp 2m c 2sv 算法

15、,它很自然地在构造决策函数时,同时考虑所有的类.将原始优化问题推广为:U (w ,N=12km =1(w m w m +Cli =1m y iNmis .t .(w i x i +b y i (w m x i +b m +2-N miN mi 0,i =1,l m 1,k y i 相应地决策函数变为:f (x =arg m ax k(w i x +b i ,i =1,k当k 取2时,和两类分类问题等价.其二是:线性规划的方法lp 2m csv .原始最优问题变为:li =1A i+Cli =1j y iN i,s .t .m :y m =y iA m K (x i ,x m +b y iA n

16、 K (x i ,x n +b y j +2-N ji A i 0,N j i 0,i =1,l ,j 1,k y i决策函数为:f (x =arg m ax n(i :y i =nA iK (x ,x i+b n 以上两方法的缺点是计算量都比较大,优点是得到的决策分类面的支持向量机的数量均比常规方法少.关于多类的L S 2SVM 分类器,J .A .K .Suyken s29使用了类似J .W eston 12中的方法一.P latt 16等提出了一个新的学习架构:决策导向的循环图(D ecisi on D irected A cyclic Grap h ,DDA G ,将多个两类分类器组合

17、成多类分类器.对于N 类问题,DDA G 含有N (N 212个分类器,每个分类器对应两类.其优点是推广误差只取决于类数N ,和节点上的类间间隙(M argin ,而与输入空间的维数无关,根据DDA G 提出算法DA GSVM ,DDA G 的每个节点和一个12a 21分类器相关,其速度显著比标准算法或取最大算法(M an W in s 快.总之,以上的算法为SVM 的实用起到了推动作用,尤其是有些算法还适用于回归和函数估计问题,如:S M O .3支持向量机的应用及发展方向(Appl ica -tion and future d irection of SV M 支持向量机在模式识别32,3

18、6(字符识别42、文本自动分类25、人脸检测1,27,39、头的姿态识别41、函数逼近23,33、数据挖掘37和非线性系统控制50中均有很好的应用.在1中用2阶多项式核,上界C 设为200.训练样本是50000个19乘19大小的人脸图像和45000个同样大小非脸图像.训练算法是O suna 提出的分解算法.训练出来的SVM 分类器同Sung 38的NN 分类器进行了比较,检测速度有所提高,但错误率也比Sung 的方法高.其应用主要在静止图像中有无人脸.39使用了这个SVM 来实时检测人脸,速度是每秒25帧.84信息与控制31卷本文综合介绍了现有的SVM训练算法,说明了各种的算法的思路和优缺点.

19、今后SVM的训练算法的研究方向主要是确定不同的优化目标,根据KKT约束优化条件寻找大规模训练样本下的实用算法,应用于模式识别时的多类问题目前还没有特别好的算法.一种训练算法不但要有理论上的收敛的证明,同时也应该有实用的可行的算法实现,这样SVM的应用才会更广泛.目前在线训练是研究重点,因为这是应用于系统辨识和控制及信号处理中的关键.参考文献(R eferences1O suna E,F reund R,Giro si F.T raining suppo rt vecto r m a2 ch ines:A n app licati on to face detecti on.In P rocee

20、dings of CV PR97,Puerto R ico,19972Joach i m s T.M ak ing large2Scale SVM L earning P ractical.A d2 vances in Kernel M ethods-Suppo rt V ecto r L earning,Sch?lkopf B.et al.(ed.,M IT P ress,19994Joach i m s T.T ext Catego rizati on w ith Suppo rt V ecto r M a2 ch ines:L earning w ith M any R elevant

21、Features.P roc.of the European Conf.on M ach ine L earning,Sp ringer,19985Joach i m s T.M ak ing large-Scale SVM L earning P ractical.L S82R epo rt,24,U niversity Do rtm und,L S V III2R epo rt,1998 6V apnik V N.T he N ature of Statistical L earning T heo ry.Sp ringer,19957V apnik V N.Statistical L e

22、arning T heo ry.N ew Yo rk,W iley, 19988Co lin C.A lgo rithm ic A pp roaches to T raining Suppo rt V ecto r M ach ines:A Survey.P roceedings of ESANN2000(D-Facto Publicati ons,Belgium,2000,27369John C P.Fast T raining of Suppo rt V ecto r M ach ines using Se2 quential M ini m al Op ti m izati on.In

23、Scho lkopf B.et al(ed.,A dvances in Kernel M ethods2Suppo rt V ecto r L earning,Cam2bridge,M A,M IT P ress,1999,18520811Ch ih W H,et al.A Si m p le D ecompo siti on M ethod fo r Suppo rt V ecto r M ach ines.T echnical repo rt,N ati onal T ai w an U niversi2 ty,199912W eston J,W atk ins C.M ultilass

24、Suppo rt V ecto r M ach ines.TR CSD TR9804,D epartm ent of Computer Science Egham, Surrey TW200EX,England,199813Chang C C,H su C W,L in C J.T he analysis of decompo siti on m ethods fo r suppo rt vecto r m ach ines.In W o rk shop on Suppo rt V ecto r m ach ines,I JCA I,199914Keerth i S S,et al.A Fas

25、t Iterative N earest Po int A lgo rithmfo r Suppo rt V ecto r M ach ine C lassifier D esign.TR-ISL-99-03D ep t.of CS and A uto.Indian Institute of Science Banga2 lo re,India,199915Keerth i S S.Convergence of a Generalized S M O A lgo rithm fo r SVM C lassifier D esign TR CD-00-01Contro l D ivisi on

26、D ep t.of M echa.and P rod.Engineering N ati onal U niversity of Singa2 po re Singapo re,200016P latt J,et al.L arge M argin DA Gs fo r M ulticlass C lassifica2 ti on,in A dvances in N eural Info rm ati on P rocessing System s 12,M IT P ress,2000,54755317Knerr S,et al.Single2layer learning revisited

27、:A stepw ise p ro2 cedure fo r building and training a neural netwo rk.In Fogel m an -Soulie et al.(ed.,N eurocomputing:A lgo rithm s,A rch itec2 tures and A pp licati ons,NA TO A S I.Sp ringer,199018K re?el U.Pairw ise classificati on and suppo rt vecto r m ach ines.In B.Scho lkopf,ed.A dvances in

28、Kernel M ethods:Suppo rt V ecto r L earning,pages M IT P ress,Cam bridge,M A,1999, 25526819Sch?lkopf B,et al.E sti m ating the suppo rt of a h igh2di m ensi on2 al distributi on.TR99-87,M icro soft R esearch.199920Scho b lkopf B,et al.N ew suppo rt vecto r algo rithm s.N eural Computati on,2000,12:1

29、083112126Zhang X.U sing class2center vecto rs to build suppo rt vecto r m ach ines.In P roceedings of NN SP99,199927L u CY,Yan P F,Zhang C S.Face recogniti on using suppo rt vecto r m ach ine,In po rc.O f I CNNB98,Beijiing,1998,652 65530M assi m iliano P,A lessandro V.O bject R ecogniti on w ith Sup

30、2 po rt V ecto r M ach ines,IEEE T rans.on PAM I,1998,20(6: 63764631Suykens J A K,J V andew alle.L east squares suppo rt vecto r m ach ine classifiers.N eural P rocessing L etters,1999,9(3: 29330032Burges C J C.A T uto rial on Suppo rt V ecto r M ach ines fo r Pat2 tern R ecogniti on.Know ledge D is

31、covery and D ata M ining, 1998,2(233Smo la A J,Scho lkopf B.A tuto rial on suppo rt vecto r regres2 si on.N euroCOL T TR N C-TR-98-030,Royal Ho llow ay Co llege,U niversity of L ondon,U K,1998941期刘江华等:支持向量机训练算法综述50 信息与控制 模式识别与人工智能, 2000, 13 (3 : 285 290 31 卷 34 Pon til M , V erri M. Suppo rt vecto r

32、 m ach ines fo r 3 - d ob ject recogn ition. IEEE T ran s. PAM I, 1998, 20: 637 646 35Roobaert D. I p roving the generalization of linear suppo rt vec2 m to r m ach ines: an app lication to 3d ob ject recogn ition w ith clu t2 tered backg round. In P roc. SVM W o rk shop at IJCA I99, 44 O lvi L M ,

33、D avid R M. Successive O verrelax iation fo r Suppo rt V ecto r M ach ines. IEEE T ran s. O n N eu ral N etw o rk s. 1999, 10 (5 : 1032 1037 45 Ronan C, Sam y B. Suppo rt V ecto r M ach ines fo r L arge 2Scale R eg ression P rob lem s, I I P - RR 00 - 17. h ttp: DA ap. ch, 2000 46 F riess T T , et a

34、 l. T he kernel2adatron algo rithm : A fast and si p le m learn ing p rocedu re fo r suppo rt vecto r m ach ines, www. id i2 Stockho lm , Sw eden, 1999 36 Roobaert D , H u lle M M V an. V iew 2based 3d ob ject recogn ition w ith suppo rt vecto r m ach ines. In IEEE N eu ral N etw o rk s fo r Signal

35、P rocessing W o rk shop , 1999 37B rad ley P. M athem atical P rog ramm ing A pp roaches to M ach ine L earn ing and D ata M in ing. PhD thesis, U n iversity of W iscon 2 sin, Com p u ter Sciences D ep artm en t, M ad ison, W I, U SA , TR 2 98211, 1998 38Sung K, Pogg io T. Exam p le2base L earn ing

36、fo r V iew 2base H u 2 . . m an Face D etection. A. I M em o 1521, M IT A. I L ab. , D e2 cem ber 1994 39 Kum ar V , Pogg io T. L earn ing 2based A pp roach to R eal T i e m T rack ing and A nalysis of Faces. In: P roceed ing s of the Fou rth In ternational Conference on Face and Gestu re R ecogn ition, Grenob le, F rance, M arch, 2000 40 Yang M H , A hu ja N. A Geom etric A pp roach to T rain Suppo rt V ecto r M ach ines, In P roceed ing s of CV PR 2000, H ilton H ead ICM L 98, 1998: 188 196 47 V ijayakum ar S, W u S. Sequen tial Suppo rt V ecto r C lassifiers and R eg