Open In Colab

Chapter 2: Information Theory Fundamentals

Read this alongside lesson.md — this notebook contains exercises referenced in the lesson.

In chapter 1, you saw that language models predict the next token. But behind every prediction is a deeper question: how much information does language contain? How efficiently can we encode it? What happens when our assumptions about the data are wrong?

This chapter answers those questions using Shannon’s information theory — first measuring unpredictability (entropy), then measuring coding inefficiency (cross-entropy).

Part 1: Understanding Entropy

Corresponds to lesson sections 0-3

Before we can measure coding efficiency, we need to understand entropy — Shannon’s measure of unpredictability and the theoretical limit of compression.

Setup

# Install the course package
!pip install -q git+https://github.com/BaytAlhikmah/hands-on-llms-for-swes.git#subdirectory=pkg

print('✓ Setup complete!')

Exercise 1: Binary Decision Tree (Uniform Case)

Lesson section 1: The guessing game with 8 equally likely options

Visualize how binary search works when all outcomes are equally likely. With 8 options, you always need exactly \(\log_2(8) = 3\) questions.

import matplotlib.pyplot as plt
from alhikmah_llms import Chapter2

print("Expected: A balanced binary tree with 8 leaves at depth 3")
print("Each path from root to leaf represents a sequence of yes/no questions\n")

# Visualize the uniform case: 8 equally likely outcomes
Chapter2.draw_uniform_tree()
plt.show()

print("\nEntropy = log₂(8) = 3.0 bits")
print("Every path from root to leaf takes exactly 3 questions.")

Exercise 2: Binary Decision Tree (Biased Case)

Lesson section 1: The guessing game with biased probabilities

When outcomes aren’t equally likely, you can do better! Check the most probable outcome first.

print("Expected: A skewed binary tree where the most frequent outcome")
print("gets checked first (shortest path = 1 question)\n")

# Visualize the biased case: 50% on option 1, rest split among 2-8
Chapter2.draw_biased_tree()
plt.show()

print("\nEntropy ≈ 2.4035 bits")
print("50% of the time, you're done in 1 question!")
print("Average: 0.5 × 1 + 0.5 × 3.807 = 2.4035 questions")

Exercise 3: Visualize Probability Distributions

Lesson section 1: How entropy relates to the “spread” of probabilities

The more “spiky” the distribution, the lower the entropy.

print("Expected: Two bar charts comparing uniform vs biased distributions")
print("The uniform distribution should appear 'flat', the biased 'spiky'\n")

# Compare the distributions
Chapter2.plot_distributions()
plt.show()

print("\nKey Observation:")
print("   Uniform (flat) = maximum entropy = maximum unpredictability")
print("   Biased (spiky) = lower entropy = more predictable")

Exercise 4: Compute Entropy for Different Distributions

Lesson section 2: Deriving the entropy formula from first principles

Verify that the formula \(H = \sum p(x) \log_2\left(\frac{1}{p(x)}\right)\) matches our intuition.

import math

def entropy(probs: list[float]) -> float:
    """Average number of yes/no questions (bits) to guess the outcome."""
    return sum(p * math.log2(1/p) for p in probs if p > 0)

# Test the formula
uniform_8 = [1/8] * 8
biased = [0.5] + [0.5/7] * 7
certain = [1.0] + [0.0] * 7

print(f"Uniform (all equal):     {entropy(uniform_8):.4f} bits  (= log₂(8))")
print(f"Biased (50% on one):     {entropy(biased):.4f} bits")
print(f"Certain (100% on one):   {entropy(certain):.4f} bits")
print()
print("Lower entropy = more predictable = fewer questions needed")

Exercise 5: Implement and Test the Entropy Function

Lesson section 2: Understanding the two equivalent forms

The formula can be written as \(-\sum p \log_2(p)\) or \(\sum p \log_2\left(\frac{1}{p}\right)\). Why are they equivalent?

# Two equivalent forms
def entropy_form1(probs: list[float]) -> float:
    """Form 1: Σ p(x) × log₂(1/p(x))"""
    return sum(p * math.log2(1/p) for p in probs if p > 0)

def entropy_form2(probs: list[float]) -> float:
    """Form 2: -Σ p(x) × log₂(p(x))"""
    return -sum(p * math.log2(p) for p in probs if p > 0)

# Verify they're the same
test_probs = [0.6, 0.2, 0.1, 0.1]
h1 = entropy_form1(test_probs)
h2 = entropy_form2(test_probs)

print(f"Form 1: {h1:.6f} bits")
print(f"Form 2: {h2:.6f} bits")
print(f"Difference: {abs(h1 - h2):.10f}")
print()
print("Why equivalent? Because log₂(1/p) = log₂(1) - log₂(p) = 0 - log₂(p) = -log₂(p)")

Exercise 6: Compression Visualization

Lesson section 3B: Entropy as optimal compression size

See how entropy-based encoding saves space by assigning short codes to frequent symbols.

print("Expected: Visualization showing how frequent symbols get short codes")
print("and rare symbols get long codes in optimal compression\n")

Chapter2.plot_compression_example()
plt.show()

print("\nKey Insight:")
print("   Entropy = theoretical compression limit")
print("   Frequent symbols get short codes, rare symbols get long codes")

Exercise 7: Surprise Curve

Lesson section 3C: Entropy as average surprise

See how surprise \(= -\log_2(p)\) relates to probability.

print("Expected: A curve showing surprise decreases as probability increases")
print("High probability events → low surprise, low probability → high surprise\n")

Chapter2.plot_surprise_curve()
plt.show()

print("\nKey Insight:")
print("   High probability → low surprise (you expected it)")
print("   Low probability → high surprise (you didn't see that coming!)")
print("   Entropy = expected surprise across all possible outcomes")

Exercise 8: Explore Entropy Across Distributions

Lesson section 3: Interactive visualizations

Exercise 8a: Binary Entropy Function

The most fundamental curve in information theory — entropy of a coin flip with probability p.

print("Expected: A symmetric bell-shaped curve peaking at p=0.5")
print("showing entropy as a function of probability\n")

Chapter2.plot_binary_entropy()
plt.show()

print("\nKey Observation:")
print("   Maximum entropy at p=0.5 (fair coin flip)")
print("   Zero entropy at p=0 or p=1 (certain outcome)")
print("   Symmetric curve — this is the foundation of all entropy calculations!")

Exercise 8b: Ternary Entropy (3-outcome distributions)

Shows entropy for all possible 3-outcome probability distributions.

print("Expected: A 3D surface plot showing entropy over the probability simplex")
print("Peak at center (uniform), valleys at corners (certain outcomes)")
print("This is an interactive plot - click and drag to rotate!\n")

Chapter2.plot_ternary_entropy_3d_plotly().show()

print("\nKey Observation:")
print("   Click and drag to rotate the 3D surface!")
print("   Peak at center (uniform 1/3, 1/3, 1/3) = maximum entropy ≈ 1.585 bits")
print("   Valleys at corners (certain outcome) = zero entropy")

Exercise 8c: Mathematical Properties of Entropy

Now that you’ve seen entropy in action, let’s formalize its key mathematical properties. These properties uniquely characterize the entropy function and explain why it’s the “right” measure of uncertainty.

Property 1: Non-negativity \[H(X) \geq 0\]

Entropy is always non-negative. It equals zero only when one outcome has probability 1 (complete certainty).

Property 2: Maximum Entropy \[H(X) \leq \log_2(n)\]

For \(n\) possible outcomes, entropy is maximized when all outcomes are equally likely (uniform distribution). Maximum \(= \log_2(n)\) bits.

Property 3: Continuity

\(H\) is a continuous function of the probability distribution. Small changes in probabilities lead to small changes in entropy.

Property 4: Symmetry

\(H\) is invariant under permutation of outcomes. The order doesn’t matter, only the probabilities.

Property 5: Additivity (for independent events) \[H(X,Y) = H(X) + H(Y) \quad \text{[if X and Y are independent]}\]

The joint entropy of two independent random variables equals the sum of their individual entropies.

Property 6: Chain Rule \[H(X,Y) = H(X) + H(Y|X)\]

Joint entropy equals the entropy of \(X\) plus the conditional entropy of \(Y\) given \(X\).

Property 7: Conditioning Reduces Entropy \[H(Y|X) \leq H(Y)\]

Knowing \(X\) can only reduce (or leave unchanged) uncertainty about \(Y\). Information never increases uncertainty. Equality holds when \(X\) and \(Y\) are independent.

These properties aren’t just mathematical curiosities — they capture fundamental facts about information and uncertainty.

# Demonstrate the properties with examples

# Property 1: Non-negativity
print("Property 1: Non-negativity")
print("-" * 50)
certain = [1.0, 0.0, 0.0]
uniform = [1/3, 1/3, 1/3]
biased = [0.7, 0.2, 0.1]

print(f"  Certain outcome:  H = {entropy(certain):.4f} bits  (minimum)")
print(f"  Uniform:          H = {entropy(uniform):.4f} bits")
print(f"  Biased:           H = {entropy(biased):.4f} bits")
print(f"  All ≥ 0 ✓\n")

# Property 2: Maximum Entropy
print("Property 2: Maximum Entropy")
print("-" * 50)
n = 8
uniform_8 = [1/8] * 8
max_entropy = math.log2(n)
actual_entropy = entropy(uniform_8)
print(f"  For n={n} outcomes:")
print(f"  Maximum possible:  log₂({n}) = {max_entropy:.4f} bits")
print(f"  Uniform achieves:  H = {actual_entropy:.4f} bits")
print(f"  Any other distribution will have H < {max_entropy:.4f}")

# Test with non-uniform
non_uniform = [0.5, 0.1, 0.1, 0.1, 0.1, 0.05, 0.03, 0.02]
print(f"  Non-uniform:       H = {entropy(non_uniform):.4f} bits < {max_entropy:.4f} ✓\n")

# Property 4: Symmetry
print("Property 4: Symmetry")
print("-" * 50)
dist1 = [0.5, 0.3, 0.2]
dist2 = [0.2, 0.5, 0.3]  # Same probabilities, different order
dist3 = [0.3, 0.2, 0.5]  # Another permutation
print(f"  [0.5, 0.3, 0.2] → H = {entropy(dist1):.6f} bits")
print(f"  [0.2, 0.5, 0.3] → H = {entropy(dist2):.6f} bits")
print(f"  [0.3, 0.2, 0.5] → H = {entropy(dist3):.6f} bits")
print(f"  Order doesn't matter, only the probabilities ✓\n")

# Property 5: Additivity (independent events)
print("Property 5: Additivity for Independent Events")
print("-" * 50)
# Two independent coin flips
coin1 = [0.5, 0.5]  # Fair coin
coin2 = [0.6, 0.4]  # Biased coin

H_coin1 = entropy(coin1)
H_coin2 = entropy(coin2)

# Joint distribution for independent events: P(X,Y) = P(X) * P(Y)
joint = [coin1[i] * coin2[j] for i in range(2) for j in range(2)]
H_joint = entropy(joint)

print(f"  Coin 1:            H = {H_coin1:.4f} bits")
print(f"  Coin 2:            H = {H_coin2:.4f} bits")
print(f"  Sum:               H₁ + H₂ = {H_coin1 + H_coin2:.4f} bits")
print(f"  Joint (independent): H(X,Y) = {H_joint:.4f} bits")
print(f"  Difference: {abs(H_joint - (H_coin1 + H_coin2)):.6f} (should be ~0) ✓\n")

# Property 7: Conditioning Reduces Entropy
print("Property 7: Conditioning Reduces Entropy")
print("-" * 50)
print("  This is the key property for prediction!")
print("  Knowing context can only reduce uncertainty about what comes next.")
print("  We'll apply this in Chapter 3 with real sequence data:\n")
print("  - H(next move) without knowing previous = higher entropy")
print("  - H(next move | previous move) = lower entropy")
print("  - The reduction tells us how much context helps predict the next outcome\n")

print("Key Takeaway:")
print("   These properties explain why entropy is the 'right' way to measure uncertainty.")
print("   Any other measure that satisfies these axioms must be equivalent to Shannon entropy.")

Part 2: Cross-Entropy — Coding with Wrong Assumptions

Corresponds to lesson section 4

Goal: Show four different encoding trees for the same data to illustrate cross-entropy.

Data: File = “AAAAAABBCD” (10 characters) - True distribution P: A=60%, B=20%, C=10%, D=10%

Four scenarios: 1. Optimal codebook - Designed for P (A=60%, B=20%, C=10%, D=10%) 2. Uniform codebook - Designed for Q_uniform (A=25%, B=25%, C=25%, D=25%) 3. Wrong-biased codebook - Designed for Q_biased (C=50%, A=25%, B=12.5%, D=12.5%) 4. Reversed-priority codebook - Designed for Q_reversed (D=50%, C=25%, A=12.5%, B=12.5%)

We’ll compute the average bits per character when encoding P with each codebook.

Exercise 9: Tree 1 - Optimal for True Distribution P

True distribution: P = {A: 60%, B: 20%, C: 10%, D: 10%}

Huffman code: - A (60%): 0 (1 bit) - B (20%): 10 (2 bits) - C (10%): 110 (3 bits) - D (10%): 111 (3 bits)

Average bits \(= 0.6 \times 1 + 0.2 \times 2 + 0.1 \times 3 + 0.1 \times 3 = 1.6\) bits

This approximates \(H(P) \approx 1.57\) bits (the theoretical entropy). Huffman coding achieves near-optimal compression using integer bit lengths, so it can only approximate the true entropy, not achieve it exactly.

print("Expected: A Huffman tree optimized for the true distribution P")
print("Symbol A (most frequent) gets the shortest path (1 bit)\n")

Chapter2.draw_optimal_tree()
plt.show()

Exercise 10: Tree 2 - Uniform Codebook

Assumed distribution: Q_uniform = {A: 25%, B: 25%, C: 25%, D: 25%}

For uniform distribution, all symbols should get equal code length = 2 bits each: - A: 00 - B: 01 - C: 10 - D: 11

If we use this to encode the true data P:

Average bits \(= 0.6 \times 2 + 0.2 \times 2 + 0.1 \times 2 + 0.1 \times 2 = 2.0\) bits

This is \(H(P, Q_{\text{uniform}})\) = cross-entropy!

print("Expected: A balanced tree where all symbols get equal 2-bit codes")
print("This wastes bits because it ignores that A is much more frequent\n")

Chapter2.draw_uniform_tree()
plt.show()

Exercise 11: Tree 3 - Wrong-Biased Codebook

Assumed distribution: Q_biased = {A: 25%, B: 12.5%, C: 50%, D: 12.5%}

Huffman code designed for \(Q_{\text{biased}}\): - C (50%): 0 (1 bit) - A (25%): 10 (2 bits) - B (12.5%): 110 (3 bits) - D (12.5%): 111 (3 bits)

But we’re encoding P where A=60%, B=20%, C=10%!

Average bits \(= 0.6 \times 2 + 0.2 \times 3 + 0.1 \times 1 + 0.1 \times 3 = 2.2\) bits

This is \(H(P, Q_{\text{biased}})\) = even worse cross-entropy!

print("Expected: A tree that prioritizes C (wrong assumption!)")
print("This wastes even more bits because C is rare in the actual data\n")

Chapter2.draw_wrong_biased_tree()
plt.show()

🤔 Challenge: Can You Do Worse?

We’ve seen three codebooks: - Optimal: 1.6 bits (perfect!) - Uniform: 2.0 bits (+0.4 wasted) - Wrong-biased: 2.2 bits (+0.6 wasted)

Question: Can you design a tree/coding that does even worse?

Think about it: What would be the worst possible way to assign codes to our symbols?

💡 Hint (click to reveal)

What if we did the complete opposite of optimal? What if we gave: - The shortest codes to the least frequent symbols? - The longest codes to the most frequent symbols?

Would that be the worst case?

Exercise 12: Tree 4 - Reversed-Priority Codebook (Worst Case)

Yes, you CAN do worse! Here’s a very bad codebook for P using code lengths (1,2,3,3):

Assumed distribution: \(Q_{\text{reversed}} = \{A: 12.5\%, B: 12.5\%, C: 25\%, D: 50\%\}\)

This is the complete reverse of the optimal tree! We assign: - D (10% actual): 1 bit ← shortest code for least frequent! - C (10% actual): 2 bits - A (60% actual): 3 bits ← longest code for MOST frequent! 💀 - B (20% actual): 3 bits

Average bits \(= 0.6 \times 3 + 0.2 \times 3 + 0.1 \times 2 + 0.1 \times 1 = 2.7\) bits

This is \(H(P, Q_{\text{reversed}})\) = a very poor cross-entropy!

Wasted: \(2.7 - 1.6 = 1.1\) bits per character (69% more than optimal!)

Important Note: This is the worst possible with code lengths (1,2,3,3), but can we do worse?

Yes! Cross-entropy has no upper bound, but not by arbitrarily picking code lengths. Instead:

\[H(P,Q) = -\sum_{x} P(x) \log_2 Q(x)\]

  • If Q assigns very low probability to symbols that P considers likely, \(H(P,Q) \to \infty\)
  • Example: If \(Q = \{A: 0.01, B: 0.33, C: 0.33, D: 0.33\}\), then \(H(P,Q) \approx 5.0\) bits
  • As \(Q(A) \to 0\) while \(P(A) = 0.6\), we get \(H(P,Q) \to \infty\)

The key: you can construct arbitrarily bad Q distributions, not arbitrarily long code sets!

print("Expected: The WORST tree - gives shortest codes to rarest symbols!")
print("This is the opposite of optimal coding\n")

Chapter2.draw_worst_case_tree()
plt.show()

Exercise 13: Side-by-Side Comparison of All Four Trees

From optimal (Q=P) to reversed-priority (opposite of optimal).

print("Expected: Four trees side-by-side showing progression from")
print("optimal (1.6 bits) to worst-case reversed (2.7 bits)\n")

Chapter2.draw_all_four_comparison()
plt.show()

Exercise 14: Calculate Entropy and Cross-Entropy Numerically

# True distribution P
P = {'A': 0.6, 'B': 0.2, 'C': 0.1, 'D': 0.1}

# Codebook 1: Optimal for P
codes_optimal = {'A': '0', 'B': '10', 'C': '110', 'D': '111'}

# Codebook 2: Uniform
codes_uniform = {'A': '00', 'B': '01', 'C': '10', 'D': '11'}

# Codebook 3: Wrong-biased (C gets shortest code, designed for Q where C is most frequent)
codes_biased = {'C': '0', 'A': '10', 'B': '110', 'D': '111'}

# Codebook 4: Reversed-priority (complete reverse of optimal)
codes_reversed = {'D': '0', 'C': '10', 'A': '110', 'B': '111'}

def average_bits(P_dist, codebook):
    """Calculate average bits per character when encoding P with codebook."""
    return sum(P_dist[char] * len(codebook[char]) for char in P_dist)

def entropy(P_dist):
    """Calculate Shannon entropy H(P)."""
    return -sum(p * math.log2(p) for p in P_dist.values() if p > 0)

def cross_entropy(P_dist, Q_dist):
    """Calculate cross-entropy H(P,Q) = -∑ P(x) log₂ Q(x)"""
    return -sum(P_dist[x] * math.log2(Q_dist[x]) for x in P_dist if Q_dist[x] > 0)

H_P = entropy(P)
avg_optimal = average_bits(P, codes_optimal)
avg_uniform = average_bits(P, codes_uniform)
avg_biased = average_bits(P, codes_biased)
avg_reversed = average_bits(P, codes_reversed)

print("="*70)
print("ENTROPY AND CROSS-ENTROPY COMPARISON")
print("="*70)
print(f"\nTrue distribution P: A=60%, B=20%, C=10%, D=10%")
print(f"\nH(P) = Entropy of P = {H_P:.4f} bits")
print(f"  → Theoretical minimum bits per character\n")

print(f"1. Optimal codebook (designed for P):")
print(f"   Average bits = {avg_optimal:.4f} bits")
print(f"   Wasted = {avg_optimal - H_P:.4f} bits (≈ 0, very close to optimal!)\n")

print(f"2. Uniform codebook (designed for Q_uniform):")
print(f"   H(P, Q_uniform) = {avg_uniform:.4f} bits")
print(f"   Wasted = {avg_uniform - H_P:.4f} bits (+{((avg_uniform/H_P - 1)*100):.1f}%)\n")

print(f"3. Wrong-biased codebook (designed for Q_biased):")
print(f"   H(P, Q_biased) = {avg_biased:.4f} bits")
print(f"   Wasted = {avg_biased - H_P:.4f} bits (+{((avg_biased/H_P - 1)*100):.1f}%)\n")

print(f"4. Reversed-priority codebook (designed for Q_reversed):")
print(f"   H(P, Q_reversed) = {avg_reversed:.4f} bits")
print(f"   Wasted = {avg_reversed - H_P:.4f} bits (+{((avg_reversed/H_P - 1)*100):.1f}%)\n")

print("="*70)
print("CAN WE DO WORSE? YES - CROSS-ENTROPY IS UNBOUNDED!")
print("="*70)

# Show how cross-entropy grows as Q becomes more mismatched
Q_bad1 = {'A': 0.01, 'B': 0.33, 'C': 0.33, 'D': 0.33}
Q_bad2 = {'A': 0.001, 'B': 0.333, 'C': 0.333, 'D': 0.333}

H_PQ_bad1 = cross_entropy(P, Q_bad1)
H_PQ_bad2 = cross_entropy(P, Q_bad2)

print(f"\n5. Very bad Q₁ (A=1%, others≈33% each):")
print(f"   H(P, Q₁) = {H_PQ_bad1:.4f} bits")
print(f"   Wasted = {H_PQ_bad1 - H_P:.4f} bits (+{((H_PQ_bad1/H_P - 1)*100):.0f}%)\n")

print(f"6. Extremely bad Q₂ (A=0.1%, others≈33% each):")
print(f"   H(P, Q₂) = {H_PQ_bad2:.4f} bits")
print(f"   Wasted = {H_PQ_bad2 - H_P:.4f} bits (+{((H_PQ_bad2/H_P - 1)*100):.0f}%)\n")

print("As Q(A) → 0 while P(A) = 60%, we get H(P,Q) → ∞")

print("\n" + "="*70)
print("KEY INSIGHTS:")
print("="*70)
print("Cross-entropy H(P,Q) = -∑ P(x) log₂ Q(x)")
print("\nAlways: H(P,Q) ≥ H(P)")
print("Equality only when Q = P (perfect match!)")
print("\nCross-entropy grows when Q assigns:")
print("  • Low probabilities to symbols that P considers likely")
print("  • High probabilities to symbols that P considers unlikely")
print(f"\nWith code lengths (1,2,3,3): ranges from {avg_optimal:.2f} to {avg_reversed:.2f} bits")
print("With arbitrarily bad Q: can approach infinity!")
print("="*70)

Summary Visualization

Let’s create a bar chart showing all four scenarios from optimal to reversed-priority.

Exercise 15: Interactive Exploration - The Full Coding Spectrum

What about all the other possible codings between optimal and reversed-priority? Let’s visualize the complete range of possibilities with code lengths (1,2,3,3)!

Important Distinction:

This visualization shows two related but different values:

  1. Average Code Length (x-axis): Σ P(x) × length(code_x)
    • Practical value from Huffman coding with integer bit lengths
    • What we showed in the trees above (1.6, 2.0, 2.2, 2.7 bits)
  2. Actual Cross-Entropy H(P,Q): -Σ P(x) log₂ Q(x)
    • Theoretical value (can be fractional)
    • Requires knowing the distribution Q that the code lengths imply
    • For Huffman codes, code length L ≈ -log₂ Q(x), so Q(x) ≈ 2^(-L)

The two values are close but not identical because Huffman uses integer lengths. Hover over the points to see both values and the implied Q distribution!

print("Expected: Interactive plot showing all possible code assignments")
print("Hover over points to see average bits and cross-entropy values\n")

Chapter2.interactive_cross_entropy().show()
print("Expected: Bar chart comparing all four coding schemes")
print("Shows the range from optimal to reversed-priority\n")

Chapter2.plot_cross_entropy_spectrum(avg_optimal, avg_uniform, avg_biased, avg_reversed, H_P)

plt.tight_layout()
plt.show()

Key Takeaways

What we learned:

  1. Cross-entropy \(H(P,Q) = -\sum_{x} P(x) \log_2 Q(x)\) measures the average bits needed to encode distribution \(P\) using a code designed for distribution \(Q\)

  2. Always \(H(P,Q) \geq H(P)\), with equality only when \(Q = P\) (perfect codebook)

  3. Cross-entropy is bounded below but NOT above:

    • Lower bound: \(H(P) \approx 1.57\) bits (Shannon entropy, theoretical minimum)
    • Huffman optimal: 1.6 bits (practical minimum with integer bit lengths)
    • With code lengths (1,2,3,3): ranges from 1.6 bits (optimal) to 2.7 bits (reversed-priority)
    • No upper bound: As Q assigns very low probabilities to symbols that P considers likely, \(H(P,Q) \to \infty\)
    • The limit comes from the math: if \(P(A) = 0.6\) and \(Q(A) \to 0\), then \(-P(A) \log_2 Q(A) \to \infty\)

  4. Wrong assumptions are costly: The more mismatched Q is from P, the more bits you waste!

Connection to Machine Learning:

In neural language models: - P = true distribution of next tokens in your data - Q = model’s predicted distribution
- Cross-entropy loss \(= H(P,Q) = -\sum_{x} P(x) \log_2 Q(x)\) - Training = adjusting Q to minimize \(H(P,Q)\), bringing it closer to \(H(P)\)

Part 3: Transitioning from Bits to Nats

Corresponds to lesson section 5

So far, we used \(\log_2\) (bits). From now on, we use \(\ln\) (nats).

Why the switch? - Machine learning libraries use natural log (PyTorch, TensorFlow) - Derivatives are cleaner: \(\frac{d}{dx}(\ln x) = \frac{1}{x}\) - Standard in ML papers and frameworks

Conversion: \(\text{bits} = \frac{\text{nats}}{\ln(2)} \approx \text{nats} \times 1.443\)

### Exercise 16: Compare Bits vs Nats

# Compare bits vs nats
P = [0.7, 0.2, 0.1]
Q = [0.65, 0.25, 0.1]

# Cross entropy in nats (natural log)
ce_nats = -sum(p * math.log(q) if q > 0 else 0 for p, q in zip(P, Q))

# In bits (log2)
ce_bits = -sum(p * math.log2(q) if q > 0 else 0 for p, q in zip(P, Q))

print(f"Cross-entropy in NATS: {ce_nats:.4f}")
print(f"Cross-entropy in BITS: {ce_bits:.4f}")
print(f"Ratio: {ce_bits / ce_nats:.4f} ≈ 1 / ln(2) ≈ 1.443")

print("\nFrom now on, we use NATS (natural log).")

Summary and Connection to Machine Learning

What We Learned

Information Theory Fundamentals: 1. Entropy \(H(P)\) = optimal compression size for distribution \(P\) (in nats or bits) 2. Cross-entropy \(H(P,Q)\) = actual size when compressing \(P\) with codebook designed for \(Q\) 3. We use nats (natural log) instead of bits in ML

Connection to Machine Learning

Why does this matter for language models?

In Chapter 3, you’ll see that: - Prediction = Compression: A model that predicts well can compress well - Cross-entropy becomes loss: \(H(P,Q)\) measures how well model \(Q\) predicts data from \(P\) - Training minimizes waste: Gradient descent reduces cross entropy by making \(Q\) match \(P\)

The language of compression (codebooks, bit lengths) is the same as the language of prediction (probabilities, losses). This isn’t a coincidence — Shannon showed they’re equivalent.

Next Steps

Chapter 3 applies these concepts to real data: - Rock-Paper-Scissors sequences - Character bigrams in text - Transition matrices and pattern exploitation - The \(V^2\) memory wall that motivates neural networks