摘要：假设空间；版本空间；

参考：

（1）《机器学习》周志华著，清华大学出版社

（2）周志华老师《机器学习》假设空间和版本空间概念辨析 - 知乎 (zhihu.com)

（3）版本空间_百度百科 (baidu.com)

（4）假设空间_百度百科 (baidu.com)

3.假设空间

3.1科学推理的两大基本手段

归纳（induction）和演绎（deduction）是科学推理的两大基本手段。

归纳：特殊到一般的“泛化”（generalization）过程，即从具体的事实归结出一般性规律。

归纳学习有广义和狭义之分。广义的归纳学习指从样例中学习；狭义的归纳学习则要求从训练数据中得到概念（concept），因此亦称“概念学习”或“概念形成”。

概念学习中最基本的是布尔概念学习，即对“是”“不是”这样的克表示为0/1布尔值的目标概念的学习。

演绎：从一般到特殊的“特化”（specialization）过程，即从基础原理推演出具体情况。

在前文机器学习——绪论（一） - 简书中提到，实际应用中，训练集即可理解为[特殊]，测试集即可理解为[一般]。我们学习的目的是“泛化”，即通过对训练集中样例的学习以获得对没见过的样例进行判断的能力。如果仅仅把训练集中的样例“记住”（又称“机械学习”或“死记硬背式学习”），今后遇到一摸一样的样例当然可以判断，可是对于不在训练集中的样例却无能为力。

3.2什么是假设空间

回到高中数学，在函数相关知识的学习中，我们知道，函数三要素分别是①定义域②对应关系③值域。知其二求其一是常见问题，在之前的学习中我们已经学习了知①②求③，知②③求①，而机器学习就是一个知①③求②的过程。根据①和③求得的所有②的集合即为“假设空间”。。

百度百科中对于假设空间有如下定义：

机器学习中可能的函数构成的空间称为“假设空间”。

监督学习（supervised learning）的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间(hypothesis space)。假设空间的确定意味着学习范围的确定。

3.3什么是版本空间

假设空间中的每一个元素对应了一个假设（hypothesis），也就是学习得到的模型，同样就是上文所说的②函数。但是在一般情况下，假设空间中的元素是非常庞大的，而我们的训练样本总是有限的，因此可能有多个假设与训练集一致，即存在着一个与训练集一致的“假设集合”，我们称之为“版本空间”（version space）。

百度百科中对于版本空间有如下定义：

版本空间(version space)是概念学习中与已知数据集一致的所有假设(hypothesis)的子集集合。

3.4示例

现假设有西瓜数据集如下：

表1.1 西瓜数据集（摘自周志华《机器学习》）

该案例是典型的有监督学习中的二分类问题。训练集中共有四个元组，即四个样例，每个样例由三个属性组成（“色泽”， “根蒂”，“敲声”），即该案例中的样本空间是三维的。每个样本带有一个标记信息，取值为{“是”， “否”}。设每个属性有 3 种可能取值，即“色泽：青绿、乌黑、浅白”，“根蒂：蜷缩、硬挺、稍蜷”，“敲声：浊响、清脆、沉闷”，于是样本空间 的大小 (元素的个数) 为 3 × 3 × 3 = 27，即：{“青绿、蜷缩、浊响”，“青绿、蜷缩、清脆”， ……}

图 1. 西瓜分类问题的属性空间（转自知乎用户ttigong）

“假设”也就是学习得到的模型，根据狭义的归纳学习的定义可知，该案例中我们只需学得一个“概念”，即什么样的瓜是好瓜就得到了我们的模型，也就是“假设”。结合训练集，每个样例有三个属性，三个属性所有的取值已明确，那么这里令假设空间是由形如“（色泽=？）（根蒂=？）（敲声=？）好瓜”的可能取值所形成的假设组成。（更一般的情况是考虑形如（AB）（CD）的析合范式。）

假设的表示一旦确定，假设空间及其规模大小就确定了。

求假设空间的方法有很多，可以参考周志华老师《机器学习》假设空间和版本空间概念辨析 - 知乎 (zhihu.com)，该文中给出了很不错的求解方法，这里说一下周志华老师书里提到的方法。

对于每一个属性来说都有三种确定的取值，但注意也许有些属性无论取什么值都合适，用通配符“*”来表示，也就是说每一个属性可能有四种取值（例如“色泽”可能的取值有“青绿”、“乌黑”、“浅白”、“*”），那么可构成的假设共有4 × 4 × 4 = 64种。还要注意有可能“好瓜”这个东西根本就不存在，也就是说没有一个模型能算出样例为“好瓜”，那么这种情况下假设空间为空，也就是。综上，该案例的假设空间规模大小为65，即共有65个假设。按照从上往下逐渐特殊的原则画出如下图示：

图2：西瓜问题的假设空间（摘自周志华《机器学习》）

我们可以把学习过程看作一个在假设空间中进行搜索的过程，搜索目标是找到与训练集“匹配”（fit）的假设，即能够将训练集中的瓜判断正确的假设。将这些假设全部找出即可求得该案例的版本空间。

可以用很多策略对这个假设空间进行搜索，例如从顶向下、从一般到特殊，或是自底向上、从特殊到一般，搜索过程中可以不断删除与正例不一致的假设、和（或）与反例一致的假设。（这些方法可选择同时进行或只选择其中一种）最终将会获得与训练集一致（即对所有训练样本都能够进行正确判断）的假设，这些假设的集合构成了“版本空间”。

图3：西瓜问题的版本空间（摘自周志华《机器学习》）

3.5样本空间、假设空间、版本空间

样本空间是属性张成的空间，以西瓜分类问题为例，样本空间中的每一个元素是一个西瓜。

假设空间是假设的集合，也就是“函数”的集合。以西瓜分类问题为例，假设空间中的每一个元素是形如“（色泽 = ？）（根蒂 = ？）（敲声 = ？）好瓜”的假设。注意假设空间并不一定无限大，有些文中提到“假设空间无限大为了方便讨论选取……作为假设空间”等类似内容个人理解是错误的。

版本空间是假设空间的子集合。其中的每一个元素都是一个假设，并且假设与训练集中的数据保持一致。