《浙江大学研究生《人工智能引论》课件之统计学习理论与SVM优秀PPT.ppt》由会员分享，可在线阅读，更多相关《浙江大学研究生《人工智能引论》课件之统计学习理论与SVM优秀PPT.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浙江高校探讨生人工智能引论课件浙江高校探讨生人工智能引论课件徐从富徐从富(Congfu Xu)PhD,Associate Professor Email:xucongfuzju.edu 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统计学习理论中的基本概
2、念n统计学习理论的发展简况n统计学习理论的基本内容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 s
3、hall 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与传统
5、方法的区分要较好地实现传统方法，须要人工选择（构造）一些数目相对较少的“奇妙的特征”SVM方法则是自动地选择（构造）一些数目较少的“奇妙的特征”在实际应用中，可通过构造两层（或多层）SVM来选择“奇妙的特征”SLT&SVM集以下模型于一身：结构风险最小化（SRM）模型数据压缩模型构造复合特征的一个通用模型 在希尔伯特空间中的内积回旋可以 看作是构造特征的一种标准途径。对实际数据的一种模型 一个小的支持向量集合可能足以对不同的机器代表整个训练集。8.2 SLT中的基本概念中的基本概念n统计方法统计方法 从观测自然现象或者特从观测自然现象或者特地支配的试验所得到的数据去推断该事地支配的试验所得到的
6、数据去推断该事务可能的规律性。务可能的规律性。n统计学习理论统计学习理论 在探讨小样本统计在探讨小样本统计估计和预料的过程中发展起来的一种新估计和预料的过程中发展起来的一种新兴理论。兴理论。n【留意】：这里所说的【留意】：这里所说的“小样本小样本”是相是相对于无穷样本而言的，故只要样本数不对于无穷样本而言的，故只要样本数不是无穷，都可称为小样本，更严格地说，是无穷，都可称为小样本，更严格地说，应当称为应当称为“有限样本有限样本”。统计学习理论中的基本概念（续）n机器学习机器学习 n主要探讨从采集样本动身得出目前尚不能主要探讨从采集样本动身得出目前尚不能通过原理分析得到的规律通过原理分析得到的规
7、律,并利用这些规律并利用这些规律对将来数据或无法观测的数据进行预料。对将来数据或无法观测的数据进行预料。n模式识别模式识别 n对表征事务或现象的各种形式对表征事务或现象的各种形式(数值、文字数值、文字及逻辑关系等及逻辑关系等)信息进行处理和分析信息进行处理和分析,以对以对事务或现象进行描述、分辨、分类和说明事务或现象进行描述、分辨、分类和说明的过程。的过程。n统计学习理论统计学习理论 n一种探讨有限样本估计和预料的数学理论一种探讨有限样本估计和预料的数学理论8.3 统计学习理论的发展简况统计学习理论的发展简况n学习过程的数学探讨nF.Rosenblatt于1958,1962年把感知器作为一个学
8、习机器模型n统计学习理论的起先nNovikoff(1962)证明白关于感知器的第一个定理n解决不适定问题的正则化原则的发觉nTikhonov(1963),Ivanov(1962),Phillips(1962)nVanik和Chervonenkis(1968)提出了VC熵和VC维的概念n提出了统计学习理论的核心概念n得到了关于收敛速度的非渐进界的主要结论SLTSLT的发展简况的发展简况(续续)Vapnik和Chervonenkis(1974)提出了结构风险最小化（SRM）归纳原则。Vapnik和Chervonenkis(1989)发觉了阅历风险最小化归纳原则和最大似然方法一样性的充分必要条件,完
9、成了对阅历风险最小化归纳推理的分析。90年头中期,有限样本状况下的机器学习理论探讨渐渐成熟起来,形成了较完善的理论体系统计学习理论(Statistical Learning Theory,简称SLT)8.4 统计学习理论的基本内容统计学习理论的基本内容n机器学习的基本问题n统计学习理论的核心内容8.4.1 机器学习的基本问题机器学习的基本问题n机器学习问题的表示学习问题的表示学习问题的表示n产生器(G)，产生随机向量x属于Rn,它们是从固定但未知的概率分布函数F(x)中独立抽取的。n训练器(S)，对每个输入向量x返回一个输出值y，产生输出的依据是同样固定但未知的条件分布函数 F(y|x)。n学
10、习机器(LM)，它能够实现确定的函数集f(x,a)，a属于A，其中A是参数集合。8.4.2 机器学习的基本问题机器学习的基本问题n机器学习就是从给定的函数集f(x,)(是参数)中,选择出能够最好地靠近训练器响应的函数。n机器学习的目的可以形式化地表示为：依据n个独立同分布的观测样本 ，n在一组函数 中求出一个最优函数 对训练器的响应进行估计,使期望风险最小 n n其中 是未知的,对于不同类型的机器学习问题有不同形式的损失函数。n 三类基本的机器学习问题三类基本的机器学习问题n模式识别n函数靠近（回来估计）n概率密度估计n【补充说明】：用有限数量信息解决问题的基本原则 在解决一个给定问题时，要设
11、法避开把解决一个更为一般的问题作为其中间步骤。上述原则意味着，当解决模式识别或回来估计问题时，必需设法去“干脆”找寻待求的函数，而不是首先估计密度，然后用估计的密度来构造待求的函数。密度估计是统计学中的一个全能问题，即知道了密度就可以解决各种问题。一般地，估计密度是一个不适定问题(ill-posed problem)，须要大量观测才能较好地解决。事实上，须要解决的问题（如决策规则估计或回来估计）是很特殊的，通常只须要有某一合理数量的观测就可以解决。阅历风险最小化原则阅历风险最小化原则n对于未知的概率分布,最小化风险函数,只有样本的信息可以利用,这导致了定义的期望风险是无法干脆计算和最小化的。n
12、依据概率论中大数定理,可用算术平均代替数据期望,于是定义了阅历风险 n n来靠近期望风险。n阅历风险最小化(ERM)原则：运用对参数w求阅历风险 的最小值代替求期望风险 的最小值。阅历风险最小化阅历风险最小化n从期望风险最小化到阅历风险最小化没有牢靠的依据,只是直观上合理的想当然。n期望风险和阅历风险都是w的函数,概率论中的大数定理只说明白当样本趋于无穷多时阅历风险将在概率意义上趋近于期望风险,并没有保证两个风险的w是同一点,更不能保证阅历风险能够趋近于期望风险。n即使有方法使这些条件在样本数无穷大时得到保证,也无法认定在这些前提下得到的阅历风险最小化方法在样本数有限时仍能得到好的结果。困难性
13、与推广实力困难性与推广实力n学习机器对将来输出进行正确预料的实力称作推广实力（也称为“泛化实力”）。n在某些状况下,训练误差过小反而导致推广实力的下降,这就是过学习问题。n神经网络的过学习问题是阅历风险最小化原则失败的一个典型例子。用三角函数拟合随意点用三角函数拟合随意点学习的示例学习的示例困难性与推广实力（续）困难性与推广实力（续）n在有限样本状况下，n阅历风险最小并不确定意味着期望风险最小；n学习机器的困难性不但与所探讨的系统有关,而且要和有限的学习样本相适应；n学习精度和推广性之间似乎是一对不行调和的冲突,接受困难的学习机器虽然简洁使得学习误差更小,却往往丢失推广性；n传统的解决方法（例
14、如：接受正则化、模型选择、噪声干扰等方法以限制学习机器的困难度）缺乏坚实的理论基础。8.5 统计学习理论的核心内容统计学习理论的核心内容nSLT被认为是目前针对有限样本统计估计和预料学习的最佳理论，它从理论上较为系统地探讨了阅历风险最小化原则成立的条件、有限样本下阅历风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。nSLT的主要内容包括:n基于阅历风险原则的统计学习过程的一样性理论n学习过程收敛速度的非渐进理论n限制学习过程的推广实力的理论n构造学习算法的理论VC维维(函数的多样性函数的多样性)n为了探讨阅历风险最小化函数集的学习一样收敛速度和推广性，SLT定义了一些指标来
15、衡量函数集的性能，其中最重要的就是VC维(Vapnik-Chervonenkis Dimension)。nVC维：对于一个指示函数（即只有0和1两种取值的函数）集，假如存在h个样本能够被函数集里的函数依据全部可能的2h种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是能够打散的最大样本数目。n假如对随意的样本数，总有函数能打散它们，则函数集的VC维就是无穷大。VC维（续）维（续）n一般而言,VC维越大,学习实力就越强,但学习机器也越困难。n目前还没有通用的关于计算随意函数集的VC维的理论,只有对一些特殊函数集的VC维可以精确知道。nN维实数空间中线性分类器和线性实函数的VC维是n+1
16、。nSin(ax)的VC维为无穷大。nVCVC维（续）维（续）Open problem:对于给定的学习函数集,如何用理论或试验的方法计算其VC维是当前统计学习理论探讨中有待解决的一个难点问题。三个里程碑定理三个里程碑定理推广性的界nSLT系统地探讨了阅历风险和实际风险之间的关系,也即推广性的界。n依据SLT中关于函数集推广性界的理论,对于指示函数集中全部的函数,阅历风险 和实际风险 之间至少以概率 满足如下关系:n n n 其中，h是函数集的VC维,n是样本数。推广性的界（续1）n学习机器的实际风险由两部分组成:n训练样本的阅历风险n置信范围(同置信水平 有关,而且同学习机器的VC维和训练样本
17、数有关。n在训练样本有限的状况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与阅历风险之间可能的差就越大。推广性的界（续2）n在设计分类器时,不但要使阅历风险最小化,还要使VC维尽量小,从而缩小置信范围,使期望风险最小。n找寻反映学习机器的实力的更好参数，从而得到更好的界是SLT今后的重要探讨方向之一。结构风险最小化n传统机器学习方法中普遍接受的阅历风险最小化原则在样本数目有限时是不合理的,因此，须要同时最小化阅历风险和置信范围。n统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集依据VC维的大小排列;在每个子集中找寻最小阅历风险,在子集间折衷考虑阅历风险和
18、置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。结构风险最小化（续1）结构风险最小化（续2）n实现SRM原则的两种思路n在每个子集中求最小阅历风险,然后选择使最小阅历风险和置信范围之和最小的子集。n设计函数集的某种结构使每个子集中都能取得最小的阅历风险,然后只需选择适当的子集使置信范围最小,则这个子集中使阅历风险最小的函数就是最优函数。支持向量机方法事实上就是这种思路的实现。8.6 支持向量机概述n支持向量机概述n支持向量机理论n支持向量机n核函数n支持向量机实现8.6.1 支持向量机概述支持向量机概述n196
19、3年，Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一组特征子集,使得对特征子集的划分等价于对整个数据集的划分,这组特征子集就被称为支持向量(SV)。n1971年，Kimeldorf提出访用线性不等约束重新构造SV的核空间,解决了一部分线性不行分问题。n1990年，Grace,Boser和Vapnik等人起先对SVM进行探讨。n1995年，Vapnik正式提出统计学习理论。8.6.2 支持向量机理论支持向量机理论nSVM从线性可分状况下的最优分类面发展而来。n最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。nSVM考虑找寻一个满足分
20、类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是找寻一个分类面使它两侧的空白区域(margin)最大。n过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。支持向量机理论（续1）广义最优分类面广义最优分类面（续1）n假定训练数据n可以被一个超平面分开n我们进行正归化n此时分类间隔等于n使最大间隔最大等价于使 最小广义最优分类面（续2）n最优分类面问题可以表示成约束优化问题MinimizeSubject ton定义Lagrange函数 广义最优分类面（续3）nLagrange函数一个简洁的例子：x1=(0,0),y1=+1x2=(1,0),y
21、2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得w和b的值。8.6.3 支持向量机支持向量机n很多状况下，训练数据集是线性不行分的，Vapnik等人提出了用广义分类面（松弛子）来解决这一问题。n非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中找寻最优分类面。高维空间中的最优分类面n分类函数只涉及到训练样本之间的内积运算(xixj),因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现,甚至不必知道变换的形式。nSLT指出,依据Hibert-Schmidt原
22、理,只要一种运算满足Mercer条件,就可以作为内积运用。Mercer条件支持向量机n在最优分类面中接受适当的内积函数就可以实现某一非线性变换后的线性分类,而计算困难度却没有增加。支持向量机8.6.4 核函数核函数nSVM中不同的内积核函数将形成不同的算法,主要的核函数有三类：n多项式核函数n径向基函数nS形函数8.6.5 支持向量机实现支持向量机实现SVMlight-2.private:/usr/local/binsvm_learn,svm_classifybsvm-2.private:/usr/local/binsvm-train,svm-classify,svm-scalelibsvm-
23、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贝尔试验室对美国邮政手写数字库进行的试验分类器错误率人工表现2.5%决策树C4.516.2%最好的两层神经网络5.9%SVM4.0%SVM与神经网络（NN）的对比SVM的理论基础比NN更坚实，更像一门严谨的“科学”（三要素：问题的表示、问题的解决、证明）SVM 严格的数学推
24、理NN 猛烈依靠于工程技巧推广实力取决于“阅历风险值”和“置信范围值”，NN不能限制两者中的任何一个。NN设计者用超群的工程技巧弥补了数学上的缺陷设计特殊的结构，利用启发式算法，有时能得到出人意料的好结果。“我们必需从一起先就澄清一个观点，就是假如某事不是科学，它并不确定不好。比如说，爱情就不是科学。因此，假如我们说某事不是科学，并不是说它有什么不对，而只是说它不是科学。”by R.Feynman from The Feynman Lectures on Physics,Addison-Wesley同理，与SVM相比，NN不像一门科学，更像一门工程技巧，但并不意味着它就确定不好！主要应用领域n
25、手写数字识别n语音识别n人脸识别n文本分类8.7.2 支持向量机探讨支持向量机探讨n如何针对不同的问题选择不同的核函数仍旧是一个悬而未决的问题。n标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁棒性是至关重要的。8.7.3 支持向量机算法探讨支持向量机算法探讨n支持向量机的本质是解一个二次规划问题,虽然有一些经典（如对偶方法、内点算法等）,但当训练集规模很大时,这些算法面临着维数灾难问题。为此,人们提出了很多针对大规模数据集的SVM训练算法。支持向量机算法探讨（续1）n思路1：分解子问题块算法SMO算法(Sequential Minimal Optimization)n思路2
26、：序列优化n思路3：近邻SVM支持向量机算法探讨（续2）n训练SVM的绝大多数算法都是针对分类问题,只有一小部分算法考虑了回来函数的估计问题。n提高算法效率、降低困难度。支持向量机算法探讨（续3）nSVM增量学习算法的探讨n超球面SVM算法探讨nOne-class SVM算法nnSVM多值分类器算法nOne-against-the-rest（一对多方法）nOne-against-one（一对一方法）nMulti-class Objective Functions（多类SVM）nDecision Directed Acyclic Graph,DDAGnSVM Decision Treen超球面S
27、VM多值分类器n总结nSVM在模式识别、回来函数估计、预料等大量应用中取得了良好的效果nSVM存在两个主要问题：n二次规划的训练速度n核函数的选择n前途是光明的，道路是曲折的。课后编程实现题目（二选一）：设计并实现一个简洁的用于文本分类的SVM。设计并实现一个简洁的基于SVM的“新闻分别器”，主要用于对浙大BBS“缥缈水云间”中news版上的新闻进行分类。主要参考文献：nA tutorial on support vector machines for pattern recognition.Data Mining and Knowledge Discovery,1998,2(2)nVapni
28、k V N.The Nature of Statistical Learning Theory,NY:Springer-Verlag,1995（中译本：张学工译.统计学习理论的本质.清华高校出版社,2000）n【说明】：该书附带介绍了很多科学探讨的基本原则，很有启发、借鉴意义。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