1 of 26

Dependency Parsing

Introduction

Christopher Manning

2 of 26

Dependency Grammar and �Dependency Structure

Dependency syntax postulates that syntactic structure consists of lexical items linked by 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

Brownback

Senator

nsubjpass

auxpass

prep

nn

immigration

conj

by

cc

and

ports

pobj

prep

on

pobj

Republican

Kansas

pobj

prep

of

appos

Christopher Manning

3 of 26

Relation between phrase structure and dependency structure

A dependency grammar has a notion of a head. Officially, CFGs don’t.
But modern linguistic theory and all modern statistical parsers (Charniak, Collins, Stanford, …) do, via hand-written phrasal “head rules”:

The head of a Noun Phrase is a noun/number/adj/…
The head of a Verb Phrase is a verb/modal/….

The head rules can be used to extract a dependency parse from a CFG parse

The closure of dependencies give constituency from a dependency tree
But the dependents of a word must be at the same level (i.e., “flat”) – there can be no VP!

Christopher Manning

4 of 26

Methods of Dependency Parsing

Dynamic programming (like in the CKY algorithm)

You can do it similarly to lexicalized PCFG parsing: an O(n⁵) algorithm

Eisner (1996) gives a clever algorithm that reduces the complexity to O(n³), by producing parse items with heads at the ends rather than in the middle

Graph algorithms

You create a Maximum Spanning Tree for a sentence

McDonald et al.’s (2005) MSTParser scores dependencies independently using a ML classifier (he uses MIRA, for online learning, but it could be MaxEnt)

Constraint Satisfaction

Edges are eliminated that don’t satisfy hard constraints. Karlsson (1990), etc.

“Deterministic parsing”

Greedy choice of attachments guided by machine learning classifiers

MaltParser (Nivre et al. 2008) – discussed in the next segment

Christopher Manning

5 of 26

Dependency Conditioning Preferences

What are the sources of information for dependency parsing?

Bilexical affinities [issues 🡪 the] is plausible
Dependency distance mostly with nearby words
Intervening material

Dependencies rarely span intervening verbs or punctuation

Valency of heads

How many dependents on which side are usual for a head?

ROOT Discussion of the outstanding issues was completed .

Christopher Manning

6 of 26

Quiz question!

Consider this sentence:

Retail sales drop in April cools afternoon market trading.

Which word are these words a dependent of?

sales
April
afternoon
trading

Christopher Manning

7 of 26

Dependency Parsing

Introduction

Christopher Manning

8 of 26

Greedy Transition-Based Parsing

MaltParser

Christopher Manning

9 of 26

MaltParser�[Nivre et al. 2008]

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

Christopher Manning

10 of 26

Basic transition-based dependency parser

Start: σ = [ROOT], β = w₁, …, w_n, A = ∅

Shift σ, w_i|β, A 🡺 σ|w_i, β, A
Left-Arc_r σ|w_i, w_j|β, A 🡺 σ, w_j|β, A∪{r(w_j,w_i)}
Right-Arc_r σ|w_i, w_j|β, A 🡺 σ, w_i|β, A∪{r(w_i,w_j)}

Finish: β = ∅

Notes:

Unlike the regular presentation of the CFG reduce step, dependencies combine one thing from each of stack and buffer

Christopher Manning

Notes:

Unlike the regular presentation of a CFG reduce step, dependencies combine one thing from each of stack and buffer

The simplest form of a shift-reduce dependency parser has 3 actions: shift, and then a left-arc and a right-arc operation. They are like reductions: They introduce a new dependency arc and reduce the number of items present in the stack or buffer.

If you’ve seen CFG shift-reduce parsers, note that the odd thing here is that the left-arc and right-arc create a dependency from one thing on the stack and one thing at the head of the buffer, rather than from only things on the stack. This simplifies the definition, and has become standard.

This version isn’t the simplest version, but the most widely used version, the so-called “arc-eager” version. In a regular shift reduce parser, a head has to have found all its dependents before it can be attached. In this form, a left head can immediately take a a word as a dependent in the and have it shift onto the stack. It’s dependents will be found later, and then it will be removed with the operation called “reduce”

This version complicates things (the Left-Arc needs a precondition, so you can’t make a dependent of something that is already a dependent of something. But being able to make attachment decisions in both directions immediately like this keeps the stack small and has generally been found to work best in systems that use machine learning classifiers to choose between actions.

11 of 26

Actions (“arc-eager” dependency parser)

Start: σ = [ROOT], β = w₁, …, w_n, A = ∅

Left-Arc_r σ|w_i, w_j|β, A 🡺 σ, w_j|β, A∪{r(w_j,w_i)}

Precondition: r’ (w_k, w_i) ∉ A, w_i ≠ ROOT

Right-Arc_r σ|w_i, w_j|β, A 🡺 σ|w_i|w_j, β, A∪{r(w_i,w_j)}
Reduce σ|w_i, β, A 🡺 σ, β, A

Precondition: r’ (w_k, w_i) ∈ A

Shift σ, w_i|β, A 🡺 σ|w_i, β, A

Finish: β = ∅

This is the common “arc-eager” variant: a head can immediately take a right dependent, before its dependents are found

Christopher Manning

The simplest form of a shift-reduce dependency parser has 3 actions: shift, and then a left-arc and a right-arc operation. They are like reductions: They introduce a new dependency arc and reduce the number of items present in the stack or buffer.

If you’ve seen CFG shift-reduce parsers, note that the odd thing here is that the left-arc and right-arc create a dependency from one thing on the stack and one thing at the head of the buffer, rather than from only things on the stack. This simplifies the definition, and has become standard.

This version isn’t the simplest version, but the most widely used version, the so-called “arc-eager” version. In a regular shift reduce parser, a head has to have found all its dependents before it can be attached. In this form, a left head can immediately take a a word as a dependent in the and have it shift onto the stack. It’s dependents will be found later, and then it will be removed with the operation called “reduce”

This version complicates things (the Left-Arc needs a precondition, so you can’t make a dependent of something that is already a dependent of something. But being able to make attachment decisions in both directions immediately like this keeps the stack small and has generally been found to work best in systems that use machine learning classifiers to choose between actions.

12 of 26

Example

Happy children like to play with their friends .

[ROOT] [Happy, children, …] ∅

Shift [ROOT, Happy] [children, like, …] ∅

LA_amod[ROOT] [children, like, …] {amod(children, happy)} = A₁

Shift [ROOT, children] [like, to, …] A₁

LA_nsubj[ROOT] [like, to, …] A₁ ∪ {nsubj(like, children)} = A₂

RA_root [ROOT, like] [to, play, …] A₂ ∪{root(ROOT, like) = A₃

Shift [ROOT, like, to] [play, with, …] A₃

LA_aux [ROOT, like] [play, with, …] A₃∪{aux(play, to) = A₄

RA_xcomp[ROOT, like, play] [with their, …] A₄∪{xcomp(like, play) = A₅

Left-Arc_r σ|w_i, w_j|β, A 🡺 σ, w_j|β, A∪{r(w_j,w_i)}

Precondition: (w_k, r’, w_i) ∉ A, w_i ≠ ROOT

Right-Arc_r σ|w_i, w_j|β, A 🡺 σ|w_i|w_j, β, A∪{r(w_i,w_j)}
Reduce σ|w_i, β, A 🡺 σ, β, A

Precondition: (w_k, r’, w_i) ∈ A

Shift σ, w_i|β, A 🡺 σ|w_i, β, A

Christopher Manning

13 of 26

Example

Happy children like to play with their friends .

RA_xcomp[ROOT, like, play] [with their, …] A₄∪{xcomp(like, play) = A₅

RA_prep[ROOT, like, play, with] [their, friends, …] A₅∪{prep(play, with) = A₆

Shift[ROOT, like, play, with, their] [friends, .] A₆

LA_poss [ROOT, like, play, with] [friends, .] A₆∪{poss(friends, their) = A₇

RA_pobj [ROOT, like, play, with, friends] [.] A₇∪{pobj(with, friends) = A₈

Reduce [ROOT, like, play, with] [.] A₈

Reduce [ROOT, like, play] [.] A₈

Reduce [ROOT, like] [.] A₈

RA_punc [ROOT, like, .] [] A₈∪{punc(like, .) = A₉

You terminate as soon as the buffer is empty. Dependencies = A₉

Left-Arc_r σ|w_i, w_j|β, A 🡺 σ, w_j|β, A∪{r(w_j,w_i)}

Precondition: (w_k, r’, w_i) ∉ A, w_i ≠ ROOT

Right-Arc_r σ|w_i, w_j|β, A 🡺 σ|w_i|w_j, β, A∪{r(w_i,w_j)}
Reduce σ|w_i, β, A 🡺 σ, β, A

Precondition: (w_k, r’, w_i) ∈ A

Shift σ, w_i|β, A 🡺 σ|w_i, β, A

Christopher Manning

14 of 26

MaltParser�[Nivre et al. 2008]

We have left to explain how we choose the next action
Each action is predicted by a discriminative classifier (often SVM, could be maxent classifier) over each legal move

Max of 4 untyped choices, max of |R| × 2 + 2 when typed
Features: top of stack word, POS; first in buffer word, POS; etc.

There is NO search (in the simplest and usual form)

But you could do some kind of beam search if you wish

The model’s accuracy is slightly below the best LPCFGs (evaluated on dependencies), but
It provides close to state of the art parsing performance
It provides VERY fast linear time parsing

Christopher Manning

15 of 26

Evaluation of Dependency Parsing: �(labeled) dependency accuracy

ROOT She saw the video lecture

0 1 2 3 4 5

Gold

2 She nsubj
0 saw root
5 the det
5 video nn
2 lecture dobj

Parsed

2 She nsubj
0 saw root
4 the det
5 video nsubj
2 lecture ccomp

Acc = # correct deps

# of deps

UAS = 4 / 5 = 80%

LAS = 2 / 5 = 40%

Christopher Manning

16 of 26

Representative performance numbers

The CoNLL-X (2006) shared task provides evaluation numbers for various dependency parsing approaches over 13 languages

MALT: LAS scores from 65–92%, depending greatly on language/treebank

Here we give a few UAS numbers for English to allow some comparison to constituency parsing

Parser	UAS%
Sagae and Lavie (2006) ensemble of dependency parsers	92.7
Charniak (2000) generative, constituency	92.2
Collins (1999) generative, constituency	91.7
McDonald and Pereira (2005) – MST graph-based dependency	91.5
Yamada and Matsumoto (2003) – transition-based dependency	90.4

Christopher Manning

17 of 26

Projectivity

Dependencies from a CFG tree using heads, must be projective

There must not be any crossing dependency arcs when the words are laid out in their linear order, with all arcs above the words.

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 ?

Christopher Manning

18 of 26

Handling non-projectivity

The arc-eager algorithm we presented only builds projective dependency trees
Possible directions to head:

Just declare defeat on nonprojective arcs
Use a dependency formalism which only admits projective representations (a CFG doesn’t represent such structures…)
Use a postprocessor to a projective dependency parsing algorithm to identify and resolve nonprojective links
Add extra types of transitions that can model at least most non-projective structures
Move to a parsing mechanism that does not use or require any constraints on projectivity (e.g., the graph-based MSTParser)

Christopher Manning

19 of 26

Greedy Transition-Based Parsing

MaltParser

Christopher Manning

20 of 26

Dependencies encode relational structure

Relation Extraction with Stanford Dependencies

Christopher Manning

21 of 26

Dependency paths identify �relations like protein interaction

[Erkan et al. EMNLP 07, Fundel et al. 2007]

KaiC 🡸nsubj interacts prep_with🡺 SasA

KaiC 🡸nsubj interacts prep_with🡺 SasA conj_and🡺 KaiA

KaiC 🡸nsubj interacts prep_with🡺 SasA conj_and🡺 KaiB

demonstrated

results

KaiC

interacts

rythmically

nsubj

The

compl

det

ccomp

that

nsubj

KaiB

KaiA

SasA

conj_and

advmod

prep_with

Christopher Manning

22 of 26

Stanford Dependencies

[de Marneffe et al. LREC 2006]

The basic dependency representation is projective
It can be generated by postprocessing headed phrase structure parses (Penn Treebank syntax)
It can also be generated directly by dependency parsers, such as MaltParser, or the Easy-First Parser

jumped

boy

over

the

little

prep

nsubj

det

amod

pobj

fence

det

Christopher Manning

23 of 26

Graph modification to facilitate semantic analysis

Bell, based in LA, makes and distributes

electronic and computer products.

makes

and

nsubj

dobj

products

computer

conj

cc

and

electronic

amod

Bell

in

prep

partmod

based

pobj

LA

cc

conj

distributes

Christopher Manning

24 of 26

Graph modification to facilitate semantic analysis

Bell, based in LA, makes and distributes

electronic and computer products.

makes

nsubj

dobj

products

computer

conj_and

electronic

amod

Bell

prep_in

partmod

based

LA

conj_and

distributes

amod

nsubj

Christopher Manning

25 of 26

BioNLP 2009/2011 relation extraction shared tasks [Björne et al. 2009]

Christopher Manning

26 of 26

Dependencies encode relational structure

Relation Extraction with Stanford Dependencies

Christopher Manning