Criterion of Calibration for Transductive Confidence Machine with Limited Feedback

Authors: Ilia Nouretdinov and Vladimir Vovk .

Source: Lecture Notes in Artificial Intelligence Vol. 2842, 2003, 259 - 267.

Abstract. This paper is concerned with the problem of on-line prediction in the situation where some data is unlabelled and can never be used for prediction, and even when data is labelled, the labels may arrive with a delay. We construct a modification of randomised Transductive Confidence Machine for this case and prove a necessary and sufficient condition for its predictions being calibrated, in the sense that in the long run they are wrong with a prespecified probability under the assumption that data is generated independently by same distribution. The condition for calibration turns out to be very weak: feedback should be given on more than a logarithmic fraction of steps.

©Copyright 2003 Springer