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

DOI10.1016/S0166-218X(98)00000-6zbMath0905.68048OpenAlexW4249341414MaRDI QIDQ1265741

Ami Litman, Shai Ben-David

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

sample compression schemesgeometric concept classesuniversal concept classes

Mathematics Subject Classification ID

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

Related Items (13)

Sample Compression Schemes for Balls in Graphs ⋮ Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property ⋮ Compression schemes for concept classes induced by three types of discrete undirected graphical models ⋮ Teaching and Compressing for Low VC-Dimension ⋮ Learning the set covering machine by bound minimization and margin-sparsity trade-off ⋮ Some new maximum VC classes ⋮ Compression schemes, stable definable families, and o-minimal structures ⋮ Order compression schemes ⋮ Bounding Embeddings of VC Classes into Maximum Classes ⋮ Shifting: one-inclusion mistake bounds and sample compression ⋮ Labeled Compression Schemes for Extremal Classes ⋮ On Version Space Compression ⋮ PAC learning with nasty noise.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Prediction-preserving reducibility
• Model theory.
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• On the density of families of sets
• Learnability and the Vapnik-Chervonenkis dimension
• Vapnik-Chervonenkis Classes of Definable Sets

This page was built for publication: Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes