Implementing N-gram Models

Prepping Your Text Data

Before you can build an N-gram model, you need to clean and prepare your text data. This process, called preprocessing, ensures your model isn't tripped up by inconsistencies like capitalization or punctuation. The goal is to create a standardized vocabulary from your raw text.

The first step is tokenization, which means breaking down text into individual units, or tokens. Usually, tokens are just words. For example, the sentence "The quick brown fox jumps." becomes a list of tokens: ["The", "quick", "brown", "fox", "jumps", "."].

Next, you'll want to normalize the text. This typically involves converting all tokens to lowercase to ensure that "The" and "the" are treated as the same word. You should also remove punctuation and any other non-alphanumeric characters that don't carry meaning for your model. After these steps, our example list looks much cleaner: ["the", "quick", "brown", "fox", "jumps"].

import re
import nltk
from nltk.tokenize import word_tokenize

nltk.download('punkt') # Ensure the tokenizer is downloaded

def preprocess_text(text):
    # Convert to lowercase
    text = text.lower()
    # Remove non-alphanumeric characters (except spaces)
    text = re.sub(r'[^a-zA-Z0-9\s]', '', text)
    # Tokenize the text into words
    tokens = word_tokenize(text)
    return tokens

# Example usage:
sample_text = "The quick, brown fox jumps over the lazy dog!"
processed_tokens = preprocess_text(sample_text)
print(processed_tokens)
# Output: ['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog']

One final consideration is handling words that appear in your test data but not in your training data. These are called out-of-vocabulary (OOV) words. A common strategy is to replace rare words in your training set with a special <UNK> (unknown) token. This helps the model learn to handle words it has never seen before.

Constructing the Model

With a clean list of tokens, you can now generate the N-grams. An N-gram is simply a sequence of N consecutive tokens. For N=2, we have bigrams; for N=3, trigrams. Let's take our processed tokens: ['the', 'quick', 'brown', 'fox', 'jumps'].

The bigrams would be: ('the', 'quick'), ('quick', 'brown'), ('brown', 'fox'), and ('fox', 'jumps').

The core of an N-gram model is counting. You need to count the occurrences of each N-gram and each (N-1)-gram that forms its prefix. For a bigram model, you'd count all the bigrams and all the individual words (unigrams).

from collections import defaultdict, Counter

def build_ngram_counts(tokens, n):
    ngram_counts = defaultdict(Counter)
    # The prefix is the first n-1 words of an n-gram
    # The target word is the nth word
    for i in range(len(tokens) - n + 1):
        prefix = tuple(tokens[i:i+n-1])
        target_word = tokens[i+n-1]
        ngram_counts[prefix][target_word] += 1
    return ngram_counts

# Using our processed tokens from before
# For a bigram model (n=2), the prefix is a 1-gram (unigram)
bigram_counts = build_ngram_counts(processed_tokens, 2)

# Let's inspect the counts for the prefix ('the',)
print(bigram_counts[('the',)])
# Output: Counter({'quick': 1, 'lazy': 1})

This bigram_counts dictionary now holds the core of our model. The keys are prefixes (tuples of words), and the values are Counter objects that map the next possible word to its frequency. To find the probability of a word given the previous word, you divide its count by the total count of all words that followed that prefix.

Smoothing Out the Bumps

A major problem arises when your model encounters an N-gram it never saw during training. For example, if the bigram ('lazy', 'cat') wasn't in our training text, its count is zero. This means the calculated probability will be zero, which can cause issues, especially when calculating the probability of an entire sentence.

Smoothing techniques solve this by redistributing a tiny bit of probability from the N-grams we've seen to the ones we haven't. This ensures that no N-gram has a probability of exactly zero.

A simple and effective method is Add-k smoothing, also known as Lidstone smoothing. The idea is to add a small constant $k$ to every N-gram count. When $k=1$ , it's called Laplace smoothing.

P(w_i | w_{i-1}) = \frac{C(w_{i-1}, w_i) + k}{C(w_{i-1}) + k|V|}

The numerator adds $k$ to the count of the specific word pair. The denominator adds $k$ for every possible word that could follow the prefix, effectively adding $k \times |V|$ to the total count of the prefix. This small adjustment prevents any probability from being zero.

Putting It to the Test

How do you know if your N-gram model is any good? You evaluate its performance on a separate set of data it wasn't trained on, called a test set. A common metric for language models is perplexity.

Perplexity measures how well a probability model predicts a sample. A lower perplexity score indicates that the model is better at predicting the text in the test set. It can be thought of as the model's confusion; a more certain model is less perplexed.

Perplexity

noun

A measurement of how well a probability distribution or probability model predicts a sample. A low perplexity indicates the probability distribution is good at predicting the sample.

Mathematically, perplexity is the inverse probability of the test set, normalized by the number of words. It's often calculated using logarithms to avoid numerical underflow with very small probabilities.

\text{Perplexity}(W) = \left( \prod_{i=1}^{N} \frac{1}{P(w_i | w_{i-n+1}, ..., w_{i-1})} \right)^{1/N}

When implementing this, you'll calculate the probability of your entire test set word by word, multiply these probabilities together, and then apply the formula. Comparing the perplexity of different models (e.g., bigram vs. trigram, or different smoothing values) on the same test set tells you which one performs better.

Quiz Questions 1/6

What is the primary purpose of text preprocessing before building an N-gram model?

Quiz Questions 2/6

Given the tokenized sentence ['the', 'quick', 'brown', 'fox'], which of the following are the correct bigrams (N=2)?

Implementing an N-gram model from scratch is a fantastic way to solidify your understanding of how language models work at a fundamental level. From cleaning text to handling unseen events, each step builds toward a functional and evaluatable model.

Advanced Statistical Language Models in Practice