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.
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":
- Identify (Training): Select a suite of probabilistic estimators, starting with Naive Bayes and followed by various SPODEs.
- Order (Training): Determine the sequence in which estimators should be executed. Since the interruption time is unknown, the most beneficial estimators must run first.
- Invoke (Classification): At runtime, execute the estimators in the pre-determined order until the time budget is exhausted.
- 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