论文标题
未标记的样品压缩方案针对定向的矩阵
Unlabeled sample compression schemes for oriented matroids
论文作者
论文摘要
长期存在的样本压缩猜想要求通过任意类别的Vapnik-Chervonenkis（VC）维度线性结合最佳样品压缩方案的大小。在本文中，我们探讨了定向矩阵（OMS）的丰富度量和组合结构，以构建适当的未标记样品压缩方案，以适用于由VC差异界定的OMS层的类别。结果延伸到了仿射OMS的顶部，以及具有角落脱皮的OMS的配合物的山顶。我们使用的主要工具是某些定向的Matroid程序的解决方案。
A long-standing sample compression conjecture asks to linearly bound the size of the optimal sample compression schemes by the Vapnik-Chervonenkis (VC) dimension of an arbitrary class. In this paper, we explore the rich metric and combinatorial structure of oriented matroids (OMs) to construct proper unlabeled sample compression schemes for the classes of topes of OMs bounded by their VC-dimension. The result extends to the topes of affine OMs, as well as to the topes of the complexes of OMs that possess a corner peeling. The main tool that we use are the solutions of certain oriented matroid programs.
