Week 5: Lecture 1
Syntax -CKY, PCFGs
Week 5: Lecture 1
CKY Algorithm
Week 5: Lecture 1
Let n be the number of words in the input. Think about n + 1 lines separating them, numbered 0 to n.
xij will denote the words between line i and j
We build a table so that xij contains all the possible non-terminal spanning for words between line i and j.
We build the Table bottom-up.
2 / 14
CKY Algorithm
Week 5: Lecture 1
Let n be the number of words in the input. Think about n + 1 lines separating them, numbered 0 to n.
xij will denote the words between line i and j
We build a table so that xij contains all the possible non-terminal spanning for words between line i and j.
We build the Table bottom-up.
Home Exercise
Use CKY algorithm to find the parse tree for “Book the flight through Houston” using the CNF form shown in the previous slide.
2 / 14
Week 5: Lecture 1
CKY for CFG
Week 5: Lecture 1
CKY for CFG
Week 5: Lecture 1
What about Ambiguities?
Probabilistic Context-free grammars (PCFGs)
Week 5: Lecture 1
6 / 14
Probabilistic Context-free grammars (PCFGs)
Week 5: Lecture 1
6 / 14
Week 5: Lecture 1
A Simple PCFG (in CNF)
Week 5: Lecture 1
Example Trees
Week 5: Lecture 1
Example Trees
Probability of trees and strings
Week 5: Lecture 1
P(t): The probability of tree is the product of the probabilities of the rules used to generate it
P(w1n): The probability of the string is the sum of the probabilities of the trees which have that string as their yield
Week 5: Lecture 1
Tree and String probabilities
11 / 14
Week 5: Lecture 1
“Book the dinner flight”
12 / 14
Week 5: Lecture 1
“Book the dinner flight”
12 / 14
“Book the dinner flight”
Week 5: Lecture 1
Probabilities
Parse tree 1: .05 × .20 × .30 × .20 × .60 × .20 × .75 × .10 × .30 = 1.62 × 10−6
Parse tree 2: .05 × .05 × .30 × .20 × .60 × .75 × .10 × .15 × .75 × .30 =
2.28 × 10−7
12 / 14
Features of PCFGs
Week 5: Lecture 1
As the number of possible trees for a given input grows, a PCFG gives some idea of the plausibility of a particular parse
But the probability estimates are based purely on structural factors, and do not factor in lexical co-occurrence. Thus, PCFG does not give a very good idea of the plausibility of the sentence.
13 / 14
Features of PCFGs
As the number of possible trees for a given input grows, a PCFG gives some idea of the plausibility of a particular parse
But the probability estimates are based purely on structural factors, and do not factor in lexical co-occurrence. Thus, PCFG does not give a very good idea of the plausibility of the sentence.
Real text tends to have grammatical mistakes. PCFG avoids this problem by ruling out nothing, but by giving implausible sentences a low probability
Week 5: Lecture 1
13 / 14
Features of PCFGs
As the number of possible trees for a given input grows, a PCFG gives some idea of the plausibility of a particular parse
But the probability estimates are based purely on structural factors, and do not factor in lexical co-occurrence. Thus, PCFG does not give a very good idea of the plausibility of the sentence.
Real text tends to have grammatical mistakes. PCFG avoids this problem by ruling out nothing, but by giving implausible sentences a low probability
In practice, a PCFG is a worse language model for English than an n-gram model
Week 5: Lecture 1
13 / 14
Features of PCFGs
As the number of possible trees for a given input grows, a PCFG gives some idea of the plausibility of a particular parse
But the probability estimates are based purely on structural factors, and do not factor in lexical co-occurrence. Thus, PCFG does not give a very good idea of the plausibility of the sentence.
Real text tends to have grammatical mistakes. PCFG avoids this problem by ruling out nothing, but by giving implausible sentences a low probability
In practice, a PCFG is a worse language model for English than an n-gram model
All else being equal, the probability of a smaller tree is greater than a larger tree
Week 5: Lecture 1
13 / 14
Important Questions?
Week 5: Lecture 1
14 / 14
Important Questions?
Week 5: Lecture 1
14 / 14
Important Questions?
Week 5: Lecture 1
14 / 14