武汉科技大学SVM分类器课件

第五讲支持向量机网络目录(1/1)目录引言统计学习理论的基本理论支持向量机核函数支持向量机优化方法支持向量机方法小结支持向量机应用领域和研究进展SupportVectorRegression参考文献1引言(1/13)1引言基于数据的机器学习是现代智能技术中的重要方面,其本质就是从观测数据出发寻找统计规律,并对未来进行预测.人的智慧中一个很重要的方面是从实例学习的能力,通过对已知事实的分析总结出规律,预测不能直接观测的事实。在这种学习中,重要的是要能够举一反三,即利用学习得到的规律,不但可以较好地解释已知的实例,而且能够对未来的现象或无法观测的现象做出正确的预测和判断。我们把这种能力叫做泛化（推广）能力。1引言(2/13)在人们对机器智能的研究中,希望能够用机器(计算机)来模拟这种学习能力,这就是我们所说的基于数据的机器学习问题,或者简单地称作机器学习问题。我们的目的是,设计某种(某些)方法,使之能够通过对已知数据的学习,找到数据内在的相互依赖关系,从而对未知数据进行预测或对其性质进行判断。同样,在这里,我们最关心的仍是泛化能力问题。迄今为止,关于机器学习还没有一种被共同接受的理论框架,关于其实现方法大致可以分为三种:经典的(参数)统计估计方法经验非线性方法,如ANN统计学习理论1引言(3/13)A.第一种是经典的(参数)统计估计方法.包括模式识别、NN等在内,现有机器学习方法共同的重要理论基础之一是统计学.参数方法正是基于传统统计学的,在这种方法中,参数的相关形式(模型结构)是已知的,训练样本用来估计参数的值.这种方法有很大的局限性,首先,它需要已知样本分布形式,这需要花费很大代价.还有,传统统计学研究的是样本数目趋于无穷大时的渐近理论,即当样本趋向于无穷多时的统计性质.现有学习方法也多是基于样本数大这一假设.1引言(4/13)但在实际问题中,样本数往往是有限的,有时还十分有限。虽然人们实际上一直知道这一点，但传统上仍以样本数目无穷多为假设来推导各种算法，希望这样得到的算法在样本较少时也能有较好的(至少是可接受的)表现。因此当样本数有限时,一些本来在样本数目无穷多为假设来推导的,理论上很优秀的学习方法实际中表现却可能不尽人意,可能表现出很差的泛化能力。其中，近年来经常可以听到人们谈论的所谓ANN过学习问题就是一个典型的代表.1引言(5/13)B.经验非线性方法,如ANN.这种方法利用已知样本建立非线性模型,克服了传统参数估计方法的困难.但是,这种方法缺乏一种统一的数学理论.C.统计学习理论.针对小样本学习问题及泛化能力差等机器学习问题，实际上人们一直在努力解决此类问题。但是，其中多数工作集中在对已有(基于传统统计学原则的)方法的改进和修正，或者利用启发式方法设计某些巧妙的算法。在人类即将迈进一个新世纪的时候，人们开始逐渐频繁地接触到一个词，就是“统计学习理论”。1引言(6/13)统计学习理论(StatisticalLearningTheory,SLT)创始人V.Vapnik从60年代开始致力于有限样本统计理论的研究,在70年代就已经建立了其基本理论体系，成为机器学习问题研究的新的思路，有着诱人的前景。到90年代中期,随着其理论的不断发展和成熟,也由于NN等学习方法在理论上缺乏实质性进展,该理论开始受到广泛的重视.1引言(7/13)SLT指出经验风险最小并不能保证期望风险最小;提出了结构风险最小化原理;给出了核心概念VC维,指出为了最小化期望风险必须同时最小化经验风险和VC维;SLT从七十年代末诞生,到九十年代之前都处在初级研究和理论准备阶段,近几年才逐渐得到重视,其本身也趋向完善,并在1992直接产生了支持向量机(SupportVectorMachine,SVM)这一将这种理论付诸实现的有效的通用机器学习方法.或许是由于SLT为人们系统研究有限样本情况下机器学习问题提供了有力的理论基础,或许更是因为在这一基础上的SVM方法所表现出的令人向往的优良特性,人们开始迅速重视起这一早在20年前就该重视的学术方向。1引言(8/13)SVM就是基于SLT的一种模式识别与机器学习的方法,它是SLT中最新的内容,也是最实用的部分.定义(Cristianini&Shawe-Taylor,2000)SupportVectorMachinesareasystemforefficientlytraininglinearlearningmachinesinkernel-inducedfeaturespaces,whilerespectingtheinsightsofgeneralisationtheoryandexploitingoptimisationtheory.SVMbecomespopularbecauseofitssuccessinhandwrittendigitrecognition1.1%testerrorrateforSVM.Thisisthesameastheerrorratesofacarefullyconstructedneuralnetwork,LeNet4.1引言(9/13)目前,SVM算法在模式识别、回归估计、概率密度函数估计等方面都有应用.例如,在模式识别方面,除对于手写数字识别外,在语音识别、人脸图像识别、文章分类等问题,SVM算法在精度上已经超过传统的学习算法或与之不相上下.SVMisnowregardedasanimportantexampleof“kernelmethods”,arguablythehottestareainmachinelearning.SVMscombinethreeimportantideasApplyoptimizationalgorithmsfromOperationsReseachLinearProgrammingandQuadraticProgrammingImplicitfeaturetransformationusingkernelsImplicitfeaturetransformationusingkernelsControlofoverfittingbymaximizingthemargin1引言(10/13)1引言(11/13)目前,对SVM的讨论和进一步研究逐渐广泛,但仍有许多方面不完善.比如:许多理论目前还只有理论上的意义,尚不能在实际算法中实现;有关SVM算法某些理论解释也并非完美(如结构风险最小原理并不能严格证明SVM为什么有好的泛化能力);对于一个实际的学习机器的VC维的分析尚没有通用的方法;SVM方法中如何根据具体问题选择适当的内积函数也没有理论依据.1引言(12/13)现在,越来越多的学者认为,关于SLT和SVM的研究,将很快出现像在80年代后期ANN研究那样的飞速发展阶段。然而,所不同的是,SLT有完备的理论基础和严格的理论体系(相比之下ANN有更多的启发式成分),而且其出发点是更符合实际情况的有限样本假设.因此,可以预期的是,SLT的这个研究热潮将持续更长久,而且将在人们关于机器智能的研究中做出影响更深远的贡献。1引言(13/13)下面开始讨论SVM,主要内容有:统计学习理论的基本理论支持向量机核函数支持向量机优化方法SVM的应用领域和研究进展2SLT的基本理论(1/4)2统计学习理论的基本理论与传统统计学相比,统计学习理论(SLT)是一种专门研究小样本情况下机器学习规律的理论.该理论针对小样本统计问题建立了一套新的理论体系,在这种体系下的统计推理规则不仅考虑了对渐近性能的要求,而且追求在现有有限信息的条件下得到最优结果.V.Vapnik等人从六、七十年代开始致力于此方面研究,到九十年代中期,随着其理论的不断发展和成熟,也由于NN等学习方法在理论上缺乏实质性进展,SLT开始受到越来越广泛的重视.2SLT的基本理论(2/4)SLT的主要内容为：在基于经验数据最小化风险泛函的模型基础上对学习问题的表示。对经验风险最小化原则的深入分析，包括其一致性的充分必要条件。用经验风险最小化原则得到的风险的非渐近界。在这些界的基础上，控制小样本学习机器的泛化能力的原则。SVM方法，它在用小样本估计函数时能够控制泛化能力。2SLT的基本理论(3/4)SLT的一个核心概念就是VC维(VCDimension)概念,它是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标,在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、泛化性能等的重要结论.SLT是建立在一套较坚实的理论基础之上的,为解决有限样本学习问题提供了一个统一的框架.它能将很多现有方法纳入其中,有望帮助解决许多原来难以解决的问题(比如NN结构选择问题、局部极小点问题等);同时,这一理论基础上发展了一种新的通用学习方法--SVM,已初步表现出很多优于已有方法的性能.2SLT的基本理论(4/4)一些学者认为,SLT和SVM正在成为继NN研究之后新的研究热点,并将推动机器学习理论和技术有重大的发展.下面讨论SLT的基本理论,主要内容有:经验风险经验风险最小一致性原理经验风险最小归纳原理VC维的概念模型复杂度和泛化能力2.1经验风险(1/3)2.1经验风险学习的目的就是根据给定的训练样本求系统输入输出之间的依赖关系.学习问题可以一般的表示为变量y与x之间存在的未知依赖关系,即遵循某一未知的联合概率F(x,y).机器学习问题就是根据n个独立同分布观测样本:{x1,y1},{x2,y2},……,{xn,yn}在一组函数{f(x,w)}中,求一个最优的数f(x,w0)对依赖关系进行估计,使如下期望的风险最小2.1经验风险(2/3)其中w为函数的广义参数;{f(x,w)}称为预测函数集,它可以表示为任何的参数集.L(y,f(x,w))为由于用f(x,w)对y进行预测而造成的损失,在两类分类问题中,L(y,f(x,w))通常如下定义:()(,(,))(,)RwLyfxwdFxy),(1),(0)],(,[wxfyifwxfyifwxfyL2.1经验风险(3/3)由于期望风险需要掌握联合概率分布F(x,y),在传统的学习方法中,采用了所谓的经验风险最小化准则,即用样本定义经验风险liiiempwxfyLlwR1)],(,[1)(机器学习的目的就是要设计学习算法,使上述风险最小,作为对R(w)的评估.2.2经验风险最小一致性原理(1/2)2.2经验风险最小一致性原理为了从有限的观测中构造学习算法,需要一种渐进理论来刻画学习过程一致性的必要和充分条件,这就产生了最小一致性原理.定义:对于指示函数集L(y,w)和概率分布函数F(y),如果下面两个序列概率地收敛到同一极限,则称为经验风险最小一致性:)(inf)(wRwRwpll)(inf)(wRwRwpllemp2.2经验风险最小一致性原理(2/2)也就是说如果经验风险最小化方法是一致性,那么它必须提供一个函数序列L(y,wl),l=1,2,…,使得期望风险和经验风险收敛到一个可能的最小的风险值.上面两个式子可以分别判定风险可能的最小值,infR(w)R(w)Remp(w)2.3经验风险最小归纳原理(1/3)2.3经验风险最小归纳原理SLT系统的研究了对于各种类型的函数集、经验风险和实际风险之间的关系,即泛化的界限.实际上,从经验风险而推出期望风险最小没有可靠的理论依据,统计理论指出:经验风险Remp(w)和实际风险R(w)之间至少以1-的概率满足如下关系nhnhwRwRemp)4/ln()1)/2(ln()()(其中n是样本数,h是函数集的VC维.2.3经验风险最小归纳原理(2/3)由此可见,统计学习的实际风险由两部分组成:一个是经验风险,另外一个是置信界限(VCconfidence).置信界限反映了真实