N-gram Language Models

It assigns a probability to each possible next word (a probability distribution over next words), and can also assign a probability to an entire sentence or word sequence.

Large language models are built just by training them to predict words. Word probabilities also help directly: correcting grammar or spelling (There are beats Their are), speech recognition (back soonish beats bassoon dish), and word suggestions in augmentative and alternative communication (AAC).

An n-gram is a sequence of n words (bigram: “water of”; trigram: “water of Walden”). An n-gram model is a probabilistic model that estimates the probability of a word given the previous n−1 words, and thereby of whole sequences.

Training and test sets, perplexity, sampling, and smoothing/interpolation: all of which carry over to neural LLMs.

Language is creative: most long histories (whole sentences) never occur, or occur too rarely, even on the entire web, so the counts are zero or unreliable.

The sequence \(w_1, w_2, \ldots, w_{n-1}\): all words before \(w_n\).

\(P(w_{1:n}) = P(w_1)P(w_2 \mid w_1)P(w_3 \mid w_{1:2})\cdots P(w_n \mid w_{1:n-1}) = \prod_{k=1}^{n} P(w_k \mid w_{1:k-1})\)

It turns the joint probability into a product of conditional probabilities, but we still have no way to estimate \(P(w_n \mid w_{1:n-1})\) for long histories.

\(P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-1})\): e.g. P(blue | The water of Walden Pond is so beautifully) ≈ P(blue | beautifully).

That the probability of a future unit depends only on a limited recent past (for a bigram, only the previous word), not on the whole history.

\(P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-N+1:n-1})\): condition only on the previous \(N-1\) words.

\(P(w_{1:n}) \approx \prod_{k=1}^{n} P(w_k \mid w_{k-1})\)

Get counts from a corpus and normalize them to lie between 0 and 1 (dividing by a total count so they sum to 1). The resulting parameters maximize the likelihood of the training set.

\(P(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n)}{C(w_{n-1})}\). The sum of counts of all bigrams starting with \(w_{n-1}\) equals the count of \(w_{n-1}\) itself.

<s> gives the first word a context. </s> makes the model a true probability distribution over sentences of all lengths; without it, probabilities would sum to one separately for each sentence length.

P(I | <s>) = 2/3 ≈ .67 (two of three sentences start with I); P(am | I) = 2/3 ≈ .67 (I occurs 3 times, twice followed by am); P(Sam | am) = 1/2 (am occurs twice, once followed by Sam).

\(P(w_n \mid w_{n-N+1:n-1}) = \frac{C(w_{n-N+1:n-1}\, w_n)}{C(w_{n-N+1:n-1})}\)

The observed frequency of a sequence divided by the observed frequency of its prefix: the MLE estimate.

400/1,000,000 = .0004. It isn’t the best estimate for every context, but it is the probability that makes 400 occurrences in a million words most likely.

Most cells are zero: n-gram counts are very sparse.

Multiply the bigram probabilities: P(i | <s>) · P(want | i) · P(english | want) · P(food | english) · P(</s> | food).

Syntactic facts (after eat comes a noun or adjective; after to, a verb), task facts (assistant queries often start with I), and even cultural facts (people ask for Chinese food more than English food).

Multiplying many probabilities ≤ 1 causes numerical underflow. Adding logs is equivalent to multiplying: \(p_1 p_2 p_3 = \exp(\log p_1 + \log p_2 + \log p_3)\).

With extra pseudo-words: the first trigram uses two start symbols, e.g. P(I | <s> <s>).

n-grams of any length, computed quickly at inference time from enormous corpora using suffix arrays, instead of precomputing huge count tables.

Quantizing probabilities to 4–8 bits, storing words as 64-bit hashes, special data structures like reverse tries, pruning (count thresholds or entropy-based pruning), and toolkits like KenLM that use sorted arrays and merge sorts.

Extrinsic (end-to-end) evaluation embeds the model in an application and measures how much the application improves: the only real proof. Intrinsic evaluation measures model quality independently of any application (e.g. perplexity): cheaper and faster.

A training set (to learn parameters), a development set (devset, for testing during development), and a test set (held out for final evaluation).

To get an unbiased estimate of how well the model generalizes to new data; a model that fits the training data perfectly may perform terribly elsewhere.

It should reflect the language the model will be used for (chemistry lectures, hotel booking requests…). For a general-purpose model, draw it from a wide variety of texts, not one document or author.

The one that assigns the higher probability to the test set, i.e. predicts it more accurately.

Letting test sentences into the training data. They get artificially high probabilities, making perplexity look much better than it really is.

Testing repeatedly on the test set while making changes implicitly tunes the model to it. So we do all testing on the devset and touch the test set only once, at the end.

Large enough to have the statistical power to detect a significant difference between models (but leaving as much as possible for training). The devset must be the same kind of text as the test set.

It depends on length: the longer the text, the smaller its probability. We want a per-word metric normalized by length.

The inverse probability of the test set, normalized by the number of words: \(\text{PP}(W) = P(w_1 \ldots w_N)^{-1/N} = \sqrt[N]{\frac{1}{P(w_1 \ldots w_N)}}\).

Lower. Because of the inverse, higher test-set probability means lower perplexity; minimizing perplexity is maximizing test-set probability.

Unigram: \(\sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i)}}\). Bigram: \(\sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i \mid w_{i-1})}}\). Both are geometric means of inverse probabilities.

Include </s> but not <s>: the end token is followed by a start token with probability ≈ 1, so that fake transition shouldn’t affect perplexity.

It drops sharply: longer contexts give more information about the next word, so the model is less surprised and assigns higher probability to the test text.

The models must be built without knowledge of the test set, and must use identical vocabularies.

No. It usually correlates with extrinsic improvements, so it is a convenient metric, but gains should be confirmed with end-to-end evaluation on a real task.

The branching factor is the number of possible next words. A uniform LM over 3 colors has perplexity 3 on any test set. If one color is very likely (P(red) = .8), the branching factor is still 3 but the perplexity on mostly-red text drops (≈ 1.89): it is a probability-weighted branching factor.

\(\big((1/3)^5\big)^{-1/5} = 3\).

Generate sentences by choosing them according to their probability under the model. It visualizes what knowledge the model embodies (a technique going back to Shannon and to Miller & Selfridge).

Lay out all words on the interval [0, 1], each covering a length equal to its probability. Pick a random number, output the word whose interval contains it, and repeat until </s> is generated.

Draw a random bigram starting with <s> according to its probability; say its second word is \(w\). Then draw a bigram starting with \(w\), and so on until </s>.

The probabilities encode specific facts of the training corpus, and higher-order n-grams model the training corpus better and better.

Unigram: no coherence or sentence ends. Bigram: some local word-to-word coherence. Trigram: starting to sound like Shakespeare. 4-gram: too much like Shakespeare, reproducing lines verbatim (“It cannot be but so”).

The corpus is tiny relative to the space of n-grams (\(V^4\) possible 4-grams), so the matrices are extremely sparse: after a given 3-word context there are only a handful of possible next words.

Both produce English-like sentences, but there is almost no overlap even in short phrases: statistical models are nearly useless if training and test text are as different as Shakespeare and the WSJ.

Use a training corpus of similar genre to the task (legal documents for legal translation, questions for QA) and in the appropriate dialect or variety (e.g. AAE features like finna or den; Nigerian Pidgin tweets).

Words can be unseen, but LMs run on subword tokens (e.g. BPE): any word can be built from known subwords, down to single letters, so the test set never contains unseen tokens.

n-grams that never occur in training but appear in the test set (“ruby slippers”). They make us underestimate plausible sequences, and if any word has probability 0 the whole test set has probability 0, so perplexity can’t be computed (division by zero).

Shaving some probability mass off frequent events and giving it to unseen events, so no plausible n-gram gets zero probability.

Add one to every count and adjust the denominator by the vocabulary size \(V\): \(P_{\text{Laplace}}(w_i) = \frac{c_i + 1}{N + V}\).

\(P(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n) + 1}{C(w_{n-1}) + V}\). The denominator is really a sum over all \(V\) bigrams starting with \(w_{n-1}\), each of which got +1.

As a baseline that introduces smoothing concepts, and as a practical smoothing method for other tasks like text classification.

The count that, divided by the original unsmoothed denominator \(C(w_{n-1})\), gives the smoothed probability: \(C^* = \frac{[C(w_{n-1} w_n) + 1]\, C(w_{n-1})}{C(w_{n-1}) + V}\). It shows how much smoothing changed the counts.

It moves far too much probability mass to all the zeros, drastically discounting seen n-grams (e.g. the count of “want to” drops from 608 to 238, and some discounts are 10× larger than others).

Add a fractional count \(k\) (e.g. 0.5, 0.01) instead of 1: \(P = \frac{C(w_{n-1} w_n) + k}{C(w_{n-1}) + kV}\). \(k\) is tuned on a devset. It still works poorly for language modeling (poor variances, inappropriate discounts).

Less context generalizes better: with no examples of a trigram, use the bigram probability; with no bigram counts, use the unigram.

Mixing n-gram orders with weights that sum to 1: \(\hat{P}(w_n \mid w_{n-2} w_{n-1}) = \lambda_1 P(w_n) + \lambda_2 P(w_n \mid w_{n-1}) + \lambda_3 P(w_n \mid w_{n-2} w_{n-1})\).

Each \(\lambda\) depends on the preceding context \(w_{n-2:n-1}\), so trigrams built on well-attested bigrams can get more weight.

On a held-out corpus: fix the n-gram probabilities and choose the \(\lambda\)s that maximize the held-out likelihood, e.g. with the EM algorithm.

Additional data held out from training, used to set hyperparameters such as interpolation weights rather than regular counts.

Backoff uses only the highest-order n-gram with nonzero counts, backing off to the (n−1)-gram only when the count is zero. Interpolation always mixes all orders. A correct backoff model must discount higher-order n-grams to reserve mass for lower orders.

A simple non-discounted backoff (Brants et al., 2007): if the n-gram count is positive use its relative frequency, otherwise use \(\lambda\) (about 0.4) times the backed-off score, ending in \(\text{count}(w)/N\). It doesn’t produce a true probability distribution, so it is written \(S\) rather than \(P\).

\(H(X) = -\sum_{x} p(x)\log_2 p(x)\), measured in bits with log base 2. It is a lower bound on the average number of bits needed to encode outcomes in an optimal code.

With probabilities ½, ¼, ⅛, 1/16 and four horses at 1/64, the entropy is 2 bits: give probable horses short codes (0, 10, 110, …) and improbable ones long codes. With equally likely horses the entropy is \(\log_2 8 = 3\) bits.

The per-word entropy in the limit of infinitely long sequences: \(H(L) = \lim_{n\to\infty} \frac{1}{n} H(w_{1:n})\).

For a stationary and ergodic process, estimate the entropy rate from a single long-enough sequence: \(H(L) = \lim_{n\to\infty} -\frac{1}{n}\log p(w_{1:n})\), instead of summing over all sequences.

One whose probabilities are invariant to shifts in the time index. n-gram (Markov) models are stationary; natural language is not, since upcoming words can depend on arbitrarily distant context. So our entropy estimates are approximations.

\(H(p, m)\): the entropy of data drawn from the true distribution \(p\) measured with log probabilities from a model \(m\). We can estimate it from a long sample, \(-\frac{1}{n}\log m(w_{1:n})\), without knowing \(p\).

\(H(p) \le H(p, m)\) for any model \(m\): cross-entropy is an upper bound. The more accurate the model, the closer the bound; between two models, the one with lower cross-entropy is better.

\(\text{Perplexity}(W) = 2^{H(W)}\), where \(H(W) = -\frac{1}{N}\log_2 P(w_1 \ldots w_N)\). This equals \(P(w_1 \ldots w_N)^{-1/N}\), which explains the inverse probability.

Andrey Markov (1913), who used Markov chains to predict whether the next letter in Pushkin’s Eugene Onegin would be a vowel or a consonant.

That finite-state Markov processes, whatever their engineering use, cannot be a complete cognitive model of grammatical knowledge. It led many linguists to ignore statistical modeling for decades.

From speech recognition at IBM (Fred Jelinek and colleagues) and at CMU (James Baker, building on declassified work by Leonard Baum). The IBM group coined both terms.

Modified Interpolated Kneser-Ney, following Chen & Goodman’s careful comparisons.

(1) Parameters grow exponentially with n-gram order; (2) n-grams can’t generalize between training and test examples unless the words are identical. Neural LMs map words into a continuous space where words in similar contexts get similar representations.