Abstract
Emphasizing issues of computational efficiency, Michael Kearns and Umesh Vazirani introduce a number of central topics in computational learning theory for researchers and students in artificial intelligence, neural networks, theoretical computer science, and statistics. Emphasizing issues of computational efficiency, Michael Kearns and Umesh Vazirani introduce a number of central topics in computational learning theory for researchers and students in artificial intelligence, neural networks, theoretical computer science, and statistics. Computational learning theory is a new and rapidly expanding area of research that examines formal models of induction with the goals of discovering the common methods underlying efficient learning algorithms and identifying the computational impediments to learning. Each topic in the book has been chosen to elucidate a general principle, which is explored in a precise formal setting. Intuition has been emphasized in the presentation to make the material accessible to the nontheoretician while still providing precise arguments for the specialist. This balance is the result of new proofs of established theorems, and new presentations of the standard proofs. The topics covered include the motivation, definitions, and fundamental results, both positive and negative, for the widely studied L. G. Valiant model of Probably Approximately Correct Learning; Occam's Razor, which formalizes a relationship between learning and data compression; the Vapnik-Chervonenkis dimension; the equivalence of weak and strong learning; efficient learning in the presence of noise by the method of statistical queries; relationships between learning and cryptography, and the resulting computational limitations on efficient learning; reducibility between learning problems; and algorithms for learning finite automata from active experimentation.
Keywords
Computational learning theoryProbably approximately correct learningAlgorithmic learning theoryComputer scienceArtificial intelligenceMathematical proofTheoretical computer scienceMachine learningInstance-based learningComputational modeloccamArtificial neural networkLearning theoryActive learning (machine learning)MathematicsProgramming languageMathematics education
Affiliated Institutions
Related Publications
An overview of statistical learning theory
Statistical learning theory was introduced in the late 1960's. Until the 1990's it was a purely theoretical analysis of the problem of function estimation from a given collectio...
On the boosting ability of top-down decision tree learning algorithms
Article Free Access Share on On the boosting ability of top-down decision tree learning algorithms Authors: Michael Kearns AT&T Research AT&T ResearchView Profile , Yishay Manso...
Deep Learning
Deep learning is a form of machine learning that enables computers to learn from experience and understand the world in terms of a hierarchy of concepts. Because the computer ga...
Large-Scale Machine Learning with Stochastic Gradient Descent
During the last decade, the data sizes have grown faster than the speed of processors. In this context, the capabilities of statistical machine learning methods is limited by th...
The Theory of Quantum Information
This largely self-contained book on the theory of quantum information focuses on precise mathematical formulations and proofs of fundamental facts that form the foundation of th...
Publication Info
- Year
- 1994
- Type
- book
- Citations
- 1717
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1717
OpenAlex
Cite This
Michael Kearns,
Umesh Vazirani
(1994).
An Introduction to Computational Learning Theory.
The MIT Press eBooks
.
https://doi.org/10.7551/mitpress/3897.001.0001
Identifiers
- DOI
- 10.7551/mitpress/3897.001.0001