Sauer–Shelah 引理

父节点：vc-dimension 前置：learning-theory —— H；以及 vc-dimension —— 打散（shattering）、VCdim。

这条引理把"有限 VC"变成一个可用的界：一个 VC 有限的假设类在 n 个点上只能实现多项式个数的标注（labeling），而不是 2ⁿ 个。它是 fundamental-theorem 的引擎。

把

h 看作一个集合，以及限制 h ∩ S 把每个假设等同于它的+ 区域——即它标注为 + 的输入集合：

$$h \;\equiv\; \{\, x \in X : h(x) = + \,\}.$$

在这一等同下，h ∩ S 就是一次普通的集合求交，挑出 S 中被标为 + 的点：

$$h \cap S \;=\; \{\, s \in S : h(s) = + \,\} \;\subseteq\; S.$$

因为标签是二元的，这个子集本身就是那个标注：s ∈ h∩S 意味着 s 是 +，s ∉ h∩S 意味着 −。所以 S 的一个子集和 S 的一个标注是同一件事，不同的 h ∩ S = 不同的标注。

增长函数（growth function）

设 S ⊆ X 是输入空间中的一个 n 点集合。把 H 限制到 S 上得到 $H|_S = \{ h \cap S : h \in H \}$——即 H 在 S 上产生的所有不同标注（把每个 h 看作它的 + 点集合）。增长函数是这一计数在所有 n 点集合上取到的最大值：

$$\Pi_H(n) \;=\; \max_{S \subseteq X,\ |S| = n} \bigl| H|_S \bigr|.$$

总有 $\Pi_H(n) \le 2^n$，等号成立当且仅当存在 n 个点被打散（shattered）。

它数的是不同的标注模式，和预测是否正确毫无关系（这里根本没有目标可言）。

从定义出发计算

Π_threshold(n) 回忆 hₜ ≡ [t, ∞)，所以 hₜ ∩ S = {pᵢ ∈ S : pᵢ ≥ t}——即 t 右边的那些点。

n = 2，S = {p₁, p₂}（p₁<p₂）。让 t 在数轴上扫过，逐段读出交集：

t 所在位置	hₜ ∩ S	标注
t ≤ p₁	{p₁, p₂}	(+,+)
p₁ < t ≤ p₂	{p₂}	(−,+)
t > p₂	∅	(−,−)

3 个不同的交集（{p₁}，即 (+,−)，永远不会出现）→ |H|_S| = 3。对任意 2 个点都是如此，所以 Π(2) = 3。

一般的 n，p₁ < … < pₙ。因为 hₜ ∩ S 总是那些 ≥ t 的点，它始终是一个后缀 {pᵢ, …, pₙ}。当 t 扫过 ℝ 时，它落在 n+1 个间隙之一（p₁ 之前、相邻两点之间、或 pₙ 之后），而这个后缀每次缩短一个点：

$$\{p_1,\dots,p_n\} \to \{p_2,\dots,p_n\} \to \cdots \to \{p_n\} \to \varnothing.$$

这就是 n+1 个不同的交集，所以 |H|_S| = n+1。对任何 n 个点的选取都是如此，因此最大值是

$$\Pi_{\text{threshold}}(n) = \max_{|S|=n} |H|_S| = n+1.$$

无穷多个阈值，在 n 个点上却只有 n+1 种行为——线性的 O(n)，与 VC = 1 相符。（验证：Sauer–Shelah 给出 C(n,0)+C(n,1) = 1 + n。）一个无限的假设类坍缩为一个多项式计数，这正是增长函数所度量的东西。

Sauer–Shelah

若 VCdim(H) = d，则对所有 n

$$\Pi_H(n) \;\le\; \sum_{i=0}^{d} \binom{n}{i} \;\le\; \left(\frac{en}{d}\right)^{d} = O(n^{d}) \quad (n \ge d).$$

所以在超过 VC 维之后，增长函数从指数级 2ⁿ 切换为多项式级 nᵈ——这一跳变正是"VC 有限 ⟹ 可学习"成立的全部原因。

证明（对 n 归纳）

记 $\Phi(n,d) = \sum_{i=0}^{d}\binom{n}{i}$；我们要证明对每个满足 |S| = n 的 S，都有 $|H|_S| \le \Phi(n,d)$，其中 $H|_S = \{\, h \cap S : h \in H \,\}$。

基础情形。 n = 0：只有一种（空）标注，且 $\Phi(0,d) = 1$。d = 0：H 打散不了任何单个点，所以所有假设在每个点上都一致，从而 $|H|_S| = 1 = \Phi(n,0)$。

归纳步。 固定一点 x ∈ S，令 $S' = S \setminus \{x\}$。按每个 S' 的标注如何延伸到 x 上，把 $H|_S$ 拆分为：

• $H' := H|_{S'}$ —— S' 上的标注（S 上两个在 S' 上一致的标注会坍缩为同一个）；
• $H''$ —— 那些在 $H|_S$ 中以 x 的两种取值都出现过的 S' 标注。

数一数延伸方式即得 $|H|_S| = |H'| + |H''|$（每个 S' 标注有一种或两种延伸方式；有两种延伸方式的那些恰好就是 $H''$）。

• H' 是 H 的一个限制，所以 VCdim(H') ≤ d，由归纳假设得 $|H'| \le \Phi(n-1,d)$。
• VCdim(H'') ≤ d − 1：若 H'' 打散了某个集合 A ⊆ S'，那么 A 的每个标注都会以 x 的两种取值出现，于是 H 打散了 A ∪ {x}；因此 |A| + 1 ≤ d。由归纳假设得 $|H''| \le \Phi(n-1,d-1)$。

两式相加，$|H|_S| \le \Phi(n-1,d) + \Phi(n-1,d-1) = \Phi(n,d)$——最后一个等号是帕斯卡恒等式（Pascal's identity）$\binom{n-1}{i} + \binom{n-1}{i-1} = \binom{n}{i}$。∎

由此，界 $\Phi(n,d) \le (en/d)^d$ 便可通过一个标准的二项式估计得到。