Information theory: entropy, cross-entropy and KL divergence — where loss functions come from

Information as surprise, entropy and the Huffman code, cross-entropy, KL divergence and information gain — and why the loss function of language models is cross-entropy.

13 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 20 of 52

Full series syllabus 52 of 83 topics published

What you will take away

What information and entropy are, why they are measured in bits and why entropy is the limit of compression.
What cross-entropy and KL divergence measure and why their minimum is where the model tells the truth.
Why cross-entropy is the loss function of classifiers and language models, and what perplexity is.

Useful to know first: Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals

When you train a classifier or a language model, you are almost certainly minimizing “cross-entropy”. Where does the word come from? From information theory, founded in 1948 by Claude Shannon while he was working out how to send messages over a telephone line as economically as possible. It turned out that the question “how many bits do I need?” and the question “how well does the model predict?” are one and the same. This part closes the module on probability and statistics.

It builds on the parts Overview of distributions and Statistics and parameter estimation.

1. Information as surprise

Definition — information of an event

Let (Ω, 𝓕, P) be a probability space and A ∈ 𝓕 an event with probability p = P(A) > 0. The information (self-information) of the event A is the number

I(p) = −log₂ p bits.

The information thus depends only on the probability of the event; we regard I as a function I : (0, 1] → [0, ∞). The unit is the bit (with the natural logarithm it would be the nat). The smaller p is, the larger I(p), and I(1) = 0.

In plain words

Information measures surprise. The sun rising in the morning does not surprise you — zero bits. A coin toss carries 1 bit, a die roll log₂ 6 ≈ 2.585 bits, and an event with odds of 1 : 1024 a full 10 bits. The logarithm makes the information of independent events add up: two coins are 2 bits.

A bit is the information in one yes/no question with a fair answer. You can guess a number from 1 to 1024 in 10 questions (“is it greater than 512?”…) — precisely because each answer carries 1 bit and log₂ 1024 = 10.

I(p) = −log₂ p

−: for p ≤ 1 the logarithm is negative or zero; the minus turns it into a non-negative number that grows as p falls
log: turns multiplying the probabilities of independent events into adding up information: log(pq) = log p + log q
2: the base determines the unit: with two, the unit is the bit, the answer to one fair yes/no question (with e it would be the nat)
p: the probability of the event — the smaller it is, the more the event surprises us

Theorem — the information of independent events adds up

Let (Ω, 𝓕, P) be a probability space and A, B ∈ 𝓕 independent events with probabilities p = P(A) > 0 and q = P(B) > 0. Then P(A ∩ B) = pq and

I(pq) = I(p) + I(q).

Proof. By independence P(A ∩ B) = pq, and I(pq) = −log₂ (pq) = −log₂ p − log₂ q = I(p) + I(q). ∎

Conversely: let J : (0, 1] → ℝ be a continuous function such that J(pq) = J(p) + J(q) for all p, q ∈ (0, 1]. Then there is a c ∈ ℝ with J(p) = −c log₂ p for all p ∈ (0, 1] (the substitution p = 2^−t gives Cauchy’s functional equation g(s + t) = g(s) + g(t) for a continuous g on [0, ∞), whose only solution is g(t) = ct). The requirement J(1/2) = 1 gives c = 1. So the logarithm is not arbitrary — it is the only continuous measure of surprise that adds up for independent events.

Example: a die and a coin at once, p = 1/6 · 1/2 = 1/12: I = log₂ 12 ≈ 3.585 = 2.585 + 1 bits.

2. Entropy

Definition — entropy

Let X be a discrete random variable with a finite or countable set of values 𝒳 and probability mass function p : 𝒳 → [0, 1], p(x) = P(X = x). The entropy of X is

H(X) = −∑_{x ∈ 𝒳} p(x) log₂ p(x),

where a term with p(x) = 0 is taken to be 0 (0 · log₂ 0 := 0, which is the limit of t log₂ t as t → 0⁺). For a countable 𝒳 the sum may be +∞. Equivalently H(X) = E[I(p(X))], the expected value of the information of the outcome. Since H(X) depends only on the distribution p, we also write H(p).

In plain words

The average surprise — how uncertain the outcome is. A fair coin has an entropy of 1 bit; a coin that lands heads 90% of the time has only 0.469 bits: you almost always know what is coming. A die has 2.585 bits.

H(X) = ∑_x p(x) · (−log₂ p(x))

∑_x: over all possible outcomes — entropy is a property of the whole distribution, not of a single event
p(x): the weight: how often the outcome occurs; frequent outcomes contribute more to the average
−log₂ p(x): the surprise of the outcome x, the information from the previous section; rare outcomes surprise a lot, but they come rarely

Entropy = the expected value of information: the average surprise, weighted by how often each surprise comes.

Example — the entropy of a coin with 90% heads

For a variable with two values with probabilities p and 1 − p (p ∈ [0, 1]), the entropy has the form h(p) = −p log₂ p − (1 − p) log₂ (1 − p) (the binary entropy, the curve below).

h(0.9) = 0.9 · (−log₂ 0.9) + 0.1 · (−log₂ 0.1) = 0.9 · 0.152 + 0.1 · 3.322 = 0.137 + 0.332 = 0.469 bits (colours as in the formula above).

Most of the entropy comes from the rare tails: it surprises to the tune of 3.32 bits, even though it comes up in only a tenth of the tosses.

Entropy of a coin as a function of the probability of heads p

Theorem — bounds on entropy

Let X be a discrete random variable with a finite set of values 𝒳, |𝒳| = n ≥ 1, and probability mass function p. Then

0 ≤ H(X) ≤ log₂ n,

where

H(X) = 0 if and only if there is an x ∈ 𝒳 with p(x) = 1 (the outcome is certain);
H(X) = log₂ n if and only if p(x) = 1/n for all x ∈ 𝒳 (the distribution is uniform).

Proof. Each term −p(x) log₂ p(x) is non-negative for p(x) ∈ [0, 1] and zero only for p(x) ∈ {0, 1}; the sum is therefore zero if and only if all p(x) are 0 or 1, i.e. one of them is 1. The upper bound and the condition for equality follow from Gibbs' inequality below for the uniform q(x) = 1/n: H(p) ≤ H(p, q) = −∑ p(x) log₂ 1/n = log₂ n, with equality exactly for p = q. ∎

In plain words

Uncertainty is lowest when the outcome is certain and highest when all possibilities are equally likely. That is why the peak of the curve is exactly at p = 0.5.

3. Entropy as code length

Definition — prefix-free code and average length

Let 𝒳 be a finite non-empty set of symbols and {0, 1}⁺ the set of all non-empty finite words made of zeros and ones. A binary code is a mapping C : 𝒳 → {0, 1}⁺; the word C(x) is the codeword of the symbol x and ℓ(x) ∈ ℕ its length (number of characters).

The code C is prefix-free if and only if for all x, y ∈ 𝒳, x ≠ y, C(x) is not a beginning (prefix) of C(y), i.e. there is no word w (not even the empty one) with C(y) = C(x)w.
The code C is uniquely decodable if and only if its extension to messages C(x₁x₂…x_m) = C(x₁)C(x₂)…C(x_m) (concatenation), m ≥ 1, is injective — different messages give different sequences of bits. Every prefix-free code is uniquely decodable: a message can be decoded from the left without separators.
Let p be a probability distribution on 𝒳. The average length of the code C is L(C) = ∑_{x ∈ 𝒳} p(x) ℓ(x).

Theorem — Kraft's inequality

Let 𝒳 be a finite non-empty set and ℓ : 𝒳 → ℕ, ℓ(x) ≥ 1, prescribed lengths. A prefix-free binary code C with word lengths ℓ(x), x ∈ 𝒳, exists if and only if

∑_{x ∈ 𝒳} 2^−ℓ(x) ≤ 1.

In plain words

Short words are expensive: a word of length 1 takes up half of all possible continuations, a word of length 2 a quarter. The budget is 1 and cannot be overdrawn. Shannon's theorem follows from this — the lengths ℓ(x) = −log₂ p(x) use up the budget exactly, and the average length is then equal to the entropy.

Theorem — Shannon's source coding theorem

Let 𝒳 be a finite set with at least two elements and p a probability distribution on 𝒳 with p(x) > 0 for all x ∈ 𝒳. Then

every uniquely decodable binary code C for 𝒳 has an average length L(C) ≥ H(p);
there is a prefix-free binary code C for 𝒳 with L(C) < H(p) + 1 (the lengths ℓ(x) = ⌈−log₂ p(x)⌉, which satisfy Kraft's inequality, will do).

In plain words

Entropy is the limit of compression: a message cannot be encoded in fewer bits than its entropy. You give frequent symbols short codes and rare ones long codes — like Morse code, where the most common letter, E, is a single dot.

Four letters A, B, C, D with probabilities 1/2, 1/4, 1/8, 1/8 have an entropy of 1.75 bits. A fixed-length code needs 2 bits per letter. The Huffman code (0, 10, 110, 111) has an average length of 1/2 · 1 + 1/4 · 2 + 2 · 1/8 · 3 = 1.75 bits — exactly the entropy. So the message ABACABAD fits into 14 bits instead of 16:

Huffman code: left 0, right 1 Huffman code: 14 bits fixed-length code: 16 bits

The code 0, 10, 110, 111 has the lengths 1, 2, 3, 3 — exactly −log₂ of the probabilities 1/2, 1/4, 1/8, 1/8. The Kraft sum is 1/2 + 1/4 + 1/8 + 1/8 = 1: the budget is used up to the last bit. Such a code is found by Huffman's algorithm:

huffman(symbols with probabilities):
    every symbol is a separate tree
    while more than one tree remains:
        take the two trees with the smallest probability   # the rarest get the longest code
        join them under a new node: the left gets 0, the right 1
        probability of the node = the sum of both
    code of a symbol = the path from the root to it

Example — Huffman for A, B, C, D

The two smallest are joined: 1/8 + 1/8 = 1/4.
The two smallest are joined: 1/4 + 1/4 = 1/2.
The two smallest are joined: 1/2 + 1/2 = 1 (the root).

Paths from the root: A = 0, B = 10, C = 110, D = 111. Each merge lengthens the code of all symbols in both joined trees by one bit — which is why C and D, joined first, have the longest code.

4. Cross-entropy

Definition — cross-entropy

Let 𝒳 be a finite non-empty set, p : 𝒳 → [0, 1] the true probability distribution and q : 𝒳 → [0, 1] the distribution according to a model, where q(x) > 0 for every x with p(x) > 0. The cross-entropy of the distribution q relative to p is

H(p, q) = −∑_{x ∈ 𝒳, p(x) > 0} p(x) log₂ q(x).

It is the expected value of the model’s surprise −log₂ q(X) when X has the true distribution p. (If q(x) = 0 for some x with p(x) > 0, we set H(p, q) = +∞.) For q = p, H(p, p) = H(p).

In plain words

The average number of bits when the data come from p but you designed the code for the model q. In other words: how much the model surprises you on average. It rains on 70% of days; a model that says “50 : 50” pays 1 bit per day, while the correct model pays only 0.881 bits.

H(p, q) = ∑_x p(x) · (−log₂ q(x))

∑_x: over all outcomes that can occur
p(x): how often the outcome actually occurs — the weights come from reality, because we average over the data that really arrive
−log₂ q(x): how much the outcome surprises the model (and how many bits a code designed for the model gives it); where the model gives a small probability to something frequent, it pays a lot

Compared with entropy, only one thing has changed: the surprise is measured by the model, not by reality.

Example — three rain forecasts

Reality: it rains with p = 0.7, i.e. p(rain) = 0.7 and p(dry) = 0.3. The model “q” gives rain the probability q and dry weather 1 − q. Colours as in the formula above:

Model 0.5: H = 0.7 · 1 + 0.3 · 1 = 1 bit.
Model 0.7: H = 0.7 · 0.515 + 0.3 · 1.737 = 0.881 bits — that is the entropy H(p).
Model 0.9: H = 0.7 · 0.152 + 0.3 · 3.322 = 0.106 + 0.997 = 1.103 bits.

The overconfident model is worse here than the undecided one: the dry days (30%) surprise it to the tune of 3.32 bits.

Theorem — Gibbs' inequality

Let 𝒳 be a finite non-empty set and p, q probability distributions on 𝒳 such that q(x) > 0 for every x with p(x) > 0. Then

H(p, q) ≥ H(p),

with equality if and only if q(x) = p(x) for all x ∈ 𝒳.

Proof. We use ln t ≤ t − 1 for t > 0 (equality only for t = 1) and log₂ t = ln t/ln 2. We sum over x with p(x) > 0:

H(p) − H(p, q) = ∑ p(x) log₂ q(x)/p(x) ≤ 1/ln 2 ∑ p(x) (q(x)/p(x) − 1) = 1/ln 2 (∑ q(x) − 1) ≤ 0,

where the last sum runs only over x with p(x) > 0 and is therefore at most 1. Equality in the first inequality holds if and only if q(x)/p(x) = 1 for all x with p(x) > 0; then ∑ q(x) over these x equals 1, equality holds in the second one as well, and q is zero outside them, so q = p. ∎

In plain words

A wrong model always costs you extra bits. You get the least surprise only with the correct distribution — which is why it makes sense to minimize cross-entropy: the minimum is where the model tells the truth.

Cross-entropy of model q when the truth is p = 0.7 KL divergence in orange

5. KL divergence

Definition — Kullback–Leibler divergence

Let 𝒳 be a finite non-empty set and p, q probability distributions on 𝒳 such that q(x) > 0 for every x with p(x) > 0. The Kullback–Leibler divergence of the distribution q from p is

D_KL(p ‖ q) = ∑_{x ∈ 𝒳, p(x) > 0} p(x) log₂ p(x)/q(x).

Writing out log₂ p(x)/q(x) = −log₂ q(x) − (−log₂ p(x)) gives D_KL(p ‖ q) = H(p, q) − H(p), so by Gibbs' inequality D_KL(p ‖ q) ≥ 0, with equality exactly for q = p.

In plain words

How many extra bits you pay for using the model q instead of the truth p — the orange segment in the figure. The “50 : 50” model for rain on 70% of days costs 1 − 0.881 = 0.119 extra bits, and the “90% rain” model as much as 0.222 bits. By Gibbs' inequality, KL divergence is always non-negative and zero only for q = p.

D_KL(p ‖ q) = ∑_x p(x) · log₂ p(x)/q(x)

p(x): weights from reality — the model’s mistakes on frequent outcomes hurt more; that is why the order of the arguments matters
log₂ p(x)/q(x): = (−log₂ q(x)) − (−log₂ p(x)): how many more bits the outcome x costs us with the model than with reality; positive where the model underestimated the outcome, negative where it overestimated it

The average number of extra bits. Individual terms can be negative, but by Gibbs' inequality the sum never is.

Careful: KL divergence is not a distance, because it is not symmetric. If for two outcomes (rain, dry) we write just the probability of rain instead of the whole distribution, then D_KL(0.7 ‖ 0.5) = 0.119, but D_KL(0.5 ‖ 0.7) = 0.126. It matters which is the truth and which is the model.

Example — why KL divergence is not symmetric

Colours as in the formula above.

D_KL(0.7 ‖ 0.5) = 0.7 · log₂ 0.7/0.5 + 0.3 · log₂ 0.3/0.5 = 0.340 − 0.221 = 0.119.

D_KL(0.5 ‖ 0.7) = 0.5 · log₂ 0.5/0.7 + 0.5 · log₂ 0.5/0.3 = −0.243 + 0.368 = 0.126.

The positive term is each time the one where the model underestimates something: in the first case rain, by the ratio 0.7/0.5 = 1.4, in the second dry weather, by the ratio 0.5/0.3 ≈ 1.67. The second underestimate is cruder, and so it costs more bits. Swapping reality and model therefore changes the result.

6. Information gain

Definition — conditional entropy

Let X and Y be discrete random variables on the same probability space with finite sets of values 𝒳 and 𝒴. For x ∈ 𝒳 with P(X = x) > 0, the entropy of the conditional distribution of Y given X = x is

H(Y | X = x) = −∑_{y ∈ 𝒴} P(Y = y | X = x) log₂ P(Y = y | X = x)

(again with 0 · log₂ 0 := 0). The conditional entropy of Y given X is the weighted average of these entropies:

H(Y | X) = ∑_{x ∈ 𝒳, P(X = x) > 0} P(X = x) · H(Y | X = x).

In plain words

How much uncertainty about Y is left, on average, once you learn X.

Definition — information gain (mutual information)

Let X and Y be discrete random variables on the same probability space with finite sets of values. The mutual information (information gain) of X and Y is

I(X; Y) = H(Y) − H(Y | X).

It is thus the difference between the uncertainty about Y before the value of X is found out and the average uncertainty after.

In plain words

By how many bits the uncertainty shrinks when you learn X. In the spam example from the part on Bayes' theorem, 40% of mail is spam: an uncertainty of 0.971 bits. Once you know whether an e-mail contains the word “prize”, it drops to 0.826 bits on average — a gain of 0.971 − 0.826 = 0.145 bits (colours as in the formula below). This is exactly how decision trees choose what to ask first: the feature with the largest information gain.

I(X; Y) = H(Y) − H(Y | X)

H(Y): the uncertainty about Y before we look at anything — the starting point
H(Y | X): the uncertainty that remains after finding out X, averaged over all possible values of X (we do not know in advance which one comes up); we subtract it because we only care about what X has removed

The gain is always ≥ 0: on average, new information never confuses us more. Also I(X; Y) = I(Y; X).

Example — the information gain of the word “prize”

Spam makes up 40% of mail; the word “prize” appears in 30% of spam and in 1% of other e-mails. Y is “spam or not”, X “contains the word or not”. Colours as in the formula above.

Before: H(Y) = h(0.4) = 0.971 bits.
P(word) = 0.3 · 0.4 + 0.01 · 0.6 = 0.126.
With the word (Bayes): P(spam | word) = 0.3 · 0.4/0.126 = 0.12/0.126 = 0.952, entropy h(0.952) = 0.276.
Without the word: P(spam | no word) = 0.7 · 0.4/0.874 = 0.320, entropy h(0.320) = 0.905.
After: H(Y | X) = 0.126 · 0.276 + 0.874 · 0.905 = 0.826.
Gain: 0.971 − 0.826 = 0.145 bits.

The word almost certainly gives spam away, but it appears in only 12.6% of e-mails; in the others the uncertainty drops only a little (0.905 instead of 0.971). That is why the average gain is modest.

nejlepsi_otazka(data, features):               # one step of a decision tree (ID3)
    for each feature X:
        zisk[X] ← H(class) − ∑ share(X = x) · H(class | X = x)
    return the feature with the largest zisk[X]  # split the data by it and repeat

7. Information theory in artificial intelligence

Cross-entropy as a loss function. For a single example with the correct class y, it is −log q(y) — how much the correct answer surprised the model. Averaged over the data, it is the negative log-likelihood, so minimizing cross-entropy is the maximum likelihood estimation from the previous part. Libraries use the natural logarithm (the unit is the nat): 1 bit = ln 2 ≈ 0.693 nats.
The perplexity of a language model is 2^H, where H is the cross-entropy per word in bits. A perplexity of 8 means the model is, on average, as uncertain as if it were choosing among eight equally likely words.
KL divergence holds together variational autoencoders (VAEs), model distillation (a small model imitates the distribution of a large one) and fine-tuning language models with human feedback (RLHF), where a KL divergence penalty keeps the model from drifting too far from the original.
Compression and prediction are the same thing. A model that predicts the next symbol well can compress the data well — and vice versa. That is why language models are compared in bits per character.

loss(θ) = 1/N ∑_i=1^N (−ln q_θ(y_i | x_i))

loss(θ): the number that training reduces by changing the parameters θ
1/N ∑: the average over the training examples — instead of the unknown p, we average over the data that came from p
−ln: the surprise in nats; the natural logarithm because of convenient derivatives, it differs from bits only by a factor of ln 2
q_θ(y_i | x_i): the probability the model gave, for the input x_i, to the correct answer y_i; the other classes are not in the formula, because the true p is 1 at the correct class and 0 elsewhere

The cross-entropy between the data and the model = the negative average log-likelihood.

Example — perplexity on four words

The model gave the correct words of a sentence the probabilities 1/2, 1/4, 1/8, 1/8. The surprise in bits: 1, 2, 3, 3; the average H = 2.25 bits per word.

The perplexity 2^2.25 ≈ 4.76: the model hesitated roughly as if choosing among five equally likely words. Careful, it is 2 to the power of the average of the logarithms, i.e. the geometric mean of the numbers 1/q — not the ordinary mean of the numbers 2, 4, 8, 8 (that would be 5.5).

8. Summary

The information of an event, −log₂ p, measures surprise in bits; the information of independent events adds up.
Entropy is the average surprise, at most log₂ n, and it is a lower bound on the average code length.
Cross-entropy measures how many bits the model q costs on data from p; it is smallest for q = p.
KL divergence is the price of a wrong model: H(p, q) − H(p) ≥ 0, and it is not symmetric.
The loss function of classifiers and language models is cross-entropy — in other words, maximum likelihood.

Do you see it differently? Write to support@coden-app.com.

Information theory: entropy, cross-entropy and KL divergence — where loss functions come from

1. Information as surprise

2. Entropy

3. Entropy as code length

4. Cross-entropy

5. KL divergence

6. Information gain

7. Information theory in artificial intelligence

8. Summary

An Agent on your computer, driven from your phone