Homework 3

CS 4705 Natural Language Processing

Due: November 13th at the beginning of class. Bring hard copy.

Question 1 (25 points)

Your friend decides to build a Treebank. He finally produces a corpus which contains the following three parse trees:

You then purchase the Treebank and decide to build a PCFG, and a parser, using your friend’s data.

Question 2(a): Show the PCFG that you would derive from this Treebank.

Question 2(b): Show two parse trees for the string “Jeff pronounced that Fred snored loudly”, and calculate their probabilities under the PCFG.

Question 2(c): You are shocked and dismayed, (see 2(b)), that “Jeff pronounced that Fred snored loudly” has two possible parses, and that one of them—that Jeff is doing the pronouncing loudly—has relatively high probability, in spite of it having the ADVP loudly modifying the “higher” verb, pronounced. This type of high attachment is never seen in the corpus, so the PCFG is clearly missing something. You decide to fix the Treebank, by altering some non-terminal labels in the corpus. Show one such transformation which results in a PCFG that gives zero probability to parse trees with “high” attachments. (Your solution should systematically refine some non-terminals in the Treebank, in a way that slightly increases the number of non-terminals in the grammar, but allows the grammar to capture the distinction between high and low attachment to VPs.)

Question 2 (30 points)

Suppose you want to capture the distinction between which adverbs modify which verbs not by modifying the grammar non-terminals but by incorporating lexical dependencies. For example, you know that while ``loudly’’ may equally well modify verbs like ``declare’’ and ``snore’’, the adverb ``melodically’’ could modify ``pronounce’’ but could not modify ``swam’’ while the adverb ``deeply’’ could modify a verb like ``dive’’ but not ``pronounce’’.

a.  How would you modify the Treebank your friend created to capture these facts? Describe what you would change, give some examples, and give an indication of how many changes would be needed.

b.  Show a lexical dependency grammar that could be derived from your examples.

c.  Describe how the Earley algorithm would need to be changed to handle parsing a lexical dependency grammar. What would be represented in the chart? How would it change as the grammar was parsed? Give an example.

3. Wordnet (20 points): Go to the Wordnet site (http://wordnet.princeton.edu) and answer the following questions:

a.  Using the hypernymy hierarchy, find the lowest common ancestor of sense 1 and sense 2 of the verb ``elect’’.

b.  Find the meronyms of all senses of the word university.

c.  Find the antonyms of all senses of the adjective late.

d.  Find the lowest common ancestor using the hypernym dictionary across all noun senses of gate and fence. Does distance in the hierarchy tell you anything about semantic relatedness? Why or why not?

4. Semantic Analysis (25 points): Problems 18.2 and 18.3, p. 609; problem 20.5, p. 679.