Natural Language Processing
with Deep Learning
CS224N/Ling284
Christopher Manning
Lecture 4: Dependency Parsing
Lecture Plan
Syntactic Structure and Dependency parsing
1. Syntactic Structure: Consistency and Dependency (25 mins)
2. Dependency Grammar and Treebanks (15 mins)
3. Transition-based dependency parsing (15 mins)
4. Neural dependency parsing (20 mins)
Reminders/comments:
In Assignment 3, out on Tuesday, you build a neural dependency parser using PyTorch
Start installing and learning PyTorch (Ass 3 has scaffolding)
Come to the PyTorch tutorial, Friday 10am (under the Zoom tab, not a Webinar)
Final project discussions – come meet with us; focus of Thursday class in week 4
2
1. Two views of linguistic structure: Constituency = phrase
structure grammar = context-free grammars (CFGs)
Phrase structure organizes words into nested constituents
Starting unit: words
the, cat, cuddly, by, door
Words combine into phrases
the cuddly cat, by the door
Phrases can combine into bigger phrases
the cuddly cat by the door
3
Two views of linguistic structure: Constituency = phrase structure
grammar = context-free grammars (CFGs)
Phrase structure organizes words into nested constituents.
the cat
a dog
large in a crate
barking on the table
cuddly by the door
large barking
talk to
walked behind
6
Two views of linguistic structure: Dependency structure
• Dependency structure shows which words depend on (modify, attach to, or are
arguments of) which other words.
Look in the large crate in the kitchen by the door
7
Why do we need sentence structure?
Humans communicate complex ideas by composing words together
into bigger units to convey complex meanings
Listeners need to work out what modifies [attaches to] what
A model needs to understand sentence structure in order to be
able to interpret language correctly
9
Prepositional phrase attachment ambiguity
10
Prepositional phrase attachment ambiguity
Scientists count whales from space
Scientists count whales from space
✓
❌
11
PP attachment ambiguities multiply
• A key parsing decision is how we ‘attach’ various constituents
• PPs, adverbial or participial phrases, infinitives, coordinations,
etc.
• Catalan numbers: Cn = (2n)!/[(n+1)!n!]
• An exponentially growing series, which arises in many tree-like contexts:
• E.g., the number of possible triangulations of a polygon with n+2 sides
• Turns up in triangulation of probabilistic graphical models (CS228)….12
Coordination scope ambiguity
Shuttle veteran and longtime NASA executive Fred Gregory appointed to board
Shuttle veteran and longtime NASA executive Fred Gregory appointed to board
14
Coordination scope ambiguity
15
Adjectival/Adverbial Modifier Ambiguity
16
Verb Phrase (VP) attachment ambiguity
17
Dependency paths help extract semantic interpretation –
simple practical example: extracting protein-protein interaction
KaiC çnsubj interacts nmod:with è SasA
KaiC çnsubj interacts nmod:with è SasA conj:andè KaiA
KaiC çnsubj interacts nmod:with è SasA conj:andè KaiB
[Erkan et al. EMNLP 07, Fundel et al. 2007, etc.]
demonstrated
results
KaiC
interacts
rythmically
nsubj
The
mark
det
ccomp
that
nsubj
KaiBKaiA
SasA
conj:and
conj:and
advmod
nmod:with
with and
cc
case
18
2. Dependency Grammar and Dependency Structure
Dependency syntax postulates that syntactic structure consists of relations between
lexical items, normally binary asymmetric relations (“arrows”) called dependencies
submitted
Bills were
Senatorby
immigration
Brownback
andon
ports
Republican
of
Kansas
19
Dependency Grammar and Dependency Structure
Dependency syntax postulates that syntactic structure consists of relations between
lexical items, normally binary asymmetric relations (“arrows”) called dependencies
The arrows are
commonly typed
with the name of
grammatical
relations (subject,
prepositional object,
apposition, etc.)
submitted
Bills were
Senatorby
nsubj:pass aux obl
case
immigration
conj
Brownback
cc
andon
case
nmod
ports flat
Republican
of
case
nmod
Kansas
appos
20
Dependency Grammar and Dependency Structure
Dependency syntax postulates that syntactic structure consists of relations between
lexical items, normally binary asymmetric relations (“arrows”) called dependencies
An arrow connects a head
(governor, superior,
regent) with a dependent
(modifier, inferior,
subordinate)
Usually, dependencies
form a tree (a connected,
acyclic, single-root graph)
submitted
Bills were
Senatorby
nsubj:pass aux obl
case
immigration
conj
Brownback
cc
andon
case
nmod
ports flat
Republican
of
case
nmod
Kansas
appos
21
Pāṇini’s grammar (c. 5th century BCE)
Gallery: http://wellcomeimages.org/indexplus/image/L0032691.html
CC BY 4.0 File:Birch bark MS from Kashmir of the Rupavatra Wellcome L0032691.jpg
22
Dependency Grammar/Parsing History
• The idea of dependency structure goes back a long way
• To Pāṇini’s grammar (c. 5th century BCE)
• Basic approach of 1st millennium Arabic grammarians
• Constituency/context-free grammar is a new-fangled invention
• 20th century invention (R.S. Wells, 1947; then Chomsky 1953, etc.)
• Modern dependency work is often sourced to Lucien Tesnière (1959)
• Was dominant approach in “East” in 20th Century (Russia, China, …)
• Good for free-er word order, inflected languages like Russian (or Latin!)
• Used in some of the earliest parsers in NLP, even in the US:
• David Hays, one of the founders of U.S. computational linguistics, built early (first?)
dependency parser (Hays 1962) and published on dependency grammar in Language
23
ROOT Discussion of the outstanding issues was completed .
• Some people draw the arrows one way; some the other way!
• Tesnière had them point from head to dependent – we follow that convention
• We usually add a fake ROOT so every word is a dependent of precisely 1 other node
Dependency Grammar and Dependency Structure
24
The rise of annotated data & Universal Dependencies treebanks
Brown corpus (1967; PoS tagged 1979); Lancaster-IBM Treebank (starting late 1980s);
Marcus et al. 1993, The Penn Treebank, Computational Linguistics;
Universal Dependencies: http://universaldependencies.org/
25
The rise of annotated data
Starting off, building a treebank seems a lot slower and less useful than writing a grammar
(by hand)
But a treebank gives us many things
• Reusability of the labor
• Many parsers, part-of-speech taggers, etc. can be built on it
• Valuable resource for linguistics
• Broad coverage, not just a few intuitions
• Frequencies and distributional information
• A way to evaluate NLP systems
26
What are the sources of information for dependency parsing?
1. Bilexical affinities The dependency [discussion à issues] is plausible
2. Dependency distance Most dependencies are between nearby words
3. Intervening material Dependencies rarely span intervening verbs or punctuation
4. Valency of heads How many dependents on which side are usual for a head?
ROOT Discussion of the outstanding issues was completed .
Dependency Conditioning Preferences
27
Dependency Parsing
• A sentence is parsed by choosing for each word what other word (including ROOT) it is
a dependent of
• Usually some constraints:
• Only one word is a dependent of ROOT
• Don’t want cycles A → B, B → A
• This makes the dependencies a tree
• Final issue is whether arrows can cross (be non-projective) or not
I give a on neuraltalk tomorrowROOT ’ll networks
28
• Definition of a projective parse: There are no crossing dependency arcs when the
words are laid out in their linear order, with all arcs above the words
• Dependencies corresponding to a CFG tree must be projective
• I.e., by forming dependencies by taking 1 child of each category as head
• Most syntactic structure is projective like this, but dependency theory normally does
allow non-projective structures to account for displaced constituents
• You can’t easily get the semantics of certain constructions right without these
nonprojective dependencies
Who did Bill buy the coffee from yesterday ?
Projectivity
29
3. Methods of Dependency Parsing
1. Dynamic programming
Eisner (1996) gives a clever algorithm with complexity O(n3), by producing parse items
with heads at the ends rather than in the middle
2. Graph algorithms
You create a Minimum Spanning Tree for a sentence
McDonald et al.’s (2005) MSTParser scores dependencies independently using an ML
classifier (he uses MIRA, for online learning, but it can be something else)
Neural graph-based parser: Dozat and Manning (2017) et seq. – very successful!
3. Constraint Satisfaction
Edges are eliminated that don’t satisfy hard constraints. Karlsson (1990), etc.
4. “Transition-based parsing” or “deterministic dependency parsing”
Greedy choice of attachments guided by good machine learning classifiers
E.g., MaltParser (Nivre et al. 2008). Has proven highly effective.
30
Greedy transition-based parsing [Nivre 2003]
• A simple form of greedy discriminative dependency parser
• The parser does a sequence of bottom-up actions
• Roughly like “shift” or “reduce” in a shift-reduce parser, but the “reduce” actions are
specialized to create dependencies with head on left or right
• The parser has:
• a stack σ, written with top to the right
• which starts with the ROOT symbol
• a buffer β, written with top to the left
• which starts with the input sentence
• a set of dependency arcs A
• which starts off empty
• a set of actions
31
Basic transition-based dependency parser
Start: σ = [ROOT], β = w1, …, wn , A = ∅
1. Shift σ, wi|β, A è σ|wi, β, A
2. Left-Arcr σ|wi|wj, β, A è σ|wj, β, A∪{r(wj,wi)}
3. Right-Arcr σ|wi|wj, β, A è σ|wi, β, A∪{r(wi,wj)}
Finish: σ = [w], β = ∅
32
Arc-standard transition-based parser
(there are other transition schemes …)
Analysis of “I ate fish”
ate fish[root]
Start
I
[root]
Shift
I ate fish
ate[root] fish
Shift
I
Start: σ = [ROOT], β = w1, …, wn , A = ∅
1. Shift σ, wi|β, A è σ|wi, β, A
2. Left-Arcr σ|wi|wj, β, A è
σ|wj, β, A∪{r(wj,wi)}
3. Right-Arcr σ|wi|wj, β, A è
σ|wi, β, A∪{r(wi,wj)}
Finish: σ = [w], β = ∅
33
Arc-standard transition-based parser
Analysis of “I ate fish”
ate[root] ate[root]
Left Arc
I
A +=
nsubj(ate → I)
ate fish[root] ate fish[root]
Shift
ate[root] [root]
Right Arc
A +=
obj(ate → fish)fish ate
ate[root] [root]
Right Arc
A +=
root([root] → ate)
Finish
34
MaltParser [Nivre and Hall 2005]
• We have left to explain how we choose the next action 🤷
• Answer: Stand back, I know machine learning!
• Each action is predicted by a discriminative classifier (e.g., softmax classifier) over each
legal move
• Max of 3 untyped choices; max of |R| × 2 + 1 when typed
• Features: top of stack word, POS; first in buffer word, POS; etc.
• There is NO search (in the simplest form)
• But you can profitably do a beam search if you wish (slower but better): You keep k
good parse prefixes at each time step
• The model’s accuracy is fractionally below the state of the art in dependency parsing,
but
• It provides very fast linear time parsing, with high accuracy – great for parsing the web
35
Conventional Feature Representation
Feature templates: usually a combination of 1–3
elements from the configuration
Indicator features
0 0 0 1 0 0 1 0 0 0 1 0binary, sparse
dim =106 –107
…
36
Evaluation of Dependency Parsing: (labeled) dependency accuracy
ROOT She saw the video lecture
0 1 2 3 4 5
Gold
1 2 She nsubj
2 0 saw root
3 5 the det
4 5 video nn
5 2 lecture obj
Parsed
1 2 She nsubj
2 0 saw root
3 4 the det
4 5 video nsubj
5 2 lecture ccomp
Acc = # correct deps
# of deps
UAS = 4 / 5 = 80%
LAS = 2 / 5 = 40%
37
Handling non-projectivity
• The arc-standard algorithm we presented only builds projective dependency trees
• Possible directions to head:
1. Just declare defeat on nonprojective arcs 🤷
2. Use dependency formalism which only has projective representations
• A CFG only allows projective structures; you promote head of projectivity violations
3. Use a postprocessor to a projective dependency parsing algorithm to identify and
resolve nonprojective links
4. Add extra transitions that can model at least most non-projective structures (e.g.,
add an extra SWAP transition, cf. bubble sort)
5. Move to a parsing mechanism that does not use or require any constraints on
projectivity (e.g., the graph-based MSTParser or Dozat and Manning (2017))
38
4. Why do we gain from a neural dependency parser?
Indicator Features Revisited
• Problem #1: sparse
• Problem #2: incomplete
• Problem #3: expensive computation
More than 95% of parsing time is consumed by
feature computation
Neural Approach:
learn a dense and compact feature representation
0.1
dense
dim = ~1000
0.9 -0.2 0.3 -0.1 -0.5…
39
A neural dependency parser [Chen and Manning 2014]
• Results on English parsing to Stanford Dependencies:
• Unlabeled attachment score (UAS) = head
• Labeled attachment score (LAS) = head and label
Parser UAS LAS sent. / s
MaltParser 89.8 87.2 469
MSTParser 91.4 88.1 10
TurboParser 92.3 89.6 8
C & M 2014 92.0 89.7 654
40
First win: Distributed Representations
• We represent each word as a d-dimensional dense vector (i.e., word embedding)
• Similar words are expected to have close vectors.
• Meanwhile, part-of-speech tags (POS) and dependency labels are also represented as
d-dimensional vectors.
• The smaller discrete sets also exhibit many semantical similarities.
come
go
werewas
is
good
NNS (plural noun) should be close to NN (singular noun).
nummod (numerical modifier) should be close to amod (adjective modifier).
41
Extracting Tokens & vector representations from configuration
• We extract a set of tokens based on the stack / buffer positions:
s1
s2
b1
lc(s1)
rc(s1)
lc(s2)
rc(s2)
good
has
control
∅
∅
He
∅
JJ
VBZ
NN
∅
∅
PRP
∅
∅
∅
∅
∅
∅
nsubj
∅
+ +
word POS dep.
}
A concatenation
of the vector
representation of
all these is the
neural
representation of
a configuration
42
Second win: Deep Learning classifiers are non-linear classifiers
• A softmax classifier assigns classes 𝑦 ∈ 𝐶 based on inputs 𝑥 ∈ ℝ" via the probability:
• We train the weight matrix 𝑊 ∈ ℝ#×" to minimize the neg. log loss : ∑% − log 𝑝(𝑦%|𝑥%)
• Traditional ML classifiers (including Naïve Bayes, SVMs, logistic regression and softmax
classifier) are not very powerful classifiers: they only give linear decision boundaries
This can be quite limiting
à Unhelpful when a problem is complex
Wouldn’t it be cool to get these correct?
43
Neural Networks are more powerful
• Neural networks can learn much more complex functions with nonlinear decision
boundaries!
• Non-linear in the original space, linear for the softmax at the top of the neural network
Visualizations with ConvNetJS by Andrej Karpathy!
http://cs.stanford.edu/people/karpathy/convnetjs/demo/classify2d.html
44
Simple feed-forward neural network multi-class classifier
Input layer x
Hidden layer h
h = ReLU(Wx + b1)
Output layer y
y = softmax(Uh + b2)
Softmax probabilities
Log loss (cross-entropy error) will be backpropagated
to the embeddings
45
The hidden layer re-represents the input —
it moves inputs around in an intermediate
layer vector space—so it can be easily
classified with a (linear) softmax
logistic = “sigmoid” ReLU = Rectified
Linear Unit
rect(z) = max(z,0)
x is result of lookup
x(i,…,i+d) = Le
lookup + concat
Neural Dependency Parser Model Architecture
Input layer x
lookup + concat
Hidden layer h
h = ReLU(Wx + b1)
Output layer y
y = softmax(Uh + b2)
Softmax probabilities
cross-entropy error will be back-propagated
to the embeddings
46
Dependency parsing for sentence structure
47
Neural networks can accurately determine the structure of sentences,
supporting interpretation
Chen and Manning (2014) was the first simple, successful neural dependency
parser
The dense representations (and non-linear classifier) let it outperform other
greedy parsers in both accuracy and speed
Further developments in transition-based neural dependency parsing
48
This work was further developed and improved by others, including in particular at Google
• Bigger, deeper networks with better tuned hyperparameters
• Beam search
• Global, conditional random field (CRF)-style inference over the decision sequence
Leading to SyntaxNet and the Parsey McParseFace model (2016):
“The World’s Most Accurate Parser”
https://research.googleblog.com/2016/05/announcing-syntaxnet-worlds-most.html
Method UAS LAS (PTB WSJ SD 3.3)
Chen & Manning 2014 92.0 89.7
Weiss et al. 2015 93.99 92.05
Andor et al. 2016 94.61 92.79
Graph-based dependency parsers
49
• Compute a score for every possible dependency for each word
• Doing this well requires good “contextual” representations of each word token,
which we will develop in coming lectures
ROOT The big cat sat
0.5
0.3
0.8
2.0
e.g., picking the head for “big”
Graph-based dependency parsers
50
• Compute a score for every possible dependency for each word
• Doing this well requires good “contextual” representations of each word token,
which we will develop in coming lectures
• And repeat the same process for each other word
ROOT The big cat sat
0.5
0.3
0.8
2.0
e.g., picking the head for “big”
A Neural graph-based dependency parser
[Dozat and Manning 2017; Dozat, Qi, and Manning 2017]
51
• This paper revived interest in graph-based dependency parsing in a neural world
• Designed a biaffine scoring model for neural dependency parsing
• Also crucially uses a neural sequence model, something we discuss next week
• Really great results!
• But slower than the simple neural transition-based parsers
• There are n2 possible dependencies in a sentence of length n
Method UAS LAS (PTB WSJ SD 3.3
Chen & Manning 2014 92.0 89.7
Weiss et al. 2015 93.99 92.05
Andor et al. 2016 94.61 92.79
Dozat & Manning 2017 95.74 94.08