统计机器学习理论综述.docVIP

统计机器学习理论综述 目前机器学习的一个比较热门的方向是统计机器学习（另外一个可能是图模型，按照Jordan的说法是统计机器学习属于频率主义，而图模型属于贝叶斯主义），对于每一个做统计机器学习的研究者来说，他们大致可以分为两类：一类做统计学习理论相关工作，如泛化界、约简或一致性；一类做优化算法，如支持向量机、Boosting等。作为一个纯统计机器学习的学者来说，我想这两块内容都得了解。优化算法的门槛低点，可能比较容易上手，了解他们并不太难，比如支持向量机本质上是求解一个RKHS上的二次优化问题，Boosting是 函数空间上的梯度下降优化问题。统计学习理论的门槛高点，需要的基础数学知识多点，离计算机出生的人比较远，因而常常使人望而生畏。最近本人对统计学习理 论这块做了些整理，发现其实这块东西并非如想象的那么难，他们的本质无非是概率集中不等式在机器学习上的应用，下面以泛化界为例讲一下自己对那块内容的理解。Talagrand(1996)说过: A random variable that depends (in a smooth way) on the influence of many independent variables(But not too much on any of them) is essentially constant. 中文上的意思是，依赖于许多独立随机变量的随机变量本质上是个常量，举个例子，经验风险就是一个依赖于一个随机训练样本集合的随机变量，因而经验风险本质上应该是个常量。正因为如此，这个随机变量离开它均值的概率就以指数形势衰减，因此这就是泛化界中常见的如下论述：“以1-\sigma的概率，作如下论断”的由来。目前使用的各种泛化界分析工具本质上正是基于这个原理，下面介绍下目前主流的三种泛化界分析方法，VC维，R复杂度和稳定性分析为了叙述清楚，如一个游戏开始之前需要设置游戏规则一样，这里简单介绍一下机器学习问题设置。统计机器学习研究的问题一般是，给定一堆带标签的训练样本集 合，需要从训练集合中学习出一个预测器来，对新的样本进行预测，使得预测结果尽可能的接近它的真实标签。相应的，对统计机器学习理论分析，我们需要做如下一些假设：假设训练样本集合是从一个未知但固定的分布中独立同分布的抽取出来，学习的目标是根据这样一个样本集合，从一个事先给定的分类器集合中挑选出一个分类器，使得分类器的对从同一个分布中随机抽取的样本在给定的一个损失评价下 的风险最小。一个需要特别注意的是，在统计学习泛化界分析时，分类器的风险常常被认为是随机样本集上的一个随机变量，这样的随机风险集合(以分类器为索引)在统计上被叫做经验过程。VC维可能是影响最深也是最早提出来的泛化界分析方法，V是统计机器学习理论的垫基者Vapnic的名称的缩写，这从名称上就验证了VC维在统计机器学习理论的影响力。这块的分析得先从Hoeffding不等式说起，Hoeffding不等式本质说明一组独立随机变量的均值离开它的期望的可能性以指数形式衰减。因此，对于任一给定的分类器F（F与训练样本集合无关)F与每个随机样本结合形成了一个F作用在该随机变量上的新的随机变量(取值0，1，即分对与分错)，这个随机变量的期望刚好是F的期望风险，N个这样随机变量的均值刚好是F的经验风险，因此，我们获得了F在N个训练样本集合上的经验风险偏离F期望风险的可能性的概率描述，为叙述方便，以下简称经验风险偏离F期望风险为偏离情况。然而，这样的概率描述只能针对一个F，它所起作用的那部分训练样本集合上也直接与F相关，而我们的学习是从事先给定的函数空间中选择一个F，因此我们并不能保证Hoeffding不等式作用的那个F就是我们选择出来的F，即使假设我们没看到训练样本集合之前，我们已经知道选择哪个F，我们在推导该F与最优F（函数空间里期望风险最小的F）之间关系时，也需要一个不随样本集合变化的概率描述。因此，我们需要一个对函数空间中的所有F一致成立的偏离情况的可能性的概率描述，这就是泛化界里常说的uniform。当函数空间的势是个有限值时，这种情况比较容易处理，分别对每个F运用Hoeffinding不等式，所有的偏离可能性的和就是存在一个F，它的偏离情况超过一个给定值的概率的上界。反过来说，即是假设空间里的任何函数都以至少一定的概率，偏离情况小于一个给定值。当函数空间的势不是一个有限值时，上面的处理就遇到了问题，因为无穷个 偏离可能性的和是个无穷大的数，这样的上界就是个无意义的事。为了处理这种情况，我们的先驱者注意到了以下两个情况：1）假设空间的中所有函数偏离情况的上确界是所有函数偏离情况的上界；2）在任何有限的样本上（比如N），尽管函数空间的势是无穷的，但是它们作用在有限个样本的分类情况却是有限的（上