previous  home  search LaTeX  -  PostScript  -  PDF  -  Html/Gif contact    up    next

## On the Existence and Convergence of Computable Universal Priors

 Author: Marcus Hutter (2003) Comments: 15 pages Subj-class: Probability Theory; Compexity; Learning Reference: Proceedings of the 14th International Conference on Algorithmic Learning Theory (ALT 2003) pages 298-312 Report-no: IDSIA-05-03 and cs.LG/0305052 Paper: LaTeX  -  PostScript  -  PDF  -  Html/Gif Slides: PostScript - PDF

Keywords: Sequence prediction; Algorithmic Information Theory; Solomonoff's prior; universal probability; mixture distributions; posterior convergence; computability concepts; Martin-Löf randomness.

Abstract: Solomonoff unified Occam's razor and Epicurus' principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. His central result is that the posterior of his universal semimeasure M converges rapidly to the true sequence generating posterior μ, if the latter is computable. Hence, M is eligible as a universal predictor in case of unknown μ. We investigate the existence and convergence of computable universal (semi)measures for a hierarchy of computability classes: finitely computable, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not finitely computable, and to dominate all enumerable semimeasures. We define seven classes of (semi)measures based on these four computability concepts. Each class may or may not contain a (semi)measure which dominates all elements of another class. The analysis of these 49 cases can be reduced to four basic cases, two of them being new. We also investigate more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for Martin-Löf random sequences. We introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues.

 previous  home  search LaTeX  -  PostScript  -  PDF  -  Html/Gif contact    up    next

### BibTeX Entry

@InProceedings{Hutter:03unipriors,
author =       "Marcus Hutter",
title =        "On the Existence and Convergence of Computable Universal Priors",
booktitle =    "Proceedings of the 14th International Conference
on Algorithmic Learning Theory ({ALT-2003})",
editor =       "Ricard Gavald{\'a} and Klaus P. Jantke and Eiji Takimoto",
series =       "Lecture Notes in Artificial Intelligence",
volume =       "2842",
publisher =    "Springer",
pages =        "298--312",
month =        sep,
year =         "2003",
ISSN =         "0302-9743",
http =         "http://www.hutter1.net/ai/uniprior.htm",
url =          "http://arxiv.org/abs/cs.LG/0305052",
ftp =          "ftp://ftp.idsia.ch/pub/techrep/IDSIA-05-03.ps.gz",
keywords =     "Sequence prediction; Algorithmic Information Theory;
Solomonoff's prior; universal probability;
mixture distributions; posterior convergence;
computability concepts; Martin-L{\"o}f randomness.",
abstract =     "Solomonoff unified Occam's razor and Epicurus' principle
of multiple explanations to one elegant, formal, universal theory
of inductive inference, which initiated the field of algorithmic
information theory. His central result is that the posterior of
his universal semimeasure $M$ converges rapidly to the true
sequence generating posterior $\mu$, if the latter is computable.
Hence, $M$ is eligible as a universal predictor in case of unknown
$\mu$. We investigates the existence, computability and convergence of
universal (semi)measures for a hierarchy of computability classes:
finitely computable, estimable, (co)enumerable, and approximable.
For instance, $\MM(x)$ is known to be enumerable, but not finitely
computable, and to dominates all enumerable semimeasures.
We define seven classes of (semi)measures based on these four
computability concepts. Each class may or may not contain a
(semi)measures which dominates all elements of another class. The
analysis of these 49 cases can be reduced to four basic cases, two
of them being new. We present proofs for discrete and continuous
semimeasures.
We also investigate more closely the type of convergence, possibly
implied by universality (in difference and in ratio, with probability
1, in mean sum, and for Martin-L{\"o}f random sequences).",
}

 previous  home  search LaTeX  -  PostScript  -  PDF  -  Html/Gif contact    up    next