s'authentifier
version française rss feed
HAL : in2p3-00580588, version 1

Fiche concise  Récupérer au format
Bandit-Aided Boosting
Busa-Fekete R., Kégl B.
OPT 2009: 2nd NIPS Workshop on Optimization for Machine Learning, Whistler : Canada (2009) - http://hal.in2p3.fr/in2p3-00580588
Informatique/Performance et fiabilité
Informatique/Algorithme et structure de données
Bandit-Aided Boosting
R. Busa-Fekete1, 2, B. Kégl1, 2, 3
1 :  LAL - Laboratoire de l'Accélérateur Linéaire
http://www.lal.in2p3.fr/
CNRS : UMR8607 – IN2P3 – Université Paris XI - Paris Sud
Centre Scientifique d'Orsay B.P. 34 91898 ORSAY Cedex
France
2 :  LRI - Laboratoire de Recherche en Informatique
http://www.lri.fr/
CNRS : UMR8623 – Université Paris Sud
LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex
France
3 :  INRIA Saclay - Ile de France - TAO
http://tao.lri.fr/tiki-index.php
INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
France
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.

Communications sans actes
12/12/2009

OPT 2009: 2nd NIPS Workshop on Optimization for Machine Learning
Poster
Whistler
Canada
12/12/2009
12/12/2009
R. Busa-Fekete

LAL 09-319

Liste des fichiers attachés à ce document : 
PDF
OPT2009-BusaFekete.pdf(454.5 KB)