Minimum Description Length

The best model compresses hardest: model bits plus data-given-model bits is the total, and the smallest total wins without a validation split.

A complex model spends 120 plus 30 bits while a simple one spends 40 plus 90, and the 130 total beats 150

Why Does This Exist?

Model selection without held-out data looks impossible: training loss always favors complexity. Cross-validation answers with compute and variance; Bayes answers with debatable priors. MDL answers with codelength: the model that compresses data most (itself included) generalizes, because compression is prediction in bits.

Two-part form: $L = L(\\text{model}) + L(\\text{data} \\mid \\text{model})$ . Complex models shrink the second term and explode the first. It connects source and channel coding to selection, and BIC falls out as its large- $n$ price.

The one idea you need first

$L(\\text{data} \\mid \\text{model}) = -\\log_2 p(\\text{data} \\mid \\hat\\theta)$ : better fit, fewer bits. $L(\\text{model}) \\approx \\tfrac{k}{2}\\log_2 n$ : each of $k$ parameters costs half a log- $n$ in bits. Add and minimize.

Think of It Like This

Shipping furniture flat-pack

Two sellers ship a shelf: one ships air (big box, tiny manual), the other flat-packs (small box, thick manual). Total shipping volume decides, not either part alone.

Complex models ship air: short manual (great fit) in a huge box (parameters). MDL measures the truck, not the shelf. Where it stops: real manuals approximate with BIC crudeness; exact codelengths need careful codes (NML, Bayesian mixtures).

How It Actually Works

Refinements: crude two-part (plug BIC), NML (minimax regret $\\log\\sum_y p(y\\mid\\hat\\theta(y))$ ), Bayesian mixtures ( $-\\log\\int p(y\\mid\\theta)w(\\theta)d\\theta$ ). BIC $= -2\\ell + k\\log n$ is MDL in nats with unit-information prior: each parameter pays $\\tfrac{1}{2}\\log n$ . Prequential (online) MDL accumulates $-\\sum\\log p(y_t\\mid y_{<t})$ : compress sequentially, no code design. All punish $k$ near $\\log n$ per parameter asymptotically.

Worked example

Hundred points, true line plus noise. Linear model ( $k=2$ ): $L(\\text{model}) = 40$ bits, residuals $90$ bits, total $130$ . Tenth-degree ( $k=11$ ): $20$ extra... model $120$ bits, residuals $30$ bits, total $150$ . MDL picks linear ( $130 < 150$ ) though the tenth-degree fits better. BIC check in nats: linear $-2\\ell = 180$ , penalty $2\\log 100/2$ ... precisely $k\\log n = 2(4.605) = 9.21$ vs $11(4.605) = 50.66$ : the 41-nat gap tracks the 20-bit codelength verdict up to constants.

Code

1linear, complex_ = (40, 90), (120, 30)  # (model, data) bits2print(sum(linear), sum(complex_))  # -> (130, 150)3print("linear" if sum(linear) < sum(complex_) else "complex")  # -> linear

Totals 130 versus 150 pick the simpler model. Fit alone would crown the complex one at 30 data bits.

Watch Out For

Comparing codelengths across different codes

Bits from mismatched codes (different precisions, different priors) do not compare: the "winner" may just use a coarser ruler. Selection then launders quantization as science.

Fix the coding scheme (same precision, same NML family) before comparing. If changing float precision flips the winner, the comparison was void.

Using MDL where compute is the constraint

Shortest description can be slow to decode (huge ensembles, deep searches). Edge and latency budgets care about FLOPs and memory, not bits.

Constrain the model class by deployability first, then MDL inside it. If the winner cannot ship, the bits were academic.

The Quick Version

Total bits $=$ model bits $+$ data-given-model bits; minimize the sum.
Example: 130-bit simple beats 150-bit complex despite worse fit.
BIC is large- $n$ MDL at $\\tfrac{k}{2}\\log n$ per parameter.
NML, mixtures, and prequential refine the crude two-part code.
Fix the code before comparing; mismatched rulers void verdicts.
Constrain by deployability first, compress inside second.