Three Useful PCFG Tasks

• Observation likelihood: To classify and order sentences.
• Most likely derivation: To determine the most likely parse tree for a sentence.
• Maximum likelihood training: To train a PCFG to fit empirical training data.

1

PCFG: Most Likely Derivation

• There is an analog to the Viterbi algorithm to efficiently determine the most probable derivation (parse tree) for a sentence.

2

Probabilistic CKY

• CKY can be modified for PCFG parsing by including in each cell a probability for each non-terminal.
• Cell[i,j] must retain the most probable derivation of each constituent (non-terminal) covering words i +1 through j together with its associated probability.
• When transforming the grammar to CNF, must set production probabilities to preserve the probability of derivations.

​

Probabilistic Grammar Conversion

S → NP VP

S → Aux NP VP

​

S → VP

​

​

​

NP → Pronoun

​

NP → Proper-Noun

​

NP → Det Nominal

Nominal → Noun

​

Nominal → Nominal Noun

Nominal → Nominal PP

VP → Verb

​

VP → Verb NP

VP → VP PP

PP → Prep NP

Original Grammar

Chomsky Normal Form

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

0.8

0.1

​

0.1

​

​

​

0.2

0.2

0.6

0.3

​

0.2

0.5

0.2

​

0.5

0.3

1.0

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

5

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

6

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

​

VP:.5*.5*.054

=.0135

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

7

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

8

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

9

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

10

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

11

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

​

NP:.6*.6*

.0024

=.000864

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

12

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

​

NP:.6*.6*

.0024

=.000864

S:.05*.5*

.000864

=.0000216

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

13

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

​

NP:.6*.6*

.0024

=.000864

S:.0000216

S:.03*.0135*

.032

=.00001296

S → NP VP

S → X1 VP

X1 → Aux NP

S → book | include | prefer

0.01 0.004 0.006

S → Verb NP

S → VP PP

NP → I | he | she | me

0.1 0.02 0.02 0.06

NP → Houston | NWA

0.16 .04

NP → Det Nominal

Nominal → book | flight | meal | money

0.03 0.15 0.06 0.06

Nominal → Nominal Noun

Nominal → Nominal PP

VP → book | include | prefer

0.1 0.04 0.06

VP → Verb NP

VP → VP PP

PP → Prep NP

Det → the | a

.6 .4

0.8

0.1

1.0

​

​

0.05

0.03

​

​

​

​

0.6

​

​

0.2

0.5

​

​

0.5

0.3

1.0

Probabilistic CKY Parser

14

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

​

NP:.6*.6*

.0024

=.000864

S:.0000216

Pick most probable

parse, i.e. take max to

combine probabilities

of multiple derivations

of each constituent in

each cell.

PCFG: Observation Likelihood

• There is an analog to Forward algorithm for HMMs called the Inside algorithm for efficiently determining how likely a string is to be produced by a PCFG.
• Can use a PCFG as a language model to choose between alternative sentences for speech recognition or machine translation.

15

Inside Algorithm

• Use CKY probabilistic parsing algorithm but combine probabilities of multiple derivations of any constituent using addition instead of max.

16

Probabilistic CKY Parser �for Inside Computation

17

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

​

NP:.6*.6*

.0024

=.000864

S:.0000216

S:..00001296

Probabilistic CKY Parser �for Inside Computation

18

Book the flight through Houston

S :.01, VP:.1,

Verb:.5

Nominal:.03

Noun:.1

Det:.6

​

Nominal:.15

Noun:.5

None

​

NP:.6*.6*.15

=.054

VP:.5*.5*.054

=.0135

S:.05*.5*.054

=.00135

None

None

None

Prep:.2

NP:.16

PropNoun:.8

PP:1.0*.2*.16

=.032

Nominal:

.5*.15*.032

=.0024

​

NP:.6*.6*

.0024

=.000864

+.0000216

=.00003456

S: .00001296

Sum probabilities

of multiple derivations

of each constituent in

each cell.

PCFG: Supervised Training

• If parse trees are provided for training sentences, a grammar and its parameters can be can all be estimated directly from counts accumulated from the tree-bank (with appropriate smoothing).

​

19

.

.

.

Tree Bank

Estimating Production Probabilities

• Set of production rules can be taken directly from the set of rewrites in the treebank.
• Parameters can be directly estimated from frequency counts in the treebank.

20

PCFG: Maximum Likelihood Training

• Given a set of sentences, induce a grammar that maximizes the probability that this data was generated from this grammar.
• Assume the number of non-terminals in the grammar is specified.
• Only need to have an unannotated set of sequences generated from the model. Does not need correct parse trees for these sentences. In this sense, it is unsupervised.

​

21

PCFG: Maximum Likelihood Training

22

John ate the apple

A dog bit Mary

Mary hit the dog

John gave Mary the cat.

​

​

.

.

.

Training Sentences

Learn the grammar itself!

Inside-Outside

• The Inside-Outside algorithm is a version of EM for unsupervised learning of a PCFG.
• Analogous to Baum-Welch (forward-backward) for HMMs
• Given the number of non-terminals, construct all possible CNF productions with these non-terminals and observed terminal symbols.
• Use EM to iteratively train the probabilities of these productions to locally maximize the likelihood of the data.
• See Manning and Schütze text for details
• Experimental results are not impressive, but recent work imposes additional constraints to improve unsupervised grammar learning.

​

Vanilla PCFG Limitations: Missing Lexical Context

• Since probabilities of productions do not rely on specific words or concepts, only general structural disambiguation is possible (e.g. prefer to attach PPs to Nominals).
• Consequently, vanilla PCFGs cannot resolve syntactic ambiguities that require semantics to resolve, e.g. ate with fork vs. meatballs.
• In order to work well, PCFGs must be lexicalized, i.e. productions must be specialized to specific words by including their head-word in their LHS non-terminals (e.g. VP-ate).

24

Example of Importance of Lexicalization

• A general preference for attaching PPs to NPs rather than VPs can be learned by a vanilla PCFG.
• But the desired preference can depend on specific words.

25

Example of Importance of Lexicalization

• A general preference for attaching PPs to NPs rather than VPs can be learned by a vanilla PCFG.
• But the desired preference can depend on specific words.

26

S

NP VP

John V NP

put the dog in the pen

X

Head Words

• Syntactic phrases usually have a word in them that is most “central” to the phrase.
• Linguists have defined the concept of a lexical head of a phrase.
• Simple rules can identify the head of any phrase by percolating head words up the parse tree.
• Head of a VP is the main verb
• Head of an NP is the main noun
• Head of a PP is the preposition
• Head of a sentence is the head of its VP

​

Lexicalized Productions

• Specialized productions can be generated by including the head word and its POS of each non-terminal as part of that non-terminal’s symbol.

S

VP

VBD NP

DT Nominal

Nominal PP

liked

IN NP

in

the

dog

NN

DT Nominal

NN

the

pen

NNP

NP

John

pen-NN

pen-NN

in-IN

dog-NN

dog-NN

dog-NN

liked-VBD

liked-VBD

John-NNP

Nominaldog-NN → Nominaldog-NN PPin-IN

Lexicalized Productions

S

VP

VP PP

DT Nominal

put

IN NP

in

the

dog

NN

DT Nominal

NN

the

pen

NNP

NP

John

pen-NN

pen-NN

in-IN

dog-NN

dog-NN

put-VBD

put-VBD

John-NNP

NP

VBD

put-VBD

VPput-VBD → VPput-VBD PPin-IN

Evaluation of Parsing: Treebanks

• English Penn Treebank: Standard corpus for testing syntactic parsing consists of 1.2 M words of text from the Wall Street Journal (WSJ).
• Typical to train on about 40,000 parsed sentences and test on an additional standard disjoint test set of 2,416 sentences.
• Chinese Penn Treebank: 100K words from the Xinhua news service.
• Other corpora existing in many languages, see the Wikipedia article “Treebank”

30

First WSJ Sentence

31

( (S

(NP-SBJ

(NP (NNP Pierre) (NNP Vinken) )

(, ,)

(ADJP

(NP (CD 61) (NNS years) )

(JJ old) )

(, ,) )

(VP (MD will)

(VP (VB join)

(NP (DT the) (NN board) )

(PP-CLR (IN as)

(NP (DT a) (JJ nonexecutive) (NN director) ))

(NP-TMP (NNP Nov.) (CD 29) )))

(. .) ))

​

Parsing Evaluation Metrics

• PARSEVAL metrics measure the fraction of the constituents that match between the computed and human parse trees. If P is the system’s parse tree and T is the human parse tree (the “gold standard”):
• Recall = (# correct constituents in P) / (# constituents in T)
• Precision = (# correct constituents in P) / (# constituents in P)
• Labeled Precision and labeled recall require getting the non-terminal label on the constituent node correct to count as correct.
• F₁ is the harmonic mean of precision and recall.

32

Constituent: N,<start>, <end>

Computing Evaluation Metrics

Correct Tree T

S

VP

Verb NP

Det Nominal

Nominal PP

book

Prep NP

through

Houston

Proper-Noun

the

flight

Noun

Computed Tree P

VP

Verb NP

Det Nominal

book

Prep NP

through

Houston

Proper-Noun

the

flight

Noun

S

VP

PP

# Constituents: 12

# Constituents: 12

# Correct Constituents: 10

Recall = 10/12= 83.3%

Precision = 10/12=83.3%

F₁ = 83.3%

Treebank Results

• Results of current state-of-the-art systems on the English Penn WSJ treebank are 91-92% labeled F₁.

34

>96% with RNNs/LSTMs/Transformers

Near-perfect accuracy now (other than

human errors)

Dependency Grammars

• An alternative to phrase-structure grammar is to define a parse as a directed graph between the words of a sentence representing dependencies between the words.

35

liked

John

dog

pen

in

the

the

liked

John

dog

pen

in

the

the

nsubj

dobj

det

det

Typed

dependency

parse

Dependency Graph from Parse Tree

• Can convert a phrase structure parse to a dependency tree by making the head of each non-head child of a node depend on the head of the head child.

36

S

VP

VBD NP

DT Nominal

Nominal PP

liked

IN NP

in

the

dog

NN

DT Nominal

NN

the

pen

NNP

NP

John

pen-NN

pen-NN

in-IN

dog-NN

dog-NN

dog-NN

liked-VBD

liked-VBD

John-NNP

liked

John

dog

pen

in

the

the

Head of a VP is the main verb

Head of an NP is the main noun

Head of a PP is the preposition

Head of a sentence is the head of its VP