第3章PAC模型
引言
PAC(probablyapproximatecorect)模型是由Valiant于1984年首先提出来的,是由统
计模式识别、决策理论提出了一些简单的概念并结合了计算复杂理论的方法而提出的学习
模型。它是研究学习及泛化问题的一个概率框架,不仅可用于神经网络分类问题,而且可广
泛用于人工智能中的学习问题。PAC模型的作用相当于提供了一套严格的形式化语言来
陈述以及刻画所提及的可学习以及样本复杂度问题。在PAC框架下,学习器必须从某一特
定类可能的函数中选择一个泛化函数(称为假设)。我们的目标是,以很高的概率,使所选择
的函数具有低泛化误差。PAC框架的一项重要创新是机器学习计算复杂性理论概念的引
入,学习器预期找到更有效的函数。本章将主要介绍基本PAC模型,并进一步讨论在有限
空间和无限空间下样本复杂度问题。本章中的讨论将限制在学习布尔值概念,且训练数据
是无噪声的,许多结论可扩展到更一般的情形。
3.基本的PAC模型
1
3.1
PAC简介
1.
PAC主要研究的内容包括:一个问题什么时候是可被学习的、样本复杂度、计算复杂
度,以及针对具体可学习问题的学习算法。虽然也可以扩展用于描述回归以及多分类等问
题,不过最初PAC模型是针对二分类问题提出的,和以前的设定类似,有一个输入空间
X
,
也称作实例空间。
X
上的一个概念
c
是
X
的一个子集,或者简单来说,1}的
函数。这里也采用这种模型,先介绍一下这种情况下的一些特有的概念
c
。
是从
X
到{0,
3.2
基本概念
1.
实例空间是指学习器能见到的所有实例,每个x∈
X
为一个实例,
X
=Un
≥1,Xn
为实
例空间。概念空间是指目标概念可以从中选取的所有概念的集合,学习器的目标就是要产
生目标概念的一个假设h,使其能准确地分类每个实例,对每个n≥1,定义每个Cn
.2xn
为
Xn
上的一系列概念,C=Un
≥1,Cn
为
X
上的概念空间,也称为概念类。假设空间是指算法
所能输出的所有假设
h
的集合,用
H
表示。对每个目标概念c∈Cn
,x)为
和实例x∈Xn
c(
实例x 上的分类值,即c(x)=1当且仅当x∈C。Cn 的任一假设h 指的是一个规则,即对给
出的x∈Xn ,算法在多项式时间内为c(x)输出一个预测值。变型空间是指能正确分类训练
样例D 的所有假设的集合,VS={h∈H|.<x,c(X )>∈D (h(X )=c(X ))}。变型空间
的重要意义是每个一致学习器都输出一个属于变型空间的假设。样本复杂度(sample
complexity)是指学习器收敛到成功假设时至少所需的训练样本数。计算复杂度
(computationalcomplexity)是指学习器收敛到成功假设时所需的计算量。出错界限是指在
成功收敛到一个假设前,学习器对训练样本的错误分类的次数。在某一特定的假设空间中,
对于给定的样本,若能找到一个假设h,使得对该概念类的任何概念都一致,且该算法的样
本复杂度仍为多项式,则该算法为一致算法。
3.1.3 问题框架
实例空间为X = {0,1}n ,概念空间和假设空间均为{0,1}n 的子集,对任意给定的准确
度ε(0<ε<1/2)及任意给定的置信度δ(0<δ<1),实例空间上的所有分布D 及目标空间中
的所有目标函数t,若学习器L 只需多项式P(n,1/ε,1/δ)个样本及在多项式P (n,1/ε,1/δ)
时间内,最终将以至少1-δ 的概率输出一个假设h∈H ,使得随机样本被错分类的概率
errorD (h,t)=Pr[{x∈X :h(x)≠t(x)}]≤ε,则称学习器L 是PAC可学习的,它是考虑样
本复杂度及计算复杂度的一个基本框架,成功的学习被定义为形式化的概率理论。
假设h 是另一个X 上的二值函数,我们试图用h 逼近c,选择X 上的一个概率分布μ,
则根据关于误差(风险)的定义,有ε(h)=μ(h(X )≠c(X )),而这个量可以很容易并且很直
观地用集合的对称差表示,如图3-1所示,误差很直观地用两个集合的对称差(阴影部分)的
面积表示。
图3-1 误差风险示意图(见彩图)
X 上的一个概念类C 就是一堆这样的概念的集合。这里的C 对应之前设定中的函数
空间F。类似地,学习问题实际上就是给定一个目标概念c∈C,寻找一个逼近h∈C 的问
题。PAC 模型与分布是无关的,因为对学习器来说,实例上的分布是未知的。该定义不要
求学习器输出零错误率的假设,只要求其错误率限定在某常数ε 的范围内(ε 可以任意小);
同时也不要求学习器对所有的随机抽取样本序列都能成功,只要其失败的概率限定在某个
常数δ 的范围内(δ 也可取任意小)即可,这样将学习到一个可能近似正确的假设。
32
第
3
章PAC
模型
2
PAC模型样本复杂度分析
3.
2.有限空间样本复杂度
3.且能用合理的样本数产生对目
1节的定义要求学习算法的运行时间在多项式时间内,
标概念的较好逼近。该模型是最坏情况模型,因为它要求在实例空间上对所有的目标概念
及所有的分布D、它所需的样本数都以某一多项式为界。
PAC可学习性很大程度上由所需的训练样例数确定。当假设空间增大时,找到一个一
致的假设将更容易,但需更多的样本来保证该假设有较高的概率是准确的。因此,在计算复
杂度和样本复杂度之间存在一个折中。下面将以布尔文字的合取是PAC学习的为例,说明
如何分析一个概念类是PAC学习的,并得到一致算法的样本复杂度的下界。
设学习器L,其假设空间与概念空间相同,即
H
=C,因假设空间为
n
个布尔文字的合
取,而每个文字有3种可能:该变量作为文字包含在假设中;该变量的否定作为文字包含在
假设中;假设中不包含该变量。所以,假设空间的大小为
=3n
,可设计如下算法。
H
(1)初始化假设
h
为2n
个文字的合取,即h=x1x1x2x2…xnxn
。
1-
/2
。
(l1/若xi=则从
h
中
(2)由样本发生器产生m=nn3+lnδ)个样本,对每个正例, 0,
删去xi;若xi=1,则从
h
中删去xi
(3)输出保留下来的假设h。
为分析该算法,需考虑3点:需要的样本数是否为多项式的;算法运行的时间是否为多
项式的,即这两者是否均为
p
(n,1/ε,1/δ);输出的假设是否满足PAC模型的标准,即
Pr[erh)≤ε]≥(-Pr[] 由于样本数已知,
roD
(1δ),表示概率。针对本算法, 显然它是多项
式的;因运行每个样本的时间为一常量,而样本数又是多项式的,则算法的运行时间也是多
项式的;因此只看它是否满足PAC模型的标准即可。若hroD
(')>ε, -a
'满足erh则称为εbd
假设,否则称为ε-exhausted假设。若最终输出的假设不是ε-bad假设,则该假设必满足
PAC模型的标准。
根据排除法计算学习一个假设所需要的样本个数,这里ε-bad假设混在ε-exhausted假
设之中,我们试图排除这些假设来计算样本个数。根据εbd假设的定义,[-a
-a有:Pr
εbd假
设与一个样本一致]≤(ε),因每个样本独立抽取,所以Pr[d假设与
m
个样本一致]≤
1-ε-ba(ε)
m
。又因最大的假设数为
,所以Pr
[存在ε-bad假设与
m
个样本一致]≤
|H|(1-ε)
m
。又因要求Pr[-bad假设]≤δ,
1
H
h
是ε所以有
m
|H|(1-ε)≤
δ
(3-1)
解得
m
≥ln|H|+ln1/
δ
(3-2)-ln(1-ε)
根据泰勒展开式:ex
=1+x+x22+…>1+x,将x=-
ε
代入泰勒展开式中,得ε<
-ln(1-ε)。将其代入式(3-1)中,得
33
m >1ε
ln|H |+ln1δ
.
è .
.
. ÷
(3-3)
式(3-3)提供了训练样例数目的一般理论边界,该数目的样例足以在所期望的值δ 和ε
程度下,使任何一致学习器成功地学习到H 中的任意目标概念。其物理含义表示:训练样
例数目m 足以保证任意一致假设是可能(可能性为1-δ)近似(错误率为ε)正确的,m 随着
1/ε 的增大呈线性增长,随着1/δ 和假设空间规模的增大呈对数增长。
针对本例有|H|=3n ,将它代入式(3-2)中得到,当样本数m >1ε
nln3+ln1δ
.
è .
.
. ÷
时,有
Pr[errorD (h)>ε]≤δ 成立。同时也证明了布尔文字的合取是PAC 学习的(算法见本节开
始部分),但也存在不是PAC学习的概念类,如k-term-CNF 或k-term-DNF。由于式(3-2)
以H 刻画样本复杂度,它存在以下不足:可能导致非常弱的边界;对于无限假设空间的情
形,式(3-2)根本无法使用,因此有必要引入另一度量标准———VC维。
3.2.2 无限空间样本复杂度
使用VC维(vapnik-chervonenkisdimension)代替H 也可以得到样本复杂度的边界,
基于VC维的样本复杂度比H 更紧凑,另外还可以刻画无限假设空间的样本复杂度。VC
维的概念是为了研究学习过程一致收敛的速度和推广性,是由统计学习理论定义的有关函
数集学习性能的一个重要指标。传统的定义是:对一个指标函数集,如果存在H 个样本能
够被函数集中的函数按所有可能的2K 种形式分开,则称函数集能够把H 个样本打散;函数
集的VC维就是它能打散的最大样本数目H 。若对任意数目的样本,都有函数能将它们打
散,则函数集的VC维是无穷大,有界实函数的VC维可以通过用一定的阈值将它转化成指
示函数来定义。
VC维反映了函数集的学习能力,VC维越大,学习机器越复杂(分类能力越大),所以
VC维又是学习机器复杂程度的一种衡量。换个角度理解,如果用函数类{f(z,a)}代表一
个学习机器,a 确定后就确定了一个判别函数,而VC维为该学习机器能学习的可以由其分
类函数正确给出的所有可能二值标识的最大训练样本数。遗憾的是,目前尚没有通用的关
于任意函数集VC维计算的理论,只知道一些特殊函数集的VC维。例如,在n 维空间中线
性分类器和线性实函数的VC维是n+1。下面举一个简单的实例进一步理解VC维。
实例集合X 为二维实平面上的点(x,y),假设空间H 为所有线性决策线。由图3-2可
以看出:除3个点在同一直线上的特殊情况,x 中3个点构成的子集的任意划分均可被线性
决策线打散,而x 中4个点构成的子集,无法被H 中的任一h 打散,所以VC(H )=3。
VC维衡量假设空间复杂度的方法不是用不同假设的数量H ,而是用X 中能被H 彻
底区分的不同实例的数量,这称为打散,可以简单理解为分类。H 的这种打散实例集合的
能力是其表示这些实例上定义的目标概念的能力的度量,如果X 的任意有限大的子集可被
H 打散,则VC(H )=∞,对于任意有限的H ,VC(H )≤log2|H|。使用VC维作为H 复杂
度的度量,就有可能推导出该问题的另一种解答,类似于式(3-2)的边界,即
m ≥1ε
4log2 2δ
+8VC(H )log213 ε
.
è .
.
. ÷
(3-4)
34
第3 章 PAC 模型
图3-2 线性分类器三维示意图
由式(3-4)可以看到:要成功进行PAC学习,所需要的训练样本数应正比于1δ
的对数,
正比于VC(H ),正比于1/ε 的对数。
3.3 VC维计算
设X ={x1,x2,…,xm }是一个大小为m 的采样集。每个假设h 在H 中标记一个样本
在X 中,结果表示为
h|X ={h(x1),h(x2),…,h(xm )} (3-5)
随着m 的增大,所有的假设h 对X 集合中的样本所能赋予的标记可能数也增大。当
m ∈N ,增长函数定义为
ΠH (m )=maxx1,x2,…,xm .X h(x1),h(x2),…,h(xm )|{ h ∈H } (3-6)
增长函数ΠH (m )表示可以用假设空间H 为m 例子标记的可能结果的最大数目。H
可以为这些示例标记的可能结果越多,H 的表达能力就越强。
将样本集的数量翻倍X = {x1,x2,…,xm ,xm +1,…,x2m },并生成子集X1 = {x1,
x2,…,xm }和X2={xm +1,xm +2,…,x2m },通常需要对原数据集进行复制操作,X1、X2 样本
集合类别定义见式(3-10)下方描述。X 的风险函数定义为
v(X )= 1
2m Σ2m
i=0
yi -f(xi) (3-7)
根据之前的研究,风险v(X1)和v(X2)之间的差异与样本集大小m 正相关。两者的风
险差异上界可以表示为
p =sup{v(X1)-v(X2)} ∝m (3-8)
进一步变化可得
1 mΣm
i=1
yi -f(xi)-1m
Σ2m
i=m+1
yi -f(xi)
= 1-1 mΣm
i=1
y~
i -f(xi) .
è .
.
. ÷
-1m
Σ2m
i=m+1
yi -f(xi) (3-9)
即
p =inf 1 mΣm
i=1
y~
i -f(xi)+1m
Σ2m
i=m+1
yi -f(xi) .
è .
.
. ÷
{ } (3-10)
其中,y~
i 是数据集的错误标签,实现层面需要将子集X1 的标签替换为错误标签,inf表示下
35
限。当样本集大小
m
相同时,VC 维与
p
成正比。
p
的结果将被标准化,存在ζ,0,∞),
这样VC 维的形式如式(3-11)所示
VC∝ ζε∈(
(3-11)
ε2p
m
e-8
p
是VC 维的度量,可用来对不同模型的VC 维进行排序。由于深度学习模型的巨大复
杂性,式(3-9)中的最小值不容易估计。只能通过局部最优估计p,这依赖深度学习优化器
实现。此外,找到被打散样品的最大数量仍然是一个开放的问题,只能通过VC 维的方法得
到一个近似的DNN 泛化性指标。该部分内容较难,更多细节参见文献[3]。
3.总结
4
PAC 学习是计算学习理论的基础,通过对PAC 学习模型的分析,可帮助读者理解VC
维的概念及训练数据对学习的有效性。当学习算法允许查询时是很有用的,并能提高其学
习能力。此外,在实际的机器学习中,PAC 模型也存在不足之处:模型中强调最坏情况,它
用最坏情况模型测量学习算法的计算复杂度及对概念空间中的每个目标概念和实例空间上
的每个分布,用最坏情况下所需要的随机样本数作为其样本复杂度的定义,使得它在实际中
不可用;定义中的目标概念和无噪声的训练数据在实际中是不现实的。
课后习题
1. 简述可PAC 学习的学习器需要满足什么条件。
2.VC 维理论是什么? 为什么要提出VC 维理论?
36