Pattern Classification and Large Margin Classifiers
These lectures will provide an introduction to the theory of pattern classification methods. They will focus on relationships between the minimax performance of a learning system and its complexity. There will be four lectures. The first will review the formulation of the pattern classification problem, and several popular pattern classification methods, and present general risk bounds in terms of Rademacher averages, a measure of the complexity of a class of functions. The second lecture will consider pattern classification in a minimax setting, and show that, in this setting, the Vapnik-Chervonenkis dimension is the key measure of complexity. The third lecture will focus on a theme of computational complexity. It will present the elegant relationship between the complexity of a class, as measured by its VC-dimension, and the computational complexity of functions from the class. This lecture will also review general results on the computational complexity of the pattern classification problem, and its tight relationship with that of an associated empirical risk optimization problems. The fourth lecture will consider large margin classification methods, such as AdaBoost, support vector machines, and neural networks, viewing them as convex relaxations of intractable empirical minimization problems. It will review several statistical properties of these large margin methods, in particular, a characterization of the convex optimization problems that lead to accurate classifiers, and relationships between these methods and probability models.
Author: Peter L. Bartlett, Berkeley , University Of California