浙江大学SVM(支持向量机)

浙江大学研究生《人工智能引论》课件徐从富(CongfuXu)PhD,AssociateProfessorEmail:[e-mail]ntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaSeptember11,2003第一稿Oct.16,2006第三次修改稿第八章统计学习理论与SVM(Chapter8SLT&SVM)目录概述统计学习理论中的基本概念统计学习理论的发展简况统计学习理论的基本内容支持向量机概述研究现状参考文献8.1.1SLT&SVM的地位和作用是统计学习方法的优秀代表有严密的数学依据，得到了严格的数学证明有力反驳——“复杂的理论是没有用的，有用的是简单的算法”等错误观点充分表明——“没有什么比一个好的理论更实用了”等基本的科学原则8.1概述8.1.2SLT&SVM的数学基础概率论与数理统计泛函分析“ForGodsolovedtheworldthathegavehisoneandonlySon,thatwhoeverbelievesinhimshallnotperishbuthaveeternallife.ForGoddidnotsendhisSonintotheworldtocondemntheworld,buttosavetheworldthroughhim.”fromJOHN3:16-17NIV8.1.3SLT&SVM所坚持的“基本信念”传统的估计高维函数依赖关系的方法所坚持的信念实际问题中总存在较少数目的一些“强特征”，用它们的简单函数（如线性组合）就能较好地逼近未知函数。因此，需要仔细地选择一个低维的特征空间，在这个空间中用常规的统计技术来求解一个逼近。SLT&SVM所坚持的信念实际问题中存在较大数目的一些“弱特征”，它们“巧妙的”线性组合可较好地逼近未知的依赖关系。因此，采用什么样的“弱特征”并不十分重要，而形成“巧妙的”线性组合更为重要。8.1.4SLT&SVM与传统方法的区别要较好地实现传统方法，需要人工选择（构造）一些数目相对较少的“巧妙的特征”SVM方法则是自动地选择（构造）一些数目较少的“巧妙的特征”在实际应用中，可通过构造两层（或多层）SVM来选择“巧妙的特征”SLT&SVM集以下模型于一身：结构风险最小化（SRM）模型数据压缩模型构造复合特征的一个通用模型在希尔伯特空间中的内积回旋可以看作是构造特征的一种标准途径。对实际数据的一种模型一个小的支持向量集合可能足以对不同的机器代表整个训练集。8.2SLT中的基本概念统计方法——从观测自然现象或者专门安排的实验所得到的数据去推断该事务可能的规律性。统计学习理论——在研究小样本统计估计和预测的过程中发展起来的一种新兴理论。【注意】：这里所说的“小样本”是相对于无穷样本而言的，故只要样本数不是无穷，都可称为小样本，更严格地说，应该称为“有限样本”。统计学习理论中的基本概念（续）机器学习主要研究从采集样本出发得出目前尚不能通过原理分析得到的规律,并利用这些规律对未来数据或无法观测的数据进行预测。模式识别对表征事务或现象的各种形式(数值、文字及逻辑关系等)信息进行处理和分析,以对事务或现象进行描述、辨认、分类和解释的过程。统计学习理论一种研究有限样本估计和预测的数学理论8.3统计学习理论的发展简况学习过程的数学研究F.Rosenblatt于1958,1962年把感知器作为一个学习机器模型统计学习理论的开始Novikoff(1962)证明了关于感知器的第一个定理解决不适定问题的正则化原则的发现Tikhonov(1963),Ivanov(1962),Phillips(1962)Vanik和Chervonenkis(1968)提出了VC熵和VC维的概念提出了统计学习理论的核心概念得到了关于收敛速度的非渐进界的主要结论SLT的发展简况(续)Vapnik和Chervonenkis(1974)提出了结构风险最小化（SRM）归纳原则。Vapnik和Chervonenkis(1989)发现了经验风险最小化归纳原则和最大似然方法一致性的充分必要条件,完成了对经验风险最小化归纳推理的分析。90年代中期,有限样本情况下的机器学习理论研究逐渐成熟起来,形成了较完善的理论体系—统计学习理论(StatisticalLearningTheory,简称SLT)8.4统计学习理论的基本内容机器学习的基本问题统计学习理论的核心内容8.4.1机器学习的基本问题机器学习问题的表示GLMSXyy学习问题的表示产生器(G)，产生随机向量x属于Rn,它们是从固定但未知的概率分布函数F(x)中独立抽取的。训练器(S)，对每个输入向量x返回一个输出值y，产生输出的根据是同样固定但未知的条件分布函数F(y|x)。学习机器(LM)，它能够实现一定的函数集f(x,a)，a属于A，其中A是参数集合。8.4.2机器学习的基本问题机器学习就是从给定的函数集f(x,)(是参数)中,选择出能够最好地逼近训练器响应的函数。机器学习的目的可以形式化地表示为：根据n个独立同分布的观测样本，在一组函数中求出一个最优函数对训练器的响应进行估计,使期望风险最小其中是未知的,对于不同类型的机器学习问题有不同形式的损失函数。1122(,),(,),,(,)nnxyxyxy{(,)}fx0{(,)}fx(,)Pxy()(,(,))(,)RLyfxdPxy三类基本的机器学习问题模式识别函数逼近（回归估计）概率密度估计【补充说明】：用有限数量信息解决问题的基本原则——在解决一个给定问题时，要设法避免把解决一个更为一般的问题作为其中间步骤。上述原则意味着，当解决模式识别或回归估计问题时，必须设法去“直接”寻找待求的函数，而不是首先估计密度，然后用估计的密度来构造待求的函数。密度估计是统计学中的一个全能问题，即知道了密度就可以解决各种问题。一般地，估计密度是一个不适定问题(ill-posedproblem)，需要大量观测才能较好地解决。实际上，需要解决的问题（如决策规则估计或回归估计）是很特殊的，通常只需要有某一合理数量的观测就可以解决。经验风险最小化原则对于未知的概率分布,最小化风险函数,只有样本的信息可以利用,这导致了定义的期望风险是无法直接计算和最小化的。根据概率论中大数定理,可用算术平均代替数据期望,于是定义了经验风险来逼近期望风险。经验风险最小化(ERM)原则：使用对参数w求经验风险的最小值代替求期望风险的最小值。11()(,(,))nempiiiRwLyfxwn()empRw()Rw经验风险最小化从期望风险最小化到经验风险最小化没有可靠的依据,只是直观上合理的想当然。期望风险和经验风险都是w的函数,概率论中的大数定理只说明了当样本趋于无穷多时经验风险将在概率意义上趋近于期望风险,并没有保证两个风险的w是同一点,更不能保证经验风险能够趋近于期望风险。即使有办法使这些条件在样本数无穷大时得到保证,也无法认定在这些前提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。复杂性与推广能力学习机器对未来输出进行正确预测的能力称作推广能力（也称为“泛化能力”）。在某些情况下,训练误差过小反而导致推广能力的下降,这就是过学习问题。神经网络的过学习问题是经验风险最小化原则失败的一个典型例子。用三角函数拟合任意点学习的示例复杂性与推广能力（续）在有限样本情况下，经验风险最小并不一定意味着期望风险最小；学习机器的复杂性不但与所研究的系统有关,而且要和有限的学习样本相适应；学习精度和推广性之间似乎是一对不可调和的矛盾,采用复杂的学习机器虽然容易使得学习误差更小,却往往丧失推广性；传统的解决办法（例如：采用正则化、模型选择、噪声干扰等方法以控制学习机器的复杂度）缺乏坚实的理论基础。8.5统计学习理论的核心内容SLT被认为是目前针对有限样本统计估计和预测学习的最佳理论，它从理论上较为系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。SLT的主要内容包括:基于经验风险原则的统计学习过程的一致性理论学习过程收敛速度的非渐进理论控制学习过程的推广能力的理论构造学习算法的理论VC维(函数的多样性)为了研究经验风险最小化函数集的学习一致收敛速度和推广性，SLT定义了一些指标来衡量函数集的性能，其中最重要的就是VC维(Vapnik-ChervonenkisDimension)。VC维：对于一个指示函数（即只有0和1两种取值的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是能够打散的最大样本数目。如果对任意的样本数，总有函数能打散它们，则函数集的VC维就是无穷大。VC维（续）一般而言,VC维越大,学习能力就越强,但学习机器也越复杂。目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。N维实数空间中线性分类器和线性实函数的VC维是n+1。Sin(ax)的VC维为无穷大。……VC维（续）Openproblem:对于给定的学习函数集,如何用理论或实验的方法计算其VC维是当前统计学习理论研究中有待解决的一个难点问题。三个里程碑定理()()(VC)lim0()lim0()lim0xannxxHnnHnnGnn收敛的充分必要条件熵快收敛速度的充分条件与概率测度无关的快收敛充要条件推广性的界SLT系统地研究了经验风险和实际风险之间的关系,也即推广性的界。根据SLT中关于函数集推广性界的理论,对于指示函数集中所有的函数,经验风险和实际风险之间至少以概率满足如下关系:其中，h是函数集的VC维,n是样本数。()empRw()Rw1(ln(2/)1)ln(/4)()()emphnhRRn推广性的界（续1）学习机器的实际风险由两部分组成:训练样本的经验风险置信范围(同置信水平有关,而且同学习机器的VC维和训练样本数有关。在训练样本有限的情况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与经验风险之间可能的差就越大。(ln(2/)1)ln(/4)()()emphnhRRn()()()empnRRh1推广性的界（续2）在设计分类器时,不但要使经验风险最小化,还要使VC维尽量小,从而缩小置信范围,使期望风险最小。寻找反映学习机器的能力的更好参数，从而得到更好的界是SLT今后的重要研究方向之一。结构风险最小化传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(StructuralRiskMinimization)，即SRM准则。结构风险最小化（续1）结构风险最小化（续2）实现SRM原则的两种思路在每个子集中求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集。设计函数集的某种结构使每个子集中都能取得最小的经验风险,然后只需选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思路的实现。8.6支持向量机概述支持向量机概述支持向量机理论支持向量机核函数支持向量机实现8.6.1支持向量机概述1963年，Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一组特征子集,使得对特征子