N-Grams and Language Models: Predicting the Next Word with Counting

Terminology

What & Why

Before neural networks took over NLP, the dominant approach to language modeling was counting. You observe a large corpus of text, count how often word sequences appear, and use those counts to estimate the probability of the next word. A bigram model asks: given the previous word, what comes next? A trigram model looks at the previous two words.

This works because of the Markov assumption: the probability of a word depends only on a small, fixed window of preceding words. The assumption is wrong (language has long-range dependencies), but it is useful enough to power spell checkers, speech recognition, and machine translation for decades.

The core challenge is sparsity. Most possible n-grams never appear in any training corpus. If you have never seen "the walrus danced," your model assigns it probability zero, which breaks everything. Smoothing techniques redistribute probability mass from observed n-grams to unseen ones, and the choice of smoothing method has a dramatic effect on model quality.

How It Works

The Chain Rule and Markov Simplification

The probability of a sentence w_1, w_2, \ldots, w_n is:

The Markov assumption truncates the conditioning context. For a bigram model:

For a trigram model:

Counting and MLE

Bigram probabilities are estimated by counting:

If "the cat" appears 100 times and "the" appears 5000 times, then P(\text{cat} | \text{the}) = 100/5000 = 0.02.

Smoothing Techniques

Laplace (Add-One): Add 1 to every count. Simple but distorts the distribution heavily, stealing too much mass from frequent n-grams.

Add-k Smoothing: Add a fractional k < 1 instead of 1. Less aggressive but k must be tuned.

Kneser-Ney Smoothing: The gold standard for n-gram models. It subtracts a fixed discount d from each observed count and distributes the freed mass proportionally to a continuation probability: how many distinct contexts a word appears in. The word "Francisco" has high unigram frequency but almost always follows "San," so its continuation probability is low. Kneser-Ney captures this.

Complexity Analysis

The storage bottleneck is the n-gram table. For a trigram model with vocabulary $V = 50{,}000$, the theoretical maximum number of trigrams is $V^3 = 1.25 \times 10^{14}$. In practice, most trigrams never occur, so sparse storage (hash maps) reduces this dramatically.

Perplexity is computed as:

Implementation

ALGORITHM TrainBigramModel(corpus)
INPUT: corpus: list of sentences (each a list of tokens)
OUTPUT: bigramProb: map of (context, word) -> probability

BEGIN
  unigramCount <- empty map
  bigramCount <- empty map
  V <- 0  // vocabulary size

  FOR EACH sentence IN corpus DO
    tokens <- ["<s>"] + sentence + ["</s>"]
    FOR i FROM 0 TO LENGTH(tokens) - 1 DO
      unigramCount[tokens[i]] <- unigramCount[tokens[i]] + 1
      IF i > 0 THEN
        pair <- (tokens[i-1], tokens[i])
        bigramCount[pair] <- bigramCount[pair] + 1
      END IF
    END FOR
  END FOR

  V <- NUMBER OF DISTINCT KEYS IN unigramCount

  bigramProb <- empty map
  FOR EACH ((ctx, word), count) IN bigramCount DO
    bigramProb[(ctx, word)] <- count / unigramCount[ctx]
  END FOR

  RETURN bigramProb, unigramCount, V
END

ALGORITHM ComputePerplexity(testCorpus, bigramProb, unigramCount, V)
INPUT: testCorpus: list of sentences, bigramProb: map, unigramCount: map, V: integer
OUTPUT: perplexity: float

BEGIN
  logSum <- 0
  tokenCount <- 0

  FOR EACH sentence IN testCorpus DO
    tokens <- ["<s>"] + sentence + ["</s>"]
    FOR i FROM 1 TO LENGTH(tokens) - 1 DO
      pair <- (tokens[i-1], tokens[i])
      IF pair IN bigramProb THEN
        p <- bigramProb[pair]
      ELSE
        // Laplace smoothing fallback
        p <- 1 / (unigramCount[tokens[i-1]] + V)
      END IF
      logSum <- logSum + LOG2(p)
      tokenCount <- tokenCount + 1
    END FOR
  END FOR

  crossEntropy <- -logSum / tokenCount
  perplexity <- 2 ^ crossEntropy
  RETURN perplexity
END

Real-World Applications

• Spell checking and autocorrect: N-gram models score candidate corrections by how likely the resulting sentence is, preferring "the cat sat" over "the bat sat" when context supports it
• Speech recognition: N-gram language models rescore acoustic model outputs, choosing the word sequence with the highest combined probability
• Machine translation (pre-neural): Statistical MT systems like Moses used n-gram language models as a fluency component alongside translation models
• Text prediction on keyboards: Mobile keyboards use n-gram models (often trigram) to suggest the next word as you type
• Spam filtering: Character-level n-grams detect patterns in spam text that word-level features miss, like obfuscated words ("v1agra")
• Authorship attribution: Character n-gram distributions serve as stylistic fingerprints, distinguishing authors by their unconscious writing patterns

Key Takeaways

• N-gram language models estimate the probability of the next word by counting how often word sequences appear in a training corpus
• The Markov assumption limits context to $n-1$ previous words, making the model tractable but unable to capture long-range dependencies
• Smoothing is essential because most possible n-grams never appear in training data, and zero probabilities break the entire model
• Kneser-Ney smoothing outperforms simpler methods by using continuation probability: how many distinct contexts a word appears in, not just its raw frequency
• Perplexity measures model quality: a perplexity of $k$ means the model is as uncertain as if it were choosing uniformly among $k$ words at each step