2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 7章 计算学习理论
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力
这个理论要回答的问题是：
– 在什么样的条件下成功的学习是可能的？
– 在什么条件下某个特定的学习算法可保证成功运行？
这里考虑两种框架：
– 可能近似正确（ PAC）
确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到
定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目
– 出错界限框架
考查了一个学习器在确定正确假设前可能产生的训练错误数量
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
机器学习理论的一些问题：
– 是否可能独立于学习算法确定学习问题中固有的难度？
– 能否知道为保证成功的学习有多少训练样例是必要的或充足的？
– 如果学习器被允许向施教者提出查询，而不是观察训练集的随机样本，会对所需样例数目有怎样的影响？
– 能否刻画出学习器在学到目标函数前会有多少次出错？
– 能否刻画出一类学习问题中固有的计算复杂度？
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介（ 2）
对所有这些问题的一般回答还未知，但不完整的学习计算理论已经开始出现
本章阐述了该理论中的一些关键结论，并提供了在特定问题下一些问题的答案
主要讨论在只给定目标函数的训练样例和候选假设空间的条件下，对该未知目标函数的归纳学习问题
主要要解决的问题是：需要多少训练样例才足以成功地学习到目标函数以及学习器在达到目标前会出多少次错
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
简介（ 3）
如果明确了学习问题的如下属性，那么有可能给出前面问题的定量的上下界
– 学习器所考虑的假设空间的大小和复杂度
– 目标概念须近似到怎样的精度
– 学习器输出成功的假设的可能性
– 训练样例提供给学习器的方式
本章不会着重于单独的学习算法，而是在较宽广的学习算法类别中考虑问题：
– 样本复杂度：学习器要收敛到成功假设，需要多少训练样例？
– 计算复杂度：学习器要收敛到成功假设，需要多大的计算量？
– 出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
简介（ 4）
为了解决这些问题需要许多特殊的条件设定，
比如
–,成功”的学习器的设定
学习器是否输出等于目标概念的假设
只要求输出的假设与目标概念在多数时间内意见一致
学习器通常输出这样的假设
– 学习器如何获得训练样例
由一个施教者给出
由学习器自己实验获得
按照某过程随机生成
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
简介（ 5）
7.2节介绍可能近似正确（ PAC）学习框架
7.3节在 PAC框架下，分析几种学习算法的样本复杂度和计算复杂度
7.4节介绍了假设空间复杂度的一个重要度量标准，称为 VC维，并且将 PAC分析扩展到假设空间无限的情况
7.5节介绍出错界限模型，并提供了前面章节中几个学习算法出错数量的界限，最后介绍了加权多数算法
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
可能学习近似正确假设
可能近似正确学习模型（ PAC）
– 指定 PAC学习模型适用的问题
– 在此模型下，学习不同类别的目标函数需要多少训练样例和多大的计算量
本章的讨论将限制在学习布尔值概念，
且训练数据是无噪声的（许多结论可扩展到更一般的情形）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
问题框架
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进行最差情况的分析
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
假设的错误率
为了描述学习器输出的假设 h对真实目标概念的逼近程度，首先要定义假设 h对应于目标概念 c和实例分布 D的真实错误率
h的真实错误率是应用 h到将来按分布 D抽取的实例时的期望的错误率
定义：假设 h的关于目标概念 c和分布 D的真实错误率为 h误分类根据 D随机抽取的实例的概率
)()(Pr)( xhxcherror DxD
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
假设的错误率（ 2）
图 7-1,h关于 c的错误率是随机选取的实例落入 h和 c不一致的区间的概率
真实错误率紧密地依赖于未知的概率分布 D
– 如果 D是一个均匀的概率分布，那么图 7-1中假设的错误率为 h和 c不一致的空间在全部实例空间中的比例
– 如果 D恰好把 h和 c不一致区间中的实例赋予了很高的概率，相同的 h
和 c将造成更高的错误率
h关于 c的错误率不能直接由学习器观察到,L只能观察到在训练样例上 h的性能
训练错误率：指代训练样例中被 h误分类的样例所占的比例
问题,h的观察到的训练错误率对真实错误率产生不正确估计的可能性多大？
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
PAC可学习性
我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算量可靠地学习
对可学习性的表述
– 一种可能的选择：为了学习到使 errorD(h)=0的假设 h，
所需的训练样例数
这样的选择不可行：首先要求对 X中每个可能的实例都提供训练样例；其次要求训练样例无误导性
– 可能近似学习：首先只要求学习器输出错误率限定在某常数?范围内的假设，其次要求对所有的随机抽取样例序列的失败的概率限定在某常数?范围内
只要求学习器可能学习到一个近似正确的假设
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
PAC可学习性（ 2）
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的编码长度
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
PAC可学习性（ 3）
在实践中，通常更关心所需的训练样例数，
– 如果 L对每个训练样例需要某最小处理时间，那么为了使 c是 L可 PAC学习的,L必须从多项式数量的训练样例中进行学习
– 实际上，为了显示某目标概念类别 C是可 PAC学习的，一个典型的途径是证明 C中每个目标概念可以从多项式数量的训练样例中学习到，且处理每个样例的时间也是多项式级
PAC可学习性的一个隐含的条件：对 C中每个目标概念 c，假设空间 H都包含一个以任意小误差接近 c的假设
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
有限假设空间的样本复杂度
PAC可学习性很大程度上由所需的训练样例数确定
随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度
我们把样本复杂度的讨论限定于一致学习器
（输出完美拟合训练数据的学习器）
能够独立于特定算法，推导出任意一致学习器所需训练样例数的界限
变型空间：能正确分类训练样例 D的所有假设的集合。 ) ) }()(()(,(|{,xcxhDxcxHhVS DH
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
有限假设空间的样本复杂度（ 2）
变型空间的重要意义是：每个一致学习器都输出一个属于变型空间的假设
因此界定任意一个一致学习器所需的样例数量，
只需要界定为保证变型中没有不可接受假设所需的样例数量
定义：考虑一假设空间 H，目标概念 c，实例分布 D以及 c的一组训练样例 S。当 VSH,D中每个假设 h关于 c和 D错误率小于?时，变型空间被称为
c和 D是?-详尽的。 )()(,herrorVSh DDH
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
有限假设空间的样本复杂度（ 3）
-详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于?
从学习器的角度看，所能知道的只是这些假设能同等地拟合训练数据，它们都有零训练错误率
只有知道目标概念的观察者才能确定变型空间是否为?-详尽的
但是，即使不知道确切的目标概念或训练样例抽取的分布，一种概率方法可在给定数目的训练样例之后界定变型空间为?-详尽的
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
有限假设空间的样本复杂度（ 4）
定理 7.1（变型空间的?-详尽化）
– 若假设空间 H有限，且 D为目标概念 c的一系列 m>=1个独立随机抽取的样例，那么对于任意 0=<?<=1，变型空间 VSH,D不是?-
详尽的概率小于或等于：
证明：
– 令 h1,...,hk为 H中关于 c的真实错误率大于?的所有假设。当且仅当 k个假设中至少有一个恰好与所有 m个独立随机抽取样例一致时，不能使变型空间?-详尽化。
– 任一假设真实错误率大于?，且与一个随机抽取样例一致的可能性最多为 1-?，因此，该假设与 m个独立抽取样例一致的概率最多为 (1-?)m
– 由于已知有 k个假设错误率大于?，那么至少有一个与所有 m个训练样例都不一致的概率最多为（当,则 ）
meH||
mmm eHHk ||)1(||)1(
10 e1
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
有限假设空间的样本复杂度（ 5）
定理 7.1基于训练样例的数目 m、允许的错误率
和 H的大小，给出了变型空间不是?-详尽的概率的上界
即它对于使用假设空间 H的任意学习器界定了 m个训练样例未能将所有“坏”的假设（错误率大于?的假设）
剔除出去的概率
利用上面的结论来确定为了减少此“未剔除”概率到一希望程度?所需的训练样例数
– 由
– 解出 m，得到
meH||
)/1ln(||ln1 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
有限假设空间的样本复杂度（ 6）
式子 7.2提供了训练样例数目的一般边界，该数目的样例足以在所期望的值?和?程度下，使任何一致学习器成功地学习到 H中的任意目标概念
训练样例的数目 m足以保证任意一致假设是可能（可能性为 1-?）近似（错误率为?）正确的
m随着 1/?线性增长，随着 1/?和假设空间的规模对数增长
上面的界限可能是过高的估计，主要来源于 |H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和
在 7.4节讨论一个更紧凑的边界以及能够覆盖无限大的假设空间的边界
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
不可知学习和不一致假设
如果学习器不假定目标概念可在 H中表示，而只简单地寻找具有最小训练错误率的假设，这样的学习器称为不可知学习器
式 7.2基于的假定是学习器输出一零错误率假设，在更一般的情形下学习器考虑到了有非零训练错误率的假设时，仍能找到一个简单的边界
令 S代表学习器可观察到的特定训练样例集合,errorS(h)
表示 h的训练错误率，即 S中被 h误分类的训练样例所占比例
令 hbest表示 H中有最小训练错误率的假设，问题是：多少训练样例才足以保证其真实错误率 errorD(hbest)不会多于?+errorS(hbest)？（上一节问题是这个问题的特例）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
不可知学习和不一致假设（ 2）
前面问题的回答使用类似定理 7.1的证明方法，这里有必要引入一般的 Hoeffding边界
Hoeffding边界刻画的是某事件的真实概率及其 m个独立试验中观察到的频率之间的差异
Hoeffding边界表明，当训练错误率 errorS(h)在包含 m个随机抽取样例的集合 S上测量时，则
上式给出了一个概率边界，说明任意选择的假设训练错误率不能代表真实情况，为保证 L寻找到的最佳的假设的错误率有以上的边界，我们必须考虑这 |H|个假设中任一个有较大错误率的概率
22])()(P r [ mSD ehe rro rhe rro r
22||)()(Pr mSD eHhe r r o rhe r r o rHh
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
不可知学习和不一致假设（ 3）
将上式左边概率称为?，问多少个训练样例 m才足以使?维持在一定值内，求解得到
式 7.3是式 7.2的一般化情形，适用于当最佳假设可能有非零训练错误率时，学习器仍能选择到最佳假设 h?H的情形。
)/1ln (||ln2 1 2 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
布尔文字的合取是 PAC可学习的
我们已经有了一个训练样例数目的边界，表示样本数目为多少时才足以可能近似学习到目标概念，现在用它来确定某些特定概念类别的样本复杂度和 PAC可学习性
考虑目标概念类 C，它由布尔文字的合取表示。
布尔文字是任意的布尔变量，或它的否定。问题,C是可 PAC学习的吗？
若假设空间 H定义为 n个布尔文字的合取，则假设空间 |H|的大小为 3n，得到关于 n布尔文字合取学习问题的样本复杂度
1 4 0)05.0/1ln (3ln101.0 1)/1ln (3ln1 nm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
布尔文字的合取是 PAC可学习的（ 2）
定理 7.2：布尔合取式的 PAC可学习性
– 布尔文字合取的类 C是用 Find-S算法 PAC可学习的
证明：
– 式 7.4显示了该概念类的样本复杂度是 n,1/?
和 1/?的多项式级，而且独立于 size(c)。为增量地处理每个训练样例,Find-S算法要求的运算量根据 n线性增长，并独立于 1/?,1/?和 size(c)。因此这一概念类别是 Find-S算法 PAC可学习的。
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
其他概念类别的 PAC可学习性
无偏学习器（无归纳偏置）
– 考虑一无偏概念类 C，它包含与 X相关的所有可教授概念,X中的实例定义为 n个布尔值特征，则有
– 无偏的目标概念类在 PAC模型下有指数级的样本复杂度
nXCH 2|| 22||||
)/1ln(2ln21 nm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
其他概念类别的 PAC可学习性
（ 2）
K项 DNF和 K-CNF概念
– 某概念类有多项式级的样本复杂度，但不能够在多项式时间内被学习到
– 概念类 C为 k项析取范式（ k项 DNF）的形式
– k项 DNF,T1?...?Tk，其中每一个 Ti为 n个布尔属性和它们的否定的合取
– 假定 H=C，则 |H|最多为 3nk，代入式 7.2，得到
– 因此,k项 DNF的样本复杂度为 1/?,1/?,n和 k的多项式级
– 但是计算复杂度不是多项式级，该问题是 NP完全问题（等效于其他已知的不能在多项式时间内解决的问题）
– 因此，虽然 k项 DNF有多项式级的样本复杂度，它对于使用
H=C的学习器没有多项式级的计算复杂度
)/1ln(3ln1 nkm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
其他概念类别的 PAC可学习性
（ 3）
– 令人吃惊的是，虽然 k项 DNF不是 PAC可学习的，但存在一个更大的概念类是 PAC可学习的
– 这个更大的概念类是 K-CNF，它有每样例的多项式级时间复杂度，又有多项式级的样本复杂度
– K-CNF：任意长度的合取式 T1?...?Tj，其中每个 Ti
为最多 k个布尔变量的析取
– 容易证明 K-CNF包含了 K项 DNF，因此概念类 k项
DNF是使用 H=K-CNF的一个有效算法可 PAC学习的
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
无限假设空间的样本复杂度
式子 7.2用 |H|刻画样本复杂度有两个缺点：
– 可能导致非常弱的边界
– 对于无限假设空间的情形，无法应用
本节考虑 H的复杂度的另一种度量，称为 H的
Vapnik-Chervonenkis维度（简称 VC维或 VC(H)）
使用 VC维代替 |H|也可以得到样本复杂度的边界，基于 VC维的样本复杂度比 |H|更紧凑，另外还可以刻画无限假设空间的样本复杂度
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
打散一个实例集合
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的这种打散实例集合的能力是其表示这些实例上定义的目标概念的能力的度量
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
Vapnik-Chervonenkis维度
打散一实例集合的能力与假设空间的归纳偏置紧密相关
无偏的假设空间能够打散所有实例组成的集合 X
直观上，被打散的 X的子集越大,H的表示能力越强
定义：定义在实例空间 X上的假设空间 H的 Vapnik-
Chervonenkis维，是可被 H打散的 X的最大有限子集的大小
如果 X的任意有限大的子集可被 H打散，则 VC(H)=?
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
Vapnik-Chervonenkis维度（ 2）
对于任意有限的 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
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
Vapnik-Chervonenkis维度（ 3）
– 假定 X上每个实例由恰好 3个布尔文字的合取表示，
而且假定 H中每个假设由至多 3个布尔文字描述，问
VC(H)是多少？
找到下面 3个实例的集合
– instance1,100
– instance2,010
– instance3,001
这三个实例的集合可被 H打散，可对如下任意所希望的划分建立一假设：如果该划分要排除 instancei，就将文字?li
加入到假设中
此讨论很容易扩展到特征数为 n的情况,n个布尔文字合取的 VC维至少为 n
实际就是 n，但证明比较困难，需要说明 n+1个实例的集合不可能被打散
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
样本复杂度和 VC维
使用 VC维作为 H复杂度的度量，就有可能推导出该问题的另一种解答，类似于式子 7.2的边界，即（ Blumer
el al,1989）
定理 7.3：样本复杂度的下界（ Ehrenfeucht et al,1989）
– 考虑任意概念类 C，且 VC(C)>=2，任意学习器 L，以及任意
0<?<1/8,0<?<1/100。存在一个分布 D以及 C中一个目标概念，
当 L观察到的样例数目小于下式时：
L将以至少?的概率输出一假设 h，使 errorD(h)>?
)/13(lo g)(8)/2(lo g41 22 HVCm
32 1)(),/1lo g (1m a x CVC
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
样本复杂度和 VC维（ 2）
定理 7.3说明，若训练样例的数目太少，
那么没有学习器能够以 PAC模型学习到任意非平凡的 C中每个目标概念
式子 7.7给出了保证充足数量的上界，而定理 7.3给出了下界
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
神经网络的 VC维
本节给出一般性的结论，以计算分层无环网络的 VC维。这个 VC维可用于界定训练样例的数量，该数达到多大才足以按照希望的?和?值近似可能正确地学习一个前馈网络
考虑一个由单元组成的网络 G，它形成一个分层有向无环图
– 分层有向无环图的特点：
节点可划分成层，即所有第 l层出来的有向边进入到第 l+1
层节点
没有有向环，即有向弧形成的回路
– 这样网络的 VC维的界定可以基于其图的结构和构造该图的基本单元的 VC维
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
神经网络的 VC维（ 2）
定义一些术语
– G表示神经网络
– n是 G的输入数目
– G只有 1个输出节点
– G的每个内部单元 Ni最多有 r个输入，并实现一布尔函数 ci:Rr?{0,1}，形成函数类 C
定义 C的 G-合成：网络 G能实现的所有函数的类，即网络 G表示的假设空间，表示成 CG
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
神经网络的 VC维（ 3）
定理 7.4分层有向无环网络的 VC维
（ Kearns & Vazirani 1994）
– 令 G为一分层有向无环图，有 n个输入节点和
s?2个内部节点，每个至少有 r个输入，令 C
为 VC维为 d的 Rr上的概念类，对应于可由每个内部节点 s描述的函数集合，令 CG为 C的 G
合成，对应于可由 G表示的函数集合，则
VC(CG)<=2dslog(es)
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
神经网络的 VC维（ 4）
假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的 r输入感知器 VC维为 r+1，
代入定理 7.4和式子 7.7，得到
上面的结果不能直接应用于反向传播的网络，
原因有两个：
– 此结果应用于感知器网络，而不是 sigmoid单元网络
– 不能处理反向传播中的训练过程
)log ()1(2)( essrCVC sp e r c e p tr o nG
))/13lo g ()lo g ()1(16)/2lo g (4(1 essrm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
学习的出错界限模型
计算学习理论考虑多种不同的问题框架
– 训练样例的生成方式（被动观察、主动提出查询）
– 数据中的噪声（有噪声或无噪声）
– 成功学习的定义（必须学到正确的目标概念还是有一定的可能性和近似性）
– 学习器所做得假定（实例的分布情况以及是否 C?H）
– 评估学习器的度量标准（训练样例数量、出错数量、
计算时间）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
学习的出错界限模型（ 2）
机器学习的出错界限模型
– 学习器的评估标准是它在收敛到正确假设前总的出错数
– 学习器每接受到一个样例 x，先预测目标值 c(x)，然后施教者给出正确的目标值
– 考虑的问题是：在学习器学习到目标概念前，它的预测会有多少次出错
– 下面讨论中，只考虑学习器确切学到目标概念前出错的次数，确切学到的含义是?x h(x)=c(x)
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
Find-S算法的出错界限
Find-S算法的一个简单实现
– 将 h初始化为最特殊假设 l1l1?...?lnln
– 对每个正例 x
从 h中移去任何不满足 x的文字
– 输出假设 h
计算一个边界，以描述 Find-S在确切学到目标概念 c前全部的出错次数
– Find-S永远不会将一反例错误地划分为正例，因此只需要计算将正例划分为反例的出错次数
– 遇到第一个正例，初始假设中 2n个项半数被删去，对后续的被当前假设误分类的正例，至少有一项从假设中删去
– 出错总数至多为 n+1
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
Halving算法的出错界限
学习器对每个新实例 x做出预测的方法是：从当前变型空间的所有假设中取多数票得来
将变型空间学习和用多数票来进行后续预测结合起来的算法称为 Halving算法
Halving算法只有在当前变型空间的多数假设不能正确分类新样例时出错，此时变型空间至少可减少到它的一半大小，因此出错界线是 log2|H|
Halving算法有可能不出任何差错就确切学习到目标概念，因为即使多数票是正确的，算法仍将移去那些不正确、少数票假设
Halving算法的一个扩展是允许假设以不同的权值进行投票（如贝叶斯最优分类器和后面讨论的加权多数算法）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
最优出错界限
问题：对于任意概念类 C，假定 H=C，最优的出错边界是什么？
最优出错边界是指在所有可能的学习算法中，最坏情况下出错边界中最小的那一个
对任意学习算法 A和任意目标概念 c，令 MA(c)代表 A为了确切学到 c，在所有可能训练样例序列中出错的最大值
对于任意非空概念类 C，令 MA(C)=maxc?CMA(c)
定义,C为任意非空概念类,C的最优出错界限定义为
Opt(C)是所有可能学习算法 A中 MA(C)的最小值
)(m in)( 学 习 CMCO pt AA 算法
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
最优出错界限（ 2）
非形式地说,Opt(C)是 C中最难的那个目标概念使用最不利的训练样例序列用最好的算法时的出错次数
Littlestone1987证明了
||lo g)()()( 2 CCMCO ptCVC H a l v i n g
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
加权多数算法
Halving算法的更一般形式称为加权多数算法
加权多数算法通过在一组预测算法中进行加权投票来作出预测，并通过改变每个预测算法的权来学习
加权多数算法可以处理不一致的训练数据，因为它不会消除与样例不一致的假设，只是降低其权
要计算加权多数算法的出错数量边界，可以用预测算法组中最好的那个算法的出错数量
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
加权多数算法（ 2）
加权多数算法一开始将每个预测算法赋予权值 1，然后考虑训练样例，只要一个预测算法误分类新训练样例，它的权被乘以某个系数 β,0<=β<1。
– 如果 β=0，则是 Halving算法
– 如果 β>0，则没有一个预测算法会被完全去掉。如果一算法误分类一个样例，那么它的权值变小
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
加权多数算法（ 3）
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
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
加权多数算法（ 4）
定理 7.5：加权多数算法的相对误差界限
– 令 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
– 由,得
意义：加权多数算法的出错数量不会大于算法池中最佳算法出错数量，加上一个随着算法池大小对数增长的项，再乘以一常数因子
ni iwW 1
W43
Mk n?
4321
)lo g(4.2)
43(lo g
)lo g(
2
2
2 nknkM
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
小结
可能近似正确模型（ PAC）针对的算法从某概念类 C中学习目标概念，使用按一个未知但固定的概念分布中随机抽取的训练样例，它要求学习器可能学习到一近似正确的假设，而计算量和训练样例数都只随着 1/?,1/?、实例长度和目标概念长度的多项式级增长
在 PAC学习模型的框架下，任何使用有限假设空间 H的一致学习器，将以 1-?的概率输出一个误差在?内的假设，所需的训练样例数 m满足
||ln)/1ln(1 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
小结（ 2）
不可知学习考虑更一般的问题：学习器不假定目标概念所在的类别，学习器从训练数据中输出 H中有最小误差率的假设。学习保证以概率
1-?从 H中最可能的假设中输出错误率小于?的假设，需要的随机抽取的训练样例数目 m满足
学习器考虑的假设空间的复杂度对所需样例的数目影响很大，而衡量假设空间复杂度的一个有用的度量是 VC维。 VC维是可被 H打散的最大实例集的大小
||ln)/1ln (2 1 2 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
小结（ 3）
在 PAC模型下以 VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是：
另一种学习模式称为出错界限模式，用于分析学习器在确切学习到目标概念之前会产生的误分类次数
– Halving算法在学习到 H中的任意目标概念前会有至多 log2|H|次出错
– 对任意概念类 C，最坏情况下最佳算法将有 Opt(C)
次出错，满足 VC(C)<=Opt(C)<=log2|C|
)/13(lo g)(8)/2(lo g41 22 HVCm 32 1)(),/1lo g (1m a x CVCm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
小结（ 4）
加权多数算法结合了多个预测算法的加权投票来分类新的实例，它基于这些预测算法在样例序列中的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数来计算
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 54
补充读物
计算学习理论中许多早期的工作针对的问题是：学习器能否在极限时确定目标概念
Gold1967给出了极限模型下的确定算法
Angluin1992给出了一个好的综述
Vapnik1982详细考察了一致收敛
Valiant1984给出了 PAC学习模型
Haussler1988讨论了?-详尽变型空间
Bluer et al.1989给出了 PAC模型下的一组有用的结论
Kearns & Vazirani1994提供了计算学习理论中许多结论的优秀的阐述
会议：计算学习理论年会 COLT
杂志：机器学习的特殊栏目
机器学习第 7章 计算学习理论
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
本章从理论上刻画了若干类型的机器学习问题中的困难和若干类型的机器学习算法的能力
这个理论要回答的问题是：
– 在什么样的条件下成功的学习是可能的？
– 在什么条件下某个特定的学习算法可保证成功运行？
这里考虑两种框架：
– 可能近似正确（ PAC）
确定了若干假设类别，判断它们能否从多项式数量的训练样例中学习得到
定义了一个对假设空间复杂度的自然度量，由它可以界定归纳学习所需的训练样例数目
– 出错界限框架
考查了一个学习器在确定正确假设前可能产生的训练错误数量
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介
机器学习理论的一些问题：
– 是否可能独立于学习算法确定学习问题中固有的难度？
– 能否知道为保证成功的学习有多少训练样例是必要的或充足的？
– 如果学习器被允许向施教者提出查询，而不是观察训练集的随机样本，会对所需样例数目有怎样的影响？
– 能否刻画出学习器在学到目标函数前会有多少次出错？
– 能否刻画出一类学习问题中固有的计算复杂度？
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
简介（ 2）
对所有这些问题的一般回答还未知，但不完整的学习计算理论已经开始出现
本章阐述了该理论中的一些关键结论，并提供了在特定问题下一些问题的答案
主要讨论在只给定目标函数的训练样例和候选假设空间的条件下，对该未知目标函数的归纳学习问题
主要要解决的问题是：需要多少训练样例才足以成功地学习到目标函数以及学习器在达到目标前会出多少次错
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
简介（ 3）
如果明确了学习问题的如下属性，那么有可能给出前面问题的定量的上下界
– 学习器所考虑的假设空间的大小和复杂度
– 目标概念须近似到怎样的精度
– 学习器输出成功的假设的可能性
– 训练样例提供给学习器的方式
本章不会着重于单独的学习算法，而是在较宽广的学习算法类别中考虑问题：
– 样本复杂度：学习器要收敛到成功假设，需要多少训练样例？
– 计算复杂度：学习器要收敛到成功假设，需要多大的计算量？
– 出错界限：在成功收敛到一个假设前，学习器对训练样例的错误分类有多少次？
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
简介（ 4）
为了解决这些问题需要许多特殊的条件设定，
比如
–,成功”的学习器的设定
学习器是否输出等于目标概念的假设
只要求输出的假设与目标概念在多数时间内意见一致
学习器通常输出这样的假设
– 学习器如何获得训练样例
由一个施教者给出
由学习器自己实验获得
按照某过程随机生成
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
简介（ 5）
7.2节介绍可能近似正确（ PAC）学习框架
7.3节在 PAC框架下，分析几种学习算法的样本复杂度和计算复杂度
7.4节介绍了假设空间复杂度的一个重要度量标准，称为 VC维，并且将 PAC分析扩展到假设空间无限的情况
7.5节介绍出错界限模型，并提供了前面章节中几个学习算法出错数量的界限，最后介绍了加权多数算法
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
可能学习近似正确假设
可能近似正确学习模型（ PAC）
– 指定 PAC学习模型适用的问题
– 在此模型下，学习不同类别的目标函数需要多少训练样例和多大的计算量
本章的讨论将限制在学习布尔值概念，
且训练数据是无噪声的（许多结论可扩展到更一般的情形）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
问题框架
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进行最差情况的分析
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
假设的错误率
为了描述学习器输出的假设 h对真实目标概念的逼近程度，首先要定义假设 h对应于目标概念 c和实例分布 D的真实错误率
h的真实错误率是应用 h到将来按分布 D抽取的实例时的期望的错误率
定义：假设 h的关于目标概念 c和分布 D的真实错误率为 h误分类根据 D随机抽取的实例的概率
)()(Pr)( xhxcherror DxD
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
假设的错误率（ 2）
图 7-1,h关于 c的错误率是随机选取的实例落入 h和 c不一致的区间的概率
真实错误率紧密地依赖于未知的概率分布 D
– 如果 D是一个均匀的概率分布，那么图 7-1中假设的错误率为 h和 c不一致的空间在全部实例空间中的比例
– 如果 D恰好把 h和 c不一致区间中的实例赋予了很高的概率，相同的 h
和 c将造成更高的错误率
h关于 c的错误率不能直接由学习器观察到,L只能观察到在训练样例上 h的性能
训练错误率：指代训练样例中被 h误分类的样例所占的比例
问题,h的观察到的训练错误率对真实错误率产生不正确估计的可能性多大？
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
PAC可学习性
我们的目标是刻画出这样的目标概念，它们能够从合理数量的随机抽取训练样例中通过合理的计算量可靠地学习
对可学习性的表述
– 一种可能的选择：为了学习到使 errorD(h)=0的假设 h，
所需的训练样例数
这样的选择不可行：首先要求对 X中每个可能的实例都提供训练样例；其次要求训练样例无误导性
– 可能近似学习：首先只要求学习器输出错误率限定在某常数?范围内的假设，其次要求对所有的随机抽取样例序列的失败的概率限定在某常数?范围内
只要求学习器可能学习到一个近似正确的假设
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
PAC可学习性（ 2）
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的编码长度
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
PAC可学习性（ 3）
在实践中，通常更关心所需的训练样例数，
– 如果 L对每个训练样例需要某最小处理时间，那么为了使 c是 L可 PAC学习的,L必须从多项式数量的训练样例中进行学习
– 实际上，为了显示某目标概念类别 C是可 PAC学习的，一个典型的途径是证明 C中每个目标概念可以从多项式数量的训练样例中学习到，且处理每个样例的时间也是多项式级
PAC可学习性的一个隐含的条件：对 C中每个目标概念 c，假设空间 H都包含一个以任意小误差接近 c的假设
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
有限假设空间的样本复杂度
PAC可学习性很大程度上由所需的训练样例数确定
随着问题规模的增长所带来的所需训练样例的增长称为该学习问题的样本复杂度
我们把样本复杂度的讨论限定于一致学习器
（输出完美拟合训练数据的学习器）
能够独立于特定算法，推导出任意一致学习器所需训练样例数的界限
变型空间：能正确分类训练样例 D的所有假设的集合。 ) ) }()(()(,(|{,xcxhDxcxHhVS DH
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
有限假设空间的样本复杂度（ 2）
变型空间的重要意义是：每个一致学习器都输出一个属于变型空间的假设
因此界定任意一个一致学习器所需的样例数量，
只需要界定为保证变型中没有不可接受假设所需的样例数量
定义：考虑一假设空间 H，目标概念 c，实例分布 D以及 c的一组训练样例 S。当 VSH,D中每个假设 h关于 c和 D错误率小于?时，变型空间被称为
c和 D是?-详尽的。 )()(,herrorVSh DDH
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
有限假设空间的样本复杂度（ 3）
-详尽的变型空间表示与训练样例一致的所有假设的真实错误率都小于?
从学习器的角度看，所能知道的只是这些假设能同等地拟合训练数据，它们都有零训练错误率
只有知道目标概念的观察者才能确定变型空间是否为?-详尽的
但是，即使不知道确切的目标概念或训练样例抽取的分布，一种概率方法可在给定数目的训练样例之后界定变型空间为?-详尽的
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
有限假设空间的样本复杂度（ 4）
定理 7.1（变型空间的?-详尽化）
– 若假设空间 H有限，且 D为目标概念 c的一系列 m>=1个独立随机抽取的样例，那么对于任意 0=<?<=1，变型空间 VSH,D不是?-
详尽的概率小于或等于：
证明：
– 令 h1,...,hk为 H中关于 c的真实错误率大于?的所有假设。当且仅当 k个假设中至少有一个恰好与所有 m个独立随机抽取样例一致时，不能使变型空间?-详尽化。
– 任一假设真实错误率大于?，且与一个随机抽取样例一致的可能性最多为 1-?，因此，该假设与 m个独立抽取样例一致的概率最多为 (1-?)m
– 由于已知有 k个假设错误率大于?，那么至少有一个与所有 m个训练样例都不一致的概率最多为（当,则 ）
meH||
mmm eHHk ||)1(||)1(
10 e1
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
有限假设空间的样本复杂度（ 5）
定理 7.1基于训练样例的数目 m、允许的错误率
和 H的大小，给出了变型空间不是?-详尽的概率的上界
即它对于使用假设空间 H的任意学习器界定了 m个训练样例未能将所有“坏”的假设（错误率大于?的假设）
剔除出去的概率
利用上面的结论来确定为了减少此“未剔除”概率到一希望程度?所需的训练样例数
– 由
– 解出 m，得到
meH||
)/1ln(||ln1 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
有限假设空间的样本复杂度（ 6）
式子 7.2提供了训练样例数目的一般边界，该数目的样例足以在所期望的值?和?程度下，使任何一致学习器成功地学习到 H中的任意目标概念
训练样例的数目 m足以保证任意一致假设是可能（可能性为 1-?）近似（错误率为?）正确的
m随着 1/?线性增长，随着 1/?和假设空间的规模对数增长
上面的界限可能是过高的估计，主要来源于 |H|项，它产生于证明过程中在所有可能假设上计算那些不可接受的假设的概率和
在 7.4节讨论一个更紧凑的边界以及能够覆盖无限大的假设空间的边界
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
不可知学习和不一致假设
如果学习器不假定目标概念可在 H中表示，而只简单地寻找具有最小训练错误率的假设，这样的学习器称为不可知学习器
式 7.2基于的假定是学习器输出一零错误率假设，在更一般的情形下学习器考虑到了有非零训练错误率的假设时，仍能找到一个简单的边界
令 S代表学习器可观察到的特定训练样例集合,errorS(h)
表示 h的训练错误率，即 S中被 h误分类的训练样例所占比例
令 hbest表示 H中有最小训练错误率的假设，问题是：多少训练样例才足以保证其真实错误率 errorD(hbest)不会多于?+errorS(hbest)？（上一节问题是这个问题的特例）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
不可知学习和不一致假设（ 2）
前面问题的回答使用类似定理 7.1的证明方法，这里有必要引入一般的 Hoeffding边界
Hoeffding边界刻画的是某事件的真实概率及其 m个独立试验中观察到的频率之间的差异
Hoeffding边界表明，当训练错误率 errorS(h)在包含 m个随机抽取样例的集合 S上测量时，则
上式给出了一个概率边界，说明任意选择的假设训练错误率不能代表真实情况，为保证 L寻找到的最佳的假设的错误率有以上的边界，我们必须考虑这 |H|个假设中任一个有较大错误率的概率
22])()(P r [ mSD ehe rro rhe rro r
22||)()(Pr mSD eHhe r r o rhe r r o rHh
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
不可知学习和不一致假设（ 3）
将上式左边概率称为?，问多少个训练样例 m才足以使?维持在一定值内，求解得到
式 7.3是式 7.2的一般化情形，适用于当最佳假设可能有非零训练错误率时，学习器仍能选择到最佳假设 h?H的情形。
)/1ln (||ln2 1 2 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
布尔文字的合取是 PAC可学习的
我们已经有了一个训练样例数目的边界，表示样本数目为多少时才足以可能近似学习到目标概念，现在用它来确定某些特定概念类别的样本复杂度和 PAC可学习性
考虑目标概念类 C，它由布尔文字的合取表示。
布尔文字是任意的布尔变量，或它的否定。问题,C是可 PAC学习的吗？
若假设空间 H定义为 n个布尔文字的合取，则假设空间 |H|的大小为 3n，得到关于 n布尔文字合取学习问题的样本复杂度
1 4 0)05.0/1ln (3ln101.0 1)/1ln (3ln1 nm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
布尔文字的合取是 PAC可学习的（ 2）
定理 7.2：布尔合取式的 PAC可学习性
– 布尔文字合取的类 C是用 Find-S算法 PAC可学习的
证明：
– 式 7.4显示了该概念类的样本复杂度是 n,1/?
和 1/?的多项式级，而且独立于 size(c)。为增量地处理每个训练样例,Find-S算法要求的运算量根据 n线性增长，并独立于 1/?,1/?和 size(c)。因此这一概念类别是 Find-S算法 PAC可学习的。
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
其他概念类别的 PAC可学习性
无偏学习器（无归纳偏置）
– 考虑一无偏概念类 C，它包含与 X相关的所有可教授概念,X中的实例定义为 n个布尔值特征，则有
– 无偏的目标概念类在 PAC模型下有指数级的样本复杂度
nXCH 2|| 22||||
)/1ln(2ln21 nm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
其他概念类别的 PAC可学习性
（ 2）
K项 DNF和 K-CNF概念
– 某概念类有多项式级的样本复杂度，但不能够在多项式时间内被学习到
– 概念类 C为 k项析取范式（ k项 DNF）的形式
– k项 DNF,T1?...?Tk，其中每一个 Ti为 n个布尔属性和它们的否定的合取
– 假定 H=C，则 |H|最多为 3nk，代入式 7.2，得到
– 因此,k项 DNF的样本复杂度为 1/?,1/?,n和 k的多项式级
– 但是计算复杂度不是多项式级，该问题是 NP完全问题（等效于其他已知的不能在多项式时间内解决的问题）
– 因此，虽然 k项 DNF有多项式级的样本复杂度，它对于使用
H=C的学习器没有多项式级的计算复杂度
)/1ln(3ln1 nkm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 28
其他概念类别的 PAC可学习性
（ 3）
– 令人吃惊的是，虽然 k项 DNF不是 PAC可学习的，但存在一个更大的概念类是 PAC可学习的
– 这个更大的概念类是 K-CNF，它有每样例的多项式级时间复杂度，又有多项式级的样本复杂度
– K-CNF：任意长度的合取式 T1?...?Tj，其中每个 Ti
为最多 k个布尔变量的析取
– 容易证明 K-CNF包含了 K项 DNF，因此概念类 k项
DNF是使用 H=K-CNF的一个有效算法可 PAC学习的
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 29
无限假设空间的样本复杂度
式子 7.2用 |H|刻画样本复杂度有两个缺点：
– 可能导致非常弱的边界
– 对于无限假设空间的情形，无法应用
本节考虑 H的复杂度的另一种度量，称为 H的
Vapnik-Chervonenkis维度（简称 VC维或 VC(H)）
使用 VC维代替 |H|也可以得到样本复杂度的边界，基于 VC维的样本复杂度比 |H|更紧凑，另外还可以刻画无限假设空间的样本复杂度
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 30
打散一个实例集合
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的这种打散实例集合的能力是其表示这些实例上定义的目标概念的能力的度量
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 31
Vapnik-Chervonenkis维度
打散一实例集合的能力与假设空间的归纳偏置紧密相关
无偏的假设空间能够打散所有实例组成的集合 X
直观上，被打散的 X的子集越大,H的表示能力越强
定义：定义在实例空间 X上的假设空间 H的 Vapnik-
Chervonenkis维，是可被 H打散的 X的最大有限子集的大小
如果 X的任意有限大的子集可被 H打散，则 VC(H)=?
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 32
Vapnik-Chervonenkis维度（ 2）
对于任意有限的 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
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 33
Vapnik-Chervonenkis维度（ 3）
– 假定 X上每个实例由恰好 3个布尔文字的合取表示，
而且假定 H中每个假设由至多 3个布尔文字描述，问
VC(H)是多少？
找到下面 3个实例的集合
– instance1,100
– instance2,010
– instance3,001
这三个实例的集合可被 H打散，可对如下任意所希望的划分建立一假设：如果该划分要排除 instancei，就将文字?li
加入到假设中
此讨论很容易扩展到特征数为 n的情况,n个布尔文字合取的 VC维至少为 n
实际就是 n，但证明比较困难，需要说明 n+1个实例的集合不可能被打散
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 34
样本复杂度和 VC维
使用 VC维作为 H复杂度的度量，就有可能推导出该问题的另一种解答，类似于式子 7.2的边界，即（ Blumer
el al,1989）
定理 7.3：样本复杂度的下界（ Ehrenfeucht et al,1989）
– 考虑任意概念类 C，且 VC(C)>=2，任意学习器 L，以及任意
0<?<1/8,0<?<1/100。存在一个分布 D以及 C中一个目标概念，
当 L观察到的样例数目小于下式时：
L将以至少?的概率输出一假设 h，使 errorD(h)>?
)/13(lo g)(8)/2(lo g41 22 HVCm
32 1)(),/1lo g (1m a x CVC
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 35
样本复杂度和 VC维（ 2）
定理 7.3说明，若训练样例的数目太少，
那么没有学习器能够以 PAC模型学习到任意非平凡的 C中每个目标概念
式子 7.7给出了保证充足数量的上界，而定理 7.3给出了下界
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 36
神经网络的 VC维
本节给出一般性的结论，以计算分层无环网络的 VC维。这个 VC维可用于界定训练样例的数量，该数达到多大才足以按照希望的?和?值近似可能正确地学习一个前馈网络
考虑一个由单元组成的网络 G，它形成一个分层有向无环图
– 分层有向无环图的特点：
节点可划分成层，即所有第 l层出来的有向边进入到第 l+1
层节点
没有有向环，即有向弧形成的回路
– 这样网络的 VC维的界定可以基于其图的结构和构造该图的基本单元的 VC维
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 37
神经网络的 VC维（ 2）
定义一些术语
– G表示神经网络
– n是 G的输入数目
– G只有 1个输出节点
– G的每个内部单元 Ni最多有 r个输入，并实现一布尔函数 ci:Rr?{0,1}，形成函数类 C
定义 C的 G-合成：网络 G能实现的所有函数的类，即网络 G表示的假设空间，表示成 CG
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 38
神经网络的 VC维（ 3）
定理 7.4分层有向无环网络的 VC维
（ Kearns & Vazirani 1994）
– 令 G为一分层有向无环图，有 n个输入节点和
s?2个内部节点，每个至少有 r个输入，令 C
为 VC维为 d的 Rr上的概念类，对应于可由每个内部节点 s描述的函数集合，令 CG为 C的 G
合成，对应于可由 G表示的函数集合，则
VC(CG)<=2dslog(es)
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 39
神经网络的 VC维（ 4）
假定要考虑的分层有向无环网络中单个节点都是感知器，由于单独的 r输入感知器 VC维为 r+1，
代入定理 7.4和式子 7.7，得到
上面的结果不能直接应用于反向传播的网络，
原因有两个：
– 此结果应用于感知器网络，而不是 sigmoid单元网络
– 不能处理反向传播中的训练过程
)log ()1(2)( essrCVC sp e r c e p tr o nG
))/13lo g ()lo g ()1(16)/2lo g (4(1 essrm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 40
学习的出错界限模型
计算学习理论考虑多种不同的问题框架
– 训练样例的生成方式（被动观察、主动提出查询）
– 数据中的噪声（有噪声或无噪声）
– 成功学习的定义（必须学到正确的目标概念还是有一定的可能性和近似性）
– 学习器所做得假定（实例的分布情况以及是否 C?H）
– 评估学习器的度量标准（训练样例数量、出错数量、
计算时间）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 41
学习的出错界限模型（ 2）
机器学习的出错界限模型
– 学习器的评估标准是它在收敛到正确假设前总的出错数
– 学习器每接受到一个样例 x，先预测目标值 c(x)，然后施教者给出正确的目标值
– 考虑的问题是：在学习器学习到目标概念前，它的预测会有多少次出错
– 下面讨论中，只考虑学习器确切学到目标概念前出错的次数，确切学到的含义是?x h(x)=c(x)
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 42
Find-S算法的出错界限
Find-S算法的一个简单实现
– 将 h初始化为最特殊假设 l1l1?...?lnln
– 对每个正例 x
从 h中移去任何不满足 x的文字
– 输出假设 h
计算一个边界，以描述 Find-S在确切学到目标概念 c前全部的出错次数
– Find-S永远不会将一反例错误地划分为正例，因此只需要计算将正例划分为反例的出错次数
– 遇到第一个正例，初始假设中 2n个项半数被删去，对后续的被当前假设误分类的正例，至少有一项从假设中删去
– 出错总数至多为 n+1
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 43
Halving算法的出错界限
学习器对每个新实例 x做出预测的方法是：从当前变型空间的所有假设中取多数票得来
将变型空间学习和用多数票来进行后续预测结合起来的算法称为 Halving算法
Halving算法只有在当前变型空间的多数假设不能正确分类新样例时出错，此时变型空间至少可减少到它的一半大小，因此出错界线是 log2|H|
Halving算法有可能不出任何差错就确切学习到目标概念，因为即使多数票是正确的，算法仍将移去那些不正确、少数票假设
Halving算法的一个扩展是允许假设以不同的权值进行投票（如贝叶斯最优分类器和后面讨论的加权多数算法）
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 44
最优出错界限
问题：对于任意概念类 C，假定 H=C，最优的出错边界是什么？
最优出错边界是指在所有可能的学习算法中，最坏情况下出错边界中最小的那一个
对任意学习算法 A和任意目标概念 c，令 MA(c)代表 A为了确切学到 c，在所有可能训练样例序列中出错的最大值
对于任意非空概念类 C，令 MA(C)=maxc?CMA(c)
定义,C为任意非空概念类,C的最优出错界限定义为
Opt(C)是所有可能学习算法 A中 MA(C)的最小值
)(m in)( 学 习 CMCO pt AA 算法
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 45
最优出错界限（ 2）
非形式地说,Opt(C)是 C中最难的那个目标概念使用最不利的训练样例序列用最好的算法时的出错次数
Littlestone1987证明了
||lo g)()()( 2 CCMCO ptCVC H a l v i n g
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 46
加权多数算法
Halving算法的更一般形式称为加权多数算法
加权多数算法通过在一组预测算法中进行加权投票来作出预测，并通过改变每个预测算法的权来学习
加权多数算法可以处理不一致的训练数据，因为它不会消除与样例不一致的假设，只是降低其权
要计算加权多数算法的出错数量边界，可以用预测算法组中最好的那个算法的出错数量
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 47
加权多数算法（ 2）
加权多数算法一开始将每个预测算法赋予权值 1，然后考虑训练样例，只要一个预测算法误分类新训练样例，它的权被乘以某个系数 β,0<=β<1。
– 如果 β=0，则是 Halving算法
– 如果 β>0，则没有一个预测算法会被完全去掉。如果一算法误分类一个样例，那么它的权值变小
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 48
加权多数算法（ 3）
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
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 49
加权多数算法（ 4）
定理 7.5：加权多数算法的相对误差界限
– 令 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
– 由,得
意义：加权多数算法的出错数量不会大于算法池中最佳算法出错数量，加上一个随着算法池大小对数增长的项，再乘以一常数因子
ni iwW 1
W43
Mk n?
4321
)lo g(4.2)
43(lo g
)lo g(
2
2
2 nknkM
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 50
小结
可能近似正确模型（ PAC）针对的算法从某概念类 C中学习目标概念，使用按一个未知但固定的概念分布中随机抽取的训练样例，它要求学习器可能学习到一近似正确的假设，而计算量和训练样例数都只随着 1/?,1/?、实例长度和目标概念长度的多项式级增长
在 PAC学习模型的框架下，任何使用有限假设空间 H的一致学习器，将以 1-?的概率输出一个误差在?内的假设，所需的训练样例数 m满足
||ln)/1ln(1 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 51
小结（ 2）
不可知学习考虑更一般的问题：学习器不假定目标概念所在的类别，学习器从训练数据中输出 H中有最小误差率的假设。学习保证以概率
1-?从 H中最可能的假设中输出错误率小于?的假设，需要的随机抽取的训练样例数目 m满足
学习器考虑的假设空间的复杂度对所需样例的数目影响很大，而衡量假设空间复杂度的一个有用的度量是 VC维。 VC维是可被 H打散的最大实例集的大小
||ln)/1ln (2 1 2 Hm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 52
小结（ 3）
在 PAC模型下以 VC(H)表示的足以导致成功学习的训练样例数目的上界和下界分别是：
另一种学习模式称为出错界限模式，用于分析学习器在确切学习到目标概念之前会产生的误分类次数
– Halving算法在学习到 H中的任意目标概念前会有至多 log2|H|次出错
– 对任意概念类 C，最坏情况下最佳算法将有 Opt(C)
次出错，满足 VC(C)<=Opt(C)<=log2|C|
)/13(lo g)(8)/2(lo g41 22 HVCm 32 1)(),/1lo g (1m a x CVCm
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 53
小结（ 4）
加权多数算法结合了多个预测算法的加权投票来分类新的实例，它基于这些预测算法在样例序列中的出错来学习每个算法的权值。加权多数算法产生的错误界限可用算法池中最佳预测算法的出错数来计算
2003.12.18 机器学习 -计算学习理论 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 54
补充读物
计算学习理论中许多早期的工作针对的问题是：学习器能否在极限时确定目标概念
Gold1967给出了极限模型下的确定算法
Angluin1992给出了一个好的综述
Vapnik1982详细考察了一致收敛
Valiant1984给出了 PAC学习模型
Haussler1988讨论了?-详尽变型空间
Bluer et al.1989给出了 PAC模型下的一组有用的结论
Kearns & Vazirani1994提供了计算学习理论中许多结论的优秀的阐述
会议：计算学习理论年会 COLT
杂志：机器学习的特殊栏目
