人工智能:理论、算法与系统|第 5 课
无限假设类与 VC 维:连续参数的模型为什么仍能泛化?
2026 年 10 月 24 日|第 1 周第 5 课|约 18 分钟
核心问题:昨天的 Hoeffding + Union Bound 要求候选模型个数 M 有限。可线性分类器的参数是连续实数,模型数量无限大。难道它就不可能获得泛化保证?
今天的学习目标:理解 Shattering(打散)的严格量词;手算阈值、区间分类器的增长函数与 VC 维;推导 Sauer–Shelah 的关键递归思想;把有限 VC 维接到统一收敛及 ERM 风险界;辨析这些理论在神经网络与 Benchmark 调参中的边界。
一、为什么昨天的 M 不能直接取无穷大?
设 D={(X_i,Y_i)}_{i=1}^n 为 i.i.d. 样本,Y_i∈{0,1};二分类假设类 H 的成员 h:X→{0,1},使用 0-1 损失。定义
[ R(h)=\Pr(h(X)\ne Y),\qquad \widehat R_D(h)=\frac1n\sum_{i=1}^{n}\mathbf 1[h(X_i)\ne Y_i]. ]
| 昨天我们对预先确定的有限类 | H | =M 证明:以至少 1−δ 的概率, |
[ \sup_{h\in H}|R(h)-\widehat R_D(h)| \le\sqrt{\frac{\ln(2M/\delta)}{2n}}. ]
现在考虑阈值分类器 (h_t(x)=\mathbf1[x\ge t]),其中 (t\in\mathbb R)。参数 t 有无穷多种取值;如果粗暴地令 M=∞,上面的界就无法使用。然而,对固定的有限样本而言,移动阈值并不能随意改变标签:它至多跨过有限个点。由此得到新思路:
不要数模型参数能取多少值,而要数模型在有限样本上能产生多少种不同的预测模式。
这是一条经典统计学习理论路线,不是关于大模型泛化的新研究结论。
二、Shattering:容量的定义必须看清量词
给定 m 个互异输入 (S=(x_1,\ldots,x_m)),定义 H 在 S 上能够实现的标签集合:
[ H|_S={(h(x_1),\ldots,h(x_m)):h\in H}. ]
如果它等于 ({0,1}^m),也就是所有 (2^m) 种标签都可以实现,就称 H 打散(shatter)了 S。
[ \boxed{\mathrm{VCdim}(H)=\sup{m:\exists\,|S|=m,\ |H|_S|=2^m}.} ]
两个量词不要搞反:证明 VC≥d,只需找到一组 d 个点可被打散;证明 VC≤d,则要证明任意 d+1 个点都无法被打散。有限 VC 维不等于“任意这么多点都能打散”。
例 1:单侧阈值分类器
在实数轴上取三个有序点 (x_1<x_2<x_3)。移动阈值 t,只能依次出现:
t > x3 : 0 0 0
x2 < t ≤ x3 : 0 0 1
x1 < t ≤ x2 : 0 1 1
t ≤ x1 : 1 1 1
绝不可能出现模式 (1,0,1),甚至任意两个有序点都不能出现 (1,0)。但任意一个点可以被标记为 0 或 1。因此阈值类的 VC 维为 1。
例 2:实数轴区间分类器
令 (h_{a,b}(x)=\mathbf1[a\le x\le b])。对两个不同点,我们可以只圈左点、只圈右点、一起圈住或都不圈住,所以能够打散两个点。
对任意 (x_1<x_2<x_3),如果区间包含首尾,就必然包含中间点。因此模式 (1,0,1) 不可能出现。于是它的 VC 维为 2。
关键观察: 两个模型类都有无限多组实数参数,却只有很小的 VC 维。这说明“参数连续”与“能够对任意数据乱贴标签”不是一回事。
三、增长函数:把直觉变成能计算的数
定义 Growth Function(增长函数):
[ \Pi_H(m)=\max_{|S|=m}|H|_S|. ]
显然 (\Pi_H(m)\le 2^m)。当 (\Pi_H(m)=2^m),说明存在可打散的 m 点集。
阈值类: 对 m 个有序互异点,阈值只能放在 m+1 个切分位置,因此
[ \boxed{\Pi_{\mathrm{threshold}}(m)=m+1.} ]
区间类: 正标签只能形成连续的一段。长度为 k 的连续段有 m−k+1 种位置;另有一个全 0 模式,故
[ \boxed{\Pi_{\mathrm{interval}}(m) =1+\sum_{k=1}^{m}(m-k+1) =1+\frac{m(m+1)}2.} ]
例如 m=4:任意标记有 (2^4=16) 种,单侧阈值只能做出 5 种,区间能做出 11 种。
| m | 所有二元标记 (2^m) | 阈值 (m+1) | 区间 (1+m(m+1)/2) |
|---|---|---|---|
| 2 | 4 | 3 | 4 |
| 3 | 8 | 4 | 7 |
| 4 | 16 | 5 | 11 |
| 6 | 64 | 7 | 22 |
这张表呈现出指数增长与低次多项式增长的差异。
flowchart TD
A["连续参数的假设类 H"] --> B["限制在 m 个固定输入上"]
B --> C["只数不同的 0/1 预测向量"]
C --> D["增长函数 Π_H(m)"]
D --> E["能否实现全部 2^m 种?"]
E --> F["VC 维:最大可打散规模"]
F --> G["Sauer–Shelah:有限 VC 维 ⇒ 多项式增长上界"]
G --> H["对 i.i.d. 0-1 损失建立统一收敛"]
四、Sauer–Shelah:为何增长从指数受限为多项式?
设 (\mathrm{VCdim}(H)=d<\infty)。经典 Sauer–Shelah 引理给出:
[ \boxed{\Pi_H(m)\le\sum_{j=0}^{d}\binom mj.}\tag{1} ]
当 (m\ge d\ge1) 时还可放宽为:
[ \boxed{\Pi_H(m)\le\left(\frac{em}{d}\right)^d.}\tag{2} ]
因此对于固定的 d,标签模式最多按 (O(m^d)) 增长,而不是 (2^m)。
为什么会出现二项式之和?看证明的递归结构。
从 m 个点的集合 S 中拿掉最后一个点 x,余下 S′ 有 m−1 个点。记 R 为 H 在 S′ 上可实现的标签模式;记 B⊆R 为那些对 x 标 0 与标 1 都能扩展实现的模式。
那么,S 上的模式数恰好满足:
[ |H|_S|=|R|+|B|. ]
原因:R 中每个模式至少有一种扩展;B 中每个模式再多出另一种扩展。
R 的 VC 维不超过 d。更关键的是,B 的 VC 维不超过 d−1:若 B 能打散 S′ 中 d 个点,那么每种 d 点标记都能在 x 上同时扩展为 0 和 1,原 H 就能打散 d+1 个点,矛盾。
所以,归纳地记 (G(m,d)=\sum_{j=0}^{d}\binom mj),有
[ |H|_S| \le G(m-1,d)+G(m-1,d-1) =G(m,d), ]
最后一步正是 Pascal 恒等式 (\binom mj=\binom{m-1}j+\binom{m-1}{j-1})。连同 m=0 或 d=0 的边界情况,完成归纳证明。
这段推导的核心不是记组合数公式,而是:新增一个样本点带来的额外标记,必须消耗一层可打散能力。
五、无限类如何得到统一收敛?
这里有一个容易犯的错误:不能看见“在训练样本上只有 Π_H(n) 种模式”,就直接把昨天的有限类 Union Bound 中的 M 替换成 Π_H(n)。因为这些模式依赖随机样本本身。
正确的经典路线是:
- 引入独立的 Ghost Sample(幽灵样本)D′,将总体风险偏差与两组经验风险之差联系起来,这一步称为对称化。
- 条件于合并后的 2n 个样本,利用随机交换与浓缩不等式。
- 在这 2n 个点上,H 的不同 0-1 错误向量数不超过 (\Pi_H(2n)):对于固定标签,错误向量只是预测向量逐位异或标签。
- 这时才对有限模式使用 Union Bound。
一种经典且常数较保守的 VC 不等式是:
[ \boxed{ \Pr\left( \sup_{h\in H}|R(h)-\widehat R_D(h)|>\epsilon \right) \le 8\Pi_H(2n)e^{-n\epsilon^2/32}. }\tag{3} ]
需满足 i.i.d. 二分类、0-1 损失及适当可测性条件。这里给出标准不等式与证明思路,不把对称化中技术性的概率步骤伪装成已完整展开的初等推导。
结合式 (2),当 (2n\ge d\ge1),使式 (3) 的右端不超过 δ,可以选择:
[ \boxed{ \epsilon_{n,d,\delta} =\sqrt{\frac{32}{n} \left[d\ln\left(\frac{2en}{d}\right)+\ln\left(\frac8\delta\right)\right]}. }\tag{4} ]
| 于是以至少 (1-\delta) 的概率,对所有 (h\in H),都有 ( | R(h)-\widehat R_D(h) | \le\epsilon_{n,d,\delta})。 |
注意它是上界,甚至可能大于 1、因而在小样本下没有实用约束力;不能把它当成真实误差的预测值。
进一步得到 ERM 风险保证
令 (\widehat h) 是经验风险最小模型,(h^*) 是 H 内总体风险最小模型(假设它存在)。在统一事件上:
[
\begin{aligned}
R(\widehat h)
&\le\widehat R_D(\widehat h)+\epsilon
&\le\widehat R_D(h^)+\epsilon
&\le R(h^)+2\epsilon.
\end{aligned}
]
所以:
[ \boxed{R(\widehat h)-R(h^*)\le2\epsilon_{n,d,\delta}.}\tag{5} ]
相比昨天用 (\ln M),今天用 VC 维 d 控制有限样本上的行为复杂度。有限 VC 维带来分布无关的统一收敛保证,即使假设类本身无限大。
不要混淆保证对象: 式 (5) 只保证靠近H 类内最优,并不保证达到 Bayes 最优。一个过于简单的 H 即使很好泛化,也可能严重欠拟合。
六、系统与现代 AI 中如何理解这个理论?
| 场景 | VC 理论能解释的部分 | 不能直接推出的结论 |
|---|---|---|
| 阈值/区间分类 | 无限连续参数仍可能有低组合容量 | 所有连续参数模型都低容量 |
| 线性二分类 | 仿射半空间在 (\mathbb R^p) 的 VC 维为 (p+1) | 参数量和 VC 维对任何架构都一一相等 |
| 深度网络 | 模型类容量、样本量会影响分布无关风险上界 | 仅凭 VC 维就能精确预测大模型测试性能 |
| 反复调 Benchmark | 数据依赖的选择会破坏简单固定候选集分析 | 有有限候选个数就自动免疫评测过拟合 |
复杂神经网络往往还涉及优化算法的隐式偏置、显式正则化、预训练数据结构及分布假设。研究中常用 Rademacher Complexity、稳定性、范数界等更细工具;VC 理论不是现代大模型泛化现象的完整解释。
一个反例:能记住训练集不等于可泛化
设输入空间连续,模型类允许给任何有限点集任意赋值,即具备无限 VC 维。它可以做到训练样本零错误,但对于从未出现过的新样本,单凭这个事实没有分布无关的低风险保证。
反过来,某个无限 VC 类也可能在特定分布、结构性归纳偏置或特定学习算法下表现很好。“无法套用当前上界”不等于“证明一定无法学习”。
最后重申损失的前提:今天分析的是 0-1 损失。交叉熵 (-\ln p_\theta(y\mid x)) 可以无界;不能不加有界性或尾部假设就照搬式 (3)。
七、易错点快速自检
误区一: VC=d 意味着任意 d 个点都能打散。实际是存在某组 d 点。
误区二: 无限参数一定导致 VC=∞。阈值分类器直接构成反例。
误区三: 看到 Π_H(n) 就能直接替换有限类 Union Bound。错误;需要处理模式与随机样本之间的依赖,对称化不可省略。
误区四: 有统一收敛保证就保证没有欠拟合。错误;风险界只比较类内最优。
八、四级自测|100 分
首次授课不公布标准答案。 Lv1—Lv3 支持客观评分,Lv4 依据推导和设计评估;题目考查不同能力,不是简单换数字。
Lv1|概念辨析:打散与 VC 维(15 分|约 2 分钟)
考点: 打散的量词与连续模型类
对连续参数的二分类假设类 H,以下哪项理解最严谨?
A. 只要 H 含无穷多个分类器,其 VC 维必定无穷大。
B. VC(H)=d 意味着任意 d 个互异输入都能够被 H 打散。
C. VC(H)=d 意味着存在某组 d 个互异输入可实现全部 2^d 种标记,但任意 d+1 个互异输入均不能被打散;有限 VC 维可用于 i.i.d. 0-1 损失的统一收敛分析。
D. VC 维在所有模型中都严格等于可训练实数参数的数量。
可选中立提示:分别检查“存在一组”和“任意一组”的量词,以及参数取值个数与标签组合个数的区别。
Lv2|数值计数:区间分类器的增长函数(20 分|约 3 分钟)
考点: 增长函数的组合计数
考虑实数轴上的区间分类器 H={h_a,b=1[a≤x≤b] : a≤b}。对 5 个互异且按大小排列的实数输入,H 最多能实现多少种不同的二元标签向量?计入全 0 模式。仅填一个整数,并写出你的计数过程。
可选中立提示:思考一个区间与有序样本相交时,哪些标记形状可以出现;不要遗漏空交集。
Lv3|多步推理:Sauer 上界与模型选择边界(25 分|约 5 分钟)
考点: Sauer 上界、数据依赖和类内最优
设二分类器使用 0-1 损失。下列哪些说法正确?(多选)
A. 若 VC(H)=2,则 H 在任意 6 个互异输入上至多产生 22 种标记模式。
B. 观察同一验证集标签后任意设计候选类,仍可只以最后保留的模型个数 M 直接套用预先固定有限类的 Hoeffding–Union Bound。
C. 实数轴区间分类器虽有无穷多组端点,但其 VC 维有限,因此在 i.i.d. 0-1 损失设定下可以建立分布无关的统一收敛界。
D. 有限 VC 维保证 ERM 的总体风险必然等于所有可测分类器中的 Bayes 最优风险,不存在近似误差。
可选中立提示:先区分组合计数、数据依赖的模型选择与假设类的近似能力,再应用相应条件。
Lv4|综合证明与实验设计(40 分|约 12 分钟)
考点: VC 证明、概率上界及评测设计
| 设二分类损失为 0-1 Loss,训练样本 i.i.d.。A(10 分):分别证明阈值分类器 H_t={1[x≥t]} 的 VC 维为 1、区间分类器 H_I={1[a≤x≤b]} 的 VC 维为 2;上下界都需证明。B(10 分):对 m 个互异有序点推导两类的增长函数 Π_t(m)、Π_I(m),并在 m=4 时与 2^4 比较。C(12 分):已知 VC(H)=d≥1、2n≥d,且可使用 Sauer–Shelah 上界 Π_H(2n)≤(2en/d)^d,以及 VC 概率不等式 Pr(sup_h | R(h)-Rhat(h) | >ε)≤8Π_H(2n)exp(-nε²/32)。推导置信度至少 1-δ 的统一风险界与 ERM 超额风险界,解释为何不能直接把随机数据选出的 h 当固定 h。D(8 分):解释为什么不能将上述 0-1 损失界不加条件用于无界交叉熵;设计训练、验证、最终测试的分离流程,并指出反复看验证集的风险。 |
可选中立提示:证明容量时要分别给出能打散的构造和无法打散的标记;概率界可先令右端不超过 δ,再使用 ERM 的两次风险比较。
九、总结与下一讲
本课知识链:
[ \boxed{\text{打散}\;\Rightarrow\;\mathrm{VCdim}(H)=d \;\Rightarrow\;\Pi_H(m)\le\sum_{j=0}^d\binom mj \;\Rightarrow\;\text{统一收敛与 ERM 风险界}.} ]
最重要的直觉是:泛化复杂度不取决于“参数可取多少个实数”,而与模型在有限数据上能做出多少种相互区别的行为有关。 这个直觉在统计学习理论里可以严格化,但要持续检查 i.i.d.、损失有界、假设类以及模型选择过程的假设。
下一课(2026-10-25,第 6 课): 算法稳定性与正则化泛化——除了限制假设类,能否直接分析“换掉一个训练样本”会让学到的模型改变多少?第 7 课进行第一周系统复盘。
经典参考: Shalev-Shwartz & Ben-David《Understanding Machine Learning》第 6 章;Vapnik–Chervonenkis 的统一收敛理论;Sauer–Shelah 引理。延伸阅读:VC 维与 Sauer–Shelah 讲义;增长函数与组合证明。
请按 Lv1—Lv4 提交答案。评分满分 100:80 分及以上按原计划继续;60–79 分针对性补练;低于 60 分回顾打散与统一收敛后再练。课程编号不因测评成绩而改变。