精华区文章阅读

发信人: AA (积极的人生、美好的人生), 信区: Algorithm
标  题: 机器学习(TOM.M.Mitchell)：第2章(zz)
发信站: 哈工大紫丁香 (2002年05月23日20:18:27 星期四), 站内信件

第2章　概念学习和一般到特殊序

从特殊的训练样例中归纳出一般函数是机器学习的中心问题。本章介绍概念学习
：给定某一类别的若干正例和反例，从中获得该类别的一般定义。概念学习也可
被看作一个搜索问题，它在预定义的假设空间中搜索假设，使其与训练样例有最
佳的拟合度。多数情形下，为了高效的搜索，可以利用假设空间中一种自然形成
的结构——即一般到特殊偏序结构。本章展示了几种概念学习算法，并讨论了这
些算法能收敛得到正确假设的条件。这里还分析了归纳学习的本质，以及任意程
序能从训练数据中泛化的理由。
2.1 介绍
许多机器学习问题涉及到从特殊训练样例中得到一般概念。比如人们不断学习的
一些一般概念和类别包括：鸟类、汽车、勤奋的学习等。每个概念可被看作一个
对象或事件集合，它是从更大的集合中选取的子集（如从动物的集合中选取鸟类
），或者是在这个较大集合中定义的布尔函数（如在动物集合中定义的函数，它
对鸟类产生true 并对其他动物产生false）。
本章考虑的问题是，给定一样例集合以及每个样例是否属于某一概念的标注，怎
样自动推断出该概念的一般定义。这一问题被称为概念学习（concept learning
），或称从样例中逼近布尔值函数。
定义：  概念学习是指从有关某个布尔函数的输入输出训练样例中，推断出该布尔函数。
2.2 一个概念学习任务
为了良好地理解概念学习，考虑一个概念学习的例子，目标概念是：“Aldo进行
水上运动的日子”。表2-1描述了一系列日子的样例，每个样例表示为属性的集合
。属性 EnjoySport表示这一天Aldo是否乐于进行水上运动。这个任务的目的是，
基于某天的各属性，以预测出该天EnjoySport的值。
表2-1目标概念EnjoySport的正例和反例
Example Sky AirTemp Humidity    Wind    Water   Forecast    EnjoySport
1   Sunny   Warm    Normal  Strong  Warm    Same    Yes
2   Sunny   Warm    High    Strong  Warm    Same    Yes
3   Rainy   Cold    High    Strong  Warm    Change  No
4   Sunny   Warm    High    Strong  Cool    Change  Yes
在这种情况下，采取什么样的形式来表示假设呢？可以先考虑一个较为简单的形
式，即实例的各属性约束的合取式。在这里，可令每个假设为6个约束的向量，这
些约束指定了属性Sky、AirTemp、Humidity、Wind、Water和Forecast的值。每个
属性可取值为：
    由“?”表示任意值
    明确指定的属性值（如 AirTemp=Warm）
    由“”表示不接受任何值
如果某些实例x满足假设h的所有约束，那么h将x 分类为正例，（h(x)=1 ）。比
如，为判定Aldo只在寒冷和潮湿的日子里进行水上运动（并与其他属性无关），
），或称从样例中逼近布尔值函数。
定义：  概念学习是指从有关某个布尔函数的输入输出训练样例中，推断出该布尔函数。
2.2 一个概念学习任务
为了良好地理解概念学习，考虑一个概念学习的例子，目标概念是：“Aldo进行
水上运动的日子”。表2-1描述了一系列日子的样例，每个样例表示为属性的集合
。属性 EnjoySport表示这一天Aldo是否乐于进行水上运动。这个任务的目的是，
基于某天的各属性，以预测出该天EnjoySport的值。
表2-1目标概念EnjoySport的正例和反例
Example Sky AirTemp Humidity    Wind    Water   Forecast    EnjoySport
1   Sunny   Warm    Normal  Strong  Warm    Same    Yes
2   Sunny   Warm    High    Strong  Warm    Same    Yes
3   Rainy   Cold    High    Strong  Warm    Change  No
4   Sunny   Warm    High    Strong  Cool    Change  Yes
在这种情况下，采取什么样的形式来表示假设呢？可以先考虑一个较为简单的形
式，即实例的各属性约束的合取式。在这里，可令每个假设为6个约束的向量，这
些约束指定了属性Sky、AirTemp、Humidity、Wind、Water和Forecast的值。每个
属性可取值为：
    由“?”表示任意值
    明确指定的属性值（如 AirTemp=Warm）
    由“”表示不接受任何值
如果某些实例x满足假设h的所有约束，那么h将x 分类为正例，（h(x)=1 ）。比
如，为判定Aldo只在寒冷和潮湿的日子里进行水上运动（并与其他属性无关），
    目标概念c: EnjoySport: X→{0, 1}
    训练样例集D：目标函数的正例和反例（见表2-1）
    求解：
    H中的一假设h，使对于X中任意x，h(x)=c(x)。
2.2.1   术语定义
在本书中，我们使用以下的术语来讨论概念学习问题。概念定义在一个实例（in
stance）集合之上，这个集合表示为X。在本例中，X是所有可能的日子，每个日
子由Sky、AirTemp、Humidity、Wind、Water和Forecast六个属性表示。待学习的
概念或函数称为目标概念 (target concept)，记作c。一般来说，c可以是定义在
实例X上的任意布尔函数，即c:X→{0, 1}。在这个例子里，目标概念对应于属性
EnjoySport的值，当EnjoySport=Yes时c(x)=1，当 EnjoySport=No时c(x)=0。
在学习目标概念时，必须提供一套训练样例（training examples），每个样例为
X中的一个实例x以及它的目标概念值c(x)（如表2-1中的训练样例）。对于c(x)=
1的实例被称为正例(positive example)，或称为目标概念的成员。对于c(x)=0的
实例为反例(negative example)，或称为非目标概念成员。经常可以用序偶<x,c
(x)>来描述训练样例，表示其包含了实例x和目标概念值c(x)。符号D用来表示训
练样例的集合。
一旦给定目标概念c的训练样例集，学习器面临的问题就是假设或估计c。使用符
号H来表示所有可能假设(all possible hypotheses)的集合，这个集合内才是为
确定目标概念所考虑的范围。通常H依设计者所选择的假设表示而定。H中每个的
假设h表示X上定义的布尔函数，即h:X→{0,1}。机器学习的目标就是寻找一个假
设h，使对于X中的所有x，h(x)=c(x)。
2.2.2   归纳学习假设
机器学习的任务是在整个实例集合X上确定与目标概念c相同的假设h，然而我们对
于c仅有的信息只是它在训练样例上的值。因此，归纳学习算法最多只能保证输出
的假设能与训练样例相拟合。如果没有更多的信息，我们只能假定，对于未见实
例最好的假设就是与训练数据最佳拟合的假设。这是归纳学习的一个基本假定，
本书中将对此做更多的阐述。这里我们简单提及，在第5、6、7章将更形式化和定
量地审定和分析这一假定。
归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也
能在未见实例中很好地逼近目标函数。
2.3 作为搜索的概念学习
概念学习可以看作是一个搜索的过程，范围是假设的表示所隐含定义的整个空间
。搜索的目标是为了寻找能最好地拟合训练样例的假设。必须注意到，当假设的
表示形式选定后，那么也就隐含地为学习算法确定了所有假设的空间。这些假设
是学习程序所能表示的，也是它能够学习的。考虑在EnjoySport 学习任务中的实
例集合X和假设集合H。如果属性Sky有3种可能的值，而AirTemp、Humidity、Win
d、Water和 Forecast都只有两种可能值，则实例空间X包含了3×2×2×2×2×2
=96种不同的实例。类似的计算可得，在假设空间H中有5×4×4×4×4×4=5120种
语法不同(syntactically distinct)的假设。然而，注意到包含有符号
的假设代表空实例集合，即它们将每个实例都分类为反例。因此，语义不同(sem
antically distinct)的假设只有1+4×3×3×3×3×3=973个。这里的EnjoySpor
t例子是一个非常简单的学习任务，它的假设空间相对较小且有限。多数实际的学
习任务包含更大的、有时是无限的假设空间。
如果把学习看作是一个搜索问题，那么很自然，对学习算法的研究需要考查假设
空间搜索的不同策略。特别引起我们兴趣的算法应能有效地搜索非常大的或无限
的假设空间，以找到最佳拟合训练数据的假设。
2.3.1   假设的一般到特殊序
许多概念学习算法中，搜索假设空间的方法依赖于其中一种很有用的结构：假设
的一般到特殊序关系。利用假设空间的这种自然结构，我们可以在无限的假设空
间中进行彻底的搜索，而不需要明确地列举所有的假设。为说明一般到特殊序，
考虑以下两个假设：
h1=<Sunny, ?, ?, Strong, ?, ?>
h2=<Sunny, ?, ?, ?, ?, ?>
哪些实例可被h1和h2划分为正例？由于h2包含的实例约束较少，它划分出的正例
也较多。实际上，任何被h1划分为正例的实例都会被h2划分为正例，因此，我们
说h2比h1更一般。
直观上的“比……更一般”这种关系可以如下精确定义。首先，对X中任意实例x
和H中任意假设h，我们说x满足h当且仅当h(x)=1。现在以实例集合的形式定义一
个more-general-than-or-equal-to的关系：给定假设hj和hk，hj more-general
-than-or-equal-to hk，当且仅当任意一个满足hk的实例同时也满足hj。
定义：  令hj和hk为在X上定义的布尔函数。定义一个more-general-than-or-equ
al-to关系，记做≥g。称hj≥g hk当且仅当
(x∈X)[(hk(x)=1)→(hj(x)=1)]
有必要考虑一假设严格地比另一假设更一般的情形。因此，我们说hj严格的more
-general-than hk（写作hj＞ghk），当且仅当(hj≥ghk)∧(hk≥ghj)。
最后，还可以定义逆向的关系“比……更特殊”为hj more-specific-than hk，
当hk more-general-than hj。
插图——原书页码：  25
Instances: 实例集
Hypotheses：假设集
Specific：特殊
General：一般

图2-1 实例、假设和more-general-than关系
左边的方框代表所有实例的集合X，右边的方框代表所有假设集合H。右边的每个
假设对应左边X中某个子集——即被此假设划分为正例的集合。连接假设的箭头代
表more-general-than关系。箭头所指为较特殊的假设。注意到h2对应的实例子集
包含了h1对应的实例子集，因此h2 more-general-than h1。
为说明这些定义，考虑EnjoySport例子中的h1、h2、h3，如图2-1所示。这三个假
设是如何由≥g关系相关联起来的？如前所述，h2比h1更一般是因为每个满足h1的
实例都满足h2。相似的，h2也比h3更一般。注意h1和h3之间相互之间不存在≥g关
系，虽然满足这两个假设的实例有交叠，但没有一个集合完全包含另一个集合。
注意≥g和＞g关系的定义独立于目标概念。它们只依赖于满足这两个假设的实例
，而与哪些实例满足目标概念无关。用形式化的语言来说，≥g关系定义了假设空
间H上的一个偏序（即这个关系是自反、反对称和传递的）。偏序关系的含义（对
应于全序）是，可能存在h1和h3这样的假设对， (h1≥gh3)而且&#6165
6; (h3≥gh1)。
≥g关系很重要，因为它在假设空间H上对任意概念学习问题提供了一种有用的结
构。后面的章节将阐述概念学习算法如何利用这一偏序结构，以有效地搜索假设
空间。
2.4 Find-S：寻找极大特殊假设
如何使用more-general-than偏序来搜索与训练样例相一致的假设？一种办法是从
H中最特殊假设开始，然后在该假设覆盖正例失败时将其一般化（当一假设能正确
地划分一个正例时，称该假设“覆盖”该正例）。使用偏序实现的Find-S算法的
精确描述见表2-3。
表2-3 Find-S算法
1.  将h初始化为H中最特殊假设
2.  对每个正例x
    对h的每个属性约束ai
如果 x满足ai
那么不做任何事
否则将h中ai替换为x满足的紧邻更一般约束
3.  输出假设h
为说明这一算法，假定给予学习器的一系列训练样例如表2-1所示。Find-S的第一
步是将h初始化为H中最特殊假设：
h←<, , , , , >
在扫描到表2-1中第一个训练样例时，它刚好是个正例。很清楚，这时的h太特殊
了。h中的每一个都不满足该样例的约束，因此，每个属性都被替换成能
满足该例的紧邻更一般的值约束，也就是这一样例的属性值本身：
h←<Sunny, Warm, Normal, Strong, Warm, Same>
这个h仍旧太特殊了，它把除了第一个样例以外的所有实例都划分为反例。下一步
，第2个训练样例（仍然为正例）迫使该算法进一步将h泛化。这次使用“?”代替
h中不能满足新样例的属性值。之后的假设变为：
h←<Sunny, Warm, ?, Strong, Warm, Same>
然后处理第三个训练样例，这里是一个反例，h不变。实际上，Find-S算法简单地
忽略每一个反例！这一开始似乎有点奇怪。注意这时假设h仍然与新的反例一致（
即h能将此例正确地划分为反例），因此不需要对h作任何更改。一般情况下，只
要我们假定假设空间H确实包含真正的目标概念c，而且训练样例不包含错误，那
么当前的假设h不需要因反例出现而更改。原因在于当前假设h是H中与所观察到的
正例相一致的最特殊的假设，由于假定目标概念c在H中，而且它一定是与所有正
例一致的，那么c一定比h更一般。而目标概念c不会覆盖一个反例，因此h也不会
（由more-general-than的定义）。因此，对反例，h不需要作出任何修改。
接着完成Find-S算法，第四个正例使得h更一般：
h←<Sunny, Warm, ?, Strong, ?, ?>
Find-S算法演示了一种利用more-general-than偏序来搜索假设空间的方法。这一
搜索沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。图2-2说明了在实例
和假设空间中的这种搜索过程。在每一步，假设只在需要覆盖新的正例时被泛化
。因此，每一步得到的假设，都是在那一点上与训练样例一致的最特殊的假设。
这也是其名字Find-S的由来。概念学习的思想在许多不同的算法中用到，它们使
用了同样的more-general-than偏序。一部分算法在本章讨论，另一些放在第10章
。
插图——原书页码：  27
Instances: 实例集
Hypotheses：假设集
Specific：特殊
General：一般

图2-2 Find-S中的假设空间搜索
搜索开始于H中最特殊的假设h0，然后根据训练样例逐渐一般化（h1到h4）。在实
例空间图中，正例被标以“+”，反例标以“-”，而没有包含在训练样例中的实
例则以实心圆点表示。
Find-S算法的关键特点在于：对以属性约束的合取式描述的假设空间（如EnjoyS
port中的H），Find-S保证输出为H中与正例一致的最特殊的假设。只要正确的目
标概念包含在H中，并且训练数据都是正确的，最终的假设也与所有反例一致。然
而，这一学习算法仍存在一些未解决的问题：
    学习过程是否收敛到了正确的目标概念？虽然Find-S找到了与训练数据
一致的假设，但没办法确定它是否找到了惟一合适的假设（即目标概念本身），
或是否还有其他可能的假设。我们希望算法知道它能否收敛到目标概念，如果不
能，至少要描述出这种不确定性。
    为什么要用最特殊的假设。如果有多个与训练样例一致的假设，Find-
S只能找到最特殊的。为什么我们偏好最特殊的假设，而不选最一般假设，抑或一
般程度位于两者之间的某个假设。
    训练样例是否相互一致？在多数实际的学习问题中，训练数据中常出现
某些错误或噪声，这样的不一致的训练集将严重破坏Find-S算法，因为它忽略了
所有反例。我们期望的算法至少能检测出训练数据的不一致性，并且最好能容纳
这样的错误。
    如果有多个极大特殊假设怎么办？在EnjoySport任务的假设语言H中，
总有一个惟一的最特殊假设与训练数据一致。然而，对其他一些假设空间（后面
将讨论到）可能有多个极大特殊假设。这种情况下，Find-S必须被扩展，以允许
其在选择怎样泛化假设的路径上回溯，以容纳目标假设位于偏序结构的另一分支
上的可能性。更进一步，我们可以定义一个不存在极大特殊假设的假设空间，然
而这是一个更理论性的问题而不是实践问题（见习题2.7）
2.5 变型空间和候选消除算法
本节描述的是概念学习的另一种途径即候选消除算法（Candidate-Elimination）
。它能解决Find-S 中的若干不足之处。Find-S 输出的假设只是H中能够拟合训练
样例的多个假设中的一个。而在候选消除算法中，输出的是与训练样例一致的所
有假设的集合。令人惊奇地是，候选消除算法在描述这一集合时不需要明确列举
其所有成员。这也归功于more-general-than偏序结构。在这里需要维护一个一致
假设集合的简洁表示，然后在遇到新的训练样例时逐步精化这一表示。
候选消除算法的应用有：从化学质谱分析（chemical mass spectroscopy）中学
习规则性 (Mitchell 1979)；和学习启发式搜索的控制规则(Mitchell et al. 1
983)。然而，候选消除算法和Find-S算法的实际应用都受到限制，因为它们在训
练数据含有噪声时性能较差。在这里介绍候选消除算法的目的，是为了基础的机
器学习理论提供一个良好的概念框架。本章其余部分将展示这一算法及相关的问
题。从下一章开始将考察面对有噪声数据时更常用的学习算法。
2.5.1   表示
候选消除算法寻找所有与训练样例一致的假设。为精确描述这一算法，这里先引
入一些基本的定义。首先，我们称一个假设是与训练样例一致的(consistent)，
当它能正确分类这些样例。
定义：  一个假设h与训练样例集合D一致(consistent)，当且仅当对D中每一个样
例<x,c(x)>，h(x)=c(x)。
Consistent(h,D)≡(<x,c(x)> ∈ D) h(x)=c(x)
注意这里定义的一致与前面定义的满足有关键的不同。一个样例x在h(x)=1时称为
满足假设h，不论x是目标概念的正例还是反例。然而，这一样例是否与h一致与目
标概念有关，即是否h(x)=c(x)。
候选消除算法能够表示与训练样例一致的所有假设。在假设空间中的这一子集被
称为关于假设空间H和训练样例D的变型空间(version space)，因为它包含的是目
标概念的所有合理的变型。
定义：  关于假设空间H和训练样例集D的变型空间(version space)，标记为VSH,
D，是H中与训练样例D一致的所有假设构成的子集。
VSH,D≡{h∈H|Consistent(h,D)}
2.5.2   列表后消除算法
显然，表示变型空间的一种方法是列出其所有成员。这样可产生一个简单的算法
，称为列表后消除（List-Then-Eliminate）算法。其定义见表2-4。
表2-4 列表后消除算法
列表后消除算法
1.  变型空间VersionSpace←包含H中所有假设的列表
2.  对每个训练样例<x, c(x)>
从变型空间中移除所有h(x)≠c(x)的假设h
3.  输出VersionSpace中的假设列表
列表后消除算法首先将变型空间初始化为包含H中所有假设，然后从中去除与任一
训练样例不一致的假设。包含候选假设的变型空间随着观察到越来越多的样例而
缩减，直到只剩一个（理想情况下）与所有样例一致的假设。这可能就是所要的
目标概念。如果没有充足的数据使变型空间缩减到只有一个假设，那么该算法将
输出一个集合，这个集合中所有的假设与训练样例都一致。
原则上，只要假设空间是有限的，就可使用列表后消除算法。它具有很多优点，
如能保证得到所有与训练数据一致的假设。但是，这一算法非常烦琐地列出了H中
所有假设，这对于大多数实际的假设空间是不现实的要求。
2.5.3   变型空间的更简明表示
候选消除算法与上面的列表后消除算法遵循同样的原则。然而，它使用一种更简
明的变型空间的表示法。在此，变型空间被表示为它的最一般的和最特殊的成员
。这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变
型空间。
插图——原书页码：  31

图2-3 变型空间及其一般和特殊边界集合
变型空间中包含了所有的6个假设，但可以简单地用S和G来表示。箭头表示实例间
的more-general-than关系。这个变型空间对应于表2-1中描述的 EnjoySport概念
学习问题及其训练样例。
为说明变型空间的这种表示，再一次考虑表2-2中描述的EnjoySport概念学习问题
。对于表2-1中给定的4个训练样例，Find-S输出假设：
h＝<Sunny, Warm, ?, Strong, ?, ?>
实际上，这只是H中与训练样例一致的所有6个假设之一。所有6个假设在图2-3中
表示出。它们构成了与该数据集合和假设表示相对应的变型空间。6个假设之间的
箭头表示实例间的more-general-than关系。候选消除算法通过使用最一般成员（
在图2-3中标为G）和最特殊成员（图中标为S）来表示变型空间。只给定这两个集
合S和G，就可以列举出变型空间中的所有成员，方法是使用一般到特殊偏序结构
来生成S和G集合之间的所有假设。
可以直观地看出，使用最一般和最特殊集合表示变型空间的作法是合理的。下面
我们精确地定义S和G这两个边界集合，并且证明它们确实代表了变型空间。
定义：  关于假设空间H和训练数据D的一般边界（General boundary）G，是在H中
与D相一致的极大一般（maximally general）成员的集合。
G≡{ g∈H | Consistent(g, D)∧(g´∈H)[(g´
＞g g) ∧Consistent(g´, D)]}
定义：  关于假设空间H和训练数据D的特殊边界（Specific boundary）S，是在H
中与D相一致的极大特殊（maximally specific）成员的集合。
S≡{ s∈H | Consistent(s, D)∧(s´∈H)[(s＞g s&ac
ute;) ∧Consistent(s´, D)]}
只要集合G和S被良好地定义了（见习题2.7），它们就完全规定了变型空间。这里
还可以证明，变型空间的确切组成是：G中包含的假设集，S中包含的假设集，以
及G和S之间偏序结构所规定的假设。
定理2-1变型空间表示定理。令X为一任意的实例集合，H与为X上定义的布尔假设
的集合。令c: X→{0, 1}为X上定义的任一目标概念，并令D为任一训练样例的集
合{<x, c(x)>}。对所有的X，H，c，D以及良好定义的S和G：
VSH,D = { h∈H | (s∈S) (g∈G) (g≥gh≥gs)}
证明：为证明该定理只需证明：(1)每一个满足上式右边的h都在VSH,D中，(2) V
SH,D的每个成员都满足等式右边。为证明（1），令g为G中任意一个成员，s为S中
任一成员，h为H的任一成员而且g≥gh≥gs。由S的定义，s必须被D中所有的正例
满足。因为h≥g s， h也被D中所有正例满足。相似地，由G的定义，g必须不被D
中任一反例满足，且由于 g≥g h，h也不被D中所有反例满足。由于 h被D中所有
正例满足且不被其中所有反例满足，因此h与D一致，因此h是VSH,D的成员。这证
明了步骤（1）。（2）的讨论稍微有些复杂，可以使用反证法，假定VSH,D中某一
h不满足等式右边，那么将产生矛盾（见习题2.6）。
2.5.4   候选消除学习算法
候选消除算法计算出的变型空间，包含H中所有与训练样例的观察到的序列一致的
假设。开始，变型空间被初始化为H中所有假设的集合。即将G边界集合初始化为
H中最一般的假设：
G0←{<?, ?, ?, ?, ?, ?>}
并将S边界集合初始化为最特殊假设：
S0←{<, , , , , >}
这两个边界集合包含了整个假设空间。因为H中所有假设都比S0更一般，且比G0更
特殊。算法在处理每个训练样例时，S和G边界集合分别被泛化和特化，从变型空
间中逐步消去与样例不一致的假设。在所有训练样例处理完后，得到的变型空间
就包含了所有与样例一致的假设，而且只包含这样的假设。这一算法在表2-5中描
述：

表2-5 使用变型空间的候选消除算法
注意正例和反例是怎样同时影响S和G的。
将G集合初始化为H中极大一般假设
将S集合初始化为H中极大特殊假设
对每个训练样例d，进行以下操作：
    如果d是一正例
    从G中移去所有与d不一致的假设
    对S中每个与d不一致的假设s
    从S中移去s
    把s的所有的极小泛化式h加入到S中，其中h满足
    h与d一致，而且G的某个成员比h更一般
    从S中移去所有这样的假设：它比S中另一假设更一般
    如果d是一个反例
    从S中移去所有与d不一致的假设
    对G中每个与d不一致的假设g
    从G中移去g
    把g的所有的极小特化式h加入到G中，其中h满足
    h与d一致，而且S的某个成员比h更特殊
    从G中移去所有这样的假设：它比G中另一假设更特殊
注意算法中的操作，包括对给定假设的极小泛化式和极小特化式的计算，并确定
那些非极小和非极大的假设。具体的实现当然依赖于实例和假设的表示方式。然
而，只要这些操作被良好地定义了，该算法就可应用于任意概念学习和任意假设
空间。在以下将实际演示算法的运行步骤，从中可以看到在EnjoySport这个例子
中，这些操作是怎样实现的。
2.5.5   算法的示例
图2-4演示了候选消除算法应用到表2-1中头两个训练样例时的运行步骤。如上所
述，边界集合先被初始化为G0和S0，分别代表H中最一般和最特殊的假设。
插图——原书页码：  34
Training examples:   训练样例

图2-4 候选消除算法步骤1
S0和G0为最初的边界集合，分别对应最特殊和最一般假设。训练样例1和2使得S边
界变得更一般，如Find-S算法中一样。这些样例对G边界没有影响。
当第一个训练样例出现时（这里为一正例），候选消除算法检查S边界，并发现它
过于特殊了——因为它不能覆盖该正例。这一边界就被修改为紧邻更一般的假设
，以覆盖新的样例。修改后的边界在图2-4中显示为S1。G边界不需要修改，因为
G0能够正确地覆盖该样例。当处理第二个训练样例时（也是－正例），同样地，
需要将S进一步泛化到S2，G仍旧不变（G2=G1=G0）。注意对头两个正例的处理非
常类似于Find-S算法。
在头两步的算法中，正例使得变型空间的S边界逐渐泛化。而反例扮演的角色恰好
相反，使得G边界逐渐特化。考虑第三个训练样例，如图2-5所示。这一反例显示
，G边界过于一般了。也就是说，G中的假设错误地将该例判定为正例了。因此G边
界中的假设必须被特化，使它能对新的反例正确分类。如图2-5所示，这里有几种
可选的极小更特殊的假设。这些全都成为新的G3边界集合的成员。
插图——原书页码：  35
Training examples:   训练样例

图2-5 候选消除算法步骤2
样例3是一反例，它把G2边界特化为G3。注意在G3中有多个可选的极大一般假设。
有6个属性可以用来使G2特化，为什么只有3个在G3中呢？比如h=<?, ?, Normal,
?, ?, ?>是G2的一个极小特化式，它能够将新的样例正确地划分为反例，但它不
在G3中。将这一假设排除在外的原因是，它与以前遇到的正例不一致。在算法中
只是简单地判断h并不比当前特殊边界S2更一般。实际上变型空间的S边界形成了
以往正例的摘要说明，它可以用来判断任何给定的假设是否与以往样例一致。根
据定义，任何比S更一般的假设能够覆盖所有S能覆盖的样例，即以往的所有正例
。同样，G边界说明了以往所有反例的信息。任何比G更特殊的假设能保证与所有
G0能够正确地覆盖该样例。当处理第二个训练样例时（也是－正例），同样地，
需要将S进一步泛化到S2，G仍旧不变（G2=G1=G0）。注意对头两个正例的处理非
常类似于Find-S算法。
在头两步的算法中，正例使得变型空间的S边界逐渐泛化。而反例扮演的角色恰好
相反，使得G边界逐渐特化。考虑第三个训练样例，如图2-5所示。这一反例显示
，G边界过于一般了。也就是说，G中的假设错误地将该例判定为正例了。因此G边
界中的假设必须被特化，使它能对新的反例正确分类。如图2-5所示，这里有几种
可选的极小更特殊的假设。这些全都成为新的G3边界集合的成员。
插图——原书页码：  35
Training examples:   训练样例

图2-5 候选消除算法步骤2
样例3是一反例，它把G2边界特化为G3。注意在G3中有多个可选的极大一般假设。
有6个属性可以用来使G2特化，为什么只有3个在G3中呢？比如h=<?, ?, Normal,
?, ?, ?>是G2的一个极小特化式，它能够将新的样例正确地划分为反例，但它不
在G3中。将这一假设排除在外的原因是，它与以前遇到的正例不一致。在算法中
只是简单地判断h并不比当前特殊边界S2更一般。实际上变型空间的S边界形成了
以往正例的摘要说明，它可以用来判断任何给定的假设是否与以往样例一致。根
据定义，任何比S更一般的假设能够覆盖所有S能覆盖的样例，即以往的所有正例
。同样，G边界说明了以往所有反例的信息。任何比G更特殊的假设能保证与所有
反例相一致。这是因为根据定义，任一假设不会覆盖G所不能覆盖的样例。
第四个训练样例，如图2-6所示，使变型空间的S边界更一般化。它也导致G边界中
的一个成员被删除，因为这个成员不能覆盖新的正例。最后这一动作来自于表2-
5算法中“如果d是一正例”下的第一步骤。为理解这一步的原因，需要考虑为什
么不一致的假设要从G中移去。注意这一假设不能再被特化，因为这样它将不能覆
盖新的样例。它也不能被泛化，因为按照G的定义，任何更一般的假设至少会覆盖
一个反例。这样，这一假设必须从G中移去，也相当于移去了变型空间的偏序结构
中的一整个分支。
插图——原书页码：  36上
Training examples:   训练样例

图2-6 候选消除算法步骤3
正例使S边界更一般，从S3变为S4。G3的一个成员也必须被删除，因为它不再比S
4边界更一般。
在处理完这4个样例后，边界集合S4和G4划分出的变型空间包含了与样例一致的所
有假设的集合。整个变型空间，包含那些由S4和G4界定的假设都在图2-7中示出。
这一变型空间不依赖于训练样本出现的次序（因为最终它包含了与训练样例集一
致的所有假设）。如果提供更多的训练数据，S和G边界将继续单调移动并相互靠
近，划分出越来越小的变型空间来。
插图——原书页码：  36下

图2-7 EnjoySport概念学习问题中的最终的变型空间
2.6 关于变型空间和候选消除的说明
2.6.1   候选消除算法是否会收敛到正确的假设
由候选消除算法得到的变型空间能够收敛到描述目标概念的假设的条件是（1）在
训练样例中没有错误（2）在H中确实包含描述目标概念的正确假设。实际上，如
果遇到新的训练样例，可以监测变型空间以判定其与真正的目标概念之间是否还
有分歧，以及为精确确定目标概念还需要多少训练样例。当S和G边界集合收敛到
单个的可确定的假设时，目标概念才真正获得。
如果训练数据中包含错误会怎样？比如，以上例子中第二个样例被错误地标示为
一反例。这种情况下，很不幸，算法肯定会从变型空间中删除正确的目标概念。
因为它会删除所有与样例不一致的假设，所以在遇到这一错误的反例时，算法将
从变型空间中移去正确的目标概念。当然，如果给定足够的训练数据，最终，我
们会发现S和G边界收敛得到一个空的变型空间，从而得知训练数据有误。空的变
型空间表示H中没有假设能够与样例一致。相似的情形会出现在另一种环境中：当
训练样例正确，但目标概念不能由假设表示方式所描述（比如目标概念是某几个
属性特征的析取，而假设空间只支持合取的形式）。以后我们将详细考虑这些可
能性。目前，我们只考虑样例数据是正确的并且目标概念确实在假设空间中。
2.6.2   下一步需要什么样的训练样例
询的数目可能会多于log2|VS|。
2.6.3   怎样使用不完全学习概念
在上面的例子中，如果除了4个样例之外没有更多的训练样例，但机器现在要对未
见过的实例进行分类。虽然图2-3的变型空间中仍包含多个假设，即目标概念还未
完全学习到，仍然有可能对新样例进行一定可信度的分类。为示范这一过程，假
定机器需要对表2-6中的4个新实例进行分类。
表2-6待分类的新实例
Instance    Sky AirTemp Humidity    Wind    Water   Forecast    EnjoySport
A   Sunny   Warm    Normal  Strong  Cool    Change  ?
B   Rainy   Cold    Normal  Light   Warm    Same    ?
C   Sunny   Warm    Normal  Light   Warm    Same    ?
D   Sunny   Cold    Normal  Strong  Warm    Same    ?
注意，虽然实例A不在训练样例中，但当前变型空间中，每个假设（见图2-3）都
将其分类为正例。由于变型空间的所有假设一致同意实例A为正例，学习器将A划
分为正例的可信度，与只有单个的目标概念时一样。不管变型空间中哪个假设最
终成为目标概念，它都会将其划分为正例。进一步，我们知道不需要列举变型空
间中所有的假设，就可知道每个假设都会将其划分为正例。这一条件成立当且仅
当实例满足S的每个成员（为什么？）。原因是变型空间中的其他每个假设，都至
少比S的某个成员更一般。由我们的more-general-than的定义，如果新的实例满
足S的所有成员，它一定也满足这些更一般的假设。
相似地，实例B被变型空间中的每个假设划分为反例。所以这个实例可被放心地划
分为反例，即使概念是不完全学习的。对这一条件的测试的有效方法是，判断实
例不满足G中的所有成员（为什么？）。
实例C的情况有所不同。变型空间中半数的假设划分其为正例，半数划分为反例。
因此，学习器无法可信地分类这一样例，除非提供更多的训练样例。注意到，实
例C与前一节提出的一个最优查询相同。这是可以预见的，因为最有分类歧义性的
实例也一定最能提供新的分类信息。
最后，实例D在变型空间中被两个假设分为正例，被其他4个假设分为反例。这个
例子的分类可信度比实例A和B要小。投票选举要倾向于反例分类，所以我们可以
输出拥有最大票数的分类，还可附带一个可信度比例以表明投票的倾向程度。在
第6章将讨论到，如果假定H中所有假设是有相等的先验概率，那么投票的方法能
得到新实例的最可能分类。进一步的，投正例票假设所占的比例可视为：在给定
训练数据时，实例为正例的可能性。
2.7 归纳偏置
如上所述，在给定正确的训练样例并且保证初始假设空间包含目标概念时，候选
消除算法可以收敛到目标概念。如果目标概念不在假设空间中怎么办？是否可设
计一包含所有假设的空间来解决这一困难？假设空间的大小对于算法推广到未见
实例的能力有什么影响？假设空间的大小对所需训练样例的数量有什么影响？这
些都是归纳推理中的一些基本问题。这里我们在候选消除算法中考察这些问题。
然而可以看到，这里的分析中得到的结论可以应用于任意的概念学习系统。
2.7.1   一个有偏的假设空间
如果想保证假设空间包含目标概念，一个明显的方法是扩大假设空间，使每个可
能的假设都包含在内。再一次使用EnjoySport这个例子，其中我们将假设空间限
制为只包含属性值的合取。由于这一限制，假设空间不能够表示最简单的析取形
式的目标概念，如“Sky=Sunny或Sky=Cloudy”。实际上，如果给定以下三个训练
样例，它们来自于该析取式假设，我们的算法将得到一个空的变型空间。
Example Sky AirTemp Humidity    Wind    Water   Forecast    EnjoySport
1   Sunny   Warm    Normal  Strong  Cool    Change  Yes
2   Cloudy  Warm    Normal  Strong  Cool    Change  Yes
3   Rainy   Warm    Normal  Strong  Cool    Change  No
之所以不存在与这3个样例一致的假设的原因是，与头两个样例一致，并且能在给
定假设空间H中表示的最特殊的假设是：
S2: <?, Warm, Nornal, Strong, Cool, Change>
这一假设虽然是H中与样例一致的最特殊的假设，它仍然过于一般化了：它将第三
个样例错误地划为正例。问题在于，我们使学习器偏向于只考虑合取的假设，这
里需要表示能力更强的假设空间。
2.7.2   无偏的学习器
很显然，为了保证目标概念在假设空间中，需要提供一个假设空间，它能表达所
有的可教授概念(every teachable concept)。换言之，它能够表达实例集X的所
有可能的子集。一般地，我们把集合X所有子集的集合称为X的幂集（power set）
。
例如在EnjoySport学习任务中，使用6种属性描述的实例空间X的大小为96。在这
一实例集合上可以定义多少概念？换言之，X的幂集大小是什么？一般说来在集合
X上定义的相异子集数目（即X幂集的大小）为2|X|，其中|X|是X的元素数目。因
此在这一实例空间上可定义296，或大约是1028个不同的目标概念，这也是学习器
所需要学习的目标概念数目。回忆2.3节中合取假设空间只能表示973个假设——

--
                人世间的事谁也无法掌握
                  该执著的  永不怨悔
                  改舍去的  不在牵挂
                  改珍惜的  好好把握

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: NLPCenter.hit.edu.cn]

Algorithm 版 (精华区)