6.863J Natural Language ProcessingLecture 10: Feature-based grammarsRobert C. [email protected]/9.611J Lecture 10 Sp03The Menu Bar• Administrivia:• Schedule alert: Lab 3 out; due next Weds. (after that: Lab4 on semantics, 2 ways)• Lab time today, tomorrow• Please read notes3.pdf!! englishgrammar.pdf (on web)• Agenda: • Limits of context-free grammars: the trouble with tribbles• Foundation for the laboratory: empty categories• Feature-based grammars/parsing6.863J/9.611J Lecture 10 Sp03CFG Solution to complexity of language• Encode constraints into the non-terminals• Noun/verb agreementSà SgSS à PlSSgS à SgNP SgVPSgNP à SgDet SgNom• Verb subcategories:IntransVP à IntransVTransVP à TransV NP6.863J/9.611J Lecture 10 Sp03Problems with this – how much info?• Even verb subcategories not obviousJohn gave Mary the book → NP NPJohn gave the book to Mary → NP PPBut:John donated the book to the library‘Alternation’ pattern – semantic? NO!6.863J/9.611J Lecture 10 Sp03Agreement gets complex…POSSUBPOSGENDERNUMBERCASEPOSSGPOSSNPERSONTENSEDCOMPNEGVOICEVAR–Czech: AGFS3----1A----6.863J/9.611J Lecture 10 Sp03More interesting clause types• Apparently “long distance” effects: ‘displacement’ of phrases from their ‘base’ positions1. So-called ‘wh-movement’:What did John eat ?2. Topicalization (actually the same)On this day, it snowed two feet.3. Other cases: so-called ‘passive’:The eggplant was eaten by John• How to handle this?6.863J/9.611J Lecture 10 Sp03`Empty’ elements or categories• Where surface phrase is displaced from its canonical syntactic position & nothing shows on the surface• Examples:• The ice-cream was eaten vs.• John ate the ice-cream• What did John eat?• What did Bill say that that John thought the cat ate?• For What x, did Bill say… the cat ate x• Bush is too stubborn to talk to• Bush is too stubborn [x to talk to Bush]• Bush is too stubborn to talk to the Pope• Bush is too stubborn [Bush to talk to the Pope]6.863J/9.611J Lecture 10 Sp03‘missing’ or empty categories• John promised Mary ___ to leave• John promised Mary [John to leave]• Known as ‘control’• John persuaded Mary [___ to leave]• John persuaded Mary [Mary to leave]6.863J/9.611J Lecture 10 Sp03We can think of this as ‘fillers’ and ‘gaps’• Filler= the displaced item• Gap = the place where it belongs, as argument• Fillers can be NPs, PPs, S’s• Gaps are invisible- so hard to parse! (we have to guess)• Can be complex:Which book did you file__ without__ reading__ ?Which violins are these sonatas difficult to play__ on ___6.863J/9.611J Lecture 10 Sp03Gaps• Pretend “kiss” is a pure transitive verb.• Is “the president kissed” grammatical?• If so, what type of phrase is it?• the sandwich that• I wonder what • What else hasthe president kissed eSally said the president kissed eSally consumed the pickle with eSally consumed e with the pickle6.863J/9.611J Lecture 10 Sp03Gaps• Object gaps:• the sandwich that• I wonder what • What else hasthe president kissed eSally said the president kissed eSally consumed the pickle with eSally consumed e with the pickle§ Subject gaps:§ the sandwich that§ I wonder what § What else hase kissed the presidentSally said e kissed the president[how could you tell the difference?]6.863J/9.611J Lecture 10 Sp03Gaps• All gaps are really the same – a missing XP:• the sandwich that• I wonder what • What else hasthe president kissed eSally said the president kissed eSally consumed the pickle with eSally consumed e with the picklePhrases with missing NP:X[missing=NP]or just X/NP for short e kissed the presidentSally said e kissed the president6.863J/9.611J Lecture 10 Sp03Representation & computation questions again• How do we represent this displacement? (difference between underlying & surface forms)• How do we compute it? (I.e., parse sentences that exhibit it)• We want to recover the underlying structural relationship because this tells us what the predicate-argument relations are – Who did what to whom• Example: What did John eat → For which x, x a thing, did John eat x? • Note how the eat-x predicate-argument is established6.863J/9.611J Lecture 10 Sp03Representations with gaps• Let’s first look at a tree with gaps:whatDid SVVPNPSεNP‘gap’ orempty elementfiller6.863J/9.611J Lecture 10 Sp03Crisper representation:Comp SwhatAuxvdidNPSbarNP VPJeatε‘gap’ orempty element‘filler’6.863J/9.611J Lecture 10 Sp03Fillers can be arbitrarily far from gaps they match with…• What did John say that Mary thought that the cat ate___?6.863J/9.611J Lecture 10 Sp03Fillers and gaps• Since ‘gap’ is NP going to empty string, we could just add rule, NP→ε• But this will overgenerate why?• We need a way to distinguish between• What did John eat• Did John eat• How did this work in the FSA case?6.863J/9.611J Lecture 10 Sp03So, what do we need?• A rule to expand NP as the empty symbol; that’s easy enough: NP→ε• A way to make sure that NP is expanded as empty symbol iff there is a gap (in the right place) before/after it• A way to link the filler and the gap• We can do all this by futzing with the nonterminal names: Generalized Phrase Structure Grammar (GPSG)6.863J/9.611J Lecture 10 Sp03Example: relative clauses• What are they?• Noun phrase with a sentence embedded in it:• The sandwich that the president ate• What about it? What’s the syntactic representation that will make the semantics transparent?The sandwichithat the president ate ei6.863J/9.611J Lecture 10 Sp03OK, that’s the output…what are the cfg rules?• Need to expand the object of eat as an empty string• So, need rule NP→ε• But more, we need to link the head noun “the sandwich” to this position• Let’s use the fsa trick to ‘remember’something – what is that trick???• Remember?6.863J/9.611J Lecture 10 Sp03Memory trick• Use state of fsa to remember• What is state in a CFG?• The nonterminal names• We need something like vowel harmony –sequence of states = nonterminalsthe sandwich that the president ate e6.863J/9.611J Lecture 10 Sp03As a parse structureNPsandwichtheNDetthat the president ate eWhat’s this? We’ve seen it before…It’s an Sbar = Comp+S6.863J/9.611J Lecture 10 Sp03Parse structure for relative clauseNPsandwichtheDetthatNSbarCompSNP VPV NPethe P.ateNPBut how to
View Full Document
Unlocking...