Paper available

[Jonathan Baxter]

The following paper is available from
http://wwwsyseng.anu.edu.au/~jon/papers/doom2.ps.gz


"Boosting Algorithms as Gradient Descent in Function Space"

                                                  by

Llew Mason, Jonathan Baxter, Peter Bartlett and Marcus Frean


Abstract:

Much recent attention, both experimental and theoretical, has been
focussed on classification algorithms which produce voted combinations
of classifiers.  Recent theoretical work has shown that the impressive
generalization performance of algorithms like AdaBoost can be
attributed to the classifier having large margins on the training
data.

We present abstract algorithms for finding linear and convex
combinations of functions that minimize arbitrary cost functionals (i.e
functionals that do not necessarily depend on the margin). Many
existing voting methods can be shown to be special cases
of these abstract algorithms. Then, following previous theoretical
results
bounding the generalization performance of convex combinations of
classifiers in terms of general cost functions of the margin, we
present a new algorithm (DOOM II) for performing a gradient descent
optimization of such cost functions.

Experiments on several data sets from the UC Irvine repository
demonstrate that DOOM II generally outperforms AdaBoost, especially in
high noise situations.  Margin distribution plots verify that DOOM II
is willing to `give up' on examples that are too hard in order to avoid
overfitting.  We also show that the overfitting behavior exhibited by
AdaBoost can be quantified in terms of our proposed cost function.