论文标题
OMS和CUOM的完整完成
Ample completions of OMs and CUOMs
论文作者
论文摘要
本文考虑了COM（面向复合物的矩阵）的完成，以使其具有相同VC维度的部分部分立方体。我们表明，这些存在于OMS（定向的矩形）和Cuoms（均匀定向的矩形）。这意味着OMS和Cuoms满足了样本压缩猜想，这是学习理论的主要开放问题之一。我们猜想每个COM都可以在不增加VC维度的情况下完成到足够的部分立方体。
This paper considers completions of COMs (complexes oriented matroids) to ample partial cubes of the same VC-dimension. We show that these exist for OMs (oriented matroids) and CUOMs (complexes of uniform oriented matroids). This implies that OMs and CUOMs satisfy the sample compression conjecture -- one of the central open questions of learning theory. We conjecture that every COM can be completed to an ample partial cube without increasing the VC-dimension.
