support-vecttornetworks

支持向量网络CorinnaCortesandVladimirVapnikAT&TLabs-Research,USA摘要.支持向量网络是一种针对两类问题的新学习机器.它的实现基于以下思想:将输入向量非线性地映射到一个很高维的特征空间.并在该特征空间中构造一个线性决策平面.该决策平面的特殊性质保证了学习机器具有很好的推广能力.支持向量网络的思想已在完全可分的训练数据集上得以实现,这里我们将它扩展到不完全可分的训练数据集.利用多项式输入变换的支持向量网络被证明具有很好的推广能力.我们以光学字体识别为实验将支持向量网络和其他不同的经典学习算法进行了性能比较.关键词：模式识别,有效的学习算法,神经网路,径向基函数分类器,多项式分类器1介绍60多年前,R.A.Fisher[7]提出了模式识别领域的第一个算法.该模型考虑n维向量x正态分布N(m1,∑1)和N(m2,∑2),m1和m2为各个分布的均值向量,∑1和∑2为各个分布的协方差矩阵,并给出最优解为如下二次决策函数:2111112221|11||()[()()()()ln]22|TTsqFxsignxmxmxmxm.(1)当∑1=∑2=∑时该二次决策函数(1)退化为一个线性函数:1111211221()[()()]2TTTlinFxsignmmxmmmm.(2)评估二次决策函数需要确定n(n+3)/2个自由参数,而评估线性函数只需要n个自由参数.在观测数目较小(小于10n2)的情况下评估O(n2)个参数是不可靠的.Fisher因此提出以下建议,在∑1≠∑2时也采用线性判别函数(2),其中的∑采用如下形式:12(1),(3)这里是某个常数.Fisher也对两个非正态分布的线性决策函数给出了建议.因此模式识别的算法最开始是和构建线性决策平面相关联的.1962年,Rosenblatt[11]提出了一种不同的学习机器:感知器(或神经网络).感知器由相关联的神经元构成,每个神经元实现一个分类超平面,因此整个感知器完成了一个分段线性分类平面.如图1.Fig1:Asimplefeed-forwardperceptronwith8inputunits,2layersofhiddenunits,and1outputunit.Thegray-shadingoftheVectorentriesreflectstheirnumericvalue.Rosenblatt没有提出通过调整网络的所有权值来最小化向量集上误差的算法,而提出了一种自适应仅仅改变输出节点上的权值的方法.由于其他权值都是固定的,输入向量被非线性地映射到最后一层节点的特征空间Z.在该空间的线性决策函数如下:()(())iiiIxsignzx(4)通过调整第i个节点到输出节点的权值i来最小化定义在训练集上的某种误差.Rosenblatt的方法,再次将构建决策规则归结为构造某个空间的线性超平面.1986年,针对模式识别问题出现了通过调整神经网络所有权值来局部最小化向量集上误差的算法[12,13,10,8],即后向传播算法.算法对神经网络的数学模型有微小的改动.至此,神经网络实现了分段线性决策函数.本文提出了一种全新的学习机器,支持向量网络.它基于以下思想:通过事先选择的非线性映射将输入向量映射到一个高维特征空间Z.在空间Z里构建一个线性决策面,该决策面的一些性质保证支持向量网络具有好的推广能力.例如:要构造一个与二阶多项式对应的决策面,我们可以构造一个特征空间Z,它有如下的N=n(n+3)/2个坐标:11,,nnzxzx,ncoordinates,22112,,nnnzxzx,ncoordinates,21121,,nNnnzxxzxx,n(n-1)/2coordinates,其中,x=1(,,)nxx.分类超平面便是在该空间中构造的.以上方法存在两个问题:一个是概念上的,另一个是技术上的.(1)概念上的问题:怎样找到一个推广性很好的分类超平面?特征空间的维数将会很高,能将数据分开的超平面不一定都具有很好的推广性.(2)技术上的问题:怎样在计算上处理如此高维的空间?要在一个200维的空间中构建一个4或5阶的多项式,需要构造一个上十亿的特征空间.概念上的问题在1965年[14]通过完全可分情况下的最优超平面得以解决.最优超平面是指使两类向量具有最大间隔的线性决策函数,如图2所示.可以发现,构造最优超平面只需考虑训练集中决定分类隔间的少量数据,即所谓的支持向量.如果训练集被最优超平面完全无错地分开,则一个测试样例被错判的期望概率以支持向量的期望数目与训练集向量数目比值为上界,即:[numberofsupportvectors][Pr()]numberoftrainingvectorsEEerror.(5)注意,这个界与分类空间的维数无关.并且由此可知,如果支持向量的个数相对与整个训练集很小,则构建出来的分类超平面将具有很好的推广性,即便是在一个无限维空间.第5节中,通过实际问题我们验证了比值(5)能够小到0.03而相应的最优超平面在一个十亿的特征空间依然具有很好的推广能力.Fig2.Anexampleofaseparableproblemina2dimensionalspace.Thesupportvectors,markedwithgreysquares,definethemarginoflargestseparationbetweenthetwoclasses.令000bwz为特征空间里的最优超平面.我们将看到,特征空间中最优超平面的权值0w可以写成支持向量的某个线性组合0supportvectorsiiwz.(6)从而特征空间里的线性决策函数I(z)为如下形式:0supportvectors()sign()iiIbzzz,(7)其中izz表示支持向量iz和向量z在特征空间里的内积.因此,该决策函数可以通过一个两层的网络来描述.如图3.尽管最优超平面保证了好的推广性,但如何处理高维特征空间这个技术上的问题依然存在.1992年,在文献[3]中证明构造决策函数的步骤可以交换顺序:不必先将输入向量通过某种非线性变换映射到特征空间再与特征空间中的支持向量做内积；而可以先在输入空间通过内积或者某种别的距离进行比较,再对比较的值进行非线性变化.如图4.这就允许我们构造足够好的分类决策面,比如任意精度的多项式决策面.称这种类型的学习机器为支持向量网络.支持向量网络的技术首先针对能够完全无错地分开的数据集.本文我们将支持向量网络推广到不能完全无错分类的数据集.通过该扩展,作为一种全新的学习机器的支持向量网络将和神经网络一样的强大和通用.第5节将展示它在256维的高维空间中针对高达7阶的多项式决策面的推广性.并将它和其他经典的算法比如线性分类器、k近邻分类器和神经网络做了性能上的比较.第2、3、4节着重引出算法并讨论了算法的一些性质.算法的一些重要细节参见附录.Fig3.Classificationbyasupport-vectornetworkofanunknownpatternisconceptuallydonebyfirsttransformingthepatternintosomehigh-dimensionalfeaturespace.Anoptimalhyperplaneconstructedinthisfeaturespacedeterminestheoutput.Thesimilaritytoatwo-layerperceptroncanbeseenbycomparisontoFig1.Fig4.Classificationofanunknownpatternbyasupport-vectornetwork.Thepatternisininputspacecomparedtosupportvectors.Theresultingvaluesarenon-linearlytransformed.Alinearfunctionofthesetransformedvaluesdeterminestheoutputoftheclassifier.2最优超平面本节回顾文献[14]中针对能被完全无错分开的训练数据的最优超平面方法.下一节介绍软间隔的概念,用来处理训练集不完全可分情况下的学习问题.2.1最优超平面算法训练样本集11(,),,(,)llyyxx,{1,1}iy(8)是线性可分的如果存在向量w和标量b使得以下不等式1if1,1if1,iiiibybywxwx(9)对(8)中所有元素都成立.我们将不等式(9)写成如下形式:(wx+)1,1,.iiybil(10)最优超平面00+0bwx(11)是指将训练数据以最大间隔分开的那个平面:它决定了向量w/|w|的方向,该方向上两不同类别训练向量间的距离最大.可回顾图2.记这个距离为(,)bw,它由下式给定:00{:1}{:1}(,)||||maxminyybxwx(12)最优超平面(w0,b0)便是使得距离(12)取最大值的那组参数.根据(12)和(10)可得0000022(,)||b(13)这表明,最优超平面就是满足条件(10)并且使得ww最小化的超平面.因此,构建一个最有超平面其实就是一个二次规划问题.满足()1iiybwx的向量ix即为支持向量.附录中将证明决定最优超平面的向量0w可以写成所有训练向量的一个线性组合:001liiiiywx,(14)其中0i≥0.由于只有支持向量处的系数0(参考附录),表达式(14)只是0w的一种简写形式.要求出参数向量i:0001(,,)Tl,需要求解以下二次规划问题:1()2TTW1-D(15)其中T=(1,,l),且满足限制:≥0,(16)TY=0,(17)T1=(1,...,1)是维的单位向量,1(,...,)TlyyY是维的类标签向量,D是×的对称矩阵其元素,,1,...,ijijijDyyijlxx.(18)不等式(16)表示非负象限.因此,问题变为在非负象限中最大化二次式(15),并服从约束条件(17).当训练数据可完全无错地分开时,在附录A中我们证明了在最大泛函(15)、00(,)b和式(13)的最大间隔0之间有以下关系:0202()W.(19)如果存在某个*和某个较大的常数0W使得不等式*0()WW(20)成立,则所有把训练集(8)分开的超平面其间隔都满足02W.如果训练集(8)不能被超平面完全分开,则两个类的样本间的间隔变的任意小,使得泛函()W的值变得任意大.因此,要在约束条件(16)和(17)下最大化泛函(15),要么能求得最大值(这种情况需要构造最大间隔为0的最优超平面),要么求出超过某个给定的常数0W的最大值(这种情况下不可能以大于02/W的间隔分开训练数据).在约束条件(16)和(17)下最大化泛函(15)的问题如下方法可有效地解决.将训练数据集划分为几部分,使每部分占有合理的少量数据.先求解由第一部分训练数据决定的二次规划问题.对于该问题,会有两个结果:其一,这部分数据不能被任何超平面分开(这种情况下整个数据集都不能被任何超平面分开);其二,找到了能分开这部分数据的最优超平面.假设对第一部分数据泛函(15)的最大化时对应的向量为1.该向量某些维上取值为零,它们是和该部分数据中非支持向量相关的.将第一部分数据中的支持向量和第二部分中不满足约束条件(10)的向量组成一个新的训练集,其中w将由1决定.对于这个新的训练集,构建泛函2()W并假设其在2最大化.持续递增地构造出覆盖全部训练数据的解向量*,此时,或者会发现无法找到将整个训练集无错分开的超平面,或者构建出了整个训练集的最优超平面,且*=0.值得注意的是,在这个过程中泛函()W的值是