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

By author > Busa-Fekete Róbert

Friday 5
Machine Learning

› 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)  -  Website
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)  -  Website
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. 


Online user: 1