Transcript Advanced NLP - Massachusetts Institute of Technology

Parsing and Syntax
Syntactic Formalisms: Historic
Perspective
• “Syntax” comes from Greek word “syntaxis”, meaning
“setting out together or arrangement”
• Early grammars: 4th century BC
– Panini compiled Sanskrit grammar
• Idea of constituency
– Bloomfield (1914): method for breaking up sentence into a
hierarchy of units
– Harris (1954): substitutability test for constituent definition
• Formal work on Syntax goes back to Chomsky’s PhD
thesis in 1950s
*Some slides in this lecture are adapted from slides of Michael Collins
Syntactic Structure
A Real Tree
What can we Learn from Syntactic
Tree?
• Part-of-speech for each word
(N=noun, V=verb, P=preposition)
• Constituent structure
Noun phrase: “the apartment”
Verb phrase: “robbed the apartment”
• Relationship structure
“the burglar” is the subject of “robbed”
Context-Free Grammars
A Context-Free Grammar for English
Left-Most Derivation
Derivation Example
Properties of CFGs
Ambiguous Sentence
Ambiguous Sentence
More Ambiguity
Syntactic Ambiguity
• Prepositional phrases
They cooked the beans in the pot on the stove with handles.
• Particle vs preposition
The puppy tore up the staircase.
• Complement structure
She knows you like the back of her hand.
• Gerund vs. participial adjective.
Visiting relatives can be boring
• Modifier scope within NPs
Plastic cup holder
(examples are compiled by Dan Klein)
Human Processing
• Garden Path:
The horse raced past the barn fell.
The man who hunts ducks out on weekends
• Ambiguity maintenance
Have the police … eaten their supper?
come in and look around
taken out and shot
A Probabilistic Context-Free Grammar
Example
Properties of PCFGs
Deriving a PCFG from a Corpus
Algorithms for PCFG
Chomsky Normal Form
A Dynamic Programming Algorithm for
the Max
A Dynamic Programming Algorithm for
the Max (cont.)
A Dynamic Programming Algorithm for
the Max (cont.)
Runtime
A Dynamic Programming Algorithm
for the Sum
A Dynamic Algorithm for the Sum
(cont.)
A Dynamic Programming Algorithm for
the Sum (cont.)
Weaknesses of PCFGs
• Lack of sensitivity to lexical information
• Lack of sensitivity to structural frequencies
PP Attachment Ambiguity
PP Attachment Ambiguity
Structural Preferences: Close
Attachment