Transductive Confidence Machine Is Universal

Authors: Ilia Nouretdinov, Vladimir V'yugin and Alex Gammerman.

Source: Lecture Notes in Artificial Intelligence Vol. 2842, 2003, 283 - 297.

Abstract. Vovk's Transductive Confidence Machine (TCM) is a practical prediction algorithm giving, in additions to its predictions, confidence information valid under the general iid assumption. The main result of this paper is that the prediction method used by TCM is universal under a natural definition of what ``valid'' means: any prediction algorithm providing valid confidence information can be replaced, without losing much of its predictive performance, by a TCM. We use as the main tool for our analysis the Kolmogorov theory of complexity and algorithmic randomness.

©Copyright 2003 Springer