previous home search |
LaTeX (51kb)
PostScript (209kb)
PDF (193kb)
Html/Gif
| contact up next |

## General Loss Bounds for Universal Sequence Prediction

Author:Marcus Hutter (2001) Comments:8 LaTeX two-column pages Subj-class:Artificial Intelligence; Learning; ACM-class:

I.2; I.2.6; I.2.8; F.1.3 Reference:Proceedings of the 18th International Conference on Machine Learning (ICML-2001) 210-217, Morgan Kaufmann Report-no:IDSIA-03-01 and cs.AI/0101019 Paper:LaTeX (51kb) PostScript (209kb) PDF (193kb) Html/Gif Slides:PostScript - PDF

Keywords:Bayesian sequence prediction; general loss function; Solomonoff induction; Kolmogorov complexity; learning; universal probability; loss bounds; games of chance; partial and delayed prediction; classification.

Abstract:The Bayesian framework is ideally suited for induction problems. The probability of observingxat time_{k}k, given past observationsxcan be computed with Bayes' rule if the true distribution µ of the sequences_{1}...x_{k-1}xis 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_{1}x_{2}x_{3}...ßis defined as a weighted sum of distributionsµin_{i}M, whereMis any countable set of distributions includingµ. This is a generalization of Solomonoff induction, in whichMis the set of all enumerable semi-measures. Systems which predicty, given_{k}xand which receive loss_{1}...x_{k-1}lif_{xk yk}xis the true next symbol of the sequence are considered. It is proven that using the universal_{k}ß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.

previous home search |
LaTeX (51kb)
PostScript (209kb)
PDF (193kb)
Html/Gif
| contact up next |

## Table of Contents

Introduction

- Induction
- Universal Sequence Prediction
- Contents
Setup and Convergence

- Strings and Probability Distributions
- Universal Prior Probability Distribution
- (Probability Classes)
Loss Bounds

- Unit Loss Function
- Proof Sketch of Loss Bound
- General Loss
Application to Games of Chance

- Introduction/Example
- Games of Chance
- Information-Theoretic Interpretation
Outlook

- General Alphabet
- Partial Prediction, Delayed Prediction, Classification
- More Active Systems
- The Weighted Majority Algorithm(s)
- Miscellaneous
- Summary

previous home search |
LaTeX (51kb)
PostScript (209kb)
PDF (193kb)
Html/Gif
| contact up next |

@Article{Hutter:01loss, author = "Marcus Hutter", title = "General Loss Bounds for Universal Sequence Prediction", number = "IDSIA-03-01", institution = "Istituto Dalle Molle di Studi sull'Intelligenza Artificiale", address = "Manno(Lugano), CH", month = june, year = "2001", pages = "210--217", journal = "Proceedings of the $18^{th}$ International Conference on Machine Learning (ICML-2001)", publisher = "Morgan Kaufmann" url = "http://www.hutter1.net/official/ploss.htm", url2 = "http://arxiv.org/abs/cs.AI/0101019", ftp = "ftp://ftp.idsia.ch/pub/techrep/IDSIA-03-01.ps.gz", categories = "I.2. [Artificial Intelligence], I.2.6. [Learning], I.2.8. [Problem Solving, Control Methods and Search], F.1.3. [Complexity Classes].", keywords = "Bayesian and deterministic prediction; general loss function; Solomonoff induction; Kolmogorov complexity; leaning; universal probability; loss bounds; games of chance; partial and delayed prediction; classification.", abstract = "The Bayesian framework is ideally suited for induction problems. The probability of observing $x_k$ at time $k$, given past observations $x_1...x_{k-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_k$, given $x_1...x_{k-1}$ and which receive loss $l_{x_k y_k}$ if $x_k$ 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 estimated. Extensions to arbitrary alphabets, partial and delayed prediction, and more active systems are discussed.", }

previous home search |
LaTeX (51kb)
PostScript (209kb)
PDF (193kb)
Html/Gif
| contact up next |