In [1]:

%%html
<script>
  function code_toggle() {
    if (code_shown){
      $('div.input').hide('500');
      $('#toggleButton').val('Show Code')
    } else {
      $('div.input').show('500');
      $('#toggleButton').val('Hide Code')
    }
    code_shown = !code_shown
  }

  $( document ).ready(function(){
    code_shown=false;
    $('div.input').hide()
  });
</script>
<form action="javascript:code_toggle()"><input type="submit" id="toggleButton" value="Show Code"></form>

In [1]:

%%capture
%load_ext autoreload
%autoreload 2
import sys
sys.path.append("..")
import statnlpbook.util as util
import statnlpbook.parsing as parsing
from statnlpbook.transition import *

util.execute_notebook('transition-based_dependency_parsing.ipynb')

$$ \newcommand{\Xs}{\mathcal{X}} \newcommand{\Ys}{\mathcal{Y}} \newcommand{\y}{\mathbf{y}} \newcommand{\balpha}{\boldsymbol{\alpha}} \newcommand{\bbeta}{\boldsymbol{\beta}} \newcommand{\aligns}{\mathbf{a}} \newcommand{\align}{a} \newcommand{\source}{\mathbf{s}} \newcommand{\target}{\mathbf{t}} \newcommand{\ssource}{s} \newcommand{\starget}{t} \newcommand{\repr}{\mathbf{f}} \newcommand{\repry}{\mathbf{g}} \newcommand{\x}{\mathbf{x}} \newcommand{\prob}{p} \newcommand{\a}{\alpha} \newcommand{\b}{\beta} \newcommand{\vocab}{V} \newcommand{\params}{\boldsymbol{\theta}} \newcommand{\param}{\theta} \DeclareMathOperator{\perplexity}{PP} \DeclareMathOperator{\argmax}{argmax} \DeclareMathOperator{\argmin}{argmin} \newcommand{\train}{\mathcal{D}} \newcommand{\counts}[2]{\#_{#1}(#2) } \newcommand{\length}[1]{\text{length}(#1) } \newcommand{\indi}{\mathbb{I}} $$

Dependency Parsing¶

Motivation¶

Constituent Parsers more complex than needed:

Often we only need grammatical relations between words
Annotation costly and error prone
- To annotate a sentence with a parse tree, you need substantial expertise

Dependency Parsing addresses this...

spaCy

Anatomy of a Dependency Tree¶

Nodes:
- Tokens of sentence
- a ROOT node (akin to the S symbol in CFGs)
Edges:
- Directed from token child to ** syntactic head**
- Each non-ROOT token has exactly one parent
  - the word that controls its syntactic function, or
  - the word "it depends on"
ROOT has no parent

Example¶

In [2]:

tokens = ["ROOT", "Economic", "news", "had", "little", "effect", "on", "financial", "markets", "."]
arcs = set([(0,3, "root"), (0,9,"p"), (2,1,"amod"),(3,2,"nsubj"), (3, 5, "dobj"), (5,4,"amod"), (5,6, "prep"), (6,8,"pmod"), (8,7,"amod")])

render_displacy(*transition.to_displacy_graph(arcs, tokens),"900px")

Out[2]:

Dependency Parsing Approaches¶

Graph-Based Parsing¶

define $s_\params(\x,\y)$ over sentences $\Xs$ and dependency graphs $\Ys$
$s_\params(\x,\y)$ decomposes into per (hyper)edge scores:

$$ s_\params(\x,\y) = \sum_{(h,c) \in \y} s(h,c,\x)=\sum_{(h,c) \in \y}\langle \mathbf{f}(h,c,\x),\mathbf{w} \rangle $$

Labelled version uses $\langle \mathbf{f}(h,c,l,\x),\mathbf{w} \rangle$ where $l$ is label

How would you define features $\mathbf{f}(h,c,\x)$?

In [3]:

tokens = ["ROOT", "Economic", "news", "had", "little", "effect", "on", "financial", "markets", "."]
arcs = set([(3, 5, "dobj")])

render_displacy(*transition.to_displacy_graph(arcs, tokens),"900px")

Out[3]:

Search/Parsing¶

Find the tree with maximal total score

$$ \argmax_{\y} \sum_{(h,c) \in \y} s(h,c,\x) $$

Corresponds to finding maximum spanning trees

Example Maximum Spanning Tree¶

Problem¶

higher order dependencies

Transition-Based Parsing¶

learn to perform the right action / transition in a bottom-up left-right parser
Train classifiers $p(y|\x)$ where $y$ is an action, and $\x$ is solution built so far, and the remaining sentence

Currently the state-of-the-art...

Parsing State¶

Akin to bottom up parsing for CFGs...

A token

Buffer¶

of remaining tokens

In [4]:

render_transitions_displacy(transitions[0:1], tokenized_sentence)

Out[4]:

buffer	stack	parse	action
ROOT Economic news had little effect on financial markets .			INIT

A token

Stack¶

of earlier tokens to attach to later

In [5]:

render_transitions_displacy(transitions[2:3],tokenized_sentence)

Out[5]:

buffer	stack	parse	action
news had little effect on financial markets .	ROOT Economic		shift

A current

Parse¶

built so far

In [6]:

render_transitions_displacy(transitions[9:10], tokenized_sentence)

Out[6]:

buffer	stack	parse	action
on financial markets .	ROOT had effect		rightArc-dobj

We use the following

Actions¶

Shift¶

push the word at the top of the buffer to the stack

$$ (S, i|B, A)\rightarrow(S|i, B, A) $$

In [7]:

render_transitions_displacy(transitions[0:2], tokenized_sentence)

Out[7]:

buffer	stack	parse	action
ROOT Economic news had little effect on financial markets .			INIT
Economic news had little effect on financial markets .	ROOT		shift

Reduce¶

pop the word at the top of the stack if it has a head

$$ (S|i, B, A)\rightarrow(S, B, A) $$

In [8]:

render_transitions_displacy(transitions[13:15], tokenized_sentence)

Out[8]:

buffer	stack	parse	action
.	ROOT had effect on markets		rightArc-pmod
.	ROOT had effect on		reduce

rightArc-[label]¶

add labeled arc from top of stack $i$ to top of the buffer $j$

$$ (S|i, j|B, A) \rightarrow (S|i|j, B, A\cup\{(i,j,l)\}) $$

In [9]:

render_transitions_displacy(transitions[5:7], tokenized_sentence)

Out[9]:

buffer	stack	parse	action
had little effect on financial markets .	ROOT		leftArc-nsubj
little effect on financial markets .	ROOT had		rightArc-root

leftArc-[label]¶

add labeled arc from top of buffer, $j$, to top of stack, $i$, if $i$ has no head

$$ (S|i, j|B, A) \rightarrow (S, j|B, A\cup\{(j,i,l)\}) $$

In [10]:

render_transitions_displacy(transitions[2:4], tokenized_sentence)

Out[10]:

buffer	stack	parse	action
news had little effect on financial markets .	ROOT Economic		shift
news had little effect on financial markets .	ROOT		leftArc-amod

Full Example¶

In [11]:

render_transitions_displacy(transitions[:], tokenized_sentence)

Out[11]:

buffer	stack	parse	action
ROOT Economic news had little effect on financial markets .			INIT
Economic news had little effect on financial markets .	ROOT		shift
news had little effect on financial markets .	ROOT Economic		shift
news had little effect on financial markets .	ROOT		leftArc-amod
had little effect on financial markets .	ROOT news		shift
had little effect on financial markets .	ROOT		leftArc-nsubj
little effect on financial markets .	ROOT had		rightArc-root
effect on financial markets .	ROOT had little		shift
effect on financial markets .	ROOT had		leftArc-amod
on financial markets .	ROOT had effect		rightArc-dobj
financial markets .	ROOT had effect on		rightArc-prep
markets .	ROOT had effect on financial		shift
markets .	ROOT had effect on		leftArc-amod
.	ROOT had effect on markets		rightArc-pmod
.	ROOT had effect on		reduce
.	ROOT had effect		reduce
.	ROOT had		reduce
.	ROOT		reduce
	ROOT .		rightArc-p
	ROOT .		TERMINAL

Machine Learning¶

How to decide what action to take?

Learn a discriminative classifier $p(y | \x)$ where
- $\x$ is a representation of buffer, stack and parse.
- $y$ is the action to choose
Current state-of-the-art systems use neural networks as classifiers (e.g. Parsey McParseFace)
Use greedy search or beam search to find the highest scoring sequence of steps

Summary¶

Dependency parsing predicts word-to-word dependencies
simpler annotations
faster parsing
sufficient for most down-stream applications

Background Material¶

EACL 2014 tutorial
Jurafsky & Martin, Speech and Language Processing (Third Edition): Chapter 13, Dependency Parsing.

In [ ]: