In the previous post, we defined sequential prediction: given x₁, …, xₙ₋₁, predict xₙ. But what’s the best possible predictor? Is there a theoretical gold standard against which we can measure all practical approaches?
Yes—and it’s called Solomonoff induction. The catch: it’s incomputable.
The Dream of Universal Prediction
Imagine a predictor that could:
- Learn any computable pattern
- Converge to the true distribution faster than any competitor
- Never be fooled by spurious correlations
- Automatically apply Occam’s razor
This isn’t science fiction—Solomonoff described exactly such a predictor in 1964. The only problem is that implementing it would require solving the halting problem.
Understanding why this ideal exists and why it’s incomputable illuminates the fundamental limits of learning and helps explain what practical algorithms are approximating.
Kolmogorov Complexity
Before we can understand Solomonoff induction, we need Kolmogorov complexity.
The Kolmogorov complexity K(x) of a string x is the length of the shortest program that outputs x:
K(x) = min { |p| : U(p) = x }
where U is a universal Turing machine and |p| is the length of program p in bits.
Intuition
Consider two strings:
A: 010101010101010101010101010101010101...
B: 011001110010110001011010011101000111...
String A has low Kolmogorov complexity: print("01" * 50) is short.
String B (random bits) has high complexity: the shortest program is essentially “print the string.”
Kolmogorov complexity captures the intuitive notion of “randomness” or “patternlessness.” A string is random if and only if it’s incompressible—if there’s no program shorter than the string itself.
Key Properties
Invariance: K(x) depends on the choice of universal machine only up to a constant. Different machines give K values that differ by at most O(1).
Uncomputability: K(x) is not computable. There’s no algorithm that takes x and returns K(x). (Proof: if K were computable, we could solve the halting problem.)
Upper bound: K(x) ≤ |x| + O(1). You can always just “print the string.”
Algorithmic Probability
Solomonoff’s algorithmic probability (or universal prior) assigns probability to each string x:
M(x) = Σ 2^(-|p|) for all programs p that output x
This sums over all programs that produce x, weighted by 2^(-length). Shorter programs contribute more.
The key insight: simpler explanations get more probability mass.
If x can be produced by a 10-bit program, it gets at least 2^(-10) = 0.001 probability. If the shortest program producing y is 1000 bits, y gets at most 2^(-1000) ≈ 0 probability.
Solomonoff’s Universal Prior
For sequential prediction, Solomonoff proposed using M as a prior over infinite sequences. The probability of the next bit being 1 given history h is:
P(1 | h) = M(h·1) / M(h)
where h·1 denotes h followed by 1, and M(h) is the probability of sequences starting with h.
This is just Bayes’ rule: condition the universal prior on what we’ve seen.
Why It’s Optimal
Theorem (Solomonoff, 1964): Solomonoff induction converges to the true distribution faster than any computable predictor, for any computable source.
More precisely, if the true distribution is μ and we denote Solomonoff’s predictor by M, then the expected total squared prediction error is bounded:
E_μ[ Σₙ (M(xₙ | x<n) - μ(xₙ | x<n))² ] ≤ K(μ) × ln(2)
where K(μ) is the Kolmogorov complexity of the true distribution.
This means:
- Total error is finite, bounded by complexity of the true source
- Per-symbol error goes to zero
- Convergence is faster for “simpler” true distributions
Why It’s Incomputable
Solomonoff induction requires:
Enumerating all programs: We’d need to consider every possible Turing machine.
Solving the halting problem: To compute M(x), we need to know which programs halt and output x. But determining whether a program halts is undecidable.
Summing infinitely many terms: Even if each term were computable, we’d need to sum over infinitely many programs.
The halting problem alone makes exact computation impossible. There’s no algorithm that computes M(x) for arbitrary x.
Practical Implications
If we can’t compute Solomonoff induction, why study it?
1. It Sets the Standard
Solomonoff induction is what we’re approximating when we build practical predictors. It tells us what optimal looks like, even if we can’t achieve it.
2. It Justifies Occam’s Razor
The success of Solomonoff induction explains why preferring simpler hypotheses works. It’s not just a heuristic—it’s provably optimal (in a well-defined sense).
3. It Guides Algorithm Design
Good practical algorithms should:
- Have an implicit simplicity bias
- Perform some form of model averaging
- Be universal over some model class
Context Tree Weighting, which we’ll explore later in this series, can be seen as Solomonoff induction restricted to tree-generating programs.
Computable Approximations
Since Solomonoff itself is out of reach, we use restricted model classes:
| Method | Model Class | Universality |
|---|---|---|
| Solomonoff | All computable | Yes (but incomputable) |
| CTW | Tree sources | No, but includes Markov |
| PPM | Variable-order Markov | No, heuristic |
| Neural LMs | Learned representations | No, but very flexible |
CTW is particularly elegant: it performs exact Bayesian inference over all tree structures, giving provable optimality for a rich subclass of computable sources.
The Hierarchy of Predictors
Solomonoff Induction (incomputable, optimal)
↓
Restricted Model Classes
↓
┌───────┴────────┐
CTW PPM (efficient, provable for subclass)
(tree sources) (heuristic)
↓
N-gram Models (simple, limited)
↓
Neural LMs (flexible, data-hungry)
Each step down trades some generality for computability. CTW is special because it maintains Bayesian optimality within its (quite general) model class.
Connection to Learning Theory
Solomonoff induction connects to broader themes in machine learning:
No Free Lunch: Any computable predictor will fail on some computable sequences. Solomonoff is the best we can do “on average” under the algorithmic probability measure.
Bias-Variance: Solomonoff’s implicit prior implements perfect regularization—complex hypotheses are downweighted but not excluded.
PAC Learning: Solomonoff converges with finite expected error, satisfying a form of probably approximately correct learning.
Key Takeaways
- Solomonoff induction is the theoretically optimal predictor for any computable sequence
- It assigns algorithmic probability: shorter programs → higher probability
- It’s incomputable due to the halting problem
- Practical algorithms approximate it via restricted model classes
- CTW achieves Solomonoff-like optimality for tree-structured sources
- Understanding the ideal helps us design and evaluate practical methods
What’s Next
The next post develops the Bayesian framework that underlies both Solomonoff induction and its practical approximations like CTW. We’ll see how model averaging—maintaining distributions over hypotheses rather than committing to one—is the key to robust prediction.
Further Reading
- Solomonoff, R. J. (1964). “A formal theory of inductive inference.” Information and Control.
- Li, M., & Vitányi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications.
- Hutter, M. (2005). Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability.
Discussion