《支持向量机中科院》由会员分享，可在线阅读，更多相关《支持向量机中科院（81页珍藏版）》请在金锄头文库上搜索。
1、2019/1/25,Chap8 SVM Zhongzhi Shi,1,高级人工智能 第八章,史忠植 中国科学院计算技术研究所,支持向量机 Support Vector Machines,2019/1/25,Chap8 SVM Zhongzhi Shi,2,内容提要,统计学习方法概述 统计学习问题 学习过程的泛化能力 支持向量机 SVM寻优算法 应用,2019/1/25,Chap8 SVM Zhongzhi Shi,3,统计学习方法概述,统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。科学规律性的东西一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出一些线索，然后提出一定的
2、假说或学说，作进一步深入的理论研究。当理论研究 提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题，都需要用统计分析的方法处理。,2019/1/25,Chap8 SVM Zhongzhi Shi,4,统计学习方法概述,近百年来，统计学得到极大的发展。我们可用下面的框架粗略地刻划统计学发展的过程： 1900-1920 数据描述 1920-1940 统计模型的曙光 1940-1960 数理统计时代 随机模型假设的挑战 松弛结构模型假设 1990-1999 建模复杂的数据结构,2019/1/
3、25,Chap8 SVM Zhongzhi Shi,5,统计学习方法概述,从1960年至1980年间，统计学领域出现了一场革命，要从观测数据对依赖关系进行估计，只要知道未知依赖关系所属的函数集的某些一般的性质就足够了。引导这一革命的是60年代的四项发现： Tikhonov, Ivanov 和 Philips 发现的关于解决不适定问题的正则化原则； Parzen, Rosenblatt 和Chentsov 发现的非参数统计学； Vapnik 和Chervonenkis 发现的在泛函数空间的大数定律，以及它与学习过程的关系； Kolmogorov, Solomonoff 和Chaitin 发现的算
4、法复杂性及其与归纳推理的关系。 这四项发现也成为人们对学习过程研究的重要基础。,2019/1/25,Chap8 SVM Zhongzhi Shi,6,统计学习方法概述,统计学习方法： 传统方法: 统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的主要是渐近理论，即当样本趋向于无穷多时的统计性质。统计方法主要考虑测试预想的假设和数据模型拟合。它依赖于显式的基本概率模型。 模糊集 粗糙集 支持向量机,2019/1/25,Chap8 SVM Zhongzhi Shi,7,统计学习方法概述,统计方法处理过程可以分为三个阶段： （1）搜集数据：采样、实验设计 （2）分析数据：建模、知识发现
5、、可视化 （3）进行推理：预测、分类 常见的统计方法有: 回归分析（多元回归、自回归等） 判别分析（贝叶斯判别、费歇尔判别、非参数判别等） 聚类分析（系统聚类、动态聚类等） 探索性分析（主元分析法、相关分析法等）等。,2019/1/25,Chap8 SVM Zhongzhi Shi,8,支持向量机,SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，从此迅速发展起来 Vapnik V N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New Y
6、ork 564 Vapnik V N. 1998. Statistical Learning Theory. Wiley-Interscience Publication, John Wiley&Sons, Inc 目前已经在许多智能信息获取与处理领域都取得了成功的应用。,2019/1/25,Chap8 SVM Zhongzhi Shi,9,统计学习理论,统计学习理论是小样本统计估计和预测学习的最佳理论。 假设输出变量Y与输入变量X之间存在某种对应的依赖关系,即一未知概率分布P(X,Y)，P(X,Y)反映了某种知识。学习问题可以概括为:根据l个独立同分布( independently draw
7、n and identically distributed )的观测样本train set， (x1,y1),(x2,y2),(xn,yn),2019/1/25,Chap8 SVM Zhongzhi Shi,10,函数估计模型,学习样本的函数: 产生器 (G) generates observations x (typically in Rn), independently drawn from some fixed distribution F(x) 训练器Supervisor (S) labels each input x with an output value y according
8、to some fixed distribution F(y|x) 学习机Learning Machine (LM) “learns” from an i.i.d. l-sample of (x,y)-pairs output from G and S, by choosing a function that best approximates S from a parameterised function class f(x,), where is in the parameter set 关键概念: F(x,y), an i.i.d. l-sample on F, functions f(
9、x,) and the equivalent representation of each f using its index ,2019/1/25,Chap8 SVM Zhongzhi Shi,11,期望风险,学习到一个假设H=f(x, w) 作为预测函数,其中w是广义参数.它对F(X,Y)的期望风险R(w)是(即统计学习的实际风险)： 其中，f(x,w)称作预测函数集，w为函数的广义参数。f(x,w)可以表示任何函数集。L(y,f(x,w)为由于用f(x,w)对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。,2019/1/25,Chap8 SVM Zhongzhi Shi
10、,12,而对train set上产生的风险Remp(w)被称为经验风险(学习的训练误差):,首先Remp(w)和R(w)都是w的函数，传统概率论中的定理只说明了(在一定条件下)当样本趋于无穷多时Remp(w)将在概率意义上趋近于R(w)，却没有保证使Remp(w)最小的点也能够使R(w) 最小(同步最小)。,经验风险,2019/1/25,Chap8 SVM Zhongzhi Shi,13,根据统计学习理论中关于函数集的推广性的界的结论，对于两类分类问题中的指示函数集f(x, w)的所有函数(当然也包括使经验风险员小的函数)，经验风险Remp(w)和实际风险R(w)之间至少以不下于1-(01)的
11、概率存在这样的关系:,经验风险,2019/1/25,Chap8 SVM Zhongzhi Shi,14,h是函数H=f(x, w)的VC维, l是样本数.,VC维(Vapnik-Chervonenkis Dimension)。模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散。函数集的VC维就是它能打散的最大样本数目h。,VC维,2019/1/25,Chap8 SVM Zhongzhi Shi,15,一般的学习方法(如神经网络)是基于 Remp(w) 最小,满足对已有训练数据的最佳拟和,在理论上可以
12、通过增加算法（如神经网络）的规模使得Remp(w) 不断降低以至为0。 但是,这样使得算法（神经网络）的复杂度增加, VC维h增加,从而(h/l)增大,导致实际风险R(w)增加,这就是学习算法的过拟合(Overfitting).,过学习,2019/1/25,Chap8 SVM Zhongzhi Shi,16,过学习Overfitting and underfitting,Problem: how rich class of classifications q(x;) to use.,underfitting,overfitting,good fit,Problem of generalizat
13、ion: a small emprical risk Remp does not imply small true expected risk R.,2019/1/25,Chap8 SVM Zhongzhi Shi,17,学习理论的四个部分,1. 学习过程的一致性理论 What are (necessary and sufficient) conditions for consistency (convergence of Remp to R) of a learning process based on the ERM Principle? 2.学习过程收敛速度的非渐近理论 How fast
14、 is the rate of convergence of a learning process? 3. 控制学习过程的泛化能力理论 How can one control the rate of convergence (the generalization ability) of a learning process? 4. 构造学习算法的理论 How can one construct algorithms that can control the generalization ability?,2019/1/25,Chap8 SVM Zhongzhi Shi,18,结构风险最小化归纳
15、原则 (SRM),ERM is intended for relatively large samples (large l/h) Large l/h induces a small which decreases the the upper bound on risk Small samples? Small empirical risk doesnt guarantee anything! we need to minimise both terms of the RHS of the risk bounds The empirical risk of the chosen An expr
16、ession depending on the VC dimension of ,2019/1/25,Chap8 SVM Zhongzhi Shi,19,结构风险最小化归纳原则 (SRM),The Structural Risk Minimisation (SRM) Principle Let S = Q(z,),. An admissible structure S1S2SnS: For each k, the VC dimension hk of Sk is finite and h1h2hnhS Every Sk is either is non-negative bounded, or satisfies for some (p,k),2019/1/25,Chap8 SVM Zhongzhi Shi,20,The SRM Principle continued For given z1,zl and an admissible structure S
