【机器学习】假设空间与版本空间

1.假设空间

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

2.版本空间

  与训练集一致的“假设集合”。

3.具体实例

  我们通过一个例子来看一下假设空间和版本空间的区别。
  假设我们的训练集如下所示：

  这里我们的假设空间由形如“（色泽=？）^（根蒂=?）^（敲声=？）”的可能取值所形成的假设组成。
  色泽有“青绿”和“乌黑”两种取值，还需考虑无论色泽取什么值都合适的情况，用通配符（*）表示。色泽属性共三种取值；
  根蒂有“蜷缩”、“硬挺”和“稍蜷”三种取值，同理再加通配符（*）表示，根蒂属性共四种取值；
  敲声有“浊响”、“清脆”和“沉闷”三种取值，同理再加通配符（*）表示，敲声属性共四种取值；
  还有一种假设组成——可能"好瓜”这个概念就不成立，我们用∅表示这种假设。
  那么，所对应的假设组成的个数为：3x4x4+1=49. 即所对应的假设空间的规模大小为49。
  假设空间如下所示：
（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） ∅

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

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

  删除假设空间中的（49）

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

根据样本（（色泽=青绿）^（根蒂=蜷缩）^（敲声=浊响））——>好瓜，

  删除（2）-（18）、（20）-（27）、（29）- （33）、（35）-（39）、（41）-（42）、（44）-（45）、（47）

根据样本（（色泽=乌黑）^（根蒂=蜷缩）^（敲声=浊响））——>好瓜，

  在上一步的基础上再删除（1）、（28）、（34）、（46）

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

根据样本（（色泽=青绿）^（根蒂=硬挺）^（敲声=清脆））——>不是好瓜，

  在上一步的基础上再删除（48）

根据样本（（色泽=乌黑）^（根蒂=稍蜷）^（敲声=沉闷））——>不是好瓜，

  剩余假设空间中已无满足此条件可被删的假设

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

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

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

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