SCIENCE@home

Convergence and Loss Bounds for Bayesian Sequence Prediction

Marcus Hutter

Published 2003 in IEEE Transactions on Information Theory

ABSTRACT

The probability of observing x/sub t/ at time t, given past observations x/sub 1/...x/sub t-1/ can be computed if the true generating distribution /spl mu/ of the sequences x/sub 1/x/sub 2/x/sub 3/... is known. If /spl mu/ is unknown, but known to belong to a class /spl Mscr/ one can base one's prediction on the Bayes mix /spl xi/ defined as a weighted sum of distributions /spl nu/ /spl isin/ /spl Mscr/. Various convergence results of the mixture posterior /spl xi//sub t/ to the true posterior /spl mu//sub t/ are presented. In particular, a new (elementary) derivation of the convergence /spl xi//sub t///spl mu//sub t/ /spl rarr/ 1 is provided, which additionally gives the rate of convergence. A general sequence predictor is allowed to choose an action y/sub t/ based on x/sub 1/...x/sub t-1/ and receives loss /spl lscr//sub x(t)y(t)/ if x/sub t/ is the next symbol of the sequence. No assumptions are made on the structure of /spl lscr/ (apart from being bounded) and /spl Mscr/. The Bayes-optimal prediction scheme /spl Lambda//sub /spl xi// based on mixture /spl xi/ and the Bayes-optimal informed prediction scheme /spl Lambda//sub /spl mu// are defined and the total loss L/sub /spl xi// of /spl Lambda//sub /spl xi// is bounded in terms of the total loss L/sub /spl mu// of /spl Lambda//sub /spl mu//. It is shown that L/sub /spl xi// is bounded for bounded L/sub /spl mu// and L/sub /spl xi///L/sub /spl mu// /spl rarr/ 1 for L/sub /spl mu// /spl rarr/ /spl infin/. Convergence of the instantaneous losses is also proven.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-20 of 20 references · Page 1 of 1

CITED BY

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