Two-part MDL codes, concretely

Minimum description length is the principle underneath the whole computational side of this programme, and it is usually explained in a way that makes it sound either obvious or mystical. This post does neither. It builds the smallest concrete example end to end, with numbers you can check, so that the plateau theorem later in the archive is read as arithmetic rather than philosophy.

The two-part code

Given data, a two-part code describes it in two chunks. Part one: a model, transmitted exactly. Part two: the residuals of the data under that model, transmitted as the remaining randomness. Total description length is the model cost plus the residual cost. The best model for the data is the one minimising the sum. That is all MDL is: compression with the price of the compressor included.

The balance is the whole content. A model with zero parameters, like the mean, costs almost nothing to state and leaves huge residuals if the data has structure. A model with a thousand parameters can zero out the residuals but pays for every parameter. Somewhere in between, the total is minimised, and that model is the one MDL calls the truth about the data, operationally defined.

A worked example

Take eleven points sampled from a parabola with a little noise: y equals x squared plus noise of about one tenth. Three candidate models.

The constant: one parameter. Model cost, one or two bits by any reasonable encoding. Residual cost: eleven residuals with standard deviation about six, which costs roughly 11 times log of 6 times a constant, call it 40 bits with the log base 2 and a half-bit-per-residue factor. Total: about 42.

The line: two parameters. Model cost, maybe 4 bits with slopes. Residuals still carry the curvature: standard deviation about 4, costing about 34. Total: about 38. Better, because the curvature it removes is worth more than the second parameter cost.

The parabola: three parameters. Model cost, say 7 bits. Residuals are now just the injected noise, standard deviation one tenth, costing about 15. Total: about 22.

The cubic: four parameters. Model cost, say 10 bits. Residuals are the same noise, costing the same 15. Total: about 25. Worse than the parabola, because the fourth parameter bought nothing: there was no cubic structure left to remove.

The minimum sits at the parabola, which is the truth used to generate the data. Note the mechanism, because it is the mechanism the plateau theorem uses. Adding parameters always reduces the residual cost, but with diminishing returns, while the model cost grows linearly. Past the true model class, each new parameter buys a smaller residual drop than its price, and the total turns upward. Discovery, in this measure, is the downward segment of that curve, and it has an end.

The two cautions

First, the numbers above are rough and depend on encoding choices, and two honest people can get different totals. The cure is to state the code: the framework’s papers specify the model-cost accounting exactly, and under the stated code the parabola wins by a margin no encoding-tweak overturns. The principle is robust; the arithmetic is only well-posed once the code is fixed.

Second, and more important: MDL finds the truth only if the truth is in the searched class. Fit the same data with exponentials and the minimum lands on whichever exponential compresses best, which is not the parabola. That is not a defect, it is the epistemology: you cannot discover structure outside your description language, and the size of the residual cost floor at the minimum is exactly the information your language cannot reach. That floor is the subject of the next walkthrough in this sequence, and it is the number that separates a plateau you can work down from one you cannot.