Why Simple Theories Win: Marcus Hutter on Occam's Razor, Compression and Kolmogorov Complexity

Hutter starts with the classic statement of Occam's razor: do not multiply entities beyond necessity. In a scientific setting, that means that if two theories or models describe the data equally well, you should pick the simpler one. He is careful to say it is not a provable law, but a principle that appears to work.

He calls it probably the most important principle in science, alongside logical deduction and experimental design. Science is about finding models of the world, and one can always build crazy complex models that explain everything but predict nothing. Simple models, by contrast, seem to have predictive power, and he gives two ways to respond to that fact: simply accept it as the principle of science, or look for a deeper principle that explains it.

His own answer is that if you assume the world is governed by simple rules, then a bias toward simplicity is the right mechanism for finding those rules. In the quantitative framework he returns to later, Solomonoff induction, one can rigorously prove that under this assumption Occam's razor is the best you can do in a certain sense.

Asked why humans find simplicity beautiful, as with E equals mc squared, Hutter reaches for evolution. Understanding regularities in the world is necessary for survival: if you see something moving in a bush and decide it is a tiger, you live. Humans are prone to finding more patterns than actually exist, like the face on Mars, but that bias is a price worth paying when the patterns are real.

Hutter describes Solomonoff induction as a theory he believes essentially solves the old problem of induction. In the narrow sense, induction means inferring models from data, and in the wide sense it also includes using those models to predict. His example is a sequence of one hundred 1s: the natural guess for what comes next is another 1, because a simple pattern is more plausible than a sudden change.

To make this formal, models must be written in a formal language, such as programs on a general-purpose computer or Turing machine. A program that prints 100 ones, then 100 zeros, then 100 ones is a possible model, but a program that just loops on printing 1 is shorter. Pushed to the extreme, you look for the shortest program that reproduces your data and keeps running, and you use its continuation as your prediction. The same logic gives a counter for the sequence 1, 2, 3, 4, 5.

The theory also handles noisy data. For a biased coin that lands heads 60 percent of the time, the method will eventually predict heads with 60 percent probability. It does this by combining Occam's razor with Epicurus's principle, which says not to discard any hypothesis that fits the data. Technically, shorter programs get a higher prior weight, precisely 2 to the minus the program's complexity, and predictions come from the resulting Bayesian mixture.

Lex Fridman asks about compression, a word Hutter uses often. For Hutter it simply means finding short programs, or more loosely simple theories and short descriptions, for the data or phenomenon at hand. He sees all of science as an endeavor of compression, perhaps all of humanity, while allowing that experimental design is a separate decision-making step meant to collect extra knowledge.

Once the data is in hand, he says, he sees no difference between compression, understanding and prediction. He then defines Kolmogorov complexity by analogy with a self-extracting archive: the shortest possible one that reproduces a file, including its own decompressor. Its length is the Kolmogorov complexity, arguably the true information content of the data, so redundant or boring data has low complexity.

On whether the universe itself can be summarized, Hutter says that based on the evidence he believes the whole universe is very simple, with a very short description that, once run, reproduces everything. Noise complicates this picture, and he jokes that it makes a scientist's life much harder. But even chaotic phenomena, like a thrown die, behave effectively like noise, so statistics cannot be avoided.

Hutter says that if there were no noise, one could in principle describe the universe with the standard model, general relativity and simple initial conditions, then just run it. But if you take a subset, such as planet Earth, it cannot be compressed into a couple of equations. The whole might be simple while a small window onto it is hugely complex, which he finds counterintuitive.

His analogy is the library of all possible 500-page books, starting with a book of only As and working through every variation. A very short program can generate this entire library, so the library has essentially zero information content. Yet pick out a subset of it, such as the books that make sense, and suddenly you have a lot of information.

Fridman then raises cellular automata, and Hutter calls Conway's Game of Life a prime example of simple rules producing rich phenomena. Its rules can be explained to a child and simulated by hand, and it is even Turing complete, so it can simulate any computer. He says this answers the doubt that chemistry and biology could rest on simple rules, since quantum electrodynamics already describes all of chemistry, and he claims intelligence can be described by a single equation.

He adds that you never really understand things, you just get used to them. He recalls programming the Mandelbrot set in assembler on a black-and-white monitor, and returning to it over the years. By solving high-order polynomials to locate the centers and sizes of its recursive copies, he slowly gained a feeling for why it looks the way it does.

Asked whether one could reverse engineer the short program behind a fractal, Hutter says yes in principle. You enumerate all programs and run them in parallel, a technique called dovetailing, giving the first program half the resources, the second a quarter, and so on. Whenever a program halts with output that matches your data, you keep it, and over time you find shorter and shorter ones.

The catch is that you can never know whether the current program is the shortest, because a still shorter one might simply be slower and need more time. Asymptotically, and after finite time, you do reach the shortest program, so the method is theoretically complete but completely impractical. It is the link between Solomonoff induction and Kolmogorov complexity.

With resource limits taken into account, things get harder. Pseudo-random number generators produce deterministic sequences that no fast, polynomial-time algorithm can tell apart from randomness. That creates a real challenge for any search for simple programs in artificial intelligence, and Hutter ends by marveling that human minds could find the simple rules of the universe at all, since it could have been otherwise.