Skip to content

伪维

pseudo-dimension · Pollard dimension

通过逐点阈值打散,把 VC 维推广到实值函数类。

条目类型
定义

形式陈述

定义

对实值函数类 FRX,其中 R实数域,若存在点 x1,,xm 和各自阈值 r1,,rm,使对每个 b{0,1}m 都有某个 fF 满足

1[f(xi)ri]=bi(i=1,,m),

就称这些点被 F 伪打散。最大的 mPdim(F);不存在最大值时为无穷。

子图类的等价形式

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

subgraph(f)={(x,r):rf(x)},

则伪维等于子图集合类 {subgraph(f):fF}VC 维。这把实值问题转成扩充空间 X×R 上的二元打散。

直觉

每个样本点都带一根可独立设定高度的横杆 ri,函数图像要能按任意二进制模式越过或低于这些横杆。阈值随点变化,使伪维捕捉实值函数在不同位置的相对高度,而不是只问同一个水平切片能形成多少分类。

子图转换把 (xi,ri) 当作扩充空间中的二分类点:函数值是否越过阈值,等价于该点是否落入函数子图。于是 VC 维的组合工具可以复用,但输出范围与损失尾部仍属于回归问题的额外条件。

例子与边界

线性函数例子

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

与相邻维度的区别

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

边界

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

推论与应用

对二元函数类,取阈值 1/2 后伪维退化为 VC 维;对线性实值函数,维数与独立线性方向对应。它因此是回归函数类的一项组合复杂度,而不是损失函数或估计器本身。

将伪维用于泛化时,还要把函数输出范围传到损失类。绝对损失需要 Lipschitz 与包络控制,平方损失的 Lipschitz 常数则依赖预测和标签界;若响应重尾,应先引入截断或稳健估计,不能只引用有限伪维。

参考资料
  • David Pollard, Convergence of Stochastic Processes, Springer, 1984.
  • Martin Anthony, Peter L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 1999.
关系图谱11 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组