6.863J Natural Language ProcessingLecture 13: Featured attractionInstructor: Robert C. [email protected]•863J/9•611J SP04 Lecture 13The Menu Bar• Administrivia:• Lab 3b out later today - Weds; due after vacation – April 5Agenda:Fillers & Gaps; I shrank the grammar!Features & feature grammars6•863J/9•611J SP04 Lecture 13Job 1: writing grammar rules• Three sorts of examples to handle:1. Simple declarative sentencesPoirot solved the casePoirot thoughtPoirot sent the solution to the policePoirot believed the detectives were incompetent2. Auxiliary verb sentencesP. may have been solving the case3. Unbounded dependencies: Questions and relative clausesWhich case did Poirot solveThe solution that P. sent to the police solved the case6•863J/9•611J SP04 Lecture 13Want to block:•do notovergenerate*Poirot solved; *P. may solved the case; *Which solution did P. send which solution to the police?6•863J/9•611J SP04 Lecture 13Preliminaries: phrase names•I said that ice-cream was on the tableI said ice-cream was on the table• What is the structure here?• Existence of Complementizer(COMP) before Sentence phrase, forming an “Sbar phrase” (S):SbarCompSSbar→(Comp) S6•863J/9•611J SP04 Lecture 13Sbar= Comp S• The Compitem can be that, which, …-or a displaced phrase• Also present in ‘root’ (top level) sentences (I like ice-cream) but usually we don’t ‘hear’ it (unless it’s filled by question or focus phrase) • Serves as ‘landing site’ for fillers• In embedded sentences, in English, the Compis optional• If Compis filled – then that blocks things:Who (F) do I know that John likes (G)6•863J/9•611J SP04 Lecture 13Filler-gap examplesJohn (F) is hard to please (G)It is hard to please JohnTough-movementThe guy (F) that John likes (G)John likes the guyRelative clausesBeans (F) John hates (G)John hates beansTopicalizationWho (F) did Mary see (G)?Mary saw BillWh-questionFiller-gap analogOrdinarySentenceExample6•863J/9•611J SP04 Lecture 13Fillers and gaps, redux• Fillers and Gaps summary: F, G• Filler is the displaced phrase• Gap is a phonological null(unpronounced) empty category (though it can have secondary phonological consequences: •This student (F) you want (G) to solve the problem blocks contraction between want and to into wanna• ? This student you wanna solve the problem• F-G relation represents displacement from canonical semantic argument position• Many examples of this in natural language6•863J/9•611J SP04 Lecture 13Fillers and gaps• Since ‘gap’ is NP going to empty string, we could just add rule, NP→ε• But this will overgenerate-how?• 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 SP04 Lecture 13So, 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 rules: Generalized Phrase Structure Grammar (GPSG)6•863J/9•611J SP04 Lecture 13“State-splitting” to remember wh seen (but not heard) – need new states (cf. vowel harmony, etc.)• We could encode the two possible routes by distinct chains of states, as follows:• Names not very elightening, so will use this instead:εNP VNPεwhat NP VεVNPεwhatss/npv/np np/np6•863J/9•611J SP04 Lecture 13So we have to add rules with new nonterminals to ‘name’ states…• S/NP → NP VP/NP • VP/NP → V NP/NP • NP/NP→ε• We haven’t put the auxiliary verb stuff in…• Note the ‘chain’ of slashed rules in the final structure• What happens computationally?6•863J/9•611J SP04 Lecture 13Actual ‘marks’ in the literature• Called a ‘slash category’• Ordinary category: Sbar, VP, NP• Slash category: Sbar/NP, VP/NP, NP/NP• “X/Y” is ONE atomic nonterminal• Interpret as: Subtree X is missing a Y (expanded as e) underneath• Example: Sbar/NP = Sbar missing NP underneath (see our example)6•863J/9•611J SP04 Lecture 13As for slash rules…• We need slash category introduction rule, e.g., Sbar → Comp S/NP• We need ‘elimination’ rule NP/NP→e• These are paired (why?)• We’ll need other slash categories, e.g.,6•863J/9•611J SP04 Lecture 13Need PP/NP… NPpretzeltheDetthatNSbarCompSNP VPVPPthe P.chokedNPPNPon e6•863J/9•611J SP04 Lecture 13How do we do ‘slashed rules’ systematically & formally• Step 1: form slashed categories•Basic categories:‘orginary’ nonterminals N={S, VP, NP, PP, …}•Slashed (derived) categories: α/β, α, β range over N• E.g., S/NP, S/VP, S/PP, NP/NP, NP/VP, NP/PP• Interpretation: tree rooted at α, with ‘gap’ (subtree) of type β somewhere beneath• Step 2: form slashed rulesfrom basic rules•Basic rule: S→ NP VP•Slashed rule: S/NP→ NP VP/NP• (Why not S/NP→ NP/NP VP)6•863J/9•611J SP04 Lecture 13Also have ‘subject’ gapsNPpresidenttheDetthatNSbarCompSNP VPVPPchokedNPPNPon the pretzele6•863J/9•611J SP04 Lecture 13Filler-gap configuration• Equivalent to notion of ‘scope’ for natural languages (scope of variables) ≈ Environment frame in Scheme/binding environment for ‘variables’ that are empty categories• Formally: Fillers c-command gaps (constituent command)• Definition of c-command:6•863J/9•611J SP04 Lecture 13Constraints on filler-gap relations• Can be “unbounded” on the surface, but underlyingly is successive cyclic (AKA – forms a chainlinking filler to gap)• [what (F) did John think (F) that Bill said (F) that Mary liked (G)]• Note that this F-G distance cannot exceed 1 adjacent S or NP boundary (in English)• What (F) [ do you wonder [who likes (G)]• (Note: What (F) do you wonder (F) who likes (G)is blocked)6•863J/9•611J SP04 Lecture 13Constraints on filler-gaps• Obeys structural relation called c-command• True in other languages also; also true there are multiple gaps• So, how does generalized phrase structure grammar (GPSG) handle all this?• We covered: basic rules; derived rules• Still to cover: metarules; constraints6•863J/9•611J SP04 Lecture 13Filler-gap configuration NPeSSeNP6•863J/9•611J SP04 Lecture 13C-command• A phrase α c-commands a phrase β iff the first branching node that dominates α also dominates β (blue = filler,
View Full Document