LLM + RoboticsUnit 1 · The foundations · Day 05

A Tutorial Introduction to the Minimum Description Length Principle

Learning is compression. The model that lets you describe the data in the fewest bits, counting the bits for the model itself, is the one to trust.

AuthorPeter Grünwald
Year / venue2004 · arXiv (math/0406077); chapters 1–2 of Advances in MDL, MIT Press
Core ideaModel selection by shortest code length
Study time5–8 h

Original: arXiv:math/0406077 · Code, notebook and exercises: 30u30 Day 5

Start here (no maths needed)

The best explanation of some data is the one that lets you write the data down in the fewest bits, counting the explanation itself.

Think of it like this

Think of zipping files on a computer. A file that says "ABABABAB…" a thousand times zips down to almost nothing, because the zip program spots the pattern. A file of random letters hardly shrinks at all. So how much a file shrinks tells you how much pattern is in it. MDL says: finding patterns is learning. But you must also count the size of the rule you used, or you could cheat with a giant rule that just lists every answer.

How it works

  1. You have some data, like dots on a graph, and several possible explanations, like a straight line or a wiggly curve.
  2. For each explanation, count the bits needed to describe the explanation itself.
  3. Then count the bits needed to describe the data's mistakes, given that explanation.
  4. Add the two numbers together.
  5. Pick the explanation with the smallest total. A wiggly curve fits better, but it costs more bits to describe.

Why robots care

A robot learning how its own arm moves has to pick a model: a simple one, or a complicated one with lots of extra terms. Too simple, and it misses real effects like friction. Too complicated, and it learns the random wobble in its sensors. MDL gives a fair way to choose.

Try it

Words to know

Compress
Make data take up fewer bits by using its patterns, like a zip file.
Model
An explanation or rule for the data.
Overfitting
Choosing an over-complicated explanation that fits random noise.
Code length
The number of bits used to write something down.

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.

1. Summary

TL;DR

Grünwald's tutorial is the standard introduction to Rissanen's Minimum Description Length principle. Any regularity in data can be used to compress it, so the more you can compress, the more you have learned. Chapter 1 is a non-technical tour. Chapter 2 makes it precise: code lengths are log-probabilities, crude MDL adds model bits to data bits, and refined MDL replaces hand-made model codes with a single, provably good code per model family (normalised maximum likelihood). It ties MDL to Bayes, to cross-validation-like prediction, and to Kolmogorov complexity.

2. The core idea

Crude, two-part MDL for a set of hypotheses:

H* = argmin_H  [ L(H) + L(D | H) ]

L(D | H) = −log₂ P(D | H)                # bits to code the data with H's help
L(H)     ≈ (k/2) · log₂ n                # k parameters at optimal precision, n data points

The trouble is that L(H) depends on an arbitrary choice of code. Refined MDL fixes that with one code per model family M:

P_nml(D | M) = P(D | θ̂(D)) / Σ_{D'} P(D' | θ̂(D'))

−log P_nml(D | M) = −log P(D | θ̂(D))  +  COMP_n(M)
COMP_n(M) ≈ (k/2) log(n / 2π) + log ∫ √det I(θ) dθ

3. Deep dive

Watching MDL choose a polynomial

Grünwald's running example is choosing the degree of a polynomial. Training error alone always prefers the highest degree. Add the cost of the parameters and the minimum lands near the truth.

Interactive: crude two-part MDL for polynomial degree

Data from a cubic plus Gaussian noise (seeded). Right: bits per degree, model L(H) stacked on data L(D|H) (relative to the best fit). The chosen degree has the shortest total. Left: the data and the chosen fit.

MDL picks degree
–
Training error picks
–
True degree
3

Two things to notice. With heavy noise and few points, MDL settles for a simpler model than the truth: the data don't justify the extra parameters, and that's the right call. Training error, meanwhile, always picks degree 8. One caution: the (k/2) log n penalty is an approximation that is only reliable for large n, and it treats every parameter as equally costly. Those small-sample and same-k weaknesses are Grünwald's reasons for refined MDL.

Four ways to read the same number

Links across the course

Limits Grünwald admits

For many models COMP_n is infinite (the Gaussian with unbounded mean, for example) and needs patching. NML is often hard to compute, so practice falls back on approximations. And MDL's Occam's razor is a claim about codes, not about the world: a short description is a good bet for prediction, not proof that nature is simple.

4. Why it matters for robotics

5. How to study it

  1. Read Chapter 1 in one sitting (about 20 pages, no maths). Then read Chapter 2 Sections 2.2–2.6 slowly, with paper.
  2. Prove the easy direction of the Kraft inequality yourself for a small code like {0, 10, 110, 111}.
  3. In the 30u30 Day 5 folder, run train_minimal.py and read implementation.py to see two-part, prequential and NML code lengths computed side by side.
  4. Do the exercises in order: two-part code, prequential coding, model selection, NML complexity, and MDL vs AIC/BIC.
  5. Stretch: compute the NML complexity of the Bernoulli model exactly for n = 10, 100, 1000 and compare it with ½ log₂ n.

6. Self-check

Why can code lengths be treated as probabilities?

By the Kraft inequality, the lengths of any prefix code satisfy Σ 2^(−L(x)) ≤ 1, so 2^(−L(x)) behaves like a probability. Conversely, any distribution gives a code with lengths of about −log₂ P(x).

Why does crude MDL charge about ½ log₂ n bits per parameter?

With n data points a parameter can only be estimated to a precision of about 1/√n. Stating it more precisely buys nothing, and stating it to that precision costs about ½ log₂ n bits.

What does the NML denominator measure?

How well the model can fit all possible data sets of size n. Flexible models fit many data sets well, so they get a large denominator and pay a higher complexity.

What is the prequential interpretation?

Code each point using a model fitted only to earlier points. The total log-loss is a code length, so model selection becomes "which model predicted the sequence best, step by step".

Does MDL assume one of the models is true?

No. It picks the model that compresses the data best, which is meaningful even when all candidates are wrong.

7. Further reading