Skip to Main content Skip to Navigation
Conference papers

Fast boosting using adversarial bandits

R. Busa-Fekete 1 Balázs Kégl 1, 2, 3
2 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 improve the computational complexity of 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 where each arm represents a subset of the base classifier set. The MAB gradually learns the ''usefulness'' 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 main improvement of this paper over a previous approach is that we use an adversarial bandit algorithm instead of stochastic bandits. This choice allows us to prove a weak-to-strong-learning theorem, which means that the proposed technique remains a boosting algorithm in a formal sense. We demonstrate on benchmark datasets that our technique can achieve a generalization performance similar to standard AdaBoost for a computational cost that is an order of magnitude smaller.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

http://hal.in2p3.fr/in2p3-00614564
Contributor : Sabine Starita <>
Submitted on : Friday, August 12, 2011 - 12:30:38 PM
Last modification on : Tuesday, April 21, 2020 - 1:07:22 AM
Document(s) archivé(s) le : Sunday, November 13, 2011 - 2:21:13 AM

File

Busa-Fekete.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : in2p3-00614564, version 1

Collections

Citation

R. Busa-Fekete, Balázs Kégl. Fast boosting using adversarial bandits. 27th International Conference on Machine Learning (ICML 2010), Jun 2010, Haifa, Israel. pp.143-150. ⟨in2p3-00614564⟩

Share

Metrics

Record views

898

Files downloads

564