Saying which hypothesis wastes bits, so a Bayes mixture beats the two-part code

The two-part code sends a hypothesis, then the data coded with it, for $L(H) + L(D \mid H)$ bits. Grünwald's tutorial illustrates it with nine hypotheses about a binary sequence $x$: coins with bias $\theta \in \{0.1, 0.2, \dots, 0.9\}$ [1]. Each coin is a prediction, and so a code for the sequence: under coin $\theta$, a 1 costs $-\log_2 \theta$ bits and a 0 costs $-\log_2(1-\theta)$. The fair coin spends 1 bit per flip; the 0.8 coin spends 0.32 bits on a 1 and 2.32 on a 0, so it is cheap for sequences heavy in 1s.

Here $H$ is a coin. The first part says which: its index among the nine, written in bits. A uniform code sends any index in $\log_2 9 \approx 3.17$ bits; call the length for coin $\theta$ $L(\theta)$. The second part is the sequence in that coin's code, $-\log_2 P(x \mid \theta)$ bits. The sender picks the coin that makes the total shortest.

The code for the index is a distribution too. Lengths $L(\theta)$ correspond to probabilities $W(\theta) = 2^{-L(\theta)}$ over the coins, a prior; the uniform code is the uniform prior of 1/9. So the total is

$$-\log_2 W(\theta) - \log_2 P(x \mid \theta) = -\log_2 \big[ W(\theta) P(x \mid \theta) \big],$$

and the shortest message picks the coin with the largest prior times likelihood: the maximum a posteriori (MAP) hypothesis. With countably many hypotheses, the two-part code is MAP counted in bits.

It also wastes bits. Any code shares out a budget of probability 1 among its messages: a message of length $\ell$ uses $2^{-\ell}$ of it. The two-part code has a message for every pair of coin and sequence, the one through coin $\theta$ using $W(\theta) P(x \mid \theta)$, and together they use up the whole budget. But for any one sequence, the sender only ever sends the shortest. Eight 1s in ten flips has nine possible messages, one through each coin; the one through the 0.8 coin holds about a third of that sequence's share, and the other two-thirds sit in eight messages that are never sent. Those eight still hold their slice of the budget, because the receiver must be able to decode them. Since a message's length is $-\log_2$ of its share, and halving a share adds one bit, getting a third of the share costs $\log_2 3 \approx 1.6$ extra bits.

• two-part keeps this
• wasted share

The fix is to give each sequence its whole share: agree in advance on one code for the whole model class, one that never says which coin. That code is the Bayes mixture, which codes $x$ in

$$-\log_2 \sum_\theta W(\theta) P(x \mid \theta)$$

bits: each sequence gets the whole of its share, the sum over all nine coins instead of the one term the sender picked. The two-part code sends $x$ through its best coin, so its length is $-\log_2$ of the largest term. The terms are nonnegative, so the sum is at least the largest term, and $-\log_2$ shrinks as its argument grows, more probability meaning a shorter code:

$$-\log_2 \sum_\theta W(\theta) P(x \mid \theta) \;\le\; -\log_2 \max_\theta W(\theta) P(x \mid \theta).$$

The gap is $\log_2$ of the sum over its largest term. Every coin gives every sequence some probability, so here the gap is always positive, and it shrinks as more data lets one coin dominate the sum. For eight 1s in ten flips, several coins are plausible: the two-part code takes 10.39 bits and the mixture 8.80, the 1.6 bits of waste recovered. For 80 in 100, the 0.8 coin's term dwarfs the rest, and the gap is 0.12 bits.

This is refined MDL: say only which model family, and code the data within it with a mixture. Solomonoff's predictor is the same kind of mixture taken over all programs, and its error bound rests on the same inequality.

References

1. A tutorial introduction to the minimum description length principle [link]
   Grunwald, P., 2004. arXiv. DOI: 10.48550/ARXIV.MATH/0406077