Occam's Razor and Minimum Description Length

"Prefer the simplest model that explains the data" is easy to say and hard to operationalize — simple compared to what, measured how? Two people can look at the same pair of models and disagree about which one is "simpler." Minimum description length (MDL) turns Occam's razor from a vague aesthetic preference into an exact number: measure simplicity in bits, the actual currency of information, by asking how many bits it would take to write down a description of the model plus a description of everywhere the model still gets the data wrong. The model with the shortest total description wins.

The analogy: describing a friend's route by a shortcut

To tell someone how to reach your house, you could give exact turn-by-turn directions for every single trip they might take from anywhere in the city — an enormous, over-specific message. Or you could give one compact rule ("take the highway to exit 12, then it's the third house") that works for almost every starting point, plus a short list of exceptions for the rare starting points where the compact rule fails. The second message is shorter overall, even after including the exceptions, precisely because it captured real structure rather than memorizing every case individually. MDL formalizes "the message that's shorter after you include the exceptions wins."

The formal principle

For a model $M$ and data $D$, the total description length is:

$$L(M, D) = L(M) + L(D \mid M)$$

In words: $L(M)$ is the number of bits needed to specify the model itself (its parameters, its structure — a complex model with many parameters needs more bits to write down), and $L(D \mid M)$ is the number of bits needed to specify the data given that model, i.e., how much information is needed to describe everywhere the model's predictions miss (a model with high error needs more bits to encode its residuals, roughly $-\log_2 P(D \mid M)$ via optimal coding). MDL says: choose the model minimizing the sum, not the model minimizing either term alone. A model complex enough to fit data perfectly makes $L(D\mid M) \to 0$ but often blows up $L(M)$; a model too simple to capture real structure keeps $L(M)$ small but leaves $L(D\mid M)$ large. The minimum sits in between.

Worked example 1: comparing a memorized table to a formula

A dataset of 20 $(x, y)$ pairs follows $y = 2x + 1$ with small noise. Model A, a lookup table storing all 20 pairs exactly: $L(M_A) = 320$ bits (20 pairs × 16 bits) and $L(D\mid M_A) \approx 0$ (zero residual). Model B, the formula $y=2x+1$ plus residuals: $L(M_B) = 32$ bits (slope and intercept) and $L(D\mid M_B) = 80$ bits (20 small residuals at 4 bits each). Totals: $L_A = 320$; $L_B = 112$. Model B wins decisively — the compact rule plus small exceptions beats the exhaustive table, even though the table has zero error.

Worked example 2: a model too simple to be worth it

Model C predicts a flat constant $y = 10$ for every $x$, ignoring the trend: $L(M_C) = 16$ bits (one number), but $L(D\mid M_C) = 180$ bits, since every residual is now sizeable (true $y$ ranges roughly 1–41, so residuals up to $\pm30$ at 9 bits each). Total $L_C = 196$ — worse than Model B's 112, better than Model A's 320. MDL correctly ranks all three: neither the maximally complex table nor the maximally simple constant wins; the model capturing the real structure does.

Try fitting the curve above with increasing polynomial flexibility — the point where residual error stops shrinking fast enough to be worth the extra coefficients' bit-cost is exactly the MDL-optimal complexity.

What this means in practice

MDL gives a principled, information-theoretic justification for regularization — an L1 or L2 penalty (The Geometry of L1 vs L2 Penalties) can be read as an approximate bit-cost for the model's parameters, and choosing a penalty strength is implicitly choosing an exchange rate between model bits and residual bits. When comparing two factor models with different parameter counts, MDL-style reasoning ("does the added complexity earn back more than its own encoding cost") is a rigorous alternative to eyeballing an in-sample R².