压缩泛化界 | Codeboy's Blog

形式陈述

设二元分类样本 $S=((X_1,Y_1),\ldots,(X_m,Y_m))\sim D^m$ 可由一个一致样本压缩方案处理：压缩器保留至多 $k<m$ 个带标签样本点和至多 $b$ 种辅助消息之一，重构器只根据这些信息输出 $h_S$ ，且 $h_S(X_i)=Y_i$ 对全部训练点成立。

则任意 $0<\delta<1$ 下，以至少 $1-\delta$ 的概率

R_D(h_S) \le \frac{\log\!\left(b\sum_{j=0}^k\binom mj2^j\right)+\log(1/\delta)}{m-k}.

若压缩子样本已经携带原训练标签，具体方案的候选计数可去掉 $2^j$ ；保留它给出不依赖编码细节的安全版本。利用二项式系数和 $\sum_{j\le k}\binom mj\le (em/k)^k$ （ $1\le k\le m/2$ ），得到熟悉的量级

R_D(h_S)=O\!\left(\frac{k\log(m/k)+\log b+\log(1/\delta)}{m}\right).

先固定一个大小为 $j\le k$ 的索引集 $I$ 、其标签编码与辅助消息。重构假设只依赖 $S_I$ 。条件于这些压缩点，剩余 $m-j$ 个样本仍独立来自 $D$ 。如果该假设的真实错误率超过 $\varepsilon$ ，它仍与所有剩余点一致的概率至多

(1-\varepsilon)^{m-j}\le e^{-\varepsilon(m-j)} \le e^{-\varepsilon(m-k)}.

可能的索引集有 $\binom mj$ 个，标签编码至多 $2^j$ 个，消息有 $b$ 个。对所有候选应用并集界，坏事件概率至多

b\sum_{j=0}^k\binom mj2^j e^{-\varepsilon(m-k)}.

令它等于 $\delta$ 并解出 $\varepsilon$ 即得定理。证明的关键不是输出假设类有限，而是每个数据依赖输出都能由短证据枚举出来；这是 Occam 计数在样本压缩中的具体形态。

直觉

压缩器虽然看过全部样本，重构器真正接收的信息却只有少量索引、标签和辅助消息。于是所有可能输出可以由短描述枚举；某个高真实错误的输出还要碰巧在未压缩样本上全部零错，概率会随剩余样本数指数下降。

例子与边界

对实线上的可实现阈值分类，保留最右侧负例与最左侧正例（缺失某一类时用一位消息处理），重构任取两者之间的阈值。压缩大小至多 $2$ ，与阈值参数是任意实数无关。上面的基础计数界给出 $O((\log m+\log(1/\delta))/m)$ 的错误率。

对阈值还能直接分析两个边界点之间的分布质量并得到更紧结论；这说明通用压缩界未必最优。稳定压缩方案也可消除某些 $\log m$ 因子，但需要额外稳定结构，不能把更紧速率无条件写进所有压缩方案。

一致性不可省略：若重构假设已在许多未压缩训练点上犯错，“剩余点全部避开真实错误集”的概率计算便不再描述实际事件。不可知数据需要容错压缩和经验错误项，不能直接套本页结论。

辅助信息必须计入描述长度。若压缩器除 $k$ 个点外还传递一个任意精度实数，候选消息不再只有 $b$ 个，计数证明可能完全失效。压缩大小刻画输出由多少训练信息决定，与一致稳定性的单点敏感度、VC 维的类级打散能力是三种不同机制。

推论与应用

stable compression 可以利用删点不改变压缩集的结构消去某些 $\log m$ 因子；容错压缩则把训练错误项加入结论以处理不可知数据。这些强化都需要修改方案定义，不能从一般一致压缩界自动获得。

压缩证明也揭示 Occam 界的更一般形式：只要数据依赖输出能由短消息重构，就可按描述长度支付选择复杂度。应用到支持向量、稀疏证据或原型选择时，必须确认重构器没有读取隐藏的训练状态。

参考资料

Nick Littlestone and Manfred Warmuth, “Relating Data Compression and Learnability,” 1986.
Sally Floyd and Manfred Warmuth, “Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension,” 1995.