样本压缩方案

形式定义 ​

对概念类 $\mathcal{C}$，大小为 $k$ 的标注样本压缩方案由压缩映射 $\kappa$ 与重构映射 $\rho$ 组成。$\kappa$ 从任意有限、由某 $c\in \mathcal{C}$ 一致标注的样本 $S$ 中选出至多 $k$ 个带标签样本，并可附带来自受控有限集合的 side information；$\rho$ 只看压缩结果，输出假设 $h$，要求 $h$ 与原样本 $S$ 的全部标签一致。

更明确地，若 $S\in (\mathcal{X}\times \{0,1\}{)}^m$，可写

$$\kappa (S)=(S_I,b),|I|\le k,\rho (S_I,b):\mathcal{X}\to \{0,1\},$$

并要求对每个与类一致的 $S$ 以及每个 $(x_i,y_i)\in S$，都有 $\rho (S_I,b)(x_i)=y_i$。量词覆盖所有有限样本和所有可实现标注；方案不能先知道生成样本的目标概念，再把目标概念名字塞进 $b$。

压缩大小如何计入辅助位必须在方案中明说。若允许随样本长度携带任意长字符串，任何样本都能“压缩”成零个点再把全部信息藏进字符串，定义便失去内容。

阈值分类器例子 ​

实线阈值类可写为 $h_a(x)=\mathbf{1}[x\ge a]$。对同时含正负样本的一致数据，只保留最右负样本与最左正样本；重构时把阈值放在二者之间，就会复原对全体训练点一致的分类器。全正或全负情形需用一个有限状态位说明边界情况。这里保留的是决定版本空间边界的样本，而不是对模型文件做通用无损压缩。

把 $x$ 解释为传感器读数、$1$ 解释为“超过报警阈值”时，这个方案有直接操作含义：历史记录中间那些远离切换位置的读数不会再约束阈值，真正决定所有一致阈值的只有“最高的未报警读数”和“最低的已报警读数”。若标注出现一次反转，使较低读数报警而较高读数不报警，样本已不再由阈值类实现；原方案不能靠多留几个点修复这一矛盾，而要改成 agnostic 压缩目标。

为什么压缩会泛化 ​

若重构假设的真实错误率为 $\epsilon$，一个 IID 样本在未被保留的 $m-k$ 个点上全都避开错误区域的概率约为 $(1-\epsilon {)}^{m-k}$。再对可能被选作压缩集的至多 $\sum _{j\le k}(\genfrac{}{}{0ex}{}{m}{j})$ 种位置及辅助状态取并，可得到依赖 $k\log m$ 和 $\log \left(1/\delta \right)$ 的一致泛化界。精确界由压缩类型决定，但机制都是“输出只由很少样本决定”。

变体与边界 ​

unlabeled compression 不保留标签；stable compression 要求删去未被压缩的样本不会改变压缩集；majority-vote compression 用多个重构器组合。它们不是同一结构的不同名字。上面定义服务于可实现一致学习；agnostic 情形通常只能要求近似保留经验误差，需另设误差指标。

截至 2025/2026，已知每个有限 VC 维 $d$ 的类存在大小 $2^{O(d)}$ 的一般压缩方案，而是否总存在 $O(d)$ 大小方案仍是开放问题，不能把压缩猜想写成定理。重构输出公理库Proper 与 Improper 学习Proper learning · Improper learning区分比较类与学习器实际允许输出的函数类。也未必属于原概念类，须单独注明 proper 性。

还要区分“选出至多 $k$ 个样本”与“重构器只依赖这些样本”。若压缩算法在选点后保留原样本顺序、未选点数量或浮点训练轨迹作为隐藏状态，描述长度仍随 $m$ 增长，泛化计数就不再只由 $k$ 控制。stable compression 等附加结构能给更锐利界，但不能倒过来写进一般压缩方案的定义。

参考资料

• Nick Littlestone, Manfred Warmuth, Relating Data Compression and Learnability, 1986.
• Shay Moran, Amir Yehudayoff, Sample Compression Schemes for VC Classes, JACM, 2016.