ABSTRACT

Robust Bounds on Generalization from the Margin Distribution

Prof. John Shawe-Taylor

A number of results have bounded generalization of a classifier in terms of its margin on the training points. There has been some debate about whether the minimum margin is the best measure of the distribution of training set margin values with which to estimate the generalization, particularly in view of its lack of robustness. Freund and Schapire have shown how a different function of the margin distribution can be used to bound the number of mistakes of an on-line learning algorithm for a perceptron, as well as an expected error bound.

We will report on joint work with Nello Cristianini in which we show that a slight generalization of their construction can be used to give a pac style bound on the tail of the distribution of the generalization errors that arise from a given sample size. Algorithms arising from the approach are related to those of Cortes and Vapnik. We generalise the basic result to function classes with bounded fat shattering dimension and the l\_1 measure for slack variables which gives rise to Vapnik's box constraint algorithm. We also extend the analysis to the regression case and among other results obtain bounds on the probability of a randomly chosen point having error greater than a given value in terms of the least squares error on the training set.

Computer Science Home Page

Maintained by rbennett@cs.ucl.ac.uk