14.4.2 Lack of sensitivity to lexical dependencies

A second class of problems with PCFGs is their lack of sensitivity to the words in the parse tree. Words do play a role in PCFGs, since the parse probability includes the probability of a word given a part-of-speech (i.e., from rules like $ V \rightarrow sleep $, NN → book, etc).

But it turns out that lexical information is useful in other places in the grammar, such as in resolving prepositional phrase attachment (PP) ambiguities. Since prepositional phrases in English can modify a noun phrase or a verb phrase, when a parser finds a prepositional phrase, it must decide where to attach it into the tree. Consider the following examples:

Workers dumped sacks into a bin.

Fig. 14.5 shows two possible parse trees for this sentence; the one on the left is the correct parse; Fig. 14.6 shows another perspective on the preposition attachment problem, demonstrating that resolving the ambiguity in Fig. 14.5 is equivalent to deciding whether to attach the prepositional phrase into the rest of the tree at the NP or VP nodes; we say that the correct parse requires VP attachment while the incorrect parse implies NP attachment.

Why doesn't a PCFG already deal with PP attachment ambiguities? Note that the two parse trees in Fig. 14.5 have almost the exact same rules; they differ only in that the left-hand parse has this rule:

$$ VP\to VBD NP PP $$

原书第 521 页

Figure 14.5 Two possible parse trees for a prepositional phrase attachment ambiguity. The left parse is the sensible one, in which ‘into a bin’ describes the resulting location of the sacks. In the right incorrect parse, the sacks to be dumped are the ones which are already ‘into a bin’, whatever that could mean.

Figure 14.6 Another view of the preposition attachment problem; should the PP on the right attach to the VP or NP nodes of the partial parse tree on the left?

while the right-hand parse has these:

$$ VP\to VBD NP $$

$$ NP\ \to\ NPP $$

Depending on how these probabilities are set, a PCFG will always either prefer NP attachment or VP attachment. As it happens, NP attachment is slightly more common in English, and so if we trained these rule probabilities on a corpus, we might always prefer NP attachment, causing us to misparse this sentence.

But suppose we set the probabilities to prefer the VP attachment for this sentence. Now we would misparse the following sentence which requires NP attachment:

(14.20) fishermen caught tons of herring

原书第 522 页

What is the information in the input sentence which lets us know that (14.20) requires NP attachment while (14.19) requires VP attachment?

It should be clear that these preferences come from the identities of the verbs, nouns and prepositions. It seems that the affinity between the verb dumped and the preposition into is greater than the affinity between the noun sacks and the preposition into, thus leading to VP attachment. On the other hand in (14.20), the affinity between tons and of is greater than that between caught and of, leading to NP attachment.

Thus in order to get the correct parse for these kinds of examples, we need a model which somehow augments the PCFG probabilities to deal with these lexical dependency statistics for different verbs and prepositions.

Coordination ambiguities are another case where lexical dependencies are the key to choosing the proper parse. Fig. 14.7 shows an example from Collins (1999), with two parses for the phrase dogs in houses and cats. Because dogs is semantically a better conjunct for cats than houses (and because dogs can't fit inside cats) the parse [dogs in [NP houses and cats]] is intuitively unnatural and should be dispreferred. The two parses in Fig. 14.7, however, have exactly the same PCFG rules and thus a PCFG will assign them the same probability.

(a)

(b)

Figure 14.7 An instance of coordination ambiguity. Although the left structure is intuitively the correct one, a PCFG will assign them identically probabilities since both structure use the exact same rules. After Collins (1999).

In summary, we have shown in this section and the previous one that probabilistic context-free grammars are incapable of modeling important structural and lexical dependencies. In the next two sections we sketch current methods for augmenting PCFGs to deal with both these issues.

14.5 IMPROVING PCFGs BY SPLITTING AND MERGING NONTERMINALS

Let's start with the first of the two problems with PCFGs mentioned above: their inability to model structural dependencies, like the fact that NPs in subject position tend to be pronouns, where NPs in object position tend to have full lexical (non-pronominal)

原书第 523 页

form. How could we augment a PCFG to correctly model this fact? One idea would be to \textit{split} the NP non-terminal into two versions: one for subjects, one for objects. Having two nodes (e.g., $ NP_{subject} $ and $ NP_{object} $) would allow us to correctly model their different distributional properties, since we would have different probabilities for the rule $ NP_{subject} \to PRP $ and the rule $ NP_{object} \to PRP $.

One way to implement this intuition of splits is to do parent annotation (Johnson, 1998), in which we annotate each node with its parent in the parse tree. Thus a node NP which is the subject of the sentence, and hence has parent S, would be annotated NP^S, while a direct object NP, whose parent is VP, would be annotated NP^VP. Fig. 14.8 shows an example of a tree produced by a grammar that parent annotates the phrasal non-terminals (like NP and VP).

Figure 14.8 A standard PCFG parse tree (a) and one which has parent annotation on the nodes which aren't preterminal (b). All the non-terminal nodes (except the preterminal part-of-speech nodes) in parse (b) have been annotated with the identity of their parent.

In addition to splitting these phrasal nodes, we can also improve a PCFG by splitting the preterminal part-of-speech nodes (Klein and Manning, 2003b). For example, different kinds of adverbs (RB) tend to occur in different syntactic positions: the most common adverbs with ADVP parents are also and now, with VP parents are n't and not, and with NP parents only and just. Thus adding tags like RB^ADVP, RB^VP, and RB^NP can be useful in improving PCFG modeling.

Similarly, the Penn Treebank tag IN is used to mark a wide variety of parts-of-speech, including subordinating conjunctions (while, as, if), complementizers (that, for), and prepositions (of, in, from). Some of these differences can be captured by parent annotation (subordinating conjunctions occur under S, prepositions under PP), while others require specifically splitting the pre-terminal nodes. Fig. 14.9 shows an example from Klein and Manning (2003b), where even a parent annotated grammar incorrectly parses works as a noun in to see if advertising works. Splitting preterminals to allow if to prefer a sentential complement results in the correct verbal parse.

In order to deal with cases where parent annotation is insufficient, we can also hand-write rules that specify a particular node split based on other features of the tree. For example to distinguish between complementizer IN and subordinating conjunction IN, both of which can have the same parent, we could write rules conditioned on other aspects of the tree such as the lexical identity (the lexeme that is likely to be a complementizer, as a subordinating conjunction).

原书第 524 页

Figure 14.9 An incorrect parse even with a parent annotated parse (left). The correct parse (right), was produced by a grammar in which the pre-terminal nodes have been split, allowing the probabilistic grammar to capture the fact that if prefers sentential complements; adapted from Klein and Manning (2003b).

Node-splitting is not without problems; it increases the size of the grammar, and hence reduces the amount of training data available for each grammar rule, leading to overfitting. Thus it is important to split to just the correct level of granularity for a particular training set. While early models involved hand-written rules to try to find an optimal number of rules (Klein and Manning, 2003b), modern models automatically search for the optimal splits. The split and merge algorithm of Petrov et al. (2006), for example starts with a simple X-bar grammar, and then alternately splits the non-terminals, and merges together non-terminals, finding the set of annotated nodes which maximizes the likelihood of the training set treebank. As of the time of this writing, the performance of the Petrov et al. (2006) algorithm as the best of any known parsing algorithm on the Penn Treebank.

14.6 PROBABILISTIC LEXICALIZED CFGs

The previous section showed that a simple probabilistic CKY algorithm for parsing raw PCFGs can achieve extremely high parsing accuracy if the grammar rule symbols are redesigned via automatic splits and merges.

In this section, we discuss an alternative family of models in which instead of modifying the grammar rules, we modify the probabilistic model of the parser to allow for lexicalized rules. The resulting family of lexicalized parsers includes the well-known Collins parser (Collins, 1999) and Charniak parser (Charniak, 1997), both of which are publicly available and widely used throughout natural language processing.

We saw in Sec. ?? in Ch. 12 that syntactic constituents could be associated with a lexical head, and we defined a lexicalized grammar in which each non-terminal in

原书第 525 页

the tree is annotated with its lexical head, where a rule like $ VP \rightarrow VBD\ NP\ PP $ would be extended as:

$$ VP(dumped)\to VBD(dumped)NP(sacks)PP(into) $$

In the standard type of lexicalized grammar we actually make a further extension, which is to associate the head tag, the part-of-speech tags of the headwords, with the nonterminal symbols as well. Each rule is thus lexicalized by both the headword and the head tag of each constituent resulting in a format for lexicalized rules like:

$$ \mathrm{VP}(\mathrm{dumped},\mathrm{VBD})\rightarrow\mathrm{VBD}(\mathrm{dumped},\mathrm{VBD})\mathrm{NP}(\mathrm{sacks},\mathrm{NNS})\mathrm{PP}(\mathrm{into},\mathrm{IN}) $$

We show a lexicalized parse tree with head tags in Fig. 14.10, extended from Fig. ??.

Figure 14.10 A lexicalized tree, including head tags, for a WSJ sentence, adapted from Collins (1999). Below we show the PCFG rules that would be needed for this parse tree, internal rules on the left, and lexical rules on the right.

In order to generate such a lexicalized tree, each PCFG rule must be augmented to identify one right-hand side constituent to be the head daughter. The headword for a

原书第 526 页

node is then set to the headword of its head daughter, and the head tag to the part-of-speech tag of the headword. Recall that we gave in Fig. ?? a set of hand-written rules for identifying the heads of particular constituents.

A natural way to think of a lexicalized grammar is like parent annotation, i.e. as a simple context-free grammar with many copies of each rule, one copy for each possible headword/head tag for each constituent. Thinking of a probabilistic lexicalized CFG in this way would lead to the set of simple PCFG rules shown below the tree in Fig. 14.10.

Note that Fig. 14.10 shows two kinds of rules: lexical rules, which express the expansion of a preterminal to a word, and internal rules, which express the other rule expansions. We need to distinguish these kinds of rules in a lexicalized grammar because they are associated with very different kinds of probabilities. The lexical rules are deterministic, i.e., have probability 1.0, since a lexicalized preterminal like NN(bin, NN) can only expand to the word bin. But for the internal rules we will need to estimate probabilities.

Suppose we were to treat a probabilistic lexicalized CFG like a really big CFG that just happened to have lots of very complex non-terminals and estimate the probabilities for each rule from maximum likelihood estimates. Thus, using Eq. 14.18, the MLE estimate for the probability for the rule $ P(VP(\text{dumped}, VBD) \rightarrow VBD(\text{dumped}, VBD) $ $ NP(\text{sacks}, NNS) $ $ PP(\text{into}, P)) $ would be:

$$ \begin{aligned}&P(VP(dumped,VBD)\rightarrow VBD(dumped,VBD)NP(sacks,NNS)PP(into,P))\\=&\frac{Count(VP(dumped,VBD)\rightarrow VBD(dumped,VBD)NP(sacks,NNS)PP(into,P))}{Count(VP(dumped,VBD))}\end{aligned} $$

But there's no way we can get good estimates of counts like those in (14.23), because they are so specific: we're very unlikely to see many (or even any) instances of a sentence with a verb phrase headed by dumped that has one NP argument headed by sacks and a PP argument headed by into. In other words, counts of fully lexicalized PCFG rules like this will be far too sparse and most rule probabilities will come out zero.

The idea of lexicalized parsing is to make some further independence assumptions to break down each rule, so that we would estimate the probability

$$ P\left(VP(dumped,VBD)\rightarrow VBD(dumped,VBD)NP(sacks,NNS)PP(into,P)\right) $$

as the product of smaller independent probability estimates for which we could acquire reasonable counts. The next section summarizes one such method, the Collins parsing method.