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",
  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).",
}
      
 previous  home  search  LaTeX  -  PostScript  -  PDF  -  Html/Gif   contact    up    next