1081 articles – 5254 Notices  [english version]
HAL : in2p3-00711150, version 1

Fiche concise  Récupérer au format
Fast classification using sparse decision DAGs
Busa-Fekete R., Benbouzid D., Kégl B.
Dans Proceedings of the 29th International Conference on Machine Learning (ICML-12) - 29th International Conference on Machine Learning (ICML 2012), Edinburgh : Royaume-Uni (2012) - http://hal.in2p3.fr/in2p3-00711150
Informatique/Apprentissage
Informatique/Environnements Informatiques pour l'Apprentissage Humain
Sciences de l'Homme et Société/Education
Fast classification using sparse decision DAGs
R. Busa-Fekete1, 2, D. Benbouzid1, 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
DIGITEO Bat. Claude Shannon - Université de Paris-Sud, Bâtiment 660, 91190 Gif-sur-Yvette
France
APPSTAT
In this paper we propose an algorithm that builds sparse decision DAGs (directed acyclic graphs) out of 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 classifier, 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 cascade detectors on three object-detection benchmarks, and it clearly outperforms them in the regime of low 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.

Communications avec actes
2012
29/06/2012
Proceedings of the 29th International Conference on Machine Learning (ICML-12)
internationale
J.Langford, J. Pineau
951-958
Omnipress

29th International Conference on Machine Learning (ICML 2012)
Edinburgh
Royaume-Uni
26/06/2012
01/07/2012

LAL 12-223
ISBN: 978-1-4503-1285-1
Liste des fichiers attachés à ce document : 
PDF
Fast_classification.pdf(382.7 KB)