14.1.1 PCFGs for Disambiguation

A PCFG assigns a probability to each parse tree $ T $ (i.e., each \textit{derivation}) of a sentence $ S $. This attribute is useful in \textit{disambiguation}. For example, consider the two parses of the sentence “Book the dinner flights” shown in Fig. 14.2. The sensible parse on the left means “Book flights that serve dinner”. The nonsensical parse on the right, however, would have to mean something like “Book flights on behalf of ‘the dinner’?”, the way that a structurally similar sentence like “Can you book John flights?” means something like “Can you book flights on behalf of John?”.

The probability of a particular parse $ T $ is defined as the product of the probabilities of all the $ n $ rules used to expand each of the $ n $ non-terminal nodes in the parse tree $ T $, (where each rule $ i $ can be expressed as $ LHS_i \to RHS_i $):

$$ P(T,S)=\prod_{i=1}^{n}P(RHS_{i}|LHS_{i}) $$

The resulting probability $P(T,S)$ is both the joint probability of the parse and the sentence, and also the probability of the parse $P(T)$. How can this be true? First, by the definition of joint probability:

$$ P(T,S)=P(T)P(S|T) $$

But since a parse tree includes all the words of the sentence, $ P(S|T) $ is 1. Thus:

$$ P(T,S)=P(T)P(S|T)=P(T) $$

The probability of each of the trees in Fig. 14.2 can be computed by multiplying together the probabilities of each of the rules used in the derivation. For example, the probability of the left tree in Figure 14.2a (call it $ T_{left} $) and the right tree (Figure 14.2b or $ T_{right} $) can be computed as follows:

$$ \begin{align*}P(T_{left})&=.05*.20*.20*.20*.75*.30*.60*.10*.40=\mathbf{2.2\times10^{-6}}\\P(T_{right})&=.05*.10*.20*.15*.75*.75*.30*.60*.10*.40=\mathbf{6.1\times10^{-7}}\end{align*} $$

We can see that the left (transitive) tree in Fig. 14.2(a) has a much higher probability than the ditransitive tree on the right. Thus this parse would correctly be chosen by a disambiguation algorithm which selects the parse with the highest PCFG probability.

Let's formalize this intuition that picking the parse with the highest probability is the correct way to do disambiguation. Consider all the possible parse trees for a given sentence S. The string of words S is called the yield of any parse tree over S. Thus out of all parse trees with a yield of S, the disambiguation algorithm picks the parse tree which is most probable given S:

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

By definition, the probability $ P(T|S) $ can be rewritten as $ P(T,S)/P(S) $, thus leading to:

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

Since we are maximizing over all parse trees for the same sentence, $ P(S) $ will be a constant for each tree, so we can eliminate it:

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

Furthermore, since we showed above that $P(T,S)=P(T)$, the final equation for choosing the most likely parse neatly simplifies to choosing the parse with the highest probability:

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