G22.2590 - Natural Language Processing -- Spring 2008 -- Prof. Grishman

Assignment #9

1.  [2 points] With the grammar
s  =  np vp
vp =  v np pp
vp =  v np
np =  n
np =  n pp
pp =  p np
the sentence “Delis serve pizza with relish.” gets two parses.  Suppose we were given a training corpus of 5 sentences, with their parses:
(s (np (n Men) (pp (p of) (np (n distinction)))) (vp (v like) (np (n broccoli))))
(s (np (n Men)) (vp (v like)  (np (n ham)   (pp (p with) (np (n eggs))))))
(s (np (n Men)) (vp (v serve) (np (n ham)   (pp (p with) (np (n eggs))))))
(s (np (n Men)) (vp (v serve) (np (n eggs)) (pp (p with) (np (n gusto)))))
(s (np (n Men)) (vp (v serve) (np (n eggs)) (pp (p to)   (np (n customers)))))
Suppose we used these five parses to train a probabilistic CFG.  What probability would be assigned to each production?  What probability would be assigned to the two parses for “Delis serve pizza with relish.”?  In your calculation, consider only the probabilities of the productions;  we are not concerned with the probabilities of generating specific lexical items.

2.  [2 points]  (a) Would the conclusion change if the probability of the expansion of the vp node were conditioned on the head of the vp?  In other words, if we used the conditional probability p(r(n) | n, h(n)) only for the productions expanding vp.  Show how you obtained your conclusion (show the revised probabilities for the vp productions and the two parses).

(b) Make the same comparison (between non-lexicalized and lexicalized probabilities) for the two parses of the sentence "Men like pizza with relish."

Due April 3th.