Abstract
Machine learning algorithms have successfully entered industry through many real-world applications (e.g., search engines and product recommendations). In these applications, the test-time CPU cost must be budgeted and accounted for. In this paper, we examine two main components of the test-time CPU cost, classifier evaluation cost and feature extraction cost, and show how to balance these costs with the classifier accuracy. Since the computation required for feature extraction dominates the test-time cost of a classifier in these settings, we develop two algorithms to efficiently balance the performance with the test-time cost. Our first contribution describes how to construct and optimize 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. Our second contribution is a natural reduction of the tree of classifiers into a cascade. The cascade is particularly useful for class-imbalanced data sets as the majority of instances can be early-exited out of the cascade when the algorithm is sufficiently confident in its prediction. Because both approaches only compute features for inputs that benefit from them the most, we find our trained classifiers lead to high accuracies at a small fraction of the computational cost.
Introduction
In high-scale machine learning environments like search engines or real-time recommendation systems, accuracy is not the sole objective. Every millisecond of CPU time spent on feature extraction and model inference translates to operational costs and potential degradation in user experience. This research addresses the "test-time budget" problem: optimizing predictive performance when features vary significantly in their computational cost.
Standard machine learning models often assume features are readily available. However, in practice, extracting complex features—such as deep image descriptors or linguistic parses—can be orders of magnitude more expensive than the model's prediction itself. The core insight of this work is that not every input requires every feature; "easy" instances can be handled with cheap features, while "hard" cases justify the expense of high-fidelity data.
Proposed Architectures: Trees and Cascades
The authors propose two primary structures to manage this trade-off: the Cost-Sensitive Tree of Classifiers (CSTC) and the Cost-Sensitive Cascade of Classifiers (CSCC).
Cost-Sensitive Tree of Classifiers (CSTC)
In a CSTC, each node acts as a classifier that determines the next path for an input. This allows the model to partition the input space and develop "specialist" branches. For example, one branch might specialize in high-relevance documents using expensive features, while another filters out low-quality noise using only cheap, surface-level features.
Cost-Sensitive Cascade of Classifiers (CSCC)
The cascade is a specialized tree structure optimized for imbalanced datasets, such as spam filtering or face detection. It prioritizes "early-exiting" the majority of negative instances using inexpensive features at early stages, reserving expensive computation only for ambiguous or likely positive cases.
Technical Implementation
To optimize these structures, the authors introduce several key technical innovations:
- Soft Traversal: To make the discrete routing decisions in a tree differentiable for gradient-based optimization, the model uses a sigmoidal "soft belief" during training. This allows the entire tree to be optimized simultaneously.
- Mixed-Norm Regularization: A mixed $l_1/l_2$ norm is employed to encourage feature reuse. The objective function explicitly rewards the model for selecting features that have already been "paid for" by ancestor nodes in the path.
- Gradient Boosting Integration: To handle non-linearities, the framework can be applied to the outputs of Gradient Boosted Regression Trees (GBRT), combining the power of boosting with cost-sensitive routing.
Experimental Results
The methods were evaluated across diverse datasets, including synthetic benchmarks, Yahoo! Learning to Rank (LTR), and a cost-sensitive version of MNIST.
- Yahoo LTR: On a dataset of 473k documents with explicit CPU costs, CSTC maintained high ranking accuracy (NDCG@5) while reducing computational costs by nearly 50% compared to standard stage-wise regression and prior state-of-the-art methods.
- Cost-Sensitive MNIST: The model learned to classify clear digits using ultra-low 4x4 resolution images, only "unlocking" higher resolutions (up to 28x28) for ambiguous cases where digits were difficult to distinguish.
Conclusion
By moving away from static feature sets and toward input-dependent feature selection, CSTC and CSCC provide a robust framework for high-performance machine learning under strict computational budgets. These models demonstrate that significant efficiency gains are possible by treating feature extraction as a dynamic, cost-aware decision process.
Reference: Xu, Z., Kusner, M. J., Weinberger, K. Q., Chen, M., & Chapelle, O. (2014). Classifier Cascades and Trees for Minimizing Feature Evaluation Cost. Journal of Machine Learning Research, 15, 2113-2144.
Summary updated