Solomonoff's universal prior (algorithmic probability)
Statement
Solomonoff defined a universal semimeasure on finite binary strings: the a priori probability of a string is (up to normalization) the sum over all programs on a fixed universal machine that output that string of 2^{-L(p)}, where L(p) is program length. This yields a formal theory of inductive inference: prediction by Bayesian updating with this prior is optimal in a certain sense among computable semimeasures. The construction predates and motivates Kolmogorov complexity and is central to algorithmic probability and universal artificial intelligence.
Formula
M(x) ∝ ∑_{U(p)=x} 2^{-L(p)}
Equation
Universal semimeasure; Bayes + Occam (short programs dominate)
Proof sketch
Solomonoff, "A Formal Theory of Inductive Inference," Information and Control 7 (1964), Part I and Part II. Proofs use computability theory and measure on the space of programs; convergence properties of predictors relative to computable stochastic sources.
Source
Solomonoff, R. J. A formal theory of inductive inference. Information and Control 7 (1964), 1–22, 224–254.
Domains
mathematics, computer-science
People
Related
- Theorem: Solomonoff's universal prior (algorithmic probability)
- Proof: Solomonoff's universal prior (algorithmic probability)