版本空间是什么？与所有训练样本都一致的假设集合

版本空间（Version Space）是机器学习中概念学习的一个基本概念，指的是在所有可能的假设中，那些与全部训练样本都相一致的假设所组成的集合。这一概念由 Tom Mitchell 在 1977 年提出。

从假设空间说起

在概念学习中，我们要根据一些正例和反例，学习出一个概念的描述。所有可能的描述构成了一个“假设空间”。比如要学习“好西瓜”的概念，每个西瓜用色泽、根蒂、敲声三个属性来描述，每个属性有若干种取值，一个假设就是对这三个属性取值的某种规定，比如“色泽青绿、根蒂蜷缩、敲声任意”。所有这样的规定组合在一起，就是假设空间。学习的过程，可以看作在假设空间中搜索与训练数据相符的假设。

一个假设如果能把所有的正例都判断为正、所有的反例都判断为反，就称它与训练数据“一致”。通常，与训练数据一致的假设不止一个，可能有很多个。这些假设组成的集合，就是版本空间。它代表了在现有数据下，所有“说得通”的概念描述。

用两个边界来表示

版本空间中可能包含大量的假设，逐一列出它们会很麻烦。Mitchell 发现，可以利用假设之间“一般”与“特殊”的关系，用两个边界来紧凑地表示整个版本空间：特殊边界 S，由版本空间中最特殊的那些假设组成，它们恰好覆盖所有的正例，再具体一点就会漏掉某个正例；一般边界 G，由版本空间中最一般的那些假设组成，它们尽可能地宽泛，再宽泛一点就会错误地包含某个反例。版本空间中的所有假设，都位于这两个边界之间：比 S 中的某个假设更一般，同时比 G 中的某个假设更特殊。

候选消除算法

基于这种表示，Mitchell 提出了候选消除算法来学习版本空间。算法开始时，S 被设为最特殊的假设，也就是什么都不包含；G 被设为最一般的假设，也就是什么都包含。然后依次处理每一个训练样本：遇到一个正例时，如果 S 中的某个假设没有覆盖它，就把这个假设进行最小程度的泛化，使它能够覆盖这个正例，同时从 G 中删除那些不能覆盖这个正例的假设；遇到一个反例时，如果 G 中的某个假设错误地覆盖了它，就把这个假设进行最小程度的特化，使它排除这个反例，同时从 S 中删除那些错误地覆盖了这个反例的假设。随着样本的增多，S 和 G 不断地相互靠拢，版本空间不断地缩小。如果最终 S 和 G 重合为同一个假设，就找到了唯一正确的概念。

版本空间的启示

版本空间的概念揭示了一个重要的问题：在训练数据有限的情况下，与数据一致的假设往往有很多个，它们对于新的、没见过的样本可能给出不同的预测。仅凭训练数据，无法判断哪一个是对的。因此，学习算法必须具有某种“归纳偏好”，才能从版本空间中选出一个假设，比如偏好最简单的假设，这就是奥卡姆剃刀原则。另一种做法是保留整个版本空间，在预测时让其中的所有假设进行投票，这与多释原则的思想一致。此外，版本空间还可以用来进行主动学习：选择那些让版本空间中的假设意见分歧最大的样本去询问标签，能最有效地缩小版本空间。

候选消除算法的局限在于：它假设训练数据中没有任何错误，一个标错的样本就可能让版本空间变成空集；而且假设空间必须包含正确的概念。因此，它在实际中很少直接使用，但它对于理解机器学习中假设、搜索和归纳偏好等基本概念很有帮助。