Fitting a grammar is minimizing surprise

What does it mean to "fit" a grammar to data? The tempting answer is: make what the model predicts look like what we saw. But there's a cleaner way to say the same thing — leave the model as little surprised as possible by the data. And "surprise" here isn't a figure of speech: it's how improbable the data is under the model, the old $-\log p$. A well-fitted model is one that finds the data unremarkable, expected, unsurprising.

Add that surprise up over all the data, each point weighted by how often it occurred, and you get the cross-entropy — the average surprise the model feels at the data. Fitting is nothing more than pushing that number down.

Except there's a floor. The data have their own unpredictability — their entropy. No one can be less surprised than that; the best you can do is stop being surprised by what the model gets wrong on its own. That extra surprise, above the floor, is the Kullback-Leibler divergence — how crooked the model sits relative to the data. Shrink the KL and the cross-entropy sinks to the floor.

Drag the $\lambda$ and bend the curve onto the histogram, watching the KL plummet; or let the descent take care of it:

That, underneath, is how a maximum-entropy grammar learns: a little push on the weights to reduce the gap between what it predicts and what it saw, again and again, until the gap is small. Minimising the divergence and maximising the likelihood are, in fact, the same move (Goldwater & Johnson, 2003; Hayes & Wilson, 2008). The "right" weights are just the ones that make the observed candidates as likely as they can be. With the weight at zero the model knows nothing and splits things evenly — far from the frequencies the data show (0.54, 0.30, 0.16):

Fitting the weight is exactly pushing the model's probability until it meets what was observed:

Worth checking the sum instead of taking my word for it. For a few values of $\lambda$, notice how the KL falls and the cross-entropy approaches the floor, never quite piercing it:

import math
# A data histogram and a maximum-entropy model. Fitting = shrinking the KL
# between the two (the same thing as maximizing the likelihood).
data = [0.04, 0.09, 0.16, 0.21, 0.21, 0.16, 0.09, 0.04]
c = [((325 + 50 * i) - 300) / 400 for i in range(8)]     # normalized centres
def model(l1, l2):
    w = [math.exp(-(l1 * ci + l2 * ci * ci)) for ci in c]
    Z = sum(w)
    return [wi / Z for wi in w]
def kl(p, q):        # in bits
    return sum(pi * math.log2(pi / qi) for pi, qi in zip(p, q) if pi > 0)

floor = -sum(pi * math.log2(pi) for pi in data if pi > 0)
print(f"floor H(data) = {floor:.3f} bits")
for (l1, l2) in [(0.0, 0.0), (-2.0, 2.0), (-4.3, 4.4)]:
    q = model(l1, l2)
    d = kl(data, q)
    print(f"lambda=({l1:>4},{l2:>3})  KL={d:.4f}  cross-entropy={floor + d:.3f} bits")

In the end, learning isn't hitting some Platonic truth. It's a humble negotiation: be as unsurprised as the data will let you, and accept the surprise you can't remove. The KL reaches zero only if your model already is the truth — which, with real data, it almost never is.

@misc{barroso2024fittingisminimizingsurprise,
  author       = {Alexandre Menezes Barroso},
  title        = {Fitting a grammar is minimizing surprise},
  year         = {2024},
  howpublished = {alexandrebarroso.com},
  url          = {https://alexandrebarroso.com/notes/fitting-is-minimizing-surprise.html},
  note         = {alexandrebarroso.com}
}