1、模模 式式 识识 别别统计学习理论与支持向量机简介统计学习理论与支持向量机简介要点o 实例学习能力与推广能力o 复杂性与推广能力o 期望风险最小化与期望风险最小化o 支持向量机原理主要内容 o统计学习理论的研究内容o学习问题研究的四个阶段o人物简介o统计学习理论的理论介绍o应用领域o网络资源统计学习理论的研究内容o 人的智慧：n 实例学习能力与推广能力o 基于数据的机器学习问题：n 是现代智能技术中的重要方面n 研究通过对已知数据的学习，找到数据内在的相互依赖关系，从而对未知数据的预测或对性质进行判断统计学习理论的研究内容o 目前机器学习方法存在的问题n 现有机器学习方法（模式识别、神经网络等
2、）共同的理论基础之一是统计学n 传统统计学基础是样本数目趋于无穷大时的渐近理论,现有学习方法也多是基于此假设n 实际问题中,样本数有限的,因此理论上优秀的学习方法实际中表现不尽人意统计学习理论的研究内容o 统计学习理论：n 把学习问题看成是一个基于经验数据进行函数估计的一般问题，研究关于学习和推广性的统计理论的基本思想。n 针对小样本情况研究统计学习规律的理论，核心思想是通过控制学习机器的容量实现对推广能力的控制。n SVM是基于统计学习理论而发明的一种工具。学习问题研究的四个阶段o 第一个学习机器的创立（60年代）n 起源与20世纪30年代的Fisher理论没有考虑归纳推断问题，不属于机器学
3、习理论n 1962 Rosenblatt第一个学习机器模型，感知器，感知器为神经元选择适当的系数n 1962 Novikoff 关于感知器的第一个定理，学习理论的开始。学习问题研究的四个阶段n 应用分析学派认为，使学习机器具有推广能力的唯一因素是训练集误差最小，这是不言而喻的；理论分析学派认为需要更智能化的归纳原则。学习问题研究的四个阶段o 学习理论的创立（6070年代）n 其它类型学习机器：Widrow的Madaline自适应学习机；Steinbuch的学习矩阵等。作为解决实际问题的工具来研究，没有作为学习现象的一般模型。为了解决实际问题的的各种逻辑函数程序（决策树等）、隐马尔可夫模型有没有
4、涉及一般学习现象的研究。学习问题研究的四个阶段n 经验风险最小 化原 则 的 理论：1968 Vapnik&Chervonenkis 模式识别问题的VC熵和VC维概念；泛函空间的大数定律，得到收敛速度的非渐进界；1971 Vapnik&Chervonenkis 上述理论的证明，为结构风险最小化奠定基础。19761981，实函数集VC熵和VC维概念；大数定律、完全有界的函数集和无界函数集一致收敛速度的界，以及结构风险最小化原则。学习问题研究的四个阶段1989 Vapnik&Chervonenkis 经验风险最小化归纳原则和最大似然方法的一致性的充分条件。90年代，能够控制推广性能的新学习机器的合
5、成，SVM 学习问题研究的四个阶段o 解决不适定问题的理论：n Tikhonov,Ivanov和Phillips发现解决不适定问题的正则化原则。o 密度估计的非参数方法：n Parzen，Rosenblatt和Chentsov发现的非参数统计学。o 算法复杂度思想：n Kolmogorov，Solomonoff和Chaitin发现的算法复杂性及其与归纳推理的关系。学习问题研究的四个阶段o 神经网络的创立（80年代）n1986 LeCun，Rumelhart，Hinton和Williams多层感知器的后向传播算法 n三个失败（自然语言翻译，通用问题求解器，大系统自动控制机）n理论分析目标的简化,
6、强调复杂理论无用，提倡简单的算法 n术语改变（感知器-神经网络）；与生理学家合作；构造利用大脑来推广的模型。n1984 可能近似正确（probably approximately correct，PAC）模型，统计分析用于人工智能领域。学习问题研究的四个阶段o 回到起点（90年代）n统计学习理论开始吸引更多学者n结构风险最小化原则和最小描述长度原则成为一个研究热点n小样本数理论开始展开。n开始研究对任意数目的观测，如何得到最高的推广能力。人物简介Vladimir Vapnik：o1958年硕士毕业于苏联乌兹别克的Uzbek State Universityo19611990莫斯科控制科学研究所
7、，计算机科学研究处的负责人oAT&T实验室研究中心的技术领导；伦敦大学教授 理论介绍:机器学习的基本问题 o 机器学习问题表示 根据 n个独立同分布观测样本:(x1,y1),(x2,y2),(xn,yn),在一组函数 中求一个最优的函数 对依赖关系进行估计,使期望风险最小),(),(,()(0yxdFxfyLR),(0 xf),(xf理论介绍:机器学习的基本问题 o 经验风险最小化学习的目标在于使期望风险最小化，传统的学习方法中采用了所谓经验风险最小化(ERM)准则,即用样本定义经验风险作为对期望风险的估计,设计学习算法使它最小化n 用 ERM准则代替期望风险最小化没有充分的理论论证niiie
8、mpxfyLnR1),(,(1)(理论介绍:机器学习的基本问题 o 复杂性与推广能力n过学习问题n过学习现象原因：一是因为样本不充分,二是学习机器设计不合理,这两个问题是互相关联的。n一个简单的例子,假设有一组实数样本 x,y,y取值在 0,1 之间,那么不论样本是依据什么模型产生的,只要用函数 f(x,)=sin(x)去拟合它们(是待定参数),总能够找到一个 使训练误差为零n由此可看出,有限样本情况下,1)经验风险最小并不一定意味着期望风险最小;2)学习机器的复杂性不但应与所研究的系统有关,而且要和有限数目的样本相适应统计学习理论的核心内容o 统计学习理论就是研究小样本统计估计和预测的理论,
9、主要内容包括四个方面:n 1)经验风险最小化准则下统计学习一致性的条件;n 2)在这些条件下关于统计学习方法推广性的界的结论;n 3)在这些界的基础上建立的小样本归纳推理准则;n 4)实现新的准则的实际方法(算法).n 其中,最有指导性的理论结果是推广性的界,与此相关的一个核心概念是 VC维.统计学习理论的核心内容o VC维n 直观定义:对一个指示函数集,如果存在 h个样本能够被函数集中的函数按所有可能的 种形式分开,则称函数集能够把 h个样本打散;函数集的 VC维就是它能打散的最大样本数目 hn 例如，n维实数空间中线性分类器和线性实函数的 VC维是 n+1；f(x,)=sin(x)的 VC
10、维则为无穷大n VC维反映了函数集的学习能力,VC维越大则学习机器越复杂(容量越大)n 尚没有通用的关于任意函数集 VC维计算的理论h2统计学习理论的核心内容o 推广性的界n经验风险和实际风险之间以至少 1-的概率满足如下关系n该结论从理论上说明学习机器的实际风险是由两部分组成的:一是经验风险(训练误差),另一部分称作置信范围,它和学习机器的 VC维及训练样本数有关n它表明,在有限训练样本下,学习机器的 VC维越高(复杂性越高)则置信范围越大,导致真实风险与经验风险之间可能的差别越大)4/ln()1)/2(ln()()(nhnhRRemp理论介绍:机器学习的基本问题 o 结构风险最小化 n经验
11、风险原则在样本有限时是不合理的,我们需要同时最小化经验风险和置信范围n在传统方法中,选择学习模型和算法的过程就是调整置信范围的过程.因为缺乏理论指导,这种选择过分依赖使用者“技巧”n结构风险最小化(Structural Risk Minimization或译有序风险最小化)即 SRM准则n实现 SRM原则可以有两种思路:1）在每个子集中求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集;理论介绍:机器学习的基本问题 2）设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为 0),然后只需选择选择适当的子集使置信范围最小支持向量机o 核心内容是在1992到 1995
12、年间提出的o 广义最优分类面 n SVM从线性可分情况下的最优分类面发展而来的n 基本思想可用两维情况说明：所谓最优分类线就是要求分类线不但能将两类正确分开(训练错误率为 0),而且使分类间隔最大.使分类间隔最大实际上就是对推广能力的控制,这是 SVM的核心思想之一 支持向量机n 公式表示最优超平面：假定训练数据(x1,y1)(xl,yl),y=+1或-1 可以被超平面 分开。则，可以得到下面的紧凑形式表示的不等式：使 最小化的就是最优超平面0)(bxlibxyii,11)(2)(支持向量机n 拉格朗日函数1(,)1/2()()1niiiiLbyxb 1niiiiy x10niiiy对w和b求
13、偏导数代入L函数，消去w和b1,11()()2nniijijijii jQy yxx niiiy10nii,1,0支持向量机n最终的分类函数为：其中：支持向量iiixy00)1()1(21*0*00 xxb)(sgn()(00byfiii支持向量xxx支持向量机o支持向量机n对非线性问题,可以通过非线性变换转化为某个高维空间中的线性问题n在最优分类面中采用适当的内积函数 K(xi,xj)取代点积，就可以实现某一非线性变换后的线性分类支持向量机n高维空间的推广：niiiy10nii,1,0ninjijijijiixxKyyW11,)(21)()(sgn()(00bKyfiii支持向量xxxSVM
14、与神经网络的类似性支持向量机n核函数有三类多项式核函数，所得到 q阶多项式分类器径向基函数(RBF)所得分类器 采用 Sigmoid函数作为内积 qiixxxxK 1)(),(|exp),(22iixxxxK)(tanh(),(cxxvxxKii支持向量机o收敛算法n标准chunking算法(投影共轭梯度PCG,二次的动态规划)n分解算法nSMO算法 应用领域o 模式识别方面n 贝尔实验室对美国邮政手写数字库进行的实验 人工识别错误率 2.5%决策树错误率 16.2%两层神经网络错误率 5.9%五层神经网络错误率为 5.1%应用领域三种 SVM方法(不同核函数)得到的错误率分别为 4.0%、4
15、.1%和 4.2%直接采用了 1 61 6的字符点阵作为 SVM的输入,并没有进行专门的特征提取 说明:不同的 SVM方法可以得到性能相近的结果三种 SVM求出的支持向量中有 80%以上是重合的 应用领域o SVM与神经网络相结合对笔迹进行在线适应o MIT用 SVM进行的人脸检测实验也取得了较好的效果可以较好地学会在图像中找出可能的人脸位置o 人脸识别、三维物体识别o 用于识别的主动学习、基于支撑向量机的说话人确认系统、基于支持向量机与无监督聚类相结合的中文网页分类器、o 特征提取、特征选择和学习o 目标检测、遥感图像分析、图像分类、基于支持向量机的相关反馈图像检索算法应用领域o 非线性时间
16、序列预测o 支撑向量决策树用于数据仓库、数据浓缩o 在函数拟合方面,主要实验尚属于原理性研究,包括函数逼近、时间序列预测及数据压缩等o 其它有关研究还有对 SVM中优化算法实现的研究、改进的 SVM方法甚至硬件实现研究等 网络资源nhttp:/www.kernel-machines.org/nhttp:/kernel-machines.org/nips97/book.htmlnhttp:/ Vectors源程序 nNearest Point Algorithm.by Sathiya Keerthi(in FORTRAN).nSVM Java Applet.by Chris Burges et
17、al.nBSVM.A decomposition method for bound-constrained SVM formulations.nQP SVM Classification and Regression.Fortran Implementation.nChunking Code.by C.Saunders,M.O.Stitson,J.Weston,L.Bottou,B.Schlkopf,and A.Smola at Royal Holloway,AT&T,and GMD FIRST(Documentation).nInterior Point Optimizer for SVM
18、Pattern Recognition.by Alex Smola.nHeroSvm1.0.A high performance DLL for training SVM on a very large training set efficiently.nLEARNSC.SVM,NN and FL MATLAB based user-friendly routines.nLIBSVM.An SVM library with a graphic interface.nlooms.a leave-one-out model selection software based on BSVM.nM-S
19、VM.Multi-class support vector machine for very large problems.Support Vectors源程序 nM-SVM.Multi-class support vector machine for very large problems.nmySVM.SVM implementation for pattern recognition and regression.nmySVM and SVMlight for Windows.SVM implementation for Windows,uses Microsoft Visual C+6
20、.0.nmySVM/db.SVM implementation to be run inside a database.nSequential Minimal Optimization.by Xianping Ge.nSMOBR.SMOBR is an implementation of the original Sequential Minimal Optimisation proposed by Platt written in C+.nSvmFu.by Ryan Rifkin.nSVMLight.by Thorsten Joachims.nSVM/LOO.Matlab code for
21、SVM incremental learning and decremental unlearning(LOO validation).nSVM/optima.SVM QP routines in Fortran for classification/regression.nSVMTorch.Support Vector Machine for Large-Scale Regression and Classification Problems.nMatlab SVM Toolbox.by Steve Gunn.nMatlab SVM Toolbox.Matlab implementation
22、 in the style of SVMlight,can train 1-norm and 2-norm SVMs.nOSU SVM Classifier Matlab Toolbox.A matlab toolbox with a C+mex core to fast implement the SVM classifiers.nSVM Toolbox.Object Oriented MATLAB Support Vector Machine Toolbox,including C+MEX implementation of the sequential minimal optimisation algorithm.nWinSVM.SVM program for running under Windows.It uses SMO algorithm,so it is very fast and easy to use.nWinSVM.SVM for windows,easy to use.
