Natural Language Processing

Counting words in context

A language model defines a probability distribution over sequences of tokens. A token is a word, a character or a byte, and it is always discrete. The earliest successful language models were -gram models, which are fixed-length windows of tokens. The book writes a sequence probability as a product of conditional probabilities, which follows from the chain rule of probability. The first minus 1 tokens use a shorter model.

Training an -gram model is counting. The maximum likelihood estimate of the next token is the count of the whole window divided by the count of its context. The book writes this as the ratio in equation (12.6), and it is cheap because only two stored probabilities are needed.

Predict first.

Equation (12.7) shows the trigram case for a whole sentence. The book starts with the marginal probability of the first three words, because the first words have no full context. Then it uses the trigram for the last word and divides out the shared bigram.

The ratio has no value when the context has no counts. The test log-likelihood is minus infinity when the context is seen but the full window never is. Both cases come from the raw counts, so the next section adds smoothing.

Smoothing and the curse of dimensionality

Smoothing moves some probability from observed windows to unseen ones. The book describes adding non-zero mass to every possible next word, and mixing higher-order and lower-order models through back-off. The additive form below is added here to make the idea concrete. The book does not print this equation.

The formula below is added here. Each count gets added, and the denominator grows by times so that the probabilities still add to one.

The book names the curse of dimensionality for n-grams. There are to the power possible windows, and is often very large. Most windows never occur in the training set, even with a massive corpus. A classical model is a local lookup, close to a nearest-neighbor predictor. Two different words are the same distance apart in one-hot space, so the model cannot borrow strength from a word that is similar to the one it saw.

The book also suggests combining the two kinds of model in an ensemble. An n-gram model stores very many counts at little computation per example, and a neural model adds capacity at a cost that grows with its parameters. An ensemble of both can reduce test error when the members make different mistakes.

Embeddings for words

Neural language models solve this by giving each word a distributed representation, which the book calls a word embedding. Each embedding is a short vector of real numbers that the model learns, so it is a point in a space of lower dimension than the vocabulary. Words that share features get nearby points, so a sentence with cat can inform the prediction for a sentence with dog.

Figure 12.3 in the book is a two-dimensional view of an embedding learned by a neural machine translation model. The book says real embeddings have higher dimension and capture several kinds of similarity at once. The words below and their positions are made up for this page and are added here.

The book notes that the idea goes back to Rumelhart et al. (1986), who learned embeddings of family members from triplets such as (Colin, Mother, Victoria). Deerwester et al. (1990) extended it to words with the SVD. Bengio et al. (2001) returned the focus to words and introduced neural language models, which produce interpretable word embeddings.

High-dimensional outputs

Word-based models must produce one score for each word in the vocabulary. The affine layer in equation (12.8) has one output per word, and the softmax in equation (12.9) normalizes over all of them. The cost is order times the hidden size, and it is paid at training time and at test time, because the normalizing sum needs every score.

The book describes several ways to reduce this cost. Each one avoids summing over the whole vocabulary in a different way.

Short list. The first neural language models kept the vocabulary to 10,000 or 20,000 words. Later work split into a shortlist of the most frequent words, handled by the neural network, and a tail of the rarer words, handled by an -gram model. The network also predicts the probability that the next word is in the tail, with one extra sigmoid output. Equation (12.10) combines the two predictions into one distribution over .

The indicator is one when its condition holds and zero otherwise, so one of the two lines contributes for each word. For a word on the shortlist, the neural prediction is weighted by one minus the tail probability. For a word in the tail, the n-gram prediction is weighted by the tail probability. If the tail probability is zero, the result is the neural model restricted to the shortlist. The book notes the cost of this approach: the advantage of the neural model is limited to the most frequent words, where, arguably, it is the least useful.

Hierarchical softmax. This method arranges the words in a tree and multiplies the branch probabilities along the path to a word, as in Figure 12.4. Its cost grows with the depth of the tree rather than with the vocabulary.

Equations (12.11) and (12.12) give the probability of one word in the tree of Figure 12.4. The first line names the three binary decisions on the path to that word. The second line is the product of their probabilities. In a balanced tree the path has depth on the order of log |V|. The book adds that the best tree is hard to learn, because the choice of word classes is discrete, and that the hierarchical softmax often gives worse test results than the sampling methods below.

Importance sampling. Training needs the gradient of the log probability of the correct word, equation (12.13). Here is the vector of pre-softmax scores, one number per word, and collects the parameters. The result has two terms. The first pushes the correct score up. The second pushes every score down, in proportion to its probability under the model. This second term is an expectation over the whole vocabulary, so it costs as much as the softmax itself.

A Monte Carlo estimate of the second term would need draws from the model, and drawing from the model needs the probability of every word. The book therefore draws the negative words from a proposal distribution that is cheap to sample, and corrects for the mismatch with weights. Exact weights would be , which needs every score. The book's solution is biased importance sampling: the weights are normalized so that they sum to one, as in equation (12.17). Equation (12.18) then replaces the sum over the vocabulary with a sum over sampled words.

The normalizer of the softmax is the same for every word, so it cancels in the ratio of equation (12.17). The weights therefore need only the scores and proposal probabilities of the sampled words, not the full sum. This cancellation is added here and is not printed in the book.

Equation (12.18) multiplies the sampled sum by 1 over . The weights in (12.17) are normalized over the same draws, so they already sum to one. The demo below therefore uses the weighted sum without that extra factor. Read literally, the two equations give different values on the same draws. This reading is added here and is not printed in the book.

Ranking loss. Equation (12.19) avoids probabilities altogether. It treats each score as a ranking signal and asks the correct score to beat each negative score by a margin of 1. The term for a negative word is zero once that margin holds. The book notes one drawback: the loss gives no conditional probabilities, which speech recognition and translation need.

Attention and translation

Machine translation reads a sentence in one language and emits an equivalent sentence in another. The encoder-decoder design in Figure 12.5 has one model that reads the source into a context, and a second model that writes the target from it. A fixed vector struggles with a long sentence, so the book describes attention. The decoder reads the whole source, then looks at a different part of it for each output word.

The weights are a softmax over relevance scores, and the context vector is their weighted average. The scores and the sharpness are added here, and the book describes the same structure in words.

The book says the weighted average is smooth and differentiable, so it can be trained with gradient descent. Direct indexing of the one chosen position is cheaper, but it cannot be trained that way. The attention mechanism is therefore a trainable approximation to reading one position.

• An n-gram model conditions on the previous n minus 1 tokens, and its maximum likelihood estimate is a ratio of counts that can be zero.
• Smoothing and embeddings address the curse of dimensionality, because embeddings let similar words share statistical strength.
• The cost of the output layer grows with the vocabulary. The hierarchical softmax and the ranking loss reduce the cost in different ways.
• Attention replaces a fixed sentence vector with a weighted average over source positions, which is the basis of neural machine translation.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 12.4 (pages 461–477), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.