论文标题
相交封闭类和极端类的未标记样品压缩方案
Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes
论文作者
论文摘要
概念类的样本可压缩性在学习理论中起着重要的作用，作为PAC可学习性的充分条件，并且最近是自适应数据分析中强大概括的途径。对于所有类别的VC尺寸$ d $的压缩方案都必须存在$ o（d）$的压缩方案尚不清楚，但猜想是沃德斯（Warmuth）的真实性。最近，Chalopin，Chepoi，Moran和Warmuth（2018）为所有最大类提供了一个精美的无标记的样品压缩方案：符合Sauer-Shelah-perles-perles Lemma的类。他们还根据一种有前途的方法称为角剥剥离，为压缩方案提供了反例。在本文中，我们简化并扩展了其证明技术，以处理所谓的vc dimension $ d $的极值类别，这些类别包含VC尺寸的最大类别$ d-1 $。给出了一个标准，这意味着所有极端类都承认$ d $的未标记压缩方案。我们还证明，所有与VC Dimension $ d $ closection Classection $ d $最多$ 11D $的压缩方案的相交类别。
The sample compressibility of concept classes plays an important role in learning theory, as a sufficient condition for PAC learnability, and more recently as an avenue for robust generalisation in adaptive data analysis. Whether compression schemes of size $O(d)$ must necessarily exist for all classes of VC dimension $d$ is unknown, but conjectured to be true by Warmuth. Recently Chalopin, Chepoi, Moran, and Warmuth (2018) gave a beautiful unlabelled sample compression scheme of size VC dimension for all maximum classes: classes that meet the Sauer-Shelah-Perles Lemma with equality. They also offered a counterexample to compression schemes based on a promising approach known as corner peeling. In this paper we simplify and extend their proof technique to deal with so-called extremal classes of VC dimension $d$ which contain maximum classes of VC dimension $d-1$. A criterion is given which would imply that all extremal classes admit unlabelled compression schemes of size $d$. We also prove that all intersection-closed classes with VC dimension $d$ admit unlabelled compression schemes of size at most $11d$.
