最少约定搜索

19.1.3 最少约定搜索

当前最佳假设方法即使在数据不充分而对选择没有把握的时候，也必须选择某个特定假设作为最佳猜测，因而会产生回溯。替代地，我们可以只保存与目前已有的所有数据保持一致的全部假设。每个新的实例要么不产生任何影响，要么去掉某些假设。回忆一下原始假设空间可以被视为一个析取语句：

H1∨H2∨H3∨…∨Hn

当发现各种假设与实例不一致时，这个析取式会收缩，只保留那些没有被排除的假设。设原始假设空间的确包含那个正确答案，那么经过缩减后的析取式一定仍然包含正确答案——因为只有那些不正确的假设被去除了。保留下来的假设集合被称为变型空间（version space），相应的学习算法（如图19.3所示）被称为变型空间学习算法（也叫做候选消除算法）。

图19.3 变型空间学习算法。算法找到V的一个子集，与examples保持一致

这种学习方法的一个重要特性是它是增量学习的：从不需要回头重新检查那些已处理过的实例。无论如何，所有保留下来的假设都保证与这些实例一致。这也是一个最少约定算法，因为它不进行任意的选择（与第十一章中的偏序规划方法相比较）。但是它也有一个明显的问题。我们已经说过假设空间是规模巨大的，因此我们如何能够把这个巨大的析取式写下来？

下面的这个简单类比非常有帮助。如何表示1和2之间的所有实数？毕竟，它们的数量是无限的！答案是使用一个区间表示法，指明这个集合的边界：[1, 2]。这种方法之所以有效是因为实数上存在一个序。

我们在假设空间上也有一个序，即一般化/特殊化。这是一个偏序关系，即每个边界不是一个点而是一个假设的集合，称为边界集。重要的是我们可以只用两个边界集就表示整个变型空间：一个最一般的边界（G-集）和一个最特殊的边界（S-集）。这两个边界之间的所有假设都保证与实例一致。在我们证明这一点之前，让我们重申一下：

• 当前的变型空间是与到目前为止所有的实例都保持一致的假设的集合。它用 G-集和 S-集表示，每个边界集都是一组假设集。

• S-集中的每个成员都与目前为止所有的观察一致，并且不存在更特殊的一致假设。

• G-集中的每个成员都与目前为止所有的观察一致，并且不存在更一般的一致假设。

我们希望初始的变型空间（在看不到任何实例之前）能够表示所有可能的假设。这时G-集被设为包含True（也就是包含所有实例的假设），S-集被设为包含False（外延为空的假设）。

图19.4显示了变型空间的边界集表示法的一般结构。为了说明这个表示是充分的，我们需要下面两个属性：

图19.4 包括所有与样例一致的假设的变型空间

① 每个一致假设（除了边界集中的假设以外）都比G-集中的某个成员更特殊，也比S-集中的某个成员更一般。（也就是说，没有“漏网之鱼”。）这能够从S和G的定义中直接得出。如果存在一个遗漏的h，那么它一定比G中的任何成员都更特殊，在这种情况下它属于G；或者比S中的任何元素都更一般，在这种情况下它属于S。

② 每个比G-集中的某个成员更特殊并且比S-集合中的某个成员更一般的假设都是一个一致假设（即在边界之间没有“漏洞”）。在S和G之间的任何h一定拒绝那些被G中的每个成员都拒绝的反例（因为h更特殊），也一定接受被S中的任何成员接受的正例（因为h更一般）。因此， h一定符合所有的实例，从而不可能是不一致的。图19.5表示了这样的情形：没有已知实例在S之外而在G之内，因此缝隙中的所有假设一定都是一致的。

图19.5 G和S中的成员的外延。在两个边界集之间没有已知实例

因此我们已经说明了如果能够保持S和G符合它们的定义，那么它们就提供了一个变型空间的令人满意的表示。剩下的唯一问题就是对一个新实例，如何更新S和G（函数VERSION-SPACE-UPDATE的工作）。最初这看起来似乎很复杂，但是根据定义，并辅以图19.4，重新构造算法就不是太困难了。

我们需要考虑S-集和G-集中的成员Si和Gi。对于每个成员，新的实例可能是一个错误正例或者错误反例。

① Si的错误正例：意味着Si太一般化了，但是根据定义不存在Si的一致的特殊化，所以我们把它从S-集中去掉。

② Si的错误反例：意味着Si太特殊化了，所以我们把它替换成所有对其进行的直接一般化，倘若它们比G中的某成员更特殊。

③ Gi的错误正例：意味着 Gi太一般化了，所以我们把它替换成所有对其进行的直接特殊化，倘若它们比S中的某成员更一般。

④ Gi的错误反例：意味着Gi太特殊化了，但是根据定义不存在Gi的一致的一般化，所以我们把它从G-集中去掉。

我们持续对每个新的实例执行这些操作，直到下列3种情况之一发生：

① 在变型空间中刚好剩下一个概念，这种情况下我们将它作为唯一假设返回；

② 变型空间坍塌——S 或者 G 变为空集，表明对训练集合而言，没有一致的假设。这与决策树算法的简单版本中的失败情况相同。

③ 当我们用完全部实例后，在变型空间中还剩下多个假设。这意味着变型空间表示了假设的一个析取式。对于任何新的实例，如果所有的析取子句意见都相同，则我们可以返回它们对该实例的分类；如果不同，则一种可能方法是采用多数投票。

我们把在餐馆问题上应用VERSION-SPACE-LEARNING算法留作一道习题。

变型空间方法有几个主要缺点：

• 如果域中含有噪声或者在精确分类中有不充分的属性，则变型空间总是要坍塌的。

• 如果我们允许假设空间的无限析取式，那么S-集将总是包含一个单一的最特殊假设，即到目前为止见到过的正例描述的一个析取式。类似地，G-集将只包含反例描述的析取式的非。

• 对于某些假设空间来说，即使存在高效的学习算法，S-集和G-集中的元素个数仍然可能按照属性个数的指数级增长。

到目前为止，还没有找到完全成功的方案解决噪声问题。析取式的问题可以通过允许有限形式的析取式或者包括使用更一般谓词的一般化层次结构来解决。例如，取代析取式 WaitEstimate(x, 30-60)∨WaitEstimate(x,＞60)，我们可以使用一个简单的文字LongWait(x)。一般化和特殊化操作的集合可以很容易地进行扩展以处理该问题。

单纯的变型空间算法首先被用于Meta-DENDRAL系统中，是为学习规则以预测质谱仪中分子如何分裂成小块而设计的（Buchanan和Mitchell，1978）。Meta-DENDARL能够生成规则，它们在分析化学的一本授权出版的期刊中是全新的——第一次由一个计算机程序生成的真正的科学知识。这一算法还用于优雅的 LEX 系统中（Mitchell 等人，1983），该系统能够通过研究自身的成功和失败而学习求解符号积分问题。虽然主要由于噪声问题，使得变型空间方法可能在大多数现实世界的学习问题中并不实用，但是它们提供了很多对假设空间的逻辑结构的深入了解。