Sample Compression Schemes for VC Classes

DOI10.1145/2890490MaRDI QIDQ3177793zbMATH OpenOpenAlexFDO

Authors Shay Moran, Amir Yehudayoff

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

PAC learningVC-dimensionsample compression schemes

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size $k$ means that given an arbitrary list of labeled examples, one can retain only $k$ of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds. We answer their question and show that every concept class $C$ with VC dimension $d$ has a sample compression scheme of size exponential in $d$. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.

Recommendations

• Compression of samplable sources
• Samplets: construction and scattered data compression
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Unlabeled compression schemes exceeding the VC-dimension
• A geometric approach to sample compression
• Recursive teaching dimension, VC-dimension and sample compression
• Sample Compression Schemes for Balls in Graphs
• Teaching and Compressing for Low VC-Dimension
• The Vcodex Platform for Data Compression
• Labeled compression schemes for extremal classes

Cited in

(28)

• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Ample completions of oriented matroids and complexes of uniform oriented matroids
• Labeled sample compression schemes for complexes of oriented matroids
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Order compression schemes
• Inclusion matrices for rainbow subsets
• Bounding embeddings of VC classes into maximum classes
• A characterization of list learnability
• Teaching and Compressing for Low VC-Dimension
• Order compression schemes
• The VC-dimension of axis-parallel boxes on the torus
• Labeled compression schemes for extremal classes
• Two-dimensional partial cubes
• On version space compression
• Compression schemes for concept classes induced by three types of discrete undirected graphical models
• Primal and dual combinatorial dimensions
• Sample Compression Schemes for Balls in Graphs
• Unlabeled compression schemes for maximum classes
• Shattering-extremal set systems from Sperner families
• Uniformly supported approximate equilibria in families of games
• Unlabeled compression schemes exceeding the VC-dimension
• On uniform definability of types over finite sets for NIP formulas
• Learning Theory
• scientific article; zbMATH DE number 7561527 (Why is no real title available?)
• On the perceptron's compression
• Generalizing labeled and unlabeled sample compression to multi-label concept classes
• Ramsey growth in some NIP structures
• Recursive teaching dimension, VC-dimension and sample compression

This page was built for publication: Sample Compression Schemes for VC Classes

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