Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression

Abstract

We systematically investigate finite maximum classes, which play an important role in machine learning as concept classes meeting Sauer's Lemma with equality. Simple arrangements of hyperplanes in Hyperbolic space are shown to represent maximum classes, generalizing the corresponding Euclidean result. We show that sweeping a generic hyperplane across such arrangements forms an unlabeled compression scheme of size VC dimension and corresponds to a special case of peeling the one-inclusion graph, resolving a conjecture of Kuzmin & Warmuth. A bijection between maximum classes and certain arrangements of Piecewise-Linear (PL) hyperplanes in either a ball or Euclidean space is established. Finally, we show that d-maximum classes corresponding to PL hyperplane arrangements in $\mathbb{R}^d$ have cubical complexes homeomorphic to a d-ball, or equivalently complexes that are manifolds with boundary.