Language models and smoothing

Intermediate

Introduction

Your phone suggesting the next word, a speech recognizer choosing between "recognize speech" and "wreck a nice beach", and a chatbot writing an answer all rely on a language model: a model that knows which word sequences are likely. Large language models are neural networks trained for exactly this job. This lesson builds the original kind, the n-gram model, from counts. It teaches the ideas that still apply to every language model: conditional probabilities, the problem of unseen events, smoothing, evaluation with perplexity, and generation.

How it works

By the chain rule of probability, the probability of a sentence is a product of conditional probabilities:

P(w₁ … wₙ) = P(w₁) × P(w₂ given w₁) × P(w₃ given w₁ w₂) × …

Long histories are too rare to count, so an n-gram model makes the Markov assumption: each word depends only on the previous n − 1 words. In a bigram model, P(wᵢ given everything before) ≈ P(wᵢ given wᵢ₋₁).

Each sentence is padded with a start marker <s> and an end marker </s>, so the model also learns which words start and end sentences. The maximum likelihood estimate is a relative frequency:

P(w given prev) = count(prev w) ÷ count(prev)

The trouble: any pair that never occurred in training gets probability 0, so a perfectly good new sentence gets probability 0. Add-one smoothing adds 1 to every bigram count:

P(w given prev) = (count(prev w) + 1) ÷ (count(prev) + V)

where V is the number of word types that can follow (all words plus </s>). Add-k uses a smaller k such as 0.1, which takes less probability away from seen pairs. Better methods, such as backoff, interpolation and Kneser-Ney smoothing, combine bigram, unigram and other estimates.

To compare models, compute the perplexity of held-out text: PP = exp(−(1/N) Σ ln P(wᵢ given wᵢ₋₁)), where N counts the predicted tokens (including </s>). A perplexity of 4 means the model is as unsure as if it chose uniformly among 4 words at each step. Lower is better, but only on the same test text with the same vocabulary.

To generate text, start at <s> and repeatedly pick a next word: the most likely one (greedy), or a random one drawn from the probabilities.

Example

import math

corpus = ["i like green tea", "i like black tea", "you like green apples"]
unigrams, bigrams = {}, {}
for line in corpus:
    words = ["<s>"] + line.split() + ["</s>"]
    for i, w in enumerate(words):
        unigrams[w] = unigrams.get(w, 0) + 1
        if i > 0:
            pair = (words[i - 1], w)
            bigrams[pair] = bigrams.get(pair, 0) + 1
V = len(unigrams) - 1
print("vocabulary (without <s>):", V)


def p_mle(prev, w):
    return bigrams.get((prev, w), 0) / unigrams[prev]


def p_add1(prev, w):
    return (bigrams.get((prev, w), 0) + 1) / (unigrams[prev] + V)


for sentence in ["you like green tea", "i like tea"]:
    words = ["<s>"] + sentence.split() + ["</s>"]
    mle, add1, log_sum = 1.0, 1.0, 0.0
    for prev, w in zip(words, words[1:]):
        mle *= p_mle(prev, w)
        p = p_add1(prev, w)
        add1 *= p
        log_sum += round(math.log(p), 12)
    perplexity = round(math.exp(-log_sum / (len(words) - 1)), 12)
    print(f"{sentence!r}: MLE {mle:.4f}, add-one {add1:.6f}, perplexity {perplexity:.2f}")

word, generated = "<s>", []
while True:
    options = [(c, w) for (p, w), c in bigrams.items() if p == word]
    word = max(options)[1]
    if word == "</s>":
        break
    generated.append(word)
print("greedy:", " ".join(generated))
Open in compiler

Line by line

  1. Every sentence gets <s> and </s>; the loop counts single words and neighbouring pairs.
  2. V is 8: the 9 counted types minus <s>, which never follows anything.
  3. "you like green tea" only uses seen pairs, so its MLE probability is 1/3 × 1 × 2/3 × 1/2 × 1 = 1/9 ≈ 0.1111 ("green" is followed by "tea" only half the time).
  4. "i like tea" contains the unseen pair "like tea", so MLE gives exactly 0. Add-one gives it a small probability, 27/12100.
  5. Perplexity is computed from the summed log probabilities; logs and the result are rounded to 12 places so every computer prints the same digits.
  6. Greedy generation always takes the most frequent next word: from <s> to "i", "like", "green" and "tea", where the end marker is most likely.

Expected result

vocabulary (without <s>): 8
'you like green tea': MLE 0.1111, add-one 0.000661, perplexity 4.32
'i like tea': MLE 0.0000, add-one 0.002231, perplexity 4.60
greedy: i like green tea

In the real world

N-gram models powered speech recognition, machine translation and keyboard prediction for decades; tools such as KenLM still train them on billions of words. Neural language models replaced them because they share information between similar words and look at much longer contexts, but they are trained with the same goal (predict the next token) and evaluated with the same perplexity. NLTK has n-gram models with smoothing (shown, not run here):

from nltk.lm import Laplace
from nltk.lm.preprocessing import padded_everygram_pipeline

sentences = [["i", "like", "green", "tea"], ["i", "like", "black", "tea"]]
train, vocab = padded_everygram_pipeline(2, sentences)
lm = Laplace(2)
lm.fit(train, vocab)
print(lm.score("tea", ["green"]))

Its vocabulary also counts the markers and an unknown-word token, so its numbers differ slightly from a hand-built model.

Common mistakes

  • Forgetting the sentence markers, so the model cannot tell which words start or end sentences.
  • Using add-one smoothing on a big vocabulary, which steals far too much probability from seen pairs; use add-k or better methods.
  • Comparing perplexities on different test sets or vocabularies.
  • Multiplying probabilities instead of adding logs, which underflows for long texts.

Best practices

  • Hold out test sentences that the model never sees in training.
  • Tune k (or other smoothing settings) on a separate validation set.
  • Map rare words to an unknown-word token so new words are handled consistently.
  • Generate a few sentences: they show at a glance what the model has learned.

Summary

A language model assigns probabilities to word sequences. An n-gram model uses the chain rule with the Markov assumption, estimating each conditional probability from counts with sentence markers. Unseen n-grams get probability zero unless the counts are smoothed with add-one, add-k or better methods. Perplexity measures how well a model predicts held-out text, and the same counts can generate new text.

Quick check

1. What does a bigram model assume?
2. Why does the maximum-likelihood estimate fail on new sentences?
3. Model A has perplexity 50 and model B 120 on the same test text. Which predicts it better?
4. With add-one smoothing, what is P(w given prev) when count(prev w) = 0, count(prev) = 3 and V = 7?

Key takeaways

  • An n-gram language model multiplies conditional probabilities of each word given the previous n − 1 words.
  • Maximum-likelihood estimates give unseen n-grams probability zero; smoothing moves some probability to them.
  • Perplexity compares models on held-out text: it is the effective number of choices per word.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.