增长函数与打散系数

所有二元函数类有 $\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$ 都要求切分方向反复改变，无法实现。

实线区间类给出另一项完整计数。对 $m$ 个有序点，一个区间的正例要么为空，要么是一段连续的索引区间。非空连续段由左右端点 $1\le i\le j\le m$ 唯一决定，共 $m(m+1)/2$ 个；再加全零标注，得到

$m=3$ 时共有七种标注，唯一缺少的是 $101$。这个计算既展示迹如何计数，也预告区间类 VC 维为 $2$。

增长函数按最不利点配置取最大值，不描述某个特定分布下常见的标注数量。参数维数相同的类也可能具有不同打散行为；多类与实值函数则必须更换维度概念，不能把输出编码成若干 bit 后机械套用二元定义。

增长函数进入泛化证明时，真正数的是样本上的限制，而不是整个无穷类。对二重样本进行对称化后，只需对至多 ${\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 }$。

在多类学习中，Natarajan 增长函数承担类似角色；在实值学习中，伪维和 fat-shattering 以阈值或间隔记录有限样本行为。共同思想都是先计算样本上可区分的预测模式，再把计数送入集中或复杂度界。