压缩泛化界

定理 ​

设二元分类样本 $S=((X_1,Y_1),\dots ,(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(\genfrac{}{}{0ex}{}{m}{j})2^j\right)+\log \left(1/\delta \right)}{m-k}.$$

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

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

计数证明 ​

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

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

可能的索引集有 $(\genfrac{}{}{0ex}{}{m}{j})$ 个，标签编码至多 $2^j$ 个，消息有 $b$ 个。对所有候选应用 并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，坏事件概率至多

$$b\sum _{j=0}^k(\genfrac{}{}{0ex}{}{m}{j})2^j{e}^{-\epsilon (m-k)}.$$

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

阈值类真例 ​

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

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

失效边界 ​

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

辅助信息必须计入描述长度。若压缩器除 $k$ 个点外还传递一个任意精度实数，候选消息不再只有 $b$ 个，计数证明可能完全失效。压缩大小刻画输出由多少训练信息决定，与 一致稳定性公理库一致稳定性泛化界Uniform stability generalization bound · Stability generalization theorem将学习算法对单点替换的一致稳定性转化为期望与经典高概率泛化间隙界。的单点敏感度、VC 维的类级打散能力是三种不同机制。

参考资料

• 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.