论文标题
VC维度最多二次的标记样品压缩方案
A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension
论文作者
论文摘要
本文介绍了任何有限概念类的适当稳定标记的样品压缩方案（\ vcd^2）$，其中$ \ vcd $表示vapnik-chervonenkis维度。该结构基于一个众所周知的机器教学模型，称为递归教学维度。这显着改善了当前最著名的对样品压缩方案的大小（由于Moran和Yehudayoff）的限制，这在$ \ vcd $中是指数的。长期以来的开放问题样本压缩方案的最小规模是否在$ O（\ vcd）$中尚未解决，但我们的结果表明，对机器教学的研究是研究此开放问题的有希望的途径。 作为机器教学与样品压缩之间牢固联系的进一步证据，我们证明了Kirkpatrick等人引入的无扣教学模型可以用来定义稳定样品压缩方案大小的非平凡下限。
This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(\VCD^2)$ for any finite concept class, where $\VCD$ denotes the Vapnik-Chervonenkis Dimension. The construction is based on a well-known model of machine teaching, referred to as recursive teaching dimension. This substantially improves on the currently best known bound on the size of sample compression schemes (due to Moran and Yehudayoff), which is exponential in $\VCD$. The long-standing open question whether the smallest size of a sample compression scheme is in $O(\VCD)$ remains unresolved, but our results show that research on machine teaching is a promising avenue for the study of this open problem. As further evidence of the strong connections between machine teaching and sample compression, we prove that the model of no-clash teaching, introduced by Kirkpatrick et al., can be used to define a non-trivial lower bound on the size of stable sample compression schemes.
