伪维

定义 ​

对 $\mathcal{F}\subseteq {\mathbb{R}}^{\mathcal{X}}$，若存在点 $x_1,\dots ,x_m$ 和各自阈值 $r_1,\dots ,r_m$，使对每个 $b\in \{0,1{\}}^m$ 都有某个 $f\in \mathcal{F}$ 满足

$$\mathbf{1}[f(x_i)\ge r_i]=b_i(i=1,\dots ,m),$$

就称这些点被 $\mathcal{F}$ 伪打散。最大的 $m$ 是 $\mathrm{Pdim}(\mathcal{F})$；不存在最大值时为无穷。

几何图像与等价形式 ​

每个样本点都带一根可独立设定高度的横杆 $r_i$，函数图像要能按任意模式越过或低于这些横杆。令

$$\mathrm{subgraph}(f)=\{(x,r):r\le f(x)\},$$

则伪维等于子图集合类 $\{\mathrm{subgraph}(f):f\in \mathcal{F}\}$ 的VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。。这把实值问题转成扩充空间 $\mathcal{X}\times \mathbb{R}$ 上的二元打散。

线性函数例子 ​

对无截距线性类 $f_w(x)=⟨w,x⟩$，$w,x\in {\mathbb{R}}^d$，伪维为 $d$；加入自由截距后通常为 $d+1$。下界可选择线性独立的输入并调节 $w$ 实现相对阈值的符号模式；上界来自扩充后的仿射半空间 VC 维。这里的结论依赖函数族的具体表示能力，而不是“有 $d$ 个参数所以必然等于 $d$”。

与相邻维度的区别 ​

若只允许一个统一阈值 $r$，得到的是不同的阈值维度，不能替代逐点 $r_i$。伪维适合回归和实值损失类；fat-shattering dimension 还引入正 margin，更能刻画尺度敏感的实值复杂度。对二元 $\{0,1\}$ 值类，取阈值 $1/2$ 后伪维退化为 VC 维。

边界 ​

有限伪维只约束组合丰富度。要从它推出平方损失或绝对损失的风险界，通常还需输出有界、尾部条件或截断；无界函数可让少量极端值主导风险。不同参数可能表示同一函数，神经网络等类的伪维也未必等于裸参数数目。

参考资料

• David Pollard, Convergence of Stochastic Processes, Springer, 1984.
• Martin Anthony, Peter L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 1999.