Until now, you have seen sentences which resulted in a single parse tree. But what if you encounter an ambiguous sentence and grammar which could lead to multiple parse trees?
Consider the following sentence: “Look at the man with one eye.” There are two possible meanings of the sentence:
- Look at the man using only one of your eyes.
- Look at the man who has one eye.
Similarly, in the previous segment, you had built two parse trees for another ambiguous sentence – “the man caught fish with a net”.
In general, since natural languages are inherently ambiguous (at least for computers to understand), there are often cases where multiple parse trees are possible. In such cases, we need a way to make the algorithms figure out the most likely parse tree.
Prof. Srinath will demonstrate a few more examples to explain ambiguities in sentences and techniques to solve them.
Note
In the above video, at 4:14, the professor incorrectly points out that the first parsed tree is interpreted as “the man saw a dog and the man had a telescope with him”
S=NP VP
VP= V NP
It should be interpreted as ” the man saw a dog which had a telescope”
This is because “the dog with a telescope” falls under a single NP.
You saw examples of sentences where ambiguities lead to multiple parse trees. Note that both top-down and bottom-up techniques will generate multiple parse trees. None of these trees is grammatically incorrect, but some of these are improbable to occur in normal conversations. To identify which of these trees is the most probable, we use the notion of probability.
Probabilistic Context-Free Grammars (PCFGs) are used when we want to find the most probable parsed structure of the sentence. PCFGs are grammar rules, similar to what you have seen, along with probabilities associated with each production rule. For example, an example production rule is as follows:
NP -> Det N (0.5) | N (0.3) |N PP (0.2)
It means that the probability of an NP breaking down to a ‘Det N’ is 0.50, to an ‘N’ is 0.30 and to an ‘N PP’ is 0.20. Note that the sum of probabilities is 1.00.
In the following lecture, Prof. Srinath explains the concept of PCFG in detail.
Let’s now learn how to implement PCFG in Python. Jupyter notebook has been attached for your reference.
You studied the idea of CFGs and PCFGs and how to build PCFG-based parse trees using NLTK. Apart from what we have covered, there are a few other non-trivial problems to address in PCFGs, one being that of computing the probabilities of production rules.
The solution is to learn these probabilities from some pre-tagged corpus where a large number of sentences have been parsed manually. Having access to such a corpus (such as the Penn Treebank), one can compute the probabilities by counting the frequencies of production rules. This is similar to how we computed the transition and emission probabilities in HMMs.
A detailed study of PCFGs is beyond the scope of this course, though you are encouraged to refer to the additional resources provided below.
Next, you will study the Chomsky Normal Form.
Additional Resources
- For a further detailed study of PCFGs, refer to chapter 12, Statistical Parsing,of the book ‘Speech and Language Processing, Daniel Jurafsky & James H. Martin’.