Andrew McCallum, UMass AmherstChart ParsingLecture #6Computational LinguisticsCMPSCI 591N, Spring 2006University of Massachusetts AmherstAndrew McCallum(Including slides from Jason Eisner)Andrew McCallum, UMass AmherstToday’s Main Points• Hand back In-class Exercise #2• Motivations and applications of Parsing.• Dynamic Programming for Parsing: CYK– Some hands-on practice• Discuss Programming Assignment #3“Implement CYK and build a grammar”Andrew McCallum, UMass AmherstProgramming 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!Andrew McCallum, UMass AmherstNatural languages No {} () [] to indicate scope & precedence Lots of overloading (arity varies) Grammar isn’t known in advance! Context-free grammar not best formalism printf "/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 && ! inrangeputchar '-'; inrange = 1; Have we broken a range? else if last + 1 != c&& inrange putchar last; inrange = 0; if ! inrange putchar c; last =c;Andrew McCallum, UMass AmherstThe parsing problemPARSERGrammarscorercorrect test treestestsentencesaccuracyAndrew McCallum, UMass AmherstApplications 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.Andrew McCallum, UMass AmherstApplications of parsing (2/2)• Grammar checking (Microsoft)• Indexing for information retrieval (Woods 1997) ... washing a car with a hose ... vehicle maintenance• Information extraction (Hobbs 1996) (Miller et al 2000)NY TimesarchiveDatabasepatternAndrew McCallum, UMass AmherstParsing State of the Art• Recent parsers quite accurate, e.g.,• A Maximum-Entropy-Inspired ParserEugene CharniakProceedings of NAACL-2000.• Three Generative, Lexicalised Models for StatisticalParsingMichael CollinsProceedings of ACL, 1997.• Most sentences parsed correctly, or with oneerrorAndrew McCallum, UMass AmherstLast class…• We defined a CFG,where it sits in the Chomsky hierarchy• Talked about parsing as search……through an exponential number of possible trees• Gave examples of bottom-up and top-down search.• Discussed problems:– Infinite loop with left-recursive rules– Much duplicated work in exponential space… backtrackingAndrew McCallum, UMass AmherstDynamic Programming for Parsing• Given CFG in Chomsky Normal Form,and an input string, we want to search forvalid parse trees.• What are the intermediate sub-problems?• What would the dynamic programming tablelook like?Andrew McCallum, UMass AmherstCKY algorithm, recognizer version Input: string of n words Output: yes/no (since it’s only a recognizer) Data structure: n x n table rows labeled 0 to n-1 columns labeled 1 to n cell [i,j] lists possible constituents spanning wordsbetween i and jAndrew McCallum, UMass AmherstCKY algorithm, recognizer version for i := 1 to n Add to [i-1,i] all (part-of-speech) categories for the ith word for width := 2 to n for start := 0 to n-width Define end := start + width for mid := start+1 to end-1 for every constituent X in [start,mid] for every constituent Y in [mid,end] for all ways of combining X and Y (if any) Add the resulting constituent to [start,end] if it’s not already there.N 84Det 13P 2V 52NP 4VP 41NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 5 NP → time Vst → time NP → flies VP → flies P → like V → like Det → an N → arrow1 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84Det 13P 2V 52NP 4VP 41NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84Det 13P 2V 52NP 4VP 41NP 10NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84Det 13P 2V 52NP 4VP 41NP 10S 8NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84Det 13P 2V 52NP 4VP 41NP 10S 8S 13NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84Det 13_P 2V 52_NP 4VP 41NP 10S 8S 13NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84NP 10Det 13_P 2V 52_NP 4VP 41NP 10S 8S 13NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84NP 10Det 13_P 2V 52_NP 4VP 41NP 10S 8S 13NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84NP 10Det 13PP 12_P 2V 52__NP 4VP 41_NP 10S 8S 13NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S → Vst NP2 S → S PP1 VP → V NP2 VP → VP PP1 NP → Det N2 NP → NP PP3 NP → NP NP0 PP → P NPN 84NP 10Det 13PP 12VP 16_P 2V 52__NP 4VP 41_NP 10S 8S 13NP 3Vst 30time 1 flies 2 like 3 an 4 arrow 51 S → NP VP6 S