Fast classification using sparse decision DAGs

Abstract

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 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 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.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

Cited by in corpus (9)

• Cost-Sensitive Tree of Classifiers
• Learning Sampling Distributions for Efficient Object Detection
• Classification with Costly Features as a Sequential Decision-Making Problem
• Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction
• LogitBoost autoregressive networks
• Tree in Tree: from Decision Trees to Decision Graphs
• Gradient Regularized Budgeted Boosting
• Accelerating E-Commerce Search Engine Ranking by Contextual Factor Selection
• Adaptive Covariate Acquisition for Minimizing Total Cost of Classification