模式识别12_统计学习

1、2007-6-261统计学习理论2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2概要机器学习的基本问题和方法统计学习理论VC维和风险的界结构风险最小化)v)v2007-6-263机器学习的基本问题和方法 机器学习问题的表示机器学习问题的基本模型：预测输出yy输入x输出y系统（S）F ( x, y)学习机器（LM）f ( x , ), 2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential4组成 。学习问题就是

2、：从给定的函数集 f ( x , ) , 中选择出能够最好地逼近系统响应的函数。这种选择是基于训练集的。训练集由根据联合F ( x , y )1)nn（i.i.d.）观测 ( x 1 , y, ( x, y), L输入x输出y预测输出yy系统（S）F(x, y)学习机器（LM）f ( x, ), L ( y , f ( x , ) = PageWriting Solid Code Module 12007-6-26 Microsoft Confidential何谓最好 风险最小化准则损失函数：风险函数：L( y, f ( x, )R( ) = L( y, f ( x, )dF ( x, y)三

3、种主要学习问题的损失函数：y = f ( x , )y f ( x , ) 0 1L ( y , f ( x , ) = ( y f ( x , ) 2L ( p ( x , ) = lo g ( p ( x , )5模式识别问题函数拟合问题密度估计问题2007-6-266学习的目标就是：在联合概率分布函数 F(x,y) 未知，所有可用的信息都包含在训练数据集中的情况下，寻找函数使它（在函数类f ( x , ) , ）最小化风险泛函f ( x , 0 )R ( )2007-6-26。 log( p ( x , )7函数拟合问题： 最小二乘模式识别：使训练集样本错误率最低的分类器机器学习的基本问

4、题和方法经验风险最小化(ERM)R em p1NL ( y , f ( x , )Ni = 1( ) =1NNi = 1R e m p ( ) =( y f ( x i , ) 2i1NNi =1概率密度估计： 最大似然方法 Rem p ( ) =2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential82007-6-26经验风险最小化方法的问题有限样本下：经验风险最小是否是期望风险最小？以经验风险最小得到的解，其期望风险如何？如果存在多个使经验风险最小的解的情况(比如线性可分的情况)，那一个使期望风险最小

5、？2007-6-269机器学习的基本问题和方法 复杂性与推广能力例1：函数拟合 f(x , ) = sin(x)经验风险最小并不意味着期望风险最小。2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential10例2：模式识别以经验风险最小得到的解，其期望风险可能很大PageWriting Solid Code Module 12007-6-26 Microsoft Confidential过拟合，过学习（overfitting）2007-6-262007-6-261112过拟合，过学习（overfitting

6、）过拟合，过学习（overfitting）13142007-6-26例3: 线性可分问题经验风险都为0，那一个使期望风险最小？2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential统计学习理论VC维和风险的界 VC维描述学习机器的复杂性线性函数正弦函数的VC维R ( )Remp ( ) + ?15162007-6-26推广性的界的定理：R ( ) R e m p ( ) + ( n / h )其中n为样本数，h为学习机器VC维，(n / h)称为置信范围或VC信任。(n / h)是随n / h增大而减小的

7、函数。由上式可知：n / h越小，(n / h)越大，用经验风险近似期望风险就有较大的误差，用经验风险最小化取得的最优解可能具有较差的推广性。而n / h较大，则期望风险最小化得到的最优解就接近实际的最优解。2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential17R ( ) R em p ( ) + ( n / h ) ( n / h )是 随 n / h 增 大 而 减 小 的 函 数对于特定的问题，样本数目n一般是固定的，VC维h越大，真实风险与期望风险间的差就越大。因此我们在设计分类器时，不但要使

8、经验风险最小化，还要使机器的复杂性也即VC维尽量小，从而使期望风险最小。2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential182007-6-26VC维与推广性的界的讨论：函数集的VC维不一定等于自由参数的个数。尚无一般方法对任意函数集计算VC维。推广性的界是对最坏情况下的结论，所给出的界往往是松的。近邻法的讨论：近邻法的VC维无穷大，但推广性较好。VC维的条件:各子集的VC维有限损失函数的条件:有界非负满足或者对一定的参数对满足：结构风险最小化设计学习机器的目标：同时最小化经验风险和置信范围。如何同时

9、最小化结构风险最小化原则把函数集S分解为一个函数子集序列（子集结构） S1 S2 Sk S,使得各子集能够按照VC维的大小排列h1 h2 hk ，这样同一个子集中的置信范围就相同。容许子集结构的条件：1920(n / h)2007-6-26结构风险最小化原则（SRM）2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential两种构造性方法：21222007-6-26理论如何应用到SVMSVM的直观形式2007-6-26PageWriting Solid Code Module 12007-6-26 Micro

10、soft Confidential没有免费的午餐在很多的算法中，哪一个是最好的？两个分类器A和B在训练集上有同样好的性能，我们更喜欢简单的分类器。为什么？23242007-6-26我们更喜欢比较平滑的分类器。为什么？2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential守恒定律物理学守恒定律：能量守恒，热力学第二定律模式识别领域是否存在类似的定理？2526举例2007-6-26训练集测试集两个分类器2007-6-26PageWriting Solid Code Module 12007-6-26 Micr

11、osoft Confidential没有免费的午餐2007-6-262007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2728图示说明没有免费的午餐不存在任何一种模式分类算法具有天然的优越性，甚至不比随机猜测更好。如果某种算法对某个特定的问题看上去比另一种算法更好，其原因仅仅是它更适合这一特定的模式分类任务。2007-6-262007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2930举例举例50 points

12、 from a Gaussian Distribution (3 times)Blue: original distributionRed: estimated distributionGreen: samples31322007-6-26举例500 points from a uniform DistributionBlue: original distributionRed: estimated distributionGreen: samples2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential

13、非参数估计33342007-6-26非参数估计2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential没有免费的午餐对于要解决的分类问题，什么是事物的本质？先验信息数据的分布训练样本的数量代价函数35362007-6-26特征与模式是否存在最好的特征表示？2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential2007-6-2637特征与模式4个人：正常，左眼瞎，右眼瞎，全瞎2007-6-26PageWriting Solid Code Module 12007-6-26 Microsoft Confidential38丑小鸭定理如果只使用有限的谓词集合来区分待研究的任意两个模式，那么任意这样两个模式所共享的谓词数目是一个与模式的选择无关的常数。此外，如果模式的相似