General loss bounds for universal sequence prediction

Abstract

The Bayesian framework is ideally suited for induction problems. The probability of observing xk at time k, given past observations x1...xk-1 can be computed with Bayes' rule if the true distribution µ of the sequences x1x2x3... is known. The problem, however, is that in many cases one does not even have a reasonable estimate of the true distribution. In order to overcome this problem a universal distribution ß is defined as a weighted sum of distributions µi in M, where M is any countable set of distributions including µ. This is a generalization of Solomonoff induction, in which M is the set of all enumerable semi-measures. Systems which predict yk, given x1...xk-1 and which receive loss lxk yk if xk is the true next symbol of the sequence are considered. It is proven that using the universal ß as a prior is nearly as good as using the unknown true distribution µ. Furthermore, games of chance, defined as a sequence of bets, observations, and rewards are studied. The time needed to reach the winning zone is estimated. Extensions to arbitrary alphabets, partial and delayed prediction, and more active systems are discussed. Show more