Fundamentals of SNLP

Lecture 1

Syntax: Constituency Parsing

Krishnendu Ghosh

Two Views of Linguistic Structure

• Phrase Structure

​

• Dependency Structure

​

​

Constituency (Phrase Structure)

• Phrase structure organizes words into nested constituents.

​

• How do we know what is a constituent? (Not that linguists don’t argue about some cases.)

Constituency (Phrase Structure)

Distribution: a constituent behaves as a unit that can appear in different places:

​

John talked [to the children] [about drugs].

John talked [about drugs] [to the children].

*John talked drugs to the children about.

​

Substitution/expansion/pro-forms:

I sat [on the box/right on top of the box/there].

​

​

Coordination, regular internal structure, no intrusion, fragments, semantics, …

A Phrase Structure Grammar

S → NP VP

VP → V NP

VP → V NP PP

NP → NP NP

NP → NP PP

NP → N

NP → e

PP → P NP

​

people fish tanks

people fish with rods

N → people

N → fish

N → tanks

N → rods

V → people

V → fish

V → tanks

P → with

Phrase Structure Grammars

= Context-Free Grammars (CFGs)

• G = (T, N, S, R)
• T is a set of terminal symbols
• N is a set of nonterminal symbols
• S is the start symbol (S ∈ N)
• R is a set of rules/productions of the form X → γ
• X ∈ N and γ ∈ (N ∪ T)*

​

• A grammar G generates a language L.

Context-Free Grammar

G = (T, C, N, S, L, R)

• T is a set of terminal symbols
• C is a set of preterminal symbols
• N is a set of nonterminal symbols
• S is the start symbol (S ∈ N)
• L is the lexicon, a set of items of the form X → x
• X ∈ P and x ∈ T
• R is the grammar, a set of items of the form X → γ
• X ∈ N and γ ∈ (N ∪ C)*
• By usual convention, S is the start symbol, but in statistical NLP, we usually have an extra node at the top (ROOT, TOP)
• We usually write e for an empty sequence, rather than nothing

Context-Free Grammar

Example 1:

• E → E + T | T
• T → T * F | F
• F → (E) | id

Context-Free Grammar

Example 2. Let us consider this grammar: E-> E + E | E*E | id, We can create two parse tree from this grammar to obtain a string id + id * id.

Probabilistic Context-Free Grammar

G = (T, N, S, R, P)

• T is a set of terminal symbols
• N is a set of nonterminal symbols
• S is the start symbol (S ∈ N)
• R is a set of rules/productions of the form X → γ
• P is a probability function
• P: R → [0,1]

​

• A grammar G generates a language model L.

​

​

A PCFG

S → NP VP 1.0

VP → V NP 0.6

VP → V NP PP 0.4

NP → NP NP 0.1

NP → NP PP 0.2

NP → N 0.7

PP → P NP 1.0

N → people 0.5

N → fish 0.2

N → tanks 0.2

N → rods 0.1

V → people 0.1

V → fish 0.6

V → tanks 0.3

P → with 1.0

Probability of Trees and Strings

P(t) – The probability of a tree t is the product of the probabilities of the rules used to generate it.

​

P(s) – The probability of the string s is the sum of the probabilities of the trees which have that string as their yield

​

P(s) = Σj P(s, t) where t is a parse of s

= Σj P(t)

Tree and String Probabilities

s = people fish tanks with rods

P(t1) = 1.0 × 0.7 × 0.4 × 0.5 × 0.6 × 0.7

× 1.0 × 0.2 × 1.0 × 0.7 × 0.1

= 0.0008232

P(t2) = 1.0 × 0.7 × 0.6 × 0.5 × 0.6 × 0.2

× 0.7 × 1.0 × 0.2 × 1.0 × 0.7 × 0.1

= 0.00024696

P(s) = P(t1) + P(t2)

= 0.0008232 + 0.00024696

= 0.00107016

​

​

Verb attachment

Noun attachment

Grammar Transforms

Restricting the grammar form for efficient parsing

Chomsky Normal Form

• All rules are of the form X → YZ or X → w
• X,Y,Z ∈ N and w ∈ T
• A transformation to this form doesn’t change the weak generative capacity of a CFG
• That is, it recognizes the same language
• But maybe with different trees
• Empties and unaries are removed recursively
• n-ary rules are divided by introducing new nonterminals (n > 2)

Chomsky Normal Form

• With some extra book-keeping in symbol names, you can even reconstruct the same trees with a detransform
• In practice full Chomsky Normal Form is a pain
• Reconstructing n-aries is easy
• Reconstructing unaries/empties is trickier
• Binarization is crucial for cubic time CFG parsing
• The rest isn’t necessary; it just makes the algorithms cleaner and a bit quicker

Chomsky Normal Form

S → NP VP

VP → V NP

VP → V NP PP

NP → NP NP

NP → NP PP

NP → N

NP → e

PP → P NP

​

N → people

N → fish

N → tanks

N → rods

V → people

V → fish

V → tanks

P → with

​

Chomsky Normal Form

S → NP VP

S → VP

VP → V NP

VP → V

VP → V NP PP

VP → V PP

NP → NP NP

NP → NP

NP → NP PP

NP → PP

NP → N

PP → P NP

PP → P

N → people

N → fish

N → tanks

N → rods

V → people

V → fish

V → tanks

P → with

​

Eliminate e

Chomsky Normal Form

S → NP VP

VP → V NP

S → V NP

VP → V

S → V

VP → V NP PP

S → V NP PP

VP → V PP

S → V PP

NP → NP NP

NP → NP

NP → NP PP

NP → PP

NP → N

PP → P NP

PP → P

N → people

N → fish

N → tanks

N → rods

V → people

V → fish

V → tanks

P → with

​

Chomsky Normal Form

S → NP VP

VP → V NP

S → V NP

VP → V

VP → V NP PP

S → V NP PP

VP → V PP

S → V PP

NP → NP NP

NP → NP

NP → NP PP

NP → PP

NP → N

PP → P NP

PP → P

N → people

N → fish

N → tanks

N → rods

V → people

S → people

V → fish

S → fish

V → tanks

S → tanks

P → with

​

Chomsky Normal Form

S → NP VP

VP → V NP

S → V NP

VP → V NP PP

S → V NP PP

VP → V PP

S → V PP

NP → NP NP

NP → NP

NP → NP PP

NP → PP

NP → N

PP → P NP

PP → P

N → people

N → fish

N → tanks

N → rods

V → people

S → people

VP → people

V → fish

S → fish

VP → fish

V → tanks

S → tanks

VP → tanks

P → with

Chomsky Normal Form

S → NP VP

VP → V NP

S → V NP

VP → V NP PP

S → V NP PP

VP → V PP

S → V PP

NP → NP NP

NP → NP PP

NP → P NP

PP → P NP

NP → people

NP → fish

NP → tanks

NP → rods

V → people

S → people

VP → people

V → fish

S → fish

VP → fish

V → tanks

S → tanks

VP → tanks

P → with

PP → with

​

Chomsky Normal Form

S → NP VP

VP → V NP

S → V NP

VP → V @VP_V

@VP_V → NP PP

S → V @S_V

@S_V → NP PP

VP → V PP

S → V PP

NP → NP NP

NP → NP PP

NP → P NP

PP → P NP

NP → people

NP → fish

NP → tanks

NP → rods

V → people

S → people

VP → people

V → fish

S → fish

VP → fish

V → tanks

S → tanks

VP → tanks

P → with

PP → with

​

Before vs After Binarization

ROOT

S

NP

VP

N

people

V

NP

PP

P

NP

rods

with

tanks

fish

N

N

Constituency Parsing

​

​

​

​

​

​

​

​

fish people fish tanks