Fat-shattering 维

定义 ​

设 $F\subseteq {\mathbb{R}}^{\mathcal{X}}$，尺度 $\gamma >0$。点集 $\{x_1,\dots ,x_m\}$ 被 $F$ 在尺度 $\gamma$ fat-shatter，是指存在逐点阈值 $r_1,\dots ,r_m\in \mathbb{R}$，使对每个符号向量 $s\in \{-1,+1{\}}^m$，都能找到 $f_s\in F$ 满足

$$s_i=+1\Rightarrow f_s(x_i)\ge r_i+\gamma ,s_i=-1\Rightarrow f_s(x_i)\le r_i-\gamma$$

对所有 $i$ 同时成立。${\mathrm{fat}}_{\gamma }(F)$ 是可被如此打散的点集最大大小；若任意大有限点集都可打散，则定义为 $\mathrm{\infty }$。

这一定义要求阈值两侧各留出 $\gamma$，所以正负候选值至少相隔 $2\gamma$。有的文献把总间隔记作 $\gamma$，在两侧写 $\gamma /2$；比较公式时必须先核对 convention。

概念图像 ​

伪维公理库伪维pseudo-dimension · Pollard dimension通过逐点阈值打散，把 VC 维推广到实值函数类。只问能否跨过每个点自己的阈值，跨过 ${10}^{-12}$ 与跨过 $10$ 都算一次。fat-shattering 维把分辨率放回问题：观察或预测精度若只有 $\gamma$，落在阈值附近的细小摆动不应被当作可稳定区分的模式。随着 $\gamma$ 增大，条件更严格，因此 ${\mathrm{fat}}_{\gamma }(F)$ 单调不增。

它与分类器的几何间隔相似但不相同。这里的 $\gamma$ 位于函数输出轴上，且阈值 $r_i$ 可逐点变化；只有给定输入范数、参数范数和 score 归一化后，才能把它解释为几何距离。

具体例子：范数受限线性类 ​

令 $\mathcal{X}$ 位于 Hilbert 空间中，$\Vert x\Vert \le R$，

$$F=\{x\mapsto ⟨w,x⟩:\Vert w\Vert \le B\}.$$

若 $m$ 个点在尺度 $\gamma$ 被打散，考虑所有符号向量并利用线性对偶与随机符号平均，可以推出

$$\gamma \sqrt{m}\lesssim BR,\text{故}{\mathrm{fat}}_{\gamma }(F)\le {\left(\frac{BR}{\gamma }\right)}^2$$

（还应与空间维数取最小值）。这说明即使环境维数巨大，只要参数半径、输入半径和要求的分辨率固定，有效复杂度仍有限。反过来，在足够高维空间取近似正交的输入，并让 $w$ 沿符号和方向变化，可得到同量级的下界，故平方依赖不是单纯证明伪影。

边界与相邻概念 ​

若只要求 $f(x_i)\ge r_i$ 或 $<r_i$ 而没有两侧间隔，就回到伪维式打散。不能直接把 $\gamma =0$ 代入定义并宣布等于伪维：弱/严格不等号、函数值恰落阈值及极限交换都会造成差异；稳妥关系是把伪维看作无尺度阈值能力，并研究 $\gamma \downarrow 0$ 时 fat 维的行为。

输出范围和范数约束至关重要。所有实值函数组成的类在任何尺度都能对任意有限点集指定巨大正负值，fat 维无穷。有限 fat 维常进入实值学习的覆盖数与 margin 泛化界，但本定义本身既不是风险界，也不保证计算上能找到相应预测器。

参考资料

• Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler, “Scale-Sensitive Dimensions, Uniform Convergence, and Learnability,” 1997.
• Martin Anthony and Peter Bartlett, Neural Network Learning: Theoretical Foundations.