On Boosting Improvement: Error Reduction and Convergence Speed-up

Abstract

Boosting is not only the most efficient ensemble learning method in practice, but also the one based on the most robust theoretical properties. The adaptive update of the sample distribution, which tends to increase the weight of the misclassified examples, allows to improve the performance of any learning algorithm. However, its ability to avoid overfitting has been challenged when boosting is applied to noisy data. This situation is frequent with the modern databases, built thanks to new data acquisition technologies, such as the Web. The convergence speed of boosting is also penalized on such databases, where there is a large overlap of probability density functions of the classes to learn (large Bayesian error). In this article, we propose a slight modification of the weight update rule of the algorithm Adaboost . We show that by exploiting an adaptive measure of a local entropy, computed from a neighborhood graph built on the examples, it is possible to identify not only the outliers but also the examples located in the Bayesian error region. Taking into account this information, we correct the weight of the examples to improve the boosting performances. A broad experimental study shows the interest of our new algorithm, called i Adaboost .