NEURONS ALL THE WAY DOWN · CHAPTER 01
A language model is a distribution over strings. Count the phrases you have seen, divide, and you already have one. Perplexity tells you how surprised it is.
Picture the night clerk at a small harbor. Five times this week they wrote a weather line in the log:
| Line | Text |
|---|---|
| 1 | fog on the bay |
| 2 | fog on the pier |
| 3 | rain on the bay |
| 4 | rain on the pier |
| 5 | sun on the bay |
A visitor starts a new line: “sun on the …” The clerk does not know the future. They do know the past. After “the”, the log said bay three times and pier twice. So they guess bay with probability 3/5, and pier with 2/5.
That guess is a language model. Not a large one. Not a neural one. Just a table of “what tends to follow what.” Everything later in this series is a better way to fill in that table.
A language model assigns a number between 0 and 1 to every string, and those numbers sum to 1. Next-word prediction is the same object, sliced by the chain rule. If you can score the next word, you can score a whole sentence. If you can score a sentence, you can sample one.
Write a sentence as a sequence of tokens \(w_1, w_2, \dots, w_n\). The model’s job is \(P(w_1, \dots, w_n)\). The chain rule of probability — not the chain rule of calculus, that is the next chapter — splits the joint into conditionals:
the chance of the whole string is the chance of the first word, times the chance of the second given the first, times the chance of the third given the first two, and so on.
Each factor is a next-word distribution. The prefix \(w_1,\dots,w_{i-1}\) is the context. The model looks at the context and puts a probability on every word in a fixed vocabulary, including a special end-of-sentence token so the product knows when to stop.
We write \(\langle s \rangle\) for the start marker and \(\langle /s \rangle\) for the end. The start marker is a context only. The model never predicts it. The end marker is a regular next-token. Scoring “sun on the pier” means scoring five bets:
four content words plus the decision to stop. Five factors, five chances to be right or wrong.
P(sentence) = 0.2 · 1 · 1 · 0.4 · 1 = 0.08
Every language model in this series estimates the same chain rule. They differ only in how they compute \(P(w_i \mid \text{context})\). Counting is the first method. Neural nets and transformers are later methods.
The true conditional \(P(w_i \mid w_1,\dots,w_{i-1})\) looks at the entire prefix. That table does not fit in memory. The n-gram assumption (a Markov assumption) says: only the last \(n-1\) words count.
a bigram (n = 2) uses one word of context. A trigram uses two. A 5-gram uses four.
Then estimate each short conditional by counting and dividing. That is maximum likelihood:
of all the times you saw context c, what fraction continued with w?
Larger \(n\) remembers more. It also sees each exact context fewer times, so more of the table is zero. That is the fidelity-versus-data trade-off. The harbor log is so small that a trigram and a bigram almost agree. On real text they do not.
Ignore context. \(P(w)\) is the word’s frequency. “Bay” and “on” are just two common words. Order is gone.
One word of memory. After “the”, prefer “bay”. After “fog”, always “on”. This is the model we build below.
Two words of memory. “on the bay” (3 times) vs “on the pier” (2 times). Same numbers as the bigram on this tiny log, by accident.
Each of the five lines is four words plus two boundary markers, so each line gives five bigrams. The whole log is 25 pairs. The next-token vocabulary is the seven content words plus \(\langle /s \rangle\), so \(V = 8\).
| Context | Next | Count | MLE |
|---|---|---|---|
| <s> | fog | 2 | 2/5 = 0.4 |
| <s> | rain | 2 | 2/5 = 0.4 |
| <s> | sun | 1 | 1/5 = 0.2 |
| fog / rain / sun | on | 2, 2, 1 | 1.0 |
| on | the | 5 | 1.0 |
| the | bay | 3 | 3/5 = 0.6 |
| the | pier | 2 | 2/5 = 0.4 |
| bay / pier | </s> | 3, 2 | 1.0 |
Now score a sentence the clerk never wrote as a whole line: sun on the pier.
The joint is \(0.2 \times 1 \times 1 \times 0.4 \times 1 = \mathbf{0.08}\). The model likes this sentence: every step but two is certain, and the uncertain steps are common ones.
The same table, as a few functions. Count pairs, divide for MLE, add \(k\) fake counts to every cell for smoothing. Perplexity is exp of the mean negative log probability.
"""Count-based language model on a tiny harbor-log corpus.
A language model is a distribution over strings. The cheapest way to
build one is to count how often each short phrase appears, then divide.
This file is the worked example from the chapter: five log lines, a
bigram table, Laplace smoothing, and perplexity.
The vocabulary of *next* tokens is the seven content words plus </s>.
<s> is only a context. It is never predicted.
"""
from collections import Counter
import math
# Five lines from a made-up harbor log. Short, repeating, no surprises.
# That is on purpose: every probability on the page can be done by hand.
CORPUS = [
"fog on the bay",
"fog on the pier",
"rain on the bay",
"rain on the pier",
"sun on the bay",
]
BOS = "<s>"
EOS = "</s>"
# Tokens a model is allowed to emit. <s> is missing on purpose.
VOCAB = ["fog", "rain", "sun", "on", "the", "bay", "pier", EOS]
V = len(VOCAB) # 8. The uniform model's branching factor.
def tokenize(line):
"""Wrap one line with boundary markers so every sentence has a start and an end."""
return [BOS] + line.split() + [EOS]
def bigram_counts(lines=CORPUS):
"""Count every adjacent pair (context, next) in the corpus."""
counts = Counter()
for line in lines:
tokens = tokenize(line)
# zip(tokens, tokens[1:]) walks (w0, w1), (w1, w2), ...
for ctx, nxt in zip(tokens, tokens[1:]):
counts[(ctx, nxt)] += 1
return counts
def row_sum(counts, ctx):
"""How many times `ctx` appeared as a context, i.e. the denominator of MLE."""
return sum(n for (c, _), n in counts.items() if c == ctx)
def mle(counts, ctx, nxt):
"""Maximum-likelihood P(next | context) = count / row sum. Zero if unseen."""
denom = row_sum(counts, ctx)
if denom == 0:
return 0.0
return counts[(ctx, nxt)] / denom
def add_k(counts, ctx, nxt, k=1.0):
"""Laplace / add-k smoothing. Every next-token gets k fake counts.
The denominator grows by k * V so the row still sums to 1.
An unseen pair gets probability k / (row_sum + k * V), never zero.
"""
denom = row_sum(counts, ctx) + k * V
return (counts[(ctx, nxt)] + k) / denom
def sequence_logprob(words, counts, smoother=mle):
"""Sum of log P(w_i | w_{i-1}) for one sentence, including the EOS.
`words` is the content only, e.g. ['sun', 'on', 'the', 'pier'].
Returns (total log-prob, list of per-step probabilities).
"""
tokens = [BOS] + list(words) + [EOS]
logp = 0.0
steps = []
for ctx, nxt in zip(tokens, tokens[1:]):
p = smoother(counts, ctx, nxt)
steps.append(p)
# math.log(0.0) is -inf. That is the unsmoothed "unseen bigram" failure.
logp += math.log(p) if p > 0.0 else float("-inf")
return logp, steps
def avg_nll(words, counts, smoother=mle):
"""Mean negative log-likelihood, one term per predicted token (incl. EOS)."""
logp, steps = sequence_logprob(words, counts, smoother)
return -logp / len(steps)
def perplexity(words, counts, smoother=mle):
"""exp(average NLL). Read it as a branching factor: 'how many guesses'.
A model that always puts probability 1/k on the true next token has
perplexity k. Uniform over V tokens has perplexity V.
"""
return math.exp(avg_nll(words, counts, smoother))
def sample(counts, smoother=mle, seed=0, max_len=12):
"""Draw one sentence by walking the roulette wheel of each row."""
# A tiny linear-congruential generator so the file has no extra imports.
state = seed & 0xFFFFFFFF
def rng():
nonlocal state
state = (1664525 * state + 1013904223) & 0xFFFFFFFF
return state / 0x100000000
tokens = [BOS]
while tokens[-1] != EOS and len(tokens) < max_len:
ctx = tokens[-1]
# Build the roulette wheel: cumulative probabilities over VOCAB.
r = rng()
acc = 0.0
chosen = EOS
for w in VOCAB:
acc += smoother(counts, ctx, w)
if r <= acc:
chosen = w
break
tokens.append(chosen)
return tokens
# --- Numbers used on the page. The check script imports these. ---
COUNTS = bigram_counts()
HELD_OUT = ["sun", "on", "the", "pier"] # never written as a whole line
ZERO_LINE = ["fog", "on", "the", "sun"] # "sun" never follows "the"
TRAIN_LINE = ["fog", "on", "the", "bay"] # a line the model has seen
# MLE path for the held-out sentence: 0.2 × 1 × 1 × 0.4 × 1 = 0.08
HELD_OUT_STEPS = sequence_logprob(HELD_OUT, COUNTS, mle)[1]
HELD_OUT_P = math.exp(sequence_logprob(HELD_OUT, COUNTS, mle)[0])
HELD_OUT_NLL = avg_nll(HELD_OUT, COUNTS, mle)
HELD_OUT_PPL = perplexity(HELD_OUT, COUNTS, mle)
# Same sentence after add-1. No zero, but every step is a little softer.
HELD_OUT_ADD1_STEPS = sequence_logprob(HELD_OUT, COUNTS, add_k)[1]
HELD_OUT_ADD1_PPL = perplexity(HELD_OUT, COUNTS, add_k)
# Unseen bigram. MLE is exactly 0; add-1 is 1 / (5 + 8) = 1/13.
P_SUN_GIVEN_THE_MLE = mle(COUNTS, "the", "sun")
P_SUN_GIVEN_THE_ADD1 = add_k(COUNTS, "the", "sun")
# A model that knows nothing assigns 1/V to every next token.
UNIFORM_NLL = math.log(V)
UNIFORM_PPL = float(V)
# Trigram count used on the page: "on the bay" vs "on the pier".
TRIGRAM_ON_THE_BAY = 3
TRIGRAM_ON_THE_PIER = 2
TRIGRAM_ON_THE = 5
V = 8 — the uniform model’s branching factor, and the extra mass add-1 spreads over.math.log(0.0) — an unseen bigram makes the whole sentence’s log-prob \(-\infty\).Try “fog on the sun”. The prefix is fine. Then the model needs \(P(\text{sun} \mid \text{the})\). That count is 0, so the joint is 0, and the log-probability is \(-\infty\). A clerk who has never written that line should be surprised, not infinitely certain it is impossible.
Add-k (Laplace) smoothing pretends you saw every next-token \(k\) extra times:
add k to every cell of the row, and add kV to the denominator so the row still sums to 1.
With \(k = 1\) and \(V = 8\), the killer cell becomes \(P(\text{sun} \mid \text{the}) = 1 / (5 + 8) = \mathbf{1/13}\). The held-out sentence “sun on the pier” is no longer 0.08. Its five add-1 factors are \(2/13\), \(2/9\), \(6/13\), \(3/13\), \(3/10\), and its perplexity rises from 1.66 to 3.91. You paid some sharpness for the right to score anything.
P(sun|the)=0 → joint = 0 → 1/13 → PPL 1.66→3.91
Add-1 is the first smoothing method, not the best one. Interpolation and Kneser–Ney keep more of the sharp mass on frequent phrases. The move that actually scales is to stop storing a table and start learning a function. That is the next neural chapter.
Products of probabilities underflow. We always work in logs. The usual training loss of a language model is the average negative log-likelihood (NLL), also called cross-entropy when the target is a one-hot word:
add up how wrong each next-word bet was, then divide by the number of bets. Lower is better.
For “sun on the pier”, \(N = 5\) and the joint is 0.08, so \(\mathrm{NLL} = -\ln 0.08 / 5 \approx 0.505\). A model that knows nothing puts \(1/8\) on every token, so its NLL is \(\ln 8 \approx \mathbf{2.08}\).
Perplexity is that loss, exponentiated:
if the model were always choosing among k equally likely next tokens and the truth was one of them, k is the perplexity.
So the held-out harbor sentence has perplexity \(0.08^{-1/5} \approx \mathbf{1.66}\). The uniform model has perplexity 8, equal to \(V\). Read 1.66 as: “the clerk needs about one-and-two-thirds guesses per word.” Read 8 as: “a clerk who has never opened the log.”
| Model | Sentence | Joint P | NLL | Perplexity |
|---|---|---|---|---|
| MLE bigram | fog on the bay (train) | 0.24 | 0.285 | 1.33 |
| MLE bigram | sun on the pier (held-out) | 0.08 | 0.505 | 1.66 |
| Add-1 bigram | sun on the pier | 0.0011 | 1.364 | 3.91 |
| MLE bigram | fog on the sun | 0 | ∞ | ∞ |
| Uniform | any sentence of length N | (1/8)^N | 2.08 | 8 |
Interactive · Harbor-log bigrams
After a given word, where does the clerk put the probability?
Perplexity is not a quality score for generated text. A model can have a low perplexity and still write dull sentences, and the other way around. It is a clean number for comparing models that share a tokenizer, on the same held-out set.
Forgetting the end token. The product needs a factor for “stop here.” Drop \(\langle /s \rangle\) and you are scoring a prefix, not a sentence. Lengths then cannot be compared.
Comparing perplexities across tokenizers. A character model and a word model are not guessing from the same set. Their perplexities live on different scales. Compare average NLL per byte or per character if you must.
Treating a zero as “the model is sure.” MLE zeros are missing data, not knowledge. One unseen pair should not send the loss to infinity. Smooth, or move to a neural model that shares strength across similar contexts.
Growing n and expecting a free lunch. A 5-gram on this log is almost all zeros. Larger n is only a win when you have enough counts, or a back-off / interpolation scheme to fall back on.
Without \(\langle /s \rangle\) you are scoring a prefix. Two sentences of different lengths would not be comparable, and a sampler would not know when to stop.
MLE: \(3/5 = 0.6\). Add-1: \((3+1)/(5+8) = 4/13\).
\(0.08^{-1/5} \approx 1.66\). Equivalently \(\exp(-\ln 0.08 / 5)\).
NLL \(= \ln 8 \approx 2.08\). Perplexity \(= 8\).
The table has one cell per possible n-gram. That is \(V^{n}\) cells. Almost all of them stay empty, so MLE is dominated by zeros. A neural model shares parameters across contexts instead of storing a cell for each one.