The Bound That Is Actually Reached

Most bounds in machine learning are loose. You prove that some error is at most something, the something is enormous, and the value of the result is its shape rather than its number.

Information theory is the exception, and that is what makes it worth a few hours. Three of its central quantities are bounds that are attained, and each one turns out to be something you already use without calling it by that name.

One: the shortest a code can be

Take four symbols with probabilities $\tfrac12$, $\tfrac14$, $\tfrac18$, $\tfrac18$. The entropy is

$$H = \sum_x p(x)\log_2\frac{1}{p(x)} = 1.75 \text{ bits}$$

Now build the best prefix code by repeatedly merging the two least likely symbols. The lengths come out as 1, 2, 3 and 3 bits, which average to 1.7500 bits - the entropy, to every decimal place. A fixed-length code would need 2 bits, so the saving is 12.5%.

The match is exact because each ideal length $\log_2(1/p)$ happens to be a whole number here. Change the source to $(0.6,\ 0.25,\ 0.1,\ 0.05)$ and it stops being exact: entropy 1.4905, best code 1.5500. The ideal length for a symbol of probability 0.6 is 0.737 bits, and no code word is 0.737 bits long.

The fix is to code several symbols at once, so the rounding error is shared:

Approaching from above, never crossing. Note what is not happening: the symbols are independent, so there is no redundancy between them to exploit and the entropy per symbol never changes. Only the granularity improves.

The practical reading is the one worth keeping. If a compressor beats the entropy you computed, the theorem is not in trouble - your distribution was wrong. Entropy is a statement about a model, which makes it a modelling tool rather than a property of a file.

Two: what the wrong distribution costs

You never know $p$. So code that same source with the optimal code for a different distribution $q$ - say the uniform one - and measure the bill:

$$\underbrace{2.0000}_{H(p,q)} = \underbrace{1.4905}_{H(p)} + \underbrace{0.5095}_{\mathrm{KL}(p\|q)}$$

Exactly two bits per symbol, splitting exactly into the entropy of the source plus a surcharge. That surcharge is the Kullback-Leibler divergence.

Look at what each term depends on. $H(p)$ is a property of the world: no model changes it, and it is the information-theoretic twin of the irreducible error in the bias-variance decomposition. $\mathrm{KL}(p\|q)$ is entirely your model.

So minimising cross-entropy over models is minimising divergence from the truth, exactly. Two things follow immediately: the loss can never reach zero on a noisy source, so a training loss approaching zero means memorisation rather than learning; and minimising cross-entropy is maximum likelihood in different units.

It is not a distance

Take a source that emits one symbol 98% of the time.

The same two distributions, and one direction costs just over twice the other.

$\mathrm{KL}(p\|q)$ is dominated by outcomes that $p$ produces and $q$ calls unlikely, so minimising it spreads the model out to cover what happens. $\mathrm{KL}(q\|p)$ punishes the reverse, so minimising it makes the model commit to one region. Which one a method minimises is a modelling decision, and it is why variational approaches that take the second direction are mode-seeking.

And it is unbounded

The loss on one example is $\log_2(1/q(\text{truth}))$:

A model that is right 95% of the time while being certain on the 5% it gets wrong scores far worse than one that is right as often and hedges. Accuracy cannot see that difference; cross-entropy is built from it. It also explains a loss curve that spikes while accuracy does not move - a few confidently wrong examples dominating the gradient.

Three: what one variable says about another

The same machinery, applied to a pair, answers an engineering question and a modelling question with one number.

For a channel that flips each bit with probability $f$, the capacity is $1 - H(f)$:

At $f = 0.1$ the channel is right nine times out of ten and carries barely half a bit: accuracy and information are not the same currency. At $f = 0.5$ it carries nothing at all, because the output distribution is then identical whatever was sent. At $f = 0.9$ it is back to 0.5310 - a consistent liar is as useful as a consistent truth-teller.

The dependence correlation reports as zero

Generate two independent bits and let the target be their XOR. Over 200,000 draws:

Every reading is correct. Neither input alone says anything - and mutual information, which would catch a dependence of any shape rather than a linear one only, agrees. The pair determines the target exactly.

So any feature screening that ranks variables one at a time discards both of them, with a perfectly clean report. This is not exotic: a drug that works only in the presence of a gene, a fault that occurs only when two settings disagree. The fix is to score subsets, or to let a model that represents interactions see them together.

One caution: mutual information is harder to estimate than a correlation. On continuous variables it depends on binning, and it is biased upward on small samples, so a high value on few points can be the estimator talking.

The ceiling nothing raises

Measure the 10% channel and you get 0.5329 bits about what was sent, matching the theoretical 0.5310. Erase three received bits in ten to 0 and measure again: 0.2763 bits.

It went down, and no processing can ever push it back up. For any chain $X \to Y \to Z$,

$$I(X;Z) \le I(X;Y)$$

because $Z$ is computed from $Y$ and sees nothing of $X$ except what $Y$ passed on. The consequences are blunt:

• codes work by adding redundancy before transmission; no decoder recovers what the channel destroyed
• no model, however deep, extracts more about the label than its features carry - layers are functions of layers, and the ceiling is set at the input
• every preprocessing step, from quantising to dropping a column, can only lose information, which may be the right trade but should be a decision rather than housekeeping

The text above erases bits; the figure instead uses a second 10% channel in series. With both flip probabilities at 0.10 its After processing reads 0.3199 bits rather than the 0.2763 above, and both sit below what the channel carried. The inequality holds for every choice; the number depends on which one you make.

Why this keeps reappearing

Compression, communication and the loss functions of machine learning are the same three quantities wearing different clothes. Entropy is the floor. Cross entropy is what you pay when your distribution is wrong, and its excess over the floor is what your optimiser has been reducing all along. Mutual information is what one variable says about another, and it bounds everything downstream.

None of them is a heuristic, which is rare enough in this field to be worth the afternoon it takes to learn them properly.