General Loss Bounds for Universal Sequence Prediction

By Marcus Hutter. 2001

17 citations recorded by the source corpus.

The Bayesian framework is ideally suited for induction problems. The probability of observing $x_t$ at time $t$, given past observations $x_1...x_{t-1}$ can be computed with Bayes'' rule if the true distribution $\mu$ of the sequences $x_1x_2x_3...$ 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 $\xi$ is defined as a weighted sum of distributions $\mu_i\!\in\!M$, where $M$ is any countable set of distributions including $\mu$. This is a generalization of Solomonoff induction, in which $M$ is the set of all enumerable semi-measures. Systems which predict $y_t$, given $x_1...x_{t-1}$ and which receive loss $l_{x_t y_t}$ if $x_t$ is the true next symbol of the sequence are considered. It is proven that using the universal $\xi$ as a prior is nearly as good as using the unknown true distribution $\mu$. Furthermore, games of chance, defined as a sequence of bets, observations, and rewards are studied. The time needed to reach the winning zone is bounded in terms of the relative entropy of $\mu$ and $\xi$. Extensions to arbitrary alphabets, partial and delayed prediction, and more active systems are discussed.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Financial market prediction system with Evolino neural network and Delphi method (2013, background): “The recent work of Hutter provides general and sharp loss bounds (Hutter 2001): Let LM ( n ) and Lp ( n ) be the total expected unit losses of the M -predictor and the p -predictor, respectively, for the first n events.”
The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions (2002, methodology): “This dominance is all we need to apply Hutter’s recent loss bounds [9]:”