Entropy and Information

"How uncertain am I?" sounds like a question about a feeling. It is not. It has a precise numerical answer, measured in bits, and that answer turns out to be the quantity that decides how a decision tree splits and what loss a classifier is trained against. Both fall out of one definition.

A. Measuring surprise in bits

Start with the intuition. A coin known to land heads always carries no uncertainty: observing it tells you nothing you did not already know. A fair coin is maximally uncertain between two options. A coin that lands heads 99% of the time is much closer to the first case than the second - guess heads and you are wrong only 1% of the time.

We want a measure that is $0$ for the certain coin, largest for the fair one, and small for the 99% coin. Following Russell & Norvig, the entropy of a random variable $V$ taking values $v_k$ with probabilities $P(v_k)$ is

$$H(V) = \sum_{k} P(v_k) \log_2 \frac{1}{P(v_k)} = -\sum_{k} P(v_k) \log_2 P(v_k) .$$

The first form is the more suggestive one. The quantity $\log_2 \frac{1}{P(v_k)}$ is the surprise of outcome $k$: large when the outcome was unlikely, zero when it was certain. Entropy is simply the expected surprise - each surprise weighted by how often it actually happens.

Why base 2. The unit is the bit, and base 2 makes it literal: entropy is the average number of yes/no questions needed to pin down the outcome. One fair coin flip takes one question, so it should measure exactly $1$ bit. It does:

$$H(\text{Fair}) = -\big(0.5 \log_2 0.5 + 0.5 \log_2 0.5\big) = 1 .$$

A fair four-sided die has four equally likely outcomes, which takes two questions: $H = 2$ bits. And the loaded coin behaves as intuition demanded:

$$H(\text{Loaded}) = -\big(0.99 \log_2 0.99 + 0.01 \log_2 0.01\big) \approx 0.08 \text{ bits}.$$

For a Boolean variable it is convenient to write $B(q)$ for the entropy of something true with probability $q$:

$$B(q) = -\big(q \log_2 q + (1-q) \log_2 (1-q)\big).$$

Symmetric about $q = 0.5$, maximal there, and zero at certainty - exactly the shape we asked for. (By convention $0 \log 0 = 0$, which is also its limit.)

B. Information gain: how much a question tells you

Entropy becomes useful the moment you ask what a test buys you. Suppose a training set has $p$ positive and $n$ negative examples. Its entropy is $B\!\left(\frac{p}{p+n}\right)$.

Now test an attribute $A$ with $d$ values, splitting the set into subsets $E_1, \dots, E_d$, where $E_k$ holds $p_k$ positives and $n_k$ negatives. Going down branch $k$ leaves $B\!\left(\frac{p_k}{p_k+n_k}\right)$ bits still to resolve, and a random example takes that branch with probability $\frac{p_k+n_k}{p+n}$. So the expected entropy remaining after the test is

$$\text{Remainder}(A) = \sum_{k=1}^{d} \frac{p_k + n_k}{p + n}\, B\!\left(\frac{p_k}{p_k + n_k}\right),$$

and the information gain is the expected reduction in entropy:

$$\text{Gain}(A) = B\!\left(\frac{p}{p+n}\right) - \text{Remainder}(A).$$

Worked example. Twelve examples, six positive and six negative, so the starting entropy is $B(0.5) = 1$ bit exactly. An attribute splits them into a branch of 5 (4 positive, 1 negative) and a branch of 7 (2 positive, 5 negative).

Branch entropies: $B(4/5) = B(0.8) = 0.7219$ and $B(2/7) = B(0.2857) = 0.8631$.

Weights: $5/12 = 0.4167$ and $7/12 = 0.5833$.

$$\text{Remainder} = 0.4167 \times 0.7219 + 0.5833 \times 0.8631 = 0.8043 ,$$ $$\text{Gain} = 1.0000 - 0.8043 = 0.1957 \text{ bits}.$$

So this attribute resolves about a fifth of a bit out of the one bit of uncertainty we started with - a real but modest improvement.

Gain near zero flags an irrelevant attribute. If a test splits the data into subsets whose class proportions all look like the parent's, it has told you nothing, and the arithmetic above returns approximately zero. That makes information gain a usable signal for pruning as well as for splitting.

The figure below runs the same arithmetic on a different split: Russell & Norvig's restaurant data, also twelve examples with six positive and six negative, and two of its attributes. Patrons gains $0.5409$ bits; Type gains exactly $0$, the irrelevant attribute of the note above. Every branch is drawn as a bar and every number recomputed rather than quoted. The third control moves examples inside Patrons' one branch that is still mixed - the only place the gain can change without changing the question - and it shows something a single worked split cannot: the expected entropy left is highest when that branch is evenly split, while the gain is not simply lowest there, because moving an example changes the entropy the split started from as well.

C. A terminology trap worth naming

Decision Trees and Ensembles introduces the splitting criterion

$$D = -\sum_{k=1}^{K} \hat p_{mk} \log \hat p_{mk}$$

and calls it cross-entropy, following the statistical-learning convention. Read against this article, that is the formula for entropy - a single distribution scored against itself.

Information theory reserves cross-entropy for a quantity involving two distributions. Both names are standard in their own literature, and neither is wrong, but they are not the same object and the collision causes real confusion. When you meet "cross-entropy" as a tree-splitting criterion, read it as node entropy; the next section is about the other thing.

D. Cross-entropy and KL divergence

Suppose the truth is $p$ but you act on a belief $q$. Cross-entropy measures the average surprise you actually incur:

$$H(p, q) = -\sum_{i} p(x_i) \log_2 q(x_i) .$$

The weights are the true probabilities $p$; the surprises are computed from your belief $q$. If $q = p$ this collapses to $H(p)$. Otherwise it is strictly larger - you are systematically more surprised than necessary.

The excess has its own name. The KL divergence between $P$ and $Q$ is

$$\text{KL}(P, Q) = \sum_{i} P(x_i) \log_2 \frac{P(x_i)}{Q(x_i)} ,$$

and the three quantities are related by

$$H(p, q) = H(p) + \text{KL}(p \,\|\, q).$$

In words: your total surprise is the irreducible uncertainty in the world, plus a penalty for being wrong about it. Since $H(p)$ is fixed by reality, minimising cross-entropy over your model is exactly minimising KL divergence from the truth.

Check it numerically. Let the truth be a fair coin, $p = (0.5, 0.5)$, while you believe $q = (0.9, 0.1)$:

$$H(p) = 1.0000, \qquad H(p, q) = 1.7370, \qquad \text{KL}(p \,\|\, q) = 0.7370 .$$

And $1.0000 + 0.7370 = 1.7370$, as claimed.

KL is not a distance. It is not symmetric - $\text{KL}(P, Q) \neq \text{KL}(Q, P)$ in general - and it does not satisfy the triangle inequality. Calling it a "divergence" rather than a distance is deliberate. Note also that it blows up if $q(x) = 0$ where $p(x) > 0$: assigning zero probability to something that then happens is infinitely surprising.

Below, the source is fixed and the model is yours to move. Watch which of the two read-outs refuses to budge: the entropy is a property of the source, and no setting of the sliders touches it. Everything above that floor is the divergence, and it is the only thing training can ever reduce. The second panel breaks the cost down symbol by symbol, which is where the arithmetic stops being an average and starts being a diagnosis - the bits are rarely wasted where you would guess.

E. Why classifiers are trained on cross-entropy

This is where the theory earns its keep. A classifier outputs a probability distribution over labels; the ground truth is also a distribution - usually all mass on one label. Training the model means making its distribution match the true one, and cross-entropy is precisely the quantity measuring the gap. Chollet puts it directly: cross-entropy is a quantity from information theory measuring the distance between probability distributions, here between the ground-truth distribution and the model's predictions, and it is usually the right choice when a model outputs probabilities.

With the truth one-hot on class $c$, all terms but one vanish and the loss for that example is just

$$-\log q(c),$$

the surprise assigned to the correct answer. Confident and right costs nearly nothing; confident and wrong costs a great deal. That asymmetry - supplied by the logarithm, not bolted on - is what makes cross-entropy a better training signal than accuracy, which is flat almost everywhere and gives gradient descent nothing to descend.

This is the same reasoning that motivates the log-loss objective in Logistic Regression and Classification: the loss is not an arbitrary convenient function, it is the expected surprise of the model's beliefs under the true distribution.

The same entropy also measures what a noisy channel can carry, which is where the figure below goes one step beyond this article. It is a binary channel that flips each bit with probability $f$, and its capacity is $1 - B(f)$ bits per use. Set the flip probability to 0.1 and read 0.5310; to 0.5 and read exactly zero; past it, and watch the capacity climb back, because a channel that always lies can be inverted. The second panel is a separate example: two fair bits and a target that is their exclusive or, where either input alone carries exactly 0 bits about the target and the pair carries 1. And the processing slider sends the output through a second channel in series: its composite flip probability is $f(1-g) + g(1-f)$, never closer to certainty than $f$ was, so the information never rises.

Key takeaways

• Entropy $H(V) = -\sum_k P(v_k)\log_2 P(v_k)$ is expected surprise, measured in bits; base 2 makes it the average number of yes/no questions.
• A fair coin is exactly $1$ bit, a fair four-sided die $2$ bits, a 99% coin about $0.08$ bits, and a certain outcome $0$.
• Information gain is the expected entropy reduction from a test; our split moved $1$ bit to $0.8043$, a gain of 0.1957 bits.
• Statistical learning calls the tree criterion $-\sum \hat p \log \hat p$ "cross-entropy"; information theory calls that entropy. Same formula, different names, genuine confusion.
• Cross-entropy $H(p,q) = -\sum p \log q$ scores a belief $q$ against a truth $p$, and decomposes as $H(p) + \text{KL}(p \| q)$ - irreducible uncertainty plus a penalty for being wrong.
• KL divergence is asymmetric and unbounded; it is not a distance.
• Minimising cross-entropy is minimising KL from the truth, which is why it is the standard classification loss.

What's next

Entropy quantifies uncertainty inside a probabilistic model. A different tradition represents knowledge with statements that are simply true or false, and reasons about what must follow - Logic and Knowledge Representation.