Labeled compression schemes for extremal classes
From MaRDI portal
Extremal set theory (05D05) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)
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
- 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
- scientific article; zbMATH DE number 1113985 (Why is no real title available?)
- 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)- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- On partial cubes, well-graded families and their duals with some applications in graphs
- The complexity of exact learning of acyclic conditional preference networks from swap examples
- Shattering-extremal set systems from Sperner families
- Unlabeled compression schemes exceeding the VC-dimension
- Shifting: one-inclusion mistake bounds and sample compression
- Bounding embeddings of VC classes into maximum classes
- Labeled compression schemes for extremal classes
- On version space compression
- Order compression schemes
- Generalizing labeled and unlabeled sample compression to multi-label concept classes
- Unlabeled compression schemes for maximum classes
- Sample Compression Schemes for VC Classes
- Sign rank versus Vapnik-Chervonenkis dimension
- Ample completions of oriented matroids and complexes of uniform oriented matroids
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Learning Theory
- Order compression schemes
- Sample Compression Schemes for Balls in Graphs
- Compression schemes for concept classes induced by three types of discrete undirected graphical models
- Unlabeled sample compression schemes for oriented matroids
- Labeled sample compression schemes for complexes of oriented matroids
- Two-dimensional partial cubes
- Compression schemes, stable definable families, and o-minimal structures
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)
