度量熵与覆盖数

从“多少个函数”到“多少种可分辨行为” ​

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

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

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

它可以是无穷。其对数

$$\log N(\epsilon ,F,d)$$

称为该尺度下的度量熵。这里的“熵”是几何计数，不是随机变量的Shannon 熵公理库Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。。

packing 与覆盖的夹逼 ​

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

$$M(2\epsilon ,F,d)\le N(\epsilon ,F,d)\le M(\epsilon ,F,d).$$

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

度量必须写在公式里 ​

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

$$d_{S,2}(f,g)={(\frac{1}{m}\sum _{i=1}^m(f(x_i)-g(x_i){)}^2)}^{1/2}.$$

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

$$d_{P,2}(f,g)=({\mathbb{E}}_{X\sim P}(f(X)-g(X){)}^2{)}^{1/2},$$

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

两个具体几何图像 ​

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

$$N(\epsilon ,B_2^d,\Vert \cdot {\Vert }_2)\le {(1+\frac{2}{\epsilon })}^d.$$

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

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

在泛化证明中的作用 ​

选定一个 $\epsilon$-cover 后，可先对有限代表集合应用集中不等式与并集界，再用损失的 Lipschitz 性把代表上的控制传回整个函数类。粗略地说，证明会在“网格越细，离散化误差越小”和“网格越细，$\log N$ 越大”之间折中。Dudley 熵积分公理库Dudley 熵积分Dudley entropy integral · Dudley bound · Dudley 熵界通过多尺度 chaining 把次高斯过程的期望上确界控制为覆盖数对数平方根的积分。进一步同时汇总所有尺度，而不是只选择一张网。

覆盖数也常用于下界。若能找到许多两两分离的函数，任何学习器都必须从样本中分辨它们；packing 与检验归约由此连接到packing–Fano 方法公理库Packing–Fano 学习下界Packing-Fano method · Fano method for minimax lower bounds将参数空间离散成大量两两分离却统计上难以区分的候选，再由 Fano 不等式导出维数敏感的极小极大下界。。上界和下界使用同一几何对象，却分别读取 cover 与 packing 的两面。

边界与使用检查 ​

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

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

参考资料

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