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 semimeasureMconverges rapidly to the true sequence generating posterior μ, if the latter is computable. Hence,Mis 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,Mis 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 |

@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 |