4.7.1 Advanced: Details of computing Katz backoff $ \alpha $ and $ P^{*} $

In this section we give the remaining details of the computation of the discounted probability $ P^{*} $ and the backoff weights $ \alpha(w) $.

We begin with $ \alpha $, which passes the left-over probability mass to the lower order N-grams. Let's represent the total amount of left-over probability mass by the function

$ \beta $, a function of the $ (N-1) $-gram context. For a given $ (N-1) $-gram context, the total left-over probability mass can be computed by subtracting from 1 the total discounted probability mass for all N-grams starting with that context:

$$ \beta(w_{n-N+1}^{n-1})=1-\sum_{w_{n}:c(w_{n-N+1}^{n})>0}P^{*}(w_{n}|w_{n-N+1}^{n-1}) $$

This gives us the total probability mass that we are ready to distribute to all (N-1)-gram (e.g., bigrams if our original model was a trigram). Each individual (N-1)-gram (bigram) will only get a fraction of this mass, so we need to normalize $ \beta $ by the total probability of all the (N-1)-grams (bigrams) that begin some N-gram (trigram) which has zero count. The final equation for computing how much probability mass to distribute from an N-gram to an (N-1)-gram is represented by the function $ \alpha $:

$$ \begin{align*}\alpha(w_{n-N+1}^{n-1})&=\frac{\beta(w_{n-N+1}^{n-1})}{\sum_{w_{n}:c(w_{n-N+1}^{n})=0}P_{katz}(w_{n}|w_{n-N+2}^{n-1})}\\&=\frac{1-\sum_{w_{n}:c(w_{n-N+1}^{n})>0}P^{*}(w_{n}|w_{n-N+1}^{n-1})}{1-\sum_{w_{n}:c(w_{n-N+1}^{n})>0}P^{*}(w_{n}|w_{n-N+2}^{n-1})}\end{align*} $$

Note that $ \alpha $ is a function of the preceding word string, that is, of $ w_{n-N+1}^{n-1} $; thus the amount by which we discount each trigram $ (d) $, and the mass that gets reassigned to lower order N-grams $ (\alpha) $ are recomputed for every $ (N-1) $-gram that occurs in any N-gram.

We only need to specify what to do when the counts of an $ (N-1) $-gram context are 0, (i.e., when $ c(w_{n-N+1}^{n-1})=0 $) and our definition is complete:

$$ P_{\mathrm{k a t z}}(w_{n}|w_{n-N+1}^{n-1})=P_{\mathrm{k a t z}}(w_{n}|w_{n-N+2}^{n-1})\quad\mathrm{i f}c(w_{n-N+1}^{n-1})=0 $$

and

$$ P^{*}(w_{n}|w_{n-N+1}^{n-1})=0\quad\mathrm{~i f~}c(w_{n-N+1}^{n-1})=0 $$

and

$$ \beta(w_{n-N+1}^{n-1})=1\quad\mathrm{i f~}c(w_{n-N+1}^{n-1})=0 $$

4.8 PRACTICAL ISSUES: TOOLKITS AND DATA FORMATS

Let's now examine how N-gram language models are represented. We represent and compute language model probabilities in log format, in order to avoid underflow and also to speed up computation. Since probabilities are (by definition) less than 1, the more probabilities we multiply together the smaller the product becomes. Multiplying enough N-grams together would result in numerical underflow. By using log probabilities instead of raw probabilities, the numbers are not as small. Since adding in log space is equivalent to multiplying in linear space, we combine log probabilities by adding them. Besides avoiding underflow, addition is faster to compute than multiplication. Since we do all computation and storage in log space, if we ever need to report probabilities we just take the exp of the logprob:

$$ p_{1}\times p_{2}\times p_{3}\times p_{4}=\exp(\log p_{1}+\log p_{2}+\log p_{3}+\log p_{4}) $$

Backoff N-gram language models are generally stored in ARPA format. An N-gram in ARPA format is an ASCII file with a small header followed by a list of all the non-zero N-gram probabilities (all the unigrams, followed by bigrams, followed by trigrams, and so on). Each N-gram entry is stored with its discounted log probability (in $ \log_{10} $ format) and its backoff weight $ \alpha $. Backoff weights are only necessary for N-grams which form a prefix of a longer N-gram, so no $ \alpha $ is computed for the highest order N-gram (in this case the trigram) or N-grams ending in the end-of-sequence token $ $. Thus for a trigram grammar, the format of each N-gram is:

$$ \begin{array}{l l l l}{{u n i g r a m:}}&{\operatorname{l o g}p^{*}(w_{i})}&{w_{i}}&{\operatorname{l o g}\alpha(w_{i})}\\ {{b i g r a m:}}&{\operatorname{l o g}p^{*}(w_{i}|w_{i-1})}&{w_{i-1}w_{i}}&{\operatorname{l o g}\alpha(w_{i-1}w_{i})}\\ {{t r i g r a m:}}&{\operatorname{l o g}p^{*}(w_{i}|w_{i-2},w_{i-1})}&{w_{i-2}w_{i-1}w_{i}}&{}\\ \end{array} $$

Fig. 4.10 shows an ARPA formatted LM file with selected N-grams from the BeRP corpus. Given one of these trigrams, the probability $ P(z|x,y) $ for the word sequence x,y,z can be computed as follows (repeated from (4.37)):

$$ P_{\mathrm{k a t z}}(z|x,y)\;=\;\left\{\begin{array}{l l}{P^{*}(z|x,y),\quad}&{\mathrm{i f}\;C(x,y,z)>0}\\ {\alpha(x,y)P_{\mathrm{k a t z}}(z|y),\quad}&{\mathrm{e l s e}\;\mathrm{i f}\;C(x,y)>0}\\ {P^{*}(z),\quad}&{\mathrm{o t h e r w i s e}.}\end{array}\right. $$

$$ P_{\mathrm{k a t z}}(z|y)=\left\{\begin{aligned}&P^{*}(z|y),\quad&if C(y,z)>0\\&\alpha(y)P^{*}(z),\quad&otherwise.\end{aligned}\right. $$

Toolkits: There are two commonly used available toolkits for building language models, the SRILM toolkit (Stolcke, 2002) and the Cambridge-CMU toolkit (Clarkson and Rosenfeld, 1997). Both are publicly available, and have similar functionality.

原书第 119 页

Figure 4.10 ARPA format for N-grams, showing some sample N-grams. Each is represented by a logprob, the word sequence, $ w_1...w_n $, followed by the log backoff weight $ \alpha $. Note that no $ \alpha $ is computed for the highest-order N-gram or for N-grams ending in $ $.

In training mode, each toolkit takes a raw text file, one sentence per line with words separated by white-space, and various parameters such as the order N, the type of discounting (Good Turing or Kneser-Ney, discussed in Sec. 4.9.1), and various thresholds. The output is a language model in ARPA format. In perplexity or decoding mode, the toolkits take a language model in ARPA format, and a sentence or corpus, and produce the probability and perplexity of the sentence or corpus. Both also implement many advanced features to be discussed later in this chapter and in following chapters, including skip N-grams, word lattices, confusion networks, and N-gram pruning.