The Computational Complexity of Machine Learning

Front Cover
MIT Press, 1990 - Computers - 165 pages
0 Reviews
The Computational Complexity of Machine Learning is a mathematical study of the possibilities for efficient learning by computers. It works within recently introduced models for machine inference that are based on the theory of computational complexity and that place an explicit emphasis on efficient and general algorithms for learning. Theorems are presented that help elucidate the boundary of what is efficiently learnable from examples. These results take the form of both algorithms with proofs of their performance, and hardness results demonstrating the intractability of learning in certain natural settings. In addition the book contains lower bounds on the resources required for learning, an extensive study of learning in the presence of errors in the sample data, and several theorems demonstrating reducibilities between learning problems. Michael J. Kearns is Postdoctoral Associate in the Laboratory for Computer Science at MIT. Contents: Definitions, Notations, and Motivation. Overview of Recent Research in Computational Learning Theory. Useful Tools for Distribution-Free Learning. Learning in the Presence of Errors. Lower Bounds on Sample Complexity. Cryptographic Limitations on Polynomial-Time Learning. Distribution-Specific Learning in Polynomial Time. Equivalence of Weak Learning and Group Learning.

What people are saying - Write a review

We haven't found any reviews in the usual places.


Recent Research in Computational Learning Theory
Tools for Distributionfree Learning
Learning in the Presence of Errors
Lower Bounds on Sample Complexity
Cryptographic Limitations on Polynomialtime Learning
Distributionspecific Learning in Polynomial Time
Equivalence of Weak Learning and Group Learning

Common terms and phrases

Popular passages

Page 155 - O. Goldreich, S. Goldwasser, S. Micali, How to Construct Random Functions, Journal of ACM, vol.
Page 154 - Proceedings of the 1988 Workshop on Computational Learning Theory. Morgan Kaufmann Publishers, Palo Alto, CA., 1988.

References to this book

All Book Search results »

About the author (1990)

Michael J. Kearns is Professor of Computer and Information Science at the University of Pennsylvania.

Bibliographic information