Unlabeled sample compression schemes and corner peelings for ample and maximum classes

摘要

We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) [20] of a partial shelling of the cross-polytope which can not be extended. From it, we derive a maximum class of VC dimension 3 without corners. This refutes several previous works in machine learning. In particular, it implies that the previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an optimal unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabeled sample compression scheme extends to ample classes, which generalize maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the associated 1-inclusion graph.