Recursive teaching dimension, VC-dimension and sample compression

MaRDI QIDQ2934114zbMATH OpenFDO

Authors Thorsten Doliwa, Gaojian Fan, Hans Ulrich Simon, Sandra Zilles

Publication date 8 December 2014

Full work available at URL http://jmlr.csail.mit.edu/papers/v15/doliwa14a.html

zbMATH Keywords

combinatorial parameterscompression schemesrecursive teaching dimensiontail matching algorithmupper boundsVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Recursive teaching dimension, learning complexity, and maximum classes
• Teaching and Compressing for Low VC-Dimension
• Sauer's bound for a notion of teaching complexity
• Algebraic methods proving Sauer's bound for teaching complexity
• Sample Compression Schemes for VC Classes

Cited in

(17)

• On the teaching complexity of linear sets
• The VC-dimension of axis-parallel boxes on the torus
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• The complexity of exact learning of acyclic conditional preference networks from swap examples
• When are epsilon-nets small?
• Distinguishing pattern languages with membership examples
• Sauer's bound for a notion of teaching complexity
• Sample Compression Schemes for VC Classes
• Teaching and Compressing for Low VC-Dimension
• Sign rank versus Vapnik-Chervonenkis dimension
• Algebraic methods proving Sauer's bound for teaching complexity
• Recursive teaching dimension, learning complexity, and maximum classes
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Order compression schemes
• A note on hardness of computing recursive teaching dimension
• Tournaments, Johnson graphs and NC-teaching
• Optimal collusion-free teaching

This page was built for publication: Recursive teaching dimension, VC-dimension and sample compression

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