泛化：训练好 ≠ 真的好

学习的目标是泛化——在未见数据上表现好。期望风险与经验风险之差就是泛化误差，理论给出其上界。

VC 维与泛化界

VC 维度量假设空间 $\mathcal H$ 的复杂度（能“打散”的最大点数）。以高概率：
$R(h)\le \hat R(h)+O!\left(\sqrt{\frac{\mathrm{VC}(\mathcal H),\log n}{n}}\right)$
模型越复杂（VC 维越大）、样本越少，泛化间隙越大——这是过拟合的理论刻画。

PAC 学习与 Rademacher 复杂度

**PAC（可能近似正确）**框架定义“用多少样本能以高概率学到近似正确的模型”。Rademacher 复杂度用模型拟合随机噪声的能力给出更紧的、数据相关的泛化界。

例题

例　平面上的线性分类器 VC 维为 $3$（能打散任意 3 点、但不能打散全部 4 点的异或排列）。这解释了为何线性模型无法解决 XOR，需要更高容量的模型。

应用

学习理论指导模型选择与正则化：用验证集估计泛化、用 $\ell_1/\ell_2$ 正则限制容量、用偏差–方差权衡解释欠拟合/过拟合。它是“为什么深度网络能泛化”这一前沿问题的出发点。