Teaching and Compressing for Low VC-Dimension
From MaRDI portal
Publication:4604393
DOI10.1007/978-3-319-44479-6_26zbMath1425.68352arXiv1502.06187MaRDI QIDQ4604393
Shay Moran, Avi Wigderson, Amir Shpilka, Amir Yehudayoff
Publication date: 26 February 2018
Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.06187
68Q32: Computational learning theory
68T05: Learning and adaptive systems in artificial intelligence
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Related Items
A note on hardness of computing recursive teaching dimension, The VC-dimension of axis-parallel boxes on the torus, Labeled Compression Schemes for Extremal Classes, On Version Space Compression
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Population recovery and partial identification
- Algebraic methods proving Sauer's bound for teaching complexity
- Teachability in computational learning
- Teaching a smarter learner.
- \(\epsilon\)-nets and simplex range queries
- Occam's razor
- Inferring decision trees using the minimum description length principle
- Central limit theorems for empirical measures
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- Learning from different teachers
- Density and dimension
- On the complexity of teaching
- On weak learning
- Boosting a weak learning algorithm by majority
- Externally definable sets and dependent pairs
- Shifting: one-inclusion mistake bounds and sample compression
- On the density of families of sets
- Restriction access
- Learning Binary Relations and Total Orders
- Sample Compression Schemes for VC Classes
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Learning Integer Lattices
- 10.1162/jmlr.2003.3.4-5.723
- Recursive Teaching Dimension, Learning Complexity, and Maximum Classes
- A Geometric Approach to Sample Compression
- Teaching Dimension and the Complexity of Active Learning
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
