PPT《*》

* 高级人工智能 史忠植 * 知识发现(数据挖掘)

第三章 史忠植 中国科学院计算技术研究所 支持向量机Support Vector machine * Chap8 SL Zhongzhi Shi * 内容提要 统计学习方法概述统计学习问题学习过程的泛化能力支持向量机SVM寻优算法应用 * Chap8 SL Zhongzhi Shi * 统计学习方法概述 统计方法是从事物的外在数量上的表现去推断该事物可能的规律性.

科学规律性的东西一般总是隐藏得比较深,最初总是从其数量表现上通过统计分析看出一些线索,然后提出一定的假说或学说,作进一步深入的理论研究.当理论研究 提出一定的结论时,往往还需要在实践中加以验证.就是说,观测一些自然现象或专门安排的实验所得资料,是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题,都需要用统计分析的方法处理. * Chap8 SL Zhongzhi Shi * 统计学习方法概述 近百年来,统计学得到极大的发展.我们可用下面的框架粗略地刻划统计学发展的过程:1900-1920 数据描述1920-1940 统计模型的曙光1940-1960 数理统计时代随机模型假设的挑战松弛结构模型假设1990-1999 建模复杂的数据结构 * Chap8 SL Zhongzhi Shi * 统计学习方法概述 从1960年至1980年间,统计学领域出现了一场革命,要从观测数据对依赖关系进行估计,只要知道未知依赖关系所属的函数集的某些一般的性质就足够了.引导这一革命的是60年代的四项发现:Tikhonov, Ivanov 和Philips 发现的关于解决不适定问题的正则化原则;

Parzen, Rosenblatt 和Chentsov 发现的非参数统计学;

Vapnik 和Chervonenkis 发现的在泛函数空间的大数定律,以及它与学习过程的关系;

Kolmogorov, Solomonoff 和Chaitin 发现的算法复杂性及其与归纳推理的关系. 这四项发现也成为人们对学习过程研究的重要基础. * Chap8 SVM Zhongzhi Shi * 统计学习方法概述 统计学习方法:传统方法: 统计学在解决机器学习问题中起着基础性的作用.传统的统计学所研究的主要是渐近理论,即当样本趋向于无穷多时的统计性质.统计方法主要考虑测试预想的假设和数据模型拟合.它依赖于显式的基本概率模型. 模糊集粗糙集支持向量机 * Chap8 SVM Zhongzhi Shi * 统计学习方法概述 统计方法处理过程可以分为三个阶段:(1)搜集数据:采样、实验设计(2)分析数据:建模、知识发现、可视化(3)进行推理:预测、分类 常见的统计方法有: 回归分析(多元回归、自回归等) 判别分析(贝叶斯判别、费歇尔判别、非参数判别等) 聚类分析(系统聚类、动态聚类等) 探索性分析(主元分析法、相关分析法等)等. * Chap8 SVM Zhongzhi Shi * 支持向量机 SVM是一种基于统计学习理论的机器学习方法,它是由Boser,Guyon, Vapnik在COLT-92上首次提出,从此迅速发展起来Vapnik V N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York Vapnik V N. 1998. Statistical Learning Theory. Wiley-Interscience Publication, John Wiley&

Sons, Inc目前已经在许多智能信息获取与处理领域都取得了成功的应用. * Chap8 SVM Zhongzhi Shi * 统计学习理论 统计学习理论是小样本统计估计和预测学习的最佳理论.假设输出变量Y与输入变量X之间存在某种对应的依赖关系,即一未知概率分布P(X,Y),P(X,Y)反映了某种知识.学习问题可以概括为:根据l个独立同分布( independently drawn and identically distributed )的观测样本train set,x1,y1),(x2,y2),…,(xn,yn) * Chap8 SVM Zhongzhi Shi * 函数估计模型 学习样本的函数:产生器 (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 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(x,?) and the equivalent representation of each f using its index ? G S LM x y y ^ * Chap8 SVM Zhongzhi Shi * 期望风险 学习到一个假设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进行预测而造成的损失.不同类型的学习问题有不同形式的损失函数. * Chap8 SVM Zhongzhi Shi * 而对train set上产生的风险Remp(w)被称为经验风险(学习的训练误差): 首先Remp(w)和R(w)都是w的函数,传统概率论中的定理只说明了(在一定条件下)当样本趋于无穷多时Remp(w)将在概率意义上趋近于R(w),却没有保证使Remp(w)最小的点也能够使R(w) 最小(同步最小). 经验风险 * Chap8 SVM Zhongzhi Shi * 根据统计学习理论中关于函数集的推广性的界的结论,对于两类分类问题中的指示函数集f(x, w)的所有函数(当然也包括使经验风险员小的函数),经验风险Remp(w)和实际风险R(w)之间至少以不下于1-η(0≤η≤1)的概率存在这样的关系: 经验风险 * Chap8 SVM Zhongzhi Shi * h是函数H=f(x, w)的VC维, l是样本数. VC维(Vapnik-Chervonenkis Dimension).模式识别方法中VC维的直观定义是:对一个指示函数集,如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开,则称函数集能够把h个样本打散.函数集的VC维就是它能打散的最大样本数目h. VC维*Chap8 SVM Zhongzhi Shi * 一般的学习方法(如神经网络)是基于 Remp(w) 最小,满足对已有训练数据的最佳拟和,在理论上可以通过增加算法(如神经网络)的规模使得Remp(w) 不断降低以至为0. 但是,这样使得算法(神经网络)的复杂度增加, VC维h增加,从而φ(h/l)增大,导致实际风险R(w)增加,这就是学习算法的过拟合(Overfitting). 过学习 * Chap8 SVM Zhongzhi Shi * 过学习Overfitting and underfitting Problem: how rich class of classifications q(x;