Université Paris 6
Pierre et Marie Curie
Université Paris 7
Denis Diderot

CNRS U.M.R. 7599
``Probabilités et Modèles Aléatoires''

On the rate of convergence of regularized boosting classifiers


Code(s) de Classification MSC:

Résumé: 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 a surprisingly large class of distributions, the probability of error converges to the Bayes risk at a rate $n^{-(V+2)/(4(V+1))}$ where $V$ is the {\sc 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.

Mots Clés: classification ; regularized boosting ; rates of convergence ; model selection ; decision stumps ; additive models

Date: 2003-05-07

Prépublication numéro: PMA-818

Front pages : PMA-818.dvi