Bounding embeddings of VC classes into maximum classes

DOI10.1007/978-3-319-21852-6_21zbMATH Open1357.68182arXiv1401.7388OpenAlexW2963945525MaRDI QIDQ2805735FDOQ2805735

Authors: Benjamin I. P. Rubinstein, Peter L. Bartlett, J. Hyam Rubinstein 

Publication date: 13 May 2016

Published in: Measures of Complexity (Search for Journal in Brave)

Abstract: One of the earliest conjectures in computational learning theory-the Sample Compression conjecture-asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension. To-date this statement is known to be true for maximum classes---those that possess maximum cardinality for their VC dimension. The most promising approach to positively resolving the conjecture is by embedding general VC classes into maximum classes without super-linear increase to their VC dimensions, as such embeddings would extend the known compression schemes to all VC classes. We show that maximum classes can be characterised by a local-connectivity property of the graph obtained by viewing the class as a cubical complex. This geometric characterisation of maximum VC classes is applied to prove a negative embedding result which demonstrates VC-d classes that cannot be embedded in any maximum class of VC dimension lower than 2d. On the other hand, we show that every VC-d class C embeds in a VC-(d+D) maximum class where D is the deficiency of C, i.e., the difference between the cardinalities of a maximum VC-d class and of C. For VC-2 classes in binary n-cubes for 4 <= n <= 6, we give best possible results on embedding into maximum classes. For some special classes of Boolean functions, relationships with maximum classes are investigated. Finally we give a general recursive procedure for embedding VC-d classes into VC-(d+k) maximum classes for smallest k.

Full work available at URL: https://arxiv.org/abs/1401.7388

Recommendations

• Labeled compression schemes for extremal classes
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Teaching and Compressing for Low VC-Dimension
• Sample Compression Schemes for VC Classes
• Unlabeled compression schemes for maximum classes

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Learnability and the Vapnik-Chervonenkis dimension
• Almost optimal set covers in finite VC-dimension
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• A general lower bound on the number of examples needed for learning
• Unlabeled compression schemes for maximum classes
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• A Geometric Approach to Sample Compression

Cited In (6)

• Labeled sample compression schemes for complexes of oriented matroids
• Sign rank versus Vapnik-Chervonenkis dimension
• Two-dimensional partial cubes
• Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids
• Shifting: one-inclusion mistake bounds and sample compression
• On partial cubes, well-graded families and their duals with some applications in graphs

This page was built for publication: Bounding embeddings of VC classes into maximum classes

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