N-gram Language Models

While deep learning models excel at learning from raw features, they operate primarily on acoustic information. To help them make linguistically sound decisions, we introduce a statistical language model. The most fundamental type is the n-gram model, which calculates the probability of a sequence of words, $W$, by making a simplifying assumption about how words relate to each other.

Instead of trying to calculate the probability of a word given the entire history of all preceding words, a computationally intensive and data-demanding task, an n-gram model assumes that the probability of a given word only depends on the previous $n-1$ words. This is an application of the Markov assumption.

The Markov Assumption in Language

The full probability of a word sequence $W = (w_1, w_2, \dots, w_k)$ can be written using the chain rule of probability:

$$P(W) = P(w_1) P(w_2|w_1) P(w_3|w_1, w_2) \dots P(w_k|w_1, \dots, w_{k-1})$$

An n-gram model approximates this by limiting the context window. For a given $n$, the probability of a word $w_i$ is approximated as:

$$P(w_i | w_1, \dots, w_{i-1}) \approx P(w_i | w_{i-n+1}, \dots, w_{i-1})$$

Let's look at how this works for common values of $n$.

Unigrams (n=1)

The simplest model, a unigram model, assumes each word is independent of all others. The probability of a word is just its frequency in the training text.

• Assumption: $P(w_i | w_1, \dots, w_{i-1}) \approx P(w_i)$
• Sequence Probability: $P(\text{"wreck a nice beach"}) = P(\text{"wreck"}) \times P(\text{"a"}) \times P(\text{"nice"}) \times P(\text{"beach"})$

This is a "bag-of-words" approach. It completely ignores word order and context, making it too simplistic for generating coherent sentences. It cannot distinguish between "recognize speech" and "speech recognize".

Bigrams (n=2)

A bigram model is a significant step up. It assumes the probability of a word depends only on the single preceding word.

• Assumption: $P(w_i | w_1, \dots, w_{i-1}) \approx P(w_i | w_{i-1})$
• Sequence Probability: $P(W) \approx \prod_{i=1}^{k} P(w_i | w_{i-1})$ (where $w_0$ is a special start-of-sentence token).

Using our running example, a bigram model would evaluate:

• $P(\text{speech} | \text{recognize})$
• $P(\text{beach} | \text{nice})$

In a large corpus of English text, the phrase "recognize speech" is far more common than "wreck a nice", so the model correctly assigns a higher probability to the first transcription.

Trigrams (n=3)

A trigram model considers the two previous words, capturing more context.

• Assumption: $P(w_i | w_1, \dots, w_{i-1}) \approx P(w_i | w_{i-2}, w_{i-1})$

This allows the model to learn longer-range dependencies, like the fact that the phrase "a nice beach" is more probable than "a nice speech". As $n$ increases, the model can capture more context, but this comes at a cost. Higher-order n-gram models require much more training data and are more susceptible to issues we will discuss shortly. In practice, 3-gram and 4-gram models have historically provided a good balance for ASR systems.

Estimation from Text Corpora

N-gram probabilities are estimated directly from a large body of text called a corpus. The calculation is a straightforward application of Maximum Likelihood Estimation (MLE), which involves counting occurrences. For a bigram model, the conditional probability $P(w_i | w_{i-1})$ is estimated as:

$$P(w_i | w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i)}{\text{count}(w_{i-1})}$$

For example, to calculate $P(\text{speech} | \text{recognize})$, you would count every occurrence of the pair "recognize speech" in your corpus and divide it by the total number of times "recognize" appears.

The conditional probability of different words that might follow "recognize," based on a text corpus. A well-trained n-gram model assigns a significantly higher score to the linguistically plausible bigram "recognize speech" than to the improbable "recognize beach."

The Zero-Frequency Problem and Smoothing

A major challenge with n-gram models is data sparsity. What happens if a perfectly valid bigram, like "transcribe audio," never appeared in your training corpus? According to the formula, its count is zero, so its probability is zero.

$$P(\text{audio} | \text{transcribe}) = \frac{\text{count}(\text{"transcribe audio"})}{\text{count}(\text{"transcribe"})} = \frac{0}{\text{count}(\text{"transcribe"})} = 0$$

This is problematic. A single unseen n-gram would cause the probability of the entire sentence to become zero, forcing the decoder to discard it, even if the rest of the sentence is highly probable.

The solution is smoothing. Smoothing techniques take a small amount of probability mass from the n-grams we have seen and redistribute it to the n-grams we have not. This ensures that no n-gram has a probability of exactly zero.

A simple method is Laplace (or Add-1) smoothing, where we add one to all n-gram counts. However, more sophisticated techniques are used in practice. Modern toolkits like KenLM, which we will use in the next section, implement advanced smoothing algorithms like Kneser-Ney smoothing, which provides much better estimates for the probabilities of low-frequency and unseen n-grams.

By understanding these statistical foundations, you can appreciate how an n-gram LM provides the linguistic constraints needed to guide the decoder. In the next section, we will move from theory to practice and build our own n-gram model using a standard toolkit.