Disclaimer: This Jupyter Notebook contains content generated with the assistance of AI. While every effort has been made to review and validate the outputs, users should independently verify critical information before relying on it. The SELENE notebook repository is constantly evolving. We recommend downloading or pulling the latest version of this notebook from Github.
N-Gram Language Models¶
Language models are at the heart of many natural language processing (NLP) applications, from machine translation and speech recognition to modern conversational AI systems. Before the rise of neural networks and large language models, one of the most influential approaches to language modeling was the $n$-gram model. $N$-gram models were among the first practical methods to assign probabilities to entire sentences by decomposing them into a sequence of conditional word probabilities. This probabilistic framework provided a principled way to quantify how likely a piece of text is and laid the foundation for many subsequent advances in NLP.
The key idea behind $n$-gram language models is both simple and powerful: instead of considering the entire history of a sentence, the probability of a word is approximated using only a limited number of preceding words. This assumption makes it possible to estimate language statistics directly from text corpora and to predict the likelihood of unseen sentences. Despite their simplicity, $n$-gram models capture many important regularities of natural language and provide an intuitive introduction to probabilistic language modeling.
Learning about $n$-gram models remains valuable even though modern NLP is now dominated by neural network–based approaches such as transformers. Many of the concepts that underpin contemporary language models (including conditional probabilities, sequence modeling, next-word prediction, and evaluation through likelihood) can be understood more easily through the lens of $n$-gram models. Because the models are mathematically transparent and relatively straightforward to implement, they provide an excellent stepping stone toward understanding more sophisticated language modeling techniques.
In this notebook, we will explore both the theory and practice of $n$-gram language models. We will learn how to estimate $n$-gram probabilities from data, compute sentence probabilities, and implement language models from scratch. Along the way, we will examine their strengths, limitations, and historical significance, gaining insight into a class of models that played a foundational role in the evolution of modern NLP.
Setting up the Notebook¶
Make Required Imports¶
This notebook requires the import of different Python packages but also additional Python modules that are part of the repository. If a package is missing, use your preferred package manager (e.g., conda or pip) to install it. If the code cell below runs with any errors, all required packages and modules have successfully been imported.
from src.utils.libimports.ngramlm import *
from src.models.ngram.ngramlm import *
from src.utils.data.files import *
Download Required Data¶
Some code examples in this notebook use data that first need to be downloaded by running the code cell below. If this code cell throws any error, please check the configuration file config.yaml if the URL for downloading datasets is up to date and matches the one on Github. If not, simply download or pull the latest version from Github.
movie_reviews_zip, target_folder = download_dataset("text/corpora/reviews/movie-reviews-imdb.zip")
File 'data/datasets/text/corpora/reviews/movie-reviews-imdb.zip' already exists (use 'overwrite=True' to overwrite it).
We also need to decompress the archive file.
movie_reviews = decompress_file(movie_reviews_zip, target_path=target_folder)
print(movie_reviews)
['data/datasets/text/corpora/reviews/movie-reviews-imdb.txt']
Quick Recap: Language Models¶
The fundamental idea behind a language model is to assign probabilities to sequences of words or tokens according to how likely they are to occur in a language. Intuitively, fluent and meaningful sequences such as "the cat sat on the mat" should receive higher probabilities than unlikely or nonsensical sequences such as "mat the on sat cat the". By estimating these probabilities from large collections of text, a language model captures statistical regularities of language and can be used to predict missing words, rank alternative interpretations, detect errors, or generate text. In essence, a language model provides a quantitative measure of how well a sequence conforms to the patterns observed in natural language.
To give a concrete example, consider the task of speech recognition, a highly non-trivial task since spoken language is highly variable and context-dependent. People have different accents, speaking speeds, intonations, and pronunciation styles, which can make it difficult for systems to consistently interpret audio input. Background noise, overlapping speech, and unclear articulation can further complicate recognition. Additionally, spoken language often includes informal expressions, filler words, and fragmented sentences that don’t follow standard grammar rules.
Another major difficulty lies in understanding context and meaning. Many words sound alike (homophones) but have different meanings, and identifying the correct word often depends on the context of the conversation. For example, distinguishing between "there", "their", and "they're" in spoken language requires understanding the broader sentence structure and intent. Furthermore, recognizing named entities (like people's names or places) and adapting to domain-specific vocabulary (such as medical or legal terms) adds another layer of complexity to building accurate and reliable speech recognition systems. For example, consider the following sentence
"I ate cereal last night."
Although seemingly a very simple sentence, notice that it contains two homophones: "cereal" vs. "serial", and "night" vs. "knight". If we as humans hear this sentence, we generally have no problem identifying which words are meant as they are the only ones that make sense to us. However, the notion of "makes sense" is obvious how to implement. Thus, in case of homophones — but generally for all kinds of ambiguous cases — a speech recognition system has to identify the most likely choice of words. Once again, we need some mechanism that tells us that
"I ate cereal last night." $>$ "I ate serial last knight."
at least most of the time, acknowledging the possibilities of exceptions. Thus, to express uncertainty, we need to assign probabilities to sequences such that we can indeed meaningfully quantify that the first sequence is the more likely one; more formally:
To generalize this idea, let $S = w_1, w_2, w_3, \dots, w_{n}$ be a sequence of words $w_i$ of length $n$. Again $S$ may be a single word, a phrase, or a sentence — in fact, $S$ may contain words beyond the boundaries of sentences or paragraphs, but we limit ourselves to sentences to keep it simple. With that, we can define the probability of sequence $S$ as the joint probability of all words $w_1, w_2, w_3, \dots, w_{n}$:
where $w_{1:n}$ is simplified notation referring to the sequence $w_1, w_2, \dots, w_{n}$.
Calculating joint probabilities directly is often difficult because the number of possible combinations of events (here: words) increases exponentially with the number of variables (here: number of words in $S$). The chain rule in probability is a way to break down a joint probability — the probability of multiple events happening together — into a product of conditional probabilities. It allows us to express complex probabilities in terms of simpler, step-by-step terms. For example, the joint probability of three events $A$, $B$, and $C$ happening together, written as $P(A,B,C)$, can be broken down using the chain rule as:
This means you first find the probability of $A$, then the probability of $B$ given that $A$ has happened, and finally the probability of $C$ given that both $A$ and $B$ have happened. The chain rule is used to model sequences or dependencies among variables by simplifying complex joint distributions into manageable conditional pieces. Using the chain rule we can calculate our joint probability $P(w_1, w_2, w_3, \dots, w_{n})$ as follows:
where $P(w_i\mid w_1, w_2,\dots ,w_{i-1})$ is the conditional probability of seeing the word $w_i$ after the sequence of words $w_1, w_2,\dots ,w_{i-1}$. All common language models calculate (or estimate!) the conditional probabilities instead of the joint probabilities directly. For example, we can calculate the probability of the sentence "I ate cereal last night" by using the chain rules as:
Of course, the question is now, how these conditional probabilities $P(w_i\mid w_1, w_2,\dots ,w_{i-1})$ are calculated and depends on the type of language model; the most common types of language models are:
- N-gram language models (count-based)
- Feed-forward neural language models
- RNN language models
- LSTM/GRU language models
- Transformer language models
Despite their differences, all language models learn the probabilities from training data, ideally a very large corpora of training data. In general, a language model will assign a higher probability to a sequence of words if the sequence — or its parts — do more commonly occur in the training corpus, and vice versa. For example, we would expect that the phrases "I ate cereal" or just "ate cereal" are much more common than the phrases "I ate serial" or "ate serial" (although they might exist in the training corpus even just as a typo).
Although Transformer-based and other modern neural language models represent the current state of the art for text generation, $n$-gram language models remain surprisingly effective for many tasks that require comparing a small number of alternatives rather than generating entirely new text. In applications such as spell checking, speech recognition, and optical character recognition, the goal is often to select the most plausible candidate from a set of possibilities, and $n$-gram models can provide reliable probability estimates for this purpose. Moreover, $n$-gram models are significantly easier to understand, implement, train, and interpret than neural models. Their predictions are based directly on observable counts in the training data, making it possible to trace and explain why a particular probability was assigned. For these reasons, $n$-gram language models continue to serve as both a practical baseline and an accessible introduction to the fundamental ideas underlying language modeling.
N-Grams LMs¶
Although modern language models are typically based on neural networks, it is helpful to begin with $n$-gram language models because they embody the core idea behind all language modeling in a simple and intuitive way. Like neural language models, $n$-gram models assign a probability to a sequence of words by decomposing it into a product of conditional probabilities. The key difference is that an $n$-gram model estimates these probabilities directly from observed counts in a corpus, using only a fixed number of preceding words as context. As a result, $n$-gram models are straightforward to implement, computationally efficient, and easy to interpret: the probability assigned to a word can be traced directly to statistics gathered from the training data.
Despite their simplicity, $n$-gram language models remain useful for a variety of applications. While they generally lack the long-range context and expressive power needed to generate fluent, coherent text, they often perform well in tasks that involve selecting the best candidate from a set of alternatives (e.g., spell checking or speech recognition. In such ranking and comparison tasks, the ability of $n$-gram models to efficiently estimate relative probabilities can make them surprisingly effective.
So let's see how they work.
Core Approach¶
$N$-gram language models compute the conditional probabilities $P(w_i|w_1, w_2,\dots ,w_{i-1})$ by using the relative frequencies of observed $n$-grams in a text corpus. The goal is to estimate the probability of a word given its preceding words. This is done using the Maximum Likelihood Estimation (MLE) approach, which assumes that the best estimate of a probability is the observed frequency of an event — here: the $n$-gram $(w_1, w_2, \dots, w_{n-1}, w_{n})$ — divided by the total number of relevant events — here: the sequence of preceding words $(w_1, w_2, \dots, w_{n-1})$; also called the context.
This, for $n$-grams of arbitrary sizes, the conditional probability $P(w_n|w_1, w_2,\dots ,w_{n-1})$ is then defined as:
where the numerator $count(w_1, w_2, \dots, w_{n-1}, w_{n})$ is the number of times the full $n$-gram appears in the corpus; the denominator $count(w_1, w_2, \dots, w_{n-1})$ is the number of times the context appears. Using this definition, we can, for example calculate the conditional probability $P(\text{"night "}|\text{ "I ate cereal last"})$ as:
A key advantage of this approach is its simplicity and intuitiveness. The estimated probability of a word directly reflects how often it has been observed to follow a particular context in the training corpus. As a result, the model requires only straightforward counting and normalization operations, making it easy to understand, implement, and interpret. This close connection between observed data and estimated probabilities makes $n$-gram language models a natural and transparent application of the maximum likelihood principle.
Markov Assumption¶
In principle, the probability of a word in a sentence depends on all preceding words. Using the chain rule, the probability of a sequence can be decomposed into a product of conditional probabilities, where each word is conditioned on the entire history of the sentence. However, estimating such probabilities directly is infeasible in practice. The number of possible word histories grows exponentially with sentence length, and even very large corpora contain only a tiny fraction of all possible contexts. Consequently, many word sequences occur rarely or not at all, making reliable probability estimation impossible.
To address this problem, $n$-gram language models adopt the Markov assumption, which states that the probability of a word depends only on a limited number of preceding words rather than the complete history. By restricting the context to the previous $n-1$ words, the model drastically reduces the number of parameters that must be estimated and increases the likelihood that relevant contexts are observed in the training data. For example, a $2$-gram (or bigram) language models considers only $1$ word as the context; a $3$-gram (or trigram) language models considers only $2$ words as the context. This approximation makes language modeling computationally tractable while still capturing many of the local dependencies that are important for predicting the next word.
For example, we can estimate the conditional probability $P(\text{"night "}|\text{ "I ate cereal last"})$ using bigram or trigram probabilities as shown below:
To show some concrete example calculations, let's define a toy training corpus containing the following sentences:
- "Everyone went home last night once the movie ended."
- "Sir Bedivere is often considered the last knight in Arthurian legend."
- "The last night of the year is called New Year's Eve."
- "The team finished last due to its poor performance throughout the last tournament"
No let's consider our speech recognition example where we need to decide if the we heard "I ate cereal last night" or "I ate cereal last knight". Assuming a bigram language model, we have to calculate the two conditional probabilities $P(\text{"night "}|\text{ "last"})$ and $P(\text{"knight "}|\text{ "last"})$. Of course, both relative frequencies have the same denominator of $count(\text{"last"}) = 5$ since the $1$-gram (or unigram) "last" appears five times in our training corpus. Regarding the numerators, we have $count(\text{"last night"}) = 2$ and $count(\text{"last knight"}) = 1$. Thus, we can calculate the two required conditional probabilities as follows:
Thus, given the training dataset and our bigram language model, we would say that that "night" is the more likely word among both homophones.
More generally, we use the Markov assumption to approximate the conditional probability $P(w_n \mid w_{1\ :\ n-1})$ by limiting the size of the context. In the case of bigrams and trigrams, these approximations look as shown below: bigram language models consider only $1$ preceding word as the context, and trigram language models consider only $2$ preceding words as the context.
To generalize, if $N$ denotes the size of the $n$-grams (e.g., $N=2$ for bigrams or $N=3$ trigrams), we approximate the conditional probability $P(w_n \mid w_{1\ :\ n-1})$ as:
Smoothing¶
Even with the simplifying power of the Markov assumption, $n$-gram language models remain fragile. While limiting the context window to $n-1$ words drastically reduces the number of unique histories the model must track, but it does not eliminate the data sparsity problem. Language is inherently creative, and the distribution of words follows a heavy-tailed power law (Zipf's law), meaning a massive portion of perfectly valid word combinations occur rarely, if ever, in any given training corpus. As a result, when an $n$-gram model encounters a completely natural but unseen sequence during testing or deployment, Maximum Likelihood Estimation (MLE) assigns it a probability of exactly $0$.
This "zero-probability problem" has catastrophic compounding effects on a language model. Because the joint probability of an entire sentence is computed as the product of its individual conditional probabilities, a single unseen $n$-gram will zero out the probability of the entire sequence, rendering the model incapable of evaluating or generating novel text. Smoothing techniques are essential to fix this structural flaw. They mathematically adjust the MLE estimates by borrowing a small amount of probability mass from frequently observed $n$-grams and redistributing it to unseen or rare sequences. By ensuring that no valid sequence is ever assigned a probability of $1$, smoothing transforms a rigid, corpus-bound frequency counter into a robust, generalizable language model.
One of the most basic smoothing methods is Laplace smoothing, also known as Add-1 smoothing, where a constant value of $1$ is added to all $n$-gram counts in the corpus. Laplace smoothing artificial inflates every count by $1$, ensuring that every possible sequence is observed at least once. To maintain a valid probability distribution that sums to $1$, the denominator is adjusted by adding the total size of the vocabulary, $V$, for each possible continuation.
For example, for a bigram model, the smoothed probability of a word $w_n$ given the previous word $w_{n-1}$ is calculated as:
If we know combine the Markov assumption with smoothing, we get the final expression to compute the conditional probability of a word give a context:
While Laplace smoothing successfully eliminates the zero-probability problem, it introduces significant practical flaws that make it poorly suited for modern language modeling.
The Vocabulary Explosion (Too Much Probability Mass Shifted): In natural language, the vocabulary size $|V|$ is typically very large (tens or hundreds of thousands of words). Because Laplace smoothing adds $1$ to every single possible word combination, it collectively invents a massive amount of "artificial" counts for unseen sequences. Consequently, the model shifts an overwhelming majority of its total probability mass to $n$-grams that never actually appeared in the training data, drastically starving the probabilities of the words that did occur.
The Equal Probability Fallacy: Laplace smoothing treats all unseen events as equally likely. For example, if the bigrams "at the" and "at pterodactyl" were both unseen in a small corpus, Laplace smoothing would assign them the exact same probability. In reality, "at the" is a highly probable English phrase that was likely missed due to a small sample size, whereas "at pterodactyl" is genuinely rare. Basic Laplace smoothing lacks the sophistication to distinguish between these cases.
Severe Distortion of Frequent Counts: Because the denominator is heavily inflated by adding $|V|$, the relative differences between frequently occurring words become flattened and distorted. The model loses its sharp predictive accuracy for common phrases because its probability distribution is artificially smoothed out toward a uniform distribution.
Later, when training small language models on real-world data, we will illustrate some of these issues in a bit more detail.
One basic approach to address this issue to generalize Laplace Smoothing from Add-$1$ smoothing to Add-$k$ smoothing, where $k$ is a positive tuning parameter typically chosen to be much smaller than 1 (e.g., $k = 0.05$ or $k = 0.01$). By choosing a fractional value for $k$, you directly mitigate the primary flaw of Laplace smoothing: the massive, artificial inflation of the denominator. The adjusted formula for a bigram model becomes:
If, say, $k = 0.01$ and your vocabulary size $V$ is $100,000$, the denominator only increases by $1,000$ instead of a crushing $100,000$. This prevents the model from shifting an overwhelming majority of its probability mass to unseen words, preserving the sharp, realistic probabilities of frequent $n$-grams. However, Add-$k$ smoothing introduces a hyperparameter that must be optimized. You typically find the best $k$ by testing a range of values on a held-out validation set and choosing the one that minimizes perplexity.
More importantly, Add-$k$ smoothing still suffers from the Equal Probability Fallacy. Even if $k$ is incredibly small, the model still adds the exact same value of $k$ to every unseen $n$-gram. More advanced smoothing methods address this issue by redistributing probability mass according to the observed statistical structure of the data rather than treating all unseen events equally. Good-Turing smoothing estimates the total probability of unseen $n$-grams from the frequency of rare events, while Katz backoff uses discounted counts and backs off to lower-order $n$-gram models when data are sparse. Kneser-Ney smoothing further improves estimates by considering not only how often a word occurs, but also in how many different contexts it appears, making it particularly effective for language modeling. These approaches provide more realistic probability estimates and avoid assigning identical probabilities to all unseen word sequences.
However, since $n$-gram language models fall a bit out of favor with the advent of neural network-based models, a more comprehensive discussion of these more sophisticated smoothing strategies is beyond the scope of this notebook.
Practical Considerations¶
Although we have covered all the essentials of $n$-gram language models, there are two additional but simple things we need to consider when actually implementing them. To motivate both, let's consider our initial example of computing the probability for the sentence "I ate cereal last night", i.e.:
Padding¶
If we would directly apply the chain rule to compute this probability and assume trigrams, we would compute get the following expression:
The main problem here is that the first two terms $P(\text{"I"})$ and $P(\text{"ate"}\mid\text{"I"})$ are not trigram probabilities. So, right now, we cannot compute these probabilities. One solution would be to also keep track of all counts for $n$-grams of size $N$ — for our example, we would also need to keep track of all bigram and unigram counts to compute the bigram and unigram probabilities. While possible, it adds a significant amount of memory to the model.
The more practical alternative is to introduce a special token (e.g., $\text{"[SOS]"}$) to mark the start of a sentence/sequence and append $N-1$ instances of this special token to the sentence/sequence. This means that our small example sentence now becomes "[SOS] [SOS] I ate cereal last night". Now applying the chain rule gives us:
Of course, with $P(\text{"[SOS]"})$ and $P(\text{"[SOS]"}\mid\text{"[SOS]"})$ we still have two non-trigram probabilities. However, since the $"[SOS]"$ tokens is not really part of the sentence, and we would compute the same probabilities for all sentences, we can comply ignore these two probabilities and start with the first trigram $P(\text{"I"}\mid\text{"[SOS] [SOS]"})$ probability for our example here.
Apart from the start of a sentence/sequence, we also have to explicitly mark its end using a special token (e.g., $\text{"EOS"}$). Without such a token, we are not really assigning probability to a complete sentence, only to a prefix. To give a counter-example, consider the alternative example sequence "[SOS] [SOS] I ate cereal last and" (which could be the beginning of a longer sentence such as "I ate cereal last and only drank water after that"). We, as humans, can "just see" that this is not a proper complete sentence, the language model can not. If we apply the chain rule now, the last probability term would be $P(\text{"and"}\mid\text{"cereal last"})$.
The problem now is that this probability $P(\text{"night"}\mid\text{"cereal last"})$ might actually have a high value, potentially higher than $P(\text{"night"}\mid\text{"cereal last"})$. Since all the other terms are the same, the language model would give "I ate cereal last and" a higher total probability than "I ate cereal last night". This issue occurs because we did not explicitly model the end of a sequence. Let's therefore and an $\text{"EOS"}$ token to the example — in contrast to the $\text{"[SOS]"}$, we only need to add a single $\text{"[EOS]"}$ token, no matter the $n$-gram size — to get
- "[SOS] [SOS] I ate cereal last night [EOS]"
- "[SOS] [SOS] I ate cereal last and [EOS]"
Again, when applying the chain rules, both expression would only differ with respect to the last two terms:
It is arguably reasonable to expect that the trigram probability $P(\text{[EOS]}\mid\text{"last and"})$ will much much lower than $P(\text{[EOS]}\mid\text{"last night"})$, thus making the overall probability of the sequence "I ate cereal last night" larger than of the sequence "I ate cereal last and". We also need the $\text[EOS]$ when using the $n$-gram language model when generating text — although such models are not commonly used for text-generation — so that the model knows when to stop predicting a next token.
Keep in mind that the underlying approach of computing $n$-gram counts to compute all probabilities does not change at all. These special tokens get more or less treated as any other tokens, which includes that we also need to add the special tokens to our vocabulary.
Log Probabilities¶
As we just saw, even when working with short sequences, we quickly need to compute the product of many $n$-gram probabilities. The problem is that all these $n$-gram probabilities tend to be small to very small values in practice. Again, this comes down to the expressiveness and flexibility of natural language, often allowing a larger number of words/tokens to follow the same context. As a consequence, we might have to compute the product of many (very) small values. For long sequences, this can result in arithmetic underflow if we reach the maximum amount of precision our computer can represent.
Fortunately, in practice, we typically do not care about the true probabilities. In basically all cases, we either want to compare the probabilities of two or more sequences, or use the language model to predict the next word given some context. In other words, we are always interested in the relationship between the probabilities (i.e., their ranking). We can therefore apply any monotonically increasing function on both sides to preserve the ranking. The most convenient choice in practice is applying the logarithm to work with log probabilities. This means that our product of probabilities becomes the sum of log probabilities. More specifically, instead of computing
we utilize the fact a product of probabilities is proportional to the sum of log probabilities, i.e.:
which finally gives us:
Now we really have all the bits and pieces to implement and train a $n$-gram language model.
Basic Implementation¶
As we just saw from all the required computations to train an $n$-gram language model, they are very intuitive and as such also quite easy to implement, at least on a basic level. So just let's do this. We first start by defining a simple dataset to illustrate all the involved steps one by one. In fact, we use the same four example sentences we have seen before to check if our implementation matches the example results (i.e., the example $n$-gram probabilities) we computed above.
sentences = [
"Everyone went home last night once the movie ended.",
"Sir Bedivere is often considered the last knight in Arthurian legend.",
"The last night of the year is called New Year's Eve.",
"The team finished last due to its poor performance throughout the last tournament.",
]
The heart of $n$-gram language models are the conditional probabilities for a word $w_n$ given some context constraint by the Markov assumption. Assuming the use of Add-$k$ smoothing, here is once more the complete expression for computing the conditional probabilities:
Looking at this expression tell us all the important variables we need to define for our implementation:
N: the maximum $n$-gram size (e.g.,N=2for a bigram language model)k: the smoothing parameter of Add-$k$ smoothingvocab: the complete vocabulary (i.e., the set of unique words/tokens in the training dataset)ngram_counts: the number of occurrences of each $n$-gram (i.e., the $count$ in the numerator of the expression)context_counts: the number of occurrences of each context (i.e., the $count$ in the denominator of the expression)
The code cell below defines and initializes all these values. Notice that we set $k=0$, meaning that we do not perform any smoothing for our small example dataset; this is merely to ensure that the result we get will match the example computations from above.
N = 2 # Size of n-grams
k = 0.0 # Smoothing factor
vocab = set() # Vocabulary
ngram_counts = Counter() # Number of bigrams
context_counts = Counter() # Number of contexts
Apart from the core components, it is also good to define the special tokens as their own variables; this is a better practice than using the actual strings in the various methods.
SOS, EOS = "[SOS]", "[EOS]" # Special tokens
Computing all the correct number of $n$-grams and context, we first need to preprocess each sentence in terms of tokenizing the sentence and adding the special tokens $\text{"[SOS]"}$ and $\text{"[EOS]"}$ as motivated above. In general, tokenization is not a trivial task. We therefore use spaCy to do the heavy lifting here for us. Once we have the list of tokens, we prepend $N-1$ $\text{"[SOS]"}$ tokens and append $1$ $\text{"[EOS]"}$ token; again, we motivated the reason for this above.
def preprocess_sentence(sentence):
doc = nlp(sentence)
# Tokenize sentence using spaCy
tokens = [ t.text for t in doc ]
# Add special tokens and return final list
return [SOS]*(N-1) + tokens + [EOS]
Let's apply this method to an example sentence to confirm its correct behavior.
preprocess_sentence("This is a test .")
['[SOS]', 'This', 'is', 'a', 'test', '.', '[EOS]']
We can now train out $n$-gram language model. Training an $n$-gram language models means to compute the number of all $n$-grams and respective contexts in the training dataset — well, and generating the vocabulary. Recall that this is all the information we need to compute the conditional probabilities later; the smoothing factor $k$ is a constant.
The train() method in the code cell below implements the training by computing all counts for all sentences of a training dataset. For each sentence, the method first calls preprocess_sentence() to tokenize the sentence and add the special tokens as required. For each sentence, the method then iterates through all tokens — starting from index $N-1$ from this where we get the first valid $n$-gram — to extract the $n$-gram in terms of the context and the subsequent word. The method then uses this information to update both counters.
def train(sentences: list[str]):
# Iterate through all sentences in dataset
for sentence in sentences:
# Tokenize sentence and add special tokens
tokens = preprocess_sentence(sentence)
# Add all tokens to the vocabulary
vocab.update(tokens)
# Iterate through all tokens to generate ngrams and contexts
for i in range(N-1, len(tokens)):
# Get ngram as context+word
context = tuple(tokens[i - N + 1:i])
word = tokens[i]
# Update ngram and context counters
ngram_counts[context + (word,)] += 1
context_counts[context] += 1
Well, let's train a bigram model — assuming we set N=2 — on our example dataset containing the $4$ sentences. Notice that, in the code cell below, we reset the vocabulary and both counters to ensure that executing the code cell several times does not result in double-counting or more.
# Reset core variables
vocab = set() # Vocabulary
ngram_counts = Counter() # Number of bigrams
context_counts = Counter() # Number of contexts
train(sentences)
As a quick sanity check, we can print the number of occurrences of the bigram "last night" since we already know that this bigram appears twice in the dataset.
bigram = "last night"
#bigram = "last knight"
print(f"Count of bigram '{bigram}': {ngram_counts[tuple(bigram.split())]}")
Count of bigram 'last night': 2
With all counts computed, we have trained our $n$-gram (by default: bigram) language model. This means we now have everything to compute the conditional probability for a word given a context. The method compute_ngram_probability() is a 1:1 implementation of the expression for computing $P(w_n \mid w_{n-N+1\ :\ n-1})$. The only additional step this method is doing at the beginning is to shorten the context to the correct size in the case the provided context is too long.
def compute_ngram_probability(word, context):
# Shorten context if needed
context = tuple(context[-(N-1):]) if N > 1 else tuple()
# Numerator: ngram count + smoothing
numerator = ngram_counts[context + (word,)] + k
# Denominator: context count + smoothing
denominator = context_counts[context] + k * len(vocab)
# Return probability as the relative frequency (smoothed)
return numerator / denominator
Let's try the method by computing the two conditional probabilities $P(\text{"night"}\mid\text{"last"})$ and $P(\text{"night"}\mid\text{"last"})$ we already computed "manually" above. Notice that in the code cell below, the provided context is to long, but we still get the correct results because to shorten the context appropriately.
print(compute_ngram_probability("knight", ("I", "ate", "cereal", "last",))) # 1/5 = 0.2
print(compute_ngram_probability("night", ("I", "ate", "cereal", "last",))) # 2/5 = 0.4
0.2 0.4
Lastly, to compute the probability of a sentence, we need to compute the product of the conditional probabilities for all $n$-grams. Of course, to avoid arithmetic underflows, instead of computing the product of probabilities, we compute the sum of log probabilities. The method compute_sentence_log_probability() implements this simple computation.
def compute_sentence_log_probability(sentence):
# Tokenize sentence and add special tokens
tokens = preprocess_sentence(sentence)
# Intialize log probability to 0
log_prob = 0.0
# Iterate through all tokens to generate ngrams and contexts
for i in range(N-1, len(tokens)):
# Get ngram as context+word
context = tuple(tokens[i-N+1:i])
word = tokens[i]
# Compute the log probability of ngram and add to final result
log_prob += np.log(compute_ngram_probability(word, context))
# Return final log probability
return log_prob
We test the method with one of the sentences in our example dataset, instead of an arbitrary sentence. The reason for this is because we do not perform smoothing by default (i.e., $k=1$). As a consequence, an arbitrary sentence to contain $n$-grams not seen during training resulting in a conditional probability of $0$. And since we compute the log probabilities, $\log{0}$ would throw an error.
sentence = sentences[0]
log_prob = compute_sentence_log_probability(sentence)
print(f"Log probability of sentence '{sentence}': {log_prob:.3f}")
Log probability of sentence 'Everyone went home last night once the movie ended.': -4.382
To sum up, the previous code represents the most basic implementation of an $n$-gram language model: counting $n$-grams and their contexts, and then compute the basic probabilities as their relative frequencies. Appreciate how short and straightforward this implementation is, again emphasizing the simplicity of $n$-gram language models. Although not shown here, we can easily inspect all individual $n$-gram probabilities when computing the log probability of a sentence. This allows for an intuitive way to interpret the results, e.g., spotting any conditional probabilities that are unexpectedly high or low.
Practical Application¶
Dataset Preparation¶
The ACL IMDB (Large Movie Review) dataset is a popular benchmark dataset for sentiment analysis, introduced by Andrew Maas et al. (2011). It contains a total of 100,000 movie reviews collected from IMDb, with 50,000 reviews being labeled as either positive or negative and evenly split into 25,000 reviews for training and 25,000 for testing. For training Word2Vec word embeddings we do not need the sentiment labels. We therefore already preprocessed the original dataset such that all 100,000 reviews are in a single file, with 1 line = 1 review. This preprocessing included the removal of any HTML tags and line breaks.
In the setup section of the notebook, we already downloaded the file containing all 100,000 movie reviews. In the following code cell, simply counts the number of reviews by containing the number of each line in the file, just to check if the dataset is complete. Note that we have to write movie_reviews[0] since movie_reviews is a list of files — it just so happens that the list contains only one file.
total_reviews = sum(1 for _ in open(movie_reviews[0]))
print(f"Total number of reviews (1 review per line): {total_reviews}")
Total number of reviews (1 review per line): 100000
Although we have a total 100,000 reviews (each containing multiple sentences), using all of them requires quite some preprocessing and training time. For convenience, we therefore distinguish between a demo and a full mode, where the demo only considers the first $10,000$ reviews. However, you can edit the code cell below to increase or decrease the number of considered reviews. For a first run, we recommend sticking to 10,000 reviews to execute and understand the code.
mode = "demo"
#mode = "full"
if mode == "demo":
num_considered_reviews = 10_000
else:
num_considered_reviews = 100_000
num_reviews = min(total_reviews, num_considered_reviews)
print(f"Number of reviews used for training dataset: {num_reviews}")
Number of reviews used for training dataset: 10000
Since every line in the file is a review typically containing multiple sentences, we first have to split each review into its sentences using spaCy. To this end, the code cell below iterates over all considered reviews, splits each review into sentences, and records all sentences in a list sentence which then serves as input for the training.
sentences = []
with open(movie_reviews[0]) as file:
for idx, review in enumerate(tqdm(file, total=num_reviews, leave=False)):
if idx >= num_reviews:
break
doc = nlp(review)
for sent in doc.sents:
sentences.append(str(sent))
print(f"Total number of sensentences: {len(sentences)}")
Total number of sensentences: 135677
Class Implementation¶
For this part, we combined all the code to train an $n$-gram language model we have seen above it its own class; you can check out the class NGramLanguageModel in the file src/model/ngram/ngramlm.py. This class features all the methods we have used individually when training a model step by step on a small example dataset. However, we have made some additions to make this class a bit more flexible and usable:
- The constructor as the optional argument
lowercaseto specify if sentences should be converted to lowercase characters; this can be a good choice for smaller dataset to reduce sparsity - The class has an additional attribute
self.contextswhich keeps track of all the words we have seen at least once for a given context; this information is used when using the trained model for generating text. - The class has a new method
generate()to generate text for a given start context (optional). In this specific implementation, we only consider words we have seen at least once for a given context. Only these words are candidate words, and from this set of candidate words, we focus on thetopkwords with the highest probabilities, and sample one word randomly proportional to the probabilities.
Side note: In principle, all words in the vocabulary can be candidates for the next word given a context; we still have the probabilities to make suitable words more likely. However, limiting the candidates to words we have seen at least once for a context tends to yield better results (within reason of $n$-gram language models) but also improves the efficiency.
Model Training & Insights¶
Effects of Smoothing¶
Recall that we introduced smoothing to address the data sparsity problem and avoid zero probabilities, when an $n$-gram model encounters a completely natural but unseen sequence during testing or deployment and assigns it a probability of $0$. This is why we introduced the concept of smoothing However, we also motivated that basic smoothing strategies such Laplace (Add-$1$) smoothing can cause issues in practice; recall
- The vocabulary explosion (too much probability mass shifted)
- The equal probability fallacy
- Severe distortion of frequent counts
To better appreciate those issues, let's train two bigram language models, one without smoothing ($k=0$) and one with Laplace smoothing ($k=1$).
ngram_lm2_unsmoothed = NGramLanguageModel(N=2, k=0.0, lowercase=True)
ngram_lm2_smoothed = NGramLanguageModel(N=2, k=1.0, lowercase=True)
ngram_lm2_unsmoothed.train(sentences)
ngram_lm2_smoothed.train(sentences)
100%|██████████████████████████████████████████████████████████████████████████████████████████████| 135677/135677 [00:25<00:00, 5311.92it/s] 100%|██████████████████████████████████████████████████████████████████████████████████████████████| 135677/135677 [00:25<00:00, 5292.55it/s]
Having trained both models, we can use them to compute their probabilities for the same $n$-gram for a comparison. In the code cell below, we compute the probabilities for the bigram "i like"; recall that we convert all sentences to lowercase.
unsmoothed_prob = ngram_lm2_unsmoothed.compute_ngram_probability("like", ("i",))
smoothed_prob = ngram_lm2_smoothed.compute_ngram_probability("like", ("i",))
print(f"Unsmoothed probability of 'i like': {unsmoothed_prob:.4f}")
print(f"Smoothed probability of 'i like': {smoothed_prob:.4f}")
Unsmoothed probability of 'i like': 0.0074 Smoothed probability of 'i like': 0.0031
Two things are worth mentioning. Firstly, even for arguably common bigrams, the probabilities are typically rather small in absolute terms. This clearly shows the importance of using log probabilities to computing the log probabilities for whole sequences/sentences. And secondly, notice how the two probabilities significantly differ. In fact, the probability when using Laplace smoothing is less than half the one without smoothing. This shows how smoothing and the resulting shifting of probability mass from unknown to unknown bigrams can greatly affect the counts and probabilities, and thus the quality of the model in practice.
To even better illustrate this problem, let's look at multiple bigram and check out their counts and probabilities in more detail. For example, let's consider the simple sentence "i like the story" defined as a list of tokens below. While we assume this example for the next steps, you can change to a different example if you are curious about other specific values.
tokens = ["i", "like", "the", "story"]
For convenience, we provide the auxiliary method generate_bigram_data() to display the counts or probabilities for bigrams and their contexts (which are just single tokens/words, i.e., unigrams) a Pandas Dataframe. We first consider the bigram model without smoothing to get the counts for all possible bigrams and contexts.
df_unsmoothed_bigram_counts, df_unsmoothed_context_counts = generate_bigram_data(ngram_lm2_unsmoothed, tokens, mode='counts')
Let's look at the counts for the contexts.
df_unsmoothed_context_counts
| i | like | the | story | |
|---|---|---|---|---|
| counts | 37140 | 9058 | 131220 | 4204 |
As the result shows, the word "the" appears $131,220$ times in the training dataset; we assume the demo mode considering $10.000$ movie reviews. In contrast, the word "story" appears only 4,204 times. Keep it mind that those are the denominator values when computing the bigram probabilities. We can now also look at the counts for the bigram. In fact, we can look at all bigrams in terms of considering any order of two words.
df_unsmoothed_bigram_counts
| i | like | the | story | |
|---|---|---|---|---|
| i | 0 | 275 | 13 | 0 |
| like | 186 | 3 | 857 | 2 |
| the | 9 | 23 | 54 | 1847 |
| story | 8 | 13 | 6 | 0 |
According to this output, the bigram "i like" appears $275$ times while the bigram "like i" appears $186$ times in the training data. The most frequent bigram for this small example is "the story" with $1,847$ occurrences. Some of the counts seem a bit unintuitive. For example, the dataset contains the bigram "the the" 54 times. This just shows that we deal with a real-world dataset here. It is very common for people to accidentally type the same word twice, especially when writing quickly or making edits. This occurs most frequently with short, high-frequency words such as articles ("the", "a") and prepositions ("of", "to", "in"*), because they are used repeatedly and are often entered automatically without conscious attention.
Using these counts, can compute all bigram probabilities. For example, the probability of "i like" is:
which matches the value we saw above. Instead of manually computing the probabilities for all the bigram, we can again use the auxiliary method generate_bigram_data() but this time to return the probabilities instead of the counts; note that we are only interested in the bigram probabilities here.
df_unsmoothed_bigram_probs, _ = generate_bigram_data(ngram_lm2_unsmoothed, tokens, mode='probs')
df_unsmoothed_bigram_probs
| i | like | the | story | |
|---|---|---|---|---|
| i | 0.0000 | 0.0074 | 0.0004 | 0.0000 |
| like | 0.0205 | 0.0003 | 0.0946 | 0.0002 |
| the | 0.0001 | 0.0002 | 0.0004 | 0.0141 |
| story | 0.0019 | 0.0031 | 0.0014 | 0.0000 |
For example, the entry in the first row and the second column represents the probability for the bigram "i like" we just computed. Notice that we have zero probabilities here since the counts for bigram such as "i i", "i story", and "story story" are $0$. While this seems reasonable here, our model is likely to contain zero probabilities for many bigrams that might occur in a text, even if they did not in the training dataset; hence, the idea of smoothing.
So let's look at the same values but now for the bigram language model with Laplace smoothing. Of course, since the smoothing is applied when computing the probabilities, the actual counts are the same in both models with and without smoothing. However, we can conceptually show what Laplace smoothing is doing by adding $1$ to each count.
(df_unsmoothed_bigram_counts + 1)
| i | like | the | story | |
|---|---|---|---|---|
| i | 1 | 276 | 14 | 1 |
| like | 187 | 4 | 858 | 3 |
| the | 10 | 24 | 55 | 1848 |
| story | 9 | 14 | 7 | 1 |
The most obvious observation is that we now no longer have any zero counts which implies that we will also not have zero probabilities. Let's compute and have a look at all the bigram probabilities for the bigram language model with Laplace smoothing; we need to increase the precision to see that some of the probabilities are indeed greater than $0$.
df_smoothed_bigram_probs, _ = generate_bigram_data(ngram_lm2_smoothed, tokens, mode='probs', decimals=6)
df_smoothed_bigram_probs
| i | like | the | story | |
|---|---|---|---|---|
| i | 0.000011 | 0.003065 | 0.000155 | 0.000011 |
| like | 0.003017 | 0.000065 | 0.013845 | 0.000048 |
| the | 0.000054 | 0.000130 | 0.000299 | 0.010036 |
| story | 0.000158 | 0.000245 | 0.000123 | 0.000018 |
Once again, we see that now the bigram probability $P(\text{"like"}, \text{"i"})$ dropped down to $0.0031$, less than half the value compared to the model without smoothing. And this is not really an exception. If you compare the matching probabilities for both models, you will notice that the probabilities of existing bigrams can change quite a bit. This shows the phenomenon that smoothing might shift too much probability mass from known to unknown bigrams (or $n$-grams, in general).
The easiest solution given our implementation is to reduce the smoothing factor $k$ from Laplace smoothing ($k=1$) to the generalized Add-$k$ smoothing and picking a value smaller than one. To this end, the code cell below trains another bigram language model on the same dataset but now with $k=0.1$.
ngram_lm2_smoothed = NGramLanguageModel(N=2, k=0.1, lowercase=True)
ngram_lm2_smoothed.train(sentences)
100%|██████████████████████████████████████████████████████████████████████████████████████████████| 135677/135677 [00:25<00:00, 5326.39it/s]
And let's print the new bigram probabilities again.
df_smoothed_bigram_probs, _ = generate_bigram_data(ngram_lm2_smoothed, tokens, mode='probs', decimals=6)
df_smoothed_bigram_probs
| i | like | the | story | |
|---|---|---|---|---|
| i | 0.000002 | 0.006483 | 0.000309 | 0.000002 |
| like | 0.012969 | 0.000216 | 0.059730 | 0.000146 |
| the | 0.000067 | 0.000169 | 0.000396 | 0.013531 |
| story | 0.000853 | 0.001380 | 0.000642 | 0.000011 |
Unsurprisingly, these probabilities are now more similar to the ones for the model without smoothing.
While reducing $k$ to lower the effect of shifting probability mass from known to unknown bigrams, basic strategies such as Add-$k$ smoothing do not address the equal probability fallacy. This requires more sophisticated smoothing strategies such as Kneser-Ney smoothing which are beyond the scope of this notebook.
Output Quality¶
Although $n$-gram language models are not typically used for text generation in practical applications, generating sample text from models with different $n$-gram sizes can provide valuable qualitative insight into their behavior and quality. By examining the generated output, one can observe how increasing the context size generally improves local coherence and grammaticality, while also revealing limitations such as repetition, sparsity, or overfitting to training sequences. These examples complement quantitative evaluation metrics by offering an intuitive understanding of how effectively each model captures patterns in the underlying language data.
Let's start by using the trained bigram model with Add-$k$ smoothing. In the code cell below, we call the generate() five times using the same start context "the movie was" to let the model generate an output text. Keep in mind that, since we have a bigram model, the first word the model will pick depends only on "was"!
for _ in range(5):
print(ngram_lm2_smoothed.generate(start_context=["the", "movie", "was"], topk=10))
the movie was so bad it was not to be the only for the same time i am not only a few minutes , the movie . the movie was so - to be . the movie was the plot of the movie is the movie is a little more than a lot of the first . the movie was the same thing . the movie was not a great , it a very disappointed that 's not the same time on a few good thing to be the movie .
The results are arguably pretty bad. However, this should not be that surprising. After all, we condition the next word only on the single preceding word. So let's see how a trigram model will do by training one using the same dataset and the same preprocessing steps; notice that we also lower the smoothing factor $k$ to $k=0.1$ to reduce the potential effects of moving too much probability mass.
ngram_lm3_smoothed = NGramLanguageModel(N=3, k=0.1, lowercase=True)
ngram_lm3_smoothed.train(sentences)
100%|██████████████████████████████████████████████████████████████████████████████████████████████| 135677/135677 [00:29<00:00, 4559.99it/s]
Once again, we can use the same start context to let the model generate a few example outputs. Now that we are using the trigram model, the first predicted word will depend on the context "movie was".
for _ in range(5):
print(ngram_lm3_smoothed.generate(start_context=["the", "movie", "was"], topk=10))
the movie was so bad i would not have to say . the movie was so bad i was watching this piece of crap . the movie was just a bunch of people who have seen . the movie was so bad it 's a good one . the movie was .
Unsurprisingly, the results are still far away from proper English sentences — and again, this is not really the expectation when using $n$-gram language models. However, overall, the generated sentences for the trigram model "look" better than the ones for the bigram model. This obviously motivates us to train a $4$-gram language model to see if there are further improvements.
ngram_lm4_smoothed = NGramLanguageModel(N=4, k=0.1, lowercase=True)
ngram_lm4_smoothed.train(sentences)
100%|██████████████████████████████████████████████████████████████████████████████████████████████| 135677/135677 [00:34<00:00, 3961.53it/s]
for _ in range(5):
print(ngram_lm4_smoothed.generate(start_context=["the", "movie", "was"], topk=10))
the movie was made during the last ones . the movie was that the film has two of the most boring movie i have ever seen . the movie was the fact that the movie is the worst movie ever made , and one of the worst movies ever made . the movie was made , portraying this woman 's clinic and she wants an abortion and all , but i do n't know what the hell was that ? the movie was not that bad , and the acting is n't too impressive .
And indeed, the results of the $4$-gram model look even better, which should not really be a big surprise. However, keep in mind that increasing the size of the $n$-grams further and further would mean that it would become more and more likely that we generate the same text for the same start context. This is because the larger the $n$-grams the less known $n$-grams of that size do we have. Also, remember that we "cheat" a little bit by considering only words we have seen at least once for a given context (instead of all words in the vocabulary).
Summary¶
This notebook introduced $n$-gram language models from both a theoretical and a practical perspective. We explored the fundamental idea that the probability of a word can be approximated using only a limited context of preceding words, leading to unigram, bigram, trigram, and higher-order models. The notebook also demonstrated how these probabilities can be estimated from text corpora and how $n$-gram models can be implemented efficiently in code.
Historically, $n$-gram language models played a central role in the development of natural language processing and speech recognition. Long before the emergence of neural networks and large language models, $n$-gram approaches provided a practical and effective framework for modeling language. Their simplicity and solid probabilistic foundations made them one of the most influential techniques in early statistical NLP, and many concepts introduced by $n$-gram models continue to inform modern language modeling methods.
The practical exercises highlighted both the strengths and limitations of $n$-gram models. While generated text can become more coherent as the $n$-gram size increases, these models struggle to capture long-range dependencies and suffer from data sparsity when the context becomes too large. For this reason, $n$-gram models are rarely used today as standalone text generators. Nevertheless, examining generated samples remains a useful way to gain intuition about how context length affects model behavior and language quality.
Despite being surpassed by modern neural architectures for many tasks, $n$-gram language models remain valuable tools. Their main advantages are their simplicity, transparency, and ease of training. Unlike many contemporary models, $n$-gram models are straightforward to interpret because the learned probabilities directly reflect patterns observed in the training data. They also remain useful for comparing alternative text sources, corpora, or domains, where interpretable probability estimates and lightweight computation are often more important than state-of-the-art text generation performance.