Machine learning and statistical inference are the primary building blocks for systems that predict the future from the past. Prediction algorithms have been tailored to fit various applications as varied as analytics, healthcare, and judicial decision-making. One of the major concerns when utilizing prediction algorithms to automate risk-critical applications is reliability. In particular, a guarantee on the error rate of any automated system is highly desirable.
To guarantee an error rate for an overall prediction system, a meta-algorithm should refuse to make a prediction when the meta-algorithm infers that the base prediction algorithm is likely enough to be in error. The implications of refusing to make a prediction may vary according to the application of interest. For example, in a medical diagnosis system, refusing to make a prediction may result in the collection of more information about the patient or a request to a human expert to make a decision based on a more thorough evaluation.
Inspired by the prediction with expert advice framework, we propose SafePredict, an online meta-algorithm that accepts or refuses predictions of a base algorithm depending on the previous performance of the base algorithm. SafePredict asymptotically bounds the error to the desired level without any assumption on the data or the base predictor. When the base predictor happens to meet the target error rate, the meta-algorithm will refuse to predict only a finite number of times. When the error rate of the base predictor varies over time, SafePredict will adapt to those changes while preserving the error guarantee. Empirical results on real and synthetic data show that SafePredict can more reliably follow a target error rate than the most prominent refusal algorithms. Furthermore, one can obtain yet fewer refusals by employing SafePredict on top of other refusal mechanisms.
Featured Group Publications
M.A. Kocak, D. Ramirez, E. Erkip, and D.E. Shasha. “SafePredict: A Meta-Algorithm for Machine Learning That Uses Refusals to Guarantee Correctness”. Submitted to IEEE Transactions on Pattern Analysis and Machine Intelligence, August 2017.