Information Theory

Self-information

A weather forecast that says “80% chance of rain” hardly surprises you when it rains. A forecast of “1% chance of snow in July” is news if the snow falls. Information theory turns that feeling into a number for each outcome .

The number has three rules. Likely events carry little information, and a certain event carries none. Rarer events carry more. Independent events add their information.

The book defines the self-information of an outcome as Equation 3.48:

Here is the probability of that outcome, and log is the natural logarithm. The unit is the nat. One nat is the information gained from an event of probability 1/e, about 0.37. Other books use base 2 and call the unit a bit. One bit is 1 / ln 2, about 1.44 nats, so the unit is only a rescaling.

Set both sliders to 1 and nothing is learned. Set one to 0.5 and that event carries 1 bit, the content of one fair coin flip, or 0.69 nats. The dot for the pair sits at the product of the two probabilities, far to the left. Its height equals the two heights added together.

The book gives an example: a tossed coin that has come up heads twice should convey twice as much information as heads once. Two independent fair coins make this concrete. Each head of a fair coin carries 0.69 nats.

The book also contrasts the sun rising, which is almost certain and carries almost no information, with a solar eclipse, which is rare and carries much more.

Self-information describes one outcome, and only its probability matters. The next section averages it over all outcomes.

Shannon entropy

A distribution produces many outcomes, each with its own surprise. The Shannon entropy averages that surprise over the distribution. Equation 3.49 writes it as the expected self-information of one draw:

The symbol is the expected value over draws from , where each outcome is weighted by how often it occurs. The same number is written .

The book gives two readings:

• Uncertainty. Nearly deterministic distributions have low entropy, and distributions close to uniform have high entropy.
• Code length. The entropy is a lower bound on the average number of bits needed to encode symbols drawn from , in base 2. Other bases change the unit.

The coin: Figure 3.5

Take a binary variable that equals 1 with probability . Figure 3.5 plots its entropy against , using the formula in its caption. That formula is not a numbered equation:

At and the coin is certain and the entropy is 0. It peaks at , where both outcomes are equally likely: ln 2 nats, which is exactly 1 bit. The curve is steepest near the ends.

Entropy as area, and as code length

With more outcomes, draw each one as a rectangle. Its width is and its height is in bits, so its area is its share of the entropy. The orange line marks the length of a Huffman code word for that outcome. Huffman coding is not in the book. It is added here as a concrete code, so that you can check the code-length reading.

The average code length never falls below the entropy and stays within one bit above it. That bound is standard coding theory, not printed in the book, and the readout checks it on your weights. A weight of 0 means the outcome never occurs, so it adds nothing.

Continuous variables and differential entropy

For a continuous variable the book uses the same definition by analogy, with the density in place of the probability. The result is the differential entropy. The book does not print the integral below. It is the standard form of the analogy, written here:

The book warns that some properties of the discrete case are lost. An event with unit density still has zero information, although it is not certain. This remark is added here and is not in the book: a density can be larger than 1, so the information of an outcome, minus the logarithm of its density, can be negative.

Set the width to 1 and the entropy is 0. Narrow the uniform density below 1 and its entropy goes negative. That does not mean less than no uncertainty. The number depends on the units of : rescaling by a factor shifts the differential entropy by . This remark is added here and is not in the book.

Among all densities with a given variance, the normal has the largest differential entropy. This is a standard fact, added here for context.

The KL divergence

Two distributions and over the same outcomes need a number that says how different they are. The book uses the Kullback-Leibler (KL) divergence, Equation 3.50:

The average is over , as the subscript says. Each outcome contributes the log of the ratio , weighted by how often produces it. In the second form it is the average of two self-informations: minus .

The book points out three properties. The divergence is never negative, which the book calls its most notable property. It is zero if and only if the distributions agree, for discrete variables, or equal almost everywhere for continuous ones. And it is not symmetric, so for some pairs. A true distance must be symmetric, so the divergence is not one.

When says an outcome is impossible but still produces it, the code for has no word for it. The cost is unbounded and is infinite. The reverse direction stays finite, because outcomes that never produces drop out of its average. That is the asymmetry in its starkest form.

The direction of the divergence

Because the divergence is asymmetric, using or as an objective gives different answers. Figure 3.6 shows it. The target has two separated peaks. We approximate it with one Gaussian , with center and width , by minimizing one divergence or the other.

• Minimizing keeps the approximation where the target is high. With two peaks it blurs them together.
• Minimizing keeps the approximation where the target is small. With well separated peaks it picks one peak, and it could equally pick the other.

Press the first button. The best Gaussian for sits between the peaks and is wide enough to cover both. Then press the second and third buttons. The best Gaussian for sits on one peak and ignores the other, and both peaks give the same value. Lower the distance until the peaks merge, and the two answers coincide. The book adds a caveat: when the two peaks are not separated by a strong low-probability region, the reverse divergence can still blur them.

Cross-entropy and the 0 log 0 convention

The cross-entropy is the average cost of coding draws from with a code built for . Equation 3.51 defines it:

The book also states that it equals the entropy of plus the divergence. The identity is stated in the text and is not numbered:

The cost of the best code, the entropy , is a floor. The cross-entropy is that floor plus the extra paid for using the wrong code, which is the divergence.

The curve touches the floor exactly where equals , and everywhere else it lies above. The gap is . Near the ends the curve rises steeply: a model that gives almost no probability to an outcome that happens often pays a large cost.

The convention for 0 log 0

Expressions of the form 0 log 0 appear when an outcome has probability 0. The book treats them as the limit as , and that limit is 0.

Slide down. The product shrinks to 0 even though log goes to minus infinity, because shrinks faster. The convention applies only to the weight in front of the logarithm, so it does not rescue a divergence where is 0 and is positive.

What to take away

• Self-information measures surprise. It is 0 for certain events, grows for rare ones, and adds for independent ones. In nats it uses the natural logarithm; in bits, base 2.
• Shannon entropy is the average surprise. It is 0 for a deterministic distribution, largest for a uniform one, and a lower bound on the average code length.
• For continuous variables the same definition gives the differential entropy, which can be negative and depends on units.
• The KL divergence is the extra information paid for using a code built for on draws from . It is never negative, zero only when the distributions agree (almost everywhere), and not symmetric.
• The direction matters. makes cover the target and may blur its modes, while lets pick a single mode.
• The cross-entropy equals plus . The two differ by a term that does not involve , so minimizing either over gives the same answer.
• By convention the term 0 log 0 equals 0, the limit of as .

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 3.13 (pages 73–76), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.