支撑矢量机推广能力分析.pdf

支撑矢量机推广能力分析周伟达,张 莉,焦李成(西安电子科技大学雷达信号处理重点实验室,西安710071)摘 要:本文针对两种不同用途的支撑矢量机,分类支撑矢量机和回归支撑矢量机,分别证明了它们的一些几何性质,从这些性质出发讨论了这两种支撑矢量机对新增样本的推广能力,新增样本对支撑矢量,非支撑矢量的影响以及新增样本本身的一些特点,得到了一些非常有价值的结论.从这些结论可以看出支撑矢量机对新增样本具有良好的推广能力,即对新增样本的良好的包容性和适应性,并且支撑矢量机是一种可积累的学习模型.关键词:分类支撑矢量机;回归支撑矢量机;学习机;KKT条件;可积累性中图分类号:O 2315 文献标识码:A 文章编号:037222112(2001)0520590205An Analysis of SVMs Generalization PerformanceZHOU Wei2da,ZHANGLi,JIAO Li2cheng(National Key Lab.for Radar Signal Processing,Xidian University,Xian710071,China)Abstract:Some geometry of Support Vector Machines for classification and regression is described and proven.And then thegeneralization performance of SVMs on newly2added samples is discussed.Through the analysis of the propertyof newly2added samplesand the effect of them on support vectors and non2support vectors,some valuable results are presented.These enable us to concludethat SVM has a good compatibility,adaptability and generalization performance for newly2added samples and is a hereditable learningmodel.Key words:support vector classification;support vector regression;learning machines;KKT conditions;hereditability1 引言 自1970年以来,Vapnik等人发展了一种新的学习机 支撑矢量机.与现有的学习机包括神经网络,模糊学习机,遗传算法,人工智能等相比,它具有许多的优点14:坚实的理论基础5和较好的推广能力,强大的非线性处理能力和高维处理能力.现在支撑矢量机快速算法有Chunking算法7,Os2una算法8,SMO算法9,针对不同的应用有分类支撑矢量机,回归支撑矢量机等.但是支撑矢量机最突出的优势还在于它强大的推广能力,它能在训练样本较少的情况下得到较好的效果.关于支撑矢量机的推广能力,尤其是针对小样本训练的推广能力,Vapnik等人已作了详细的分析1,5.他们对于支撑矢量机推广能力的讨论都是围绕着这样一个问题,即先验知识不够,训练样本缺乏,在这种情况下训练的支撑矢量机用于实际分类和回归分析时性能如何?但实际情况中推广能力还应包括另一方面的问题.上面的这种推广能力的分析实际上是相当于对新增测试样本的分析,而没有涉及对新增训练样本的分析.这儿所谓的新增测试样本实际上是指训练好的支撑矢量机后实际中新出现的样本,对于这些样本预先是不知道真正的输出结果的.新增训练样本是指训练好的支撑矢量机后,又出现了一些已知输出结果的样本,这些训练样本需要原支撑矢量机来进一步学习.新增训练样本对于实际问题是非常常见而且是非常合理的,实际中样本的采集都是一步一步而来,知识也都是逐步积累.这样一个非常符合常理的问题,在现在的大部分的学习机中仍得不到合理解决,许多学习机对于这一问题几乎无能为力,仅仅是把新样本加进来,重新开始进行训练.这其中的浪费是显而易见的,它们完全抛弃了已有的知识,这是有悖于常理的.那么支撑矢量机对于这种新增的训练样本的推广能力如何?它如何来处理这些新增的训练样本?它能否完成这种可积累性的学习?已经成为大家非常关注的问题,同时它又是支撑矢量机应用的基础.本文围绕着这一问题进行了研究,得到了一些有价值的结果.2 分类支撑矢量机 对于分类问题,支撑矢量机把分类边界最大最终归结为如下凸半正定二次规划问题:maxW()=li=1i-12li,j=1ijyiyjK(xixj)(1)s.t.li=1iyi=0(2)i0,C,i=1,l(3)收稿日期:2000206219;修回日期:2001201210基金项目:国家“863”项目(No.863230620620621)和教育部博士点基金第5期2001年5月电 子 学 报ACTA ELECTRONICA SINICAVol.29No.5May2001 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.判决函数为:f(x)=li=1iyiK(xix)+b(4)y=sgn(f(x)(5)下面我们引用数学优化中的一个重要定理.KKT条件9:由于Qij=yiyjK(xixj)是半正定的,对于上述规划的一个可行解,当且仅仅对于每一个x都满足KKT条件(由Lagrange乘子确定)时,才是上述规划的最优解.上述规划的KKT条件也特别简单:i=0yif(xi)1,0 iCyif(xi)=1i=Cyif(xi)1(6)由于上述规划不一定是严格的凸规划(Q为半正定),所以最优解可能不止一个,但每个最优解都必须满足KKT条件.211 分类支撑矢量机基本几何知识对于已训练好的支撑矢量机,定义这样的分类支撑矢量机等高线.定义1 把由f(x)=li=1iyik(xix)+b=h(其中h为一组常量)确定的一组曲线称为分类支撑矢量机等高线.如图1,绘出了三条h=1,0,-1的分类支撑矢量机等高线.图1 以二维线性可分支撑矢量机为例,i=0的样本分布在f(xi)1或f(xi)-1区域内,0 iC的样本分布在等高线f(xi)=1或f(xi)=-1上,i=C的样本分布在-1f(xi)1的区域内.定理1 分类支撑矢量机中,对应于=0的样本分布于那两条虚线(f(x)=-1和f(x)=1)之外的区域(含两条虚线);对应于0 C的样本分布在两条虚线上.对应于=C的样本分布于两条虚线(f(x)=-1和f(x)=1)之间(含两条虚线).即:i=0:f(xi)1或f(xi)-1;0 iC:f(xi)=1或f(xi)=-1;i=C:-1f(xi)1;(7)如图1所示.证明见附录1.现在考虑新增训练样本,由于新增训练样本并未得到原支撑矢量机训练,令此时这些样本所对应的Lagrange乘子为0.定理2 新增训练样本违背KKT条件的充要条件为新增样本位于-1 f(xi)1区域中(其中f为原已训练好的支撑矢量机的决策函数(4).证明见附录2.由上述两定理可见分类支撑矢量机在最大化边界的过程中,其几何意义非常明确而且直观.这两个定理有助于直观地理解支撑矢量机的分类机理,同时由这两个定理出发,将在后面得到更具价值的性质.212 新增训练样本分析下面来讨论新增训练样本对于原训练好的支撑矢量机,以及在原支撑矢量机训练中得到的支撑矢量,非支撑矢量和它们所对应的Lagrange乘子的影响.定理3 如果新增训练样本中存在某些样本违反了KKT条件,则在这些违反违背KKT条件的样本中肯定存在着部分或全部(至少一个)新支撑矢量(新的支撑矢量是指如果把原有样本和新增样本全部拿来训练得到的新支撑矢量);没有违背KKT条件的新增样本中肯定不存在新支撑矢量.定理证明见附录3.定理3可以说是一个非常有用的性质.由于支撑矢量机的训练只受支撑矢量的影响,非支撑矢量对训练过程不起作用.所以新增训练样本中只有那些违反KKT条件的样本对支撑矢量机的可累积性学习起作用.依据这个性质,就可以大大简化支撑矢量机对新增训练样本的操作.首先对于新增训练样本中没有违反原支撑矢量机KKT条件的样本,说明原支撑矢量机已经包含了这部分样本的信息,不需要再对这部分样本学习.其次对于新增训练样本中那些违反KKT条件的样本,说明原支撑矢量机没有包含这部分样本的信息需要对这部分样本进行学习.这种学习不仅没有破坏原有的支撑矢量机包含的信息而且大大简化了对于新增样本的学习.所以这种学习是可积累性的.定理4 如果新增训练样本中存在违反KKT条件的样本,则原分类支撑矢量机中非支撑矢量有可能转化为支撑矢量.定理的证明可以通过例子来说明:一个二维线性的支撑矢量机如图2,其中原分类支撑矢量机(第一次训练)时每类均为两个样本(一类为(S1,S2),另一类(S3,S4).第一次训练的结果为S1,S2,S3为支撑矢量.现加入样本S5,由于S5违反了原分类支撑矢量机的KKT条件,进行再训练得到支撑矢量为S3,S4,S5.从本例中可以看到,由于样本S5的加入,使得原不是支撑矢量的S4变成了支撑矢量.同时不难看出只要第二类中有位于图中网格区的样本,就有可能成为支撑矢量.同时随着训练样本集的增大,支撑矢量或位于支撑矢量附近的样本将增多,而再生支撑矢量的网格区域将越来越小,即原非支撑矢量变成支撑矢量的可能性越来越小.在此补充一点,虽然本文中所举的例子都是线性支撑矢量机,但是上述的结论对所有核支撑矢量机都是成立的.下面再来分析新增训练样本对原支撑矢量的影响,并分别考虑线性支撑矢量机和非线性支撑矢量机.对于线性支撑矢量机,它的支撑矢量等高线是直线,如果在线性支撑矢量机的某一类中存在两个不同支撑矢量的La2granre乘子满足0 iC,则它的分类边界为平行于过这两点的直线(两点确定一直线),也就是分类边界的斜率由这两点确定,现在向该类中加入样本AddSamples,设这些新增样本中存在违反KKT的样本AKKTAddSamples.则原来的支撑矢195第 5 期周伟达:支撑矢量机推广能力分析 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.量集,将有部分转化为非支撑矢量,除非AKKT全都在原支撑矢量所确定的这条直线上.如图3所示,S1,S2,S3,S4是原样本集,其中S1,S2,S4是支撑矢量,现若加入样本SAdd1,则支撑矢量中S2将变为非支撑矢量,若加入样本SAdd2,则支撑矢量将有4个S1,S2,S4,SAdd2.对于非线性支撑矢量机,新增支撑矢量对原支撑矢量的影响就更复杂.既有可能使原支撑矢量减少,也有可能不变即原支撑矢量全部成为新的支撑矢量.在此不再详细讨论.图2 图中绘出了新增样本前后两次支撑 矢量机训练结果的情况,S5为新增 样本.实线为第一次训练得到的h=-1,0,1等高级,点划线为第二 次训练得到的h=-1,0,1等高线.图3 线性支撑矢量机中,新增 样本对原支撑矢量的影响.图4 以线性回归可分支撑矢量机为例,=011,(3)i=0的样本分布在-011f(xi)011 区域内,0(3)iC的样本分布在等高线f(xi)=011或f(xi)=-011上,(3)i=C 的样本发布在f(xi)011或f(xi)-0113 回归支撑矢量机 类似于分类支撑矢量机,对于回归支撑矢量机也能得到类似的结论.关于回归分析,下面得到的结论适用于所有不同类型的损失函数,在此采用Vapnik的 不敏感损失函数为例,回归支撑矢量机最终把回归问题归结为如下的二次规划:max-12li,j=1(i-3i)(j-3j)k(xi,xj)-li=1(i+3i)+li=1yi(i-3i)(8)s.t.li=1(i-3i)=0(3)i0,C(9)为表示简略,在本文中用(3)表示和3.求解二次规划,得到回归输出函数为f(x)=li=1(i-3i)k(xi,x)+b(10)回归分析的KKT条件9为:(3)i=0|yi-f(xi)|0(3)iC|yi-f(xi)|=(3)i=C|yi-f(xi)|(11)上述二次规划中Qij=K(xixj)是半正定的,最优解可能不止一个,但当且仅当(3)对于每一个x都能使其满足KKT条件时,(3)才是上述规划的最优解.311 回归支撑矢量机基本几何知识对于已训练好的回归支撑矢量机,定义这样的支撑矢量机等高线.定义2 把由f(x)=li=1(i-3i)k(xi,x)+b=h(其中h为一组常量)确定的一组曲线称为回归支撑矢量机等高线.如图4,绘出了三条h=,0,-的回归支撑矢量机等高线.定理5 回归支撑矢量机中,对应于(3)=0的样本分布于那两条虚线(f(x=-和f(x)=)之间的区域(含两条虚线);对应于0 C的样本分布在两条虚线上.对应于=C的样本分布于两条虚线(f(x)=-和f(x)=)之外(含两条虚线).即:(3)i=0,-f(xj)0(3)iC,f(xi)=或f(xi)=-(3)i=C,f(xi)或f(xi)-(12)如图4所示.此定理证明类似于定理1的证明,在此不赘述.现在考虑新增训练样本,由于新增训练样本并未得到原支撑矢量机训练,令此时这些样本所对应的Lagrange乘子(3)i为0.定理6 新增训练样本违反KKT条件的充要条件为新增样本位于f(xi)区域中(其中f为原已训练好的支撑矢量机的决策函数式(10).同样证明与定理2证明类似.建立了这两个定理之后就可以直观地来理解回归支撑矢量机求解一个满足误差要求的回归曲线的几何意义,并揭示其几何机理.从这两个定理出发,将得到类似于分类支撑矢量机的性质.312 新增训练样本分析下面来讨论在回归支撑矢量机中新增训练样本对于原训练好的支撑矢量机,以及在原支撑矢量机训练中得到的支撑矢量,非支撑矢量和它们所对应的Lagrange乘子的影响.定理7 如果新增训练样本中存在某些样本违反KKT条件,则在这些违反KKT条件的样本中肯定存在着部分或全部(至少一个)新支撑矢量(新的支撑矢量是指如果把原有样本和新增样本全部拿来训练得到的新支撑矢量);没有违反KKT条件的新增样本中肯定不存在新支撑矢量.定理的证明类似于定理3.定理7与定理3一样是一个非常有用的性质.它保证了只需对新增训练样本中违反KKT条件的样本进行训练就能得到与所有样本同优的结果.首先对于新增训练样本中没有违背反原支撑矢量机KKT条件的样295 电 子 学 报2001年 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.本,说明原支撑矢量机已经包含了这部分样本的信息,不需要再对这部分样本学习.其次对于新增训练样本中那些违反KKT条件的样本,说明原支撑矢量机没有包含这部分样本的信息需要对这部分样本进行学习.这种学习很好地保持了原有的支撑矢量机包含的信息.所以这种学习也是可积累性的.定理8 如果新增训练样本中存在违反KKT条件的样本,则原回归支撑矢量机中非支撑矢量有可能转化为支撑矢量.类似定理4,也可以通过一个图例来说明:一个线性回归支撑矢量机如图5.其中原回归支撑矢量机(第一次训练)时四个样本(S1,S2,S3,S4).训练的结果为S1,S2,S3为支撑矢量.现加入样本S5,由于S5违反了原支撑矢量机的KKT条件,进行再训练得到支撑矢量为S2,S3,S4,S5.从本例中可以看到,由于样本S5的加入,使得原不是支撑矢量的S4变成了支撑矢量.看来回归支撑矢量机与分类支撑矢量机一样也存在这样的支撑矢量再生区(图5网格区),位于此区域中的矢量有可能转变为新的支撑矢量,这样的区域也将随着训练样本的增加而减少.图5 图中绘出了新增样本前后两次支撑矢量机训练结果的情况,S5为新增样本.实线为第一次训练得到的h=-,0,等高线,点划线为第二次训练得到h=-,0,等高线.关于回归支撑矢量机中新增训练样本对原支撑矢量的影响与分类支撑矢量机非常相似.新增训练样本有可能使原来的支撑矢量变为非支撑矢量.4 结论 本文对于两种不同用途的支撑矢量机(分类支撑矢量机和回归支撑矢量机)首先证明了它们的一些几何性质,这样一方面既有利于比较直观地来理解支撑矢量机的分类机理,同时又能更好地掌握,运用支撑矢量机.特别是低维的支撑矢量机,可以通过绘制支撑矢量机等高线来理解和分析支撑矢量机的运行情况.接着本文讨论了新增样本对支撑矢量机,支撑矢量,非支撑矢量的影响以及新增样本本身的情况.得到的一些结论,对于理解,证明现有的支撑矢量机快速算法非常有益,同时也丰富了对支撑矢量机在各个环节增强其功能的途径,如把先验知识加入支撑矢量机,支撑矢量机进行可积累性的学习等.总之,支撑矢量机与其他的智能学习机相比对于新增样本具有较强的包容能力,适应性和非常强的推广能力,它是一种可进行可积累性学习的学习模型,而且这种积累性学习算法是非常方便的.附录1:定理1证明:对于训练好的支撑矢量机,得到最优解,它满足KKT条件,即对应于i=0yif(xi)1,对应于0 iCyif(xi)=1,对应于i=Cyif(xi)1,把yi=1或yi=-1代入上述三种情况得:i=0,f(xi)1 或 f(xi)-1;0 i 30(2)其中k为模型连接系数,为两模型在30 处的比值.3 算例 针对某型雷达高度计,利用散射模型(2),结合该型雷达高度计的天线照区模型、脉冲亮区、相应的回波功率计算模型、回波DOPPLER谱计算模型以及反射回波信号和散射回波计算模型.可以在试验室对大地回波进行计算.设:天线的发射脉冲功率为1w,脉宽为016s,发射脉冲周期为013ms,发射载波频率为318GHz;天线随载体的运动速率为1000m/s,天线距离大地平面高度为1000米,天线载体的倾角为60,天线辐射宽度为30,天线的发射与接收增益均为0dB.4 结论 利用本文的RCF模型,可以全面地计算各类地面的回波信号,从而可以从轮廓上把握大地回波的波形参数.实用表明,计算生成的回波符合大地回波特征要求,可用于雷达高度计的性能评估.(曾 超)2 A.Smola.Regression estimation with support vector learning machinesDB/OL.Masters Thesis.Tech.University of Mumchen,1996.Available http:/www.first.gmd.de/smola.3 A.Smola,B.Schlkopf.A tutorial on support vector regression R.NeuroCOLT,Rep.19,1998.Available http:/svm.first.gmd.de.4 B.Schlkopf,A.J.Smola,R.Willianson,P.Bartlett.New support vec2tor algorithms R.NeuroCOLT2 Technical Report Series,1998.Avail2able http:/.5 V.Vapnik.The Nature of Statistical Learning Theory M.New Y ork:Springer Verlag,1995.6 B.Schlkopf,K.Sung,C.Burges,F.G irosi,P.Niyogi,T.Poggio,V.Vapnik.Comparing support vector machines with Gaussian kernels toradial basis function classifiers J.IEEE Transactions on Signal Pro2cessing,1997,45(11).7 B.E.Boser,I.M.Guyon and V.Vapnik.A training algorithmfor opti2mal margin classifiers J.In Fifth Annual Workshop on ComputationalLearning Theory,Pittsburgh,1992,ACM.8 E.Osuna,R.Freund,F.G irrosi.Improved training algorithm for sup2port vector machines A.PRO.IEEE NNSP97 C,1997.9 J.C.Platt.Fast training of support vector machine using sequentialminimal optimization A.http:/ 1974年出生.西安电子科技大学在读博士.研究领域包括:机器学习、统计学习理论和智能信号处理.张 莉 1975年出生.西安电子科技大学在读博士生.主要研究方向有数据挖掘、模式识别和神经网络.495 电 子 学 报2001年 1995-2005 Tsinghua Tongfang Optical Disc Co.,Ltd.All rights reserved.