14.1.2 PCFGs for Language Modeling

A second attribute of a PCFG is that it assigns a probability to the string of words constituting a sentence. This is important in language modeling, whether for use in speech recognition, machine translation, spell-correction, augmentative communication, or other applications. The probability of an unambiguous sentence is $ P(T, S) = P(T) $ or just the probability of the single parse tree for that sentence. The probability of an ambiguous sentence is the sum of the probabilities of all the parse trees for the sentence:

$$ \begin{array}{r l}{P(S)}&{=\displaystyle\sum_{T s.t.S=\mathrm{y i e l d}(T)}P(T,S)}\\ &{=\displaystyle\sum_{T s.t.S=\mathrm{y i e l d}(T)}P(T)}\end{array} $$

An additional feature of PCFGs that is useful for language modeling is their ability to assign a probability to substrings of a sentence. For example, suppose we want to know the probability of the next word $ w_i $ in a sentence given all the words we've seen so far $ w_1, ..., w_{i-1} $. The general formula for this is:

$$ P(w_{i}|w_{1},w_{2},...,w_{i-1})=\frac{P(w_{1},w_{2},...,w_{i-1},w_{i},...)}{P(w_{1},w_{2},...,w_{i-1},...)} $$

We saw in Ch. 4 a simple approximation of this probability using N-grams, conditioning on only the last word or two instead of the entire context; thus the bigram approximation would give us:

$$ P\big(w_{i}|w_{1},w_{2},...,w_{i-1}\big)\approx\frac{P\big(w_{i-1},w_{i}\big)}{P\big(w_{i-1}\big)} $$

But the fact that the N-gram model can only make use of a couple words of context means it is ignoring potentially useful prediction cues. Consider predicting the word after in the following sentence from Chelba and Jelinek (2000):

(14.13) the contract ended with a loss of 7 cents after trading as low as 9 cents

A trigram grammar must predict after from the words 7 cents, while it seems clear that the verb ended and the subject contract would be useful predictors that a PCFG-based parser could help us make use of. Indeed, it turns out that a PCFGs allow us to condition on the entire previous context $ w_{1}, w_{2}, ..., w_{i-1} $ shown in Equation (14.11). We'll see the details of ways to use PCFGs and augmentations of PCFGs as language models in Sec. 14.9.

In summary, this section and the previous one have shown that PCFGs can be applied both to disambiguation in syntactic parsing and to word prediction in language modeling. Both of these applications require that we be able to compute the probability of parse tree T for a given sentence S. The next few sections introduce some algorithms for computing this probability.

14.2 PROBABILISTIC CKY PARSING OF PCFGs

The parsing problem for PCFGs is to produce the most-likely parse $ \hat{T} $ for a given sentence S, i.e.,

$$ \hat{T}(S)=\underset{T s.t.S=yield(T)}{argmax}P(T) $$

The algorithms for computing the most-likely parse are simple extensions of the standard algorithms for parsing; there are probabilistic versions of both the CKY and Earley algorithms of Ch. 13. Most modern probabilistic parsers are based on the probabilistic CKY (Cocke-Kasami-Younger) algorithm, first described by Ney (1991).

As with the CKY algorithm, we will assume for the probabilistic CKY algorithm that the PCFG is in Chomsky normal form. Recall from page ?? that grammars in CNF are restricted to rules of the form $ A \to B C $, or $ A \to w $. That is, the right-hand side of each rule must expand to either two non-terminals or to a single terminal.

For the CKY algorithm, we represented each sentence as having indices between the words. Thus an example sentence like

(14.15) Book the flight through Houston.

would assume the following indices between each word:

① Book ① the ② flight ③ through ④ Houston ⑤

Using these indices, each constituent in the CKY parse tree is encoded in a two-dimensional matrix. Specifically, for a sentence of length $n$ and a grammar that contains $V$ non-terminals, we use the upper-triangular portion of an $(n+1)\times(n+1)$ matrix. For CKY, each cell $table[i,j]$ contained a list of constituents that could span the sequence of words from $i$ to $j$. For probabilistic CKY, it's slightly simpler to think of the constituents in each cell as constituting a third dimension of maximum length $V$. This third dimension corresponds to each nonterminal that can be placed in this cell, and the value of the cell is then a probability for that nonterminal/constituent rather than a list of constituents. In summary, each cell $[i,j,A]$ in this $(n+1)\times(n+1)\times V$ matrix is the probability of a constituent $A$ that spans positions $i$ through $j$ of the input.

Fig. 14.3 gives pseudocode for this probabilistic CKY algorithm, extending the basic CKY algorithm from Fig. \ref{fig:14}.

Like the CKY algorithm, the probabilistic CKY algorithm as shown in Fig. 14.3 requires a grammar in Chomsky Normal Form. Converting a probabilistic grammar to CNF requires that we also modify the probabilities so that the probability of each parse remains the same under the new CNF grammar. Exercise 14.2 asks you to modify the algorithm for conversion to CNF in Ch. 13 so that it correctly handles rule probabilities.

In practice, we more often use a generalized CKY algorithm which handles unit productions directly rather than converting them to CNF. Recall that Exercise ?? asked you to make this change in CKY; Exercise 14.3 asks you to extend this change to probabilistic CKY.

Let's see an example of the probabilistic CKY chart, using the following minigrammar which is already in CNF:

function PROBABILISTIC-CKY(words,grammar) returns most probable parse

and its probability

for $ j \leftarrow $ from 1 to LENGTH(words) do

for all $ \{A \mid A \rightarrow \text{words}[j] \in \text{grammar}\} $

table $ [j-1, j, A] \leftarrow P(A \rightarrow \text{words}[j]) $

for $ i \leftarrow $ from j-2 downto 0 do

for $ k \leftarrow i + 1 $ to j-1 do

for all $ \{A \mid A \rightarrow BC \in \text{grammar}, \text{and } \text{table}[i,k,B] > 0 \text{ and } \text{table}[k,j,C] > 0\} $

if $ (table[i,j,A] < P(A \rightarrow BC) \times \text{table}[i,k,B] \times \text{table}[k,j,C]) $ then

table $ [i,j,A] \leftarrow P(A \rightarrow BC) \times \text{table}[i,k,B] \times \text{table}[k,j,C] $

back $ [i,j,A] \leftarrow \{k,B,C\} $

return BUILD_TREE(back $ [1, LENGTH(\text{words}), S] $), table $ [1, LENGTH(\text{words}), S] $

S $ \rightarrow $ NP VP .80 | Det $ \rightarrow $ the .50

NP $ \rightarrow $ Det N .30 | Det $ \rightarrow $ a .40

VP $ \rightarrow $ V NP .20 | N $ \rightarrow $ meal .01

V $ \rightarrow $ includes .05 | N $ \rightarrow $ flight .02

Given this grammar, Fig. 14.4 shows the first steps in the probabilistic CKY parse of this sentence:

(14.17) The flight includes a meal

14.3 LEARNING PCFG RULE PROBABILITIES

TREEBANK

Where do PCFG rule probabilities come from? There are two ways to learn probabilities for the rules of a grammar. The simplest way is to use a treebank, a corpus of already- parsed sentences. Recall that we introduced in Ch. 12 the idea of treebanks and the commonly-used Penn Treebank (Marcus et al., 1993), a collection of parse trees in English, Chinese, and other languages distributed by the Linguistic Data Consortium. Given a treebank, the probability of each expansion of a non-terminal can be computed by counting the number of times that expansion occurs and then normalizing.

$$ P(\alpha\to\beta|\alpha)=\frac{\operatorname{Count}(\alpha\to\beta)}{\sum_{\gamma}\operatorname{Count}(\alpha\to\gamma)}=\frac{\operatorname{Count}(\alpha\to\beta)}{\operatorname{Count}(\alpha)} $$

If we don’t have a treebank, but we do have a (non-probabilistic) parser, we can generate the counts we need for computing PCFG rule probabilities by first parsing a corpus of sentences with the parser. If sentences were unambiguous, it would be as

EXPECTATION

E-STEP

(EXPECTATION STEP)

IN EM

MAXIMIZATION

M-STEP

(MAXIMIZATION

STEP) IN EM

simple as this: parse the corpus, increment a counter for every rule in the parse, and then normalize to get probabilities.

But wait! Since most sentences are ambiguous, i.e. have multiple parses, we don't know which parse to count the rules in. Instead, we need to keep a separate count for each parse of a sentence and weight each of these partial counts by the probability of the parse it appears in. But to get these parse probabilities to weight the rules we need to already have a probabilistic parser.

The intuition for solving this chicken-and-egg problem is to incrementally improve our estimates by beginning with a parser with equal rule probabilities, parsing the sentence, compute a probability for each parse, use these probabilities to weight the counts, then reestimate the rule probabilities, and so on, until our probabilities converge. The standard algorithm for computing this is called the inside-outside algorithm, and was proposed by Baker (1979) as a generalization of the forward-backward algorithm of Ch. 6. Like forward-backward, inside-outside is a special case of the EM (expectation-maximization) algorithm, and hence has two steps: the expectation step, or E-step (expectation step) in EM, and the maximization step, or M-step (maximization step) in EM. See Lari and Young (1990) or Manning and Schütze (1999) for a complete description of the algorithm.

This use of the inside-outside algorithm to estimate the rule probabilities for a grammar is actually a kind of limited use of inside-outside. The inside-outside algorithm can actually be used not only to set the rule probabilities, but even to induce

the grammar rules themselves. It turns out, however, that grammar induction is so difficult that inside-outside by itself is not a very successful grammar inducer; see the end notes for pointers to other grammar induction algorithms.

14.4 PROBLEMS WITH PCFGs

While probabilistic context-free grammars are a natural extension to context-free grammars, they have two main problems as probability estimators:

poor independence assumptions: CFG rules impose an independence assumption on probabilities, resulting in poor modeling of structural dependencies across the parse tree.

lack of lexical conditioning: CFG rules don't model syntactic facts about specific words, leading to problems with subcategorization ambiguities, preposition attachment, and coordinate structure ambiguities.

Because of these problems, most current probabilistic parsing models use some augmented version of PCFGs, or modify the Treebank-based grammar in some way. In the next few sections after discussing the problems in more detail we will introduce some of these augmentations.