Kolmogorov Complexity

In the previous chapter, we saw what coding theory tells us about compressing strings. If we treat letters of the text independently, coding theory is especially powerful. But that's an assumption that good compression algorithms can't make.

Kolmogorov complexity is a different approach to the same compressing question. It's the ultimate limit for how much a file can be compressed. This makes it a very powerful theoretical concept to have in our dictionary!

The Mandelbrot Set

Take a good look at the following picture.¹ It shows the Mandelbrot set—we color each pixel of the plane based on how quickly a certain sequence of numbers shoots to infinity.

If you take a screenshot of this picture and save it on your disk, it will take a few MB. But what if you instead save the instruction for how to create this image? All relevant ingredients are stored in the two boxes below the picture—the formula used to create it, and a bunch of numbers like the coordinates you are looking at. We are talking about less than a kilobyte of memory now. ²

This is the gist of Kolmogorov complexity. For any given object—represented as a binary string—its Kolmogorov complexity is the length of the shortest program that prints that string. This is the limit on how much a file can be compressed.

Here are a few more examples.

• Although digits of have many random-like properties, the Kolmogorov complexity of its first million digits is extremely small. That's because there are some extremely short programs printing it.
• Larger numbers (written down in binary) typically have larger Kolmogorov complexity. But there are huge numbers like with very small Kolmogorov complexity.
• Whenever you can zip a file to a size of 100 MB, you can say that "Kolmogorov complexity of the file is at most 100 MB"
• If you flip a fair coin times, the resulting sequence is likely to have Kolmogorov complexity of about . There's no good way of compressing it.

And here's one more example: The final riddle we haven't discussed yet—Hutter's challenge is the challenge of upper bounding the Kolmogorov complexity of 1GB of Wikipedia as much as possible.

Definition of Kolmogorov complexity

Kolmogorov complexity is a great concept that helps me think clearly about all kinds of things. The unfortunate part is that it takes a bit of time to get accustomed to it, and to understand some subtleties. The two main ones: How do we define it formally, and how do we compute it?

Kolmogorov vs entropy:

Both Kolmogorov complexity and entropy try to measure something very similar: complexity, information, compression limit. Naturally, they are closely connected! It's a bit hard to see this on the first glance though: Entropy talks about probabilities, and their logarithms. Kolmogorov complexity talks about computer programs and their length.

The connection goes like this: If you have a reasonable distribution () over bit strings and you sample from it (), then the entropy of the distribution is roughly equal to the expected Kolmogorov complexity of the sample. I.e.,

print('01000...010110')

If you look at the above example, you can notice that we did not really use that the distribution is uniform, it works pretty much for any distribution.³ I.e., you can think of the relation between the two as The entropy is the average Kolmogorov complexity.

The case of a uniform distribution is the most interesting one: it tells us that most -bit strings can't really be compressed, since their Kolmogorov complexity is close to . In fact, -bit strings with Kolmogorov complexity are called Kolmogorov random, to highlight the insight that bits are random if we can't compress them.

Solomonoff prior

Let's finish this minicourse where we started—with our Bayesian detective.

Bayes' rule and derived formulas like KL divergence are great to understand what's happening as we are getting more and more evidence. Yet, there's a big elephant in the room here—how should the detective set up her prior probabilities?

Solomonoff prior is the right answer to this question. It says:

Before we try to justify it, let's see it on an example.

A fishy situation

This time, our Bayesian detective isn't flipping a coin, but she has a black box with a button -- each press gives back one bit (a red or a blue chip), possibly correlated with the past outputs of the box.

Our detective pressed the button ten times and this is what she sees:

What now? You can notice that our detective is now in an opposite situation to the first chapter. In that chapter, she started with a fixed prior and we just focused on the evolution of that prior as she was getting evidence.

Now, she has the data and has to come up with some hypotheses and their priors. This is the situation that we find ourselves in much more often than the first-chapter situation. It's also much more dangerous: this is where we can fall into the trap of overfitting (discussed later).

Solomonoff gives the detective the following advice for what to do in our situation: just start with all possible hypotheses you can imagine and give each hypothesis a prior proportional to . Then compute the posterior.

In theory, this is an extremely appealing approach, and pretty much the answer for how to do statistics, if you ask me. In practice, there are two problems with this: First, we can't work with infinitely many hypotheses. Second, we can't compute their Kolmogorov complexity.

Computing priors

This sounds pretty bad but it's not the end of the world. To overcome the first problem, our detective may simply come up with a few plausible hypotheses after she sees the data. Most hypotheses have probabilities close to zero anyway.

Here are four of them:

• : Each dot is 50/50 red or blue, independently
• : Each dot is independently red with 60% probability
• : The sequence alternates red and blue—each time there's 10% probability of the other color, though.
• : The sequence alternates blocks of length five that are either "mostly red" (2/3 red probability) or "mostly blue" (2/3 blue probability)

The second problem is that we can't compute Kolmogorov complexity; and it's not even well-defined unless we fix some programming language. That's also not necessarily that bad. We can often get some reasonable approximation. Let me try to do it here:

• : I give this one zero bits of penalty, i.e., . This looks weird since all programs that generate this hypothesis as their output have to spend at least a few bits to do stuff like "print(0.5)". But this kind of constant overhead is the same for all four hypothesis and adding a constant to all log-priors does not change anything, so we might as well forget this and give 0 penalty to the simplest hypothesis—this one.
• : The difference between this and the previous hypothesis is that now we have to specify a number—0.6. If you asked me to start listing different numbers between 0 and 1 in order of how "simple" they are, I would probably list 0.6 somewhere around 20-50th place, so let me give this hypothesis a penalty of .
• : This hypothesis is more complicated than treating each dot independently, but we still have only two types of dots. I give this penalty of 3 bits since I can think of a bunch of different mechanisms roughly as simple as this one, even if this one is among the simplest. The number 0.9 seems roughly as "simple" as 0.6 to me, so I give it 5 bits. In total: .
• : This one seems the most complicated. I give 3 bits for alterations, and additional 3-4 more bits for the blocks having length 5. Finally, the number is actually pretty simple, so bits for that. In total: .

The following widget shows how these hypotheses fare on the data: ⁴

Some observations:

• If you compare and hypotheses, they both have almost the same likelihoods (-10 vs -9.71 bits). Seeing 10 data points is simply not enough to start making meaningful inferences about whether the bias is 50%, or only "close to 50% but not quite".
• hypothesis is making very strong predictions. Since it matches the data pretty well, it hence accumulated a lot of evidence in its favor. With just 10 data points, the evidence is roughly offset by its complexity. But if we generate a few more data points from either or distribution, the hypothesis quickly gets to the top, or to the bottom.
• The hypothesis looks a lot like overfitting⁵: We got a modest improvement at evidence at the cost of a large complexity of the hypothesis.

Intuition

If a detective uses both Bayes' theorem to update her beliefs, and starts with the Solomonoff prior, we say she does Solomonoff induction. Why is this the right approach? There are some more complicated and rigorous justifications,⁶ but here's how I think about this.

First of all, the formula shouldn't feel so shocking. After all, we spent an entire chapter arguing that if you care about , the natural distributions look like . So using this prior really represents a belief that the complexity of the hypothesis is the important factor.

But here's a better justification that is more down to earth.

Let's think of an experiment where our Bayesian detective samples $n$ samples from an unknown distribution $p$; we have different models $q_1, \dots, q_k$. Solomonoff prior of $q_i$ is $2^{-K(q_i)}$ and the evidence going for that model is $2^{-H(p, q_i)}$.

First, remember: under Solomonoff prior, a hypothesis $q$ has prior $2^{-K(q)}$ and if the data are $p$, the evidence for $q$ is $2^{-H(p,q)}$. So, choosing the most likely hypothesis means choosing the $q$ that minimize $K(q) + n \cdot H(p,q)$.

But we know what that formula means! $K(q)$ is how many bits of memory we need to store the model $q$, and $n \cdot H(p,q)$ is how many bits of memory we need to store $p$, once we know $q$. ⁷

That is, using Solomonoff prior means that we are simply supposed to prefer the models that compress the data the most. This is also called the Minimum description length principle.

What's next?

Nothing! If you enjoyed this journey through probability and information theory, let me know. You can also leave feedback. Also, check out the resources page.