Classifier Cascade for Minimizing Feature Evaluation Cost

Minmin Chen, Zhixiang Eddie Xu, Kilian Q. Weinberger, Olivier Chapelle, Dor KedemAISTATS 2012 · OpenReview

Abstract

Machine learning algorithms are increasingly used in large-scale industrial settings. Here, the operational cost during test-time has to be taken into account when an algorithm is designed. This operational cost is affected by the average running time and the computation time required for feature extraction. When a diverse set of features is used, the latter can vary drastically. In this paper we propose an algorithm that constructs a cascade of classifiers that explicitly trades-off operational cost and classifier accuracy while accounting for on-demand feature extraction costs. Different from previous work, our algorithm re-optimizes trained classifiers and allows expensive features to be scheduled at any stage within the cascade to minimize overall cost. Experiments on actual web-search ranking data sets demonstrate that our framework leads to drastic test-time improvements.

Introduction

In large-scale industrial systems like web search engines or spam filters, test-time latency is a critical constraint. While academic research often prioritizes accuracy, industrial applications must balance performance with infrastructure costs. The challenge lies in two areas: the discrepancy between average and worst-case processing times, and the varying costs of feature acquisition. For instance, simple metadata is cheap to fetch, whereas deep content analysis is computationally expensive.

Existing "cascade" methods often rely on greedy heuristics or pre-assigned feature stages. This paper introduces Cronus, an algorithm designed to globally optimize a classifier cascade. Cronus intelligently re-weights and re-orders pre-trained weak learners (such as decision trees) to discard "easy" negative instances early using inexpensive features, reserving costly computations for ambiguous cases.

Methodology: The Cronus Framework

Cronus operates as a post-processing optimization for existing ensembles, such as Gradient Boosted Regression Trees (GBRT). It constructs a multi-stage pipeline where each stage can decide to either exit with a prediction or pass the instance to the next, more complex stage.

The Cronus Cascade Architecture

Key Technical Innovations

  • Mixed-Norm Regularization: To model feature costs, Cronus employs a weighted $\ell_1/\ell_2$ mixed-norm. This penalizes the initial acquisition of a feature heavily but allows its subsequent use in later stages at no additional cost, encouraging feature sparsity across the cascade.
  • Soft Cascades: The discrete "exit or continue" decision is modeled using a sigmoid-based "soft" indicator function. This makes the objective function differentiable, enabling gradient-based optimization of stage weights and thresholds.
  • Cyclic Optimization: The non-convex optimization problem is addressed by iteratively optimizing one stage at a time while keeping others fixed.
  • Convex Initialization: A robust starting point is found by solving a convex sub-problem where each stage is treated as a potential final stage.

Experimental Results

The framework was evaluated on the Yahoo Learning to Rank Challenge dataset, comprising over 470,000 documents. This dataset is highly imbalanced (~9.5% relevance), mirroring real-world search scenarios where most documents are irrelevant to a specific query. Features were assigned realistic costs ranging from 1 to 200 units.

Performance Trade-off Comparison

Key Findings

  • Superior Trade-offs: Cronus significantly outperformed standard GBRT and other state-of-the-art methods like Soft-Cascade and AND-OR structures. It achieved comparable precision to a full GBRT model at a fraction of the test-time cost.
  • Intelligent Scheduling: The optimization naturally learned to schedule cheap features (cost 1-5) in early stages and reserve expensive features (cost 100+) for the final stages.
  • Automatic Stage Pruning: Although initialized with 10 stages, the optimization often collapsed redundant stages, resulting in a more efficient 4-stage effective cascade.

Conclusion

Cronus provides a principled approach to minimizing test-time costs by optimizing the average path an instance takes through a model. By "failing fast" on easy negatives, it preserves computational budget for difficult instances. While highly effective for imbalanced ranking tasks, future work could explore its application in balanced multi-class problems and methods to train weak learners specifically for the cascade structure.

Summary updated

Abstract

Machine learning algorithms are increasingly used in large-scale industrial settings. Here, the operational cost during test-time has to be taken into account when an algorithm is designed. This operational cost is affected by the average running time and the computation time required for feature extraction. When a diverse set of features is used, the latter can vary drastically. In this paper we propose an algorithm that constructs a cascade of classifiers that explicitly trades-off operational cost and classifier accuracy while accounting for on-demand feature extraction costs. Different from previous work, our algorithm re-optimizes trained classifiers and allows expensive features to be scheduled at any stage within the cascade to minimize overall cost. Experiments on actual web-search ranking data sets demonstrate that our framework leads to drastic test-time improvements.
BibTeX
@inproceedings{chen2012classifier,
  author = {Minmin Chen and Zhixiang Eddie Xu and Kilian Q. Weinberger and Olivier Chapelle and Dor Kedem},
  title = {{Classifier Cascade for Minimizing Feature Evaluation Cost}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=aPu2j5QHist},
}
Figure