压缩泛化界

形式陈述 ​

设 $m\ge 1$，二元分类样本 $S=((X_1,Y_1),\dots ,(X_m,Y_m))\sim D^{\otimes m}$ 为IID 样本理路独立同分布样本IID sample · Independent and identically distributed sample以乘积分布描述来自同一总体的独立重复观测。，且 $Y=c(X)$ 几乎必然，其中 $c$ 属于指定概念类。该类可由一个一致样本压缩方案理路样本压缩方案sample compression scheme从一致标注样本保留少量样本与辅助信息，并重构对原样本一致的预测器。处理：压缩器保留至多 $0\le k<m$ 个带标签样本点和至多 $b\ge 1$ 种辅助消息之一，其中 $k,b$ 为整数，重构器只根据这些信息输出 $h_S$，且 $h_S(X_i)=Y_i$ 对全部训练点成立。假定选点和重构损失可测；标签直接采用保留样本的真实标签。

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

这里不另乘 $2^j$，因为条件于带标签子样本后，标签已经固定。若再对所有二元标签编码取并，也能得到含 $2^j$ 的较松界，但本页方案不需要这笔重复计数。利用二项式系数理路二项式系数Binomial coefficientn 元集合的 k 元子集数，记作 C(n,k)。和 $\sum _{j\le k}(\genfrac{}{}{0ex}{}{m}{j})\le (em/k{)}^k$（$1\le k\le m/2$），得到熟悉的量级

计数证明 ​

先在读数据之前固定一个大小为 $j\le k$ 的候选索引集 $I$ 与辅助消息。重构假设只依赖 $S_I$。条件于带标签的 $S_I$，剩余 $m-j$ 个样本仍独立来自 $D$。这里不能再条件于“压缩器恰好选择了 $I$”，因为那会使用剩余样本的信息；最后的并集负责覆盖实际的数据依赖选择。如果该假设的真实错误率超过 $\epsilon$，它仍与所有剩余点一致的概率至多

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

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