Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions

DOI10.1006/JCSS.1995.1008zbMath0827.68095DBLPjournals/jcss/Ben-DavidCHL95OpenAlexW2025263811WikidataQ59538631 ScholiaQ59538631MaRDI QIDQ1892207

Shai Ben-David, Nicolò Cesa-Bianchi, Philip M. Long, David Haussler

Publication date: 8 June 1995

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

Full work available at URL: https://doi.org/10.1006/jcss.1995.1008

zbMATH Keywords

VC-dimensionVapnik-Chervonenkis dimensionPAC learnability

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (11)

Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension ⋮ Learning with stochastic inputs and adversarial outputs ⋮ Sample Complexity of Classifiers Taking Values in ℝ^Q, Application to Multi-Class SVMs ⋮ Corrigendum to ``Shifting: One-inclusion mistake bounds and sample compression ⋮ On the Complexity of Computing and Learning with Multiplicative Neural Networks ⋮ Comments on: Support vector machines maximizing geometric margins for multi-class classification ⋮ Shifting: one-inclusion mistake bounds and sample compression ⋮ Valid Generalisation from Approximate Interpolation ⋮ Unnamed Item ⋮ Primal and dual combinatorial dimensions

This page was built for publication: Characterizations of learnability for classes of \(\{0,\dots,n\}\)-valued functions