统计学习基本定理

父节点：vc-dimension 前置：learning-theory — H、err、ε、δ、m；以及 sauer-shelah。

PAC 可学习 ⟺ VC 维有限

一个二元假设类 H PAC-learnable，当且仅当 VCdim(H) = d < ∞。而且经验风险最小化（在样本上挑选错误数最少的 h ∈ H）就能达到这一点，其样本复杂度为
$m(\varepsilon,\delta) \;=\; \Theta\!\left(\frac{d + \log(1/\delta)}{\varepsilon^{2}}\right)$
这是不可知（agnostic）情形下的复杂度（在可实现（realizable）情形下则为 $\Theta\big((d\log(1/\varepsilon) + \log(1/\delta))/\varepsilon\big)$ ）。

两个方向。

(⇐) VC 维有限 ⟹ 可学习——一致收敛

整件事的关键在于界定泛化间隙（generalization gap） $\sup_{h\in H} |\hat{err}(h) - err(h)|$ （其中 $\hat{err}$ 是样本上的错误率）。如果这个间隙对所有 h 同时都 ≤ ε，那么经验最小化器就落在 H 中最优者的 2ε 范围之内。

对称化（幽灵样本，symmetrization / ghost sample）。 把 m 个点的样本，跟另一个独立的、同样有 m 个点的"幽灵"样本相比较；间隙的大小由 H 在这 2m 个点整体上的行为所控制。
Sauer–Shelah 引理。 在这 2m 个点上，H 最多能实现 $\Pi_H(2m) \le (2em/d)^d$ 种不同的标注方式——这是多项式的，而不是 $2^{2m}$ 。所以尽管 H 是无限的，这里真正起作用的"有效假设"只有多项式那么多。
联合界 + Hoeffding 不等式。 对这有限多种行为中的每一种，Hoeffding 不等式都能界定其经验错误率与真实错误率相差 > ε 的概率；对这 (2em/d)ᵈ 种行为取联合界，得到

\Pr\!\left[\sup_{h\in H} |{\hat{err}}(h) - err(h)| > \varepsilon\right] \;\le\; 4\,\Pi_H(2m)\,e^{-m\varepsilon^{2}/8}.

因为 $\Pi_H(2m)$ 只是 m 的多项式，指数项占了上风：一旦 $m = O\big((d + \log(1/\delta))/\varepsilon^2\big)$ ，这个界就降到了 δ 以下。一致收敛成立 → ERM 能泛化 → 可学习。∎

VC 维唯一登场的地方是第 2 步——正是 d 有限，才让联合界是多项式的，而不是空洞无效的。

(⇒) VC 维无限 ⟹ 不可学习——天下没有免费的午餐

假设 VCdim(H) = ∞。固定任意样本量 m；取一个大小为 2m 的被打散（shattered）的集合，并在其上放置均匀分布。令目标标签是这 2m 个点上的一个均匀随机标注（这是可实现的：H 能打散它们，所以总有某个 h 与之吻合）。

学习器看到 m 个带标签的点；其余 ≥ m 个点未见过。在一个未见过的点上，标签是一枚独立的公平硬币，样本对它没有任何揭示，所以任何学习器在那里出错的概率都是 1/2。未见过的点占了 ≥ 1/2 的质量，所以期望真实错误率 ≥ 1/4——对每一个 m 都成立。没有任何有限样本能把错误率压到 1/4 以下 → 不是 PAC 可学习的。∎

如何理解

d 就是价签：所需样本量随 VCdim(H) 线性增长——这正是 the bias–variance cost 的来处。
d = ∞ 是一堵墙：sin 类（只有一个参数，VC 维却无限）无法被学习，无论用什么算法、给多少数据——这正是"太灵活以至于学不了"的精确边界。