TR on Soft Margins for AdaBoost

[raetsch@zoo.brain.riken.go.jp]

Dear Connectionists,

A new paper on a Soft Margin approach for AdaBoost is available:

``Soft Margins for AdaBoost'', G. R\"atsch, T. Onoda, K.-R. M\"uller,
NeuroColt2 TechReport NC-TR-1998-021.

http://www.first.gmd.de/~raetsch/Neurocolt_Margin.ps.gz

Comments and questions are welcome. Please contact me at raetsch at first.gmd.de.

Thanks, 

Gunnar R\"atsch

 
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
  understanding 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 {\em hard margin}
  distribution, i.e. the algorithm concentrates its resources on a few
  hard-to-learn patterns (here an interesting overlap emerge to
  Support Vectors).  This is clearly a sub-optimal strategy in the
  noisy case. 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 AdaBoost$_{Reg}$ 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 algorithms are useful and competitive for noisy data.