Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

N-gram Language Models › The Language Modeling Problem

Michael BrenndoerferMarch 23, 20256 min read

Language AI HandbookAll chapters

Part 2 of 67Classical Text Representations

Chapter 8N-gram Language Models › The Language Modeling Problem

Reading section 2 of 15 · The Language Modeling Problem · 6 minSection 2 of 15 · 6 min

Section 2 of 15 · 6 min read

N-gram Language Models › The Language Modeling ProblemOne section · Sections in this chapter2 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

A language model assigns probabilities to sequences of words. Given a sequence of $n$ words, denoted $w_1, w_2, \ldots, w_n$ , the model estimates $P(w_1, w_2, \ldots, w_n)$ , the probability of that exact sequence occurring in natural language. Here $w_i$ represents the $i$ -th word in the sequence. For example, $w_1$ might be "the" and $w_2$ might be "cat."

Language Model

A language model is a probability distribution over sequences of words. It assigns higher probabilities to sequences that are more likely to occur in natural language and lower probabilities to unlikely or ungrammatical sequences.

Why is assigning probabilities to word sequences useful? The applications are remarkably broad.

Disambiguation. A speech recognition system hears an ambiguous audio signal. It might produce two candidate transcriptions: "I saw a van" and "eyes awe of an." A language model knows the first sequence is far more probable and helps the system choose correctly. The acoustic model tells you what sounds were produced; the language model tells you which word sequence those sounds most plausibly correspond to.

Ranking. A machine translation system generates dozens of candidate translations for a source sentence. A language model scores each candidate by how natural it sounds in the target language, allowing the system to prefer fluent output over grammatically awkward but technically accurate alternatives.

Generation. If we can compute $P(w_1, \ldots, w_n)$ for any sequence, we can generate new text by sampling words according to their probabilities given the preceding context. Start from the beginning of a sentence, pick the next word proportionally to its probability, advance the window, and repeat. This same generation mechanism, refined and scaled enormously, underlies modern large language models like GPT-4.

Evaluation. A language model provides a principled way to measure how "natural" a corpus is. Lower perplexity under the model means the text fits the learned distribution more closely, which makes language models useful for detecting out-of-domain text, machine-generated content, or low-quality data.

The Chain Rule of ProbabilityLink Copied

Computing the probability of a full sequence seems daunting at first. How could we possibly estimate $P(\text{"the cat sat on the mat"})$ directly? We would need to count how often this exact six-word sequence appears in training data, then divide by the total number of six-word sequences. But most sentences are unique. Even in a corpus of billions of words, we are unlikely to see any specific sentence more than a handful of times. For longer sentences, the chance of observing a particular sequence approaches zero.

The chain rule of probability offers an escape from this dilemma. Instead of estimating the joint probability directly, we decompose it into a product of conditional probabilities. Each conditional probability asks a simpler question: given everything that came before, how likely is the next word?

The chain rule derives from the definition of conditional probability. Conditional probability is defined as:

P(A|B) = \frac{P(A, B)}{P(B)}

where:

$P(A|B)$ : the probability of event $A$ occurring given that event $B$ has already occurred
$P(A, B)$ : the joint probability of both $A$ and $B$ occurring together
$P(B)$ : the probability of event $B$ occurring, serving as the normalizing denominator

Rearranging gives the multiplication rule: $P(A, B) = P(B) \times P(A|B)$ . The probability of both events equals the probability of the first event times the probability of the second event given the first. For a sequence of words, we apply this rule repeatedly to break down the joint probability into simpler conditional probabilities.

Step 1: Start with the joint probability of all words:

P(w_1, w_2, \ldots, w_n)

Step 2: Apply the multiplication rule to separate the last word, treating "all words up to $w_{n-1}$ " as event $B$ and " $w_n$ appears next" as event $A$ :

P(w_1, \ldots, w_n) = P(w_1, \ldots, w_{n-1}) \times P(w_n|w_1, \ldots, w_{n-1})

Step 3: Apply the same rule recursively to $P(w_1, \ldots, w_{n-1})$ , peeling off one word at a time, until only $P(w_1)$ remains:

\begin{aligned} P(w_1, w_2, \ldots, w_n) &= P(w_1) \times P(w_2|w_1) \times P(w_3|w_1, w_2) \times \cdots \times P(w_n|w_1, \ldots, w_{n-1}) \end{aligned}

Using product notation, this is written compactly as:

P(w_1, \ldots, w_n) = \prod_{i=1}^{n} P(w_i|w_1, \ldots, w_{i-1})

where:

$w_i$ : the $i$ -th word in the sequence
$P(w_i|w_1, \ldots, w_{i-1})$ : the conditional probability of word $w_i$ given all preceding words, the "history"
$\prod_{i=1}^{n}$ : the product operator, which multiplies all $n$ terms together

The probability of a sequence equals the probability of the first word, times the probability of the second word given the first, times the probability of the third word given the first two, and so on. Each step conditions on all previously observed words.

This decomposition is mathematically exact, not an approximation. The chain rule holds for any joint distribution, regardless of how complex the dependencies between words are.

Let us see this decomposition in action with a concrete example:

In[3]:

Code

# Illustrate the chain rule decomposition
sentence = "the cat sat on the mat"
words = sentence.split()

# The chain rule breaks the joint probability into conditional probabilities
decomposition = []
for i, word in enumerate(words):
    if i == 0:
        term = f"P({word})"
    else:
        context = " ".join(words[:i])
        term = f"P({word}|{context})"
    decomposition.append(term)

Out[4]:

Console

Sentence: "the cat sat on the mat"

Chain rule decomposition:
P(the cat sat on the mat) =
    P(the)
  x P(cat|the)
  x P(sat|the cat)
  x P(on|the cat sat)
  x P(the|the cat sat on)
  x P(mat|the cat sat on the)

Each term in this product answers a progressively more specific question. The first asks: how likely is "the" to start a sentence? The second asks: given we started with "the," how likely is "cat" to follow? By the time we reach the final word, we are asking: given the entire context "the cat sat on the," how likely is "mat"?

The chain rule is mathematically exact, but it creates a severe practical problem. To compute $P(w_n|w_1, \ldots, w_{n-1})$ , we need the probability of word $w_n$ given the entire preceding context. For long sentences, this context can be arbitrarily long. A 20-word sentence requires estimating the probability of the 20th word given all 19 preceding words. We will never have enough training data to estimate these long-context probabilities reliably, since most 19-word contexts appear only once, if ever. The number of distinct 19-word contexts in any finite corpus is essentially as large as the corpus itself.

This is where the Markov assumption comes in.