N-Gram Language Models

Long before neural networks, people built language models with nothing but counting. In nineteen forty eight, Claude Shannon asked a beautiful question. If you know the last word, what's your best guess for the next? That idea is the direct ancestor of every chatbot today.

• 1948: Claude Shannon
• Guess the next word
• The ancestor of every chatbot

A language model from counting

We count which word follows which. That gives us a table of chances, for the next word after each word. It's called a bigram model. Then we generate. Pick a word, roll weighted dice for the next, and repeat. Run it. Look at the chances after the word the. Then the generated text, which looks strangely like language. There's no neural network here. Just counting. And yet this has the same shape as GPT. Predict the next token, sample, and repeat.

text = ("the cat sat on the mat . the dog sat on the log . the cat saw the dog . "
        "the dog saw the cat . a cat and a dog sat on a mat . ") * 20
words = text.split()

from collections import Counter, defaultdict
import random

pairs = defaultdict(Counter)
for a, b in zip(words, words[1:]):
    pairs[a][b] += 1

total = sum(pairs["the"].values())
for w, n in pairs["the"].most_common(4):
    print(f"P({w} | the) = {n / total:.2f}")

random.seed(1)
w, out = "the", ["the"]
for _ in range(14):
    w = random.choices(list(pairs[w]), weights=pairs[w].values())[0]
    out.append(w)
print(" ".join(out))

P(cat | the) = 0.38
P(dog | the) = 0.38
P(mat | the) = 0.12
P(log | the) = 0.12
the cat and a cat saw the dog saw the cat and a mat .

Scoring a sentence

A language model can also judge how natural a sentence is. We use perplexity, which is roughly how surprised the model is by each word. Lower is better. We test a normal sentence, one with the words swapped, and one that's shuffled. Run it. The normal one has the lowest score, and the shuffled one is far worse. That's how speech recognition chooses between words that sound alike. And it's the standard way of measuring language models today.

text = ("the cat sat on the mat . the dog sat on the log . the cat saw the dog . "
        "the dog saw the cat . a cat and a dog sat on a mat . ") * 20
words = text.split()

import math
from collections import Counter

uni = Counter(words)
bi = Counter(zip(words, words[1:]))
V = len(uni)

def score(sentence, k):
    toks = sentence.split()
    logp = sum(math.log((bi[(a, b)] + k) / (uni[a] + k * V)) for a, b in zip(toks, toks[1:]))
    return math.exp(-logp / (len(toks) - 1))

for s in ["the cat sat on the mat", "the mat sat on the cat", "mat the on sat cat the"]:
    print(f"{score(s, 1):8.2f}  {s}")

    2.88  the cat sat on the mat
    4.72  the mat sat on the cat
   83.26  mat the on sat cat the

Handling what you have never seen

Here's a big problem. If a word pair never appeared in training, its chance is zero, and one zero makes the whole sentence impossible. The classic fix is smoothing. Pretend that everything was seen a little. Add a small count to every pair. Run it. Zero becomes a small number. It's a simple idea, and it teaches something very deep. Your training data can never contain everything.

text = ("the cat sat on the mat . the dog sat on the log . the cat saw the dog . "
        "the dog saw the cat . a cat and a dog sat on a mat . ") * 20
words = text.split()

from collections import Counter

uni = Counter(words)
bi = Counter(zip(words, words[1:]))
V = len(uni)

for k in [0, 1]:
    p = (bi[("dog", "mat")] + k) / (uni["dog"] + k * V)
    print(f"k = {k}: P(mat | dog) = {p:.4f}")

k = 0: P(mat | dog) = 0.0000
k = 1: P(mat | dog) = 0.0110

Summary