The Greedy Miser: Learning under Test-time Budgets
arXiv:1206.6451
Abstract
As machine learning algorithms enter applications in industrial settings, there is increased interest in controlling their cpu-time during testing. The cpu-time consists of the running time of the algorithm and the extraction time of the features. The latter can vary drastically when the feature set is diverse. In this paper, we propose an algorithm, the Greedy Miser, that incorporates the feature extraction cost during training to explicitly minimize the cpu-time during testing. The algorithm is a straightforward extension of stage-wise regression and is equally suitable for regression or multi-class classification. Compared to prior work, it is significantly more cost-effective and scales to larger data sets.
Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)
Cited by in corpus (18)
- Cost-Sensitive Tree of Classifiers
- The Expando-Mono-Duo Design Pattern for Text Ranking with Pretrained Sequence-to-Sequence Models
- Classification with Costly Features as a Sequential Decision-Making Problem
- Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction
- Dynamic Feature Acquisition Using Denoising Autoencoders
- Pruning Random Forests for Prediction on a Budget
- Learning Anytime Predictions in Neural Networks via Adaptive Loss Balancing
- Anytime Stereo Image Depth Estimation on Mobile Devices
- Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
- SpeedMachines: Anytime Structured Prediction
- Efficient Feature Group Sequencing for Anytime Linear Prediction
- Learning Tree-Structured Detection Cascades for Heterogeneous Networks of Embedded Devices
- Dynamic Model Selection for Prediction Under a Budget
- Learning Dynamic Hierarchical Models for Anytime Scene Labeling
- Gradient Regularized Budgeted Boosting
- Cost-Sensitive Feature-Value Acquisition Using Feature Relevance
- Field of Groves: An Energy-Efficient Random Forest
- Adaptive Covariate Acquisition for Minimizing Total Cost of Classification