Hedging Predictions in Machine Learning

Abstract

Recent advances in machine learning make it possible to design efficient\nprediction algorithms for data sets with huge numbers of parameters. This paper\ndescribes a new technique for "hedging" the predictions output by many such\nalgorithms, including support vector machines, kernel ridge regression, kernel\nnearest neighbours, and by many other state-of-the-art methods. The hedged\npredictions for the labels of new objects include quantitative measures of\ntheir own accuracy and reliability. These measures are provably valid under the\nassumption of randomness, traditional in machine learning: the objects and\ntheir labels are assumed to be generated independently from the same\nprobability distribution. In particular, it becomes possible to control (up to\nstatistical fluctuations) the number of erroneous predictions by selecting a\nsuitable confidence level. Validity being achieved automatically, the remaining\ngoal of hedged prediction is efficiency: taking full account of the new\nobjects' features and other available information to produce as accurate\npredictions as possible. This can be done successfully using the powerful\nmachinery of modern machine learning.\n