A geometric approach to sample compression

MaRDI QIDQ5405160zbMATH OpenFDO

Authors Benjamin I. P. Rubinstein, J. Hyam Rubinstein

Publication date 1 April 2014

Full work available at URL https://arxiv.org/abs/0911.3633, http://www.jmlr.org/papers/v13/rubinstein12a.html

zbMATH Keywords

hyperplane arrangementssample compressionhyperbolic and piecewise-linear geometryone-inclusion graphs

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for over two decades. This paper presents a systematic geometric investigation of the compression of finite maximum concept classes. Simple arrangements of hyperplanes in Hyperbolic space, and Piecewise-Linear hyperplane arrangements, are shown to represent maximum classes, generalizing the corresponding Euclidean result. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled d-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some d-maximal classes cannot be embedded into any maximum class of VC dimension d+k, for any constant k. The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of d other hyperplanes. This extends the well known Pachner moves for triangulations to cubical complexes.

Recommendations

• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Unlabeled compression schemes for maximum classes
• Bounding embeddings of VC classes into maximum classes
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Generalizing labeled and unlabeled sample compression to multi-label concept classes

Cited in

(17)

• Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property
• Labeled sample compression schemes for complexes of oriented matroids
• Teaching and Compressing for Low VC-Dimension
• Ample completions of oriented matroids and complexes of uniform oriented matroids
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Sample Compression Schemes for VC Classes
• Some new maximum VC classes
• Compression schemes for concept classes induced by three types of discrete undirected graphical models
• Sign rank versus Vapnik-Chervonenkis dimension
• Order compression schemes
• What convex geometries tell about shattering-extremal systems
• The complexity of exact learning of acyclic conditional preference networks from swap examples
• scientific article; zbMATH DE number 7561527 (Why is no real title available?)
• Unlabeled sample compression schemes for oriented matroids
• Shifting: one-inclusion mistake bounds and sample compression
• Bounding embeddings of VC classes into maximum classes
• Labeled compression schemes for extremal classes

This page was built for publication: A geometric approach to sample compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405160)