Probabilistic Context Free GrammarsLecture #14Computational LinguisticsCMPSCI 591N, Spring 2006Andrew McCallum(including slides from Jason Eisner)Andrew McCallum, UMassAmbiguity in Parsing•Time flies like an arrow.•Fruit flies like a banana.•I saw the man with the telescope.Andrew McCallum, UMassHow to solve this combinatorial explosion of ambiguity?1. First try parsing without any weird rules, throwing them in only if needed.2. Better: every rule has a weight. A tree’s weight is total weight of all its rules. Pick the overall “lightest” parse of sentence.3. Can we pick the weights automatically?We’ll get to this later …Andrew McCallum, UMassCYK ParserInput: A string of words, grammar in CNFOutput: yes/noData structure: n x n tablerows labeled 0 to n-1, columns 1 to ncell (i,j) lists constituents spanning i,jFor each i from 1 to nAdd to (i-1,i) all Nonterminals that could produce the word at (i-1,i)time 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1 4 N! 81 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 NPAndrew McCallum, UMassCYK ParserFor width from 2 to nFor start from 0 to n-widthDefine end to be start+widthFor mid from start+1 to end-1For every constituent in (start, mid)For every constituent in (mid,end)For all ways of combining them (if any)Add the resulting constituent to (start,end).time 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1 4 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10! 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1 4 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1 4 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1 4 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1 4 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 3 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 PP! 123 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 2 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 NP! 18 2 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 NP! 18S! 21 2 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 NP! 18S! 21VP! 182 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 1 NP! 4VP! 4 NP! 18S! 21VP! 182 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 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 NPtime 1 flies 2 like 3 an 4 arrow 50NP! 3Vst! 3NP! 10!S! 8S! 13 NP! 241 NP! 4VP! 4 NP! 18S! 21VP! 182 P! 2!V! 5 PP! 12VP! 163 Det! 1NP! 104 N! 81 S → NP VP6 S → Vst NP2 S → S PP1 VP → …