6 891 Lecture 4 September 20 2005 Parsing and Syntax II Overview Weaknesses of PCFGs Heads in context free rules Dependency representations of parse trees Two models making use of dependencies Weaknesses of PCFGs Lack of sensitivity to lexical information Lack of sensitivity to structural frequencies S VP NP NNP Vt NP IBM bought NNP Lotus PROB P S NP VP S P VP V NP VP P NP NNP NP P NP NNP NP P NNP IBM NNP P Vt bought Vt P NNP Lotus NNP Another Case of PP Attachment Ambiguity a S VP NP NNS PP VP workers VBD NP IN dumped NNS into sacks NP DT NN a bin b S VP NP NNS workers NP VBD dumped PP NP NNS IN sacks into NP DT NN a bin a Rules S NP VP NP NNS VP VP PP VP VBD NP NP NNS PP IN NP NP DT NN NNS workers VBD dumped NNS sacks IN into DT a NN bin b Rules S NP VP NP NNS NP NP PP VP VBD NP NP NNS PP IN NP NP DT NN NNS workers VBD dumped NNS sacks IN into DT a NN bin If P NP NP PP NP P VP VP PP VP then b is more probable else a is more probable Attachment decision is completely independent of the words A Case of Coordination Ambiguity a NP NP PP NP NNS IN NP dogs in NNS houses CC NP and NNS cats b NP PP NP NNS dogs NP IN in NP CC NP NNS and NNS houses cats a Rules NP NP CC NP NP NP PP NP NNS PP IN NP NP NNS NP NNS NNS dogs IN in NNS houses CC and NNS cats b Rules NP NP CC NP NP NP PP NP NNS PP IN NP NP NNS NP NNS NNS dogs IN in NNS houses CC and NNS cats Here the two parses have identical rules and therefore have identical probability under any assignment of PCFG rule probabilities Structural Preferences Close Attachment a b NP PP NP NN NP IN NP IN NN IN PP NP PP NP NN PP NP IN NP NP NP NN NN NN Example president of a company in Africa Both parses have the same rules therefore receive same probability under a PCFG Close attachment structure a is twice as likely in Wall Street Journal text Structural Preferences Close Attachment Previous example John was believed to have been shot by Bill Here the low attachment analysis Bill does the shooting contains same rules as the high attachment analysis Bill does the believing so the two analyses receive same probability Heads in Context Free Rules Add annotations specifying the head of each rule S VP VP VP NP NP PP NP Vi Vt VP DT NP IN VP NP PP NN PP NP Vi Vt NN NN NN DT IN IN sleeps saw man woman telescope the with in Note S sentence VP verb phrase NP noun phrase PP prepositional phrase DT determiner Vi intransitive verb Vt transitive verb NN noun IN preposition More about Heads Each context free rule has one special child that is the head of the rule e g S VP NP NP Vt DT VP NP NN NN VP is the head Vt is the head NN is the head A core idea in linguistics X bar Theory Head Driven Phrase Structure Grammar Some intuitions The central sub constituent of each rule The semantic predicate in each rule Rules which Recover Heads An Example of rules for NPs If the rule contains NN NNS or NNP Choose the rightmost NN NNS or NNP Else If the rule contains an NP Choose the leftmost NP Else If the rule contains a JJ Choose the rightmost JJ Else If the rule contains a CD Choose the rightmost CD Else Choose the rightmost child e g NP NP NP NP NP DT DT NP DT DT NNP NN PP JJ NN NNP Rules which Recover Heads An Example of rules for VPs If the rule contains Vi or Vt Choose the leftmost Vi or Vt Else If the rule contains an VP Choose the leftmost VP Else Choose the leftmost child e g VP VP Vt VP NP PP Adding Headwords to Trees S VP NP DT NN the lawyer NP Vt questioned DT NN the witness S questioned NP lawyer DT the NN lawyer the lawyer VP questioned Vt questioned questioned NP witness DT the NN witness the witness Adding Headwords to Trees S questioned NP lawyer VP questioned DT the NN lawyer the lawyer Vt questioned questioned NP witness DT the NN witness the witness A constituent receives its headword from its head child S VP NP NP Vt DT VP NP NN S receives headword from VP VP receives headword from Vt NP receives headword from NN Chomsky Normal Form A context free grammar G N R S in Chomsky Normal Form is as follows N is a set of non terminal symbols is a set of terminal symbols R is a set of rules which take one of two forms X Y1 Y2 for X N and Y1 Y2 N X Y for X N and Y S N is a distinguished start symbol We can nd the highest scoring parse under a PCFG in this form in O n3 R time where n is the length of the string being parsed and R is the number of rules in the grammar see the dynamic programming algorithm in the previous notes A New Form of Grammar We de ne the following type of lexicalized grammar N is a set of non terminal symbols is a set of terminal symbols R is a set of rules which take one of three forms X h Y1 h Y2 w for X N and Y1 Y2 N and h w X h Y1 w Y2 h for X N and Y1 Y2 N and h w X h h for X N and h S N is a distinguished start symbol A New Form of Grammar The new form of grammar looks just like a Chomsky normal form CFG but with potentially O 2 N 3 possible rules Naively parsing an n word sentence using the dynamic programming algorithm will take O n3 2 N 3 time But can be huge Crucial observation at most O n2 N 3 rules can be applicable to a given sentence w1 w2 wn of length n This is because any rules which contain a lexical item that is not one of w1 wn can be safely discarded The result we can parse in O n5 N 3 time Adding Headtags to Trees S questioned Vt NP lawyer NN DT VP questioned Vt NN Vt the lawyer questioned NP witness NN DT NN the witness Also propagate part of speech tags up the trees We ll see soon why this is useful Heads and Semantics like Bill Clinton S VP NP Bill Vt NP likes Clinton Syntactic structure Semantics Logical form Predicate argument structure Adding Predicate Argument Structure to our Grammar Identify words …