Information Theory

Knowing X reduces our uncertainty about Y from H(Y) = 1.0 bit to 0.722 bits. The mutual information I(X;Y) = H(Y) − H(Y|X) = 1.0 − 0.722 = 0.278 bits.

This matches I(X;Y) = H(Y) − H(Y|X) = 1.0 − 0.722 = 0.278. Mutual information is symmetric: knowing X tells you as much about Y as knowing Y tells you about X.

If X and Y are independent, H(X,Y) = H(X) + H(Y). So I(X;Y) = H(X) + H(Y) − H(X,Y) = 0. Equivalently, H(Y|X) = H(Y) — learning X doesn't reduce uncertainty about Y at all. Mutual information is always ≥ 0.

Equivalently: the pair (X,Y) has 36 equally likely outcomes, so H = log₂(36) = log₂(6²) = 2·log₂(6) = 5.170 bits.

Knowing whether it rains reduces temperature uncertainty by 0.4 bits. This is intuitive — rainy days tend to be cooler, so rain gives you partial information about temperature.

The fair distribution P "wastes" 0.737 bits when encoded using a code optimized for Q. This is asymmetric — compare with D_KL(Q||P) in the next exercise.

D_KL(P||Q) ≠ D_KL(Q||P) in general, though in this specific case with P uniform they happen to relate simply. The asymmetry becomes dramatic when Q has a zero probability where P is nonzero — that makes D_KL(P||Q) = ∞.

Very close distributions have very small KL. This is why KL works well as a loss — as the model distribution approaches the target, the loss smoothly approaches zero.

D_KL(P||Q) requires computing log(p/q). When p > 0 but q = 0, we get log(p/0) = ∞. This is infinite divergence — a code designed for Q literally cannot encode an event that Q says is impossible but P says can happen. This is why in ML, we use label smoothing or add small ε to predicted probabilities.

Cross-entropy is always at least as large as the true entropy H(P). The gap is exactly D_KL — the "cost of being wrong." This is why minimizing cross-entropy is equivalent to minimizing KL divergence (since H(P) is fixed).

javascript
function klDivergence(p, q) {
  let kl = 0;
  for (let i = 0; i < p.length; i++) {
    if (p[i] === 0) continue;
    if (q[i] === 0) return Infinity;
    kl += p[i] * Math.log2(p[i] / q[i]);
  }
  return kl;
}

In bits: 0.357 × 1.443 = 0.515 bits. The loss only depends on the predicted probability of the true class. If the model predicted 0.99 for the true class, the loss would be −ln(0.99) = 0.01 nats — nearly perfect.

The model was very confident in the wrong class. The loss is huge. If the model had predicted exactly 0 for the true class, the loss would be infinity — this is why we never let softmax outputs reach exact zero.

With label smoothing, the loss is higher (0.517 vs 0.357) even with the same predictions, because we're penalizing the model for not spreading some probability to the non-true classes. This acts as regularization.

For one-hot labels, cross-entropy and KL divergence are identical. This is why minimizing cross-entropy loss is exactly the same as minimizing KL divergence from the labels. The two objectives are interchangeable.

javascript
function crossEntropy(p, q) {
  let ce = 0;
  for (let i = 0; i < p.length; i++) {
    if (p[i] > 0) ce -= p[i] * Math.log(q[i]);
  }
  return ce;
}

Equivalently: bits = nats × log₂(e) = 3.2 × 1.4427 = 4.617. Perplexity = 2^bits = 2^4.617 ≈ 24.5, meaning the model is "as confused as choosing uniformly among 24.5 tokens."

Step 1: Merge D(0.1) + E(0.1) = DE(0.2). Queue: A(0.4), B(0.2), C(0.2), DE(0.2).

Step 2: Merge B(0.2) + C(0.2) = BC(0.4). Queue: A(0.4), BC(0.4), DE(0.2).

Wait — we should merge the two smallest: actually after step 1, we pick the two smallest from {A:0.4, B:0.2, C:0.2, DE:0.2}. That's any two of {B, C, DE}. Merge C(0.2) + DE(0.2) = CDE(0.4). Queue: A(0.4), B(0.2), CDE(0.4).

Step 3: Merge B(0.2) + A(0.4) or B(0.2) + CDE(0.4). Merge B(0.2) + CDE(0.4) = BCDE(0.6). Queue: A(0.4), BCDE(0.6).

Step 4: Merge A(0.4) + BCDE(0.6) = root.

Result: A=1 bit (code: 0), B=3 bits (code: 100), C=3 bits (code: 110), D=3 bits (code: 1110), E=3 bits (code: 1111). Actually this depends on tie-breaking. One valid Huffman: A:1, B:3, C:3, D:3, E:3.

The entropy was 2.122 bits. The Huffman code achieves 2.2 bits — only 0.078 bits above the theoretical minimum. The efficiency is H/L = 2.122/2.2 = 96.5%. A better Huffman tree (codes A:1, B:2, C:3, D:4, E:4 or similar) could get closer.

Same average! Different valid Huffman trees can produce different code assignments, but the average code length is always the same. This Huffman average of 2.2 is optimal — no prefix-free code can do better for these probabilities.

We saved 80,000 bits (10 KB). The theoretical limit would be 100,000 × 2.122 = 212,200 bits, giving ratio 1.414:1. Huffman gets us 96.5% of the way there.

1. Count frequencies → 2. Build tree (merge lowest-probability nodes) → 3. Assign codes (left=0, right=1 from root) → 4. Encode (replace each symbol with its code) → 5. Header (prepend the codebook so the decoder can reconstruct the tree).

Even with 10% bit flips, we can still reliably communicate at 0.531 bits per channel use. The trick is using error-correcting codes that add redundancy — you send more bits than needed, and the decoder corrects the errors.

Doubling the bandwidth doubles the capacity (linear). But doubling the SNR only adds log₂(2) ≈ 1 bit/s/Hz in the high-SNR regime. Bandwidth is precious; power is cheap. This drives engineering decisions in telecommunications.

Real Wi-Fi 5 (802.11ac) on a 20 MHz channel achieves about 87 Mbits/s — roughly 65% of Shannon capacity. The gap is due to practical coding, guard intervals, and protocol overhead.

At p = 0.5, the output is a random coin flip regardless of input — zero information passes through. But at p = 1.0, every bit is flipped deterministically. The receiver just inverts every bit and recovers the original perfectly. C = 1 − H_b(1.0) = 1 − 0 = 1 bit. A channel that always flips is just as good as one that never flips!

Halving the bandwidth requires ~10x more power (SNR). This exponential tradeoff is why bandwidth is the more valuable resource — spectrum is scarce, transmit power is adjustable.

To represent a Gaussian source with 10% of its variance as distortion, you need at least 1.661 bits per sample. This is the absolute floor — no quantizer can do better.

Halving the distortion costs exactly 0.5 bits per sample for a Gaussian source. This is a universal rule for Gaussian R-D: each halving of distortion adds 0.5 bits. Equivalently, each additional bit reduces distortion by factor of 4 (6 dB per bit).

This says ~3.3 bits per weight is the theoretical minimum for 1% distortion. In practice, 4-bit quantization (INT4) works well for many models — it's slightly above the theoretical limit. Going to 2-bit quantization would give D = σ²/2⁴ = 0.000625, which is 6.25% of variance — often too much.

R(D) = 0.5·log₂(σ²/D). Setting R = 0: 0 = 0.5·log₂(σ²/D), so σ²/D = 1, meaning D = σ². With zero bits, the optimal strategy is to always output the mean (0), giving MSE = E[X²] = σ². You can't encode anything, so you just predict the most likely value.

Each additional bit buys a 4x reduction in distortion. In dB: 10·log₁₀(4) = 6.02 dB. This "6 dB per bit" rule is a cornerstone of audio/video engineering and quantization theory.

The DPI says: for X → T → Y, I(X;Y) ≥ I(T;Y). Each processing step can only lose information. So I(X;Y) ≥ I(T₁;Y) ≥ I(T₂;Y). A network must preserve the right information — it can't synthesize new predictive information about Y.

Note H_b(0.9) = H_b(0.1) = 0.469 since H_b(p) = H_b(1−p). Knowing X reduces uncertainty about Y by 0.397 bits — a substantial fraction of H(Y). The channel is informative but noisy.

A sufficient statistic T captures everything about Y that X contained, while potentially discarding irrelevant details of X. This is the ideal: I(X;T) can be much smaller than H(X) (compression), but I(T;Y) = I(X;Y) (no label information lost). The information bottleneck objective seeks exactly this: minimize I(X;T) subject to preserving I(T;Y).

Higher β means we value label information more relative to compression. At β = 1, the cost of storing 2 bits dominates. At β = 5, the label information is so valuable that the Lagrangian is very negative (good). The IB method sweeps β to trace the optimal tradeoff curve.

MI = H(T) − H(T|Y) requires knowing the distribution of T. For a 768-dimensional hidden representation, estimating this density is essentially impossible with finite samples. This is the "curse of dimensionality" for MI estimation. Modern approaches use variational bounds (MINE, InfoNCE) or binning with caveats. This difficulty is why the information plane theory remains controversial.

The encoder is moderately close to the prior — μ is only 0.5 away from 0, and σ = 0.8 is fairly close to 1. The KL cost per dimension is small. In a VAE with hundreds of latent dimensions, these small per-dimension costs add up.

ELBO = E[log p(x|z)] − KL. The reconstruction term is a negative log-likelihood, typically reported as a positive loss. So ELBO = −50.0 − 3.2 = −53.2. Maximizing the ELBO (making it less negative) means: (1) improve reconstruction (decrease the 50.0), and (2) keep the posterior close to the prior (decrease the 3.2). In practice, we minimize −ELBO = 53.2.

Posterior collapse: q(z|x) = p(z) regardless of x, so KL = 0 — the "information cost" is zero because the encoder transmits zero information. But this means the decoder gets no useful signal from z and must model p(x) entirely on its own, giving poor reconstruction. The fix: KL annealing — start with low KL weight and gradually increase it, letting the encoder learn useful representations before being penalized for diverging from the prior.

Total = 0.227 + 0.083 + 0.816 = 1.126 nats. Dimension 2 dominates: it has both a shifted mean (μ=0.8) and a narrow variance (σ=0.4), making it most different from the N(0,1) prior. Dimension 1 contributes least because its wider variance (σ=1.2) partially offsets the small mean shift.

Line 6 computes the negative ELBO contribution (which is negative, not the KL itself). The KL divergence is KL = −0.5·(1 + log(σ²) − μ² − σ²). The line is missing the negative sign. It should be: kl += -0.5 * (1 + logvar[i] - mu[i]*mu[i] - sigma2);. Without the negation, the sum is negative (since σ² + μ² > 1 + log(σ²) for typical values), making KL appear negative, which violates KL ≥ 0.

This is the zero-order (unigram) entropy — treating each character as independent. Real English text has much lower entropy (~1.0–1.5 bits/char) because of sequential dependencies. The gap between unigram entropy and true entropy is what n-gram and neural language models exploit.

We can compress to ~41% of the original size using just unigram statistics. Real compressors (gzip, zstd) do even better because they exploit sequential patterns. The Shannon limit with full context is ~1.2 bits/char × 10,000 = 1,500 bytes — a 6.67:1 ratio.

Huffman: H ≤ L < H + 1 (per symbol). Arithmetic coding can approach H to within O(1/n) total bits for a sequence of length n. For long sequences, arithmetic coding is near-optimal. This is why modern compressors (zlib, zstd, ANS) use arithmetic-coding variants rather than Huffman.

This model is worse than unigram Huffman (3.3 bits/char)! It must be a bad model or the test set is unusual. GPT-4-class models achieve ~0.7–0.9 bits per character on standard English, approaching the Shannon limit. A perplexity of 15.3 at the character level is quite high.

~1.4 bits per character is in the range of Shannon's estimate for English (1.0–1.5 bits/char). This means GPT-2 captures most of the statistical structure of English text. Better models (GPT-4) push this even lower, suggesting the true entropy of English may be below 1.0 bits/char.

From 10 KB original to 1.75 KB — a 5.7:1 compression ratio. The progression shows how each level of modeling captures more structure: unigram frequencies → local patterns (gzip) → full linguistic context (LLM). This is why "language modeling is compression" is not just a metaphor — a better language model is literally a better compressor.

Worst → Best compression: ASCII (no compression) → Huffman (unigram model) → gzip (local pattern matching) → LLM (full context model) → Shannon limit (theoretical floor). Each step exploits more structure in the data. The Shannon limit is unreachable but approachable.

javascript
function bitsPerChar(perplexity, charsPerToken) {
  const bitsPerToken = Math.log2(perplexity);
  return bitsPerToken / charsPerToken;
}