On the Existence and Convergence of Computable Universal Priors
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.
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",
address = "Berlin",
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).",
}