6.863J Natural Language ProcessingLecture 7: parsing with hierarchical structures – context-free parsingRobert C. [email protected]/9.611J Lecture 7 Sp03The Menu Bar• Administrivia:• Schedule alert: Lab2 due Weds; Lab 3 out –Monday (chunk parsing to ‘real’ parsing)• Lab time today, tomorrow• Please read notes3.pdf, englishgrammar.pdf (on web)• Agenda: • Marxist analysis – simple & post-modern• What: hierarchical representations; constituents, representation• How: constituent or ‘context-free’ parsing (next time – how to do it fast)• Why: to extract ‘meaning’6.863J/9.611J Lecture 7 Sp03Motivation• What, How, and Why• What: word chunks behave as units, like words or endings (morphemes), like ing• How: we have to recover these from input• Why: chunks used to discover meaning• Parsing: mapping from strings to structured representation6.863J/9.611J Lecture 7 Sp03Programming languagesprintf ("/charset [%s", (re_opcode_t) *(p - 1) == charset_not ? "^" : "");assert (p + *p < pend);for (c = 0; c < 256; c++)if (c / 8 < *p && (p[1 + (c/8)] & (1 << (c % 8)))) {/* Are we starting a range? */if (last + 1 == c && ! inrange) {putchar ('-');inrange = 1;}/* Have we broken a range? */else if (last + 1 != c && inrange) {putchar (last);inrange = 0;}if (! inrange)putchar (c);last = c;}§ Easy to parse.§ Designed that way!6.863J/9.611J Lecture 7 Sp03Natural languages§ No {} () [] to indicate scope & precedence§ Lots of overloading (arity varies)§ Grammar isn’t known in advance!§ Context-free grammar not best formalismprintf "/charset %s", re_opcode_t *p - 1 == charset_not ? "^" : ""; assert p + *p < pend; for c = 0; c < 256; c++ if c / 8 < *p && p1 + c/8 & 1 << c % 8 Are we starting a range? if last + 1 == c && ! inrange putchar '-'; inrange = 1; Have we broken a range? else if last + 1 != c && inrange putchar last;inrange = 0; if ! inrange putchar c; last = c;6.863J/9.611J Lecture 7 Sp03How: The parsing problemPARSERGrammarscorercorrect test treestestsentencesaccuracyRecent parsers quite accurate6.863J/9.611J Lecture 7 Sp03Syntactic Parsing• Declarative formalisms like CFGs define the legal strings of a language but don’t specify how to recognize or assign structure to them• Parsing algorithms specify how to recognize the strings of a language and assign each string one or more syntactic structures• Parse trees useful for grammar checking, semantic analysis, MT, QA, information extraction, speech recognition…and almost every task in NLP6.863J/9.611J Lecture 7 Sp03Applications of parsing (1/2)§ Machine translation (Alshawi 1996, Wu 1997, ...)English Chinesetreeoperations§ Speech synthesis from parses (Prevost 1996)The government plans to raise income tax.The government plans to raise income tax the imagination.§ Speech recognition using parsing (Chelba et al 1998)Put the file in the folder. Put the file and the folder.6.863J/9.611J Lecture 7 Sp03Applications of parsing§ Grammar checking (Microsoft)§ Indexing for information retrieval (Woods 72-1997)... washing a car with a hose ... vehicle maintenance§ Information extraction (Keyser, Chomsky ’62 to Hobbs 1996)§NY Times§archive§Database§query6.863J/9.611J Lecture 7 Sp03Why: Q&A systems (lab 4)(top-level)Shall I clear the database? (y or n) y>John saw Mary in the parkOK.>Where did John see MaryIN THE PARK.>John gave Fido to MaryOK.>Who gave John FidoI DON'T KNOW>Who gave Mary FidoJOHN>John saw FidoOK.>Who did John seeFIDO AND MARY6.863J/9.611J Lecture 7 Sp03Why: express ‘long distance’ relationships via adjacency• The guy that we know in Somerville likes ice-cream• Who did the guy who lives in Somerville see __?SNP+sg VP+sgSThe guythat we know inSom.V NPlikesice-cream6.863J/9.611J Lecture 7 Sp03Why: recover meaning from structureJohn ate ice-cream → ate(John, ice-cream)-This must be done from structure -Actually want something like λxλy ate(x,y)How?6.863J/9.611J Lecture 7 Sp03Why: recover meaning from structureSNP VPVNPJohnateice-cream= λy.ate (y, ice-cream)VP(NP)= ate (john , icecream)ice-creamjohnλxλy.ate(y, x)6.863J/9.611J Lecture 7 Sp03Why: Parsing for the Turing Test§ Most linguistic properties are defined over hierarchical structure§ One needs to parse to see subtle distinctionsSara likes her. (her ≠ Sara)Sara thinks that someone likes her. (her = or ≠ Sara)Sara dislikes anyone’s criticism of her. (her = Sara or her ≠ Sara)Who did John see? → For which x, x a person, likes(Bill, x)Distinction here is based on hierarchical structure = scopein natural language6.863J/9.611J Lecture 7 Sp03Structure must be recovered whodid SVVPxSNP‘gap’ orempty elementsee6.863J/9.611J Lecture 7 Sp03What is the structure that matters?Turns out to be SCOPE for natural languages!S6.863J/9.611J Lecture 7 Sp03The elements1. What: hierarchical representations (anything with recursion) using phrasesAKA “constituents”2. How: context-free parsing (plus…)3. Why: (meaning)6.863J/9.611J Lecture 7 Sp03Networks to context-free grammars (CFGs) and back: 1-1 correspondenceSentence:NP VPNP:VP:S→NP VPNameDet NounVerb NPVP→Verb NPNP→NameNP→DetNoun+ terminal expansionrules6.863J/9.611J Lecture 7 Sp03Added information• FSA represents pure linear relation: what can precede or (follow) what• CFG/RTN adds a new predicate: dominate• Claim: The dominance and precedence relations amongst the words exhaustively describe its syntactic structure• When we parse, we are recovering these predicates6.863J/9.611J Lecture 7 Sp03How do we move from linear to hierarchical?sawtheguyBushSentence:Noun phrase:“splice out” commonsubnetsWe already have the machinery for this…6.863J/9.611J Lecture 7 Sp03Use of epsilon transitions (‘jump’ arcs) – they consume no inputSentence:S-0S-1S-2verbNP-0NP-1NP-3determinernounεεVP-0 VP-1 VP-2εNPVPεεVerb phrasesubnetεNounphrasesubnet…note that no input isconsumed during jump6.863J/9.611J Lecture 7 Sp03This will work… with one catch• Consider tracing through “the guy ate the ice-cream”• What happens when we get to the second noun phrase????• Where do we return to?• Epsilon transition takes us back to different points6.863J/9.611J Lecture 7 Sp03What: Context-free grammars (CFG)S(entence)→NP VPVP→V NPNP→Det NN → pizza, N → guy, Det → the } pre-terminals, lexical entriesV → ateA context-free grammar (CFG):Sets of terminals
View Full Document
Unlocking...