《支持向量机》PPT课件

支持向量机,Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(SupportVectorMachine，简称SVM)。,支持向量机方法是在近年来提出的一种新方法。支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。,线性可分条件下的支持向量机最优分界面,SVM的思想：由于两类别训练样本线性可分，因此在两个类别的样本集之间存在一个间隔。对一个二维空间的问题用下图表示。,线性可分条件下的支持向量机最优分界面,其中H是将两类分开的分界面，而H1与H2与H平行，H是其平分面，H1上的样本是第一类样本到H最近距离的点，H2的点则是第二类样本距H的最近点。,H,H1,H2,线性可分条件下的支持向量机最优分界面,由于这两种样本点很特殊，处在间隔的边缘上，因此再附加一个圈表示。这些点称为支持向量，它们决定了这个间隔。,H,H1,H2,线性可分条件下的支持向量机最优分界面,从图上可以看出能把两类分开的分界面并不止H这一个，如果略改变H的方向，则根据H1、H2与H平行这一条件，H1、H2的方向也随之改变，这样一来，H1与H2之间的间隔(两条平行线的垂直距离)会发生改变。显然使H1与H2之间间隔最大的分界面H是最合理的选择，因此最大间隔准则就是支持向量机的最佳准则。,从图上可以看出能把两类分开的分界面并不止H这一个，如果略改变H的方向，则根据H1、H2与H平行这一条件，H1、H2的方向也随之改变，这样一来，H1与H2之间的间隔(两条平行线的垂直距离)会发生改变。显然使H1与H2之间间隔最大的分界面H是最合理的选择，因此最大间隔准则就是支持向量机的最佳准则。,BestLinearSeparator?,FindClosestPointsinConvex,c,d,PlaneBisectClosestPoints,d,c,支持向量机,BestLinearSeparator:SupportingPlaneMethod,MaximizedistanceBetweentwoparallelsupportingplanes,Distance=“Margin”=,支持向量机,线性可分条件下的支持向量机最优分界面,为了将这个准则具体化，需要用数学式子表达。为了方便，将训练样本集表示成xi,yi，i=1，N，其中xi为d维向量也就是特征向量，而yi-1，+1，即用yi是+1或-1表示其类别。对于分界面H表示成,(1),(2),线性可分条件下的支持向量机最优分界面,显然H1平面到坐标原点的距离为,故H1到H2的间隔为,因此欲达到Vapnik提出的使间隔最大的准则，则应使|w|最小。必须遵守约束条件（2）,线性可分条件下的支持向量机最优分界面,因此欲达到Vapnik提出的使间隔最大的准则，则应使|W|最小。,而H2则为,故H1到H2的间隔为,而下式是它必须遵守的约束条件，可改写成大于零的不等式,线性可分条件下的支持向量机最优分界面,因此欲达到Vapnik提出的使间隔最大的准则，则应使|w|最小。,对于这样一个带约束条件为不等式的条件极值问题，需要引用扩展的拉格朗日乘子理论，按这个理论构造拉格朗日函数的原则为：,Minimize,Subjectto,线性可分条件下的支持向量机最优分界面,使目标函数为最小，减去用拉格朗日乘子(乘子值必须不小于0)与约束条件函数的乘积，在讨论的问题中可写成,目标函数是二次函数，而约束条件中为线性函数，按拉格朗日理论该问题存在唯一解，根据研究扩展的拉格朗日理论的Kuhn与Tucker等人的研究，表明以下是该唯一解的充分必要条件：,(3),线性可分条件下的支持向量机最优分界面,对于这样一个带约束条件为不等式的条件极值问题，为了求出最优解，拉格朗日理论中引入一种对偶函数：,线性可分条件下的支持向量机最优分界面,Maximize,(4),Subjectto,线性可分条件下的支持向量机最优分界面,WhereDisanNNmatrixsuchthatDij=yiyjxixj,拉格朗日理论证明：满足上述条件时，找LD极大值的解就是LP式的条件极小值，因此由LD可求得各个最佳值。,线性可分条件下的支持向量机最优分界面,bcanbedeterminedfrom*,whichisasolutionofthedualproblem,andfromtheKuhn-Tuckerconditions,(5),线性可分条件下的支持向量机最优分界面,Notethattheonlyi*thatcanbenonzeroin(5)thoseforwhichtheconstraints(2)aresatisfiedwiththeequalitysign.,(5),(2),线性可分条件下的支持向量机最优分界面,Mostoftheconstraintsin(2)aresatisfiedwithinequalitysignsi.e.,most*solvedfromthedualarenull.,(2),线性可分条件下的支持向量机最优分界面,Whereforalli=1,N,either,irrelevant,or,Thesolutionisdeterminedbytheexamplesonthemargin.Thus,线性可分条件下的支持向量机最优分界面,只有满足约束条件(2)中等于的点,其拉格朗日乘子才可能不为零；而对满足约束条件(2)大于的样本数据来说，其拉格朗日乘子必须为零，显然只有部分(经常是少量)的样本数据的i不为零，而线性分界面的权向量w则是这些i不为零的样本数据的线性组合，i不为零的样本数据也因而被称为支持向量。,线性可分条件下的支持向量机最优分界面,至此，再回顾一下线性可分条件下的支持向量机方法。首先支持向量机的方法是明确提出一个间隔概念，并把使间隔最宽作为确定线性分界面的最佳原则。既然是间隔又有线性可分作条件，只需找到处在间隔边缘上的点，以便确定最优的间隔就行，而其它数据点的作用，只是要求所确定的间隔能保证把它们置在间隔外确定的一方就行。,线性可分条件下的支持向量机最优分界面,这样一来，数据点就分成两部分，一种对确定间隔参数(体现在权向量w的确定很重要，而另一类(一般说占数据的大部分)对确定间隔的参数没有直接的影响，在这个意义上说它们对确定间隔参数无关紧要。它们相应的拉格朗日乘子i是否为0，就表示了数据的这种重要性，对确定间隔参数主要的点应有i0，并称为支持向量，而其余的数据点，它的i=0，,线性可分条件下的支持向量机最优分界面,一旦使LD式达极大值的数据确定下来(只有少量的*i0，其余都为0)，则最佳的权向量w也就可以利用定下来，它们是这些支持向量数据的线性求和。,线性可分条件下的支持向量机最优分界面,如果知道哪些数据是支持向量，哪些不是，则问题就简单了。问题在于哪些数据是支持向量事先并不能确定，因此这只有通过求(3)式的极大值来求解。对(4)式的来源不要求弄懂，只需知道，它的极大值解与(3)式的极小值解是一致的就行了。因为后面还要用(4)说明一些问题。,线性可分条件下的支持向量机最优分界面,例：XOR问题的SVM异或问题是最简单的一个无法直接对特征采用线性判别函数解决的问题。,如图所示的四个样本点。利用SVM将他们映射到一个更高维的空间，使之线性可分。,线性可分条件下的支持向量机最优分界面,如采用最简单且展开不超过二次的展开：在6维空间中的最佳超平面是,(6维空间),裕量为,其二维空间投影如图所示：,线性可分条件下的支持向量机最优分界面,通过支持向量的超平面是：,它对应于原始特征空间中的双曲线,线性可分条件下的支持向量机最优分界面,寻找使前面(4)最大化,即,Subjectto,根据问题的对称性,线性可分条件下的支持向量机最优分界面,利用解析方法解出,所有的样本都是支持向量。SVM的重要优点是所获得的分类器复杂度可以采用支持向量的个数，而不是变换空间的维数来刻划。因此SVM往往不像一些别的方法一样容易发生过拟合(overfitting)现象。,线性不可分条件下的广义最优线性分界面,以上讨论的是线性可分条件下的最优线性分界面的计算方法，对于线性不可分的情况下，如果仍要使用线性分界面，则必然有部分训练样本向量被错分。在线性分界面条件下，被错分的样本从本类别训练样本占主导的决策域，进入了对方的决策域。,线性不可分条件下的广义最优线性分界面,在这种条件下，严格意义上的间隔已不存在，前面公式也对一些数据不适用。但是仍然可以保留求最大间隔的框架，但允许有些数据能进入间隔区，甚至到对方的决策域中。但是对这部分数据的数量要严加控制。为了实行控制，可以采用的一种方法是对下式作一些改动，增加一种起缓冲作用的量i，i0,(2),线性不可分条件下的广义最优线性分界面,Purpose：toallowforasmallnumberofmisclassifiedpointsforbettergeneralizationorcomputationalefficiency.,suchthat,GeneralizedOSH,ThegeneralizedOSHisthenregardedasthesolutiontoProblem3,Subjectto,Minimize,GeneralizedOSH,RoleofC:Asaregularizationparameter(cf.RadialBasisFunction,fitting).,DualProblem,Problem4,Maximize,subjectto,DualProblem,Asbefore,andb*canbedeterminedfrom*,solutionofthedualProblem4andfromthenewKuhn-Tuckerconditions,where*arethevaluesoftheatthesaddlepoint.Similartoseparablecase,thepointsxiforwhichi*0aretermedsupportvectors.,DualProblem,Twocases:i*n)usingfunction.：RnRm,NonlinearSupportVectorMachine,Example:Alldegree2monomials,NonlinearSupportVectorMachine,ThenthetrainingalgorithmwouldonlydependonthedotproductsinH,i.e.,onthefunctionsoftheform(xi)(xj).Inotherwords,NonlinearSupportVectorMachine,Butthetransformationoperator,iscomputationallyexpensive.Iftherewerea“kernelfunction”KsuchthatK(xi,xj)=(xi)(xj),wewouldonlyneedtouseKinthetrainingalgorithm.Oneexample,AllthepreviousderivationsinlinearSVMhold(substitutingdotproductwithkernelfunction),sincewearestilldoingalinearseparation,butinadifferentspace.,MercersConditionforKernelFunction,TheideaofconstructingsupportvectornetworkscomesfromconsideringgeneralformsofthedotproductinaHilbertspace.,Question:WhichkerneldoesthereexistapairH,)suchthatK(xi,xj)=(xi)(xj)Answer:Mercerscondition.Ittellsuswhetherornotaprospectivekernelisactuallyadotproductinsomespace.,(21),MercersConditionforKernelFunction,AccordingtotheHilbert-SchmidtTheory,anysymmetricfunctionK(u,v),withK(u,v)L2,canbeexpandedintheform,whereiRandareeigenvalueandeigenfunction,OftheintegraloperatordefinedbythekernelK(u,v).,(22),MercersConditionforKernelFunction,Asufficientconditiontoensurethat(21)definesadotproductinafeaturespaceisthatalltheeigenvaluesintheexpansion(22)arepositive.Toguaranteethatthesecoefficientsarepositive,itisnecessaryandsufficient(Mercerstheorem)thatthecondition,issatisfiedforallgsuchthat,SomeKernelFunctioninSVM,Thefirstkernelsinvestigatedforthepatternrecognitionproblemwerethefollowing:apolynomialofdegreepinthedata,two-layerneuralnetwork,Gaussianradialbasisfunction,SomeKernelFunctioninSVM,wherethekernelwaschosentobeacubicpolynomial.,linearlyseparablecase(leftpanel),thesolutionisroughlylinear,indicatingthatthecapacityisbeingcontrolledlinearlynon-separablecase(rightpanel)hasbecomeseparable,SomeKernelFunctioninSVM,ToyExamplewithGaussianKernel,TheSVMArchitecture,ExampleshowingthebinarySVMclassifiertrainedontheRiplysdata.,Exampleshowingthemulti-classSVMclassifierbuildbyone-against-alldecomposition.,Exampleshowingthemulti-classSVMclassifierbuildbyone-against-onedecomposition.,ExampleshowsthebinaryclassifiertrainedbasedontheKernelFisherDiscriminant.,ExampleshowsthedecisionboundariesoftheSVMclassifiertrainedbySMOandtheapproximatedSVMclassifierfoundbythereducedsetmethod.Theoriginaldecisionruleinvolves94supportvectorswhilethereducedoneonly10supportvectors.,ExampleshowsthedecisionboundariesoftheSVMclassifiertrainedbySMOandtheapproximatedSVMclassifierfoundbythereducedsetmethod.Theoriginaldecisionruleinvolves94supportvectorswhilethereducedoneonly10