Learning for Anytime Classification

Many on-line applications of machine learning require that the learned classifiers complete classification within strict real-time constraints. In consequence, efficient classifiers such as naive Bayes (NB) are often employed that can complete the required classification tasks even under peak computational loads. While NB provides acceptable accuracy, more computationally intensive approaches can improve thereon. The current paper explores techniques that utilize any additional computational resources available at classification time to improve upon the prediction accuracy of NB. This is achieved by augmenting NB with a sequence of super-parent one-dependence estimators. As many of these are evaluated as possible within the available computational resources and the resulting set of probability estimates aggregated to produce a final prediction. The algorithm is demonstrated to provide consistent improvements in accuracy as computational resources are increased.