|
NeuroCOLT
Technical Report NC-TR-98-020
Margin
Distribution Bounds on Generalization
John Shawe-Taylor
RHUL
Nello Cristianini
University of Bristol
Keywords:
Received:
17-JUL-98
Abstract
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. Freund and Schapire [6] 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 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.
Download Compressed Postscript
|