Customer Reviews

An Introduction to Computational Learning Theory

5 star:		(2)
4 star:		(1)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

Kearns is an impressive researcher, precise and succinct. The material on this book follows a tradition of careful proofs of fundamental issues in learning. I wouldn't think this is material of practical use; for that kind of material I'd recommend the new edition of Duda. Rather, Kearns is one of a team of researchers pushing the frontier of proving what is learnable and what is not, why some representations are good for learning and which are not, the dimensionality of the target problem (related to overfitting) working with prinpled definitions of what it is meant to learn borrowed from computational complexity theory.

...about machine learning since learning algorithms are, in fact, algorithms. At a high level, computational learning theory answers the same sort of questions as statistical learning theory ("What kind of guarantees can I make about my learning procedure? In what situations is learning possible?") with different tools and methodology. Trade in your operator equations, modes of convergence, and support vectors for boolean formulae, complexity classes, and quadratic residues, but don't worry; the trade is temporary, since the theories are complementary, and short-lived, since the book is easy and quick to read. At well under 200 large-type pages, you can mow through it armed with little besides Big-O notation, basic probability, and a few (IID) samples of your favorite stimulant.

In return for your mild effort, you will be acquainted with the PAC model of learning and techniques for reasoning about tractability, sample size, connections to well-known problems, etc. The best material, in my opinion, relates to the importance of problem representation and methods for establishing the difficulty of efficient predictability. Even the most unsatisfying material (the treatment of Occam's razor and the description of VC dimension) isn't stale, and wasn't really bad to start; this, despite the book's age (15 years in a 25 year old subfield), is most probably* a testament to the book's value as an approachable introduction.

* (As usual, some positive probability is reserved to indict the field's lack of advancement. But not much).

The few chapters I have read of this book seem good. Good examples which is nice.