On generalized computable universal priors and their convergence

DOI10.1016/J.TCS.2006.07.039zbMATH Open1110.03031DBLPjournals/tcs/Hutter06arXivcs/0503026OpenAlexW2120361535WikidataQ58012433 ScholiaQ58012433MaRDI QIDQ860822FDOQ860822

Authors: Marcus Hutter 

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

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 the 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. 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-Loef 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.

Full work available at URL: https://arxiv.org/abs/cs/0503026

Recommendations

• On the existence and convergence of computable universal priors
• (Non-)Equivalence of Universal Priors
• A universal prior distribution for Bayesian consistency of non parametric procedures
• Consensus priors in the presence of general laws
• On convergence of posterior distributions
• Common priors under incomplete information: a unification
• scientific article; zbMATH DE number 1849136
• Posterior concentration and fast convergence rates for generalized Bayesian learning
• The Uniform Distribution as a Universal Prior

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Martin-L%EF%BF%BD%EF%BF%BDf+randomness&go=Go Martin-L��f randomness]sequence predictionalgorithmic information theorymixture distributionsposterior convergencecomputability conceptsSolomonoff's prioruniversal probability

Mathematics Subject Classification ID

Computational learning theory (68Q32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Theory of Program Size Formally Identical to Information Theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Title not available (Why is that?)
• Von Mises' definition of random sequences reconsidered
• Minimum description length induction, Bayesianism, and Kolmogorov complexity
• Complexity-based induction systems: Comparisons and convergence theorems
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• Title not available (Why is that?)
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
• Sequence prediction based on monotone complexity.
• Algorithmic Learning Theory
• On the existence and convergence of computable universal priors

Cited In (10)

• On Martin-Löf (non-)convergence of Solomonoff's universal mixture
• Title not available (Why is that?)
• Algorithmic Learning Theory
• Open problems in universal induction \& intelligence
• On the existence and convergence of computable universal priors
• On universal prediction and Bayesian confirmation
• The semimeasure property of algorithmic probability -- ``feature or ``bug?
• (Non-)Equivalence of Universal Priors
• A generalized characterization of algorithmic probability
• An optimal superfarthingale and its convergence over a computable topological space

This page was built for publication: On generalized computable universal priors and their convergence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q860822)