Machine Learning II (2007/2008)

5/16 Computational Learning Theory

In this overview lecture of computational learning theory we discuss such classical topics as learning boolean functions, decision lists and half planes in n-dimensional Euclidean space. We describe the PAC model and the online learning model and end with an introduction to VC theory.

Concepts covered: Non-probabilistic approaches to learning, online learning and PAC learning. Learning conjunctions, disjunctions and decision lists. The eliminiation algorithm, winnow, the weighted majority algorithm and the perceptron. Growth function and Vapnik-Chervonenkis dimension.

• M. Kearns and U. Vaziarani: An introduction to computational learning theory. MIT Press, 1994 [amazon]
• A. Blum: On-line algorithms in machine learning. [ps.gz]