Skip to Main content Skip to Navigation
Poster communications

Bandit-Aided Boosting

Róbert Busa-Fekete 1, 2 Balázs Kégl 1, 2, 3
3 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
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.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

http://hal.in2p3.fr/in2p3-00580588
Contributor : Sabine Starita <>
Submitted on : Monday, March 28, 2011 - 4:01:06 PM
Last modification on : Wednesday, September 16, 2020 - 5:08:06 PM
Long-term archiving on: : Wednesday, June 29, 2011 - 2:35:42 AM

File

OPT2009-BusaFekete.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : in2p3-00580588, version 1

Collections

Citation

Róbert Busa-Fekete, Balázs Kégl. Bandit-Aided Boosting. OPT 2009: 2nd NIPS Workshop on Optimization for Machine Learning, Dec 2009, Whistler, Canada. ⟨in2p3-00580588⟩

Share

Metrics

Record views

571

Files downloads

328