{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "%%capture\n", "%load_ext autoreload\n", "%autoreload 2\n", "import sys\n", "sys.path.append(\"..\")\n", "import statnlpbook.util as util\n", "import statnlpbook.parsing as parsing\n", "from statnlpbook.transition import *\n", "\n", "util.execute_notebook('Transition-based dependency parsing.ipynb')" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "\n", "$$\n", "\\newcommand{\\Xs}{\\mathcal{X}}\n", "\\newcommand{\\Ys}{\\mathcal{Y}}\n", "\\newcommand{\\y}{\\mathbf{y}}\n", "\\newcommand{\\balpha}{\\boldsymbol{\\alpha}}\n", "\\newcommand{\\bbeta}{\\boldsymbol{\\beta}}\n", "\\newcommand{\\aligns}{\\mathbf{a}}\n", "\\newcommand{\\align}{a}\n", "\\newcommand{\\source}{\\mathbf{s}}\n", "\\newcommand{\\target}{\\mathbf{t}}\n", "\\newcommand{\\ssource}{s}\n", "\\newcommand{\\starget}{t}\n", "\\newcommand{\\repr}{\\mathbf{f}}\n", "\\newcommand{\\repry}{\\mathbf{g}}\n", "\\newcommand{\\x}{\\mathbf{x}}\n", "\\newcommand{\\prob}{p}\n", "\\newcommand{\\a}{\\alpha}\n", "\\newcommand{\\b}{\\beta}\n", "\\newcommand{\\vocab}{V}\n", "\\newcommand{\\params}{\\boldsymbol{\\theta}}\n", "\\newcommand{\\param}{\\theta}\n", "\\DeclareMathOperator{\\perplexity}{PP}\n", "\\DeclareMathOperator{\\argmax}{argmax}\n", "\\DeclareMathOperator{\\argmin}{argmin}\n", "\\newcommand{\\train}{\\mathcal{D}}\n", "\\newcommand{\\counts}[2]{\\#_{#1}(#2) }\n", "\\newcommand{\\length}[1]{\\text{length}(#1) }\n", "\\newcommand{\\indi}{\\mathbb{I}}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Dependency Parsing" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Motivation \n", "\n", "Constituent Parsers **more complex than needed**:\n", "* Often we only need grammatical **relations between words**\n", "* Annotation **costly** and **error prone**\n", " * To annotate a sentence with a parse tree, you need substantial expertise" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "**Dependency Parsing** addresses this...\n", "\n", "[spaCy](https://demos.explosion.ai/displacy/)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Anatomy of a Dependency Tree\n", "\n", "* Nodes:\n", " * Tokens of sentence\n", " * a ROOT node (akin to the S symbol in CFGs)\n", "* Edges:\n", " * Directed from token child to ** syntactic head**\n", " * Each **non-ROOT **token has **exactly one parent**\n", " * the word that controls its syntactic function, or\n", " * the word \"it depends on\"\n", "* ROOT **has no parent**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Example" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hideCode": true, "hidePrompt": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tokens = [\"ROOT\", \"Economic\", \"news\", \"had\", \"little\", \"effect\", \"on\", \"financial\", \"markets\", \".\"]\n", "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\")])\n", "\n", "render_displacy(*transition.to_displacy_graph(arcs, tokens),\"900px\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Dependency Parsing Approaches" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Graph-Based Parsing\n", "* define $s_\\params(\\x,\\y)$ over sentences $\\Xs$ and dependency graphs $\\Ys$\n", "* $s_\\params(\\x,\\y)$ decomposes into per (hyper)edge scores:\n", "$$\n", "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\n", "$$ \n", "* **Labelled** version uses $\\langle \\mathbf{f}(h,c,l,\\x),\\mathbf{w} \\rangle$ where $l$ is label" ] }, { "cell_type": "markdown", "metadata": { "hidePrompt": false, "slideshow": { "slide_type": "subslide" } }, "source": [ "How would you define features $\\mathbf{f}(h,c,\\x)$?" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "hideCode": true, "hidePrompt": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tokens = [\"ROOT\", \"Economic\", \"news\", \"had\", \"little\", \"effect\", \"on\", \"financial\", \"markets\", \".\"]\n", "arcs = set([(3, 5, \"dobj\")])\n", "\n", "render_displacy(*transition.to_displacy_graph(arcs, tokens),\"900px\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Search/Parsing\n", "\n", "Find the **tree** with maximal total score\n", "\n", "$$\n", "\\argmax_{\\y} \\sum_{(h,c) \\in \\y} s(h,c,\\x)\n", "$$\n", "\n", "Corresponds to **finding maximum spanning trees**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Example Maximum Spanning Tree\n", "\n", "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n" ] }, { "cell_type": "raw", "metadata": { "hide_egal": false, "is_egal": true }, "source": [ "Created with Snap" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Problem\n", "higher order dependencies\n", "\n", "\n", "\n", "\n", "\n", " \n", " \n", " \n", "\n" ] }, { "cell_type": "raw", "metadata": { "hide_egal": false, "is_egal": true, "slideshow": { "slide_type": "-" } }, "source": [ "Created with Snap" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Transition-Based Parsing\n", "* learn to perform the right action / transition in a bottom-up left-right parser\n", "* Train classifiers $p(y|\\x)$ where $y$ is an action, and $\\x$ is solution built so far, and the remaining sentence\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Currently the state-of-the-art..." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Parsing State \n", "Akin to bottom up parsing for CFGs..." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "A token \n", "### Buffer\n", "of **remaining tokens**" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "hidePrompt": true, "scrolled": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "
bufferstackparseaction
ROOT Economic news had little effect on financial markets .\n", "
\n", " 		INIT
" ], "text/plain": [ ".Output at 0x7f16909726a0>" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[0:1], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "A token \n", "### Stack\n", "of earlier tokens to **attach to later**" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "hidePrompt": true, "scrolled": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "
bufferstackparseaction
news had little effect on financial markets .ROOT Economic\n", "
\n", " 		shift
" ], "text/plain": [ ".Output at 0x7f1690972668>" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[2:3],tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "hidePrompt": false, "slideshow": { "slide_type": "subslide" } }, "source": [ "A current \n", "### Parse \n", "built so far" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "hidePrompt": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "
bufferstackparseaction
on financial markets .ROOT had effect\n", "
\n", " 		rightArc-dobj
" ], "text/plain": [ ".Output at 0x7f16909722e8>" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[9:10], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "hidePrompt": false, "slideshow": { "slide_type": "subslide" } }, "source": [ "We use the following \n", "### Actions" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Shift\n", "\n", "push the word at the top of the buffer to the stack \n", "\n", "$$\n", "(S, i|B, A)\\rightarrow(S|i, B, A)\n", "$$" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "hidePrompt": true, "scrolled": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "
bufferstackparseaction
ROOT Economic news had little effect on financial markets .\n", "
\n", " 		INIT
Economic news had little effect on financial markets .ROOT\n", "
\n", " 		shift
" ], "text/plain": [ ".Output at 0x7f169094e908>" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[0:2], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Reduce\n", "\n", "pop the word at the top of the stack if it has a head \n", "\n", "$$\n", "(S|i, B, A)\\rightarrow(S, B, A)\n", "$$" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "hidePrompt": true, "scrolled": false, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "
bufferstackparseaction
.ROOT had effect on markets\n", "
\n", " 		rightArc-pmod
.ROOT had effect on\n", "
\n", " 		reduce
" ], "text/plain": [ ".Output at 0x7f169094e400>" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[13:15], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## rightArc-[label]\n", "\n", "add labeled arc from top of stack \\\\(i\\\\) to top of the buffer \\\\(j\\\\) \n", "\n", "$$\n", "(S|i, j|B, A) \\rightarrow (S|i|j, B, A\\cup\\{(i,j,l)\\})\n", "$$\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "scrolled": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "
bufferstackparseaction
had little effect on financial markets .ROOT\n", "
\n", " 		leftArc-nsubj
little effect on financial markets .ROOT had\n", "
\n", " 		rightArc-root
" ], "text/plain": [ ".Output at 0x7f169094e668>" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[5:7], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### leftArc-[label] \n", "\n", "add labeled arc from top of buffer, \\\\(j\\\\), to top of stack, \\\\(i\\\\), if \\\\(i\\\\) has no head \n", "\n", "$$\n", "(S|i, j|B, A) \\rightarrow (S, j|B, A\\cup\\{(j,i,l)\\})\n", "$$\n" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "scrolled": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "
bufferstackparseaction
news had little effect on financial markets .ROOT Economic\n", "
\n", " 		shift
news had little effect on financial markets .ROOT\n", "
\n", " 		leftArc-amod
" ], "text/plain": [ ".Output at 0x7f169094eef0>" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[2:4], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "## Full Example" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "scrolled": true, "slideshow": { "slide_type": "-" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
bufferstackparseaction
ROOT Economic news had little effect on financial markets .\n", "
\n", " 		INIT
Economic news had little effect on financial markets .ROOT\n", "
\n", " 		shift
news had little effect on financial markets .ROOT Economic\n", "
\n", " 		shift
news had little effect on financial markets .ROOT\n", "
\n", " 		leftArc-amod
had little effect on financial markets .ROOT news\n", "
\n", " 		shift
had little effect on financial markets .ROOT\n", "
\n", " 		leftArc-nsubj
little effect on financial markets .ROOT had\n", "
\n", " 		rightArc-root
effect on financial markets .ROOT had little\n", "
\n", " 		shift
effect on financial markets .ROOT had\n", "
\n", " 		leftArc-amod
on financial markets .ROOT had effect\n", "
\n", " 		rightArc-dobj
financial markets .ROOT had effect on\n", "
\n", " 		rightArc-prep
markets .ROOT had effect on financial\n", "
\n", " 		shift
markets .ROOT had effect on\n", "
\n", " 		leftArc-amod
.ROOT had effect on markets\n", "
\n", " 		rightArc-pmod
.ROOT had effect on\n", "
\n", " 		reduce
.ROOT had effect\n", "
\n", " 		reduce
.ROOT had\n", "
\n", " 		reduce
.ROOT\n", "
\n", " 		reduce
ROOT .\n", "
\n", " 		rightArc-p
ROOT .\n", "
\n", " 		TERMINAL
" ], "text/plain": [ ".Output at 0x7f169094ef98>" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "render_transitions_displacy(transitions[:], tokenized_sentence)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Machine Learning\n", "\n", "How to decide what action to take? \n", "\n", "* Learn a discriminative classifier $p(y | \\x)$ where \n", " * $\\x$ is a representation of buffer, stack and parse. \n", " * $y$ is the action to choose\n", "* Current state-of-the-art systems use neural networks as classifiers (e.g. Parsey McParseFace)\n", "* Use **greedy search** or **beam search** to find the highest scoring sequence of steps" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Summary\n", "\n", "* Dependency parsing predicts word-to-word dependencies \n", "* simpler annotations\n", "* faster parsing\n", "* sufficient for most down-stream applications" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Background Material\n", "\n", "* [EACL 2014 tutorial](http://stp.lingfil.uu.se/~nivre/eacl14.html)" ] } ], "metadata": { "celltoolbar": "Hide code", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.2" } }, "nbformat": 4, "nbformat_minor": 1 }