先承认两件做不到的事：你只看到有限样本，总可能抽到一批极不典型的数据；就算数据典型，也不可能一点不错。Valiant 1984 年的妥协极务实——把「学会」定义成大概率（Probably）做到近似正确（Approximately Correct）。两个宽容度：$\varepsilon$ 允许你错一点点，$\delta$ 允许你运气差一次。
看一个能一路算到底的例子。目标是平面上一个坐标轴对齐的矩形，算法极简：取所有正例的最小外接矩形。它只会画小、不会画大，误差因此全藏在真矩形四条边内侧的窄带里。若某条带的概率质量超过 $\varepsilon/4$，而 $m$ 个样本竟一个都没落进去，这件坏事的概率是 $(1-\varepsilon/4)^m$；四条带用并集界一加，$4e^{-m\varepsilon/4}\le\delta$，解得 $m\ge\frac{4}{\varepsilon}\ln\frac{4}{\delta}$。「学会了」被翻译成了一句关于样本量的算术。
$D$ 是数据背后那个未知的真实分布；$S$ 是从 $D$ 独立抽出的 $m$ 个样本；$\hat h$ 是算法看完 $S$ 后交出的假设；$\mathrm{err}_D$ 是它在真实世界上的错误率。外层的 $\Pr$ 管抽样的运气，内层的 $\varepsilon$ 管精度——两层不确定性各有一个旋钮。可学 = 存在算法，其样本量 $m(\varepsilon,\delta)$ 是 $1/\varepsilon$ 与 $1/\delta$ 的多项式。
它把「学习」这个哲学词变成了能证明的命题，并顺手暴露了代价的结构：$\varepsilon$ 出现在 $1/\varepsilon$ 里，$\delta$ 却只出现在 $\ln(1/\delta)$ 里。精度昂贵，信心便宜——把失败率从 5% 压到 0.001%，样本只需多几倍；把误差减半，样本要翻倍甚至更多。这解释了为什么工程上「多跑几次确认」划算，而「再精确一个数量级」总是很贵。更漂亮的是它分布无关。
PAC 是主动学习、多臂老虎机（Day 54）样本复杂度、差分隐私预算分析的公共语言。Boosting 就诞生于 PAC 里的一个提问：「弱可学（只比抛硬币好一点）是否蕴含强可学？」Schapire 1990 年证明答案是是，AdaBoost 与 XGBoost 都是这个证明的构造性副产品。今天判断一次 A/B 实验需要多少样本，问的仍是同一个 $m(\varepsilon,\delta)$。
怎么衡量一族模型「多强」？别数参数，数它能打散多少个点。给定 $d$ 个点，无论你怎么贴正负标签（共 $2^d$ 种贴法），族里都能找出一个成员完全拟合——这叫打散（shatter）。能打散的最大点数就是 VC 维。
平面上的直线：任取 3 个不共线的点，8 种标签全能用一条直线分开。4 个点呢？摆成正方形、对角同号（即 XOR），任何直线都做不到。所以平面线性分类器的 VC 维恰是 3，$d$ 维则是 $d+1$。
而 $\mathrm{sign}(\sin\theta x)$ 只有一个参数，VC 维却是无穷。参数个数与容量之间没有可靠的换算。
$\mathcal H_{|S}$ 是假设类 $\mathcal H$ 限制在点集 $S$ 上后实际能产生的标签模式集合——两个函数只要在 $S$ 上贴出同样的标签就算同一模式。$|\mathcal H_{|S}|=2^d$ 即「$2^d$ 种模式一个不缺」。
真正的定理是 Sauer–Shelah 引理：若 $\mathrm{VC}(\mathcal H)=d$，则任意 $m$ 个点上的模式数 $\le\sum_{i=0}^{d}\binom{m}{i}=O(m^d)$。一个本可以是 $2^m$ 的量，只要 VC 维有限，就塌成关于 $m$ 的多项式，相变正好发生在 $m=d$。
这是一个纯组合的二分律。人们本以为「复杂度」是连续、渐变、说不清的东西，Sauer–Shelah 却说函数类只有两种命运：要么处处打散（$2^m$，VC 维无穷，学不动），要么被一个整数 $d$ 卡死成 $O(m^d)$，中间地带不存在。更动人的是它被独立发现了三次——极值组合、模型论的稳定性理论（Shelah 的 NIP）、离散几何的 $\varepsilon$-网定理。三群互不通气的人撞上同一堵墙，通常意味着他们摸到的是同一个结构。
SVM 的理论合法性正来自这里：核方法把数据升到无穷维，参数无穷多，但「最大间隔」这一约束让有效 VC 维被 $(R/\gamma)^2$ 控制（$R$ 是数据半径，$\gamma$ 是间隔），与环境维度无关——这是「维数灾难可被几何绕开」的第一个漂亮例证。
训练误差低本身不算证据——你是看过答案之后才挑的这个假设，等于先射箭再画靶。要让训练误差可信，必须保证假设类里每一个成员的训练误差都贴近它的真实误差（这叫一致收敛），这样你事后无论挑中谁都安全。
而「每一个」要付费：类越大，为「事后挑选的自由」交的保险费越高。泛化界因此都长成同一个样子——真实误差 ≤ 拟合得多好 + 从多大的池子里挑的。
以概率 $1-\delta$，对类中所有 $h$ 同时成立。$\widehat{\mathrm{err}}_S$ 是训练误差，$d$ 是 VC 维，$m$ 是样本数。三处细节：外面的平方根来自中心极限——$m$ 个样本估一个均值，误差天然是 $1/\sqrt m$ 量级；$d\log(m/d)$ 正是 Sauer–Shelah 那个多项式取对数后的产物，代表「要同时担保多少个本质不同的假设」；$\log(1/\delta)$ 再次印证信心便宜。关键比值是 $d/m$。
它给了奥卡姆剃刀一个定量版本。「简单的解释更可能正确」两千年来只是审美偏好，这里第一次成为可证的定理：小 $d$ 直接兑换成更紧的保证。Vapnik 又把它变成算法——结构风险最小化：不最小化训练误差，而最小化「训练误差 + 复杂度罚」。你写下的每一个正则项，都是这行不等式的后代。
L2 / L1 正则、决策树剪枝、early stopping、dropout，都可读成在压低有效容量而非拟合能力。更现代的 Rademacher 复杂度换了个度量方式——「这个类能多好地拟合纯随机标签」——它随实际数据分布变化，比 VC 维贴身得多。
经典理论的预测很清楚：参数远多于样本 → 容量爆炸 → 灾难性过拟合。现实却相反。Zhang 等人 2017 年的实验很残酷：把 CIFAR-10 的标签全部随机打乱，网络照样训练到零误差——它的容量确实足以死记硬背一切。可换回真实标签，同一个网络泛化得很好。同一模型类既能记住纯噪声又能学到规律，说明决定命运的不只是容量，还有算法的偏好。
更违反直觉的是双下降：模型规模增大时，测试误差先降后升（经典 U 型），在「恰好能插值」（参数量≈样本量）处冲到峰值，然后继续加大——再次下降，甚至低于第一个谷底。经典理论只看见了曲线的左半边。
核心概念是隐式正则化：在所有能把训练集拟合到零误差的解里，梯度下降不是随机挑一个，而是系统性地偏向某一类。$R$ 就是这个偏好——由优化算法而非损失函数隐含定义的复杂度。这不是空话：可分数据上用梯度下降训练线性分类器，方向可证明地收敛到最大间隔解（正好回到 VC 维那张牌）。深度非线性网络的 $R$ 是什么，至今没人知道——这就是开放问题本身。
这是一场真正的理论危机，而解法不是推翻旧理论，是发现旧理论问错了问题。一致收敛问「整个假设类安不安全」；实际发生的却是「算法只走过假设类的一个极小角落」。对整个类要求安全，自然得到空洞的界。良性过拟合补上另一半：高维空间里，噪声可被吸收进那些几乎不影响预测的方向——过拟合与泛化竟能共存。数学没有失败，只是容量这把尺子太粗；而知道尺子哪里粗，本身就是进展。
这直接改写了实践直觉：为什么「再大一点」常常有益而非有害（scaling law 的理论底色）；为什么在插值区间做模型选择必须靠留出集而非复杂度惩罚；为什么权重衰减、early stopping、数据增强彼此不可替代——它们改变的是算法走向哪个解，不是类里有哪些解。