浙江大学SVM支持向量机

《浙江大学SVM支持向量机》由会员分享，可在线阅读，更多相关《浙江大学SVM支持向量机（68页珍藏版）》请在装配图网上搜索。

1、浙江大学研究生浙江大学研究生人工智能引论人工智能引论课件课件徐从富徐从富(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)目录目录n概述n统计学习理论中的基本概念n统计学习理论的发展简况n统计

2、学习理论的基本内容n支持向量机概述n研究现状n参考文献8.1.1 SLT&SVM的地位和作用的地位和作用n是统计学习方法的优秀代表n有严密的数学依据，得到了严格的数学证明n有力反驳 “复杂的理论是没有用的，有用的是简单的算法”等错误观点n充分表明 “没有什么比一个好的理论更实用了没有什么比一个好的理论更实用了”等基本的科学原则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 sh

3、all 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所坚持的“基本信念”传统的估计高维函数依赖关系的方法所坚持的信传统的估计高维函数依赖关系的方法所坚持的信念念 实际问题中总存在较少数目的一些“强特征强特征”，用它们的简单函数（如线性组合）就能较好地逼近未知函数。因此，需要仔细地选择一个低仔细地选择一个低维

4、的特征空间维的特征空间，在这个空间中用常规的统计技术来求解一个逼近。SLT&SVM所坚持的信念所坚持的信念 实际问题中存在较大数目的一些“弱特征弱特征”，它们“巧妙的”线性组合可较好地逼近未知的依赖关系。因此，采用什么样的“弱特征”并不十分重要，而形成“巧妙的”线性组合更为重要。8.1.4 SLT&SVM与传统方法的区别要较好地实现传统方法传统方法，需要人工选择（构造）一些数目相对较少的“巧妙的特征”SVM方法方法则是自动地选择（构造）一些数目较少的“巧妙的特征”在实际应用中，可通过构造两层（或多层）构造两层（或多层）SVM来选择“巧妙的特征”SLT&SVM集以下模型于一身：结构风险最小化（S

5、RM）模型数据压缩模型构造复合特征的一个通用模型 在希尔伯特空间中的内积回旋可以 看作是构造特征的一种标准途径。对实际数据的一种模型 一个小的支持向量集合可能足以对不同的机器代表整个训练集。8.2 SLT中的基本概念中的基本概念n统计方法统计方法 从观测自然现象或者专门安排的实验所得到的数据去推断该事务可能的规律性。n统计学习理论统计学习理论 在研究小样本小样本统计估计和预测的过程中发展起来的一种新兴理论。【注意注意】：这里所说的“小样本”是相对于无穷样本而言的，故只要样本数不是无穷，都可称为小样本，更严格地说，应该称为“有限样本有限样本”。统计学习理论中的基本概念（续）n机器学习机器学习 主

6、要研究从采集样本出发得出目前尚不能通过原理分析得到的规律,并利用这些规律对未来数据或无法观测的数据进行预测。n模式识别模式识别 对表征事务或现象的各种形式(数值、文字及逻辑关系等)信息进行处理和分析,以对事务或现象进行描述、辨认、分类和解释的过程。n统计学习理论统计学习理论 一种研究有限样本估计和预测的数学理论8.3 统计学习理论的发展简况统计学习理论的发展简况n学习过程的数学研究F.Rosenblatt于1958,1962年把感知器作为一个学习机器模型n统计学习理论的开始Novikoff(1962)证明了关于感知器的第一个定理n解决不适定问题的正则化原则的发现Tikhonov(1963),I

7、vanov(1962),Phillips(1962)nVanik和Chervonenkis(1968)提出了VC熵熵和VC维维的概念提出了统计学习理论的核心概念得到了关于收敛速度的非渐进界的主要结论SLTSLT的发展简况的发展简况(续续)Vapnik和Chervonenkis(1974)提出了结构风结构风险最小化（险最小化（SRM）归纳原则）归纳原则。Vapnik和Chervonenkis(1989)发现了经验风险最小化归纳原则和最大似然方法一致性的充分必要条件,完成了对经验风险最小化归纳推理的分析。90年代中期,有限样本情况下的机器学习理论研究逐渐成熟起来,形成了较完善的理论体系统计学习理论

8、(Statistical Learning Theory,简称SLT)8.4 统计学习理论的基本内容统计学习理论的基本内容n机器学习的基本问题n统计学习理论的核心内容8.4.1 机器学习的基本问题机器学习的基本问题n机器学习问题的表示GLMSX Xyy学习问题的表示学习问题的表示n产生器(G)，产生随机向量x属于Rn,它们是从固定但未知的概率分布函数F(x)中独立抽取的。n训练器(S)，对每个输入向量x返回一个输出值y，产生输出的根据是同样固定但未知的条件分布函数 F(y|x)。n学习机器(LM)，它能够实现一定的函数集f(x,a)，a属于A，其中A是参数集合。8.4.2 机器学习的基本问题机

9、器学习的基本问题n机器学习就是从给定的函数集f(x x,)(是参数)中,选择出能够最好地逼近训练器响应的函数。n机器学习的目的可以形式化地表示为：根据n个独立同分布的观测样本 ，在一组函数 中求出一个最优函数 对训练器的响应进行估计,使期望风险最小 其中 是未知的,对于不同类型的机器学习问题有不同形式的损失函数。1122(,),(,),(,)nnx yxyxy(,)f x0(,)f x(,)P x y()(,(,)(,)RL y f xdP x y三类基本的机器学习问题三类基本的机器学习问题n模式识别n函数逼近（回归估计）n概率密度估计【补充说明】：用有限数量信息解决问题的基基本原则本原则 在

10、解决一个给定问题时，要设法在解决一个给定问题时，要设法避免把解决一个更为一般的问题作为其中间避免把解决一个更为一般的问题作为其中间步骤步骤。上述原则意味着，当解决模式识别或回归估计问题时，必须设法去必须设法去“直接直接”寻找待求的函数寻找待求的函数，而不是不是首先估计密度，然后用估计的密度来构造待求的函数。密度估计密度估计是统计学中的一个全能问题，即知道了密度就可以解决各种问题。一般地，估计密度是一个不适定问题(ill-posed problem)，需要大量观测才能较好地解决。实际上，需要解决的问题（如决策规则估计或回归估计）是很特殊的，通常只需要有某一合理数通常只需要有某一合理数量的观测就可

11、以解决量的观测就可以解决。经验风险最小化原则经验风险最小化原则n对于未知的概率分布,最小化风险函数,只有样本的信息可以利用,这导致了定义的期望风险是无法直接计算和最小化的。n根据概率论中大数定理,可用算术平均代替数据期望,于是定义了经验风险 来逼近期望风险。n经验风险最小化(ERM)原则：使用对参数w求经验风险 的最小值代替求期望风险 的最小值。11()(,(,)nempiiiRwL yf x wn()empRw()R w经验风险最小化经验风险最小化n从期望风险最小化到经验风险最小化没有可靠的依据,只是直观上合理的想当然。期望风险和经验风险都是w的函数,概率论中的大数定理只说明了当样本趋于无穷

12、多时经验风险将在概率意义上趋近于期望风险,并没有保证两个风险的w是同一点,更不能保证经验风险能够趋近于期望风险。即使有办法使这些条件在样本数无穷大时得到保证,也无法认定在这些前提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。复杂性与推广能力复杂性与推广能力n学习机器对未来输出进行正确预测的能力称作推推广能力（广能力（也称为“泛化能力泛化能力”）。）。n在某些情况下,训练误差过小反而导致推广能力的下降,这就是过学习过学习问题。n神经网络的过学习问题是经验风险最小化原则失败的一个典型例子。用三角函数拟合任意点用三角函数拟合任意点学习的示例学习的示例复杂性与推广能力（续）复杂性与推广能力

13、（续）n在有限样本情况下，经验风险最小并不一定意味着期望风险最小；学习机器的复杂性不但与所研究的系统有关,而且要和有限的学习样本相适应；学习精度和推广性之间似乎是一对不可调和的学习精度和推广性之间似乎是一对不可调和的矛盾矛盾,采用复杂的学习机器虽然容易使得学习采用复杂的学习机器虽然容易使得学习误差更小误差更小,却往往丧失推广性；却往往丧失推广性；传统的解决办法（例如：采用正则化、模型选择、噪声干扰等方法以控制学习机器的复杂度）缺乏坚实的理论基础。8.5 统计学习理论的核心内容统计学习理论的核心内容nSLT被认为是目前针对有限样本统计估计和预测学习的最佳理论，它从理论上较为系统地研究了经验风险最

14、小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。nSLT的主要内容包括:基于经验风险原则的统计学习过程的一致性理论学习过程收敛速度的非渐进理论控制学习过程的推广能力的理论构造学习算法的理论VC维维(函数的多样性函数的多样性)n为了研究经验风险最小化函数集的学习一致收敛速度和推广性，SLT定义了一些指标来衡量函数集的性能，其中最重要的就是VC维(Vapnik-Chervonenkis Dimension)。nVC维维：对于一个指示函数（即只有0和1两种取值的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集

15、能够把h个样本打散，函数集的VC维就是能够打散的最大样本数目。n如果对任意的样本数，总有函数能打散它们，则函数集的VC维就是无穷大。VC维（续）维（续）n一般而言,VC维越大,学习能力就越强,但学习机器也越复杂。n目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。nN维实数空间中线性分类器和线性实函数的VC维是n+1。nSin(ax)的VC维为无穷大。nVCVC维（续）维（续）Open problem:对于给定的学习函数集,如何用理论或实验的方法计算其VC维是当前统计学习理论研究中有待解决的一个难点问题。三个里程碑定理三个里程碑定理()()(VC)li

16、m0()lim0()lim0 xannxxH nnHnnG nn收敛的充分 必要 条件熵快收敛速度的充分条件 与概率测度无关的快收敛充要条件推广性的界nSLT系统地研究了经验风险和实际风险之间的关系,也即推广性的界。n根据SLT中关于函数集推广性界的理论,对于指示函数集中所有的函数,经验风险 和实际风险 之间至少以概率 满足如下关系:其中，h是函数集的VC维,n是样本数。()empRw()R w1(ln(2/)1)ln(/4)()()emphn hRRn 推广性的界（续1）n学习机器的实际风险由两部分组成:训练样本的经验风险置信范围(同置信水平 有关,而且同学习机器的VC维和训练样本数有关。n

17、在训练样本有限的情况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与经验风险之间可能的差就越大。(ln(2/)1)ln(/4)()()emphn hRRn()()()empnRRh 1推广性的界（续2）n在设计分类器时,不但要使经验风险最小化,还要使VC维尽量小,从而缩小置信范围,使期望风险最小。n寻找反映学习机器的能力的更好参数，从而得到更好的界是SLT今后的重要研究方向之一。结构风险最小化n传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。n统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集

18、按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。结构风险最小化（续1）结构风险最小化（续2）n实现SRM原则的两种思路在每个子集中求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集。设计函数集的某种结构使每个子集中都能取得最小的经验风险,然后只需选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思路的实现。8.6 支持向量机概述n支持向量机概述n支持向量机理论n支持向量

19、机n核函数n支持向量机实现8.6.1 支持向量机概述支持向量机概述n1963年，Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一组特征子集,使得对特征子集的划分等价于对整个数据集的划分,这组特征子集就被称为支持向量(SV)。n1971年，Kimeldorf提出使用线性不等约束重新构造SV的核空间,解决了一部分线性不可分问题。n1990年，Grace,Boser和Vapnik等人开始对SVM进行研究。n1995年，Vapnik正式提出统计学习理论。8.6.2 支持向量机理论支持向量机理论nSVM从线性可分情况下的最优分类面发展而来。n最优分类面就是要求分类线不但能将两

20、类正确分开(训练错误率为0),且使分类间隔最大。nSVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。n过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。支持向量机理论（续1）广义最优分类面广义最优分类面（续1）n假定训练数据n可以被一个超平面分开n我们进行正归化n此时分类间隔等于n使最大间隔最大等价于使 最小()1,1,.,iiyw xbilRbRwbxwN,0).(11(,),.,(,),1,1nllx yx yxR y 2w2w广义最优分类面（续2）n最优分类

21、面问题可以表示成约束优化问题MinimizeSubject ton定义Lagrange函数211()()22()1,1,.,iiwww wyw xbilliiiibwxywbwL1221)1)(),(广义最优分类面（续3）nLagrange函数liiiibwxywbwL1221)1)(),(0),(0),(bwLwbwLbiiliiiliixywya110liiiiliiiililjijijijiibxxyxfyandlixxyyW1111,21)(sgn()(0,.,1,0)()(一个简单的例子：4x3x2x1x2221234223341()()(444)2Qx1=(0,0),y1=+1x2

22、=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得w和b的值。123412013/41/41120312002144231113,02224()3220wbgxxx 8.6.3 支持向量机支持向量机n很多情况下，训练数据集是线性不可分的，Vapnik等人提出了用广义分类面（松弛子）来解决这一问题。n非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。高维空间中的最优分类面n分类函数只涉及到训练样本之间的内积运算(xixj),因此,在高维空间中只需进行内积运算

23、,这种内积运算可通过定义在原空间中的函数来实现,甚至不必知道变换的形式。nSLT指出,根据Hibert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积使用。Mercer条件2(,),()0(),)()()0K x xxx dxKxxx dxdx对于任意的对称函数它是某个特征空间中的内积运算的充要条件是,对于任意的且有(x,支持向量机n在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。支持向量机8.6.4 核函数核函数nSVM中不同的内积核函数将形成不同的算法,主要的核函数有三类：n多项式核函数n径向基函数nS形函数8.6.5 支

24、持向量机实现支持向量机实现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 研究现状研究现状n应用研究n支持向量机研究n支持向量机算法研究8.7.1 应用研究应用研究nSVM的应用主要于模式识别领域n贝

25、尔实验室对美国邮政手写数字库进行的实验分类器错误率人工表现2.5%决策树C4.516.2%最好的两层神经网络5.9%SVM4.0%SVM与神经网络（NN）的对比SVM的理论基础比NN更坚实，更像一门严谨的“科学科学”（三要素：问题的表示、问题的解决、证明）SVM 严格的数学推理NN 强烈依赖于工程技巧推广能力推广能力取决于“经验风险值”和“置信范围值”，NN不能控制两者中的任何一个。NN设计者用高超的工程技巧弥补了数学上的缺陷设计特殊的结构，利用启发式算法，有时能得到出人意料的好结果。“我们必须从一开始就澄清一个观点，就是如果某事不是科学，它并不一定不好。比如说，爱情就不是科学。因此，如果我们

26、说某事不是科学，并不是如果我们说某事不是科学，并不是说它有什么不对，而只是说它不是科学说它有什么不对，而只是说它不是科学。”by R.Feynman from The Feynman Lectures on Physics,Addison-Wesley同理，与SVM相比，NN不像一门科学，更像一门工程技巧，但并不意味着它就一定不好！主要应用领域n手写数字识别n语音识别n人脸识别n文本分类8.7.2 支持向量机研究支持向量机研究n如何针对不同的问题选择不同的核函数仍然是一个悬而未决的问题。n标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁棒性是至关重要的。8.7.3 支持向量机

27、算法研究支持向量机算法研究n支持向量机的本质是解一个二次规划问题,虽然有一些经典（如对偶方法、内点算法等）,但当训练集规模很大时,这些算法面临着维数灾难问题。为此,人们提出了许多针对大规模数据集的SVM训练算法。支持向量机算法研究（续1）n思路1：分解子问题块算法SMO算法(Sequential Minimal Optimization)n思路2：序列优化n思路3：近邻SVM支持向量机算法研究（续2）n训练SVM的绝大多数算法都是针对分类问题,只有一小部分算法考虑了回归函数的估计问题。n提高算法效率、降低复杂度。支持向量机算法研究（续3）nSVM增量学习算法的研究n超球面SVM算法研究One-

28、class SVM算法nSVM多值分类器算法One-against-the-rest（一对多方法）One-against-one（一对一方法）Multi-class Objective Functions（多类SVM）Decision Directed Acyclic Graph,DDAGSVM Decision Tree超球面SVM多值分类器总结nSVM在模式识别、回归函数估计、预测等大量应用中取得了良好的效果nSVM存在两个主要问题：二次规划的训练速度核函数的选择n前途是光明的，道路是曲折的。课后编程实现题目（二选一）：设计并实现一个简单的用于文本分类的SVM。设计并实现一个简单的基于SV

29、M的“新闻新闻分离器分离器”，主要用于对浙大BBS“缥缈水云间”中news版上的新闻进行分类。主要参考文献：nA tutorial on support vector machines for pattern recognition.Data Mining and Knowledge Discovery,1998,2(2)nVapnik V N.The Nature of Statistical Learning Theory,NY:Springer-Verlag,1995（中译本：张学工译.统计学习理论的本质.清华大学出版社,2000）【说明】：该书附带介绍了很多科学研究的基本原则，很有启发

30、、借鉴意义。nIntroduction to Support Vector Machine.nVapnik V N.著，张学工译.统计学习理论.人民邮电出版社.n张学工.关于统计学习理论与支持向量机.自动化学报,2000年第1期.n史朝辉.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