skip to content

What does relative entropy measure about a coder built on the wrong symbol probabilities?

level: seniorimportance: must knowfreq 49%

answer

  1. the price of a mismatched model
  2. cross-entropy minus the true entropy
  3. lengths from q, weights from p
  4. zero only when the two agree
  5. bits per symbol, multiplied by stream length

basics

~20 s

Relative entropy is the extra bits per symbol a coder pays for using the wrong probabilities: cross-entropy minus the source's true entropy. It is zero only when the assumed probabilities match the real frequencies, and strictly positive otherwise.

solid answer

~40 s

A coder built on assumed probabilities `q` spends about `-log2 q(s)` bits on symbol `s`, but the symbols actually arrive at the true frequencies `p`. The average charge is therefore the **cross-entropy** `H(p,q) = -sum p(s) log2 q(s)`, while the best achievable average is the entropy `H(p)`. The gap, `D(p||q) = H(p,q) - H(p) = sum p(s) log2(p(s)/q(s))`, is the **relative entropy** — the avoidable cost of the mismatch, in bits per symbol. Worked on two symbols: a source at 0.9 and 0.1 has entropy about 0.469 bits, a coder assuming 0.5 and 0.5 spends exactly 1 bit, so the model wastes about 0.531 bits per symbol. That is also why cross-entropy works as a training loss: it differs from the divergence only by `H(p)`, which the model cannot change.

code

pseudocode · 10 lines
pseudocode
# p[s] = true frequency of symbol s, q[s] = probability the coder assumed
cross   = 0
entropy = 0
for each s in alphabet:
  if p[s] > 0:
    if q[s] == 0:
      return INFINITY          # no finite codeword for a symbol that occurs
    cross   = cross   - p[s] * log2( q[s] )
    entropy = entropy - p[s] * log2( p[s] )
return cross - entropy         # extra bits per symbol

go deeper

for a junior

Hold on to the one-line reading: a coder built on the wrong probabilities pays more bits per symbol than one built on the right ones, and relative entropy is exactly that extra amount.

for a middle

Be able to separate the three quantities — entropy as the floor, cross-entropy as the bill, relative entropy as the difference — and say which distribution supplies the code lengths and which supplies the weights.

for a senior

Run a small case end to end and convert per-symbol bits into bytes over a realistic stream length, so that the argument about whether a mismatch is worth fixing rests on a number rather than on an intuition.

for a principal

Weigh the excess against what closing it costs: an adaptive or better-fitted model buys bits back but adds state, complexity and a failure mode when the source's mix shifts away from what the model learned.

## Code lengths come from the model, frequencies come from the source An optimal code built on a probability table `q` gives symbol `s` a length of about `-log2 q(s)` bits: likely symbols get short codewords, unlikely ones long. If `q` is right, the average length is the source's **entropy** `H(p) = -sum p(s) log2 p(s)`, and nothing lossless does better. Now separate the two roles. The **lengths** are fixed by whatever the coder assumed, `q`. The **frequencies** at which those lengths are charged are set by the source, `p`. The average bill per symbol is therefore `H(p,q) = -sum over s of p(s) * log2 q(s)` which is the **cross-entropy** of the source against the model. Subtract the floor and the difference is the **relative entropy**, also called the **Kullback-Leibler divergence**: `D(p||q) = H(p,q) - H(p) = sum over s of p(s) * log2( p(s) / q(s) )` That number is the answer to the question: the extra bits per symbol you pay for believing the wrong distribution. It is never negative, and it is zero only when `q(s) = p(s)` for every symbol the source actually emits. ## The worked two-symbol case Take a source emitting `A` nine times out of ten and `B` once in ten, and a coder that assumes both are equally likely. | Symbol | True p | Model q | Bits charged, -log2 q | Ideal bits, -log2 p | |---|---|---|---|---| | A | 0.9 | 0.5 | 1.000 | 0.152 | | B | 0.1 | 0.5 | 1.000 | 3.322 | - **Average charged:** `0.9 * 1.000 + 0.1 * 1.000 = 1.000` bit per symbol. - **The floor:** `0.9 * 0.152 + 0.1 * 3.322 = 0.137 + 0.332 = 0.469` bits per symbol. - **Relative entropy:** `1.000 - 0.469 = 0.531` bits per symbol. Over a stream of a million symbols that is about 531,000 bits, roughly 66,000 bytes, thrown away purely by holding the wrong belief about the source. Notice where the waste comes from: the flat model spends a full bit on the symbol that arrives 90% of the time, when a code matched to the source would spend a small fraction of a bit on it and pay the long codeword only on the rare symbol. ## Three quantities, one picture | Quantity | Formula | Reads as | |---|---|---| | Entropy `H(p)` | `-sum p log2 p` | The floor: bits per symbol under a perfect model | | Cross-entropy `H(p,q)` | `-sum p log2 q` | The bill: what this model actually costs per symbol | | Relative entropy `D(p||q)` | `sum p log2 (p/q)` | The excess: bill minus floor | The frequent mistake is to report the bill as if it were the excess, or the floor as if it were the bill. The excess is the only one of the three that is zero for a perfect model. ## Why this is also a training loss When a model is fitted to data, `p` is the distribution the data came from and `q` is what the model predicts. Minimising `D(p||q)` is what you want — bring the model's beliefs onto the source's. But `D(p||q) = H(p,q) - H(p)`, and `H(p)` depends only on the data, not on any parameter you can turn. So minimising the **cross-entropy** minimises the divergence exactly, and cross-entropy has the practical advantage of being computable straight from observed outcomes and predicted probabilities without ever estimating the source's own entropy. This is why a fitted model's loss is usually reported as a cross-entropy figure, and why that figure has a floor it cannot go below rather than trending toward zero. ## Consequences worth stating - **A wrong model can never beat the true entropy on average.** The divergence is non-negative, so the bill is always at or above the floor. - **A small per-symbol gap is not a small total.** The excess multiplies by the number of symbols; a tenth of a bit is over a hundred kilobytes across ten million symbols. - **The gap is where adaptive coders earn their keep.** A coder that re-estimates `q` from what it has already seen drives the mismatch down as the stream goes on, at the cost of carrying the estimation machinery. - **Both pieces must be over the same alphabet.** If the model has no probability at all for a symbol the source emits, the cost of that symbol is unbounded rather than merely large. ## What an interviewer is listening for Name the three quantities and keep them distinct; give the formula for the excess in one line; and be able to run a two-symbol case end to end on a whiteboard, saying which factor supplies the code lengths and which supplies the weights. The candidate who says "it measures how different two distributions are" has the vague version; the coding reading — extra bits per symbol, weighted by what really arrives — is the one that survives a follow-up.

  • Why is cross-entropy rather than relative entropy minimised when fitting a model?
    The two differ by the source's own entropy, which is fixed by the data and unaffected by any parameter. Minimising cross-entropy therefore minimises the divergence exactly, and cross-entropy is computable directly from observed outcomes and predicted probabilities without estimating the source's entropy at all.
  • What is the lowest value cross-entropy can reach, and what does reaching it mean?
    The entropy of the distribution being scored against. Cross-entropy equals it exactly when the model's probabilities match the true frequencies for every symbol that occurs, and the gap above it is the relative entropy. A reported value below that floor means the two numbers were computed over different distributions, not that the model beat the floor.
  • Does a divergence of 0.53 bits per symbol matter for a real payload?
    It depends entirely on the symbol count, which is why the per-symbol figure should always be multiplied out before anyone argues about it. At 0.53 bits, a million symbols waste about 531,000 bits — roughly 66,000 bytes. Across a thousand such streams it is tens of megabytes; inside one short message it is a handful of bits nobody will notice.

A courier that prices every parcel as though all sizes were equally likely: the small parcels you actually ship end up paying for shelf slots reserved for sizes that almost never arrive. The relative entropy is the fee you would recover by pricing from your real shipping mix.

saying these in an interview costs you the question

  • Calls it the total coded size rather than the excess
  • Claims a wrong model can beat the true entropy on average
  • Uses cross-entropy and entropy as interchangeable names
  • Weights the per-symbol costs by the model's probabilities
  • Assumes a small per-symbol gap cannot matter on a long stream