Labeled compression schemes for extremal classes
From MaRDI portal
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Extremal set theory (05D05)
Abstract: It is a long-standing open problem whether there always exists a compression scheme whose size is of the order of the Vapnik-Chervonienkis (VC) dimension . Recently compression schemes of size exponential in have been found for any concept class of VC dimension . Previously, compression schemes of size have been given for maximum classes, which are special concept classes whose size equals an upper bound due to Sauer-Shelah. We consider a generalization of maximum classes called extremal classes. Their definition is based on a powerful generalization of the Sauer-Shelah bound called the Sandwich Theorem, which has been studied in several areas of combinatorics and computer science. The key result of the paper is a construction of a sample compression scheme for extremal classes of size equal to their VC dimension. We also give a number of open problems concerning the combinatorial structure of extremal classes and the existence of unlabeled compression schemes for them.
Recommendations
Cites work
- scientific article; zbMATH DE number 1113985 (Why is no real title available?)
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A geometric approach to sample compression
- A theory of the learnable
- Boosting. Foundations and algorithms.
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Combinatorics of lopsided sets
- Defect Sauer results
- Embeddings and the trace of finite sets
- Externally definable sets and dependent pairs
- Generalizing labeled and unlabeled sample compression to multi-label concept classes
- Labeled compression schemes for extremal classes
- Learnability and the Vapnik-Chervonenkis dimension
- Lopsided sets and orthant-intersection by convex sets
- Occam's razor
- On the density of families of sets
- Recursive teaching dimension, learning complexity, and maximum classes
- Reverse Kleitman Inequalities
- Sample Compression Schemes for VC Classes
- Shattering news
- Shattering, graph orientations, and connectivity
- Shattering-extremal set systems of VC dimension at most 2
- Teaching and Compressing for Low VC-Dimension
- Unlabeled compression schemes for maximum classes
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
Cited in
(24)- Shattering-extremal set systems from Sperner families
- On partial cubes, well-graded families and their duals with some applications in graphs
- Labeled sample compression schemes for complexes of oriented matroids
- Compression schemes, stable definable families, and o-minimal structures
- Sample Compression Schemes for Balls in Graphs
- Learning Theory
- Generalizing labeled and unlabeled sample compression to multi-label concept classes
- Ample completions of oriented matroids and complexes of uniform oriented matroids
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- On version space compression
- Unlabeled compression schemes exceeding the VC-dimension
- Sample Compression Schemes for 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
- Order compression schemes
- The complexity of exact learning of acyclic conditional preference networks from swap examples
- Two-dimensional partial cubes
- Unlabeled compression schemes for maximum classes
- 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: Labeled compression schemes for extremal classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830265)
