Classifying under Computational Resource Constraints: Anytime Classification Using Probabilistic Estimators

In many online applications of machine learning, the computational resources available for classification will vary from time to time. Existing techniques are designed to operate within the constraints of the minimum expected resources and fail to utilize further resources when they are available. This paper presents an analysis of the relevant categories of computational resource involved and presents an algorithm that starts with the classification time and accuracy of naive Bayes, utilizing additional CPU time to increase classification accuracy.