Fast classification using sparse decision DAGs

R. Busa-Fekete 1, 2 D. Benbouzid 3 B. Kégl 1, 2, 4
3 Appstat
LRI - Laboratoire de Recherche en Informatique, LAL - Laboratoire de l'Accélérateur Linéaire
4 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : 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.
Type de document :
Communication dans un congrès
J.Langford, J. Pineau. 29th International Conference on Machine Learning (ICML 2012), Jun 2012, Edinburgh, United Kingdom. Omnipress, pp.951-958, 2012


http://hal.in2p3.fr/in2p3-00711150
Contributeur : Sabine Starita <>
Soumis le : vendredi 22 juin 2012 - 15:12:39
Dernière modification le : mercredi 20 juillet 2016 - 09:44:52
Document(s) archivé(s) le : dimanche 23 septembre 2012 - 02:41:05

Fichier

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

Identifiants

  • HAL Id : in2p3-00711150, version 1

Collections

Citation

R. Busa-Fekete, D. Benbouzid, B. Kégl. Fast classification using sparse decision DAGs. J.Langford, J. Pineau. 29th International Conference on Machine Learning (ICML 2012), Jun 2012, Edinburgh, United Kingdom. Omnipress, pp.951-958, 2012. <in2p3-00711150>

Exporter

Partager

Métriques

Consultations de
la notice

314

Téléchargements du document

196