样本压缩方案

压缩方案寻找的是一小组能够见证整个版本空间边界的样本。若最终预测器只由这份短证据决定，就不可能记住训练集的所有偶然细节；泛化代价因而由证据长度而不是原假设类的表面大小控制。

阈值分类器例子 ​

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

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

为什么压缩会泛化 ​

若某一候选重构假设的真实错误率超过 $\epsilon$，在固定压缩位置、固定侧信息和已保留样本后，其余 $m-j$ 个独立同分布样本公理库独立同分布样本IID sample · Independent and identically distributed sample以乘积分布描述来自同一总体的独立重复观测。全都避开错误区域的概率至多为 $(1-\epsilon {)}^{m-j}$。再对 $0\le j\le k$ 的压缩位置和 $|I|$ 个侧信息状态取并，可得到由 $k\log m+\log |I|+\log \left(1/\delta \right)$ 控制的一致泛化界。精确常数以及能否去掉 $\log m$ 因压缩类型而异，但共同机制是：输出只能来自由短证据索引的一小族候选假设。

变体与边界 ​

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

截至 2026 年 8 月 10 日，已经进入同行评议文献的一般结论仍是：每个VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。为 $d$ 的二元概念类存在大小 $2^{O(d)}$ 的 labeled 压缩方案。把一般上界降到 $O(d)$ 仍是样本压缩猜想；“大小恰为 $d$”又比线性上界更强，不能当作定义或已知定理。重构输出公理库Proper 与 Improper 学习Proper learning · Improper learning区分比较类与学习器实际允许输出的函数类。是否属于原概念类也必须单独注明。

几份容易被搜索结果误读为突破的预印本均未改变这项状态。2022 年，Zachary Chase 的 Optimally Compressing VC Classes 声称大小 $d$，随后因 Proposition 3.2 以及主定理的证明无效而撤回；Farnam Mansouri 与 Sandra Zilles 的另一份稿件声称 $O(d^2)$，也因构造与所需 teaching-dimension 参数没有所述关系、主结论错误而撤回。

2026 年的 arXiv:2603.23561 还需要按版本而不是按记录编号阅读。3 月 24 日的 v1 题为 Labeled Compression Schemes for Concept Classes of Finite Functions，声称对有限函数概念类构造大小恰为 $d$ 的方案；3 月 26 日的 v2 因第 5 页压缩方案错误撤回。4 月 1 日的 v3 已改题为 The No-Clash Teaching Dimension is Bounded by VC Dimension，作者与研究命题也发生变化；8 月 3 日的 v4 因 Lemma 2 证明错误撤回。后一次撤回针对改题后的 teaching-dimension 论证，不应写成同一份样本压缩证明被“再次撤回”。就样本压缩而言，决定性事实是 v2 已撤回原来的大小 $d$ 声明。

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

压缩泛化界把可枚举的短证据转成高概率错误率，因此阈值、最大间隔支持点和若干稳定压缩算法都能获得不依赖全局类基数的证书。若重构允许类外输出，还需单独说明 proper/improper 性质。

样本压缩与VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。共享“有限样本行为受控”的思想，但二者目前不是线性等价的已知定理。可靠的状态表述应把层级分开：$2^{O(d)}$ 的一般上界已经发表；$O(d)$ 仍是猜想；2022 年的大小 $d$ 与 $O(d^2)$ 声明以及 2026 年的大小 $d$ 声明都已由作者撤回。长期猜想的页面不能只读取旧摘要或搜索引擎快照，还必须核对具体版本、改题记录与撤回原因。