度量熵与覆盖数 | Codeboy's Blog

形式陈述

覆盖数把函数类置于度量结构中，并按分辨率计算可区分行为；它不以参数个数或集合的裸基数替代几何。

有限假设类可以直接用 $|H|$ 计数，无穷类却不能靠基数区分复杂程度：一条参数曲线和所有连续函数都可能具有不可数基数。覆盖数改问一个与学习更贴近的问题：当误差小于 $\varepsilon$ 的函数被视为不可分辨时，需要多少个代表才能覆盖整个类？尺度越细，代表通常越多，增长速度便形成函数类的分辨率画像。

设 $(F,d)$ 为伪度量空间。集合 $V\subseteq F$ 是 $F$ 的一个 $\varepsilon$ -cover，若每个 $f\in F$ 都存在 $v\in V$ 使 $d(f,v)\le\varepsilon$ 。最小可能大小称为覆盖数

N(\varepsilon,F,d) =\inf\{|V|:V\text{ 是 }F\text{ 的 }\varepsilon\text{-cover}\}.

它可以是无穷。其对数

\log N(\varepsilon,F,d)

称为该尺度下的度量熵。这里的“熵”是几何计数，不是随机变量的Shannon 熵。

packing 与覆盖的夹逼

集合 $P\subseteq F$ 是 $\varepsilon$ -packing，若任意不同 $f,g\in P$ 都满足 $d(f,g)>\varepsilon$ 。最大 packing 大小记为 $M(\varepsilon,F,d)$ 。极大 packing 必然也是同尺度的 cover，否则还能加入一个离所有点都更远的新点；另一方面，一个足够细的 cover 不可能同时服务两个相距太远的 packing 点。因此在常用闭球约定下有

M(2\varepsilon,F,d) \le N(\varepsilon,F,d) \le M(\varepsilon,F,d).

常数 $2$ 会随严格不等式和球半径约定改变，但方向不会改变。packing 提供“至少需要这么多代表”的下界，cover 给出“这些代表已经够用”的上界。

度量必须写在公式里

同一个函数类在不同度量下可能呈现完全不同的复杂度。给定样本 $S=(x_1,\ldots,x_m)$ ，经验 $L_2$ 伪度量为

d_{S,2}(f,g) =\left(\frac1m\sum_{i=1}^m(f(x_i)-g(x_i))^2\right)^{1/2}.

它只观察样本点上的差异，所以两个全局不同、但在 $S$ 上一致的函数距离为零。总体度量则可写成

d_{P,2}(f,g)=\bigl(\mathbb E_{X\sim P}(f(X)-g(X))^2\bigr)^{1/2},

它依赖未知分布 $P$ 。 $L_\infty$ 度量要求处处接近，通常比经验 $L_2$ 严得多。省略下标不仅损失信息，还可能把数据依赖的随机覆盖数误当成确定量。

直觉

尺度越细，代表越多；度量决定哪些差异对当前样本或分布可见。因此同一参数集合可以呈现完全不同的有效复杂度，而熵曲线记录了这种复杂度随分辨率增长的速度。

例子与边界

两个具体几何图像

在欧氏单位球 $B_2^d\subset\mathbb R^d$ 中，用半径 $\varepsilon$ 的欧氏球覆盖，体积比较给出

N(\varepsilon,B_2^d,\|\cdot\|_2) \le \left(1+\frac{2}{\varepsilon}\right)^d.

于是度量熵随 $d\log(1/\varepsilon)$ 增长。这里的 $d$ 不是因为集合有 $d$ 个点，而是因为每缩小一个尺度， $d$ 个独立方向都需要更细的网格。

对有界线性函数 $f_w(x)=\langle w,x\rangle$ ，若 $\|w\|_2\le B$ 且样本矩阵只落在一个低秩子空间，经验 $L_2$ 覆盖数由这个样本可见子空间控制，而非环境参数维数。这个例子说明经验覆盖能够利用数据几何；同一参数球在总体最坏分布下未必有同样小的网。

在泛化证明中的作用

选定一个 $\varepsilon$ -cover 后，可先对有限代表集合应用集中不等式与并集界，再用损失的 Lipschitz 性把代表上的控制传回整个函数类。粗略地说，证明会在“网格越细，离散化误差越小”和“网格越细， $\log N$ 越大”之间折中。Dudley 熵积分进一步同时汇总所有尺度，而不是只选择一张网。

覆盖数也常用于下界。若能找到许多两两分离的函数，任何学习器都必须从样本中分辨它们；packing 与检验归约由此连接到packing–Fano 方法。上界和下界使用同一几何对象，却分别读取 cover 与 packing 的两面。

边界与使用检查

一个有限的粗尺度 cover 不意味着类在任意精度下都可控。若 $\log N(\varepsilon)$ 在 $\varepsilon\downarrow0$ 时增长过快，熵积分可能发散。反过来，某个经验样本上的覆盖数很小，也不能直接推出所有分布上的统一保证；需要对样本随机性再取期望或给高概率控制。

cover 中心是否必须属于 $F$ 也有内部与外部覆盖两种约定。多数学习论结论只差常数，但证明中必须固定一种。函数无界、度量不全或可测性失控时，最小 cover 可能不存在；此时覆盖数定义用下确界，不应假装一定能取到最优网。

推论与应用

单尺度 cover 结合集中与并集界给出离散化泛化界，Dudley 熵积分把所有尺度的增量组织成 chaining，从而控制 Rademacher 或 Gaussian 上确界。packing 则反向为 Fano 等下界方法提供许多彼此分离的候选。

经验覆盖能够利用样本低秩结构，总体覆盖适合分布依赖分析， $L_\infty$ 覆盖则提供更强的处处控制。应用时先固定度量和尺度，再讨论熵增长；只报告一个没有下标的 covering number 无法复现结论。

参考资料

Aad van der Vaart and Jon Wellner, Weak Convergence and Empirical Processes, Springer, 1996, Chapter 2.
Richard M. Dudley, Uniform Central Limit Theorems, Cambridge University Press, 1999, Chapters 1–2.
Martin Anthony and Peter Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 1999, covering-number chapters.

形式陈述 ​

packing 与覆盖的夹逼 ​

度量必须写在公式里 ​

两个具体几何图像 ​

在泛化证明中的作用 ​