Labeled Compression Schemes for Extremal Classes

DOI10.1007/978-3-319-46379-7_3zbMath1478.68298arXiv1506.00165OpenAlexW2964190130MaRDI QIDQ2830265

Shay Moran, Manfred K. Warmuth

Publication date: 9 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Extremal set theory (05D05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (12)

Unlabeled sample compression schemes and corner peelings for ample and maximum classes ⋮ Ample Completions of Oriented Matroids and Complexes of Uniform Oriented Matroids ⋮ Sample Compression Schemes for Balls in Graphs ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Compression schemes for concept classes induced by three types of discrete undirected graphical models ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Unnamed Item ⋮ The complexity of exact learning of acyclic conditional preference networks from swap examples ⋮ Shattering-extremal set systems from Sperner families ⋮ Labeled Compression Schemes for Extremal Classes ⋮ On Version Space Compression ⋮ Two-dimensional partial cubes

Uses Software

• AdaBoost.MH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embeddings and the trace of finite sets
• Shattering, graph orientations, and connectivity
• Shattering-extremal set systems of VC dimension at most 2
• Occam's razor
• Lopsided sets and orthant-intersection by convex sets
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• Shattering news
• Defect Sauer results
• Externally definable sets and dependent pairs
• Combinatorics of lopsided sets
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Labeled Compression Schemes for Extremal Classes
• Generalizing Labeled and Unlabeled Sample Compression to Multi-label Concept Classes
• Sample Compression Schemes for VC Classes
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Reverse Kleitman Inequalities
• Teaching and Compressing for Low VC-Dimension
• Recursive Teaching Dimension, Learning Complexity, and Maximum Classes
• A Geometric Approach to Sample Compression

This page was built for publication: Labeled Compression Schemes for Extremal Classes