1. 概念

• 假设空间： 监督学习（supervised learning）的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间(hypothesis space)。 我们也可以将学习过程看作一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集"匹配"的假设，即能够将训练集中的瓜判断正确的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。

• 版本空间： 与训练集一致的“假设集合”。

2. 求假设空间（针对西瓜分类分题进行讲解）

属性： 3 个属性

色泽：（青绿，乌黑，浅白）

根蒂：（蜷缩，硬挺，稍蜷）

敲声：（浊响，清脆，沉闷）

假设空间： 属性所有可能取值组成的可能的样本

• 色泽有“青绿”和“乌黑”两种取值，还需考虑无论色泽取什么值都合适的情况，用通配符（*）表示。色泽属性共 3 种取值；

• 根蒂有“蜷缩”、“硬挺”和“稍蜷”三种取值，同理再加通配符（*）表示，根蒂属性共 4 种取值；

• 敲声有“浊响”、“清脆”和“沉闷”三种取值，同理再加通配符（*）表示，敲声属性共 4 种取值；

• 还有一种假设组成——可能"好瓜”这个概念就不成立，我们用 ∅ 表示这种假设。

那么，所对应的假设组成的个数为：3 x 4 x 4 + 1 = 49. 即表 1.1 所对应的假设空间的规模大小为 49. 其中：

• 具体假设： 2x3x3=18 种
• 一个通配符：2x3+3x3+2x3=21种
• 两个通配符：2+3+3=8 种
• 三个通配符：1种
• 概念不存在：1种

（1）（色泽=青绿）^（根蒂=蜷缩）^（敲声=浊响）

（2）（色泽=青绿）^（根蒂=蜷缩）^（敲声=清脆）

（3）（色泽=青绿）^（根蒂=蜷缩）^（敲声=沉闷）


（4）（色泽=青绿）^（根蒂=硬挺）^（敲声=浊响）

（5）（色泽=青绿）^（根蒂=硬挺）^（敲声=清脆）

（6）（色泽=青绿）^（根蒂=硬挺）^（敲声=沉闷）


（7）（色泽=青绿）^（根蒂=稍蜷）^（敲声=浊响）

（8）（色泽=青绿）^（根蒂=稍蜷）^（敲声=清脆）

（9）（色泽=青绿）^（根蒂=稍蜷）^（敲声=沉闷）


（10）（色泽=乌黑）^（根蒂=蜷缩）^（敲声=浊响）

（11）（色泽=乌黑）^（根蒂=蜷缩）^（敲声=清脆）

（12）（色泽=乌黑）^（根蒂=蜷缩）^（敲声=沉闷）

（13）（色泽=乌黑）^（根蒂=硬挺）^（敲声=浊响）

（14）（色泽=乌黑）^（根蒂=硬挺）^（敲声=清脆）

（15）（色泽=乌黑）^（根蒂=硬挺）^（敲声=沉闷）

（16）（色泽=乌黑）^（根蒂=稍蜷）^（敲声=浊响）

（17）（色泽=乌黑）^（根蒂=稍蜷）^（敲声=清脆）

（18）（色泽=乌黑）^（根蒂=稍蜷）^（敲声=沉闷）



（19）（色泽=*）^（根蒂=蜷缩）^（敲声=浊响）

（20）（色泽=*）^（根蒂=蜷缩）^（敲声=清脆）

（21）（色泽=*）^（根蒂=蜷缩）^（敲声=沉闷）

（22）（色泽=*）^（根蒂=硬挺）^（敲声=浊响）

（23）（色泽=*）^（根蒂=硬挺）^（敲声=清脆）

（24）（色泽=*）^（根蒂=硬挺）^（敲声=沉闷）

（25）（色泽=*）^（根蒂=稍蜷）^（敲声=浊响）

（26）（色泽=*）^（根蒂=稍蜷）^（敲声=清脆）

（27）（色泽=*）^（根蒂=稍蜷）^（敲声=沉闷）


（28）（色泽=青绿）^（根蒂=*）^（敲声=浊响）

（29）（色泽=青绿）^（根蒂=*）^（敲声=清脆）

（30）（色泽=青绿）^（根蒂=*）^（敲声=沉闷）

（31）（色泽=乌黑）^（根蒂=*）^（敲声=浊响）

（32）（色泽=乌黑）^（根蒂=*）^（敲声=清脆）

（33）（色泽=乌黑）^（根蒂=*）^（敲声=沉闷）

（34）（色泽=青绿）^（根蒂=蜷缩）^（敲声=*）

（35）（色泽=青绿）^（根蒂=硬挺）^（敲声=*）

（36）（色泽=青绿）^（根蒂=稍蜷）^（敲声=*）

（37）（色泽=乌黑）^（根蒂=蜷缩）^（敲声=*）

（38）（色泽=乌黑）^（根蒂=硬挺）^（敲声=*）

（39）（色泽=乌黑）^（根蒂=稍蜷）^（敲声=*）



（40）（色泽=*）^（根蒂=*）^（敲声=浊响）

（41）（色泽=*）^（根蒂=*）^（敲声=清脆）

（42）（色泽=*）^（根蒂=*）^（敲声=沉闷）

（43）（色泽=*）^（根蒂=蜷缩）^（敲声=*）

（44）（色泽=*）^（根蒂=硬挺）^（敲声=*）

（45）（色泽=*）^（根蒂=稍蜷）^（敲声=*）

（46）（色泽=青绿）^（根蒂=*）^（敲声=*）

（47）（色泽=乌黑）^（根蒂=*）^（敲声=*）



（48）（色泽=*）^（根蒂=*）^（敲声=*）

（49） ∅

2. 求版本空间（version space）

• 版本空间为与训练集一致的“假设集合”。

• 在此西瓜例中，我们的学习目标为 “好瓜”，所以我们要通过训练集（表1.1），从假设空间中删除与正例不一致的假设、和（或）与反例一致的假设，最终将会获得与训练集一致（即对所有训练样本能够进行正确判断）的假设，这就是我们学得的结果，学得的假设集合即为要求的版本空间。步骤如下：

1） 根据表1.1的样本 1，我们知 “好瓜” 的概念是成立的，所以先删除 ∅ 的假设

• 删除假设空间中的（49）

2） 删除与正例（好瓜）不一致的假设

• 根据样本（色泽=青绿）^（根蒂=蜷缩）^（敲声=浊响）$\to$ 好瓜
  删除（2）-（18）、（20）-（27）、（29）- （33）、（35）-（39）、（41）-（42）、（44）-（45）、（47）

• 根据样本（色泽=乌黑）^（根蒂=蜷缩）^（敲声=浊响）$\to$ 好瓜，
  在上一步的基础上再删除（1）、（28）、（34）、（46）

3）删除与反例（不是好瓜）一致的假设

• 根据样本（色泽=青绿）^（根蒂=硬挺）^（敲声=清脆）$\to$ 不是好瓜
  在上一步的基础上再删除（48）

• 根据样本（色泽=乌黑）^（根蒂=稍蜷）^（敲声=沉闷）$\to$ 不是好瓜，
  剩余假设空间中已无满足此条件可被删的假设。

此时，只剩余（19）、（40）、（43）与训练集一致

（19）（色泽=*）^（根蒂=蜷缩）^（敲声=浊响）

（40）（色泽=*） ^（根蒂=*）^（敲声=浊响）

（43）（色泽=*）^（根蒂=蜷缩）^（敲声=*）

注： 此图敲声 "清脆”，改为 “浊响”

References

[1] 机器学习（周志华）：版本空间的理解和求法(详细版)

[2] 《机器学习》中的假设空间和版本空间