支撑矢量机推广能力分析VIP专享VIP免费

支撑矢量机推广能力分析周伟达,张莉,焦李成(西安电子科技大学雷达信号处理重点实验室,西安710071)摘要:本文针对两种不同用途的支撑矢量机,分类支撑矢量机和回归支撑矢量机,分别证明了它们的一些几何性质,从这些性质出发讨论了这两种支撑矢量机对新增样本的推广能力,新增样本对支撑矢量,非支撑矢量的影响以及新增样本本身的一些特点,得到了一些非常有价值的结论.从这些结论可以看出支撑矢量机对新增样本具有良好的推广能力,即对新增样本的良好的包容性和适应性,并且支撑矢量机是一种可积累的学习模型.关键词:分类支撑矢量机;回归支撑矢量机;学习机;KKT条件;可积累性中图分类号:O2315文献标识码:A文章编号:037222112(2001)0520590205AnAnalysisofSVMsGeneralizationPerformanceZHOUWei2da,ZHANGLi,JIAOLi2cheng(NationalKeyLab.forRadarSignalProcessing,XidianUniversity,Xi’an710071,China)Abstract:SomegeometryofSupportVectorMachinesforclassificationandregressionisdescribedandproven.AndthenthegeneralizationperformanceofSVMsonnewly2addedsamplesisdiscussed.Throughtheanalysisofthepropertyofnewly2addedsamplesandtheeffectofthemonsupportvectorsandnon2supportvectors,somevaluableresultsarepresented.TheseenableustoconcludethatSVMhasagoodcompatibility,adaptabilityandgeneralizationperformancefornewly2addedsamplesandisahereditablelearningmodel.Keywords:supportvectorclassification;supportvectorregression;learningmachines;KKTconditions;hereditability1引言自1970年以来,Vapnik等人发展了一种新的学习机———支撑矢量机.与现有的学习机包括神经网络,模糊学习机,遗传算法,人工智能等相比,它具有许多的优点[1～4]:坚实的理论基础[5]和较好的推广能力,强大的非线性处理能力和高维处理能力.现在支撑矢量机快速算法有Chunking算法[7],Os2una算法[8],SMO算法[9],针对不同的应用有分类支撑矢量机,回归支撑矢量机等.但是支撑矢量机最突出的优势还在于它强大的推广能力,它能在训练样本较少的情况下得到较好的效果.关于支撑矢量机的推广能力,尤其是针对小样本训练的推广能力,Vapnik等人已作了详细的分析[1,5].他们对于支撑矢量机推广能力的讨论都是围绕着这样一个问题,即先验知识不够,训练样本缺乏,在这种情况下训练的支撑矢量机用于实际分类和回归分析时性能如何?但实际情况中推广能力还应包括另一方面的问题.上面的这种推广能力的分析实际上是相当于对新增测试样本的分析,而没有涉及对新增训练样本的分析.这儿所谓的新增测试样本实际上是指训练好的支撑矢量机后实际中新出现的样本,对于这些样本预先是不知道真正的输出结果的.新增训练样本是指训练好的支撑矢量机后,又出现了一些已知输出结果的样本,这些训练样本需要原支撑矢量机来进一步学习.新增训练样本对于实际问题是非常常见而且是非常合理的,实际中样本的采集都是一步一步而来,知识也都是逐步积累.这样一个非常符合常理的问题,在现在的大部分的学习机中仍得不到合理解决,许多学习机对于这一问题几乎无能为力,仅仅是把新样本加进来,重新开始进行训练.这其中的浪费是显而易见的,它们完全抛弃了已有的知识,这是有悖于常理的.那么支撑矢量机对于这种新增的训练样本的推广能力如何?它如何来处理这些新增的训练样本?它能否完成这种可积累性的学习?已经成为大家非常关注的问题,同时它又是支撑矢量机应用的基础.本文围绕着这一问题进行了研究,得到了一些有价值的结果.2分类支撑矢量机对于分类问题,支撑矢量机把分类边界最大最终归结为如下凸半正定二次规划问题:maxW(α)=∑li=1αi-12∑li,j=1αiαjyiyjK(xi·xj)(1)s.t.∑li=1αiyi=0(2)αi∈[0,C],i=1,⋯,l(3)收稿日期:2000206219;修回日期:2001201210基金项目:国家“863”项目(No.863230620620621)和教育部博士点基金第5期2001年5月电子学报ACTAELECTRONICASINICAVol.29No.5May2001©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.判决函数为:f(x)=∑li=1αiyiK(xi·x)+b(4)y=sgn(f(x))(5)下面我们引用数学优化中的一个重要定理.KK...