Cost-Sensitive Tree of Classifiers

Abstract

Recently, machine learning algorithms have successfully entered large-scale real-world industrial applications (e.g. search engines and email spam filters). Here, the CPU cost during test time must be budgeted and accounted for. In this paper, we address the challenge of balancing the test-time cost and the classifier accuracy in a principled fashion. The test-time cost of a classifier is often dominated by the computation required for feature extraction-which can vary drastically across eatures. We decrease this extraction time by constructing a tree of classifiers, through which test inputs traverse along individual paths. Each path extracts different features and is optimized for a specific sub-partition of the input space. By only computing features for inputs that benefit from them the most, our cost sensitive tree of classifiers can match the high accuracies of the current state-of-the-art at a small fraction of the computational cost.

References in corpus (12)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• The Greedy Miser: Learning under Test-time Budgets
• Fast classification using sparse decision DAGs

Cited by in corpus (14)

• Cascade Learning by Optimally Partitioning
• Classification with Costly Features as a Sequential Decision-Making Problem
• Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction
• Partition-wise Linear Models
• Consistent Estimation for Partition-wise Regression and Classification Models
• Anytime Stereo Image Depth Estimation on Mobile Devices
• Learning Tree-Structured Detection Cascades for Heterogeneous Networks of Embedded Devices
• Cascaded Classifier for Pareto-Optimal Accuracy-Cost Trade-Off Using off-the-Shelf ANNs
• Effective Medical Test Suggestions Using Deep Reinforcement Learning
• Learning Dynamic Feature Selection for Fast Sequential Prediction
• Gradient Regularized Budgeted Boosting
• Trading-Off Cost of Deployment Versus Accuracy in Learning Predictive Models
• Robust Text Classifier on Test-Time Budgets
• Cost-Sensitive Feature-Value Acquisition Using Feature Relevance