Information Theory for AI
Entropy, cross-entropy and KL divergence as the language of learning.
A language model's training loss, its perplexity, the number of bits a compressor built from it would need, and its distance from the truth are one quantity in different units. Information theory makes that precise, and supplies the inequalities (Jensen, Gibbs, data processing) that turn it into proofs.
What you’ll learn
- Define entropy, conditional entropy, mutual information, cross-entropy and KL divergence, and use the chain rules that relate them.
- Prove Jensen's and Gibbs' inequalities and derive their corollaries, including the data-processing inequality.
- Connect cross-entropy to code length and perplexity through the source coding theorem.
- Distinguish forward from reverse KL, derive the evidence lower bound, and explain what each divergence rewards.
The quantities, precisely
The quantities fit together through chain rules. Writing and averaging gives , and from it:
For densities, the differential entropy behaves differently: it can be negative, and it is not invariant under reparametrization, since . KL divergence and mutual information, by contrast, are invariant under invertible transformations and keep their meaning. Among all densities with variance , the Gaussian has the largest differential entropy, , which makes Gaussian assumptions the least committal ones given a variance.
Think first Let be independent fair bits and . Compute and .
Whatever is, flips with probability , so is a fair bit independent of and . Given , though, determines : bit. The three-way "overlap" is bit. Conditioning can create dependence, which is why pairwise scores miss features that matter only jointly.
Jensen, Gibbs and their corollaries
A convex has a supporting line at every interior point of its interval. At there is a slope (for differentiable , ) with
Substitute and take expectations. The linear term has mean zero:
If is strictly convex, the line touches the graph only at , so the gap below is a nonnegative variable that is positive whenever . Its mean vanishes only if almost surely. (If is an endpoint of the interval, almost surely anyway.)
Let ; terms outside contribute nothing. Apply Jensen to the convex function , with the variable distributed according to :
Equality in the first step requires to be constant on (strict concavity of ), and in the second it requires . Together they force .
Gibbs' inequality is the workhorse behind most of the field's inequalities:
- The uniform distribution maximizes entropy. With uniform on a finite , , so , with equality iff is uniform.
- Information is nonnegative. , so , with equality iff : conditioning reduces entropy on average.
- Data processing. If is a Markov chain, then . Expand by the chain rule in two orders, , and use . No processing of , deterministic or random, creates information about .
- Pinsker's inequality. , with KL in nats: a small KL divergence forces a small total-variation distance.
Which statement about conditioning is always true?
- for every value
- , with equality if and only if and are independent
- only when and are positively correlated
Show the answer
B. , with equality if and only if and are independent
by Gibbs' inequality, with equality iff , i.e. independence. The guarantee holds only on average over .
Codes, compression and perplexity
A prefix code gives each symbol a binary codeword, none a prefix of another, so a stream decodes without separators. The Kraft inequality says that lengths are achievable by a prefix code if and only if , and McMillan showed that the same constraint binds every uniquely decodable code. Short codewords are a scarce resource; the question is how to spend them.
Lower bound. Given lengths that satisfy Kraft, define with . Then , and averaging over gives
Upper bound. The Shannon code satisfies Kraft, and rounding up costs less than one bit:
Wrong model. A code built from a model instead of the truth costs the cross-entropy: the entropy plus the KL divergence as redundancy.
Arithmetic coding removes the rounding: it encodes a whole sequence in at most about two bits more than . Any sequential predictor is therefore a compressor, and its log-loss is its code length. For a language model, the average log-loss per token on held-out text estimates the cross-entropy between the text's distribution and the model, and the perplexity is its exponential, : the effective number of equally likely next tokens. Used this way, large language models are strong general-purpose compressors (Delétang et al., 2024).
A language model's validation loss is nats per token. What is its perplexity?
Show the answer
7.4
: on average the model is as uncertain as a uniform choice among about 7.4 tokens. In bits the loss is bits per token, and again. Lowering the loss by nats cuts the perplexity by about 10%, since .
Forward and reverse KL, and the ELBO
Which direction of KL you minimize decides what your model is good at. Maximum likelihood minimizes the forward KL: , and only the first term depends on . Variational inference minimizes the reverse KL , which averages over and needs only up to its normalizing constant, exactly what is available for a posterior.
| Property | Forward | Reverse |
|---|---|---|
| Averages over | the target (data) | the approximation |
| Infinite when | somewhere | somewhere |
| Behavior | mass-covering; over a Gaussian family it matches the mean and covariance of | mode-seeking; may lock onto one mode and underestimate spread |
| Used by | maximum likelihood, cross-entropy training | variational inference, VAE encoders |
For a latent-variable model , write the evidence as an expectation under any distribution that is positive wherever is:
Apply Jensen's inequality to the concave logarithm:
The gap is exactly a reverse KL to the posterior, since :
Maximizing the ELBO over thus minimizes without ever computing ; maximizing it over the model's parameters as well is how variational autoencoders are trained (Kingma & Welling, 2014). Splitting gives the familiar reconstruction-minus-KL form:
KL is one member of the family of -divergences, for convex with , all of which satisfy data processing. At the optimal discriminator, the original GAN objective equals , so the generator minimizes the Jensen–Shannon divergence (Goodfellow et al., 2014). Information also limits learning: Fano's inequality, for any estimator of from with error probability , is the standard tool for proving that no learner can succeed from too little data.
Key takeaways
- Entropy, conditional entropy, mutual information, cross-entropy and KL are linked by chain rules: , and .
- Jensen's inequality gives Gibbs' inequality , and with it , (conditioning reduces entropy on average) and the data-processing inequality.
- Source coding: bits, and a code built from a model costs bits per symbol, so log-loss is code length and perplexity is its exponential.
- Maximum likelihood minimizes the forward KL (mass-covering); variational inference minimizes the reverse KL (mode-seeking) through the ELBO, which equals .
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
You fit a single Gaussian to a distribution with two well-separated modes. What do the two directions of KL give?
- Both directions give the same Gaussian
- Neither is defined, because is bimodal
- Minimizing gives a broad Gaussian covering both modes; minimizing gives a narrow Gaussian on one mode
- Minimizing gives a narrow Gaussian on one mode; minimizing gives a broad one covering both
Show the answer
C. Minimizing gives a broad Gaussian covering both modes; minimizing gives a narrow Gaussian on one mode
Forward KL averages over and blows up wherever misses mass of , so spreads out; over Gaussians its minimizer matches the mean and covariance of . Reverse KL averages over and penalizes mass where is small, so settles on one mode.
is a Markov chain with for a deterministic feature extractor . Which relation must hold?
- , because can extract useful features
- No general relation holds
Show the answer
B.
This is the data-processing inequality. Equality holds exactly when , i.e. when is a sufficient statistic of for . Feature extraction can make information easier to use, but never more plentiful.
Two language models report perplexities of 20 and 30 on the same text, but they use different tokenizers. What can you conclude?
- The first model is better
- The second model is better, because it was evaluated on more tokens
- They are equally good, since perplexity does not depend on the tokenizer
- Nothing directly: per-token perplexity depends on how the text is split, so compare the total log-loss of the text, e.g. in bits per byte
Show the answer
D. Nothing directly: per-token perplexity depends on how the text is split, so compare the total log-loss of the text, e.g. in bits per byte
Perplexity is of the average log-loss per token. A tokenizer that cuts the text into fewer, longer tokens raises the loss per token even at the same total code length. The total negative log-likelihood of the text, normalized per byte or character, is comparable across tokenizers.
Why is the ELBO, , a lower bound on ?
- By Jensen's inequality for the concave logarithm; the gap is
- Because the term is subtracted inside it
- Because
- It is not: the ELBO is an upper bound on
Show the answer
A. By Jensen's inequality for the concave logarithm; the gap is
, and the slack is exactly the reverse KL from to the true posterior. Maximizing the ELBO therefore tightens the bound and improves the approximate posterior at the same time.
Further reading
- C. E. Shannon, "A mathematical theory of communication," Bell System Technical Journal 27 (1948), 379–423 and 623–656.
- T. M. Cover & J. A. Thomas, Elements of Information Theory, 2nd ed. (Wiley, 2006).
- D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms (Cambridge University Press, 2003).
- S. Kullback & R. A. Leibler, "On information and sufficiency," Annals of Mathematical Statistics 22 (1951), 79–86.
- D. P. Kingma & M. Welling, "Auto-encoding variational Bayes," ICLR (2014).