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)。写成

$${\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 维把无限假设类压缩成有限样本上的可控组合数量的方式。递推式把“最后一个点是否能自由翻转”拆成维度不变和维度下降两支，恰好复现 Pascal 三角。

例子与边界

实线上阈值的 VC 维为 $1$；在 $m$ 个有序点上只能得到

$$m+1=(\genfrac{}{}{0ex}{}{m}{0})+(\genfrac{}{}{0ex}{}{m}{1})$$

种标注，达到组合上界等号。实线区间的 VC 维为 $2$，其正点必须是一段连续索引，因而标注数为

$$1+\frac{m(m+1)}{2}=(\genfrac{}{}{0ex}{}{m}{0})+(\genfrac{}{}{0ex}{}{m}{1})+(\genfrac{}{}{0ex}{}{m}{2}).$$

例如 $m=4$ 时共有 $11=1+4+6$ 种区间标注。两个类都达到 Sauer–Shelah 上界；原因是它们的限制族形成最大类，而不只是因为分别使用一个或两个端点参数。

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

推论与应用

把组合和代入 VC 一致收敛证明，就能对无限二元类在二重样本上的所有标注模式取并，并得到维度依赖的泛化界。引理负责把类缩成有限模式，概率集中和对称化则承担另外两步。

多类的 Natarajan 维、实值类的伪维也有相应增长控制，但需要各自的迹定义。Sauer–Shelah 的二元结论不能只靠编码输出直接迁移。

参考资料

• 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.