Shifting: one-inclusion mistake bounds and sample compression

DOI10.1016/J.JCSS.2008.07.005MaRDI QIDQ2517823zbMATH OpenOpenAlexFDO

Authors Benjamin I. P. Rubinstein, Peter L. Bartlett, J. Hyam Rubinstein

Publication date 9 January 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-86.pdf

zbMATH Keywords

multiclass predictionone-inclusion mistake boundssample compressionshiftingworst-case expected risk

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• A geometric approach to sample compression
• Bounding embeddings of VC classes into maximum classes
• Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression
• Labeled compression schemes for extremal classes
• The one-inclusion graph algorithm is near-optimal for the prediction model of learning

Cites work

• B-valuations of graphs
• A general lower bound on the number of examples needed for learning
• Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions
• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 6791296 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• Learning Theory
• On Representatives of Subsets
• On the density of families of sets
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• The one-inclusion graph algorithm is near-optimal for the prediction model of learning
• Unlabeled compression schemes for maximum classes
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements

Cited in

(7)

• On partial cubes, well-graded families and their duals with some applications in graphs
• On density of subgraphs of halved cubes
• Teaching and Compressing for Low VC-Dimension
• Algebraic methods proving Sauer's bound for teaching complexity
• Sample compression for real-valued learners
• Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression
• One-inclusion hypergraph density revisited

This page was built for publication: Shifting: one-inclusion mistake bounds and sample compression

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