3-5 juil. 2013 Villeneuve d'Ascq (Lille) (France)

Par auteur > Kégl Balázs

Vendredi 5
Apprentissage Automatique

› 12:00 - 12:30 (30min)
Fast classification using sparse decision DAGs
Djalel Benbouzid  1, 2@  , Róbert Busa-Fekete  1, 3  , Balázs Kégl  1, 2  
1 : Laboratoire de l'Accélérateur Linéaire  (LAL)  -  Site web
CNRS : UMR8607, IN2P3, Université Paris XI - Paris Sud
Centre Scientifique d'Orsay B.P. 34 91898 ORSAY Cedex -  France
2 : Laboratoire de Recherche en Informatique  (LRI)  -  Site web
CNRS : UMR8623, Université Paris XI - Paris Sud
LRI - Bâtiment 490 Université Paris-Sud 91405 Orsay Cedex -  France
3 : Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and University of Szeged

In this paper we propose an algorithm that builds sparse decision DAGs (directed acyclic graphs) from a list of base classifiers provided by an external learning method such as AdaBoost. The basic idea is to cast the DAG design task as a Markov decision process. Each instance can decide to use or to skip each base classi- fier, based on the current state of the classifier being built. The result is a sparse decision DAG where the base classifiers are selected in a data-dependent way. The method has a single hyperparameter with a clear semantics of controlling the accuracy/speed trade-off. The algorithm is competitive with state-of-the-art cas- cade detectors on three object-detection benchmarks, and it clearly outperforms them when there is a small number of base classifiers. Unlike cascades, it is also readily applicable for multi-class classification. Using the multi-class setup, we show on a benchmark web page ranking data set that we can significantly improve the decision speed without harming the performance of the ranker. 

Personnes connectées : 1