Machine Learning II (2007/2008)

6/13 VC Theory

This lecture is an introduction to Vapnik-Chervonenkis theory.

Concepts covered: Empirical error and true error. Hoeffding's inequality, uniform convergence, union bounds. Symmetrization, growth function, VC dimension and the Sauer-Shelah Lemma. [notes]