Online Region Prediction with Real Teachers
In the online prediction scenario the predictor’s task is to predict the label of an object given by Nature at each trial, based on the labels for the objects learned so far. At each trial Nature discloses the correct label for the current object, so the predictor is being taught. While this pure online scenario is convenient for theoretical studies, it is a poor model for many practical applications: the situation where the correct answers are given immediately after each prediction does not often occur in reality. In this work we suggest a more general scenario for online prediction, according to which correct answers may be given with some delay and not at every trial. We modify a particular class of region predictors, Transductive Confidence Machines, which have been proved to have several useful properties, to work in the new scenario, and find some sufficient conditions under which their rates of erroneous and uncertain predictions remain the same in the new online scenario as in the traditional one.