董妍++张翌旸

[摘 要]传统统计模式识别的方法都是在样本数目足够多的前提下进行研究的，只有在样本数趋向无穷大时其性能才有理论上的保证。而在多数实际应用中，样本数目通常是有限的，这时很多方法都难以取得理想的效果。统计学习理论是一种专门的小样本统计理论，为研究有限样本情况下的统计模式识别和更广泛的机器学习问题建立了一个较好的理论框架。

中图分类号：TG333.7 文献标识码：A 文章编号：1009-914X（2016）21-0016-01

1 统计模式识别问题简介

统计模式识别问题可以看作是一个更广义的问题的特例，就是基于数据的机器学习问题。基于数据的机器学习是现代智能技术中十分重要的一个方面，主要研究如何从一些观测数据出发得出目前尚不能通过原理分析得到的规律，利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预测。现实世界中存在大量我们尚无法准确认识但却可以进行观测的事物，因此这种机器学习在从现代科学、技术到社会、经济等各领域中都有着十分重要的应用。当我们把要研究的规律抽象成分类关系时，这种机器学习问题就是模式识别。

统计是我们面对数据而又缺乏理论模型时最基本的分析手段，传统统计学所研究的是渐进理论，即当样本数目趋向于无穷大时的极限特性，统计学中关于估计的一致性、无偏性和估计方差的界等，以及分类错误率诸多结论，都具有这种渐近特性。但实际应用中，这种前提条件却往往得不到满足，当问题处在高维空间时尤其如此，这实际上是包括模式识别和神经网络等在内的现有机器学习理论和方法中的一个根本问题。

V.Vapnik等人早在20世纪60年代就开始研究有限样本情况下的机器学习问题。由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较艰涩， 90年代以前并没有提出能够将其理论付诸实现的较好的方法。加之当时正处在其他学习方法飞速发展的时期，因此这些研究一直没有得到充分的重视。直到90年代中期，有限样本情况下的机器学习理论研究逐渐成熟起来，形成了一个较完善的理论体系——统计学习理论（Statistical Learning Theory，简称SLT）。同时，神经网络等较新兴的机器学习方法的研究则遇到一些重要的困难，比如如何确定网络结构的问题、过学习与欠学习问题、局部极小点问题等等。在这种情况下，试图从更本质上研究机器学习问题的统计学习理论逐步得到重视。

为了解决有限样本的机器学习问题，在过去二十多年里，发展了很多新的统计学方法，其中V.Vapnike等发展了专门研究小样本统计估计和预测的统计学习理论以及结构风险最小化原则（Structural Risk Minimization，SRM）。

统计学习理论就是研究小样本统计估计和预测的理论， 主要内容包括四个方面：

1） 经验风险最小化原则下统计学习一致性的条件；

2） 在这些条件下关于统计学习方法推广性的界的结论；

3） 在这些界的基础上建立的小样本归纳推理准则；

4） 实现新的准则的实际方法（算法）。

其中， 最有指导性的理论结果是推广性的界，与此相关的一个核心概念是VC维。

2 VC维

模式识别方法中VC（Vapnik Chervonenk Dimension）维的直观定义是：对一个指示函数集， 如果存在h 个样本能够被函数集中的函数按所有可能的2h种形式分开， 则称函数集能够把h 个样本打散；函数集的VC维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散， 则函数集的VC维是无穷大。有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。

VC维反映了函数集的学习能力，VC维越大则学习机器越复杂（容量越大）。 遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是n+1， 而上一节例子中的VC维则为无穷大。对于一些比较复杂的学习机器（如神经网络），其VC维除了与函数集（神经网结构）有关外， 还受学习算法等的影响，其确定更加困难。对于给定的学习函数集， 如何（用理论或实验的方法）计算其VC维是当前统计学习理论中有待研究的一个问题。

3 推广性的界

统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数（包括使经验风险最小的函数），经验风险和真实风险之间以至少1-η的概率满足如下关系：

上式右端第一项反映训练样本的拟合程度；第二项称为Vapnik Chervonenkis置信范围（又称VC置信范围），h是函数集的VC维。

式（1）表明，在有限训练样本下，学习机器的VC维越高（复杂性越高） 则置信范围越大， 导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。

4 结构风险最小化（SRM）原则

在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程，如果模型比较适合现有的的训练样本（相当于 n/h 值适当），则可以取得比较好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和经验，造成了如神经网络等方法对使用者“技巧”的过分依赖。

当 n/h 较大时，式（1）右边的第二部分就较小，真实风险就接近经验风险的取值。如果n/h 较小，那么一个小的经验风险值并不能保证小的真实风险值。在这种情况下，要最小化真实风险值，就必须对不等式（1）右边的两项同时最小化。但是需要注意，不等式（1）右边的第一项取决于函数集中的一个特定函数，而第二项取决于整个函数集的VC维。因此要对风险的界，即式（1）的右边的两项同时最小化，我们必须使VC维成为一个可以控制的变量。

统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照 VC 维的大小（亦即Φ的大小）排列，在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得真实风险的最小，如图1所示。

于是有两个思路：一是在每个子集中求最小经验风险， 然后选择使最小经验风险和置信范围之和最小的子集。这种方法比较费时， 当子集数目很大甚至是无穷时不可行。于是有第二种思路， 即设计函数集的某种结构使每个子集中都能取得最小的经验风险（如使训练误差为0），然后只需选择适当的子集使置信范围最小，这个子集中使经验风险最小的函数就是最优函数。支持向量机就是这种思想的具体实现。

作者简介

董妍（1974-），女，吉林省怀德市人，硕士研究生，讲师，毕业院校：长春理工大学，研究方向：电子技术。