4.9.4 Using Longer Distance Information: A Brief Summary

There are many methods for incorporating longer-distance context into N-gram modeling. While we have limited our discussion mainly to bigram and trigrams, state-of-the-art speech recognition systems, for example, are based on longer-distance N-grams, especially 4-grams, but also 5-grams. Goodman (2006) showed that with 284 million words of training data, 5-grams do improve perplexity scores over 4-grams, but not by much. Goodman checked contexts up to 20-grams, and found that after 6-grams, longer contexts weren't useful, at least not with 284 million words of training data.

Many models focus on more sophisticated ways to get longer-distance information. For example people tend to repeat words they have used before. Thus if a word is used once in a text, it will probably be used again. We can capture this fact by a cache language model (Kuhn and De Mori, 1990). For example to use a unigram cache model

to predict word i of a test corpus, we create a unigram grammar from the preceding part of the test corpus (words 1 to i-1) and mix this with our conventional N-gram. We might use only a shorter window from the previous words, rather than the entire set. Cache language models are very powerful in any applications where we have perfect knowledge of the words. Cache models work less well in domains where the previous words are not known exactly. In speech applications, for example, unless there is some way for users to correct errors, cache models tend to “lock in” errors they made on earlier words.

The fact that words are often repeated in a text is a symptom of a more general fact about words; texts tend to be about things. Documents which are about particular topics tend to use similar words. This suggests that we could train separate language models for different topics. In topic-based language models (Chen et al., 1998; Gildea and Hofmann, 1999), we try to take advantage of the fact that different topics will have different kinds of words. For example we can train different language models for each topic t, and then mix them, weighted by how likely each topic is given the history h:

$$ p(w|h)=\sum_{t}P(w|t)P(t|h) $$

A very similar class of models relies on the intuition that upcoming words are semantically similar to preceding words in the text. These models use a measure of semantic word association such as the latent semantic indexing described in Ch. 20 (Coccaro and Jurafsky, 1998; Bellegarda, 1999, 2000), or on-line dictionaries or the sauri (Demetriou et al., 1997) to compute a probability based on a word's similarity to preceding words, and then mix it with a conventional N-gram.

There are also various ways to extend the $ N $-gram model by having the previous (conditioning) word be something other than a fixed window of previous words. For example we can choose as a predictor a word called a \textit{trigger} which is not adjacent but which is very related (has high mutual information with) the word we are trying to predict (Rosenfeld, 1996; Niesler and Woodland, 1999; Zhou and Lua, 1998). Or we can create \textit{skip} $ N $-grams, where the preceding context ‘skips over’ some intermediate words, for example computing a probability such as $ P(w_i|w_{i-1},w_{i-3}) $. We can also use extra previous context just in cases where a longer phrase is particularly frequent or predictive, producing a \textit{variable-length} $ N $-gram (Ney et al., 1994; Kneser, 1996; Niesler and Woodland, 1996).

In general, using very large and rich contexts can result in very large language models. Thus these models are often pruned by removing low-probability events. Pruning is also essential for using language models on small platforms such as cellphones (Stolcke, 1998; Church et al., 2007).

Finally, there is a wide body of research on integrating sophisticated linguistic structures into language modeling. Language models based on syntactic structure from probabilistic parsers are described in Ch. 14. Language models based on the current speech act in dialogue are described in Ch. 24.

4.10 ADVANCED: INFORMATION THEORY BACKGROUND

I got the horse right here

Frank Loesser, Guys and Dolls

We introduced perplexity in Sec. 4.4 as a way to evaluate N-gram models on a test set. A better N-gram model is one which assigns a higher probability to the test data, and perplexity is a normalized version of the probability of the test set. Another way to think about perplexity is based on the information-theoretic concept of cross-entropy. In order to give another intuition into perplexity as a metric, this section gives a quick review of fundamental facts from information theory including the concept of cross-entropy that underlies perplexity. The interested reader should consult a good information theory textbook like Cover and Thomas (1991).

Perplexity is based on the information-theoretic notion of cross-entropy, which we will now work toward defining. Entropy is a measure of information, and is invaluable throughout speech and language processing. It can be used as a metric for how much information there is in a particular grammar, for how well a given grammar matches a given language, for how predictive a given N-gram grammar is about what the next word could be. Given two grammars and a corpus, we can use entropy to tell us which grammar better matches the corpus. We can also use entropy to compare how difficult two speech recognition tasks are, and also to measure how well a given probabilistic grammar matches human grammars.

Computing entropy requires that we establish a random variable X that ranges over whatever we are predicting (words, letters, parts of speech, the set of which we'll call $ \chi $), and that has a particular probability function, call it $ p(x) $. The entropy of this random variable X is then

$$ H(X)=-\sum_{x\in\mathcal{X}}p(x)\log_{2}p(x) $$

The log can in principle be computed in any base. If we use log base 2, the resulting value of entropy will be measured in bits.

The most intuitive way to define entropy for computer scientists is to think of the entropy as a lower bound on the number of bits it would take to encode a certain decision or piece of information in the optimal coding scheme.

Cover and Thomas (1991) suggest the following example. Imagine that we want to place a bet on a horse race but it is too far to go all the way to Yonkers Racetrack, and we'd like to send a short message to the bookie to tell him which horse to bet on. Suppose there are eight horses in this particular race.

One way to encode this message is just to use the binary representation of the horse's number as the code; thus horse 1 would be 001, horse 2 010, horse 3 011, and so on, with horse 8 coded as 000. If we spend the whole day betting, and each horse is coded with 3 bits, on average we would be sending 3 bits per race.

Can we do better? Suppose that the spread is the actual distribution of the bets placed, and that we represent it as the prior probability of each horse as follows:

| Horse 1 | $ \frac{1}{2} $ | Horse 5 | $ \frac{1}{64} $ |

| --- | --- | --- | --- |

| Horse 2 | $ \frac{1}{4} $ | Horse 6 | $ \frac{1}{64} $ |

| Horse 3 | $ \frac{1}{8} $ | Horse 7 | $ \frac{1}{64} $ |

| Horse 4 | $ \frac{1}{16} $ | Horse 8 | $ \frac{1}{64} $ |

The entropy of the random variable X that ranges over horses gives us a lower bound on the number of bits, and is:

$$ \begin{align*}H(X)&=-\sum_{i=1}^{i=8}p(i)\log p(i)\\&=-\tfrac{1}{2}\log\tfrac{1}{2}-\tfrac{1}{4}\log\tfrac{1}{4}-\tfrac{1}{8}\log\tfrac{1}{8}-\tfrac{1}{16}\log\tfrac{1}{16}-4(\tfrac{1}{64}\log\tfrac{1}{64})\\&=2\mathrm{bits}\end{align*} $$

A code that averages 2 bits per race can be built by using short encodings for more probable horses, and longer encodings for less probable horses. For example, we could encode the most likely horse with the code 0, and the remaining horses as 10, then 110, 1110, 111100, 111101, 111110, and 111111.

What if the horses are equally likely? We saw above that if we used an equal-length binary code for the horse numbers, each horse took 3 bits to code, so the average was 3. Is the entropy the same? In this case each horse would have a probability of $ \frac{1}{8} $. The entropy of the choice of horses is then:

$$ H(X)=-\sum_{i=1}^{i=8}\frac{1}{8}\log\frac{1}{8}=-\log\frac{1}{8}=3bits $$

Until now we have been computing the entropy of a single variable. But most of what we will use entropy for involves sequences. For a grammar, for example, we will be computing the entropy of some sequence of words $ W = \{w_0, w_1, w_2, \ldots, w_n\} $. One way to do this is to have a variable that ranges over sequences of words. For example we can compute the entropy of a random variable that ranges over all finite sequences of words of length $ n $ in some language $ L $ as follows:

$$ H(w_{1},w_{2},\ldots,w_{n})=-\sum_{W_{1}^{n}\in L}p(W_{1}^{n})\log p(W_{1}^{n}) $$

We could define the entropy rate (we could also think of this as the per-word entropy) as the entropy of this sequence divided by the number of words:

$$ \frac{1}{n}H(W^{n}_{1})=-\frac{1}{n}\sum_{W^{n}_{1}\in L}p(W^{n}_{1})\log p(W^{n}_{1}) $$

But to measure the true entropy of a language, we need to consider sequences of infinite length. If we think of a language as a stochastic process $L$ that produces a sequence of words, its entropy rate $H(L)$ is defined as:

$$ \begin{align*}H(L)&=-\lim_{n\to\infty}\frac{1}{n}H(w_{1},w_{2},\ldots,w_{n})\\&=-\lim_{n\to\infty}\frac{1}{n}\sum_{W\in L}p(w_{1},\ldots,w_{n})\log p(w_{1},\ldots,w_{n})\end{align*} $$

The Shannon-McMillan-Breiman theorem (Algoet and Cover, 1988; Cover and Thomas, 1991) states that if the language is regular in certain ways (to be exact, if it is both stationary and ergodic),

$$ H(L)=\lim_{n\to\infty}-\frac{1}{n}\log p(w_{1}w_{2}\ldots w_{n}) $$

That is, we can take a single sequence that is long enough instead of summing over all possible sequences. The intuition of the Shannon-McMillan-Breiman theorem is that a long enough sequence of words will contain in it many other shorter sequences, and that each of these shorter sequences will reoccur in the longer sequence according to their probabilities.

A stochastic process is said to be stationary if the probabilities it assigns to a sequence are invariant with respect to shifts in the time index. In other words, the probability distribution for words at time $t$ is the same as the probability distribution at time $t+1$. Markov models, and hence N-grams, are stationary. For example, in a bigram, $P_{i}$ is dependent only on $P_{t-1}$. So if we shift our time index by $x$, $P_{t+x}$ is still dependent on $P_{t+x-1}$. But natural language is not stationary, since as we will see in Ch. 12, the probability of upcoming words can be dependent on events that were arbitrarily distant and time dependent. Thus our statistical models only give an approximation to the correct distributions and entropies of natural language.

To summarize, by making some incorrect but convenient simplifying assumptions, we can compute the entropy of some stochastic process by taking a very long sample of the output, and computing its average log probability. In the next section we talk about the why and how: why we would want to do this (i.e., for what kinds of problems would the entropy tell us something useful), and how to compute the probability of a very long sequence.