Solomonoff Induction

Solomonoff induction is an inference system defined by 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. 

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

Unfortunately, computing the exact value of m(y0) would require solving the halting problem, which is undecidable. Nonetheless, it is easy to derive an expression for m(y0). 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 𝒫𝒫 of self-delimiting programs is the prefix code for U. It is the determination of the elements of 𝒫𝒫 that requires a solution to the halting problem.

Given p ∈ 𝒫, we write "prog"prog (x0) = p" to express the proposition that x0 begins with p, and we write "U(p) = y0" to express the proposition that U produces output y0, and then halts, when fed any input beginning with p. Proposition (*) is then equivalent to the exclusive disjunction


p ∈ 𝒫: U(p) = y0(prog (x0) = p).
Since x0 was chosen at random from {0,{0, 1}ω, we take the probability of prog (x0) = p to be 2 − ℓ(p), where ℓ(ℓ(p) is the length of p as a bit string. Hence, the probability of (*) is


m(y0) := ∑p ∈ 𝒫: U(p) = y02 − ℓ(p).
 

Blog posts

Applied to Decoherence is Simple by Multicore at 1y