2.8

本章中指出如果给定一个无偏的假设空间（即实例的幂集），学习器将发现每一个未观察的实例将刚好与变型空间中半数的成员匹配，而不论已经过了怎样的训练样例。证明这一结论。确切地讲，证明对于任意实例空间 X，任意训练样例集 D 及任意不包含在 D 中的实例 $x \in X$，如果 $H$ 是 $X$ 的幂集，那么在 $VS_{H,D}$ 中有恰好半数的假设将 x 划分为正例，另外半数划分为反例。

解答： (来自 DeepSeek)

证明：

设实例空间为 $X$，训练集 $D$ 包含 $n$ 个实例且不包含 $x$，假设空间 $H = 2^X$（即所有可能的子集）。变型空间 $VS_{H,D}$ 包含所有与 $D$ 一致的假设。对于任意 $x \notin D$，需证明 $VS_{H,D}$ 中恰有半数假设将 $x$ 标记为正例。

核心思想：自由分类的对称性¶

由于 $x$ 未出现在 $D$ 中，假设对 $x$ 的分类不受 $D$ 约束，即无论一个假设将 $x$ 分为正例还是反例，都不会违反 $D$ 中出现的每一个训练样例。具体步骤如下：

1. 构造双射映射
   对任意假设 $h \in \text{VS}_{H,D}$，定义其对应假设 $h' = h \oplus \{x\}$，即：
   $h' = \begin{cases} h \cup \{x\} & \text{若 } x \notin h \\ h \setminus \{x\} & \text{若 } x \in h \end{cases}$ 由于 $x \notin D$，改变 $x$ 的标记不影响 $h$ 与 $D$ 的一致性，故 $h' \in \text{VS}_{H,D}$。

2. 保持分类一致性
   映射 $h \leftrightarrow h'$ 是一一对应的，且每个 $h$ 与其 $h'$ 对 $x$ 的标记相反。因此，$\text{VS}_{H,D}$ 可划分为若干对 $(h, h')$，每对中一个假设标记 $x$ 为正，另一个为反。

3. 数量均等性
   假设总共有 $m$ 个假设满足 $D$，则通过配对关系可知：
   $\text{标记 } x \text{ 为正的假设数} = \text{标记 } x \text{ 为反的假设数} = \frac{m}{2}$

严格数学表述¶

设 $S = \{h \in \text{VS}_{H,D} \mid x \in h\}$，$T = \{h \in \text{VS}_{H,D} \mid x \notin h\}$，则：

• 存在双射 $f: S \to T$ 使得 $f(h) = h \setminus \{x\}$
• 因此 $|S| = |T|$，即两类假设数量相等。

结论：在无偏假设空间下，未观测实例 $x$ 在变型空间中的正反标记假设数严格各占半数。

举例¶

改进版水果案例解析（含符号标注）

符号对应说明¶

具体分析¶

步骤1：定义合法猜想（$VS_{H,D}$）¶

假设机器人脑中合法的猜想必须满足：

• 包含🍎（因为 D 中🍎是正例）
• 不包含🪨（因为 D 中🪨是反例）
• 对🍊和🍌无限制（因为 D 未提及它们）

示例假设：

步骤2：观察未提及的🍊橘子（x）¶

所有合法猜想对🍊的分类有两种可能：

• 包含🍊（如 h₂, h₄）
• 不包含🍊（如 h₁, h₃）

关键发现：

• 对任意包含🍊的假设，存在一个"镜像假设"：
  h₂ = {🍎, 🍊} 的镜像是 h₁ = {🍎}
h₄ = {🍎, 🍊, 🍌} 的镜像是 h₃ = {🍎, 🍌}
• 镜像假设的唯一区别是是否包含🍊，且都满足 D 的约束。

步骤3：严格的数量均等¶

• 总合法假设数：在 X 的幂集 H 中，满足 D 的假设数量为 4（见示例）。
• 分类统计：
  • 包含🍊的假设数：2（h₂, h₄）
  • 不包含🍊的假设数：2（h₁, h₃）
• 比例：50% vs 50%

数学本质：
对于任意未观察的 x（如🍊），假设空间 H 中满足 D 的猜想可通过"翻转 x 的标记"一一配对，因此正反分类数量必然相等。

可视化总结¶

变型空间 $VS_{H,D}$：

   ┌───────────────┬───────────────┐
   │  包含🍊的假设   │ 不包含🍊的假设  │
   ├───────────────┼───────────────┤
   │    {🍎, 🍊}    │     {🍎}      │
   │ {🍎, 🍊, 🍌}   │   {🍎, 🍌}    │
   └───────────────┴───────────────┘