NEURONS ALL THE WAY DOWN · CHAPTER 01

What is a Language Model?
Counting, n-grams & perplexity

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.

~18 min read1 interactiveTested Python

What you'll learn

  • How the chain rule turns “probability of a sentence” into next-word prediction
  • How an n-gram model estimates those conditionals by counting
  • Why unseen phrases get probability 0, and how add-k smoothing fixes that
  • How to read negative log-likelihood and perplexity as a branching factor

Before you start

  • Conditional probability, \(P(A \mid B)\)
  • Natural log and exp — the rest of the series uses them constantly
  • No neural nets yet. Those start in chapter 03.

The night clerk’s log

Picture the night clerk at a small harbor. Five times this week they wrote a weather line in the log:

LineText
1fog on the bay
2fog on the pier
3rain on the bay
4rain on the pier
5sun 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.

A sentence is a product of next-word bets

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

MANIM Five next-word bets multiply into one sentence score. Use the beat buttons to jump.

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.

Pretend only the last few words matter

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.

Unigram

Ignore context. \(P(w)\) is the word’s frequency. “Bay” and “on” are just two common words. Order is gone.

Bigram

One word of memory. After “the”, prefer “bay”. After “fog”, always “on”. This is the model we build below.

Trigram

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.

Twenty-five bigrams, one page of arithmetic

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\).

ContextNextCountMLE
<s>fog22/5 = 0.4
<s>rain22/5 = 0.4
<s>sun11/5 = 0.2
fog / rain / sunon2, 2, 11.0
onthe51.0
thebay33/5 = 0.6
thepier22/5 = 0.4
bay / pier</s>3, 21.0
Every other pair has count 0. After “the”, the model has never seen “sun”.

Now score a sentence the clerk never wrote as a whole line: sun on the pier.

  1. \(P(\text{sun} \mid \langle s \rangle) = 0.2\)
  2. \(P(\text{on} \mid \text{sun}) = 1\)
  3. \(P(\text{the} \mid \text{on}) = 1\)
  4. \(P(\text{pier} \mid \text{the}) = 0.4\)
  5. \(P(\langle /s \rangle \mid \text{pier}) = 1\)

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 code

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.

ngrams.pyheld-out joint 0.08, add-1 rows sum to 1
"""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\).
  • The sampler is a roulette wheel: draw \(r \in [0,1]\), walk the row until the cumulative mass covers \(r\).

One unseen pair sinks the sentence

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

MANIM One unseen cell zeros the joint; add-1 resurrects it soft. Use the beat buttons to jump.

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.

How many guesses does the model need?

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.”

ModelSentenceJoint PNLLPerplexity
MLE bigramfog on the bay (train)0.240.2851.33
MLE bigramsun on the pier (held-out)0.080.5051.66
Add-1 bigramsun on the pier0.00111.3643.91
MLE bigramfog on the sun0∞∞
Uniformany sentence of length N(1/8)^N2.088

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.

Mistakes learners make

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.

What to remember

  • A language model is \(P(\text{text})\). The chain rule turns that into next-token prediction.
  • An n-gram estimates each conditional by counting a short context and dividing.
  • Unseen n-grams get MLE probability 0. Add-k smoothing spends some sharpness to remove the zeros.
  • Average NLL is the usual loss. Perplexity \(= \exp(\mathrm{NLL})\) is that loss as a branching factor.

Check yourself

1. Why does scoring a sentence need an end token?

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.

2. On the harbor log, what is \(P(\text{bay} \mid \text{the})\) under MLE? Under add-1?

MLE: \(3/5 = 0.6\). Add-1: \((3+1)/(5+8) = 4/13\).

3. The held-out joint is 0.08 over 5 tokens. What is the perplexity?

\(0.08^{-1/5} \approx 1.66\). Equivalently \(\exp(-\ln 0.08 / 5)\).

4. A uniform model over 8 next-tokens has what NLL and what perplexity?

NLL \(= \ln 8 \approx 2.08\). Perplexity \(= 8\).

5. Why will counting fail as the context grows?

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.

Go to the source

Keep going