Equivalence of models for polynomial learnability

DOI10.1016/0890-5401(91)90042-ZzbMath0743.68115MaRDI QIDQ1183606

Manfred K. Warmuth, Michael Kearns, David Haussler, Nicholas Littlestone

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

equivalencesmachine learningconsistent hypothesespolynomial learnabilityprediction learningValiant's learnability model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Efficient distribution-free learning of probabilistic concepts, Nonuniform learnability, Halfspace learning, linear programming, and nonmalicious distributions, Some connections between learning and optimization, Efficient algorithms for learning functions with bounded variation, A theory for memory-based learning, Can PAC learning algorithms tolerate random attribute noise?, From learning in the limit to stochastic finite learning, Knowing what doesn't matter: exploiting the omission of irrelevant data, On the non-efficient PAC learnability of conjunctive queries, Learning reliably and with one-sided error, Learning recursive functions: A survey, Learning indexed families of recursive languages from positive data: A survey, Learning in parallel, Four types of noise in data for PAC learning, Decision theoretic generalizations of the PAC model for neural net and other learning applications, PAC Learning under Helpful Distributions, Closure properties of uniform convergence of empirical means and PAC learnability under a family of probability measures., Learning logic programs with structured background knowledge, Agnostic learning of geometric patterns, Teachability in computational learning, Prediction, learning, uniform convergence, and scale-sensitive dimensions, Learning with unreliable boundary queries, Learning with restricted focus of attention, Hybrid classification algorithms based on boosting and support vector machines, Noise-tolerant parallel learning of geometric concepts, Unnamed Item, Exploiting random walks for learning, Learning from positive and unlabeled examples, A geometric approach to leveraging weak learners

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Prediction-preserving reducibility
• \(\epsilon\)-nets and simplex range queries
• Occam's razor
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Queries and concept learning
• On the density of families of sets
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Computational limitations on learning from examples
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities