N-gram Language Models

An n-gram is a contiguous sequence of n tokens from a piece of text. N-gram models estimate the probability of a word based on the previous n-1 words (the Markov assumption from the previous lesson).

Types of N-grams

Generating N-grams in Python

from nltk import word_tokenize
from nltk.util import ngrams

text = "I love natural language processing"
tokens = word_tokenize(text)

bigrams = list(ngrams(tokens, 2))
trigrams = list(ngrams(tokens, 3))

print(bigrams)
# [('I', 'love'), ('love', 'natural'), ('natural', 'language'), ('language', 'processing')]
print(trigrams)
# [('I', 'love', 'natural'), ('love', 'natural', 'language'), ('natural', 'language', 'processing')]

Maximum Likelihood Estimation (MLE) for Bigrams

P(w_i | w_{i-1}) = Count(w_{i-1}, w_i) / Count(w_{i-1})

from collections import Counter
from nltk import word_tokenize, bigrams

corpus = "the cat sat on the mat the cat ate the fish"
tokens = word_tokenize(corpus)

unigram_counts = Counter(tokens)
bigram_counts = Counter(bigrams(tokens))

def mle_bigram_prob(w1, w2):
    return bigram_counts[(w1, w2)] / unigram_counts[w1]

print(mle_bigram_prob("the", "cat"))   # 2/4 = 0.5
print(mle_bigram_prob("cat", "sat"))   # 1/2 = 0.5

Using an N-gram Model to Predict the Next Word

def predict_next_word(w1, bigram_counts):
    candidates = {w2: c for (w1_, w2), c in bigram_counts.items() if w1_ == w1}
    if not candidates:
        return None
    return max(candidates, key=candidates.get)

print(predict_next_word("the", bigram_counts))   # 'cat' (most frequent word after "the")

Computing Sentence Probability with a Bigram Model

def sentence_probability(sentence_tokens, bigram_counts, unigram_counts):
    prob = 1.0
    for w1, w2 in zip(sentence_tokens, sentence_tokens[1:]):
        prob *= bigram_counts[(w1, w2)] / unigram_counts[w1]
    return prob

s = word_tokenize("the cat sat")
print(sentence_probability(s, bigram_counts, unigram_counts))
# 0.5 * 0.5 = 0.25

The Zero-Probability Problem

s2 = word_tokenize("the fish sat")
print(sentence_probability(s2, bigram_counts, unigram_counts))
# ("fish", "sat") never occurred in training data -> Count = 0 -> entire product = 0.0!

If even one bigram in a test sentence was never seen in training, the model assigns the entire sentence a probability of zero — clearly wrong, since "the fish sat" is a perfectly plausible sentence just not present in this tiny corpus. This is the data sparsity problem, and it is solved using smoothing techniques, covered in the next lesson.

Choosing N — the Trade-off

In practice, trigrams are a common sweet spot for classical statistical LMs — beyond that, neural language models (Unit 4) handle long context far more gracefully.