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

形式陈述

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

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

设 $(F,d)$ 为非空伪度量空间， $\varepsilon>0$ 。这里的 $F$ 可以是任意点集，函数类是学习中的重要应用。集合 $V\subseteq F$ 是 $F$ 的一个 $\varepsilon$ -cover，若每个 $f\in F$ 都存在 $v\in V$ 使 $d(f,v)\le\varepsilon$ 。若存在有限 cover，最少的中心个数称为覆盖数

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

若没有有限 cover，约定 $N=+\infty$ ；若有，可能大小是一组非空正整数，故最小值必能取得。其对数

\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)$ ；若大小无界则取 $+\infty$ ，若有限则最大值取得。极大 packing 必然也是同尺度的 cover，否则还能加入一个离所有点都更远的新点；另一方面，一个足够细的 cover 不可能同时服务两个相距太远的 packing 点。因此在常用闭球约定下有

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

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

度量必须写在公式里

同一个函数类在不同度量下可能呈现完全不同的复杂度。对实值函数类，给定 $m\ge1$ 个输入组成的样本 $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},

这里要求函数可测且每对差 $f-g$ 平方可积，才能得到有限值的伪度量；它依赖未知分布 $P$ 。用逐点上确界定义的 $d_\infty(f,g)=\sup_x|f(x)-g(x)|$ 也须保证有限，且要求处处接近，通常比经验 $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，却不会让一个有限的最小中心数无法取得。另一方面，逐个样本存在最小网，不保证能把网中心选成样本的可测函数；数据依赖的网还需单独处理可测选择。

对有限真正度量，最远点优先k-center反过来固定中心数k，求小覆盖半径。维护每点到已有中心的最近距离，逐次加入最远点；当k<n时，最后的k个中心加一个最远见证两两相距至少R，于是R/2是最优中心半径下界。按固定ε截断同一序列，则得到内部ε-cover与严格ε-packing，须保留终止不等号。

推论与应用

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

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

在度量空间中，各个正尺度的覆盖数都有限正是全有界性；紧空间的度量刻画证明，完备性再把这种有限分辨率控制提升为紧性。对紧定义域上的标量连续函数，Arzelà–Ascoli 定理以共同连续尺度和有限采样值编码构造有限网。它首先回答“每个尺度是否有限”，本页的覆盖数则进一步量化代表数随尺度怎样增长。

参考资料

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 与覆盖的夹逼 ​

度量必须写在公式里 ​

两个具体几何图像 ​

在泛化证明中的作用 ​