Bandit-Aided BoostingReport as inadecuate

Bandit-Aided Boosting - Download this document for free, or read online. Document in PDF available to download.

1 LAL - Laboratoire de l-Accélérateur Linéaire 2 LRI - Laboratoire de Recherche en Informatique 3 TAO - Machine Learning and Optimisation LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623

Abstract : In this paper we apply multi-armed bandits MABs to accelerate ADABOOST. ADABOOST constructs a strong classifier in a stepwise fashion by selecting simple base classifiers and using their weighted -vote- to determine the final classification. We model this stepwise base classifier selection as a sequential decision problem, and optimize it with MABs. Each arm represent a subset of the base classifier set. The MAB gradually learns the -utility- of the subsets, and selects one of the subsets in each iteration. ADABOOST then searches only this subset instead of optimizing the base classifier over the whole space. The reward is defined as a function of the accuracy of the base classifier. We investigate how the MAB algorithms UCB, UCT can be applied in the case of boosted stumps, trees, and products of base classifiers. On benchmark datasets, our bandit-based approach achieves only slightly worse test errors than the standard boosted learners for a computational cost that is an order of magnitude smaller than with standard ADABOOST.

Author: R. Busa-Fekete - B. Kégl -



Related documents