Kearns M.J., Vazirani U.V. An Introduction to Computational Learning Theory

MIT Press, 1994. — 216 p.In the Fall term of 1990, we jointly taught a graduate seminar in computational learning theory in the computer science department of the University of California at Berkeley. The material that is presented here has its origins in that course, both in content and exposition. Rather than attempt to give an exhaustive overview of this rapidly expanding and changing area of research, we have tried to carefully select fundamental topics that demonstrate important principles that may be applicable in a wider setting than the one examined here. In the technical sections, we have tried to emphasize intuition whenever possible, while still providing precise arguments.
The book is intended for researchers and students in artificial intelligence, neural networks, theoretical computer science and statistics, and anyone else interested in mathematical models of learning. It is appropriate for use as the central text in a specialized seminar course, or as a supplemental text in a broader course that perhaps also studies the viewpoints taken by artificial intelligence and neural networks. While Chapter 1 lays a common foundation for all the subsequent material, the later chapters are essentially self-contained and may be read selectively and in any order. Exercises are provided at the end of each chapter.The Probably Approximately Correct Learning Model
Occam‘s Razor
The Vapnik-Chervonenkis Dimension
Weak and Strong Learning
Learning in the Presence of Noise
Inherent Unpredictability
Reducibility in PAC Learning
Learning Finite Automata by Experimentation
A: Some Tools for Probabilistic Analysis