Information theory & optimization

1 · Entropy — expected surprise intermediate

Entropy H(p) = −Σ p_i log p_i is the average surprise of a distribution — in bits when the log is base 2. A rare event (small p) carries more surprise (−log p is large); a certain event carries none. Entropy is maximized by the uniform distribution (maximum uncertainty) and zero for a certain outcome. It is the information-theoretic floor: the fewest bits per symbol any code could achieve, and the baseline the loss functions below are measured against.

python# stdlib only
import math

def entropy(p, base=2):
    return -sum(pi * math.log(pi, base) for pi in p if pi > 0)   # 0*log0 := 0

print("fair coin   :", entropy([0.5, 0.5]))          # 1.0 bit
print("biased coin :", round(entropy([0.9, 0.1]), 5))# 0.469 bits (less uncertain)
print("uniform of 4:", entropy([0.25]*4))            # 2.0 bits
print("certain     :", entropy([1.0, 0.0]))          # -0.0 bits (no surprise)

fair coin   : 1.0
biased coin : 0.469
uniform of 4: 2.0
certain     : -0.0

A fair coin needs exactly 1 bit; a 90/10 coin only 0.469 bits (you can usually guess ‘heads’); a uniform 4-way choice needs 2 bits; a certain outcome needs none. Entropy quantifies how much a distribution can surprise you — the reference point for measuring a model against reality next.

2 · Cross-entropy & KL divergence — THE loss advanced

Cross-entropy H(p, q) = −Σ p_i log q_i is the average surprise when reality is p but you encoded for q — your model’s predicted distribution. KL divergence D(p‖q) = Σ p_i log(p_i/q_i) is the extra cost of that mismatch. The identity that matters: H(p, q) = H(p) + D(p‖q). Since H(p) is fixed by the data, minimizing cross-entropy = minimizing KL = making the model’s distribution match reality. When the label is one-hot, cross-entropy collapses to −log q(correct) — the negative log-likelihood that classifiers and LLMs train on.

python# stdlib only
import math

def entropy(p, base=2):        return -sum(pi*math.log(pi, base) for pi in p if pi > 0)
def cross_entropy(p, q, base=2): return -sum(pi*math.log(qi, base) for pi, qi in zip(p, q) if pi > 0)
def kl(p, q, base=2):          return sum(pi*math.log(pi/qi, base) for pi, qi in zip(p, q) if pi > 0)

# One-hot label -> cross-entropy is just -log(prob of correct class):
true = [1, 0, 0]
pred = [0.7, 0.2, 0.1]
print("CE (one-hot, nats):", round(cross_entropy(true, pred, math.e), 5))  # 0.35667
print("-ln(0.7)          :", round(-math.log(0.7), 5))                      # 0.35667

# General case: verify H(p,q) = H(p) + KL(p||q)
p = [0.5, 0.3, 0.2]
q = [0.4, 0.4, 0.2]
print("H(p)      :", round(entropy(p), 5))          # 1.48548
print("H(p,q)    :", round(cross_entropy(p, q), 5)) # 1.52193
print("KL(p||q)  :", round(kl(p, q), 5))            # 0.03645
print("H(p,q)-H(p):", round(cross_entropy(p, q) - entropy(p), 5))  # 0.03645

CE (one-hot, nats): 0.35667
-ln(0.7)          : 0.35667
H(p)      : 1.48548
H(p,q)    : 1.52193
KL(p||q)  : 0.03645
H(p,q)-H(p): 0.03645

With a one-hot label, cross-entropy is exactly −ln(0.7) = 0.357 — the model is penalized purely by the probability it gave the correct class. In the general case H(p,q) − H(p) equals KL(p‖q) = 0.03645 to the digit, confirming the decomposition. This is why the training loss for every classifier and LLM is cross-entropy: minimizing it drives the model’s predictions toward the true distribution (and equals the MLE of A11).

3 · Perplexity — what the LLM number means advanced

Perplexity = exp(average negative log-likelihood) = exp(cross-entropy in nats). It is the cross-entropy loss made interpretable: a perplexity of K means the model is, on average, as uncertain as if it were choosing uniformly among K equally likely tokens. Lower is better. A model that predicts the actual next token with high probability has low perplexity; a clueless uniform model over a vocabulary of size V has perplexity V. It is the standard intrinsic metric for language models.

python# stdlib only
import math

# The probability the model assigned to each ACTUAL next token of a sequence:
token_probs = [0.5, 0.1, 0.25, 0.4]
avg_nll = -sum(math.log(pt) for pt in token_probs) / len(token_probs)
ppl = math.exp(avg_nll)
print("avg NLL (nats):", round(avg_nll, 5))    # 1.32458
print("perplexity    :", round(ppl, 5))         # 3.7606

# Sanity check: a uniform model over vocab V has perplexity V.
V = 100
uniform_probs = [1.0 / V] * 10
ppl_u = math.exp(-sum(math.log(pt) for pt in uniform_probs) / len(uniform_probs))
print("uniform(V=100):", round(ppl_u, 5))       # 100.0

avg NLL (nats): 1.32458
perplexity    : 3.7606
uniform(V=100): 100.0

The model’s effective ‘branching factor’ on this sequence is 3.76 — as uncertain as picking among ~3.76 equally likely tokens each step. The sanity check confirms the meaning: a model that knows nothing beyond a uniform choice over 100 tokens has perplexity exactly 100. When you read ‘this LLM has perplexity 8 on the test set,’ it means an average branching factor of 8 — and it is just exp of the cross-entropy loss from §2.

4 · Mutual information intermediate

Mutual information I(X; Y) = Σ p(x,y) log(p(x,y)/(p(x)p(y))) measures how much knowing one variable reduces uncertainty about the other — it is the KL divergence between the joint and the product of marginals. I = 0 exactly when X and Y are independent. In AI it drives feature selection (keep features informative about the label), diagnostics, and information-theoretic probes of what a representation encodes.

python# stdlib only
import math

# Joint P(X,Y) over {0,1}x{0,1}: X and Y agree 80% of the time.
joint = [[0.4, 0.1],
         [0.1, 0.4]]
px = [sum(row) for row in joint]                       # marginal of X
py = [sum(joint[i][j] for i in range(2)) for j in range(2)]  # marginal of Y

mi = 0.0
for i in range(2):
    for j in range(2):
        if joint[i][j] > 0:
            mi += joint[i][j] * math.log(joint[i][j] / (px[i]*py[j]), 2)
print("marginals:", px, py)         # [0.5, 0.5] [0.5, 0.5]
print("MI (bits):", round(mi, 5))   # 0.27807  (>0 -> dependent)

marginals: [0.5, 0.5] [0.5, 0.5]
MI (bits): 0.27807

Each variable alone is a fair coin (marginals 0.5/0.5), but they agree 80% of the time, so knowing X tells you 0.278 bits about Y — positive mutual information means dependence. Make the joint the product of marginals (0.25 everywhere) and MI drops to 0. This is the quantity a feature selector maximizes to keep inputs that actually inform the label.

5 · Gradient descent from scratch advanced

Training minimizes a loss by gradient descent: repeatedly step the parameters in the direction of the negative gradient (steepest downhill), x ← x − η·∇f(x), where η is the learning rate. The gradient points uphill; negating it descends. The learning rate is the make-or-break knob: too small and it crawls, too large and it overshoots and diverges.

python# stdlib only
def f(x):    return (x - 3)**2
def grad(x): return 2 * (x - 3)          # df/dx, by hand

def descend(lr, steps):
    x = 0.0
    for _ in range(steps):
        x -= lr * grad(x)                # the update rule
    return x

good = descend(lr=0.1, steps=50)
print("lr=0.1 ->", round(good, 6), "f =", round(f(good), 8))   # ~3.0, ~0.0

bad = descend(lr=1.1, steps=20)          # too large: overshoots
print("lr=1.1 ->", round(bad, 3))        # blows up -> -112.013

lr=0.1 -> 2.999957 f = 0.0
lr=1.1 -> -112.013

With η=0.1 the parameter converges to the minimum x=3 (loss ~0). With η=1.1 each step overshoots the minimum by more than it started, so the iterate explodes to −112 and keeps growing — the classic diverging-loss symptom you see as NaN in training when the learning rate is too high. Tuning η (and schedules/warmup) is a core part of getting training to converge (see MS2).

6 · Convexity, SGD vs batch advanced

A function is convex if its graph curves up everywhere (second derivative ≥ 0) — then any local minimum is the global minimum and gradient descent is guaranteed to find it. (x−3)² is convex; deep networks are not, which is why training is an art. Batch GD uses the whole dataset per step (accurate gradient, expensive); stochastic GD (SGD) uses one example (noisy but cheap and can escape shallow traps); mini-batch — a handful at a time — is the practical middle ground every framework uses.

python# stdlib only
# Convex: second derivative constant and positive.
def f(x): return (x - 3)**2
h = 1e-5
def second_deriv(x):
    return (f(x+h) - 2*f(x) + f(x-h)) / h**2
print("f''(x) ~", round(second_deriv(0.0), 3), "-> convex (>0)")   # 2.0

# Linear model loss over 4 points; compare batch grad vs single-sample grad.
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]           # y = 2x + 1
w = b = 0.0
# Batch gradient (averaged over ALL points):
n = len(xs)
gw = sum(2*((w*x+b)-y)*x for x, y in zip(xs, ys)) / n
gb = sum(2*((w*x+b)-y)   for x, y in zip(xs, ys)) / n
print("batch grad (w,b):", round(gw, 3), round(gb, 3))     # -35.0 -12.0
# SGD gradient (ONE random-ish point, here the first):
x0, y0 = xs[0], ys[0]
sgw, sgb = 2*((w*x0+b)-y0)*x0, 2*((w*x0+b)-y0)
print("sgd  grad (w,b):", round(sgw, 3), round(sgb, 3))    # -6.0 -6.0

f''(x) ~ 2.0 -> convex (>0)
batch grad (w,b): -35.0 -12.0
sgd  grad (w,b): -6.0 -6.0

The numeric second derivative is 2 everywhere — positive, so the loss is convex and GD will find the global minimum. The batch gradient averages all four points (−35, −12); the SGD gradient from a single point (−6, −6) is a cheaper, noisier estimate of the same direction. Real training uses mini-batches: enough samples to smooth the noise, few enough to fit in memory and step often (MS1).

7 · The chain rule & backprop — tiny, end-to-end expert expert

Backpropagation is the chain rule applied backwards through a computation to get the gradient of the loss with respect to every parameter. For the loss L = (w·x + b − y)², the chain rule gives ∂L/∂w = 2(pred−y)·x and ∂L/∂b = 2(pred−y). Below we train a 1-feature linear model end-to-end with these hand-derived gradients — deliberately the smallest case so you can see every number, but the exact mechanism (forward pass → loss → gradients → update) that scales to billion-parameter nets (the autograd engine of A4).

python# stdlib only  (deliberately a 1-feature model so every step is visible)
xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]           # target relationship: y = 2x + 1

w, b = 0.0, 0.0
lr = 0.01
for epoch in range(1000):
    dw = db = 0.0
    n = len(xs)
    for x, y in zip(xs, ys):
        pred = w * x + b            # forward pass
        err  = pred - y             # dL/dpred = 2*err (MSE)
        dw += 2 * err * x / n       # chain rule: dL/dw
        db += 2 * err / n           # chain rule: dL/db
    w -= lr * dw                    # gradient-descent update
    b -= lr * db

loss = sum((w*x + b - y)**2 for x, y in zip(xs, ys)) / len(xs)
print("learned w, b:", round(w, 4), round(b, 4))   # ~2.0, ~1.0
print("final MSE   :", round(loss, 6))             # ~0.0

learned w, b: 2.0049 0.9857
final MSE   : 3.4e-05

Starting from w=b=0, 1000 gradient steps recover w≈2.00 and b≈0.99 — the true y = 2x + 1 relationship — driving the MSE to essentially zero. Every step did exactly what an LLM does per batch: run the forward pass, compute the loss, backprop the gradients via the chain rule, and nudge the parameters downhill. Swap the hand-derived gradients for an autograd engine and this scales to the whole network.

Checkpoint expert

import math
def entropy(p):
    return -sum(pi*math.log(pi, 2) for pi in p if pi > 0)

print(entropy([0.5, 0.5]))         # 1.0
print(entropy([0.25]*4))           # 2.0
print(round(entropy([0.9, 0.1]), 4))  # 0.469

1.0
2.0
0.469

import math
def ce(true, pred):
    return -sum(t*math.log(q) for t, q in zip(true, pred) if t > 0)

print(round(ce([1,0,0], [0.7,0.2,0.1]), 5))   # 0.35667  (-ln 0.7)
print(round(ce([1,0,0], [0.4,0.3,0.3]), 5))   # 0.91629  (-ln 0.4, worse)
print(round(-math.log(0.7), 5))               # 0.35667

0.35667
0.91629
0.35667

import math
def perplexity(token_probs):
    nll = -sum(math.log(p) for p in token_probs) / len(token_probs)
    return math.exp(nll)

print(round(perplexity([0.5, 0.1, 0.25, 0.4]), 5))   # 3.7606
V = 50
print(round(perplexity([1/V]*8), 5))                 # 50.0

3.7606
50.0

def grad(x): return 2*(x-3)
def run(lr, steps=60):
    x = 0.0
    for _ in range(steps): x -= lr*grad(x)
    return x

for lr in (0.01, 0.1, 0.9, 1.1):
    print(lr, round(run(lr), 4))

0.01 2.1073
0.1 3.0
0.9 3.0
1.1 -169039.5431

import math
def mi(joint):
    px = [sum(r) for r in joint]
    py = [sum(joint[i][j] for i in range(len(joint))) for j in range(len(joint[0]))]
    tot = 0.0
    for i,row in enumerate(joint):
        for j,pij in enumerate(row):
            if pij > 0: tot += pij*math.log(pij/(px[i]*py[j]), 2)
    return tot

print(round(mi([[0.4,0.1],[0.1,0.4]]), 5))   # 0.27807 (dependent)
print(round(mi([[0.25,0.25],[0.25,0.25]]), 5))  # 0.0 (independent)

0.27807
0.0

xs = [1.0, 2.0, 3.0, 4.0]
ys = [3.0, 5.0, 7.0, 9.0]        # y = 2x + 1
w = b = 0.0
lr = 0.01
for _ in range(2000):
    n = len(xs)
    dw = sum(2*((w*x+b)-y)*x for x,y in zip(xs,ys)) / n
    db = sum(2*((w*x+b)-y)   for x,y in zip(xs,ys)) / n
    w -= lr*dw; b -= lr*db
loss = sum((w*x+b-y)**2 for x,y in zip(xs,ys)) / len(xs)
print(round(w,4), round(b,4), round(loss,8))

2.0002 0.9993 8e-08