当前最佳假设搜索

19.1.2 当前最佳假设搜索

当前最佳假设搜索背后的思想是维护一个简单的假设，并根据出现的新实例对其进行调整，以维持一致性。基本算法由John Stuart Mill（1843）描述，也可能出现得甚至更早。

设我们有某个假设比如Hr，该假设到目前为止一直表现不错。只要每个新的实例都具有一致性，我们什么都不用做。然后出现了一个错误反例X13。我们该做什么？图19.1（a）示意性地以区域的形式显示了Hr，在这个矩形内的所有内容都是包含于Hr的外延中。目前为止实际看到的实例表示为“+”或者“−”。我们看到Hr正确地把所有实例分类为WillWait的正例或者反例。在图19.1（b）中，一个新的实例（圆圈）是错误反例：假设认为该实例应该是反例，但是事实上它是正例。必须扩大假设的外延以包含该实例。这被称为一般化；一个可能的一般化如图19.1（c）中所示。在图19.1（d）中，我们看到一个错误正例：假设认为新的实例（圆圈）应该是正例，但是实际上是反例。因此假设的外延就应该被缩小，以排除该实例。这被称为特殊化；图19.1（e）中我们看到对假设的一个可能的特殊化。假设之间的“更一般”和“更特殊”关系提供了假设空间上的逻辑结构，这使得高效的搜索成为可能。

图19.1 （a）一个具有一致性的假设。（b）一个错误反例。（c）假设被一般化。（d）一个错误正例。（e）假设被特殊化

我们现在可以详细描述CURRENT-BEST-LEARNING（当前最佳学习）算法了，如图19.2所示。注意到每次我们考虑对假设进行一般化或特殊化的时候，我们必须检查与其它实例的一致性，因为任意地扩大/缩小外延可能会包括/排除以前见到过的反例/正例。

图19.2 当前最佳假设学习算法。该算法搜索一个一致性假设，并当无法找到一致的特殊化或一般化的时候回溯

我们把一般化和特殊化定义为改变假设的外延的运算。现在我们需要决定它们如何被作为句法运算而实现，这些运算对与假设相关联的候选定义加以修改，从而能够被一个程序所执行。要完成这些工作，首先注意到一般化和特殊化也都是假设之间的逻辑关系。如果假设 H1（其定义为 C1）是假设H2（其定义为C2）的一个一般化，那么我们一定有：

于是为了构造H2的一个一般化，我们只需要找到一个逻辑上被C2所蕴涵的定义C1。这很容易做到。例如，如果C2(x)是Alternate(x)∧Patrons(x, Some)，那么一个可能的一般化就是C1(x) ≡ Patrons(x, Some)。这被称为丢弃条件。直观地，它生成一个更弱的定义，并且因此允许一个更大的正例集合。还有很多其它的一般化操作，依赖于要进行处理的语言。相似地，我们可以通过对候选定义增加额外条件或者从析取式定义中去掉一些析取子句来特殊化一个假设。让我们看看在餐馆这个例子中这是如何工作的，使用图18.3中的数据。

• 第1个实例X1是正例。Alternate(X1)为真，因此令初始假设为

H1:　∀ x　WillWait(x)⇔Alternate(x)

• 第 2 个实例 X2是反例。H1预测其为正例，所以这是一个错误正例。因此，我们需要特殊化H1。这可以通过增加一个排除X2的额外条件来实现。一个可能方式为

H2:　∀ x　WillWait(x)⇔Alternate(x)∧Patrons(x,Some)

• 第 3 个实例 X3是正例。H2预测其为反例，所以这是一个错误反例。因此，我们需要一般化H2。我们去掉Alternate条件，得到

H3:　∀ x　WillWait(x)⇔Patrons(x,Some)

• 第 4 个实例 X4是正例。H3预测其为反例，所以这是一个错误反例。因此，我们需要一般化H3。我们不能丢弃Patrons条件，因为那将产生一个全包含假设，与X2不一致。一个可能方法是增加一个析取子句：

H4:　∀ x　WillWait(x)⇔Patrons(x,Some)∨(Patrons(s,full)∧Fri/Sat(x))

这个假设已经开始看起来很有道理了。显然，还有其它一些与前4个实例一致的可能假设；这里给出其中两个：

H4'：∀ x　WillWait(x)⇔¬WaitEstimate(x,30-60)

H4"：∀ x　WillWait(x)⇔Patrons(x,Some)∨(Patrons(s,full)∧WaitEstimate(x,10-30))

CURRENT-BEST-LEARNING算法是非确定性地描述的，因为在任何一点上都可能有几个可用的特殊化或者一般化。所做出的选择不一定能够得到最简单的假设，并可能导致一个不可恢复的情形，没有简单修改能够使假设与所有的数据保持一致。在这种情况下，程序必须回溯到上一个选择点。

CURRENT-BEST-LEARNING 算法及其各种变形从 Patrick Winston（1975）的“弧学习”（“arch-learning”）程序开始，已经用于很多机器学习系统中。然而在大量实例和很大空间的情况下，一些困难出现了：

① 每次进行修改都要把以前所有的实例再检查一遍，代价非常大；

② 搜索过程可能涉及大量的回溯。如同我们在第十八章中看到的，假设空间可以达到双重指数空间大小。