On the Rate of Convergence of Regularized Boosting Classifiers
Gilles Blanchard, Gábor Lugosi, Nicolas Vayatis; 4(Oct):861-894, 2003.
Abstract
A regularized boosting method is introduced, for which regularization
is obtained through a penalization function. It is shown through
oracle inequalities that this method is model adaptive. The rate of
convergence of the probability of misclassification is investigated.
It is shown that for
quite a large class of distributions, the probability of error
converges to the Bayes risk at a rate
faster than
n-(V+2)/(4(V+1)) where
V is the VC dimension
of the "base" class whose elements are combined by boosting methods
to obtain an aggregated classifier. The dimension-independent nature
of the rates may partially explain the good behavior of these methods
in practical problems. Under Tsybakov's noise condition the rate of
convergence is even faster. We investigate the conditions necessary to
obtain such rates for different base classes. The special case of
boosting using decision stumps is studied in detail. We characterize
the class of classifiers realizable by aggregating decision stumps. It
is shown that some versions of boosting work especially well in
high-dimensional logistic additive models. It appears that adding a
limited labelling noise to the training data may in certain cases
improve the convergence, as has been also suggested by other authors.
[abs][pdf][ps.gz][ps]
