Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 37 ยท Entropy and Information

KL Divergence and Cross-Entropy

Understand relative entropy (KL divergence) and cross-entropy: the extra bits you pay for coding with the wrong model, Gibbs' inequality, and the link to log-loss in machine learning.

Suppose the true distribution of a source is p, but you built your code, or your machine-learning model, for a different distribution q. How much worse off are you? Two closely related quantities answer this: cross-entropy H(p, q) and the Kullback-Leibler (KL) divergence D(p || q).

They are everywhere: the loss you minimize when training a classifier is a cross-entropy, and the gap between a model and reality is a KL divergence.

Cross-entropy: coding with the wrong model

If you design an ideal code for q, it spends -log2 q(x) bits on symbol x. But symbols actually arrive according to p, so the average cost is

TEXT
H(p, q) = - sum over x of p(x) log2 q(x)

When q = p this is the ordinary entropy H(p). Otherwise it is larger.

Python Cost of the wrong model

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the right model you pay 1.75 bits per symbol. A uniform guess costs 2 bits. A confidently wrong model costs far more.

KL divergence: the extra bits

The excess cost over the optimum is the KL divergence (also called relative entropy):

TEXT
D(p || q) = sum over x of p(x) log2 [ p(x) / q(x) ] = H(p, q) - H(p)

It is the number of extra bits per symbol wasted by using a code built for q when the truth is p.

Key facts:

  • Gibbs' inequality: D(p || q) >= 0, with equality iff p = q. The right model is the best model.
  • It is not symmetric: D(p || q) != D(q || p) in general, so it is not a true distance.
  • It is infinite if q(x) = 0 while p(x) > 0: your code has no word for a symbol that occurs.
Python KL is non-negative and asymmetric

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two directions differ, D(p||p) is exactly 0, and putting probability 0 on a symbol that can occur gives infinity.

Verify with SciPy

scipy.stats.entropy(p, q) computes the KL divergence, in nats by default; pass base=2 for bits. With one argument it returns the plain entropy.

Python Compare with scipy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first two lines match, and the nats line divided by ln 2 gives the same value again.

Why machine learning minimizes cross-entropy

In classification, the true label distribution for one example is a one-hot vector p (probability 1 on the right class). The model outputs predicted probabilities q. Then H(p, q) = -log q(true class), the familiar log-loss. Because H(p) is fixed (0 for one-hot labels), minimizing cross-entropy over the data is the same as minimizing the KL divergence between the data and the model, which is also the same as maximizing likelihood.

Python Log-loss is cross-entropy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two computations agree. Perfect predictions would give a loss of 0; assigning probability 0.01 to the correct class costs -log2(0.01) = 6.6 bits.

Deep-learning libraries compute cross-entropy with natural logs, so their numbers are in nats. A loss of 0.693 for a two-class problem is ln 2: the model is guessing 50/50.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does D(p || q) measure in coding terms?

    D(p||q) = H(p, q) - H(p): the excess of the cross-entropy over the optimum.
  2. 2. Which statement about KL divergence is true?

    Gibbs' inequality gives D >= 0 with equality iff p = q. It is asymmetric and infinite if q misses a symbol that p can produce.
  3. 3. For one-hot labels, the cross-entropy loss for one example equals

    With a one-hot p, H(p, q) = -log q(true class), the standard log-loss.
  4. 4. scipy.stats.entropy(p, q) returns its result in

    The default base is e. Pass base=2 for bits.

Summary

  • Cross-entropy H(p, q) = -sum p log q is the average code length when data follow p but the code is built for q.
  • KL divergence D(p || q) = H(p, q) - H(p) >= 0 is the wasted bits; it is zero only when q = p, and it is not symmetric.
  • Classification log-loss is cross-entropy with one-hot targets; minimizing it equals maximum likelihood.
  • Library results are often in nats; convert with ln 2.

Next: Properties and Inequalities