增长函数与打散系数

定义 ​

对 $\mathcal{H}\subseteq \{0,1{\}}^{\mathcal{X}}$ 与点组 $x_{1:m}$，其限制集合是

$$\mathcal{H}{|}_{x_{1:m}}=\{(h(x_1),\dots ,h(x_m)):h\in \mathcal{H}\}.$$

增长函数

$${\mathrm{\Pi }}_{\mathcal{H}}(m)=\underset{x_1,\dots ,x_m}{max}|\mathcal{H}{|}_{x_{1:m}}|$$

取最有利点配置上的最大标注数。若某个含 $m$ 个互异点的集合实现全部 $2^m$ 种标注，就说它被 $\mathcal{H}$ 打散。重复点不可能获得相反标签，故不增加有效计数。

两个极端 ​

所有二元函数类有 $\mathrm{\Pi }(m)=2^m$。实线单阈值在有序的 $m$ 个点上只能把 0 与 1 切一次，连上两个常量标注，共 $m+1$ 种。虽然阈值参数不可数，其有限样本行为仅线性增长；这正是增长函数比全局 $|\mathcal{H}|$ 更适合无限类的原因。

增长函数不是参数计数。多类输出和实值函数也不能直接套 $2^m$ 的二元打散定义，需要 Natarajan、伪维或其他复杂度。VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。记录增长函数最后还能达到 $2^m$ 的规模，Sauer–Shelah 则把此后的增长压到多项式计数。

以 $m=3$ 的阈值为例，设 $x_1<x_2<x_3$。可实现的标注依次为 $000,001,011,111$，恰有 $4=m+1$ 个；$010$ 或 $101$ 都要求切分方向反复改变，无法实现。若坐标有重复点，要求同一输入取不同标签的模式更不可能出现，所以最大值可在互异点上考察。

增长函数进入泛化证明时，真正数的是样本上的限制，而不是整个无穷类。对二重样本进行对称化后，只需对至多 ${\mathrm{\Pi }}_{\mathcal{H}}(2m)$ 个标注模式控制偏差；若 VC 维为 $d$，Sauer–Shelah 再给 $\mathrm{\Pi }(2m)\le \sum _{i=0}^d(\genfrac{}{}{0ex}{}{2m}{i})$。这条链解释了组合维度如何替代无意义的 $|\mathcal{H}|=\mathrm{\infty }$。

参考资料

• Vapnik, Chervonenkis, 1971.
• Sauer, “On the Density of Families of Sets,” 1972; Shelah, 1972.