version française rss feed
HAL : in2p3-00711150, version 1

Fiche détaillée  Récupérer au format
29th International Conference on Machine Learning (ICML 2012), Edinburgh : Royaume-Uni (2012)
Fast classification using sparse decision DAGs
R. Busa-Fekete1, 2, D. Benbouzid1, 2, B. Kégl1, 2, 3

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.
1 :  LAL - Laboratoire de l'Accélérateur Linéaire
2 :  LRI - Laboratoire de Recherche en Informatique
3 :  INRIA Saclay - Ile de France - TAO

Informatique/Environnements Informatiques pour l'Apprentissage Humain

Sciences de l'Homme et Société/Education
Liste des fichiers attachés à ce document : 
Fast_classification.pdf(382.7 KB)