三个空间

对应于函数$y=h(x)$的三个字母$x,y,h$，机器学习中也有三个对称的东西，称为三个空间：输入空间$\mathcal{X}$、输出空间$\mathcal{Y}$以及假设空间$\mathcal{H}$

我们从宏观上、抽象的角度整理一下相关概念。

图1-4-1 三个空间的关系的上半部分即是前述的通过训练集学习出一个模型$h^{\ast }$，以解决我们的实际问题。 我们再看下半部分。

在中学我们学过函数，回忆函数的三要素：定义域、值域以及映射关系。 在这里定义域与值域称为输入空间与输出空间，映射关系称为假设（hypothesis），它以预测器的候选者身份出现（故为假设），通常以hypothesis的首字母$h$来代表假设。

现在我们假定输入空间$\mathcal{X}$与输出空间$\mathcal{Y}$已经给定，让映射关系$h$变化，借“上帝”之力，收集在某种约束（如算法）下所有可能的映射关系$h$，形成一个函数（假设）集合，称为假设空间$\mathcal{H}$。 注意：此时并没有训练集干扰“上帝”的收集。

输出空间$\mathcal{Y}$有时很小，小到只有两个元素 { a , b } \{ a,b \} {a,b}，这时，假设空间$\mathcal{H}$中的任一假设$h$把输入空间$\mathcal{X}$一分为二（一部分映射到$a$，另一部分映射到$b$），这就是机器学习研究较多的“二分类”问题。 前面已将这两个元素数值化为 Y = { − 1 , + 1 } \mathcal{Y}=\{-1,+1 \} Y={−1,+1}或 Y = { 0 , 1 } \mathcal{Y}=\{0,1 \} Y={0,1}。

现在我们有三个空间：输入空间$\mathcal{X}$、输出空间$\mathcal{Y}$以及假设空间$\mathcal{H}$。 故此，我们的任务变为：在假设空间$\mathcal{H}$中寻找合适的假设$h$使之“尽可能”满足训练集的约束。 这里的“尽可能”表示两个方面，一是可能没有满足的解（前述我们讨论过它与解方程组的区别），二是由于算法能力或时间成本等原因，我们找不到实际的最优解时，退而求其次，总会“尽力”得到一个解$h^{\ast }$（这也常常称为算法给出的最优解，实际可能是次优解）。

反之，也可能约束不够，使得满足训练集的解有多个，即存在一个与训练集一致的“假设集合”，称之为“版本空间”，它包含了不同版本的解，此时，再根据“偏好”得到一个满意的解$h^{\ast }$。

“假设空间”是不考虑样例集约束的所有可能情况，加上样例集的约束则缩小为“版本空间”，再加上偏好则唯一选出一个“模型”（模型实例）。

（1）为了更容易地理解【西瓜书图1.1】假设空间，我们作如下说明：

• 每个结点表示好瓜的一个“假设”（不考虑样例集的约束）；
• 通配符“$\ast$”表示可在取值范内取任意值。 根结点的值全为“$\ast$”，表示任何情况下都是好瓜（瓜贩拍着胸脯说，这些瓜都是好瓜，这当然是一个“假设”。 ）；叶子结点没有“$\ast$”，表示在这种具体取值情况下为好瓜（这里要理解成：当所有属性取具体值时，样本被“唯一”确定，没有泛化的余地，受例子的局限性没有很好地体现这一点，我们结点表示的是“这只西瓜”是好西瓜，而现实中是“这样的西瓜”是好西瓜，例如：由于“大小”没有作为属性，故属性相同大小不同的西瓜是“这样的西瓜”（可视为重复样本））。 这些结点都属于“假设空间”。
• 箭头表示泛化关系，即从下往上泛化，从上往下具体化；
  \item 这棵树共有$4^3$个结点，这是有好瓜的各种可能情况$4^3$，再考虑好瓜为空集的情况，故“假设空间”的大小为$4^3+1$。 为什么其“假设空间”这么小呢？这是由于我们将西瓜简化了：它只有三个属性，每个属性只有三个值（加上通配符，则每个属性可取四个值）。 另一方面，我们看到它以属性作为指数，当属性增加时，“假设空间”将以指数级增长，故“假设空间”通常会非常大，如，有$d$个属性，每个属性有$k$个值，则“假设空间”的大小为$(k+1{)}^d+1$。
  若严格按“二分类”，则“假设空间”的大小为$4^3-1$，减1是表示根结点应该去掉，因它说所有的瓜都是好瓜（没有坏瓜），不满足“二分类”的要求，好瓜为空集也不在计算之列。

（2）为了更容易地理解【西瓜书图1.2】版本空间，我们作如下说明：

• 假设空间是棵树，样例集中若有一个反例，则否定了该树（被剪掉）；
• 剪叶子：对照样例集，对假设空间树的叶子逐一进行处理，矛盾的叶子（叶子说此瓜为好瓜，样例说此瓜为坏瓜）被剪掉；
• 缩子树：若某子树完整（没有被剪掉某部分），则该子树“缩”为一个结点（子树的根），相当于剪枝，如，编号为1和2的两样例对应的叶子被剪掉；
• 上述过程后，得到一个“残缺的树”，该树中同层可能有相同的结点，合并这些结点，则树变成了“非树”，故版本空间不是树形结构。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：1-3 对简化模型数学化
下一篇：1-5 没有免费的午餐（NFL）的证明