Information Theory Weeks 1-2

Shannon's two limits: Entropy and Capacity

Entropy H(X): The limit of lossless compression; How few bits can represent information?

Capacity C: The limit of reliable communication; How fast can information be transmitted?

Entropy: Definition and Meaning

Entropy measures the average uncertainty of a random variable.

Entropy formula

Binary Entropy

A binary random variable has two possible outcomes, 0 and 1.

Uniform Distribution

Every possible outcome has the same probability

Jensen's Inequality (Concave Form)

A function is concave if it curves downward, like an upside-down bowl.

The average of a concave function's outputs is less than or equal to the function evaluated at the average input.

Bounds on Entropy

|X| means the number of possible outcomes

When does maximum entropy occur?

When all possible outcomes are equally likely.

Entropy as the Average Number of Yes/No Questions

Imagine I secretly select one of eight equally likely numbers.

You need to figure out which number I chose by asking yes/no questions.

A good strategy is to eliminate half the remaining possibilities with each question.

ex: takes 3 questions (bits) find one of eight equally likely numbers

Joint entropy

Measures the uncertainty of two random variables considered together

Joint entropy when X and Y are independent

Joint entropy when Y = X

H(X,Y) = 1 bit

Because once you know X, you automatically know Y.

The chain rule

Total uncertainty = uncertainty of the first variable + uncertainty remaining about the second after learning the first.

Conditional Entropy

How much uncertainty remains about Y after we observe X?

Conditional Entropy Formula

1. Find the entropy of Y for each possible value of X.

2. Weight each conditional entropy by the probability of that X.

3. Add them together.

Condition ___ entropy

Reduces

Conditional Entropy cases

Mutual Information: Definition

Mutual information measures how much knowing one random variable reduces uncertainty about another.

Three properties of mutual information

Deterministic Processing

What happens when you transform a random variable using a deterministic function (which always gives the same output for the same input)

Deterministic Processing Property

Applying a deterministic function cannot increase the entropy of a discrete random variable.

The function can combine different input values into the same output, potentially losing information.

Conditional Mutual Information

How much does Y tell us about X when we already know Z?

Conditioning ____ mutual information

does not necessarily reduce

Chain Rule for Mutual Information

Markov Chains

X → Y → Z

p(z | x, y) = p(z | y)

Once we know Y, knowing X provides no additional information about Z.

Data Processing Inequality

Processing information cannot create additional information about the original source.

Fano's Inequality

If there's still a lot of uncertainty about X after observing Y, it's impossible to predict X with extremely low error.

KL divergence

KL divergence, also called relative entropy, measures how different one probability distribution is from another.

Imagine two distributions:

• p(x): the true probability distribution.

• q(x): your model's estimated distribution.

KL divergence measures the penalty associated with using q when the truth is p.

KL divergence formula

Properties of Relative Entropy

Mutual Information as KL Divergence

p(X, Y) = the actual joint distribution of X and Y.

p(X)p(Y) = what the joint distribution would be if X and Y were independent

KL Example: Bernoulli

KL Example: Gaussian

Forward KL vs Reverse KL

Cross-Entropy

Measures the average surprise when data comes from the true distribution p, but we predict using another distribution q.

Cross entropy relationship

Cross-entropy = inherent uncertainty + penalty for using an imperfect model

Cross-entropy is minimized when q matches p.

Classification loss

Perplexity