|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-01-097
2001-097
Marginal
Boosting
Gunnar Ratsch
Manfred K. Warmuth
ABSTRACT
AdaBoost
produces a linear combination of weak hypotheses. It has been observed
in practice that the generalization error of the algorithm continues
to improve even after all examples are
classified correctly by the current linear combination, i.e.\ by a
\emph{hyperplane} in feature space where each weak hypothesis is a
dimension. The improvement is attributed to the experimental observation
that the distances (margins) of the examples to the separating hyperplane
are increasing even when the training error is already zero, i.e.\
all examples are on the correct side of the hyperplane. We give an
iterative version of AdaBoost that explicitly maximizes the minimum
margin of the examples. We bound the number of iterations and the
number of hypotheses used in the final linear combination which approximates
the maximum margin hyperplane with a certain precision. This result
is shown to be independent from the
size of the hypothesis class -- even infinite hypothesis classes are
allowed.
Download
PDF
|