Boosting Active Learning to Optimality: a Tractable Monte-Carlo, Billiard-based Algorithm

Philippe Rolet 1 Michèle Sebag 2 Olivier Teytaud 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
3 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : 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.
Type de document :
Communication dans un congrès
ECML, 2009, Bled, Slovenia. pp.302-317, 2009
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00433866
Contributeur : Olivier Teytaud <>
Soumis le : vendredi 20 novembre 2009 - 13:17:05
Dernière modification le : mercredi 28 novembre 2018 - 15:36:02
Document(s) archivé(s) le : jeudi 30 juin 2011 - 11:57:56

Fichier

BALO.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00433866, version 1

Collections

Citation

Philippe Rolet, Michèle Sebag, Olivier Teytaud. Boosting Active Learning to Optimality: a Tractable Monte-Carlo, Billiard-based Algorithm. ECML, 2009, Bled, Slovenia. pp.302-317, 2009. 〈inria-00433866〉

Partager

Métriques

Consultations de la notice

2518

Téléchargements de fichiers

631