Information Theory for Machine Learning

Phase 0 · Week 7 · ~8–10 hours

Information theory answers a precise question: how much “surprise” or “uncertainty” is contained in a probability distribution, and how much information is shared between two variables? These questions turn out to be the exact foundation for understanding loss functions (cross-entropy IS an information-theoretic quantity), model comparison (KL divergence IS an information-theoretic distance), and the compression perspective on learning itself. This is a short but high-density module — every concept here maps directly to something you’ve already used without knowing why.

Why Information Theory Is Not Just Theory

The connection to ML practice is immediate and exact:

Information Theory Concept

ML Appearance

Shannon Entropy H(P)

Minimum expected bits to encode a random variable; appears in decision tree splitting criteria

Cross-Entropy H(P, Q)

The standard classification loss function

KL Divergence KL(P‖Q)

VAE loss term, RL policy optimization, model comparison

Mutual Information I(X; Y)

Feature selection, disentangled representations, information bottleneck

Core Concepts

1. Shannon Entropy

Entropy measures the average uncertainty in a distribution. High entropy = high uncertainty = more bits needed to describe outcomes.

H(P) = -Σₓ P(x) log₂ P(x)     (bits, base 2)
H(P) = -Σₓ P(x) ln P(x)       (nats, base e — used in ML)

import numpy as np

def entropy(p, base='nats'):
    """Shannon entropy of a discrete distribution."""
    p = np.array(p, dtype=float)
    p = p / p.sum()  # normalize
    # Filter out zero probabilities (0 * log(0) = 0 by convention)
    p_nonzero = p[p > 0]
    if base == 'bits':
        return -np.sum(p_nonzero * np.log2(p_nonzero))
    else:  # nats
        return -np.sum(p_nonzero * np.log(p_nonzero))

# Minimum entropy: all probability on one outcome
p_certain = [1.0, 0.0, 0.0, 0.0]
print(f"H(certain): {entropy(p_certain, 'bits'):.4f} bits")  # 0.0

# Maximum entropy: uniform distribution (most uncertain)
p_uniform = [0.25, 0.25, 0.25, 0.25]
print(f"H(uniform 4): {entropy(p_uniform, 'bits'):.4f} bits")  # 2.0 (= log2(4))

# Intermediate
p_skewed = [0.7, 0.1, 0.1, 0.1]
print(f"H(skewed): {entropy(p_skewed, 'bits'):.4f} bits")  # ~1.36

# ML connection: decision tree splitting maximizes information gain
# = choosing split that maximizes H(parent) - weighted H(children)

Why entropy appears in decision trees: When a decision tree splits a node, it chooses the feature that maximizes information gain — the reduction in entropy after the split. A pure node (all one class) has H = 0. A maximally impure node (50/50 binary) has H = 1 bit. The Gini impurity (also used in trees) is a cheaper-to-compute approximation of entropy.

2. Cross-Entropy — The ML Loss Function, Derived

Cross-entropy H(P, Q) measures the average bits needed to encode events from distribution P using a code optimized for distribution Q:

H(P, Q) = -Σₓ P(x) log Q(x)

Where P is the “true” distribution and Q is our “model” distribution.

def cross_entropy(p_true, q_model, eps=1e-10):
    """Cross-entropy H(P, Q)."""
    p = np.array(p_true, dtype=float)
    q = np.array(q_model, dtype=float) + eps
    p = p / p.sum()
    q = q / q.sum()
    return -np.sum(p * np.log(q))  # nats

# Binary classification example
# True labels (one-hot): y = [1, 0] → class 0
# Model output (softmax): q = [0.8, 0.2]

y_true = [1.0, 0.0]  # one-hot, class 0
q_good = [0.9, 0.1]  # confident correct prediction
q_bad  = [0.1, 0.9]  # confident wrong prediction
q_random = [0.5, 0.5]  # uncertain prediction

print(f"CE (confident correct): {cross_entropy(y_true, q_good):.4f}")   # ~0.105
print(f"CE (uncertain):         {cross_entropy(y_true, q_random):.4f}") # ~0.693
print(f"CE (confident wrong):   {cross_entropy(y_true, q_bad):.4f}")    # ~2.303

# Key insight: CE for one-hot labels reduces to:
# H(P, Q) = -log Q(true_class)
# This is exactly PyTorch's nn.CrossEntropyLoss / F.cross_entropy

# Verify:
import scipy.special
logits = np.array([2.0, 0.5])  # raw logits
probs = np.exp(logits) / np.sum(np.exp(logits))  # softmax
true_class = 0

ce_manual = -np.log(probs[true_class])
print(f"\nManual CE: {ce_manual:.4f}")
# PyTorch equivalent: F.cross_entropy(logits, torch.tensor([0]))

The derivation chain (burn this into memory):

  1. Assume labels y follow Categorical(softmax(logits))

  2. MLE = maximize Σᵢ log P(yᵢ | xᵢ) = maximize Σᵢ log softmax_{yᵢ}(f(xᵢ))

  3. Equivalently, minimize -Σᵢ log softmax_{yᵢ}(f(xᵢ))

  4. This IS cross-entropy loss

Cross-entropy is not a heuristic. It is the negative log-likelihood of a categorical model. Every time you use it, you’re doing MLE.

3. KL Divergence — Revisited from Information Theory

In the previous file, we computed KL numerically. Here’s the information-theoretic meaning:

KL(P‖Q) = H(P, Q) - H(P) = excess bits needed to encode P-events using Q-code vs P-code

def kl_divergence(p, q, eps=1e-10):
    p = np.array(p, dtype=float) + eps
    q = np.array(q, dtype=float) + eps
    p, q = p / p.sum(), q / q.sum()
    return np.sum(p * np.log(p / q))

P = [0.4, 0.3, 0.2, 0.1]
Q = [0.25, 0.25, 0.25, 0.25]

H_P = entropy(P)
H_PQ = cross_entropy(P, Q)
KL_PQ = kl_divergence(P, Q)

print(f"H(P) = {H_P:.4f} nats")
print(f"H(P,Q) = {H_PQ:.4f} nats")
print(f"KL(P‖Q) = {KL_PQ:.4f} nats")
print(f"H(P,Q) = H(P) + KL(P‖Q)? {np.isclose(H_PQ, H_P + KL_PQ)}")  # True

# Minimizing cross-entropy H(P,Q) w.r.t. Q
# = minimizing KL(P‖Q) + constant H(P)
# = making the model distribution Q as close as possible to the true distribution P
# This is the information-theoretic interpretation of training

KL in Variational Autoencoders (VAE): The VAE loss = Reconstruction Loss + β · KL(q(z|x) ‖ p(z))

  • Reconstruction term: forces decoder to reconstruct inputs (cross-entropy or MSE)

  • KL term: forces the encoder’s latent distribution q(z|x) to be close to the prior p(z) = N(0,I)

  • β controls the tradeoff (β-VAE)

4. Mutual Information

Mutual information I(X; Y) measures how much knowing X reduces uncertainty about Y (and vice versa):

I(X; Y) = H(X) - H(X|Y)
         = H(Y) - H(Y|X)
         = KL(P(X,Y) ‖ P(X)P(Y))

I(X;Y) = 0 means X and Y are independent. I(X;Y) > 0 means they share information.

def mutual_information_discrete(joint_probs):
    """
    Compute I(X; Y) from a joint probability table.
    joint_probs: 2D array where [i,j] = P(X=i, Y=j)
    """
    joint = np.array(joint_probs, dtype=float)
    joint = joint / joint.sum()
    
    p_x = joint.sum(axis=1)  # marginal P(X)
    p_y = joint.sum(axis=0)  # marginal P(Y)
    
    mi = 0.0
    for i in range(joint.shape[0]):
        for j in range(joint.shape[1]):
            if joint[i, j] > 0:
                mi += joint[i, j] * np.log(joint[i, j] / (p_x[i] * p_y[j]))
    return mi

# Example: Weather (sunny/rainy) and umbrella (yes/no)
# Highly correlated
joint_correlated = [[0.4, 0.05],  # P(sunny, no-umb), P(sunny, umb)
                    [0.05, 0.5]]  # P(rainy, no-umb), P(rainy, umb)

# Independent variables
joint_independent = [[0.5 * 0.5, 0.5 * 0.5],
                     [0.5 * 0.5, 0.5 * 0.5]]

print(f"MI (correlated): {mutual_information_discrete(joint_correlated):.4f} nats")
print(f"MI (independent): {mutual_information_discrete(joint_independent):.4f} nats")
# correlated ≈ 0.60 nats, independent ≈ 0.0

ML connections for Mutual Information:

  1. Feature selection: Select features with highest MI with target variable (sklearn’s mutual_info_classif)

  2. InfoNCE loss (contrastive learning): CLIP, SimCLR maximize a lower bound on mutual information between augmented views

  3. Information Bottleneck: A framework (Tishby et al.) that says deep networks learn to compress inputs while preserving task-relevant information — formally expressed as minimizing I(X; Z) subject to I(Z; Y) ≥ threshold

  4. Disentangled representations: β-VAE disentangles by minimizing MI between latent dimensions

The Compression View of Learning

There’s a beautiful unifying perspective: a trained model is a compressed representation of the training data. Information theory makes this precise.

  • A model with fewer parameters than data points has compressed the data

  • The training loss measures the compression quality (how well can you reconstruct/predict?)

  • Regularization limits model capacity = enforces compression

  • Generalization = the compressed representation captures the true data-generating process, not the noise

This is not just philosophy — it’s the basis of Minimum Description Length (MDL) and relates to Kolmogorov complexity. For your purposes: when you’re choosing between models of different complexities, you’re implicitly making information-theoretic trade-offs about how much to compress the data.

What Most Learners Get Wrong

They treat entropy and cross-entropy as separate topics from loss functions.

They are the same topic. The moment you write criterion = nn.CrossEntropyLoss(), you are using Shannon’s cross-entropy formula from 1948. The naming is not coincidental — it is the exact same mathematical object. Understanding this unifies probability, information theory, and loss design into a single coherent framework.

Second gap: forgetting the direction of KL divergence matters. KL(P‖Q) is called “forward KL” — it’s what you minimize in MLE/cross-entropy training. It penalizes Q for being zero where P is nonzero (mass-covering behavior). KL(Q‖P) is “reverse KL” — used in variational inference. It penalizes Q for being nonzero where P is zero (mode-seeking behavior). These produce qualitatively different approximations.

Practice Problems with Acceptance Criteria

Problem 1 — Entropy of a Decision Tree Split Implement information_gain(parent_labels, left_labels, right_labels) that computes the reduction in entropy from a binary split. Verify on a hand-computed example (perfect split → IG = full entropy).

  • Acceptance criteria: information_gain([0,0,1,1], [0,0], [1,1]) returns 1.0 bit. Function uses your own entropy(), not sklearn.

Problem 2 — Cross-Entropy Loss Match Implement cross_entropy_loss(y_true_onehot, logits) in numpy. Verify it matches torch.nn.CrossEntropyLoss (or sklearn’s log_loss) on the same inputs.

  • Acceptance criteria: Max absolute difference < 1e-5 on 100 random examples.

Problem 3 — Mutual Information Feature Selection Load the breast cancer dataset from sklearn. Compute mutual information between each feature and the binary target using your own mutual_information_discrete() implementation (after discretizing features into 10 bins). Compare ranking to sklearn.feature_selection.mutual_info_classif.

  • Acceptance criteria: Top-3 features match between your implementation and sklearn. Explain why MI is better than correlation for feature selection (hint: MI captures non-linear relationships).

Resources

Resource

Focus

Time

Free?

3Blue1Brown “But what is entropy?”

Visual intuition

~25 min

✅

Elements of Information Theory (Cover & Thomas) Ch. 1–2

Rigorous foundations

~4 hrs

Partial

Chris Olah “Visual Information Theory” (blog)

Excellent visual explainer

~1.5 hrs

✅

StatQuest entropy/decision tree videos

ML application

~1 hr

✅

Best single resource: Chris Olah’s blog post “Visual Information Theory” (colah.github.io). It connects entropy, cross-entropy, KL divergence, and mutual information with clean visual intuitions in a single 45-minute read. Start there.

Return to README.md · Next: 05_phase_projects.md