The best model is the one that compresses the data most.
“Learning” usually sounds vague: find the pattern, don't overfit, prefer the simpler explanation. MDL makes it concrete by swapping in one measurable thing — bits. Any genuine pattern in the data lets you write the data down shorter than spelling it out literally. So the more you can compress the data, the more you have actually learned about it.
That turns model selection into bookkeeping. Describe your model in bits, then describe the data using that model in bits, and add them up. The model that gives the shortest total wins. A model too simple can't compress; a model too complex costs too many bits to even write down. The right one sits in between — and MDL finds it without any tuning knob or prior.
Replace “probability of the data” with “length of its shortest description,” and Occam's razor becomes something you can compute.
Learning is compression
Why “finding the pattern” and “shrinking the file” are the same job
Step 1 · The black box & the one number
Feed a dataset to a compressor — the bit count is the grade.
Here is the whole subject in one picture. Hand a dataset D to an ideal compressor: it returns the shortest description it can find, and the length of that description in bits is the only number we care about. We'll call it the codelength L(D), and it follows us through every step:
The grade is just a length: how many bits the shortest description takes. Lower is better — a short code means the compressor found structure it could exploit. A dataset with no structure can't be shortened at all; you're stuck writing it out one symbol at a time.
Here is the move that makes the whole field click. Compressing the data and learning from it are the same act. Every regularity you discover — a bias, a repetition, a rule — is exactly a way to shave bits off the description. So “how well did we learn?” and “how short is the code?” are two phrasings of one question.
One number, the codelength in bits, stands in for the whole task. The rest of this page is about how to count those bits honestly — so that a model can never cheat its way to a short code by secretly being complicated.
Grünwald, §1.1: “any regularity in the data can be used to compress the data… the more we are able to compress the data, the more we have learned about the data.”
Step 2 · Three sequences
Structure shows up as bits you don't have to write.
You've met the codelength L(D) — the one number we want to push down. To feel why “shorter = learned more,” look at three datasets of the exact same size, 10,000 bits each, and ask how short an honest code can make each one.
These three are Grünwald's own opening example. They look equally big, but they compress to wildly different lengths:
A · perfectly regular
~30
0001 repeated 2,500 times. A short program reproduces the whole thing, so the code is only about 2·log₂(2500)+1 ≈ 24 bits — it shrinks from 10,000 to a handful.
B · pure noise
10,000
Fair-coin tosses. With no structure to exploit, the shortest code is essentially the sequence itself — about 10,000 bits. Random data is incompressible; there is nothing to learn.
C · biased — the middle
~7,200
Roughly 4× as many 0s as 1s (p ≈ 0.2). A code tuned to that bias needs about 0.72 bits per symbol, so ≈ 7,200 bits — between the two extremes. This is where real learning lives.
Same raw size, three very different codelengths. The gap between “10,000 bits” and what you actually pay is the regularity you found — the learning, measured in bits. Case C, the partly-predictable one, is the interesting case, and it's the example we carry forward.
Grünwald, §1.1: a regular sequence is compressible by a short program; a fair-coin sequence's shortest description is, with high probability, roughly the sequence itself; a statistically biased sequence sits in between, at αn bits with 0 < α < 1.
The two-part code
Model bits plus data bits · counted honestly · with one real worked example
Step 3 · Split the code in two
Describe the model, then describe the data using it. Add the bits.
You saw that the biased dataset (Case C) can be shortened — but only if the decoder knows about the bias. That's the catch: to use a model, you first have to tell the reader which model. MDL's whole trick is to charge you for that, too.
So the description comes in two parts. First spell out a hypothesis H — here, the bias of the coin — which costs L(H) bits. Then encode the data D using that hypothesis, which costs L(D|H) bits. The reader gets H first, then replays it to recover D. Crude MDL picks the H that makes the sum as small as possible:
Ĥ=argminH[L(H)+L(D | H)]
model bits + data bits → pick the hypothesis with the shortest total description
Read it slowly, because every later step is just this sum with the two terms filled in. A model that fits the data beautifully drives L(D|H) down — but if it's an elaborate model, it pushes L(H) up. MDL refuses to look at one term in isolation; it only ever judges the total.
There is no free regularization knob here, and no prior to invent. The penalty for complexity isn't bolted on by hand — it falls out of one unavoidable cost: a fancier model simply takes more bits to write down.
Grünwald, §1.3 (“Crude MDL”): L(H) is the length in bits of the description of the hypothesis; L(D|H) is the length in bits of the data when encoded with the help of the hypothesis.
Step 4 · Codes are probabilities in disguise
Bits and probabilities are the same thing: L = −log₂ P.
We keep saying “encode the data using H,” but what does that cost? The answer is the one bridge the whole theory rests on — and it lets us turn any probability model straight into a bit count.
The rule (a consequence of the Kraft inequality, which says short codewords are a limited resource you can't overspend): if you believe an outcome has probability P, the best code spends −log₂ P bits on it. Likely things get short codewords; rare things get long ones. Three quick conversions — verify each in your head:
a 50-50 outcome
L = −log₂(1/2)
= 1 bit
One coin flip's worth of surprise. The everyday unit of one bit.
a 1-in-8 outcome
L = −log₂(1/8)
= 3 bits
Rarer outcome, longer codeword. Halving P adds exactly one bit.
a likely outcome
L = −log₂(0.8)
≈ 0.32 bits
Expected things are nearly free — a fraction of a bit each.
Because codelength = −log₂ P, “find the shortest code for D” and “find the model that gives D the highest probability” are the same search. MDL can borrow the entire machinery of probability and statistics while still talking only about bits.
Grünwald, §2 (Fig. 2.1): for any distribution P there is a prefix code with length ⌈−log P(z)⌉ for each z, and conversely. Ignoring the rounding, codelength and −log-probability are interchangeable.
Step 5 · Compute the data bits by hand
A model that knows the bias saves 1,887 bits on our dataset.
Now we cash in the bridge from Step 4. Take our running dataset — a sequence of n = 10,000 bits, about 1 in 4 ones (so p ≈ 0.25). Let's count L(D|H), the data bits, when H is “a biased coin with p = 0.25.” Follow the arithmetic:
Cost of writing a 0 vs. a 1
Each symbol costs −log₂ P bits. A 0 (P = 0.75) is cheap; a 1 (P = 0.25) is dear.
Average cost per symbol = the entropy
Mix the two costs by how often each appears: 75% cheap zeros, 25% dear ones. That weighted average is the binary entropy H(p).
Multiply by the 10,000 symbols
The whole dataset's data bits is just that per-symbol cost times the length.
Compare with no model at all
Spelling the data out literally costs one bit per symbol — 10,000 bits. The model paid for itself many times over.
We haven't yet paid L(H) — the bits to announce
that p = 0.25. Pin p down to a sensible resolution and that's only about
½·log₂(n) ≈ 7 bits. Set against 1,887 bits saved, naming the
model is almost free here — so the biased coin is clearly worth it.
Binary entropy H(0.25) = −0.25·log₂0.25 − 0.75·log₂0.75 ≈ 0.811 bits. A fair-coin model (p = 0.5) would give H = 1 bit/symbol = 10,000 bits — no savings, because there's no bias to exploit.
Step 6 · The U-shaped curve
Too simple, too complex — the shortest total sits in the middle.
In Step 5 the biased coin clearly beat “no model.” But a coin is the simplest model there is. What if we offer MDL a ladder of richer models and let it choose? Watch the two terms pull against each other.
Our ladder is Markov models — models that predict the next bit from the previous few. An order-0 model sees no context; order-1 looks back 1 bit; order-2 looks back 2 bits; and so on. Each step up doubles the parameters (one bias per context), so L(H) climbs fast. Each step up also fits a little better, so L(D|H) falls — but with shrinking returns. Drag the slider over model complexity and read off the total:
Drag the complexity — watch model bits rise while data bits fall, and the total dip then climb
Move left and the model is too simple: it can't fit, so data bits balloon. Move right and each new parameter buys almost no fit but costs real bits — the total turns back up. The minimum at order 1 is MDL's answer, and here it's the true source of the data.
The total is a U. MDL doesn't need a held-out test set to spot overfitting — the rising right arm of the U is overfitting, made of wasted model bits. Numbers are this worked example (n = 1,000 here); the shape is the point.
One curve does the whole job of model selection. No regularization coefficient, no validation split — just two bit counts added together, minimized. That is the entire MDL procedure in one picture.
Worked numbers (n = 1,000): order 0 → 5 + 950 = 955; order 1 → 10 + 800 = 810; order 2 → 20 + 795 = 815; order 3 → 40 + 793 = 833; order 4 → 80 + 792 = 872. Model bits ≈ (#params)·½·log₂n; data bits = n·(conditional entropy).
Why it works & what it became
No overfitting for free · Occam made precise · and the ideas it seeded
Step 7 · Why it can't overfit
A model that memorizes noise has to pay for the noise — in bits.
The U-curve in Step 6 turned back up on the right. That rising arm is the heart of MDL's most famous property — no overfitting, automatically — so it's worth seeing exactly why a too-complex model loses.
Overfitting is when a model latches onto the random quirks of this dataset instead of the real pattern. Grünwald's picture is a polynomial fit: with enough degrees you can thread a curve through every point — perfect fit, L(D|H) → 0 — but that wiggly curve is now describing the noise, and it fails on fresh data.
Maximum-likelihood would happily pick the wiggly curve — it has the lowest data bits, after all. MDL won't, and the reason is the other term. To pin down a degree-9 polynomial you must transmit 10 finely-tuned coefficients; that's a large L(H). The bits you save on fit, you more than spend on description.
Noise is, by definition, incompressible. A model can only “fit” the noise by absorbing it into its own description — so the bits never vanish, they just move from L(D|H) into L(H). The total can't be fooled.
Grünwald, §1.1: “MDL procedures automatically and inherently protect against overfitting” — no separate penalty term, validation set, or stopping rule is bolted on; it is a property of counting total bits.
Step 8 · Occam's razor, as a bill of bits
Three candidate models, one tie-breaker: whose total bill is smallest?
You now have both terms and the reason the total can't be gamed. Let's put it to work as a judge. Back to our biased dataset (n = 1,000 bits, p ≈ 0.25) and three hypotheses competing to describe it — pick each and read its bill.
Occam's razor says “prefer the simpler explanation.” MDL turns that slogan into an invoice: model bits + data bits. Click a candidate and watch which one wins on the total, not on either term alone:
Pick a model — bars show its model bits, data bits, and total (shorter total wins)
Biased coin: 7 + 811 = 818 bits — the shortest total. This is MDL's pick. ✓
Fair coin can't compress (data bits = 1,000). Memorize-it drives data bits to ~0 but needs ~1,000 model bits to spell out the table — it just relocates the cost. The biased coin wins the total. Bars are bits on a 0–1,000 scale.
“Memorize-it” is the perfectly-fitting model from Step 7 in miniature: L(D|H) ≈ 0, but L(H) explodes. MDL rejects it for the same reason it rejected the wiggly polynomial — the total is what's judged, so simplicity and fit are weighed in one currency.
Bits (n = 1,000): fair coin → 0 + 1,000 = 1,000; biased coin → 7 + 811 = 818; memorize-it → ~1,000 + 0 ≈ 1,000. Grünwald, §1.6: MDL is a precise, quantitative form of Occam's razor.
Step 9 · The big picture & recap
One rule, four payoffs — and can you now explain it?
You've met the two-part code, computed it by hand, watched the U-curve, and seen why noise can't sneak past the bill. Time to step back: what does this one rule actually buy you, and have you genuinely got it?
Report card · what the principle delivers
Complexity · given a real unit
Overfitting · handled by
Tuning knobs · regularizer / prior
Occam's razor · before MDL
Now you can explain it. Five questions — answer each out loud before opening it. If all five come easily, you've genuinely got this tutorial.
Why is “learning” the same as “compression”?
Any genuine regularity in the data lets you describe it in fewer bits than spelling it out. So the amount you can compress the data is exactly the amount of structure you've found — the learning, measured in bits.
What are the two parts of the two-part code?
L(H), the bits to describe the hypothesis (the model), plus L(D|H), the bits to describe the data once that model is known. MDL picks the H that minimizes their sum.
Why does L = −log₂ P matter so much?
It makes codes and probabilities interchangeable: a likely outcome gets a short codeword. So “shortest code” and “highest-probability model” are the same search, and MDL can borrow all of statistics while talking only in bits.
Why doesn't MDL overfit?
A too-complex model can fit the noise, but only by absorbing it into its own description — the bits move from L(D|H) into L(H), so the total turns back up. The minimum of that U-curve is the right complexity; no validation set required.
How is this Occam's razor made precise?
“Prefer the simpler explanation” becomes “prefer the shorter total description.” Simplicity (L(H)) and fit (L(D|H)) are finally measured in one currency — bits — so they can be traded off without an arbitrary weighting constant.
What happened next — MDL became a working tool: select polynomial degrees, prune decision trees, choose the number of clusters or the order of a Markov chain — all by minimizing total bits. The same idea, “the best model compresses best,” later echoed through modern views of why neural networks generalize at all.
“The more we are able to compress the data, the more we have learned about the data.” — Peter Grünwald, 2004
One ruler — bits — for the whole problem of induction.
By identifying learning with compression, MDL gave a vague, centuries-old idea (Occam's razor) a number you can compute, and a clean answer to the oldest practical problem in modeling: how complex should my model be?
Rissanen's program
MDL grew from Rissanen's work and the Kolmogorov–Solomonoff theory of algorithmic information — keeping their beauty while staying computable, unlike Kolmogorov complexity itself.
Model selection
A principled, prior-free way to pick polynomial degree, tree size, cluster count or Markov order — kin to BIC and Bayesian model selection, but framed entirely in bits.
Why deep nets generalize
“The best model compresses best” reappears in modern accounts of generalization, and in compression-based views of what large models are really doing.
Replace probability with description length and a slogan becomes arithmetic — the lasting gift of the MDL principle.