第10章 模式识别的理论与方法(第3讲)

传统的模式识别和机器学习方法都是在样本数目足够多的前提下进行研究的，所提出的各种

方法只有在样本数趋于无穷大时其性能才有理论上的保证。而在多数实际应用中，样本数目

通常是有限的，尤其图像样本更是如此，因为图像所需的存储和计算量都比较大，对它进行大数量级的取样是不可想象的。

统计学习理论是一种小样本统计理论，它为研究有限样本情况下的统计模式识别和更广泛的机器学习问题建立了一个较好的理论框架，同时也发展了一种新的模式识别方法——支持向量机，能够较好地解决小样本学习问题。

1．机器学习理论的基本问题

基于数据的机器学习是现代智能技术中十分重要的一个方面，主要研究如何从一些观测数据（样本）出发得到目前尚不能通过原理分析得到的规律，利用这些规律去分析客观对象，对未来数据或无法观测的数据进行预测。

机器学习问题的基本模型，可以用图10－34表示，其中，系统S是研究的对象，它在一定输

入x 下得到一定的输出y ，LM是所求的学习机，输出为y。机器学习的目的是根据给定

的已知训练样本求取对系统输入输出之间依赖关系的估计，使它能对未知输出作尽可能准确

的预测。

图10－34 机器学习的基本模型

机器学习问题可以形式化地表示为：

已知变量y 与输入x 之间存在一定的未知依赖关系，即存在一个未知的联合概率

F(x,y)，

机器学习就是根据n个独立同分布观测样本

(x1,y1),(x2,y2),(xn,yn)在一组函数fx,中, 求一个最优的函数fx,0。使预测的期望风险

R()Ly,f(x,)dF(x,y)(10－156)

最小。

其中，fx,称作预测函数集，

为函数的广义参数，故fx,可以表示任何函数集；

Ly,f(x,)为由于用

f(x,)对y 进行预测而造

成的损失。不同类型的机器学习问题有不同形式的损失函数。预测函数通常也称作学习函数、学习模

型或学习机器。

有三类基本的机器学习问题:

模式识别函数逼近

概率密度估计

对于模式识别问题，系统输出就是类别标号。在两类情况下，y0,1或

y1,1是二值

函数，这时预测函数称作指示函数，也称作判别函数。

模式识别问题中损失函数的基本定义可以是:

0Ly,f(x,ω)1如果如果yfx,ωyfx,ω要使式(10－156)定义的期望风险最小化，必须依赖关于联合概率

F(x,y)的信息，在模式

识别问题中就是必须已知类先验概率和类条件概率密度。但是，在实际的机器学习问题中，我们只能利用已知样本的信息，因此，期望风险无法计算和最小化。

在实际中，常用算术平均代替式中的数学期望，于是定义

1nRempLyi,f(xi,)ni1(10－158)

来逼近式中的期望风险，也称之为经验风险。

相应的，对参数求经验风险

Remp的最小

值就称之为经验风险最小化（ERM）原则。然而，从期望风险最小化到经验风险最小化并没有可靠的理论依据，所以必然存在着一些问题。

在以往的机器学习实践中，人们往往注重经验风险最小化的实现，但一味追求训练误差最小

并不总能达到好的预测效果。将学习机器对未来输出进行正确预测的能力称作推广性。某些

情况下，当训练误差过小反而会导致推广能力的下降。之所以出现这种现象，一是因为学习

样本不充分，二是学习机器设计不合理，这两个问题是相互关联的。

所以说，经验风险最小化并不一定意味着期望风险最小，学习机器的复杂性不但与所研究的系统有关，而且要和有限的学习样本相适应。

2．统计学习理论的核心内容

统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。它从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。

研究表明，当训练样本数目趋于无穷大时，经

验风险的最优值能够收敛到真实风险的最优值，这就是所谓的学习过程的一致性。只有满足一

致性条件，才能保证在经验风险最小化原则下得到的最优方法当样本无穷大时趋近于使期望

风险最小的最优结果。这种关系可用图10－35表示：

图10－35 经验风险和真实风险的关系示意图

对于有界损失函数，经验风险最小化学习一致的充要条件是经验风险在如下意义上一致地收

敛于真实风险：

LimP[sup(R()Remp()]0n0（10－159）

这里，P表示概率，Remp()和R()分别表示在n

个样本下的经验风险和对于同一

的真实

风险。这就是在统计学习理论中的重要定理——学习理论的关键定理。该定理把学习一致性问题转化为上式的一致收敛问题。它既依赖于预测函数集，也依赖于样本的概率分布。

3．VC维

VC维（Vapnik-Chervonenkis Dimension）是为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性收敛速度而定义的。

•一般来讲，VC维是一组函数的特性，这种特性是各类函数集都具有的。这里仅考虑两类的

模式识别问题。假如存在一个有h个样本的样本集能够被一个函数集中的函数按照所有可能

的形式分成两类，则称函数集能够把样本数为h的样本集打散（shattering）。

函数集的VC维就是用这个函数集所能打散的最大样本集的样本数目。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在有h＋1个样本集能够被函数集打散，则函数集的VC维就是h。

如果对于任意样本数，总能找到一个样本集能够被这个函数集打散，则函数集的VC维就是

无穷大。研究表明，经验风险最小化学习过程一致的充分必要条件是函数集的VC维有限，

且这时的收敛速度是最快的。

实际上，经验风险最小化原则下学习机器的实际风险是由两部分组成，可以写作

RRemp(10－160)

其中,第一部分为训练样本的经验风险，另一

部分称作置信范围，也叫VC信任（VC confidence）。

4. 结构风险最小化

从前面的讨论中可以看出，传统的机器学习方法中普遍采用的经验风险最小化原则在样本数

目有限时是不合理的，因为经验风险和置信范围需要同时最小化。事实上，在传统方法中，

我们选择学习模型和算法的过程就是优化置信范围的过程。

所以，选择最小经验风险与置信范围之和最小的函数集，可以达到期望风险最小。

在实际实现中，我们可以把函数集分成一个函数子集序列，使各个子集能按VC的大小排列（也就是按的大小排列），这样，在同一个子集中置信范围相同，在每一个子集中寻

找最小风险，选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险最小。

这个子集中使经验风险最小的函数就是要求的最优函数，这种思想称作结构风险最小化（Structural Risk Minimization），简称SRM原则。

在结构风险最小化原则下，一个分类器的设计过程包括以下两方面的任务：

1、选择一个适当的函数子集（使之对问题来说有最优的分类能力）；

2、从这个子集中选择一个判别函数（使经验风险最小）。

结构风险最小化原则为我们提供了一种不同于经验风险最小化的更科学的学习机器设计原则，而支持向量机则是这一原则的具体应用成果。

5．支持向量机

支持向量机（Support Vector Machines，简称SVM方法）是实现统计学习理论的一种具体方法，其主要内容在1992年－1995年间才基本完

成，目前仍处在不断发展阶段。

可以说，统计学习理论之所以从20世纪90年代以来受到越来越多的重视，很大程度上是因为提出了支持向量机这一通用学习方法。因为从某种意义上它可以表示成类似神经网络的形式，支持向量机起初也叫支持向量网络。

支持向量机是从线性可分情况下的最优分类面（Optimal Hyperplane）提出的。考虑图10-36

中所示的二维两类线性可分情况，图中的两类点分别表示两类训练样本，H是把两类没有错

误分开的分类线，

H1、H2分别为过各类样本中离分类线最近的点

且平行于分类线的直线，和之间的距离叫做两类的分类空隙或分类间隔（margin）。所谓最

优分类线就是要求分类线不但能将两类无错误地分开，而且要使两类的分类空隙最大。前者保证经验风险最小，而分类空隙最大实际上就是使置信范围最小，从而使真实风险最小。

设：线性可分样本为

xi,y，ii=1，…，n，xRdy1,1是类别标号。d维空间中线性判别函数

的一般形式为gxwxb，分类面方程为：

wxb0(10－161)

将判别函数归一化，使两类所有样本都满足，gx1这样，离分离面最近的样本的gx1这样分类间隔就等于2w等价于使ω（或）ω2，因此，间隔最大最小；

而要求分类线对所有样本正确分类，就是要求它满足

yiwxib10i=1，2，…，n

因此，满足上述条件且使

ω2(10－162)

最小的分类面就是最优分类面。

•过两类样本中离分类面最近的点且平行于最优分类面的超平面H1、H2上的训练样本就是式(10－162)中使等号成立的那些样本，它们叫做支持向量（Support Vectors）。

因为它们支撑了最优分类面，最优分类面的示意图如下图，图中用圆圈标出的点为支持向量。

图10－36 最优分类面示意图

最优分类面的问题可以表示成约束优化问题，即在条件(10－162)的约束下，求函数1ww221ww2(10－163)

的最小值。

为此，定义如下拉各朗日函数：

n1Lw,b,wwiyi(wxi)b12i1(10－164)

其中，i0为拉各朗日系数，对

w和b 求拉各朗日函数的极小值。

把式(10－164)分别对

w和b 求偏微分并令它

们等于0，就可以把原问题转化为如下这种较简单的对偶问题：在约束条件

yii0i1ni0i=1，…，n

(10－165)

之下对

ni求解下列函数的最大值：

(10－166)

1nQiijyiyjxixj2i,j1i1若

wi为最优解，则

i1niyixi(10－167)

即最优分类面的权系数向量是训练样本向量的线性组合。

这是一个不等式约束下的二次函数极值问题，存在唯一解。且根据Kühn-Tucker条件，这个

优化问题的解须满足

iyi(wxib)-10(10－168)

因此，对多数样本将为零，取值不为零的

i对应于使式(10－162)等号成立的样本，即

支持向量，它们通常只是全体样本中的很少一部分。

i求解上述问题后得到的最优分类函数是

fxsgn(wx)bsgniyi(xix)bi1n(10－169)

由于非支持向量对应的i均为零，因此，

式中的求和实际上只对支持向量进行。而b是分类的阈值，可以由任意一个支持向量用式(10－162)求得，或通过两类中任意一对支持向量取中值求得。

上面讨论的最优分类面仅限于样本线性可分的情况，分类函数(10－169)中只包括待分样本与训练样本中的支持向量的内积运算xxi，同样，它的求解过程式(10－165)~(10－167)也只涉及训练样本之间的内积运算

xixj，

可见，要解决一个特征空间的最优线性分类问题，只要知道该空间的内积运算即可。

如果问题定义的空间不是线性可分的，则必须通过非线性变换来解决这些样本的分类问题。于是，定义非线性变换

d:RFd，将

原空间R映射到另一个高维空间F，将原空间的向量xx1,x2,,xd映射成新空间的向量

x1x,2x,,Nx使经过映射之后的样本在新的高维空间中变得线性可分，并在空间F中求最优分类面。经过映射之后，内积运算变成如下形式xxi。此时的优化函数(10－166)变为

1nQααiαiαjyiyjΦxiΦxj2i,j1i1n(10－170)

相应的判别函数(10－169)变为

nfxsgnαyΦ(x)Φ(x)biiii1(10－171)

非线性映射的理论基础是Cover关于样本可分性的理论，该理论指出，一个线性不可分多维样本空间可以映射到一个全新的线性可分的高维空间进行处理。

这种映射必须满足两个条件，首先，映射是非线性的；其次，特征空间的维数必须相当高。这种非线性变换可以解决实际操作中的高维空间计算问题，可以使某些高维映射的内积运算变得简单。非线性映射示意图在图10－37中示出。

图10－37 非线性映射示意图，线性不可分的样本空间（左）经过非线性映射后成为线性可分的新空间（右）

根据泛函理论中的Hilbert-Schmidt原理，只要一种核函数

Kx,y满足Mercer条件，

它就对应某一变换空间的内积，核函数的定义如下：

Kx,yxy(10－172)

这样的话，只要选择合适的核函数，然后用内积函数代替分类函数(10－171)中的内积，就构成了支持向量机，具体形式见式(10－173)。其建立过程不考虑非线性映射的具体形式，而只需进行核函数的计算（式（10－172））。

fxsgniyiKxixbi1n(10－173)

支持向量机求得的分类函数形式上类似于一个神经网络，其输出是若干中间层节点的线性组合，而每个中间层节点对应于输入样本与一个

支持向量的内积（非线性样本可用核函数代替）。由于最终的判别函数实际只包含支持向

量的内积和求和，因此，识别时的计算复杂度取决于支持向量的个数。

核函数有多种形式，这里列出常用的几种：1）多项式形式内积函数

Kx,yxy12）径向基内积函数

q(10－174)

Kx,yexy2/22(10－175)

3）Sigmoid 内积函数

Kx,ytanhxy(10－176)

统计学习理论和支持向量机的算法之所以从20世纪90年代以来受到很大的重视，在于它们对有限样本情况下模式识别中的一些根本性的问题进行了系统的理论研究，并且在此基础上建立了一种较好的通用学习算法。

以往很多困扰机器学习方法的问题，在这里都得到了一定程度的解决。而且，很多的传统的机器学习方法都可以看作是支持向量机的一种实现，因而统计学习理论和支持向量机被很多人看作研究机器学习问题的一个基本框架。

6．支持向量机的的应用

应用支持向量机进行纹理分类算法的主要步骤可以用如下（图10－38）流程图表示

纹理样本均来自Brotadz纹理库。其中，图10－39由Brotadz库中的D4和D84组成，图10－40由Brotadz库中的D5和D92组成，大小均为256×512像素。应用支持向量机方法对它们进行了分类实验。

图10－39 D4和D84组成的纹理图像

图10－40 D5和D92组成的纹理图像

图10－41 D12和D17组成的纹理图像

图10－42 自建的测试图像（1）

图10－43 自建的测试图像（2）