1、统计学习理论统计学习理论Chapt 1:学习问题的表示学习问题的表示Outline函数估计模型函数估计模型风险最小化问题风险最小化问题三种主要的学习问题三种主要的学习问题学习问题的一般表示学习问题的一般表示经验风险最小化归纳原则经验风险最小化归纳原则学习理论的四个部分学习理论的四个部分非正式推导和评述非正式推导和评述1outline函数估计模型函数估计模型样本学习的一般模型样本学习的一般模型产生器产生器G,F(x)训练器训练器S,F(yx)学习机器学习机器LM,函数集函数集f(x,a)学习问题的目的学习问题的目的从给定的函数集从给定的函数集f中选出中选出能够最好地逼近训练器能够最好地逼近训练器
2、响应的函数；响应的函数；训练集训练集F(x,y)=F(x)F(yx)由（由（x1y1），），（xmym）组成）组成GSLMxyyoutline风险最小化问题风险最小化问题损失函数损失函数风险泛函风险泛函目的：使得风险泛函最小的函数目的：使得风险泛函最小的函数,L y fx,(,)RL y fdFyxx0,fxoutline三种主要的学习问题三种主要的学习问题模式识别模式识别训练器的输出为训练器的输出为0/1f(x,),为指示函数集为指示函数集损失函数损失函数分类错误分类错误学习问题：在概率测度学习问题：在概率测度F(x,y)未知，但是训练数据未知，但是训练数据已知情况下，寻找使分类错误的概率最
3、小的函数已知情况下，寻找使分类错误的概率最小的函数0(,),(,)1(,)if yfL y fif yfxxx三种主要的学习问题三种主要的学习问题回归估计回归估计训练器的输出实数值训练器的输出实数值f(x,),为实数函数为实数函数回归函数回归函数损失函数损失函数学习问题：在概率测度学习问题：在概率测度F(x,y)未知，但是训练数据未知，但是训练数据已知情况下，已知情况下，对采用平方误差损失函数的风险泛函对采用平方误差损失函数的风险泛函最小化最小化2,(,)(,)L y fyfxx 00,|ffydF yxxx三种主要的学习问题三种主要的学习问题密度估计密度估计密度函数集密度函数集(x,),损失
4、函数损失函数学习问题：在相应的概率测度学习问题：在相应的概率测度F(x,y)未知，但是给未知，但是给出了独立同分布数据出了独立同分布数据x1xl的情况下，使风险泛的情况下，使风险泛函最小化函最小化outline(,)log(,)L pp xx学习问题的一般表示学习问题的一般表示定义在空间定义在空间Z上的概率测度上的概率测度F(z)函数的集合函数的集合Q(z,),独立同分布样本独立同分布样本z1zl风险泛函风险泛函,(),RQ zdF zoutline经验风险最小化归纳原则经验风险最小化归纳原则ERM归纳原则归纳原则经验风险泛函经验风险泛函用使得经验风险最小的函数用使得经验风险最小的函数Q(z,
5、l)来逼近来逼近使风险泛函最小的函数使风险泛函最小的函数Q(z,0)11,lempiiRQ zl经验风险最小化归纳原则经验风险最小化归纳原则ERM原则的体现原则的体现最小二乘方法最小二乘方法最大似然方法（等价）最大似然方法（等价）211,lempiiiRyf xl11ln,lempiiRp xl outline学习理论的四个部分学习理论的四个部分研究的四个问题研究的四个问题一个基于一个基于ERM原则的学习过程具有一致原则的学习过程具有一致性的条件（充分必要条件）是什么？性的条件（充分必要条件）是什么？这个学习过程收敛的速度有多快？这个学习过程收敛的速度有多快？如何控制这个学习过程的收敛速度（推
6、广如何控制这个学习过程的收敛速度（推广能力）？能力）？怎样构造能够控制推广能力的算法？怎样构造能够控制推广能力的算法？学习理论的四个部分学习理论的四个部分四个理论四个理论学习过程一致性理论学习过程一致性理论学习过程收敛速度的非渐近理论学习过程收敛速度的非渐近理论控制学习过程的推广能力的理论控制学习过程的推广能力的理论构造学习算法的理论构造学习算法的理论outline非正式推导和评述非正式推导和评述1解决学习问题的传统模式解决学习问题的传统模式密度估计的非参数方法密度估计的非参数方法用有限数量信息解决问题的基本原则用有限数量信息解决问题的基本原则基于经验数据的风险最小化模型基于经验数据的风险最小
7、化模型随机逼近推理随机逼近推理outline非正式推导和评述1 第一章中给出的学习问题的表示反映了两个主要的要求：第一章中给出的学习问题的表示反映了两个主要的要求：(1)从一个宽的函数集合中估计待求的函数；从一个宽的函数集合中估计待求的函数；(2)在有限数量的例子的基础上估计待求的函数。在有限数量的例子的基础上估计待求的函数。在在(创建于创建于20年代和年代和30年代的年代的)传统理论体系中发展起来的传统理论体系中发展起来的方法没有考虑到这些要求。方法没有考虑到这些要求。因此，在因此，在60年代，人们在两个方向上进行了很大的努力，年代，人们在两个方向上进行了很大的努力，一是把传统的结果推广到范
8、围更宽的函数集合，二是针对一是把传统的结果推广到范围更宽的函数集合，二是针对小样本数目改进已有技术。小样本数目改进已有技术。下面我们将对其中的一些研究进行订论。下面我们将对其中的一些研究进行订论。密度估计密度估计问题（问题（最大似然方法最大似然方法）在传统理论体系的框架中，函数估计在传统理论体系的框架中，函数估计的所有模型都是基于最大似然方法的。的所有模型都是基于最大似然方法的。它成了传统体系下的一个归纳引擎。它成了传统体系下的一个归纳引擎。密度估计密度估计问题（问题（最大似然方法最大似然方法）问题的描述设问题的描述设p(x,),是一个函数密度集合，是一个函数密度集合，设未知的密度设未知的密度
9、p(x,0)属于这个函数集合属于这个函数集合独立同分布数据：独立同分布数据：x1xl最大似然方法最大似然方法在在20年代，年代，Fisher(1952)研究出了估计密度函研究出了估计密度函数的未知参数的最大似然方法，提出用使泛函数的未知参数的最大似然方法，提出用使泛函最大的参数取值来逼近未知的参数最大的参数取值来逼近未知的参数。1ln,liiLpx模式识别（判别分析）问题模式识别（判别分析）问题Fisher的模型的模型-存在两类数据存在两类数据两个不同的密度两个不同的密度p1(x,*)，p2(x,*)设第一类数据出现的概率为设第一类数据出现的概率为q1第二类出现的概率为第二类出现的概率为1-q
10、1决策规则决策规则:使错误的概率最小使错误的概率最小*1112,1,q pqpxx*1121sgn ln,ln,ln1qf xppqxx模式识别（判别分析）问题Fisher的模型-存在两类数据两个不同的密度p1(x,*)，p2(x,*)设第一类数据出现的概率为q1第二类出现的概率为1-q1决策规则:使错误的概率最小模式识别（判别分析）问题决策规则决策规则:使错误的概率最小使错误的概率最小如果知道这两个统计规律和概率如果知道这两个统计规律和概率q1的值，可以立的值，可以立即构造出这样一个规则：若向量即构造出这样一个规则：若向量x属于第一类的概属于第一类的概率不小于它属于第二类的概率，决策规则就认
11、为率不小于它属于第二类的概率，决策规则就认为这个向量属于第一类。这个向量属于第一类。这个决策规则可以取得最小的错误率。所谓这个决策规则可以取得最小的错误率。所谓x属于属于第一类的概率不小于它属于第二类的概率、就是第一类的概率不小于它属于第二类的概率、就是下面的不等式成立：下面的不等式成立：*1112,1,q pqpxx模式识别（判别分析）问题这一决策规则可以表示成下面的等价形式：这一决策规则可以表示成下面的等价形式：称作判别函数称作判别函数(判别规则判别规则)，它把第一类的样本赋，它把第一类的样本赋值为值为1，而把第二类样本赋值为，而把第二类样本赋值为-1；为了得到这一判别函数，必须估计两个概
12、率密度：为了得到这一判别函数，必须估计两个概率密度：p1(x,*)和和 p2(x,*)；在传统的体系中，人们用最大似然法来估计这两在传统的体系中，人们用最大似然法来估计这两个密度中的参数个密度中的参数*和和*。*1121sgn ln,ln,ln1qf xppqxx回归估计模型回归估计模型 在传统体系中，回归估计是建立在另在传统体系中，回归估计是建立在另外一个模型基础上的。这个模型就是外一个模型基础上的。这个模型就是所谓的度量含有加性噪声的函数的模所谓的度量含有加性噪声的函数的模型。型。设某个未知函数有下而的参数化形式：设某个未知函数有下而的参数化形式：0,ffxx回归估计模型回归估计模型泛函正
13、态分布最小二乘泛函 1ln,liiiLp yfx 221exp22p0,iiiyfx 21,liiiMyfx解决学习问题的传统模式最大似然法的局限传统体系中的主要方法失效情况：如高斯混合分布例子推导 22211,expexp22222 2xxp x 密度估计的非参数方法Parzen核函数密度函数估计渐近理论对于从一个非常宽的密度类中估计密度函数，Parzen估计是一致的（对于平滑的密度函数，Parzen估计器的渐近收敛速度是最优结论如果观测数量足够多，用非参数方法替代参数方法可以得到对待求依赖关系的好的逼近1,niinKKRxxx xx 11,liipKlxx x密度估计的非参数方法给定的函数
14、集p(t)中，求解积分方程经验分布函数经验分布函数Fl(x)到待求函数F(x)的一致收敛特性()xp t dtF x 11lliiF xlxx sup|0PllxF xF x 密度估计的非参数方法密度估计问题的一般性描述 在概率分布函数未知，但是已知一组独立同分布数据的情况下，求解积分方程利用已知的数据来构造经验分布函数Fl(x)两个结论一般来说，估计一个密度是一个很难的不适定的计算问题为了较好地解决这个问题，必须采用正则化技术已经证明已有的非参数算法可以通过用标准的正则化技术（使用不同类型的正则化因子），并用经验分布函数代替未知分布函数来得到推导用有限数量信息解决问题的基本原则基本原则在解决
15、一个给定问题时，要设法避免把解决一个更为一般的问题作为其中间步骤对于依赖关系估计问题解决模式识别或者回归估计问题时，必须设法直接来寻找待求的函数，而不是首先估计密度函数，然后用估计的密度来构造待求的函数密度估计是统计学中的一个全能的问题密度估计一般来说是一个不适定问题，需要大量的观测才能较好地解决用有限数量信息解决问题的基本原则例子要构造一个把两个向量集合分开的决策规则，两个集合分别遵循两个正态分布：N(1,1)和N(2,2)1111122211sgn22TTf xxxxxC1121lnln1qCq 1111211122111sgnln221TTTqfxxq推导基于经验数据的风险最小化模型模式
16、识别问题：利用样本从容许函数的集合中寻找使得错误率最小的函数回归估计问题：在L2(F)度量下，利用样本在容许函数集合中寻找与回归函数最近的函数,(,)RL y fdFyxx 2200,(,)RffdFyfdFyxxxxx 2*0,RffdFxxx基于经验数据的风险最小化模型密度估计问题：用给定的样本在容许的密度函数集合中，寻找离待求密度的Kullback-Leibler距离最近的函数推导 0ln(,)()()ln(,)Rp tdF tp tp tdt *00(,)ln()()p tRp t dtp t 随机逼近推理随机逼近原则独立同分布数据最小化泛函迭代公式能保证学习过程一致性的两种一般性归纳
17、原则随机逼近的原则经验风险最小化的原则一般性学习理论对随机逼近归纳推理的一般性渐近学习理论对经验风险最小化归纳推理的一般性非渐近模式识别理论 ,RQ zdF z 1,kkkkgrad Q zk随机逼近推理什么时候必须停止训练过程？可能的回答当对训练数据中的所有元素，其梯度值都非常小，则停止训练过程当学习过程没有饱和，但是达到了某种停止准则时，则停止学习过程随机逼近原则的解释经验风险最小化方法的归纳特性正则化方法的归纳特性随机逼近推理Bayes推理先验信息：分布函数目标函数必须包括在假设函数集中分析学习过程的核心问题对经验风险最小化原则的探索推导机器学习的基本问题 问题的表示 机器学习的目的是根
18、据给定的训练样本求对某系统输入输出之间依赖关系的估计,使它能够对未知输出作出尽可能准确的预测.可以一般地表示为:变量y 与x 存在一定的未知依赖关系,即遵循某一未知的联合概率F(x,y),(x 和y 之间的确定性关系可以看作是其特例)。机器学习问题就是根据n 个独立同分布观测样本(x 1,y 1),(x 2,y 2),.,(x n,y n),在一组函数f(x,w)中求一个最优的函数f(x,w 0)对依赖关系进行估计,使期望风险R(w)=L(y,f(x,w)dF(x,y)(2)最小.其中,f(x,w)称作预测函数集,w 为函数的广义参数,f(x,w)可以表示任何函数集;L(y,f(x,w)为由于用f(x,w)对y 进行预测而造成的损失,不同类型的学习问题有不同形式的损失函数.预测函数也称作学习函数、学习模型或学习机器.
