Natural Language Processing · n-grams · Neural Language Models

§12.4 Natural language processing

Natural language processing (NLP) is the use of human languages by a computer — machine translation, question answering, and more. Most NLP rests on language models: a language model defines a probability distribution over sequences of tokens (words, characters, or bytes). Generic neural techniques apply, but scale demands specialization for sequential data — and, because the vocabulary is huge, word-based models must operate on an extremely high-dimensional, sparse discrete space.

§12.4.1 n-grams

The earliest successful language models are n-grams — a fixed-length sequence of $n$ tokens. An n-gram model defines the probability of a sequence as a product of conditionals, each on the previous $n-1$ tokens:

The n-gram decomposition (eq 12.5)

P(x_1,\dots,x_\tau) = P(x_1,\dots,x_{n-1})\prod_{t=n}^{\tau} P\!\big(x_t \mid x_{t-n+1},\dots,x_{t-1}\big)

$\prod_{t=n}^{\tau}$	chain rule of probability: the sequence probability is a product of one-step predictions	product
$P(x_t \mid x_{t-n+1},\dots,x_{t-1})$	each token conditions on ONLY the previous n−1 tokens — the n-gram (Markov) assumption	conditional
$P(x_1,\dots,x_{n-1})$	the opening tokens, handled by a smaller-n model	boundary

Training is just counting. Usually you keep both an $n$ -gram and an $(n{-}1)$ -gram model, so a conditional is a ratio of two stored counts — e.g. for the trigram “THE DOG RAN AWAY”:

$P(\text{THE DOG RAN AWAY}) = P_3(\text{THE DOG RAN})\,\frac{P_3(\text{DOG RAN AWAY})}{P_2(\text{DOG RAN})}$

But counting is brittle. Pick a context and watch what happens when it’s unseen — then turn on smoothing:

Fig (interactive) — a trigram model estimated by counting on a toy corpus. Unseen next-words get probability 0; an unseen context is undefined (−∞ log-likelihood). Add-α smoothing shifts mass to unseen words.

contextadd-α smoothing

Maximum-likelihood counts: only words seen after "the cat" get probability (pink); every other word gets exactly 0. On a huge vocabulary most n-grams are unseen, so raw counts are brittle — hence smoothing.

The zero-count catastrophe — an unseen tuple giving zero (or undefined) probability — forces every n-gram model to use smoothing (add-mass, back-off to lower-order models, or mixtures). Deeper still, n-grams suffer the curse of dimensionality: there are $|V|^n$ possible n-grams, so most never occur in training. An n-gram model is really a local, nearest-neighbor predictor (§5.11.2) — and in one-hot space every pair of words is equidistant, so only literal repeats of a context help. Class-based models cluster words to share strength, but lose much information.

§12.4.2 Neural language models

Neural language models beat the curse of dimensionality with a distributed representation — a word embedding for each word. Unlike a class-based model, they recognize that two words are similar without collapsing them into one class. Click a word to see its neighbors, and toggle to the one-hot baseline to feel the difference:

Fig 12.3 (interactive) — a learned word-embedding space. Semantically similar words (countries, numbers, animals) cluster together; one-hot vectors, by contrast, place every pair equidistant with no similarity structure.

Nearest neighbours of cat: dog, kitten, puppy — all in the same semantic neighbourhood. Because cat and its neighbours share learned features, a sentence about one informs predictions about the others, letting the model generalize to exponentially many similar sentences.

Why embeddings generalize exponentially

If dog and cat map to representations sharing many attributes, then a sentence containing cat informs the model’s predictions for sentences containing dog, and vice versa. Because there are many such shared attributes, each training sentence transfers information to an exponentially large number of semantically related sentences — directly countering the curse of dimensionality, which demands generalizing to a number of sentences exponential in their length. (Other domains have embeddings too — a CNN’s hidden layer is an “image embedding” — but NLP practitioners prize them most, because language doesn’t start in a real-valued vector space.)

Next: the flip side of a large vocabulary — the expensive softmax output layer, and the tricks that tame it — high-dimensional outputs and combining with n-grams.

Check yourself — n-grams and neural language models

1.What is a language model?

2.How does an n-gram language model work?

3.In the NGramLab, choosing an unseen context gives an undefined distribution. What is this problem and how is it addressed?

4.Why are classical n-gram models vulnerable to the curse of dimensionality?

5.How do neural language models overcome the curse of dimensionality? (See the WordEmbeddingLab.)

6.Why does a distributed (embedded) representation generalize so well?

6 questions