|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-98-021
Soft
Margins for AdaBoost
Gunnar Raetsch, Takashi Onoda, & Klaus-R. Mueller
GMD
Keywords:
AdaBoost, Arcing, Large Margin, Hard Margin, Soft Margin, Classification,
Support Vectors
Received:
10-AUG-98
Abstract
Recently ensemble methods like AdaBoost were
successfully applied to character recognition tasks, seemingly defying
the problems of overfitting. This paper shows that although AdaBoost
rarely overfits in the low noise regime it clearly does so for higher
noise levels. Central for under- standing this fact is the margin
distribution and we find that AdaBoost achieves - doing gradient descent
in an error function with respect to the margin - asymptotically a
hard margin distribution, i.e. the algorithm concentrates its resources
on a few hard-to-learn patterns (here an interesting overlap emerges
to Support Vectors). This is clearly a sub- optimal strategy in the
noisy case, and regularization, i.e. a mistrust in the data, must
be introduced in the algorithm to alleviate the distortions that a
dificult pattern (e.g. outliers) can cause to the margin distribution.
We propose several regularization methods and generalizations of the
original
AdaBoost algorithm to achieve a soft margin - a concept known from
Support Vector learning. In particular we suggest (1) regularized
AdaBoostReg using the soft margin directly in a modified loss function
and (2) regularized linear and quadratic programming (LP/QP-) AdaBoost,
where the soft margin is attained by introducing slack variables.
Extensive simulations demonstrate that the proposed regularized
AdaBoost- type algorithms are useful
and competitive for noisy data.
Download Compressed Postscript
|