机器学习---可能近似正确（PAC）、出错界限框架

1. 计算学习理论概述

从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力

这个理论要回答的问题是：

在什么样的条件下成功的学习是可能的？

在什么条件下某个特定的学习算法可保证成功运行？

这里考虑两种框架：

可能近似正确（PAC）：确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得

到，定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目。

出错界限框架：考查了一个学习器在确定正确假设前可能产生的训练错误数量。

机器学习理论的一些问题：

是否可能独立于学习算法确定学习问题中固有的难度？能否知道为保证成功的学习有多少训练样例

是必要的或充足的？如果学习器被允许向施教者提出查询，而不是观察训练集的随机样本，会对所

需样例数目有怎样的影响？能否刻画出学习器在学到目标函数前会有多少次出错？能否刻画出一类

学习问题中固有的计算复杂度？

对所有这些问题的一般回答还未知，但不完整的学习计算理论已经开始出现。本文阐述了该理论中

的一些关键结论，并提供了在特定问题下一些问题的答案。主要讨论在只给定目标函数的训练样例

和候选假设空间的条件下，对该未知目标函数的归纳学习问题。主要要解决的问题是：需要多少训

练样例才足以成功地学习到目标函数以及学习器在达到目标前会出多少次错。

如果明确了学习问题的如下属性，那么有可能给出前面问题的定量的上下界：学习器所考虑的假设

空间的大小和复杂度；目标概念须近似到怎样的精度；学习器输出成功的假设的可能性；训练样例

提供给学习器的方式。

本文不会着重于单独的学习算法，而是在较宽广的学习算法类别中考虑问题：样本复杂度：学习器

要收敛到成功假设，需要多少训练样例？计算复杂度：学习器要收敛到成功假设，需要多大的计算

量？出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？

为了解决这些问题需要许多特殊的条件设定，比如：“成功”的学习器的设定；学习器是否输出等于

目标概念的假设；只要求输出的假设与目标概念在多数时间内意见一致；学习器通常输出这样的假

设。学习器如何获得训练样例：由一个施教者给出；由学习器自己实验获得；按照某过程随机生成

本文会介绍可能近似正确（PAC）学习框架。在PAC框架下，分析几种学习算法的样本复杂度和计

算复杂度；介绍了假设空间复杂度的一个重要度量标准，称为VC维，并且将PAC分析扩展到假设

空间无限的情况；介绍出错界限模型，并提供了前面章节中几个学习算法出错数量的界限，最后介

绍了加权多数算法。

2. 可能近似正确学习模型（PAC）

 可能近似正确学习模型（PAC）：指定PAC学习模型适用的问题；在此模型下，学习不同类别的目

标函数需要多少训练样例和多大的计算量；本文的讨论将限制在学习布尔值概念，且训练数据是无

噪声的（许多结论可扩展到更一般的情形）。 

X表示所有实例的集合，C代表学习器要学习的目标概念集合，C中每个目标概念c，对应于X的某

个子集或一个等效的布尔函数c: X->{0,1}；假定实例按照某概率分布D从X中随机产生；学习器L在

学习目标概念时考虑可能假设的集合H。在观察了一系列关于目标概念c的训练样例后，L必须从H

中输出某假设h，它是对c的估计；我们通过h在从X中抽取的新实例上的性能来评估L是否成功。新

实例与训练数据具有相同的概率分布；我们要求L足够一般，以至可以从C中学到任何目标概念而

不管训练样例的分布如何，因此，我们会对C中所有可能的目标概念和所有可能的实例分布D进行

最差情况的分析。

2.1 假设的错误率

为了描述学习器输出的假设h对真实目标概念的逼近程度，首先要定义假设h对应于目标概念c和实

例分布D的真实错误率；h的真实错误率是应用h到将来按分布D抽取的实例时的期望的错误率；定

义：假设h的关于目标概念c和分布D的真实错误率为h误分类根据D随机抽取的实例的概率

。

真实错误率紧密地依赖于未知的概率分布D：如果D是一个均匀的概率分布，假设的错误率为h和c

不一致的空间在全部实例空间中的比例；如果D恰好把h和c不一致区间中的实例赋予了很高的概

率，相同的h和c将造成更高的错误率。

h关于c的错误率不能直接由学习器观察到，L只能观察到在训练样例上h的性能；训练错误率：指

代训练样例中被h误分类的样例所占的比例；问题：h的观察到的训练错误率对真实错误率产生不正

确估计的可能性多大？

2.2 PAC可学习性

我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算

量可靠地学习。对可学习性的表述：一种可能的选择：为了学习到使errorD(h)=0的假设h，所需的

训练样例数；这样的选择不可行：首先要求对X中每个可能的实例都提供训练样例；其次要求训练

样例无误导性；可能近似学习：首先只要求学习器输出错误率限定在某常数ε范围内的假设，其次

要求对所有的随机抽取样例序列的失败的概率限定在某常数δ范围内；只要求学习器可能学习到一

个近似正确的假设。

PAC可学习性的定义：考虑定义在长度为n的实例集合X上的一概念类别C，学习器L使用假设空间

H。当对所有c∈C，X上的分布D，ε和δ满足0<ε，δ<1/2，学习器L将以至少1-δ输出一假设h∈H，

使errorD(h)<=ε，这时称C是使用H的L可PAC学习的，所使用的时间为1/ε，1/δ，n以及size(c)的多

项式函数。上面定义要求学习器L满足两个条件：L必须以任意高的概率（1-δ）输出一个错误率任

意低（ε）的假设；学习过程必须是高效的，其时间最多以多项式方式增长。上面定义的说明：1/ε

和1/δ表示了对输出假设要求的强度，n和size(c)表示了实例空间X和概念类别C中固有的复杂度；n

为X中实例的长度，size(c)为概念c的编码长度。

在实践中，通常更关心所需的训练样例数，如果L对每个训练样例需要某最小处理时间，那么为了

使c是L可PAC学习的，L必须从多项式数量的训练样例中进行学习。实际上，为了显示某目标概念

类别C是可PAC学习的，一个典型的途径是证明C中每个目标概念可以从多项式数量的训练样例中

学习到，且处理每个样例的时间也是多项式级。PAC可学习性的一个隐含的条件：对C中每个目标

概念c，假设空间H都包含一个以任意小误差接近c的假设。

2.3 有限假设空间的样本复杂度

PAC可学习性很大程度上由所需的训练样例数确定；随着问题规模的增长所带来的所需训练样例的

增长称为该学习问题的样本复杂度；我们把样本复杂度的讨论限定于一致学习器（输出完美拟合训

练数据的学习器）；能够独立于特定算法，推导出任意一致学习器所需训练样例数的界限；变型空

间：能正确分类训练样例D的所有假设的集合。

变型空间的重要意义是：每个一致学习器都输出一个属于变型空间的假设。因此界定任意一个一致

学习器所需的样例数量，只需要界定为保证变型中没有不可接受假设所需的样例数量。定义：考虑

一假设空间H，目标概念c，实例分布D以及c的一组训练样例S。当VSH,D中每个假设h关于c和D错

误率小于ε时，变型空间被称为c和D是ε-详尽的。

ε-详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于ε。从学习器的角度看，所

能知道的只是这些假设能同等地拟合训练数据，它们都有零训练错误率。只有知道目标概念的观察

者才能确定变型空间是否为ε-详尽的。但是，即使不知道确切的目标概念或训练样例抽取的分布，

一种概率方法可在给定数目的训练样例之后界定变型空间为ε-详尽的。

变型空间的ε-详尽化定理：若假设空间H有限，且D为目标概念c的一系列m>=1个独立随机抽取的

样例，那么对于任意0=<ε<=1，变型空间VSH,D不是ε-详尽的概率小于或等于：

证明：令h1,...,hk为H中关于c的真实错误率大于ε的所有假设。当且仅当k个假设中至少有一个恰好

与所有m个独立随机抽取样例一致时，不能使变型空间ε-详尽化。任一假设真实错误率大于ε，且与

一个随机抽取样例一致的可能性最多为1-ε，因此，该假设与m个独立抽取样例一致的概率最多为

。由于已知有k个假设错误率大于ε，那么至少有一个与所有m个训练样例都不一致的概率最

多为，。

基于训练样例的数目m、允许的错误率ε和H的大小，给出了变型空间不是ε-详尽的概率的上界；即

它对于使用假设空间H的任意学习器界定了m个训练样例未能将所有“坏”的假设（错误率大于ε的假

设）剔除出去的概率；利用上面的结论来确定为了减少此“未剔除”概率到一希望程度δ所需的训练

样例数，由，解出m，得到：。

训练样例的数目m足以保证任意一致假设是可能（可能性为1-δ）近似（错误率为ε）正确的；m随

着1/ε线性增长，随着1/δ和假设空间的规模对数增长；上面的界限可能是过高的估计，主要来源

于|H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和。

2.4 不可知学习和不一致假设

如果学习器不假定目标概念可在H中表示，而只简单地寻找具有最小训练错误率的假设，这样的学

习器称为不可知学习器。基于的假定是学习器输出一零错误率假设，在更一般的情形下学习器考虑

到了有非零训练错误率的假设时，仍能找到一个简单的边界。令S代表学习器可观察到的特定训练

样例集合，errorS(h)表示h的训练错误率，即S中被h误分类的训练样例所占比例。令hbest表示H中

有最小训练错误率的假设，问题是：多少训练样例才足以保证其真实错误率errorD(hbest)不会多于

e+errorS(hbest)？（上一节问题是这个问题的特例）

引入一般的Hoeffding边界。Hoeffding边界刻画的是某事件的真实概率及其m个独立试验中观察到

的频率之间的差异。Hoeffding边界表明，当训练错误率errorS(h)在包含m个随机抽取样例的集合S

上测量时，则。上式给出了一个概率边界，说明任意选择的

假设训练错误率不能代表真实情况，为保证L寻找到的最佳的假设的错误率有以上的边界，我们必

须考虑这|H|个假设中任一个有较大错误率的概率

 将上式左边概率称为δ，问多少个训练样例m才足以使δ维持在一定值内，求解得到

。适用于当最佳假设可能有非零训练错误率时，学习器仍能选择到最

佳假设h∈H的情形。

2.5 布尔文字的合取是PAC可学习的

我们已经有了一个训练样例数目的边界，表示样本数目为多少时才足以可能近似学习到目标概念，

现在用它来确定某些特定概念类别的样本复杂度和PAC可学习性。考虑目标概念类C，它由布尔文

字的合取表示。布尔文字是任意的布尔变量，或它的否定。问题：C是可PAC学习的吗？若假设空

间H定义为n个布尔文字的合取，则假设空间|H|的大小为3n，得到关于n布尔文字合取学习问题的

样本复杂度。

布尔合取式的PAC可学习性：布尔文字合取的类C是用Find-S算法PAC可学习的。

证明：该概念类的样本复杂度是n、1/δ和1/ε的多项式级，而且独立于size(c)。为增量地处理每个

训练样例，Find-S算法要求的运算量根据n线性增长，并独立于1/δ、1/ε和size(c)。因此这一概念类

别是Find-S算法PAC可学习的。

2.6 其他概念类别的PAC可学习性

无偏学习器（无归纳偏置）：考虑一无偏概念类C，它包含与X相关的所有可教授概念，X中的实例

定义为n个布尔值特征，则有

无偏的目标概念类在PAC模型下有指数级的样本复杂度。

K项DNF和K-CNF概念：某概念类有多项式级的样本复杂度，但不能够在多项式时间内被学习到。

概念类C为k项析取范式（k项DNF）的形式；k项DNF：T1∪...∪Tk，其中每一个Ti为n个布尔属性

和它们的否定的合取。假定H=C，则|H|最多为3nk，得到

因此，k项DNF的样本复杂度为1/δ、1/ε、n和k的多项式级；但是计算复杂度不是多项式级，该问

题是NP完全问题（等效于其他已知的不能在多项式时间内解决的问题）；因此，虽然k项DNF有多

项式级的样本复杂度，它对于使用H=C的学习器没有多项式级的计算复杂度。

令人吃惊的是，虽然k项DNF不是PAC可学习的，但存在一个更大的概念类是PAC可学习的；这个

更大的概念类是K-CNF，它有每样例的多项式级时间复杂度，又有多项式级的样本复杂度；K-

CNF：任意长度的合取式T1∪...∪Tj，其中每个Ti为最多k个布尔变量的析取；容易证明K-CNF包

含了K项DNF，因此概念类k项DNF是使用H=K-CNF的一个有效算法可PAC学习的。

3. 无限假设空间的样本复杂度

用|H|刻画样本复杂度有两个缺点：可能导致非常弱的边界；对于无限假设空间的情形，无法应

用。本节考虑H的复杂度的另一种度量，称为H的Vapnik-Chervonenkis维度（简称VC维或

VC(H)）。使用VC维代替|H|也可以得到样本复杂度的边界，基于VC维的样本复杂度比|H|更紧凑，

另外还可以刻画无限假设空间的样本复杂度。

VC维衡量假设空间复杂度的方法不是用不同假设的数量|H|，而是用X中能被H彻底区分的不同实例

的数量。S是一个实例集，H中每个h导致S的一个划分，即h将S分割为两个子集{x∈S|h(x)=1}和{x

属于S|h(x)=0}。定义：一实例集S被假设空间H打散，当且仅当对S的每个划分，存在H中的某假设

与此划分一致。如果一实例集合没有被假设空间打散，那么必然存在某概念可被定义在实例集之

上，但不能由假设空间表示。H的这种打散实例集合的能力是其表示这些实例上定义的目标概念的

能力的度量。

3.1 Vapnik-Chervonenkis维度

打散一实例集合的能力与假设空间的归纳偏置紧密相关，无偏的假设空间能够打散所有实例组成的

集合X。直观上，被打散的X的子集越大，H的表示能力越强。定义：定义在实例空间X上的假设空

间H的Vapnik-Chervonenkis维，是可被H打散的X的最大有限子集的大小。如果X的任意有限大的

子集可被H打散，则VC(H)=∞。

对于任意有限的H，VC(H)<=log2|H|。

VC维举例：假定实例空间X为实数集合，而且H为实数轴上的区间的集合，问VC(H)是多少？

只要找到能被H打散的X的最大子集，首先包含2个实例的集合能够被H打散，其次包含3个实例的

集合不能被H打散，因此VC(H)=2。实例集合S对应x、y平面上的点，令H为此平面内所有线性决策

面的集合，问H的VC维是多少？能够找到3个点组成的集合，被H打散，但无法找到能够被H打散的

4个点组成的集合，因此VC(H)=3。更一般地，在r维空间中，线性决策面的VC维为r+1。

假定X上每个实例由恰好3个布尔文字的合取表示，而且假定H中每个假设由至多3个布尔文字描

述，问VC(H)是多少？

找到下面3个实例的集合：instance1: 100；instance2: 010；instance3: 001

这三个实例的集合可被H打散，可对如下任意所希望的划分建立一假设：如果该划分要排除

instancei，就将文字┐li加入到假设中。此讨论很容易扩展到特征数为n的情况，n个布尔文字合取

的VC维至少为n。实际就是n，但证明比较困难，需要说明n+1个实例的集合不可能被打散。

使用VC维作为H复杂度的度量，就有可能推导出该问题的另一种解答，类似于前面式子的边界，即

（Blumer el al. 1989）。

 样本复杂度的下界（Ehrenfeucht et al. 1989）：考虑任意概念类C，且VC(C)>=2，任意学习器

L，以及任意0<ε<1/8，0<δ<1/100。存在一个分布D以及C中一个目标概念，当L观察到的样例数目

小于下式时：

将以至少d的概率输出一假设h，使errorD(h)>ε。

若训练样例的数目太少，那么没有学习器能够以PAC模型学习到任意非平凡的C中每个目标概念。

3.2 神经网络的VC维

计算分层无环网络的VC维。这个VC维可用于界定训练样例的数量，该数达到多大才足以按照希望

的ε和δ值近似可能正确地学习一个前馈网络.考虑一个由单元组成的网络G，它形成一个分层有向

无环图。分层有向无环图的特点：节点可划分成层，即所有第l层出来的有向边进入到第l+1层节

点；没有有向环，即有向弧形成的回路。这样网络的VC维的界定可以基于其图的结构和构造该图

的基本单元的VC维。

定义一些术语：G表示神经网络；n是G的输入数目；G只有1个输出节点；G的每个内部单元Ni最

多有r个输入，并实现一布尔函数ci:Rr->{0,1}，形成函数类C。定义C的G-合成：网络G能实现的所

有函数的类，即网络G表示的假设空间，表示成CG。

分层有向无环网络的VC维（Kearns & Vazirani 1994）：令G为一分层有向无环图，有n个输入节

点和s>=2个内部节点，每个至少有r个输入，令C为VC维为d的Rr上的概念类，对应于可由每个内

部节点s描述的函数集合，令CG为C的G合成，对应于可由G表示的函数集合，则VC(CG)

<=2dslog(es)。

假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的r输入感知器VC维为r+1，得

到：

上面的结果不能直接应用于反向传播的网络，原因有两个：此结果应用于感知器网络，而不是

sigmoid单元网络；不能处理反向传播中的训练过程。

4. 学习的出错界限模型

计算学习理论考虑多种不同的问题框架：训练样例的生成方式（被动观察、主动提出查询）；数据

中的噪声（有噪声或无噪声）；成功学习的定义（必须学到正确的目标概念还是有一定的可能性和

近似性）；学习器所做得假定（实例的分布情况以及是否C⊆H）；评估学习器的度量标准（训练

样例数量、出错数量、计算时间）。

机器学习的出错界限模型：学习器的评估标准是它在收敛到正确假设前总的出错数；学习器每接受

到一个样例x，先预测目标值c(x)，然后施教者给出正确的目标值；考虑的问题是：在学习器学习

到目标概念前，它的预测会有多少次出错；下面讨论中，只考虑学习器确切学到目标概念前出错的

次数，确切学到的含义∀x h(x)=c(x)。

4.1 Find-S算法的出错界限

Find-S算法的一个简单实现：将h初始化为最特殊假设l1∪l1∪...∪ln∪ln。对每个正例x：从h中移

去任何不满足x的文字；输出假设h。计算一个边界，以描述Find-S在确切学到目标概念c前全部的

出错次数：Find-S永远不会将一反例错误地划分为正例，因此只需要计算将正例划分为反例的出错

次数；遇到第一个正例，初始假设中2n个项半数被删去，对后续的被当前假设误分类的正例，至少

有一项从假设中删去；出错总数至多为n+1。

4.2 Halving算法的出错界限

学习器对每个新实例x做出预测的方法是：从当前变型空间的所有假设中取多数票得来；将变型空

间学习和用多数票来进行后续预测结合起来的算法称为Halving算法；Halving算法只有在当前变型

空间的多数假设不能正确分类新样例时出错，此时变型空间至少可减少到它的一半大小，因此出错

界线是log2|H|；Halving算法有可能不出任何差错就确切学习到目标概念，因为即使多数票是正确

的，算法仍将移去那些不正确、少数票假设；Halving算法的一个扩展是允许假设以不同的权值进

行投票（如贝叶斯最优分类器和后面讨论的加权多数算法）。

4.3 最优出错界限

问题：对于任意概念类C，假定H=C，最优的出错边界是什么？

最优出错边界是指在所有可能的学习算法中，最坏情况下出错边界中最小的那一个；对任意学习算

法A和任意目标概念c，令MA(c)代表A为了确切学到c，在所有可能训练样例序列中出错的最大值；

对于任意非空概念类C，令MA(C)=max（c∈C）MA(c)。定义：C为任意非空概念类，C的最优出

错界限定义为Opt(C)是所有可能学习算法A中MA(C)的最小值。

非形式地说，Opt(C)是C中最难的那个目标概念使用最不利的训练样例序列用最好的算法时的出错

次数。Littlestone1987证明了。

4.4 加权多数算法

Halving算法的更一般形式称为加权多数算法。加权多数算法通过在一组预测算法中进行加权投票

来作出预测，并通过改变每个预测算法的权来学习。加权多数算法可以处理不一致的训练数据，因

为它不会消除与样例不一致的假设，只是降低其权。要计算加权多数算法的出错数量边界，可以用

预测算法组中最好的那个算法的出错数量。

加权多数算法一开始将每个预测算法赋予权值1，然后考虑训练样例，只要一个预测算法误分类新

训练样例，它的权被乘以某个系数β，0<=β<1。如果β=0，则是Halving算法；如果β>0，则没有一

个预测算法会被完全去掉。如果一算法误分类一个样例，那么它的权值变小。

ai代表算法池A中第i个预测算法，wi代表与ai相关联的权值。对所有i，初始化wi<-1，对每个训练样

例<x, c(x)>做：初始化q0和q1为0；对每个预测算法ai；如果ai(x)=0，那么q0<-q0+wi；如果

ai(x)=1，那么q1<-q1+wi。如果q1>q0，那么预测c(x)=1；如果q0>q1，那么预测c(x)=0；如果

q0=q1，那么对c(x)随机预测为0或1；对每个预测算法ai。如果ai(x)≠c(x)，那么wi<-βwi。

加权多数算法的相对误差界限：令D为任意的训练样例序列，令A为任意n个预测算法集合，令k为A

中任意算法对样例序列D的出错次数的最小值。那么使用β=1/2的加权多数算法在D上出错次数最多

为：2.4(k+log2n)

证明：可通过比较最佳预测算法的最终权和所有算法的权之和来证明。令aj表示A中一算法，并且

它出错的次数为最优的k次，则与aj关联的权wj将为(1/2)k。A中所有n个算法的权的和，

W的初始值为n，对加权多数算法的每次出错，W被减小为最多，其原因是加权投票占少数的

算法最少拥有整个权W的一半值，而这一部分将被乘以因子1/2。令M代表加权多数算法对训练序

列D的总出错次数，那么最终的总权W最多为n(3/4)M。由，得

意义：加权多数算法的出错数量不会大于算法池中最佳算法出错数量，加上一个随着算法池大小对

数增长的项，再乘以一常数因子。

可能近似正确模型（PAC）针对的算法从某概念类C中学习目标概念，使用按一个未知但固定的概

念分布中随机抽取的训练样例，它要求学习器可能学习到一近似正确的假设，而计算量和训练样例

数都只随着1/δ、1/ε、实例长度和目标概念长度的多项式级增长。在PAC学习模型的框架下，任何

使用有限假设空间H的一致学习器，将以1-δ的概率输出一个误差在ε内的假设，所需的训练样例数

m满足。

不可知学习考虑更一般的问题：学习器不假定目标概念所在的类别，学习器从训练数据中输出H中

有最小误差率的假设。学习保证以概率1-δ从H中最可能的假设中输出错误率小于ε的假设，需要的随机抽取的训练样例数目m满足。

学习器考虑的假设空间的复杂度对所需样例的数目影响很大，而衡量假设空间复杂度的一个有用的

度量是VC维。VC维是可被H打散的最大实例集的大小。

在PAC模型下以VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是：

另一种学习模式称为出错界限模式，用于分析学习器在确切学习到目标概念之前会产生的误分类次

数，Halving算法在学习到H中的任意目标概念前会有至多log2|H|次出错，对任意概念类C，最坏情

况下最佳算法将有Opt(C)次出错，满足VC(C)<=Opt(C)<=log2|C|。

加权多数算法结合了多个预测算法的加权投票来分类新的实例，它基于这些预测算法在样例序列中

的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数

来计算。