Teaching and Compressing for Low VC-Dimension

DOI10.1007/978-3-319-44479-6_26zbMATH Open1425.68352OpenAlexW2962808814MaRDI QIDQ4604393FDOQ4604393

Authors Shay Moran, Amir Shpilka, A. Wigderson, 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

Mathematics Subject Classification ID

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)

Abstract: In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. Namely, the quality of sample compression schemes and of teaching sets for classes of low VC-dimension. Let $C$ be a binary concept class of size $m$ and VC-dimension $d$. Prior to this work, the best known upper bounds for both parameters were $log(m)$, while the best lower bounds are linear in $d$. We present significantly better upper bounds on both as follows. Set $k=O(d{2}^{d}loglog|C|)$. We show that there always exists a concept $c$ in $C$ with a teaching set (i.e. a list of $c$-labeled examples uniquely identifying $c$ in $C$) of size $k$. This problem was studied by Kuhlmann (1999). Our construction implies that the recursive teaching (RT) dimension of $C$ is at most $k$ as well. The RT-dimension was suggested by Zilles et al. and Doliwa et al. (2010). The same notion (under the name partial-ID width) was independently studied by Wigderson and Yehudayoff (2013). An upper bound on this parameter that depends only on $d$ is known just for the very simple case $d=1$, and is open even for $d=2$. We also make small progress towards this seemingly modest goal. We further construct sample compression schemes of size $k$ for $C$, with additional information of $klog(k)$ bits. Roughly speaking, given any list of $C$-labelled examples of arbitrary length, we can retain only $k$ labeled examples in a way that allows to recover the labels of all others examples in the list, using additional $klog(k)$ information bits. This problem was first suggested by Littlestone and Warmuth (1986).

Recommendations

• Recursive teaching dimension, VC-dimension and sample compression
• Learning in compressed space
• Compressed representation of learning spaces
• Combined compression and classification with learning vector quantization
• Learning as Data Compression
• Unlabeled compression schemes exceeding the VC-dimension
• Sample Compression Schemes for VC Classes

Cites work

• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• 10.1162/jmlr.2003.3.4-5.723
• A geometric approach to sample compression
• A theory of the learnable
• Algebraic methods proving Sauer's bound for teaching complexity
• An introduction to support vector machines and other kernel-based learning methods.
• Boosting a weak learning algorithm by majority
• Central limit theorems for empirical measures
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Density and dimension
• Externally definable sets and dependent pairs
• Inferring decision trees using the minimum description length principle
• Learnability and the Vapnik-Chervonenkis dimension
• Learning Binary Relations and Total Orders
• Learning Integer Lattices
• Learning from different teachers
• Models of cooperative teaching and learning
• Occam's razor
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the complexity of teaching
• On the density of families of sets
• On weak learning
• Population recovery and partial identification
• Recursive teaching dimension, learning complexity, and maximum classes
• Restriction access
• Sample Compression Schemes for VC Classes
• Shifting: one-inclusion mistake bounds and sample compression
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• Teachability in computational learning
• Teaching Dimension and the Complexity of Active Learning
• Teaching a smarter learner.
• Unlabeled compression schemes for maximum classes
• \(\epsilon\)-nets and simplex range queries

Cited in

(10)

• Algebraic methods proving Sauer's bound for teaching complexity
• Bounding embeddings of VC classes into maximum classes
• The VC-dimension of axis-parallel boxes on the torus
• Labeled compression schemes for extremal classes
• On version space compression
• Recursive teaching dimension, learning complexity, and maximum classes
• Sample Compression Schemes for VC Classes
• Sauer's bound for a notion of teaching complexity
• Recursive teaching dimension, VC-dimension and sample compression
• A note on hardness of computing recursive teaching dimension

This page was built for publication: Teaching and Compressing for Low VC-Dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604393)