$$ \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¶

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)$?

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

A token

Stack¶

of earlier tokens to attach to later

A current

Parse¶

built so far

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) $$

Reduce¶

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

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

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)\}) $$

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)\}) $$

Full Example¶

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