Classifying under computational resource constraints: anytime classification using probabilistic estimators

Ying Yang, Geoffrey I. Webb, Kevin B. Korb, Kai Ming Ting

Abstract

In dynamic environments such as real-time fraud detection or interactive recommender systems, computational resources are often unpredictable. Traditional machine learning models typically follow an "all-or-nothing" execution pattern, requiring a fixed time budget to produce a result. This paper introduces Anytime Averaged Probabilistic Estimators (AAPE), a framework designed for anytime classification. AAPE utilizes an ordered ensemble of efficient Bayesian estimators to provide a valid prediction at any moment, with accuracy monotonically increasing as more computational time is allocated.

Introduction

Real-world online applications frequently face fluctuating CPU availability. During peak traffic, a system may have only milliseconds to respond, whereas idle periods offer significantly more processing time. Standard models are often optimized for the worst-case scenario, deploying the fastest but least accurate model (e.g., Naive Bayes) to ensure responsiveness. This approach wastes idle resources that could otherwise be used to improve prediction quality.

The challenge of anytime classification is to create a model that can be interrupted at any point to provide a "best-so-far" result, while also refining its predictions if additional time is granted. AAPE addresses this by decomposing classification into a sequence of incremental improvement steps.

The AAPE Framework

The AAPE framework operates by ensembling an ordered sequence of probabilistic estimators. It primarily utilizes Naive Bayes (NB) as a baseline and SuperParent-One-Dependence Estimators (SPODEs) for refinement. SPODEs extend NB by allowing each attribute to depend on both the class and a single "super-parent" attribute, capturing more complex relationships at a modest computational cost.

The AAPE framework architecture, distinguishing between the offline training phase and the online anytime classification phase.

As illustrated in the framework's architecture, the process is divided into two distinct phases: training and classification. Within these phases, the system follows a four-stage "road map":

  1. Identify (Training): Select a suite of probabilistic estimators, starting with Naive Bayes and followed by various SPODEs.
  2. Order (Training): Determine the sequence in which estimators should be executed. Since the interruption time is unknown, the most beneficial estimators must run first.
  3. Invoke (Classification): At runtime, execute the estimators in the pre-determined order until the time budget is exhausted.
  4. Ensemble (Classification): Average the probability estimates from all completed estimators to produce the final prediction.

Ordering Strategies

The efficacy of AAPE depends heavily on the ordering of estimators. The authors evaluated seven metrics to optimize this sequence, including:

  • Forward Sequential Addition (FSA): A greedy approach that adds the estimator providing the greatest improvement to the current ensemble.
  • Cross-Validation (CV): Uses internal validation to rank estimators.
  • Frequency (FEQ) and Random (RAN): Simpler baselines based on attribute frequency or random selection.

FSA and CV emerged as the most effective strategies. While FSA provides the highest accuracy, it requires more training time. CV serves as a faster alternative that still delivers strong performance.

Experimental Evaluation

AAPE was evaluated using 60 benchmark datasets from the UCI Machine Learning Repository, covering diverse domains such as medical diagnosis and financial analysis. The datasets varied in scale, ranging from 32 to nearly 100,000 instances and 3 to 166 attributes.

Key Results

  • Accuracy and Monotonicity: AAPE significantly outperformed standard Naive Bayes across the majority of datasets. Crucially, classification error generally decreased as more SPODEs were processed, confirming the framework's ability to utilize extra time effectively.
  • Efficiency: The system remains highly efficient. Classification complexity scales linearly with the number of attributes ($O(m^2k)$), making it suitable for high-throughput environments.
  • Robustness: By starting with Naive Bayes, AAPE ensures a stable, low-variance baseline even under extreme time pressure. Subsequent SPODEs act as refinements that reduce the bias inherent in the simple NB model.

Conclusion and Future Work

AAPE provides a practical solution for classification under varying resource constraints. By leveraging the incremental nature of Bayesian frequency tables, it offers a flexible "anytime" capability that outperforms static models.

Future research directions include extending the framework to handle continuous data without discretization and exploring the integration of other model types, such as Decision Trees or SVMs, into the anytime ensemble. Additionally, optimizing for multi-dimensional constraints—such as simultaneous time and memory limits—remains an open challenge.

Summary updated

Abstract

In many online applications of machine learning, the computational resources available for classification will vary from time to time. Most techniques are designed to operate within the constraints of the minimum expected resources and fail to utilize further resources when they are available. We propose a novel anytime classification algorithm, anytime averaged probabilistic estimators (AAPE), which is capable of delivering strong prediction accuracy with little CPU time and utilizing additional CPU time to increase classification accuracy. The idea is to run an ordered sequence of very efficient Bayesian probabilistic estimators (single improvement steps) until classification time runs out. Theoretical studies and empirical validations reveal that by properly identifying, ordering, invoking and ensembling single improvement steps, AAPE is able to accomplish accurate classification whenever it is interrupted. It is also able to output class probability estimates beyond simple 0/1-loss classifications, as well as adeptly handle incremental learning.
BibTeX
@article{yang2007classifying,
  author = {Ying Yang and Geoffrey I. Webb and Kevin B. Korb and Kai Ming Ting},
  title = {{Classifying under computational resource constraints: anytime classification using probabilistic estimators}},
  journal = {Machine Learning},
  year = {2007},
  doi = {10.1007/s10994-007-5020-z},
}
Figure