TY - JOUR

T1 - On generalized computable universal priors and their convergence

AU - Hutter, Marcus

PY - 2006/11/2

Y1 - 2006/11/2

N2 - 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 the 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 μ. The first part of the paper investigates the existence and convergence of computable universal (semi) measures for a hierarchy of computability classes: recursive, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not estimable, and to dominate all enumerable semimeasures. We present proofs for discrete and continuous semimeasures. The second part investigates 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. In particular, we show that convergence fails (holds) on generalized-random sequences in gappy (dense) Bernoulli classes.

AB - 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 the 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 μ. The first part of the paper investigates the existence and convergence of computable universal (semi) measures for a hierarchy of computability classes: recursive, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not estimable, and to dominate all enumerable semimeasures. We present proofs for discrete and continuous semimeasures. The second part investigates 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. In particular, we show that convergence fails (holds) on generalized-random sequences in gappy (dense) Bernoulli classes.

KW - Algorithmic information theory

KW - Computability concepts

KW - Martin-Löf randomness

KW - Mixture distributions

KW - Posterior convergence

KW - Sequence prediction

KW - Solomonoff's prior

KW - Universal probability

UR - http://www.scopus.com/inward/record.url?scp=34548228002&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2006.07.039

DO - 10.1016/j.tcs.2006.07.039

M3 - Article

SN - 0304-3975

VL - 364

SP - 27

EP - 41

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -