inria-00433866, version 1
Boosting Active Learning to Optimality: a Tractable Monte-Carlo, Billiard-based Algorithm
Philippe Rolet
1Michèle Sebag
2Olivier Teytaud
1, 2, 3
ECML (2009) 302-317
Résumé : Abstract. This paper focuses on Active Learning with a limited num- ber of queries; in application domains such as Numerical Engineering, the size of the training set might be limited to a few dozen or hundred exam- ples due to computational constraints. Active Learning under bounded resources is formalized as a finite horizon Reinforcement Learning prob- lem, where the sampling strategy aims at minimizing the expectation of the generalization error. A tractable approximation of the optimal (in- tractable) policy is presented, the Bandit-based Active Learner (BAAL) algorithm. Viewing Active Learning as a single-player game, BAAL com- bines UCT, the tree structured multi-armed bandit algorithm proposed by Kocsis and Szepesv´ri (2006), and billiard algorithms. A proof of a principle of the approach demonstrates its good empirical convergence toward an optimal policy and its ability to incorporate prior AL crite- ria. Its hybridization with the Query-by-Committee approach is found to improve on both stand-alone BAAL and stand-alone QbC.
- 1 : Laboratoire de Recherche en Informatique (LRI)
- CNRS : UMR8623 – Université Paris XI - Paris Sud
- 2 : TAO (INRIA Saclay - Ile de France)
- INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
- 3 : TAO (INRIA Futurs)
- INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
- Domaine : Mathématiques/Optimisation et contrôle
- inria-00433866, version 1
- http://hal.inria.fr/inria-00433866
- oai:hal.inria.fr:inria-00433866
- Contributeur : Olivier Teytaud
- Soumis le : Vendredi 20 Novembre 2009, 13:17:05
- Dernière modification le : Vendredi 20 Novembre 2009, 14:11:19






Documents associés
Exporter