支持向量机浙大.ppt

浙江大学研究生人工智能引论课件,徐从富(Congfu Xu)PhD,Associate Professor Email:Institute of Artificial Intelligence,College of Computer Science,Zhejiang University,Hangzhou 310027,P.R.ChinaSeptember 11,2003第一稿Oct.16,2006第三次修改稿,第八章 统计学习理论与SVM(Chapter8 SLT&SVM),目录,概述统计学习理论中的基本概念统计学习理论的发展简况统计学习理论的基本内容支持向量机概述研究现状参考文献,8.1.1 SLT&SVM的地位和作用,是统计学习方法的优秀代表有严密的数学依据，得到了严格的数学证明有力反驳“复杂的理论是没有用的，有用的是简单的算法”等错误观点充分表明“没有什么比一个好的理论更实用了”等基本的科学原则,8.1 概述,8.1.2 SLT&SVM的数学基础,概率论与数理统计泛函分析,“For God so loved the world that he gave his one and only Son,that whoever believes in him shall not perish but have eternal life.For God did not send his Son into the world to condemn the world,but to save the world through him.”from JOHN 3:16-17 NIV,8.1.3 SLT&SVM所坚持的“基本信念”,传统的估计高维函数依赖关系的方法所坚持的信念 实际问题中总存在较少数目的一些“强特征”，用它们的简单函数（如线性组合）就能较好地逼近未知函数。因此，需要仔细地选择一个低维的特征空间，在这个空间中用常规的统计技术来求解一个逼近。SLT&SVM所坚持的信念 实际问题中存在较大数目的一些“弱特征”，它们“巧妙的”线性组合可较好地逼近未知的依赖关系。因此，采用什么样的“弱特征”并不十分重要，而形成“巧妙的”线性组合更为重要。,8.1.4 SLT&SVM与传统方法的区别,要较好地实现传统方法，需要人工选择（构造）一些数目相对较少的“巧妙的特征”SVM方法则是自动地选择（构造）一些数目较少的“巧妙的特征”在实际应用中，可通过构造两层（或多层）SVM来选择“巧妙的特征”,SLT&SVM集以下模型于一身：,结构风险最小化（SRM）模型数据压缩模型构造复合特征的一个通用模型 在希尔伯特空间中的内积回旋可以 看作是构造特征的一种标准途径。对实际数据的一种模型 一个小的支持向量集合可能足以对不同的机器代表整个训练集。,8.2 SLT中的基本概念,统计方法 从观测自然现象或者专门安排的实验所得到的数据去推断该事务可能的规律性。统计学习理论 在研究小样本统计估计和预测的过程中发展起来的一种新兴理论。【注意】：这里所说的“小样本”是相对于无穷样本而言的，故只要样本数不是无穷，都可称为小样本，更严格地说，应该称为“有限样本”。,统计学习理论中的基本概念（续）,机器学习 主要研究从采集样本出发得出目前尚不能通过原理分析得到的规律,并利用这些规律对未来数据或无法观测的数据进行预测。模式识别 对表征事务或现象的各种形式(数值、文字及逻辑关系等)信息进行处理和分析,以对事务或现象进行描述、辨认、分类和解释的过程。统计学习理论 一种研究有限样本估计和预测的数学理论,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年代中期,有限样本情况下的机器学习理论研究逐渐成熟起来,形成了较完善的理论体系统计学习理论(Statistical Learning Theory,简称SLT),8.4 统计学习理论的基本内容,机器学习的基本问题统计学习理论的核心内容,8.4.1 机器学习的基本问题,机器学习问题的表示,学习问题的表示,产生器(G)，产生随机向量x属于Rn,它们是从固定但未知的概率分布函数F(x)中独立抽取的。训练器(S)，对每个输入向量x返回一个输出值y，产生输出的根据是同样固定但未知的条件分布函数 F(y|x)。学习机器(LM)，它能够实现一定的函数集f(x,a)，a属于A，其中A是参数集合。,8.4.2 机器学习的基本问题,机器学习就是从给定的函数集f(x,)(是参数)中,选择出能够最好地逼近训练器响应的函数。机器学习的目的可以形式化地表示为：根据n个独立同分布的观测样本，在一组函数 中求出一个最优函数 对训练器的响应进行估计,使期望风险最小 其中 是未知的,对于不同类型的机器学习问题有不同形式的损失函数。,三类基本的机器学习问题,模式识别函数逼近（回归估计）概率密度估计【补充说明】：用有限数量信息解决问题的基本原则 在解决一个给定问题时，要设法避免把解决一个更为一般的问题作为其中间步骤。,上述原则意味着，当解决模式识别或回归估计问题时，必须设法去“直接”寻找待求的函数，而不是首先估计密度，然后用估计的密度来构造待求的函数。密度估计是统计学中的一个全能问题，即知道了密度就可以解决各种问题。一般地，估计密度是一个不适定问题(ill-posed problem)，需要大量观测才能较好地解决。实际上，需要解决的问题（如决策规则估计或回归估计）是很特殊的，通常只需要有某一合理数量的观测就可以解决。,经验风险最小化原则,对于未知的概率分布,最小化风险函数,只有样本的信息可以利用,这导致了定义的期望风险是无法直接计算和最小化的。根据概率论中大数定理,可用算术平均代替数据期望,于是定义了经验风险 来逼近期望风险。经验风险最小化(ERM)原则：使用对参数w求经验风险 的最小值代替求期望风险 的最小值。,经验风险最小化,从期望风险最小化到经验风险最小化没有可靠的依据,只是直观上合理的想当然。期望风险和经验风险都是w的函数,概率论中的大数定理只说明了当样本趋于无穷多时经验风险将在概率意义上趋近于期望风险,并没有保证两个风险的w是同一点,更不能保证经验风险能够趋近于期望风险。即使有办法使这些条件在样本数无穷大时得到保证,也无法认定在这些前提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。,复杂性与推广能力,学习机器对未来输出进行正确预测的能力称作推广能力（也称为“泛化能力”）。在某些情况下,训练误差过小反而导致推广能力的下降,这就是过学习问题。神经网络的过学习问题是经验风险最小化原则失败的一个典型例子。,用三角函数拟合任意点,学习的示例,复杂性与推广能力（续）,在有限样本情况下，经验风险最小并不一定意味着期望风险最小；学习机器的复杂性不但与所研究的系统有关,而且要和有限的学习样本相适应；学习精度和推广性之间似乎是一对不可调和的矛盾,采用复杂的学习机器虽然容易使得学习误差更小,却往往丧失推广性；传统的解决办法（例如：采用正则化、模型选择、噪声干扰等方法以控制学习机器的复杂度）缺乏坚实的理论基础。,8.5 统计学习理论的核心内容,SLT被认为是目前针对有限样本统计估计和预测学习的最佳理论，它从理论上较为系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。SLT的主要内容包括:基于经验风险原则的统计学习过程的一致性理论学习过程收敛速度的非渐进理论控制学习过程的推广能力的理论构造学习算法的理论,VC维(函数的多样性),为了研究经验风险最小化函数集的学习一致收敛速度和推广性，SLT定义了一些指标来衡量函数集的性能，其中最重要的就是VC维(Vapnik-Chervonenkis Dimension)。VC维：对于一个指示函数（即只有0和1两种取值的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是能够打散的最大样本数目。如果对任意的样本数，总有函数能打散它们，则函数集的VC维就是无穷大。,VC维（续）,一般而言,VC维越大,学习能力就越强,但学习机器也越复杂。目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。N维实数空间中线性分类器和线性实函数的VC维是n+1。Sin(ax)的VC维为无穷大。,VC维（续）,Open problem:对于给定的学习函数集,如何用理论或实验的方法计算其VC维是当前统计学习理论研究中有待解决的一个难点问题。,三个里程碑定理,推广性的界,SLT系统地研究了经验风险和实际风险之间的关系,也即推广性的界。根据SLT中关于函数集推广性界的理论,对于指示函数集中所有的函数,经验风险 和实际风险 之间至少以概率 满足如下关系:其中，h是函数集的VC维,n是样本数。,推广性的界（续1）,学习机器的实际风险由两部分组成:训练样本的经验风险置信范围(同置信水平 有关,而且同学习机器的VC维和训练样本数有关。在训练样本有限的情况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与经验风险之间可能的差就越大。,推广性的界（续2）,在设计分类器时,不但要使经验风险最小化,还要使VC维尽量小,从而缩小置信范围,使期望风险最小。寻找反映学习机器的能力的更好参数，从而得到更好的界是SLT今后的重要研究方向之一。,结构风险最小化,传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。,结构风险最小化（续1）,结构风险最小化（续2）,实现SRM原则的两种思路在每个子集中求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集。设计函数集的某种结构使每个子集中都能取得最小的经验风险,然后只需选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思路的实现。,8.6 支持向量机概述,支持向量机概述支持向量机理论支持向量机核函数支持向量机实现,8.6.1 支持向量机概述,1963年，Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一组特征子集,使得对特征子集的划分等价于对整个数据集的划分,这组特征子集就被称为支持向量(SV)。1971年，Kimeldorf提出使用线性不等约束重新构造SV的核空间,解决了一部分线性不可分问题。1990年，Grace,Boser和Vapnik等人开始对SVM进行研究。1995年，Vapnik正式提出统计学习理论。,8.6.2 支持向量机理论,SVM从线性可分情况下的最优分类面发展而来。最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。,支持向量机理论（续1）,广义最优分类面,广义最优分类面（续1）,假定训练数据可以被一个超平面分开我们进行正归化此时分类间隔等于使最大间隔最大等价于使 最小,广义最优分类面（续2）,最优分类面问题可以表示成约束优化问题MinimizeSubject to定义Lagrange函数,广义最优分类面（续3）,Lagrange函数,一个简单的例子：,x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1,可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得w和b的值。,8.6.3 支持向量机,很多情况下，训练数据集是线性不可分的，Vapnik等人提出了用广义分类面（松弛子）来解决这一问题。非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。,高维空间中的最优分类面,分类函数只涉及到训练样本之间的内积运算(xixj),因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现,甚至不必知道变换的形式。SLT指出,根据Hibert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积使用。,Mercer条件,支持向量机,在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。,支持向量机,8.6.4 核函数,SVM中不同的内积核函数将形成不同的算法,主要的核函数有三类：多项式核函数径向基函数S形函数,8.6.5 支持向量机实现,SVMlight-2.private:/usr/local/binsvm_learn,svm_classifybsvm-2.private:/usr/local/binsvm-train,svm-classify,svm-scalelibsvm-2.private:/usr/local/binsvm-train,svm-predict,svm-scale,svm-toymySVMMATLAB svm toolbox,支持向量机实现,8.7 研究现状,应用研究支持向量机研究支持向量机算法研究,8.7.1 应用研究,SVM的应用主要于模式识别领域贝尔实验室对美国邮政手写数字库进行的实验,SVM与神经网络（NN）的对比,SVM的理论基础比NN更坚实，更像一门严谨的“科学”（三要素：问题的表示、问题的解决、证明）SVM 严格的数学推理NN 强烈依赖于工程技巧推广能力取决于“经验风险值”和“置信范围值”，NN不能控制两者中的任何一个。NN设计者用高超的工程技巧弥补了数学上的缺陷设计特殊的结构，利用启发式算法，有时能得到出人意料的好结果。,“我们必须从一开始就澄清一个观点，就是如果某事不是科学，它并不一定不好。比如说，爱情就不是科学。因此，如果我们说某事不是科学，并不是说它有什么不对，而只是说它不是科学。”by R.Feynman from The Feynman Lectures on Physics,Addison-Wesley同理，与SVM相比，NN不像一门科学，更像一门工程技巧，但并不意味着它就一定不好！,主要应用领域,手写数字识别语音识别人脸识别文本分类,8.7.2 支持向量机研究,如何针对不同的问题选择不同的核函数仍然是一个悬而未决的问题。标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁棒性是至关重要的。,8.7.3 支持向量机算法研究,支持向量机的本质是解一个二次规划问题,虽然有一些经典（如对偶方法、内点算法等）,但当训练集规模很大时,这些算法面临着维数灾难问题。为此,人们提出了许多针对大规模数据集的SVM训练算法。,支持向量机算法研究（续1）,思路1：分解子问题块算法SMO算法(Sequential Minimal Optimization)思路2：序列优化思路3：近邻SVM,支持向量机算法研究（续2）,训练SVM的绝大多数算法都是针对分类问题,只有一小部分算法考虑了回归函数的估计问题。提高算法效率、降低复杂度。,支持向量机算法研究（续3）,SVM增量学习算法的研究超球面SVM算法研究One-class SVM算法SVM多值分类器算法One-against-the-rest（一对多方法）One-against-one（一对一方法）Multi-class Objective Functions（多类SVM）Decision Directed Acyclic Graph,DDAGSVM Decision Tree超球面SVM多值分类器,总结,SVM在模式识别、回归函数估计、预测等大量应用中取得了良好的效果SVM存在两个主要问题：二次规划的训练速度核函数的选择前途是光明的，道路是曲折的。,课后编程实现题目（二选一）：,设计并实现一个简单的用于文本分类的SVM。设计并实现一个简单的基于SVM的“新闻分离器”，主要用于对浙大BBS“缥缈水云间”中news版上的新闻进行分类。,主要参考文献：,A tutorial on support vector machines for pattern recognition.Data Mining and Knowledge Discovery,1998,2(2)Vapnik V N.The Nature of Statistical Learning Theory,NY:Springer-Verlag,1995（中译本：张学工译.统计学习理论的本质.清华大学出版社,2000）【说明】：该书附带介绍了很多科学研究的基本原则，很有启发、借鉴意义。,Introduction to Support Vector Machine.Vapnik V N.著，张学工译.统计学习理论.人民邮电出版社.张学工.关于统计学习理论与支持向量机.自动化学报,2000年第1期.史朝辉.SVM算法研究及在HRRP分类中的应用.空军工程大学硕士学位论文,2005.,主要参考文献（续）：,THANKS FOR YOUR PRESENCE!,“A righteous man may have many troubles,but the LORD delivers him from them all;he protects all his bones,not one of them will be broken.”from Psalms 34:19-20 NIV,