Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes

DOI10.1016/S0166-218X(98)00000-6MaRDI QIDQ1265741zbMATH OpenOpenAlexFDO

Authors Shai Ben-David, Ami Litman

Publication date 27 September 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

geometric concept classessample compression schemesuniversal concept classes

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Data structures (68P05)

Recommendations

• Compressed sampling inequalities by Tchakaloff's theorem
• Compression of Multivariate Discrete Measures and Applications
• scientific article; zbMATH DE number 4168234
• Compression and hadamard power inequalities
• Sample Compression Schemes for Balls in Graphs
• Compressed representations of permutations, and applications
• scientific article; zbMATH DE number 3930883
• Compressibility of Deterministic and Random Infinite Sequences
• Sample Compression Schemes for VC Classes
• Constraints placed on random sequences by their compressibility

Cites work

• scientific article; zbMATH DE number 3883309 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559548 (Why is no real title available?)
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• Learnability and the Vapnik-Chervonenkis dimension
• Model theory.
• On the density of families of sets
• Prediction-preserving reducibility
• Vapnik-Chervonenkis Classes of Definable Sets

Cited in

(17)

• Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property
• Labeled sample compression schemes for complexes of oriented matroids
• Compression schemes, stable definable families, and o-minimal structures
• Teaching and Compressing for Low VC-Dimension
• Sample Compression Schemes for Balls in Graphs
• On version space compression
• Sample Compression Schemes for VC Classes
• Some new maximum VC classes
• PAC learning with nasty noise.
• Compression schemes for concept classes induced by three types of discrete undirected graphical models
• Order compression schemes
• Learning the set covering machine by bound minimization and margin-sparsity trade-off
• A geometric approach to sample compression
• 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: Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes

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