实例和假设

19.1.1 实例和假设

回忆一下第十八章中的餐馆学习问题：学习一条用来决定是否等待座位的规则。实例用属性描述，诸如Alternate（改变），bar（酒吧），Fri/Sat（周五/周六）等。在逻辑表示中，实例是被逻辑语句描述的对象；属性是一元谓词。让我们把第i个实例一般地称为Xi。例如，图18.3中的第一个实例可以用下面的语句来描述：

Alternate(X1)∧¬Bar(X1)∧¬Fri/Sat(X1) ∧ Hungry(X1)∧…

我们用符号Di(Xi)来表示对Xi的描述，其中Di可以是带有一个简单参数的任何逻辑表达式。对象的分类由下面的语句给出：

WillWait (X1)

如果是正例，我们用一般符号Q(Xi)表示，反例则用¬Q(Xi)表示。于是整个训练集就是所有描述和分类语句的合取式。

在逻辑表示中，归纳学习的目的就是为目标谓词Q寻找一个等价的逻辑表达式，使我们能够使用Q对实例进行正确的分类。每个假设都提出一个这样的表达式，我们称之为目标谓词的候选定义。用Ci表示候选定义，每个假设Hi就是一条形如∀ x Q(x) ⇔ Ci(x)的语句。例如，当且仅当满足有一个分支指向真值的时候，决策树断言对于一个对象而言该目标谓词为真。因此，图18.6表达了如下的逻辑定义（我们称之为Hr，以便将来引用）：

每个假设都会预测某个实例集合——即那些满足其候选定义的实例——作为目标谓词的实例。这个集合称为谓词的外延。两个外延不同的假设因此在逻辑上是不一致的，由于它们对至少一个实例的预测不同。如果具有相同的外延，它们在逻辑上就是等价的。

假设空间H是所有假设构成的集合{H1, … , H2}，设计学习算法就是为了满足这些假设。例如， DECISION-TREE-LEARNING（决策树学习）算法能够满足按照所提供的属性定义的任何决策树假设；因此它的假设空间就由所有这些决策树组成。大致上，学习算法相信这些假设之一是正确的；也就是说，它相信这条语句：

当出现一个实例的时候，那些与实例不一致的假设就可以被排除掉。让我们更仔细地检查一下这个一致性的概念。显然，如果假设Hi与整个训练集一致，那么它必须与每个实例都一致。那么与某个实例不一致意味着什么？可能发生两种情况之一：

• 如果该假设认为一个实例应该是反例而事实上是正例，则这个实例是该假设的错误反例（false negative——医学术语中为“假阴性”——译者注）。例如，具有如下描述的新实例X13：

Patrons(X13,Full)∧Wait(X13,0-10)∧¬ Hungry(X13)∧…∧WillWait(X13)

可能成为前面给出的假设Hr的错误反例。从Hr和实例的描述，我们可以推论出从实例得到的WillWait(X13)和从假设预测到的¬ WillWait(X13)。因此假设和实例在逻辑上不一致。

• 如果该假设认为一个实例是正例而事实上是反例，则这个实例是该假设的错误正例[7]（false positive——医学术语中为“假阳性”——译者注）。

如果一个实例是某个假设的错误正例或者错误反例，则该实例和该假设逻辑上相互不一致。设该实例是对事实的一个正确观察，则该假设就可以被排除。逻辑上说，这与推理的归结规则（参见第九章）完全类似，其中假设的析取式对应于子句，而实例对应于可以与该子句中某个文字进行归结的文字。因此，原则上来说，一个普通的逻辑推理系统通过消除一个或者多个假设从实例中进行学习。例如，设实例用语句I1表示，假设空间为H1∨H2∨H3∨H4。那么如果I1与H2和H3不一致，则逻辑推理系统就可以推论得到新的假设空间H1∨H4。

因此我们可以把逻辑表示中的归纳学习作为一个逐渐消除与实例不一致的假设，从而缩小可能范围的过程。由于假设空间通常很大（在一阶逻辑的情况下甚至是无限大的），我们不建议人们尝试去构造一个使用基于归结定理证明的学习系统和一个穷举的假设空间。相反地，我们将描述两种能够用少得多的努力找到逻辑上具有一致性的假设的方法。