Information theory

Information theory, founded by Claude Shannon (1948), studies how to measure, represent, and efficiently communicate information.

Originally developed for electronic communication, it now underpins many fields, including deep learning, where it helps evaluate model performance.

Surprise and context

Surprise

Communication involves a sender transferring some form of message to a receiver.

The surprise of a message describes how unexpected it is to the receiver: the more surprising, the more information it conveys.

To visualize this, imagine a subjective surprise scale:

• 0 → completely expected
• 100 → total surprise

An unexpected text message beginning with:

• "Thanks" might rank at 20
• "Hippopotamus" might rank at 80 (that's unusual unless the topic is already related)

Context

Context is the environment that gives meaning to a message.

It comes in two forms:

1. global context:
   • shared knowledge between sender and receiver (language, grammar, cultural norms, and general expectations)
2. local context:
   • immediate environment within the message, e.g., surrounding words

Context helps determine how surprising a word is:

• "Hippopotamus" might be highly surprising alone
• but less so after "Let's go to the zoo and see a big gray…"

Measuring surprise

To connect surprise to probability, we can assign a "surprise value" to each word in a dictionary (a tedious but possible job).

Scaling these values to sum to 1 produces a probability mass function (pmf) from which we can randomly draw words.

Two ways to sample from a pmf:

1. sampling by surprise values: the pmf is proportional to surprise, so surprising words are more likely to be drawn
2. sampling by commonness: the pmf is proportional to frequency, so common/less surprising words are more likely to be drawn (this is the approach used most in practice)

Measuring information

Information in a message can be quantified using a mathematical formula with two inputs:

1. the text of the message
2. a probability distribution (a pmf) that describes how surprising each word (or event) is

For each word:

• the formula calculates a number based on its probability
• this number is called the word's entropy
• it represents how much information the word carries, measured in bits, or how many bits are needed to communicate that word

The total information of a message is found by adding up the entropy of each word.

The formula is designed to satisfy four properties, illustrated here using an "office context" rather than a "river":

1. likely events (common words) have low information
   • e.g., "stapler"
2. unlikely events (rare words) have high information
   • e.g., "crocodile"
3. likely events have less information than unlikely events
   • e.g., "stapler" conveys less information than "crocodile"
4. the information from two unrelated events adds together
   • if someone asked us for a "kumquat daffodil", the words are completely unrelated
   • the information in the phrase is found by adding the information of each word

Fixed vs adaptive codes

The amount of information each message carries depends on the size of the possible vocabulary.

Transmitting a text is more efficient if we use a custom word list reflecting that text's vocabulary rather than a universal word list.

This principle of adapting transmission to content underlies adaptive coding.

	Adaptive code	Fixed code
Definition	An adaptive code is a code where time required to send a message depends on the specific letter patterns it contains. E.g., Morse code represents each character with patterns of dots, dashes, and timed spaces, where transmission length is measured in units called "dits".	A fixed code is a code where every character takes the same time to transmit. E.g., imagine a Morse code where every character takes the same time (9 dits).
Image
Time to transmit "Squire Trelawney" (15 characters)	101 dits of time	177 dits of time: 15 characters × 9 dits = 135 dits 14 silences between letters × 3 dits = 42 dits (Morse code requires a silence of 3 dits between letters)

To improve efficiency, Morse code adapts to human language use:

• frequently used English letters are assigned shorter patterns
• less frequent letters are assigned longer ones

Codes that improve efficiency this way are called variable-bitrate code or adaptive code.

For the full Treasure Island text (338,000 characters), an adaptive code would take only 42% of the time of a fixed-length code.

We can go further: instead of a code tuned to English in general, we could design one perfectly matched to the letter frequencies in Treasure Island itself.

Entropy (or uncertainty)

Surprise refers to things we didn't expect.

A related concept is uncertainty: we know all possible outcomes of a process but not which one will occur (for example, rolling a fair die). The formal name for this uncertainty is entropy.

Entropy is used in different fields:

• in physics, it means "disorder"
• in information theory, it means "uncertainty"
• both ideas are similar: the more mixed or unpredictable something is, the higher its entropy

Example – mixing coffee and milk:

• before mixing: coffee and milk are separate → low disorder (physics) and low uncertainty (information theory) → low entropy
• after mixing: coffee and milk are blended → high disorder and unpredictability → high entropy

Entropy depends on:

1. the number of possible outcomes:
   • more possible outcomes → more uncertainty → higher entropy
   • examples:
     • flipping a coin → 2 outcomes (each with probability 1/2)
     • rolling a die → 6 outcomes (each with probability 1/6)
     • picking a random letter → 26 outcomes (each with probability 1/26)
2. the probability of each outcome:
   • evenly distributed probabilities produce higher entropy
   • maximum entropy = all outcomes are equally likely
   • zero entropy = one outcome is certain (probability = 1)

In machine learning, entropy underpins measures like cross entropy.

Cross entropy

Entropy measures the uncertainty within a single probability distribution.

Cross entropy measures the difference between two probability distributions.

Two adaptive codes

We use Treasure Island and The Adventures of Huckleberry Finn to build an adaptive code for each.

Each book has its own word frequency pattern, which defines a probability distribution over words:

• common words (like "the") → high probability
• rare words → low probability

Adaptive coding uses this distribution to minimize transmission cost:

• high-probability words → short codes
• low-probability words → long codes

Because the two books have different probability distributions, each requires its own optimized code.

Their vocabularies are unified by adding any missing words to each code, so that either code can represent both books.

When encoding text:

Using a code tuned to a different book requires more bits because the code is optimized for a different probability distribution.

That inefficiency is what cross entropy measures.

Cross entropy in practice

In training a photo classifier, we compare two probability distributions:

1. the label manually created to describe the photo
2. the probabilities predicted by the system

Cross entropy measures how wrong the predictions are compared to the labels:

• larger cross entropy → larger error
• smaller cross entropy → better match

E.g., classifying a picture of a dog:

• start of training (left): predictions poorly match labels → cross entropy ≈ 1.9
• after much training (right): predictions match labels better → cross entropy ≈ 1.6

Our goal in training is to try to minimize the cross entropy to make two distributions (the predictions and the labels assigned by hand) as similar as possible.

Kullback-Leibler divergence

Cross entropy measures the difference between two distributions.

Kullback-Leibler divergence (KL divergence) is the part of that difference that comes specifically from the mismatch between the distributions: KL divergence = cross entropy - entropy.

Smaller values indicate more similar distributions.

In practice:

• cross entropy is usually preferred because it is simpler and faster to compute
• KL divergence is more common in technical and theoretical discussions