Reinventing Entropy | Compression & Intelligence Part 1
3Blue1Brown
The limits of text compression 0:00
Text encoded in plain ASCII uses eight bits per character, which is wasteful. Assigning shorter bit strings to common characters can bring the average down to around four bits per character, and cleverer methods that spot patterns across long stretches of text do even better. The natural question is whether there is some absolute limit to how far this can go, a question that traces back to Claude Shannon's work in the 1940s that founded information theory.
Compression and prediction are the same thing 1:03
When large language models are trained, the pre-training step is usually described as next token prediction using something called cross-entropy loss, a term borrowed from information theory. One of the conclusions of information theory is that prediction and compression are mathematically equivalent, so training a model to predict the next token can be reframed as training it to be the most efficient possible text compressor. Some people even claim that compression is intelligence, though since intelligence is hard to define precisely, the safer version of that claim is that the mathematical theory of compression is strangely relevant to artificial intelligence.
A robot on a distant moon 3:32
To explore the limits of compression, picture a robot on a faraway moon that receives movement instructions from Earth: up, down, left, or right, each with a fixed step size. The instructions are not evenly distributed. Half of them are up, a quarter are down, one eighth are left, and one eighth are right, and each instruction is sampled independently of what came before. The puzzle is to find the most efficient way to send these instructions as a stream of bits.
Three students, three encodings 4:33
A straightforward student suggests two bits per instruction, since there are four possible instructions, giving codes like 00 for up and 11 for right. A cleverer student instead uses variable-length codes, a single bit 0 for up, two bits 10 for down, and three bits 110 and 111 for left and right, which averages out to 1.75 bits per instruction, better than the flat two-bit scheme. This works because the code words are prefix-free, meaning no code word is the beginning of another, which lets the robot unambiguously tell where one instruction ends and the next begins.
Visualizing prefix-free codes 8:31
A diagram of all possible binary strings, arranged so that every string beginning with a given prefix sits above it, helps show why prefix-free codes work. Assigning the single bit 0 to up consumes half of this space, assigning 10 to down consumes a quarter, and the two three-bit codes each consume an eighth, filling the space exactly with no overlap. Strikingly, these proportions match the actual probabilities of each instruction, hinting at a deep link between probability and code length.
Why perfect compression looks like noise 11:02
A third, more theoretical student argues that a perfectly compressed message should be indistinguishable from random noise, since genuinely random data cannot be compressed further. The robot's clever encoding does behave this way, with each bit acting like an independent fifty-fifty coin flip. Using the same diagram of binary strings, one can show that if compressed messages are equally likely to be any string of a given length, then giving one message fewer bits forces others to need more, so the only efficient arrangement is one where all equally likely messages get the same length.
Information as negative log probability 15:01
This reasoning leads to the idea that a message using n bits under perfect compression must have probability 1 over 2 to the n, which rearranges into the formula for information: negative log base 2 of the probability, often read as how many times you halve the space of possibilities to reach that probability. Shannon defined this expression as the information of an event, so unlikely events carry high information and expected ones carry very little, and even when perfect compression is impossible, this value still sets a lower bound on how much a message can be compressed on average.
From letters to language 19:01
Applying this idea to real text means looking at how predictable each new letter is given everything before it, using something like a small GPT model to assign probabilities and taking the negative log of each one to get its information content. Because probabilities of a whole phrase multiply together letter by letter through the chain rule, and logarithms turn multiplication into addition, the information of a full message is just the sum of the information of each letter, a fact later used to build compression algorithms that get within a bit or two of this theoretical bound.
Shannon's experiments with real language 21:03
Before language models existed, Shannon estimated the information content of English by studying short letter sequences, or n-grams, and tracking what tended to follow them in books, though this approach broke down for longer, rarer strings even though those longer contexts are actually the most predictable and compressible. He then turned to a human predictor, his wife Betty, having her guess each next letter in a book and recording only her misses, showing that a much shorter transcript could still carry the same information if replayed to an identical guesser. In his 1950 paper on prediction and entropy in printed English, he refined this by recording how many guesses each person needed to get the right letter, effectively treating the human brain as a black box model of language, a project that foreshadows how today's models are built to predict and compress language directly rather than merely being studied for it.
Average Information and Compression Limits 25:33
Measuring the average information per symbol in a message is really a question about the limit of compression, since it sets a lower bound on how efficiently a signal can be encoded. This mirrors the earlier calculation of average bits per instruction for the robot's perfect encoding, where each code word length matched its symbol's information content exactly. For any probability distribution, the average information per symbol is found by adding up p times the negative log of p for every probability p. Visually, this is the total area of rectangles stacked over the probability bars, where each rectangle's height equals that symbol's information value.
Naming Entropy 27:01
This quantity only holds when every symbol follows the same distribution, as in the robot case but not in English. Shannon named it entropy, supposedly on John von Neumann's suggestion, since the formula resembles one from statistical mechanics and since, as the story goes, nobody really understands entropy anyway, giving Shannon an edge in arguments. Shannon denoted it with the letter h. A more even distribution produces higher entropy, a skewed one with a dominant event produces lower entropy, and spreading probability across more symbols raises entropy further.
The Noiseless Coding Theorem 28:31
Entropy measures uncertainty, but more precisely it gives the minimum bits per symbol needed to encode a message following that distribution. This is the core of Shannon's 1948 noiseless coding theorem, which states no encoding can beat this limit, though you can always get arbitrarily close to it.
Entropy Rate and Language 29:00
For messages where symbols don't share one fixed distribution, such as natural language, Shannon needed the entropy rate for a stochastic process, averaging information across all possible messages. Since no clean formula describes language, Shannon relied on estimates from human subjects rather than pure data analysis. With at least 100 preceding letters of context, he estimated English entropy at about one bit per character, meaning English could in theory compress to roughly one yes or no answer per character.
AI-generated summary. It can be wrong or incomplete - check anything that matters against the original.
