NLP Programming Tutorial 12 – Dependency Parsing

NLP Programming Tutorial 12 Dependency Parsing

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 12 – Dependency Parsing

Interpreting Language is Hard!
I saw a girl with a telescope●“Parsing” resolves structural ambiguity in a formal way
2

NLP Programming Tutorial 12 – Dependency Parsing

Two Types of Parsing●Dependency: focuses on relations between words

I saw a girl with a telescope●Phrase structure: focuses on identifying phrases andtheir recursive structure
SVP
PPNPNPPRP VBD DT NN

NPINDTNN

I saw a girl with a telescope

3

NLP Programming Tutorial 12 – Dependency Parsing

Dependencies Also Resolve Ambiguity

I saw a girl with a telescope

I saw a girl with a telescope

4

NLP Programming Tutorial 12 – Dependency Parsing

Dependencies●

Typed: Label indicating relationship between words
prepnsubj

dobj
detpobjdet

I saw a girl with a telescope●

Untyped: Only which words depend

I saw a girl with a telescope

5

NLP Programming Tutorial 12 – Dependency Parsing

Dependency Parsing Methods●Shift-reduce
Predict from left-to-right● Fast (linear), but slightly less accurate?
● MaltParser●●Spanning tree
Calculate full tree at once
● Slightly more accurate, slower● MSTParser, Eda (Japanese)●●

Cascaded chunking
Chunk words into phrases, find heads, delete nonheads, repeat● CaboCha (Japanese)●6NLP Programming Tutorial 12 – Dependency Parsing

Maximum Spanning Tree●

Each dependency is an edge in a directed graph●Assign each edge a score (with machine learning)●Keep the tree with the highest score
Graph

Scored Graph

Dependency Treesawsawsaw

6girl

IaI-2-1

2

1

7a

64

girl

4girl

I
75a(Chu-Liu-Edmonds Algorithm)

7

NLP Programming Tutorial 12 – Dependency Parsing

Cascaded Chunking●Works for Japanese, which is strictly head-final●

Divide sentence into chunks, head is rightmost word

私 は 望遠鏡 で
は
私

で
望遠鏡

は
私

女 の 子 を 見たの 子 を 見た
女

で
望遠鏡

子 を 見たの女
は
私

見たで
望遠鏡
女の子を 見たはでを子
私 望遠鏡の8
女

NLP Programming Tutorial 12 – Dependency Parsing

Shift-Reduce●

Process words one-by-one left-to-right●Two data structures
Queue: of unprocessed words● Stack: of partially processed words●●At each point choose
shift: move one word from queue to stack● reduce left: top word on stack is head of second word
● reduce right: second word on stack is head of top word●●

Learn how to choose each action with a classifier
9

NLP Programming Tutorial 12 – Dependency Parsing

Shift Reduce Example
StackQueueStackI saw a girlsaw a girlshiftIQueueI
saw a girlr left

shift
I saw

sawa girl

shift

Igirl
ar leftsawa girl

II

sawI

shift
saw ar rightgirl

girla10NLP Programming Tutorial 12 – Dependency Parsing

Classification for Shift-Reduce●

Given a state:
StackQueue

saw agirlI●

Which action do we choose?
shift ?
r left ?

saw a girl

asaw

I

r right ?
girl

saw
Igirl
aI
●

Correct actions → correct tree

11

NLP Programming Tutorial 12 – Dependency Parsing

Classification for Shift-Reduce●●●●We have a weight vector for “shift” “reduce left”“reduce right”
ws wl wr
Calculate feature functions from the queue and stackφ(queue, stack)Multiply the feature functions to get scoresss = ws * φ(queue,stack)Take the highest scoress > sl && ss > sr → do shift
12

NLP Programming Tutorial 12 – Dependency Parsing

Features for Shift Reduce●Features should generally cover at least the last stack
entries and first queue entry

Word:
POS:

stack[-2]stack[-1]queue[0]sawVBDaDETgirlNN(-2 → second-to-last)(-1 → last)(0 → first)

φW-2saw,W-1a = 1

φW-1a,W0girl = 1

φW-2saw,P-1DET = 1

φW-1a,P0NN = 1

φP-2VBD,W-1a = 1

φP-1DET,W0girl = 1

φP-2VBD,P-1DET = 1

φP-1DET,P0NN = 113

NLP Programming Tutorial 12 – Dependency Parsing

Algorithm Definition●●

The algorithm ShiftReduce takes as input:●

Weights ws wl wr●

A queue=[ (1, word1, POS1), (2, word2, POS2), …]

starts with a stack holding the special ROOT symbol:●●stack = [ (0, “ROOT”, “ROOT”) ]processes and returns:●heads = [ -1, head1, head2, … ]14NLP Programming Tutorial 12 – Dependency Parsing

Shift Reduce Algorithm

ShiftReduce(queue)
make list heads
stack = [ (0, “ROOT”, “ROOT”) ]while |queue| > 0 or |stack| > 1:feats = MakeFeats(stack, queue)ss = ws * feats# Score for “shift”
sl = wl * feats# Score for “reduce left”
sr = wr * feats# Score for “reduce right”
if ss >= sl and ss >= sr and |queue| > 0:
stack.push( queue.popleft() ) # Do the shift
elif sl >= sr:# Do the reduce left
heads[ stack[-2].id ] = stack[-1].idstack.remove(-2)
else:# Do the reduce right15
heads[ stack[-1].id ] = stack[-2].idstack.remove(-1)

NLP Programming Tutorial 12 – Dependency Parsing

Training Shift-Reduce●●●

Can be trained using perceptron algorithm
Do parsing, if correct answer corr different fromclassifier answer ans, update weights
e.g. if ans = SHIFT and corr = LEFT
ws -= φ(queue,stack)
wl += φ(queue,stack)16NLP Programming Tutorial 12 – Dependency Parsing

Keeping Track of the Correct Answer(Initial Attempt)●

Assume we know correct head of each stack entry:
stack[-1].head == stack[-2].id→ corr = RIGHT(left is head of right)

stack[-2].head == stack[-1].id→ corr = LEFT

(right is head of left)

else→ corr = SHIFT●Problem: too greedy for right-branching dependencies

gotoschool

stack[-2] stack[-1] queue[0]gotoschool
id:12
3
head: 012→ RIGHT17NLP Programming Tutorial 12 – Dependency Parsing

Keeping Track of the Correct Answer(Revised)
●

●

●

●

●

Count the number of unprocessed children
stack[-1].head == stack[-2].id(right is head of left)
stack[-1].unproc == 0 (left no unprocessed children)→ corr = RIGHT
stack[-2].head == stack[-1].id(left is head of right)
stack[-2].unproc == 0(right no unprocessed children)→ corr = LEFT
else
→ corr = SHIFT
Increase unproc when reading in the tree
When we reduce a head, decrement unproc
corr == RIGHT → stack[-1].unproc -= 118

NLP Programming Tutorial 12 – Dependency Parsing

Shift Reduce Training Algorithm
ShiftReduceTrain(queue)
make list heads
stack = [ (0, “ROOT”, “ROOT”) ]while |queue| > 0 or |stack| > 1:feats = MakeFeats(stack, queue)
calculate ans# Same as ShiftReduce
calculate corr
# Previous slides
if ans != corr:wans -= feats
wcorr += feats
perform action according to corr
19

NLP Programming Tutorial 12 – Dependency Parsing

CoNLL File Format:●●Standard format for dependencies
Tab-separated columns, sentences separated byspace
ID Word
1 ms.
2 haag
3 plays
4 elianti
5 .

Basems.
haagplayselianti.

POS POS2NNP NNPNNP NNPVBZ VBZ
NNP NNP.
.

?
_____

Head Type
2DEP
3NP-SBJ
0ROOT
3NP-OBJ
3DEP

20

NLP Programming Tutorial 12 – Dependency Parsing

Exercise21

NLP Programming Tutorial 12 – Dependency Parsing

Exercise●

Write train-sr.py test-sr.py●

Train the program●●

Run the program on actual data:●●●Input: data/mstparser­en­train.depdata/mstparser­en­test.dep

Measure: accuracy withscript/grade­dep.py
Challenge:
think of better features to use● use a better classification algorithm than perceptron
22● analyze the common mistakes●

NLP Programming Tutorial 12 – Dependency Parsing

Thank You!

23