STABILITY AND GENERALIZATION ERROR
Dr Andre Elisseeff, Barnhill Technologies

Abstract: Classical studies in statistical learning theory use combinatorial quantities to bound the generalization error of learning systems. In this talk, we will discuss a different approach based on stability properties of the learning system. By defining a stable learner as a system for which the learned solution does not change much with small changes in the training set, we will derive bounds that do not depend on any measure of the complexity of the hypothesis space (e.g. VC dimension). The bounds depend rather on how the learning algorithm searches this space, and can thus be applied even when the VC dimension is infinite. We will give general results and show how they can be applied to well known methods such as regularization methods, Support Vector Machines and methods related to the Maximum Relative Entropy Discrimination.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 5 February 2001.

back