Sauer–Shelah 引理

形式陈述 ​

对二元假设类 $\mathcal{H}$，令增长函数 ${\mathrm{\Pi }}_{\mathcal{H}}(m)$ 表示它在任意 $m$ 个点上能实现的最大标注数。若VC 维理路VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。 $d=\mathrm{VCdim}(\mathcal{H})<m$，则用二项式系数理路二项式系数Binomial coefficientn 元集合的 k 元子集数，记作 C(n,k)。写成

当 $1\le d\le m$ 时，进一步有

若 $d\ge m$，正确的平凡上界是 $2^m$；$d=0$ 时组合和为 $1$，不能把含 $d$ 的粗界机械代入。

递推证明 ​

固定一个 $m$ 点集合并挑出点 $x_m$。把在前 $m-1$ 点上的标注分成两类：只可由一种 $x_m$ 标签延伸的模式，以及两种标签都能延伸的模式。后一类在前 $m-1$ 点上形成的迹类 VC 维至多 $d-1$；否则再加 $x_m$ 就能打散 $d+1$ 个点。因此最大迹数 $G(m,d)$ 满足

结合 $G(m,0)=1$ 与 $G(m,m)=2^m$，用 Pascal 恒等式归纳得到 $G(m,d)\le \sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})$。

第二个界需要分情况。若 $1\le d\le m/2$，对 $0<x\le 1$ 用二项式定理理路二项式定理Binomial theorem(x+y)^n 按二项式系数展开为各次幂项之和。得到

；这里第二个不等号使用 $i\le d$ 和 $x\le 1$。取 $x=d/(m-d)$ 后，

最后一步使用 $(1+d/(m-d){)}^{m-d}\le e^d$。若 $m/2<d\le m$，上述 $x$ 已大于 $1$，不能继续使用同一中间不等式；此时改用

后一式可令 $r=d/m\in (1/2,1]$，验证 $r\log \left(e/r\right)\ge \log 2$。这样两个参数区间都覆盖到，而没有把只对 $x\le 1$ 有效的步骤越界使用。