本书展示了机器学习中核心的
算法和理论，并阐明了算法的运行过程。本书综合了许多的研究成果，例如统计学、人工智能、哲学、信息论、生物学、认知科学、计算复杂性和控制论等，并以此来理解问题的背景、算法和其中的隐含假定。
本书可作为计算机专业本科生、研究生教材，也可作为相关领域研究人员、教师的参考书。
第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的值。每个属性可取值为：
l
由“?”表示任意值
l
明确指定的属性值（如 AirTemp=Warm）
l
由“Æ”表示不接受任何值
如果某些实例x满足假设h的所有约束，那么h将x 分类为正例，（h(x)=1
）。比如，为判定Aldo只在寒冷和潮湿的日子里进行水上运动（并与其他属性无关），这样的假设可表示为下面的表达式：
<?, Cold,
High, ?, ?, ?>
最一般的假设是每一天都是正例，可表示为：
<?, ?, ?, ?, ?, ?>
而最特殊的假设即每一天都是反例，表示为：
<Æ, Æ, Æ, Æ, Æ, Æ >
综上所述，EnjoySport 这个概念学习任务需要学习的是使EnjoySport=Yes的日子，并将其表示为属性约束的合取式。一般说来，任何概念学习任务能被描述为：实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。以这种一般形式定义的EnjoySport概念学习任务见表2-2。
表2-2 EnjoySport 概念学习任务
|
n
已知：
n
实例集X：可能的日子，每个日子由下面的属性描述：
n
Sky（可取值为Sunny，Cloudy和Rainy）
n
AirTemp（可取值为Warm和Cold）
n
Humidity（可取值为Normal和High）
n
Wind（可取值为Strong和Weak）
n
Water（可取值为Warm和Cool）
n
Forecast（可取值为Same和Change）
n
假设集H：每个假设描述为6个属性Sky，AirTemp，Humidity，Wind，Water和Forecast的值约束的合取。约束可以为“?”（表示接受任意值），“Æ”（表示拒绝所有值），或一特定值。
n
目标概念c: EnjoySport: X→{0, 1}
n
训练样例集D：目标函数的正例和反例（见表2-1）
n
求解：
n
H中的一假设h，使对于X中任意x，h(x)=c(x)。
|
2.2.1
术语定义
在本书中，我们使用以下的术语来讨论概念学习问题。概念定义在一个实例（instance）集合之上，这个集合表示为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、Wind、Water和 Forecast都只有两种可能值，则实例空间X包含了3×2×2×2×2×2=96种不同的实例。类似的计算可得，在假设空间H中有5×4×4×4×4×4=5120种语法不同(syntactically
distinct)的假设。然而，注意到包含有Æ符号的假设代表空实例集合，即它们将每个实例都分类为反例。因此，语义不同(semantically distinct)的假设只有1+4×3×3×3×3×3=973个。这里的EnjoySport例子是一个非常简单的学习任务，它的假设空间相对较小且有限。多数实际的学习任务包含更大的、有时是无限的假设空间。
如果把学习看作是一个搜索问题，那么很自然，对学习算法的研究需要考查假设空间搜索的不同策略。特别引起我们兴趣的算法应能有效地搜索非常大的或无限的假设空间，以找到最佳拟合训练数据的假设。
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，hjmore-general-than-or-equal-to hk，当且仅当任意一个满足hk的实例同时也满足hj。
定义：
令hj和hk为在X上定义的布尔函数。定义一个more-general-than-or-equal-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。
Instances: 实例集
Hypotheses：假设集
Specific：特殊
General：一般
图2-1 实例、假设和more-general-than关系
左边的方框代表所有实例的集合X，右边的方框代表所有假设集合H。右边的每个假设对应左边X中某个子集——即被此假设划分为正例的集合。连接假设的箭头代表more-general-than关系。箭头所指为较特殊的假设。注意到h2对应的实例子集包含了h1对应的实例子集，因此h2more-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)而且Ø (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
n
对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章。
Instances: 实例集
Hypotheses：假设集
Specific：特殊
General：一般
图2-2 Find-S中的假设空间搜索
搜索开始于H中最特殊的假设h0，然后根据训练样例逐渐一般化（h1到h4）。在实例空间图中，正例被标以“+”，反例标以“-”，而没有包含在训练样例中的实例则以实心圆点表示。
Find-S算法的关键特点在于：对以属性约束的合取式描述的假设空间（如EnjoySport中的H），Find-S保证输出为H中与正例一致的最特殊的假设。只要正确的目标概念包含在H中，并且训练数据都是正确的，最终的假设也与所有反例一致。然而，这一学习算法仍存在一些未解决的问题：
l
学习过程是否收敛到了正确的目标概念？虽然Find-S找到了与训练数据一致的假设，但没办法确定它是否找到了惟一合适的假设（即目标概念本身），或是否还有其他可能的假设。我们希望算法知道它能否收敛到目标概念，如果不能，至少要描述出这种不确定性。
l
为什么要用最特殊的假设。如果有多个与训练样例一致的假设，Find-S只能找到最特殊的。为什么我们偏好最特殊的假设，而不选最一般假设，抑或一般程度位于两者之间的某个假设。
l
训练样例是否相互一致？在多数实际的学习问题中，训练数据中常出现某些错误或噪声，这样的不一致的训练集将严重破坏Find-S算法，因为它忽略了所有反例。我们期望的算法至少能检测出训练数据的不一致性，并且最好能容纳这样的错误。
l
如果有多个极大特殊假设怎么办？在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. 1983)。然而，候选消除算法和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
变型空间的更简明表示
候选消除算法与上面的列表后消除算法遵循同样的原则。然而，它使用一种更简明的变型空间的表示法。在此，变型空间被表示为它的最一般的和最特殊的成员。这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。
图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´) ∧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) VSH,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，进行以下操作：
n
如果d是一正例
n
从G中移去所有与d不一致的假设
n
对S中每个与d不一致的假设s
n
从S中移去s
n
把s的所有的极小泛化式h加入到S中，其中h满足
n
h与d一致，而且G的某个成员比h更一般
n
从S中移去所有这样的假设：它比S中另一假设更一般
n
如果d是一个反例
n
从S中移去所有与d不一致的假设
n
对G中每个与d不一致的假设g
n
从G中移去g
n
把g的所有的极小特化式h加入到G中，其中h满足
n
h与d一致，而且S的某个成员比h更特殊
n
从G中移去所有这样的假设：它比G中另一假设更特殊
|
注意算法中的操作，包括对给定假设的极小泛
化式和极小特化式的计算，并确定那些非极小和非极大的假设。具体的实现当然依赖于实例和假设的表示方式。然而，只要这些操作被良好地定义了，该算法就可应
用于任意概念学习和任意假设空间。在以下将实际演示算法的运行步骤，从中可以看到在EnjoySport这个例子中，这些操作是怎样实现的。
2.5.5
算法的示例
图2-4演示了候选消除算法应用到表2-1中头两个训练样例时的运行步骤。如上所述，边界集合先被初始化为G0和S0，分别代表H中最一般和最特殊的假设。
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边界集合的成员。
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中移去，也相当于移去了变型空间的偏序结构中的一整个分支。
Training
examples: 训练样例
图2-6 候选消除算法步骤3
正例使S边界更一般，从S3变为S4。G3的一个成员也必须被删除，因为它不再比S4边界更一般。
在处理完这4个样例后，边界集合S4和G4划分出的变型空间包含了与样例一致的所有假设的集合。整个变型空间，包含那些由S4和G4界定的假设都在图2-7中示出。这一变型空间不依赖于训练样本出现的次序（因为最终它包含了与训练样例集一致的所有假设）。如果提供更多的训练数据，S和G边界将继续单调移动并相互靠近，划分出越来越小的变型空间来。
图2-7 EnjoySport概念学习问题中的最终的变型空间
2.6
关于变型空间和候选消除的说明
2.6.1
候选消除算法是否会收敛到正确的假设
由候选消除算法得到的变型空间能够收敛到描述目标概念的假设的条件是（1）在训练样例中没有错误（2）在H中确实包含描述目标概念的正确假设。实际上，如果遇到新的训练样例，可以监测变型空间以判定其与真正的目标概念之间是否还有分歧，以及为精确确定目标概念还需要多少训练样例。当S和G边界集合收敛到单个的可确定的假设时，目标概念才真正获得。
如果训练数据中包含错误会怎样？比如，以上
例子中第二个样例被错误地标示为一反例。这种情况下，很不幸，算法肯定会从变型空间中删除正确的目标概念。因为它会删除所有与样例不一致的假设，所以在遇
到这一错误的反例时，算法将从变型空间中移去正确的目标概念。当然，如果给定足够的训练数据，最终，我们会发现S和G边界收敛得到一个空的变型空间，从而得知训练数据有误。空的变型空间表示H中没有假
设能够与样例一致。相似的情形会出现在另一种环境中：当训练样例正确，但目标概念不能由假设表示方式所描述（比如目标概念是某几个属性特征的析取，而假设
空间只支持合取的形式）。以后我们将详细考虑这些可能性。目前，我们只考虑样例数据是正确的并且目标概念确实在假设空间中。
2.6.2
下一步需要什么样的训练样例
到这里我们都假定训练样例由某个外部的施教
者提供。假想学习器可以主宰实验进程，下一步它要自己选择一个实例，然后从外界（自然界或一个施教者）获得该实例的正确分类结果。这一场景可分为两种情
况，一种是学习器在自然界中进行实验（如造一座新桥然后让自然界决定其是否牢固），或在一个施教者指导下学习（提出一座新桥梁的设计，然后让施教者来判断
它是否牢固）。我们这里用查询（query）来代表学习器建立的这个实例，然后由外界来对它分类。
再次考虑图2-3中所示的从EnjoySport的4个
样例中学习到的变型空间。这时学习器怎样能提出一个较好的查询？一般情况下怎样采取一种好的查询策略？显然学习器应试图在当前变型空间中选择假设，以进一
步划分该空间。因此，需要选择的实例需满足：它能被变型空间中一些假设分类为正例，另一些分类为反例。其中一个这样的实例是：
<Sunny, Warm, Normal, Light, Warm, Same>
注意这一实例满足变型空间的6个假设中的3个。如果施教者将实例划分为正例，变型空间的S边界就需要被泛化。相反，如果施教者划分其为反例，G边界需要被特化。无论哪种情况，机器将能够学到更多的知识，以确定目标概念，并将变型空间缩小到原来的一半。
一般来说，概念学习的最优查询策略，是产生实例以满足当前变型空间中大致半数的假设。如此，变型空间的大小可以在遇到每个新样例时减半，正确的目标概念就可在élog2|VS|ù次实验后得到。这有点象玩“20问”游戏，通过问题的是／否回答逐渐获得问题的最终答案，玩20问游戏的策略是提的问题最好能把候选答案减半。虽然在图2-3的变型空间中，我们可以生成一个实例将其精确地分半。但一般情况下，可能无法构造出这样的精确分半的实例。这样，查询的数目可能会多于é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个假设——实在是一个偏置很大的假设空间！
现在将EnjoySport学习任务重新定义为一种无偏的形式。方法是定义一个新的假设空间H´，它能表示实例的每一个子集，也就是把H´对应到X的幂集。定义H´的一种办法是，允许使用前面的假设的任意析取、合取和否定式。例如目标概念“Sky=Sunny 或Sky=Cloudy”可被描述为：
<Sunny,
?, ?, ?, ?, ?> ∨ <Cloudy, ?, ?, ?, ?,
?>
给定这样的假设空间，我们就可以安全地使用候选消除算法，而不必担心无法表达目标概念。然而，虽然这个假设空间排除了表达能力的问题，它又产生了一个新的、同样困难的问题：概念学习算法将完全无法从训练样例中泛化！其原因如下，假定我们提供了3个正例（x1，x2，x3）以及两个反例（x4，x5）给学习器。这时，变型空间的S边界包含的假设正好是三个正例的析取：
S: { (x1∨x2∨x3) }
因为这是能覆盖3个正例的最特殊假设。相似地，G边界将由那些刚好能排除掉反例的那些假设组成。
G: {Ø (x4∨x5)}
问题在于，这一非常具有表达力的假设表示方法中，S边界总是简单的所有正例析取式，G边界总是所有反例的析取的否定式。这样能够由S和G无歧义地分类的，只有已见到的训练样例本身。要想获得单个的目标概念，就必须提供X中所有的实例作为训练样例。
看起来避免这一问题的方法可以使用此部分学习的变型空间，然后如2.6.3 节中那样由变型空间的所有成员投票。不幸的是