Minimum description length

Remarks

The length $-\log_2 P_H(D)$ is the length, up to rounding, of a Shannon code for $D$ built from $P_H$. Example: for $n$ coin tosses with $h$ heads, take $\mathcal{H} = \set{\text{fair coin}, \text{coin with } p = h/n}$ with $L(H) = 1$ bit each. The fair coin costs $1 + n$ bits; the other costs $1 + n\, \mathrm{H}(h/n)$ bits, where $\mathrm{H}$ is the binary entropy, so this toy rule picks it whenever $h \ne n/2$. This is too generous, because the second hypothesis depends on the data. A real two-part code must also encode $h$, which costs about $\log_2 (n + 1)$ bits, and then MDL picks the biased coin only when $h/n$ is far enough from $1/2$. Non-example: minimizing $L(D \mid H)$ alone is maximum likelihood, not MDL, and it ignores the cost of complex hypotheses. Refined versions of MDL replace the two-part code by a single universal code, such as the normalized maximum likelihood code.