600.465 - Intro to NLP - J. Eisner 1Weighted Parsing, Probabilistic Parsing600.465 - Intro to NLP - J. Eisner 2Our bane: Ambiguity John saw Mary  Typhoid Mary Phillips screwdriver Marynote how rare rules interact I see a bird  is this 4 nouns – parsed like “city park scavenger bird”?rare parts of speech, plus systematic ambiguity in noun sequences Time flies like an arrow Fruit flies like a banana Time reactions like this one Time reactions like a chemistor is it just an NP?600.465 - Intro to NLP - J. Eisner 3Our bane: Ambiguity John saw Mary  Typhoid Mary Phillips screwdriver Marynote how rare rules interact I see a bird  is this 4 nouns – parsed like “city park scavenger bird”?rare parts of speech, plus systematic ambiguity in noun sequences Time | flies like an arrow NP VP Fruit flies | like a banana NP VP Time | reactions like this one V[stem] NP Time reactions | like a chemist S PPor is it just an NP?600.465 - Intro to NLP - J. Eisner 4How 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 …time 1 flies 2 like 3 an 4 arrow 50NP 3Vst 31NP 4VP 42P2V53Det 14N81 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 31NP 4VP 42P2V53Det 14N81 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 101NP 4VP 42P2V53Det 14N81 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 10S81NP 4VP 42P2V53Det 14N81 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 10S8S131NP 4VP 42P2V53Det 14N81 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 10S8S131NP 4VP 42P2V53Det 14N81 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 10S8S131NP 4VP 42P2V53Det 1 NP 104N81 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 10S8S131NP 4VP 42P2V53Det 1 NP 104N81 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 10S8S131NP 4VP 42P2V5PP 123Det 1 NP 104N81 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 10S8S131NP 4VP 42P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S131NP 4VP 42P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S131NP 4VP 4NP 182P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S131NP 4VP 4NP 18S212P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S131NP 4VP 4NP 18S21VP 182P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S131NP 4VP 4NP 18S21VP 182P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S13NP 241NP 4VP 4NP 18S21VP 182P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S13NP 24S221NP 4VP 4NP 18S21VP 182P2V5PP 12VP 163Det 1 NP 104N81 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 10S8S13NP 24S22S271NP 4VP 4NP 18S21VP 182P2V5PP 12VP 163Det 1 NP 104N81 S  NP VP6 S  Vst NP2 S  S PP1 VP  V NP2 VP  VP PP1 NP  Det N2 NP  NP PP3 NP  …