




已阅读5页,还剩58页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
支持向量机,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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年城市生态修复项目社会稳定风险评估与生态修复项目风险评估与风险控制报告
- 信访知识培训课件
- 辽宁省丹东市东港市2024-2025学年七年级上学期期中教学质量监测道德与法治试卷(含答案)
- 中小企业公共服务平台建设方案
- 2025年传媒互联网行业投资策略分析报告:AI应用落地机会景气娱乐赛道
- 输电安全课件
- 小麦病虫害防治图谱课件
- 小鸭子课件模板
- 农业企业注销与土地流转及农民权益保障协议
- 城市四区住房保障家庭租赁补贴协议及资金监管执行
- Unit 2 单元测试卷-2024-2025学年人教版七年级英语上册
- 2025股权技术入股合同
- 钢桁架桥制作施工方案
- 2025-2026学年北京版(2024)小学体育与健康一年级全一册教学计划及进度表(第一学期)
- 新《斜视弱视学》期末考试复习题库(含答案)
- 幼儿园数学活动《6和7的认识》课件
- 肠菌移植治疗炎症性肠病专家共识解读课件
- 2025年山西省建设工程专业高级职称评审考试(建筑工程管理)历年参考题库含答案详解(5卷)
- 医院医疗质量安全专项整治自查表
- 骨折固定与康复技术新进展
- 2025-2030中国医院经营管理模式与创新发展规划研究报告
评论
0/150
提交评论