SCIENCE@home

General Loss Bounds for Universal Sequence Prediction

Marcus Hutter

Published 2001 in International Conference on Machine Learning

ABSTRACT

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.

PUBLICATION RECORD

  • Publication year

    2001

  • Venue

    International Conference on Machine Learning

  • Publication date

    2001-01-21

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv cs/0101019
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-24 of 24 references · Page 1 of 1

CITED BY

Showing 1-17 of 17 citing papers · Page 1 of 1