Solomonoff induction

Ray Solomonoff defined an inference system that will learn to correctly predict any computable sequence with only the absolute minimum amount of data. This system, in a certain sense, is the perfect universal prediction algorithm. To summarize it very informally, Solomonoff induction works by:

• Starting with all possible hypotheses (sequences) as represented by computer programs (that generate those sequences), weighted by their simplicity (2^-n, where n is the program length);
• Discarding those hypotheses that are inconsistent with the data.

Weighting hypotheses by simplicity, the system automatically incorporates a form of Occam's razor, which is why it has been playfully referred to as Solomonoff's lightsaber.

Solomonoff induction gets off the ground with a solution to the "problem of the priors". Suppose that you stand before a universal prefix Turing machine $U$. You are interested in a certain finite output string $y_{0}$. In particular, you want to know the probability that $U$ will produce the output $y_{0}$ given a random input tape. This probability is the Solomonoff a priori probability of $y_{0}$.

More precisely, suppose that a particular infinite input string $x_{0}$ is about to be fed into $U$. However, you know nothing about $x_{0}$ other than that each term of the string is either $0$ or $1$. As far as your state of knowledge is concerned, the $i$th digit of $x_{0}$ is as likely to be $0$ as it is to be $1$, for all $i=1,2,\ldots$. You want to find the a priori probability $m(y_{0})$ of the following proposition:

(*) If $U$ takes in $x_{0}$ as input, then $U$ will produce output $y_{0}$ and then halt.

Unfortunately, computing the exact value of $m(y_{0})$ would require solving the halting problem, which is undecidable. Nonetheless, it is easy to derive an expression for $m(y_{0})$. If $U$ halts on an infinite input string $x$, then $U$ must read only a finite initial segment of $x$, after which $U$ immediately halts. We call a finite string $p$ a self-delimiting program if and only if there exists an infinite input string $x$ beginning with $p$ such that $U$ halts on $x$ immediately after reading to the end of $p$. The set ${\mathcal {P}}$ of self-delimiting programs is the prefix code for $U$. It is the determination of the elements of ${\mathcal {P}}$ that requires a solution to the halting problem.

Given $p\in {\mathcal {P}}$, we write "$\operatorname {prog} (x_{0})=p$" to express the proposition that $x_{0}$ begins with $p$, and we write "$U(p)=y_{0}$" to express the proposition that $U$ produces output $y_{0}$, and then halts, when fed any input beginning with $p$. Proposition (*) is then equivalent to the exclusive disjunction

$\bigvee _{p\in {\mathcal {P}}\colon U(p)=y_{0}}(\operatorname {prog} (x_{0})=p).$

Since $x_{0}$ was chosen at random from $\{0,1\}^{\omega }$, we take the probability of $\operatorname {prog} (x_{0})=p$ to be $2^{-\ell (p)}$, where $\ell (p)$ is the length of $p$ as a bit string. Hence, the probability of (*) is

$m(y_{0}):=\sum _{p\in {\mathcal {P}}\colon U(p)=y_{0}}2^{-\ell (p)}.$

Blog posts

• An Intuitive Explanation of Solomonoff Induction by lukeprog and Alex_Altair

See also

• Kolmogorov complexity
• AIXI
• Occam's razor

References

• Algorithmic probability on Scholarpedia