Information theory

1Why measure information?

In Week 1 the umbrella agent got better when it remembered a week of past weather, then got worse with two weeks. In Week 2 one well-chosen number did as well as a week of memory. Both results raise the same question: how much does a clue actually tell you?

Some clues are worth a lot. Some are worth nothing. Some look large but are mostly repetition. If we could put a number on "how much this tells me", we could compare clues, compare memories and compare agents on one scale. That number exists. Claude Shannon worked it out in 1948 while thinking about telephone lines, and it turned out to be about far more than telephones.

This week builds it in three steps: the surprise of one event, the average surprise of a whole situation (entropy), and how much one thing reduces the surprise of another (mutual information). Then we use it to score forecasters and to see why predicting and compressing are the same skill.

2Surprise, measured in bits

Play a game. A friend picks a number from 1 to 8 and you may only ask yes-or-no questions. The smart way is to halve the possibilities each time: "Is it 4 or less?" "Is it 2 or less?" "Is it 1?" Three questions always do it, because 2 × 2 × 2 = 8. With 16 numbers you need four questions; with 2 numbers, one.

Each yes-or-no answer that halves the possibilities is one bit of information. Learning which of 8 equally likely options happened gives you 3 bits.

Now turn this around. If something had probability 1/8 and it happened, you just received 3 bits. Rarer things carry more bits; certain things carry none. That gives the surprise of an event with probability p:

• A fair coin lands heads: p = 1/2, surprise = 1 bit.
• A die shows six: p = 1/6, surprise ≈ 2.585 bits. A bit more than two questions' worth.
• The sun rises: p ≈ 1, surprise ≈ 0. You learned nothing.
• Rain on a day you gave a 1% chance: p = 0.01, surprise ≈ 6.6 bits. Very surprising.

Why a logarithm rather than just 1/p? Because surprises should add up. Two coin flips both landing heads has probability 1/4 and surprise 2 bits: one bit for each coin. The logarithm turns "multiply the probabilities" into "add the surprises".

3Entropy: average surprise

Surprise is about one event. Entropy is about a whole situation: how surprised you will be on average before you know what happens. Weight each outcome's surprise by how often it happens and add up:

That is the expected value from Week 2, applied to surprise. In code it is one line:

def entropy(probs):
    return sum(p * math.log2(1 / p) for p in probs if p > 0)

entropy([0.5, 0.5])        # fair coin: 1.000 bit
entropy([1/6] * 6)         # fair die: 2.585 bits
entropy([0.425, 0.575])    # rain in the umbrella world: 0.984 bits

Entropy measures how uncertain you are. Equivalently, it is how many yes-or-no questions you need, on average, to find out what happened. Table 1 shows it for a coin that is bent more and more.

Three things to notice:

• Entropy is largest when every outcome is equally likely. A fair coin is as unpredictable as a two-outcome thing can be.
• It falls slowly at first. A 60/40 coin is still almost as uncertain as a fair one (0.971 bits).
• It reaches zero only when the outcome is certain. No uncertainty, nothing to learn.

Rain in the umbrella world happens on 42.5% of days, so its entropy is 0.984 bits: very close to a fair coin. Before looking at anything, the weather is nearly as hard to guess as a coin toss. Everything an agent does to predict it better is an attempt to bring that number down.

4Mutual information: what a clue is worth

The agent looks at the sky. How much does that reduce its uncertainty about rain? Before looking, the uncertainty is 0.984 bits. After looking, it is the entropy of rain given the sky, averaged over cloudy and clear mornings. Using Week 2's Table 1: on cloudy mornings rain has probability 0.60, on clear ones 0.30, and the average leftover uncertainty works out to 0.918 bits. The difference is the information the sky carries about rain:

This is mutual information: how many bits of uncertainty about one thing disappear when you learn another. It is never negative, since on average a clue cannot make you more uncertain, and it is zero exactly when the two things are independent (Week 2, Section 3). It is also symmetric: the sky tells you as much about rain as rain tells you about the sky.

0.065 bits may look tiny. It is a real but weak clue: enough to lift accuracy from 57.5% (always guess "dry") to about 66%, as Week 1 found, but far from the full 0.984 bits that would make rain certain.

Measuring the Week 1 clues

Now the payoff. The Week 1 agent saw two things: today's sky and how many of the last k days were rainy. Part B of the code simulates 200,000 days in each of the two Week 1 worlds and measures, by counting, how many bits that clue carries about today's rain.

Put this next to Week 1's Table 2 and the pattern is the same, column for column:

• Random seasons: memory adds no bits at all, and in Week 1 it added no accuracy. When yesterday is independent of today, remembering it is useless.
• Long seasons: information rises from 0.066 to 0.202 bits as memory grows to 7 days, then falls at 14. Accuracy did exactly the same.

The fall at 14 is now less mysterious. A count of rainy days over two weeks really does contain less information about today than a count over one week, because it lumps recent days, which matter, together with old days that may belong to a different season. The Week 1 learner did not fail to use the information. The information was not there.

Exploratory observation This supports the Week 1 hypothesis that old days drown out recent ones, but only for this one way of summarising memory (a plain count). Seminar exercise 3 asks whether a different summary of the same 14 days does better.

(The sky-only values, 0.066 and 0.063, should both be 0.065, as equation 3 says. Counting from a finite sample always wobbles a little. Keep that in mind whenever a number comes from data.)

5Scoring forecasts in bits

So far our agents said "umbrella" or "no umbrella". A more useful agent says "70% chance of rain", like a weather forecast. How do we score that? Being right or wrong is not enough, because a forecast of 51% and one of 99% would both count as "right" when it rains.

The information-theory answer: score each day by how surprised the forecaster was at what actually happened, and average over days. If it said 0.7 and it rained, surprise = log₂(1/0.7) ≈ 0.51 bits. If it said 0.7 and it stayed dry, surprise = log₂(1/0.3) ≈ 1.74 bits. Lower average surprise is better. This average is called the cross-entropy or log loss, and it is the most common way to train and score machine-learning models that output probabilities.

def bits_per_day(forecasts, days):
    # Average surprise at what actually happened. Lower is better.
    return sum(math.log2(1 / (p if rained else 1 - p))
               for p, (_, rained) in zip(forecasts, days)) / len(days)

The ordering is what you would hope: each extra piece of knowledge lowers the score. The forecaster that always says 0.425 scores almost exactly the entropy of rain (0.984 bits), which makes sense: it knows how often it rains and nothing else.

Look at the last row. The overconfident forecaster uses the same clue as "sky only" and takes the umbrella on exactly the same days, so its accuracy is identical. But it scores far worse than knowing nothing at all. Every clear day that rains, it was 99% sure of dry weather and pays log₂(1/0.01) ≈ 6.6 bits. Log loss rewards honest uncertainty and punishes false confidence hard.

6Prediction is compression

Here is one of the most important ideas in this course. Suppose you want to store a long weather record, one day per character: 1101000111…. Stored as text, each day takes 8 bits. Can you do better?

Yes, and how much better depends on how well you can predict. The trick is to give short codes to things you expect and long codes to things that surprise you, much like a text-message shorthand uses short forms for common words. Shannon showed two things. Any forecaster can be turned into a code whose average length is about its average surprise, and no code can do better than the average surprise of the best possible predictor. A forecaster with a log loss of 0.825 bits per day can, in principle, be turned into a compressor that stores the record in about 0.825 bits per day. (The method, called arithmetic coding, comes very close to this in practice.) No method can beat the average surprise of the best possible predictor.

Part D of the code tests this with two general-purpose compressors from Python's standard library, the kind used for ZIP files.

Read it this way:

• Both compressors do far better than plain text, but neither reaches the limit. They look for repeated patterns in general; they know nothing about seasons.
• In the random world the limit is 0.984 bits, the entropy of a single day. Today is independent of the past, so nothing in the past can help.
• In the long-season world the limit drops to 0.825, because the past does predict the future. The compressors also do better here: finding patterns and predicting are the same activity.

Established result The link between prediction and compression is a theorem (Shannon, 1948), not an observation from our simulation. The table just shows it at work.

This is why many researchers treat compression as a test of understanding. An agent that has found the structure in its world, such as "seasons last about 50 days", can describe its experience in fewer bits than one that has not. We will return to this idea when we discuss representation (Week 7) and theories of intelligence (Week 11).

7Summary

• The surprise of an event with probability p is log₂(1/p) bits. Rare events carry more information.
• Entropy is average surprise: how uncertain you are before you look. It is largest when all outcomes are equally likely and zero when one is certain.
• Mutual information is how much learning one thing reduces uncertainty about another. It is zero for independent things.
• Measured in bits, the Week 1 memory clues rise and fall exactly as Week 1's accuracy did. More memory can contain less useful information if it is summarised badly.
• Cross-entropy (log loss) scores probability forecasts by average surprise. It punishes overconfidence much more than accuracy does.
• The average surprise of the best predictor is the limit on how far data can be compressed. Prediction and compression are two views of the same thing.

·Key terms

Bit

The information in one yes-or-no answer between two equally likely options.

Surprise

log₂(1/p): how much information an event of probability p carries. Also called self-information.

Entropy

The average surprise of a distribution, H; a measure of uncertainty.

Conditional entropy

The uncertainty left about one thing once you know another, H(Y | X).

Mutual information

I(X; Y) = H(Y) − H(Y | X): how much knowing X reduces uncertainty about Y.

Cross-entropy, log loss

The average surprise of a forecaster at what actually happened. Lower is better.

Overconfidence

Giving probabilities closer to 0 or 1 than the evidence supports.

Compression

Storing data in fewer bits by exploiting what is predictable about it.

Arithmetic coding

A method that turns any probability forecaster into a compressor whose code length is close to the forecaster's log loss.

·Check your understanding

Try each question before opening the answer.

1. How many bits of surprise is drawing one particular card from a shuffled deck of 52?
   Show answer

   log₂ 52 ≈ 5.7 bits. A little under six yes-or-no questions, since 2⁶ = 64 is just more than 52.

2. Which has more entropy: a fair coin, or a fair four-sided die? By how much?
   Show answer

   The die: 2 bits against 1. Four equally likely outcomes need two yes-or-no questions; two need one.

3. A clue has zero mutual information with the thing you care about. What does that mean, and what would happen to a learner that uses it?
   Show answer

   The clue and the target are independent: knowing the clue does not change the probabilities at all. A learner can gain nothing from it, which is exactly what happened to memory in the random-season world (Table 2 here, Table 2 in Week 1).

4. A forecaster says 0.9 chance of rain, and it stays dry. Another says 0.6, and it stays dry. How many bits does each lose that day?
   Show answer

   log₂(1/0.1) ≈ 3.32 bits for the first and log₂(1/0.4) ≈ 1.32 bits for the second. Being confidently wrong costs much more.

5. Why could no compressor store the random-season rain record in fewer than about 0.984 bits per day, however clever it is?
   Show answer

   In that world each day is independent of the past, with rain 42.5% of the time. The best possible predictor can only say 0.425 every day, and its average surprise is the entropy, 0.984 bits. Compression cannot beat the best predictor.

·Seminar exercises

As always, write your prediction before you run anything.

1. Twenty questions. Play in pairs with a number from 1 to 1,000. Count your questions over five rounds. Compare with log₂ 1,000. Then play with the rule that the number is chosen by rolling two dice and adding them (2 to 12). Is halving the range still the best strategy? Why not?
2. Entropy of English. Count the letters in a page of any English text and compute the entropy of the letter distribution. Compare with log₂ 26. Then compress the same text with zlib and work out bits per letter. Why is the compressed size lower than the letter entropy?
3. A better summary of memory. Instead of counting rainy days in the last 14 equally, give recent days more weight (for example, count only the last 7, or weight each day by 0.9 per day of age, then round into a few bins). Use mutual_information to measure how many bits your summary carries. Can you beat 0.202 bits with 14 days of data?
4. Calibration. Take the "sky only" forecaster and replace 0.60 and 0.30 with other pairs: (0.7, 0.2), (0.5, 0.4), (0.9, 0.1). Score each in bits per day. Which pair is best, and why does it match the true conditional probabilities from Week 2?

·Readings

• Core. MacKay, D. J. C. (2003). Information theory, inference, and learning algorithms. Cambridge University Press. Chapter 1 and Sections 2.4–2.5. The book is freely available online from its author.
• Core. Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27. Read the introduction and Section 6, "Choice, uncertainty and entropy". It is more readable than its reputation.
• Further. Cover, T. M., & Thomas, J. A. (2006). Elements of information theory (2nd ed.). Wiley. Chapter 2, for entropy, mutual information and their conditional forms, which the course's research programme uses.