Sauer–Shelah 引理

形式陈述 ​

对二元假设类 $\mathcal{H}$，令增长函数 ${\mathrm{\Pi }}_{\mathcal{H}}(m)$ 表示它在任意 $m$ 个点上能实现的最大标注数。若 $d=\mathrm{VCdim}(\mathcal{H})<m$，则

$${\mathrm{\Pi }}_{\mathcal{H}}(m)\le \sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i}).$$

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

$$\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})\le {\left(\frac{em}{d}\right)}^d.$$

若 $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,d)\le G(m-1,d)+G(m-1,d-1).$$

结合 $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 按二项式系数展开为各次幂项之和。得到

$$(1+x{)}^m\ge \sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})x^i\ge x^d\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})$$

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

$$\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})\le {\left(\frac{m}{d}\right)}^d{\left(\frac{m}{m-d}\right)}^{m-d}\le {\left(\frac{em}{d}\right)}^d,$$

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

$$\sum _{i=0}^d(\genfrac{}{}{0ex}{}{m}{i})\le 2^m\le {\left(\frac{em}{d}\right)}^d.$$

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

概念图像与例子 ​

若 $d$ 固定，类在 $m$ 点上的有效标注数至多是 $m^d$ 量级，而不是所有 $2^m$ 种标注。这正是 VC 维把无限假设类压缩成有限样本上的可控组合数量的方式。实线上阈值的 VC 维为 $1$；在 $m$ 个有序点上只能得到 $m+1=(\genfrac{}{}{0ex}{}{m}{0})+(\genfrac{}{}{0ex}{}{m}{1})$ 种标注，达到等号。

边界与辨析 ​

引理没有说 $|\mathcal{H}|\le 2^d$：类本身可以无限，受控的是它在有限点集上的迹。某些最大类达到组合和等号，所以不附加几何或代数结构时不能普遍降低量级。该引理把VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。接到有限类并集界，但它自身不是概率定理。

参考资料

• Norbert Sauer, On the Density of Families of Sets, JCTA, 1972.
• Saharon Shelah, A Combinatorial Problem; Stability and Order for Models and Theories in Infinitary Languages, 1972.