第5 3章 统计学习理论与支持机简介

1、 模 式 识 别 统计学习理论与支持向量机简介 要点 o 实例学习能力与推广能力o 复杂性与推广能力 o 期望风险最小化与期望风险最小化o 支持向量机原理 主要内容 o 统计学习理论的研究内容o 学习问题研究的四个阶段o 人物简介 o 统计学习理论的理论介绍o 应用领域 o 网络资源 统计学习理论的研究内容 o 人的智慧： n 实例学习能力与推广能力 o 基于数据的机器学习问题： n 是现代智能技术中的重要方面 n 研究通过对已知数据的学习，找到数据内在的相互依赖关系，从而对未知数据的预测或对性质进行判断 统计学习理论的研究内容 o 目前机器学习方法存在的问题现有机器学习方法（模式识别、神经网

2、络等）共同的理论基础之一是统计学 传统统计学基础是样本数目趋于无穷大时的渐近理论 ,现有学习方法也多是基于此假设 实际问题中 ,样本数有限的 ,因此理论上优秀的学习方法实际中表现不尽人意 统计学习理论的研究内容 o 统计学习理论： 把学习问题看成是一个基于经验数据进行 函数估计的一般问题，研究关于学习和推广性的统计理论的基本思想。 针对小样本情况研究统计学习规律的理论， 核心思想是通过控制学习机器的容量实现对推广能力的控制。 SVM是基于统计学习理论而发明的一种 工具。 学习问题研究的四个阶段 o 第一个学习机器的创立（60年代） n 起源与20世纪30年代的Fisher理论没有考虑归纳推断问

3、题，不属于机器学习理论 n 1962 Rosenblatt第一个学习机器模型， 感知器，感知器为神经元选择适当的系数 n 1962 Novikoff 关于感知器的第一个定理，学习理论的开始。 学习问题研究的四个阶段 应用分析学派认为，使学习机器具有推广能力的唯一因素是训练集误差最小，这是不言而喻的；理论分析学派认为需要更智能化的归纳原则。 学习问题研究的四个阶段 o 学习理论的创立（6070年代） n 其它类型学习机器：Widrow的Madaline自适应学习机；Steinbuch的学习矩阵等。作为解决实际问题的工具来研究，没有作为学习现象的一般模型。为了解决实际问题的的各种逻辑函数程序 （决

4、策树等）、隐马尔可夫模型有没有涉及一般学习现象的研究。 学习问题研究的四个阶段 经验风险最小 化原 则 的 理论： 1968 Vapnik & Chervonenkis 模式识别问题的VC熵和VC维概念；泛函空间的大数定律，得到收敛速度的非渐进界； 1971 Vapnik & Chervonenkis 上述理论的证明，为结构风险最小化奠定基础。19761981，实函数集VC熵和VC维概 险最小化原则。 学习问题研究的四个阶段 1989 Vapnik & Chervonenkis 经验风险最小化归纳原则和最大似然方法的一致性的充分条件。 90年代，能够控制推广性能的新学习机器的合成，SVM 学习

5、问题研究的四个阶段 o 解决不适定问题的理论： n Tikhonov,Ivanov和Phillips发现解决不适定 问题的正则化原则。 密度估计的非参数方法： n Parzen，Rosenblatt和Chentsov发现的非参 数统计学。 算法复杂度思想： n Kolmogorov，Solomonoff和Chaitin发现的 算法复杂性及其与归纳推理的关系。 oo 学习问题研究的四个阶段 o 神经网络的创立（80年代）1986 LeCun，Rumelhart，Hinton和Williams多层感知器的后向传播算法 三个失败（自然语言翻译，通用问题求解器，大系统自动控制机） 理论分析目标的简化,

6、强调复杂理论无用，提倡简单的算法 术语改变（感知器-神经网络）；与生理学家合作；构造利用大脑来推广的模型。 1984 可能近似正确（probably approximately correct， PAC）模型，统计分析用于人工智能领域。 学习问题研究的四个阶段 o 回到起点（90年代）统计学习理论开始吸引更多学者 结构风险最小化原则和最小描述长度原则成为一个研究热点 小样本数理论开始展开。 开始研究对任意数目的观测，如何得到最高的推广能力。 人物简介 Vladimir Vapnik： o1958年硕士毕业于苏联乌兹别 克 的 Uzbek State Universityo19611990莫斯科

7、控制科学研究所，计算机科学研究处的负责人 oAT&T实验室研究中心的技术领导；伦敦大学教授 理论介绍:机器学习的基本问题 o 机器学习问题表示 根据 n个独立同分布观测样本:(x1 , y1 ) , (x2 , y2 ) , , (xn, yn),在一组函数 f (x,w)中求一个最优的函数 f (x,w 0) 对依赖关系进行估计 ,使期望风险 R(w)=L(y, f(x,w0)dF(x, y)最小 理论介绍:机器学习的基本问题 o 经验风险最小化 学习的目标在于使期望风险最小化，传统的学习方法中采用了所谓经验风险最小化(ERM)准则 ,即用样本定义经验风险 n1R(w) =L(y , f (

8、x ,w)empiini=1作为对期望风险的估计 ,设计学习算法使它最小化n 用 ERM准则代替期望风险最小化没有充分的理论论证 理论介绍:机器学习的基本问题 o 复杂性与推广能力过学习问题 过学习现象原因：一是因为样本不充分 ,二是学习机器设计不合理 ,这两个问题是互相关联的。 一个简单的例子 ,假设有一组实数样本 x, y , y取值在 0 , 1 之间 ,那么不论样本是依据什么模型产生的 , 只要用函数 f(x, ) =sin(x)去拟合它们 (是待定参数 ) ,总能够找到一个 使训练误差为零 由此可看出 ,有限样本情况下 , 1 )经验风险最小并不一定意味着期望风险最小 ; 2 )学习

9、机器的复杂性不但应与所研究的系统有关 ,而且要和有限数目的样本相适应 统计学习理论的核心内容 o 统计学习理论就是研究小样本统计估计和预测的理论 ,主要内容包括四个方面:n 1 )经验风险最小化准则下统计学习一致性的条件 ;n 2 )在这些条件下关于统计学习方法推广性的界的结论 ;n 3 )在这些界的基础上建立的小样本归纳推理准则 ;n 4 )实现新的准则的实际方法 (算法 ) .n 其中 ,最有指导性的理论结果是推广性的界 , 与此相关的一个核心概念是 VC维 . 统计学习理论的核心内容 VC维o直观定义:对一个指示函数集 ,如果存在 h个样本能够被函数集中的函数按所有可能的 2h 种形式分

10、开 , 则称函数集能够把 h个样本打散 ;函数集的 VC维就是它能打散的最大样本数目 h例如，n维实数空间中线性分类器和线性实函数的VC维是 n+1；f(x, ) = sin(x)的 VC维则为无穷大 VC维反映了函数集的学习能力 , VC维越大则学习机器越复杂 (容量越大 )尚没有通用的关于任意函数集 VC维计算的理论 统计学习理论的核心内容 o 推广性的界经验风险和实际风险之间以至少 1 -的概率满足如下关系 ( h(ln(2n / h) + 1) - ln(h / 4)R(w) Remp (w) +)n该结论从理论上说明学习机器的实际风险是由两部分组成的 :一是经验风险 (训练误差 )

11、,另一部分称作置信范围 ,它和学习机器的 VC维及训练样本数有关 它表明 ,在有限训练样本下 ,学习机器的 VC维越高 (复杂性越高 )则置信范围越大 ,导致真实风险与经验风险之间可能的差别越大 理论介绍:机器学习的基本问题 o 结构风险最小化经验风险原则在样本有限时是不合理的 ,我们需要同时最小化经验风险和置信范围 在传统方法中 ,选择学习模型和算法的过程就是调整置信范围的过程.因为缺乏理论指导,这种选择过分依赖使用者“技巧” 结构风险最小化 (Structural Risk Minimization或译有序风险最小化)即 SRM准则 实 现 SRM 原 则 可 以 有 两 种 思 路 :1

12、）在每个子集中求最小经验风险 ,然后选择使最小经验风险和置信范围之和最小的子集; 理论介绍:机器学习的基本问题 2）设计函数集的某种结构使每个子集中都能取得最小的经验风险 (如使训练误差为 0 ) ,然后只需选择选择适当的子集使置信范围最小 支持向量机 o 核心内容是在1992到 1995年间提出的o 广义最优分类面 SVM从线性可分情况下的最优分类面发展而来的 基本思想可用两维情况说明：所谓最优分类线就是要求分类线不但能将两类正确分开 (训练错误率为 0 ) ,而且使分类间隔最大 . 使分类间隔最大实际上就是对推广能力的控 制 ,这是 SVM的核心思想之一 支持向量机 o 两类分类问题y(x

13、)= wT(x)+ b训练样本集 oN 输入 x1, . . . , xNo目标值 t1, . . . , tN测试样本 tn 1, 1ox 根据输出的符号来分类 y(x)假设线性可分 otn y(xn) 0 支持向量机 o x 到分类决策平面(y(x) = 0)的距离:|y(x)|/wo xn到分类决策平面(y(x) = 0)的距离: 支持向量机 o 边缘距离尺度因子: w w and b b距离决策面最近的点 所有的数据点:优化问题: 最大化|w|1 二次优化问题 支持向量机 拉格朗日函数nL(w, b,a ) = 1 / 2(w w) - ai yi (w xi ) + b -1i =1

14、对w和b求偏导数nni =1aw = ai yi xiy= 0iii =1代入L函数，消去w和ba 0,i = 1,L, nin1nQ(a ) = ai -a a j yi y j(x i x j )in2y ai =1i, j=1= 0iii=1 支持向量机 最终的分类函数为： f (x) = sgn(ai yi K (xi x) -b0 )支持向量 其中：=ay xdef0 x j ) = j(xi ) j (x j )K (xi0iii支持向量b= 1 ( x* (1) + ( x* (-1)0002 支持向量机 o支持向量机 对非线性问题 ,可以通过非线性变换转化为某个高维空间中的线性

15、问题 在最优分类面中采用适当的内积函数 K(xi, xj)取代点积，就可以实现某一非线性变换 后的线性分类 支持向量机 高维空间的推广： f (x) = sgn(a 0 y K (x x) - b )iii0支持向量nn12W (a) = aiaa-y y K (x x )ijijiji=1i, j =1n yiai i=1a 0,= 0i = 1,L, ni SVM与神经网络的类似性 支持向量机:核函数 y(x) = wT(x)+ b分类函数defK (xi x j ) = j (xi ) j (x j )核函数核函数就是x映射到高维空间(x)后的点积。 通过核函数可以将空间映射以及点积运算

16、合并。 支持向量机 核函数有三类 多项式核函数，所得到 q阶多项式分类器K (x, xi ) = (x xi ) + 1q径向基函数 (RBF) 所得分类器| x - x|2K (x, xi ) = exp- i2 s采用 Sigmoid函数作为内积K (x, xi ) = tanh(v(x xi ) + c) 线性不可分的支持向量机y=-1 soft marginy=01y=1parameterC 01=0The classification constraints=0 支持向量机的误差函数 支持向量机解决函数拟合问题（回归问题） o 误差函数 线性回归稀疏解 e-insensitive e

17、rror function正则化错误 SVMs for regression 3 SVMs for regression 4 o Slack variables The condition for a target pointthe condition for slack variables 支持向量机 o收敛算法 标准chunking算法 (投影共轭梯度PCG,二次的动态规划) 分解算法 SMO算法 应用领域 o 模式识别方面 贝尔实验室对美国邮政手写数字库进行的实验 人工识别错误率 2 . 5%决策树错误率 16. 2 %两层神经网络错误率 5. 9%五层神经网络错误率为 5. 1 % 应用领域 三种 SVM方法 (不同核函数 )得到的错误率分别为 4. 0 %、4. 1 %和 4. 2 %直接采用了 1 61 6的字符点阵作为SVM的输入 ,并没有进行专门的特征提取说明:不同的 SVM方法可以得到性能相近的结果 三种 SVM求出的支持向量中有 80 %以上是重合的 应用领域 oo SVM与神经网络相结合对笔迹进行在线适应 MIT用 SVM进行的人脸检测实验也取得了较好的 效果可以较好地学会在图像中找出可能的人脸位置人脸识别、三维物体识别 用于识别的主动学习、基于支撑向量机的说话人确认系统、基于支持向量机与无监督聚类相结