N-gram Language Models

A language model (LM) is a probability distribution over sequences of words. For a sentence $W = w_1 w_2 \cdots w_T$, the model assigns $P(W)$, and by the chain rule of probability this factors exactly as

This factorization is exact — no assumption yet — but it is useless in practice because the conditioning context $w_1, \dots, w_{i-1}$ grows without bound, and no corpus is large enough to have seen every possible long history even once. Estimating $P(w_i \mid w_1, \dots, w_{i-1})$ directly from counts would require the exact prefix to have occurred before in training data, which becomes vanishingly likely as $i$ grows. The n-gram model resolves this with the Markov assumption: the probability of the next word depends only on the previous $n-1$ words, not the entire history.

An n-gram itself is simply a contiguous sequence of $n$ tokens. A unigram model ($n=1$) assumes words are independent; a bigram model ($n=2$) conditions on one previous word; a trigram model ($n=3$) conditions on two. The name is a slight misnomer in common usage: "bigram model" refers to a model that uses two-word windows to estimate one-word-ahead conditional probabilities, i.e., it conditions on a history of $n-1$ words. Combining the chain rule with the Markov approximation gives the full sentence probability under an n-gram model:

where $w_{i-n+1}^{i-1}$ denotes the shorthand for the $(n-1)$-word history. Sentences are typically padded with special boundary tokens `` (start) and `` (end) so that the model can assign probability to the first few words and learn when a sentence is likely to terminate. The remaining question is how to obtain the conditional probabilities $P(w_i \mid \text{history})$. This is where maximum-likelihood estimation (MLE) enters: count how often the history is followed by each candidate word in a training corpus, and normalize.

Step 1 — Preprocessing. Tokenize the corpus (this is assumed prior knowledge; see Text Preprocessing and Tokenization), and wrap each sentence with $n-1$ start markers `` and one end marker ``. This padding ensures every position has a well-defined history and that sentence-ending behavior is itself learned.

Step 2 — Counting. Scan the corpus once and count every n-gram occurrence, and every $(n-1)$-gram (context) occurrence. These counts are stored in a hash map or trie keyed by the token tuple.

Step 3 — Estimation (MLE). The maximum-likelihood estimate of a bigram probability is the relative frequency of the bigram among all bigrams sharing that history:

Generalizing to arbitrary $n$:

Here $C(\cdot)$ denotes raw count in the training corpus. This is literally "count and divide" — no iterative optimization is needed because the log-likelihood of the training data is maximized in closed form by relative frequencies (shown in Complexity & correctness below).

Step 4 — Scoring a new sentence. To compute the probability (or, more commonly, the log-probability, to avoid numerical underflow from multiplying many small numbers) of a new sentence, slide an $n$-word window across it and multiply the per-position conditional probabilities looked up from the count tables.

Step 5 — Handling unseen n-grams. If a test n-gram was never observed in training, $C(\cdot) = 0$, and the MLE probability is exactly zero — collapsing the entire sentence probability to zero regardless of how plausible the rest of the sentence is. This is the central weakness of pure MLE n-grams and is the reason smoothing techniques (Laplace, Kneser-Ney, back-off) exist; those are developed as their own topic, but the pseudocode below flags exactly where they intervene. ```

# ---- TRAINING ---- function TRAIN_NGRAM(corpus, n): ngram_counts = empty hash map # maps (w_{i-n+1}, ..., w_i) -> count context_counts = empty hash map # maps (w_{i-n+1}, ..., w_{i-1}) -> count for sentence in corpus: tokens = [] * (n - 1) + tokenize(sentence) + [] for i from (n - 1) to length(tokens) - 1: ngram = tokens[i - n + 1 .. i] # length-n tuple context = tokens[i - n + 1 .. i - 1] # length-(n-1) tuple ngram_counts[ngram] += 1 context_counts[context] += 1 return ngram_counts, context_counts

# ---- PROBABILITY OF ONE NEXT WORD ---- function PROB(word, context, ngram_counts, context_counts, V): ngram = context + (word,) if context_counts[context] == 0: return UNDEFINED # never-seen context; hand off to smoothing/back-off if ngram_counts[ngram] == 0: return 0.0 # MLE gives zero probability -- the sparsity problem return ngram_counts[ngram] / context_counts[context]

# ---- SCORING A FULL SENTENCE ---- function SENTENCE_LOGPROB(sentence, n, ngram_counts, context_counts): tokens = [] * (n - 1) + tokenize(sentence) + [] logP = 0.0 for i from (n - 1) to length(tokens) - 1: context = tokens[i - n + 1 .. i - 1] word = tokens[i] p = PROB(word, context, ngram_counts, context_counts, V=vocab_size) if p == 0.0 or p == UNDEFINED: return -infinity # whole sentence assigned zero probability logP += log(p) return logP

# ---- GREEDY / SAMPLING GENERATION ---- function GENERATE(n, ngram_counts, context_counts, max_len): context = (,) * (n - 1) output = [] repeat max_len times: w = argmax_or_sample over vocabulary V of PROB(w, context, ...) if w == : break output.append(w) context = (context[1:] + (w,)) # slide the window forward return output ``` The two hash maps (`ngram_counts`, `context_counts`) are the entire model — there is no training loop, no gradient descent, no iteration to convergence. This is one of the appeals of the classical approach: training is a single linear pass over the corpus.

Time complexity. Training scans the corpus once: for a corpus of $T$ total tokens, building the count tables takes $O(T)$ time (assuming $O(1)$ amortized hash-map insert/increment). Scoring a sentence of length $L$ takes $O(L)$ lookups, each $O(1)$ amortized. This is asymptotically optimal: any language model must at minimum read every token of the sentence once.

Space complexity. In the worst case the number of distinct n-grams is $O(T)$ (every window is unique), but in practice with natural language's Zipfian structure the number of distinct n-grams is much smaller and grows sublinearly after the vocabulary saturates. Space is $O(\text{number of distinct n-grams and contexts observed})$, which grows with both corpus size and $n$: larger $n$ means exponentially more possible distinct windows ($|V|^n$ in principle), so storage and sparsity both worsen as $n$ increases. This tension — bigger context window vs. exploding parameter count — is the central engineering tradeoff of n-gram modeling.

Why MLE is the "correct" estimator here. Given a fixed context $c$, let $n_1, \dots, n_k$ be the counts of each vocabulary word following $c$ in the training data, with $N = \sum_j n_j$. We want probabilities $p_1, \dots, p_k$ (with $\sum p_j = 1$) that maximize the likelihood of the observed continuations, i.e., maximize $\prod_j p_j^{n_j}$, equivalently maximize $\sum_j n_j \log p_j$ subject to $\sum_j p_j = 1$. Using a Lagrange multiplier $\lambda$:

Summing both sides over $j$ and using $\sum_j p_j = 1$ gives $\lambda = N$, so $p_j = n_j / N$ — exactly the relative-frequency count. This proves that the count-and-divide rule is not an ad hoc heuristic but the unique maximizer of the training-data log-likelihood under the categorical (multinomial) model implicit in the n-gram assumption. It is correct in the narrow but precise sense of being the maximum-likelihood estimator for this model class.

The correctness caveat — generalization, not fit. MLE guarantees the best possible fit to the training data, not good behavior on unseen data. Any n-gram absent from training receives probability exactly zero, which is provably too pessimistic: absence of evidence is not evidence of impossibility. This is why n-gram models are always paired with a smoothing method in practice; MLE is correct as an in-sample optimizer but systematically miscalibrated out-of-sample, an issue formalized and measured via Perplexity on held-out data. That pairing (MLE counts + smoothing) is covered under Smoothing for Language Models.

Markov assumption validity. The approximation $P(w_i \mid w_1^{i-1}) \approx P(w_i \mid w_{i-n+1}^{i-1})$ is exact only if the true generative process for language were actually a finite-order Markov chain — it is not; long-range syntactic and discourse dependencies exist (subject-verb agreement across clauses, pronoun coreference many sentences later). The assumption is a deliberate bias-variance tradeoff: it sacrifices some modeling fidelity (bias) in exchange for the ability to estimate parameters reliably from finite data (variance reduction). Larger $n$ reduces bias but increases variance (more parameters, sparser counts per parameter) — a textbook bias–variance tradeoff instantiated in an NLP setting.

Consider this toy training corpus of three sentences (already tokenized, lowercase): ``` I am Sam Sam I am I do not like green eggs ``` We train a bigram model. First tally the counts $C(w_{i-1}, w_i)$ and context counts $C(w_{i-1})$:

Now score the new sentence ` I am Sam ` (it happens to appear verbatim in training, chosen deliberately so we can sanity-check against the counts):

Now try a novel sentence: ` I like eggs `. Every bigram it needs — (I, like), (like, eggs) — was never observed jointly in training (we only saw I am, I do, not like, green eggs). Look up $C(\text{I},\text{like})$: it is 0, so $P(\text{like}\mid\text{I}) = 0$, and the entire sentence probability collapses to exactly zero — even though "I like eggs" is a perfectly ordinary English sentence and every individual word appears in training. This starkly demonstrates the sparsity problem flagged above: MLE n-grams cannot generalize past exact substrings seen during training, which is precisely the gap that additive smoothing, back-off, and interpolation (Kneser-Ney) are designed to close.

The mathematical seed of the n-gram idea predates computing entirely: it comes from the theory of stochastic processes with limited memory.

N-gram language models were, for decades, the statistical backbone of speech recognition (scoring candidate transcriptions for fluency), statistical machine translation (favoring fluent target-language output), spelling and grammar correction (flagging low-probability word sequences), and predictive text / autocomplete on early mobile keyboards. Search engines used n-gram statistics for query completion and did-you-mean suggestions. Information-retrieval systems used n-gram overlap for text similarity and plagiarism detection. Even though large neural language models have superseded n-grams for state-of-the-art generation quality, n-grams remain in active use: as fast, cheap baselines; inside evaluation metrics like BLEU and ROUGE (which compare n-gram overlap between generated and reference text); in lightweight on-device applications where a neural model is too large or slow; and in smoothing/back-off techniques that continue to be studied as interpolation weights in hybrid neural-statistical systems. Conceptually, every autoregressive neural language model — including GPT-style transformers — is still factoring sentence probability via the same chain rule that opens this article; only the conditional probability estimator has changed, from counting to a deep network. Understanding n-grams gives you, essentially for free, the probabilistic scaffolding underneath every modern LM, and sets up the two natural next questions: how do we fix the zero-probability problem (see Smoothing for Language Models), and how do we numerically compare two language models' quality (see Perplexity).

Ask the tutor: How does add-one (Laplace) smoothing modify the MLE formula to avoid zero probabilities, and what problems does that fix introduce in turn?