n-gram language models

Before neural language models there were n-grams: guess the next word from the n−1 preceding ones, by counting how often the combination has occurred in a body of text.

P(word | the preceding ones) = count(the preceding ones + the word) / count(the preceding ones)

With a bigram model (n = 2) you only count word pairs. «the cat sleeps» occurred 12 times, «the cat» 300 times → P(sleeps | the cat) = 0.04.

The problem: sparsity. With a vocabulary of 50 000 words there are 2.5 billion possible bigrams and 10¹⁴ trigrams. The vast majority you have never seen — and then the probability becomes zero, which makes the whole sentence impossible. You smooth by adding a small probability everywhere, but the underlying problem remains.

from collections import defaultdict, Counter
import math, random

def build_bigram(tokens):
    model = defaultdict(Counter)
    for a, b in zip(tokens, tokens[1:]):
        model[a][b] += 1
    return model

def probability(model, a, b, vocab, alpha=1.0):       # add-alpha smoothing
    return (model[a][b] + alpha) / (sum(model[a].values()) + alpha * len(vocab))

def perplexity(model, tokens, vocab):
    logs = [math.log(probability(model, a, b, vocab)) for a, b in zip(tokens, tokens[1:])]
    return math.exp(-sum(logs) / len(logs))

def generate(model, start, n=12):
    out = [start]
    for _ in range(n):
        choices = model[out[-1]]
        if not choices: break
        out.append(random.choices(list(choices), weights=choices.values())[0])
    return " ".join(out)

What n-grams cannot do: «The man who lived in the house by the lake was» — to choose «was» you need «man», seven words away. A 3-gram model only sees «by the lake». Simply increasing n does not help: the data is never enough.

That is precisely the problem neural models solved — first with embeddings (similar words share statistics), then with attention (an arbitrarily long dependency).