4.3.2 Unknown Words: Open versus closed vocabulary tasks

Sometimes we have a language task in which we know all the words that can occur, and hence we know the vocabulary size V in advance. The closed vocabulary assumption is the assumption that we have such a lexicon, and that the test set can only contain words from this lexicon. The closed vocabulary task thus assumes there are no unknown words.

But of course this is a simplification; as we suggested earlier, the number of unseen words grows constantly, so we can't possibly know in advance exactly how many there are, and we'd like our model to do something reasonable with them. We call these unseen events unknown words, or out of vocabulary (OOV) words. The percentage of OOV words that appear in the test set is called the OOV rate.

An open vocabulary system is one where we model these potential unknown words in the test set by adding a pseudo-word called . We can train the probabilities of the unknown word model as follows:

1. Choose a vocabulary (word list) which is fixed in advance.

2. Convert in the training set any word that is not in this set (any OOV word) to the unknown word token in a text normalization step.

3. Estimate the probabilities for from its counts just like any other regular word in the training set.

4.4 EVALUATING N-GRAMS: PERPLEXITY

The best way to evaluate the performance of a language model is to embed it in an application and measure the total performance of the application. Such end-to-end evaluation is called extrinsic evaluation, and also sometimes called in vivo evaluation (Sparck Jones and Galliers, 1996). Extrinsic evaluation is the only way to know if a particular improvement in a component is really going to help the task at hand. Thus for speech recognition, we can compare the performance of two language models by running the speech recognizer twice, once with each language model, and seeing which gives the more accurate transcription.

Unfortunately, end-to-end evaluation is often very expensive; evaluating a large speech recognition test set, for example, takes hours or even days. Thus we would like a metric that can be used to quickly evaluate potential improvements in a language model. An intrinsic evaluation metric is one which measures the quality of a model independent of any application. Perplexity is the most common intrinsic evaluation metric for N-gram language models. While an (intrinsic) improvement in perplexity does not guarantee an (extrinsic) improvement in speech recognition performance (or any other end-to-end metric), it often correlates with such improvements. Thus it is

commonly used as a quick check on an algorithm and an improvement in perplexity can then be confirmed by an end-to-end evaluation.

The intuition of perplexity is that given two probabilistic models, the better model is the one that has a tighter fit to the test data, or predicts the details of the test data better. We can measure better prediction by looking at the probability the model assigns to the test data; the better model will assign a higher probability to the test data.

More formally, the perplexity (sometimes called PP for short) of a language model on a test set is a function of the probability that the language model assigns to that test set. For a test set $ W = w_1 w_2 \ldots w_N $, the perplexity is the probability of the test set, normalized by the number of words:

$$ \begin{align*}\operatorname{PP}(W)&=P(w_1w_2\ldots w_N)^{-\frac{1}{N}}\\&=\sqrt[N]{\frac{1}{P(w_1w_2\ldots w_N)}}\end{align*} $$

We can use the chain rule to expand the probability of W:

$$ \mathrm{PP}(W)=\sqrt[N]{\prod_{i=1}^{N}\frac{1}{P(w_{i}|w_{1}\ldots w_{i-1})}} $$

Thus if we are computing the perplexity of W with a bigram language model, we get:

$$ PP(W)=\sqrt[N]{\prod_{i=1}^{N}\frac{1}{P(w_{i}|w_{i-1})}} $$

Note that because of the inverse in Equation (4.17), the higher the conditional probability of the word sequence, the lower the perplexity. Thus minimizing perplexity is equivalent to maximizing the test set probability according to the language model. What we generally use for word sequence in Equation (4.17) or Equation (4.18) is the entire sequence of words in some test set. Since of course this sequence will cross many sentence boundaries, we need to include the begin- and end-sentence markers $ \langle s \rangle $ and $ \langle /s \rangle $ in the probability computation. We also need to include the end-of-sentence marker $ \langle /s \rangle $ (but not the beginning-of-sentence marker $ \langle s \rangle $) in the total count of word tokens N.

There is another way to think about perplexity: as the weighted average branching factor of a language. The branching factor of a language is the number of possible next words that can follow any word. Consider the task of recognizing the digits in English (zero, one, two,..., nine), given that each of the 10 digits occurs with equal probability $ P = \frac{1}{10} $. The perplexity of this mini-language is in fact 10. To see that, imagine a string of digits of length N. By Equation (4.17), the perplexity will be:

$$ PP(W)\;=\;P(w_{1}w_{2}\ldots w_{N})^{-\frac{1}{N}} $$

$$ \begin{aligned}=&(\frac{1}{10}^{N})^{-\frac{1}{N}}\\ =&\frac{1}{10}^{-1}\\ =&10\end{aligned} $$

But now suppose that the number zero is really frequent and occurs 10 times more often than other numbers. Now we should expect the perplexity to be lower, since most of the time the next number will be zero. Thus although the branching factor is still 10, the perplexity or weighted branching factor is smaller. We leave this calculation as an exercise to the reader.

We'll see in Sec. 4.10 that perplexity is also closely related to the information-theoretic notion of entropy.

Finally, let's see an example of how perplexity can be used to compare three N-gram models. We trained unigram, bigram, and trigram grammars on 38 million words (including start-of-sentence tokens) from the Wall Street Journal, using a 19,979 word vocabulary. $ ^{5} $ We then computed the perplexity of each of these models on a test set of 1.5 million words via Equation (4.65). The table below shows the perplexity of a 1.5 million word WSJ test set according to each of these grammars.

As we see above, the more information the N-gram gives us about the word sequence, the lower the perplexity (since as Equation (4.17) showed, perplexity is related inversely to the likelihood of the test sequence according to the model).

Note that in computing perplexities the N-gram model P must be constructed without any knowledge of the test set. Any kind of knowledge of the test set can cause the perplexity to be artificially low. For example, we defined above the closed vocabulary task, in which the vocabulary for the test set is specified in advance. This can greatly reduce the perplexity. As long as this knowledge is provided equally to each of the models we are comparing, the closed vocabulary perplexity can still be useful for comparing models, but care must be taken in interpreting the results. In general, the perplexity of two language models is only comparable if they use the same vocabulary.

4.5 SMOOTHING

Never do I ever want to hear another word! There isn't one, I haven't heard!

Eliza Doolittle in Alan Jay Lerner's My Fair Lady

There is a major problem with the maximum likelihood estimation process we have seen for training the parameters of an N-gram model. This is the problem of sparse data caused by the fact that our maximum likelihood estimate was based on a particular set of training data. For any N-gram that occurred a sufficient number of times, we might have a good estimate of its probability. But because any corpus is limited, some perfectly acceptable English word sequences are bound to be missing from it. This missing data means that the N-gram matrix for any given training corpus is bound to have a very large number of cases of putative "zero probability N-grams" that should really have some non-zero probability. Furthermore, the MLE method also produces poor estimates when the counts are non-zero but still small.

We need a method which can help get better estimates for these zero or low-frequency counts. Zero counts turn out to cause another huge problem. The perplexity metric defined above requires that we compute the probability of each test sentence. But if a test sentence has an N-gram that never appeared in the training set, the Maximum Likelihood estimate of the probability for this N-gram, and hence for the whole test sentence, will be zero! This means that in order to evaluate our language models, we need to modify the MLE method to assign some non-zero probability to any N-gram, even one that was never observed in training.

For these reasons, we'll want to modify the maximum likelihood estimates for computing $ N $-gram probabilities, focusing on the $ N $-gram events that we incorrectly assumed had zero probability. We use the term 'smoothing' for such modifications that address the poor estimates that are due to variability in small data sets. The name comes from the fact that (looking ahead a bit) we will be shaving a little bit of probability mass from the higher counts, and piling it instead on the zero counts, making the distribution a little less jagged.

In the next few sections we will introduce some smoothing algorithms and show how they modify the Berkeley Restaurant bigram probabilities in Fig. 4.2.