CONCEPT
Minimum Description Length
Jorma Rissanen’s operationalisation of
Kolmogorov complexity into a computable model-selection criterion: the best model of a dataset is the one that minimises the total number of bits needed to describe the model
plus the data encoded with the model’s help—a principle that dissolves overfitting at its root and identifies the right amount of complexity as the amount that minimises total description length.
The minimum description length principle is the practical machine you can build from
Kolmogorov’s uncomputable ideal. Kolmogorov complexity defines the best possible model as the one producing the shortest program for the data—but that shortest program cannot in general be found. Jorma Rissanen, working in the 1970s from Kolmogorov’s and Solomonoff’s foundations, replaced the uncomputable ideal with a computable proxy. Instead of the shortest program, use two codes: one for the model itself, one for the data
given the model. Minimise the sum. The result is a criterion that simultaneously penalises model complexity (you pay bits to describe your hypothesis) and model error (you pay bits to correct the model’s remaining mistakes). A model that is too simple cannot describe the data compactly: high error cost. A model that is too complex