#!/usr/bin/env python
# coding: utf-8

# In[1]:


get_ipython().run_cell_magic('html', '', '<script>\n  function code_toggle() {\n    if (code_shown){\n      $(\'div.input\').hide(\'500\');\n      $(\'#toggleButton\').val(\'Show Code\')\n    } else {\n      $(\'div.input\').show(\'500\');\n      $(\'#toggleButton\').val(\'Hide Code\')\n    }\n    code_shown = !code_shown\n  }\n\n  $( document ).ready(function(){\n    code_shown=false;\n    $(\'div.input\').hide()\n  });\n</script>\n<form action="javascript:code_toggle()"><input type="submit" id="toggleButton" value="Show Code"></form>\n<style>\n.rendered_html td {\n    font-size: xx-large;\n    text-align: left; !important\n}\n.rendered_html th {\n    font-size: xx-large;\n    text-align: left; !important\n}\n</style>\n')


# In[2]:


get_ipython().run_cell_magic('capture', '', '%load_ext autoreload\n%autoreload 2\nimport sys\nsys.path.append("..")\nfrom statnlpbook.util import execute_notebook\nimport statnlpbook.parsing as parsing\nfrom statnlpbook.transition import *\nfrom statnlpbook.dep import *\nimport pandas as pd\nfrom io import StringIO\nfrom IPython.display import display, HTML\n\nexecute_notebook(\'transition-based_dependency_parsing.ipynb\')\n')


# <!---
# Latex Macros
# -->
# $$
# \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}}
# $$

# In[3]:


get_ipython().run_line_magic('load_ext', 'tikzmagic')


# # Parsing

# + Syntactic constituency
# + Syntactic dependencies
# + Parsing algorithms
# + Evaluation

# # Syntactic constituency

# ## Reminder: parts of speech (POS)
# 
# [Parts of speech](sequence_labeling_slides.ipynb) categorise the syntactic function of words.
# 
# [Penn Treebank POS tagset](https://www.ling.upenn.edu/courses/Fall_2003/ling001/penn_treebank_pos.html):
# 
# Tag || Example
# :--- | :--- | :---
# CC | Coordinating conjunction | *and*
# CD | Cardinal number | *1*
# DT | Determiner | *the*
# EX | Existential there | *there*
# FW | Foreign word | *שלום*
# IN | Preposition or subordinating conjunction | *in*
# JJ | Adjective | *high*
# JJR | Adjective, comparative | *higher*
# JJS | Adjective, superlative | *highest*
# LS | List item marker | *,*
# MD | Modal | *can*
# NN | Noun, singular or mass | *desk*
# NNS | Noun, plural | *desks*
# NNP | Proper noun, singular | *Denmark*
# NNPS | Proper noun, plural | *Danes*
# PDT | Predeterminer | *both*
# POS | Possessive ending | *'s*
# PRP | Personal pronoun | *you*
# PRP$ | Possessive pronoun | *your*
# RB | Adverb | *well*
# RBR | Adverb, comparative | *better*
# RBS | Adverb, superlative | *best*
# RP | Particle |
# SYM | Symbol |
# TO | to |
# UH | Interjection |
# VB | Verb, base form | *see*
# VBD | Verb, past tense | *saw*
# VBG | Verb, gerund or present participle | *seeing*
# VBN | Verb, past participle | *seen*
# VBP | Verb, non-3rd person singular present | *see*
# VBZ | Verb, 3rd person singular present | *sees*
# WDT | Wh-determiner |
# WP | Wh-pronoun |
# WP\$ | Possessive wh-pronoun |
# WRB | Wh-adverb |

# ## Syntactic constituents
# 
# **Phrases** also have a grammatical function when they are syntactic constituents.
# 
# [Penn Treebank constituent tagset](https://www.ldc.upenn.edu/sites/www.ldc.upenn.edu/files/penn-etb-2-style-guidelines.pdf):
# 
# Phrase Level || Example
# :--- | :--- | :---
# ADJP | Adjective Phrase | *really high*
# ADVP | Adverb Phrase | *very well*
# CONJP | Conjunction Phrase | *as well as*
# FRAG | Fragment |
# INTJ | Interjection |
# LST | List marker |
# NP | Noun Phrase | *high desk*
# PP | Prepositional Phrase | *at home*
# PRN | Parenthetical |
# PRT | Particle. Category for words that should be tagged RP |
# QP | Quantifier Phrase (i.e. complex measure/amount phrase); used within NP |
# RRC | Reduced Relative Clause |
# VP | Verb Phrase | *see the desk*
# WHADJP | Wh-adjective Phrase. Adjectival phrase containing a wh-adverb | *how hot*
# WHAVP | Wh-adverb Phrase, containing a wh-adverb | *how well*
# WHNP | Wh-noun Phrase, containing some wh-word | *which book*
# WHPP | Wh-prepositional Phrase, containing a wh-noun phrase | *of which*
# X | Unknown, uncertain, or unbracketable. |

# Clause Level ||
# :--- | :---
# S | simple declarative clause, i.e. one that is not introduced by a (possible empty) subordinating conjunction or a wh-word and that does not exhibit subject-verb inversion.
# SBAR | Clause introduced by a (possibly empty) subordinating conjunction.
# SBARQ | Direct question introduced by a wh-word or a wh-phrase. Indirect questions and relative clauses should be bracketed as SBAR, not SBARQ.
# SINV | Inverted declarative sentence, i.e. one in which the subject follows the tensed verb or modal.
# SQ | Inverted yes/no question, or main clause of a wh-question, following the wh-phrase in SBARQ.

# ## Trees
# 
# A **tree** is a connected acyclic undirected graph.
# 
# Graphs consist of **nodes** and **edges** between them.
# 
# <center><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Tree_graph.svg/1920px-Tree_graph.svg.png" width=40%/></center>

# ## Syntactic constituency trees (phrase structure trees)
# 
# * **Nodes**: syntactic constituents, labeled by type (including individual words, labeled by POS).
# * **Edges**: connecting phrases to their constituents, unlabeled.
# 
# <center>
#     <img src="../img/spaghetti1.png" width=80%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/P13-1045/">Socher et al., 2013</a>)
# </div>

# <center>
#     <table><tr>
#     <td><img src="https://d3i71xaburhd42.cloudfront.net/0fea9208b2e18dd679a0e913a918bbb949eb8589/2-Figure2-1.png" width=80%></td>
#     <td><img src="https://d3i71xaburhd42.cloudfront.net/0fea9208b2e18dd679a0e913a918bbb949eb8589/3-Figure5-1.png" width=80%></td>
#         </tr></table>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/N18-5011">Gokcen et al., 2018</a>)
# </div>

# Another example of a *PP attachment* problem: does the **PP** (prepositional phrase) attach to the **VP** (verbal phrase) or the **NP** (noun phrase)?
# <center>
#     <img src="../img/proposal.png" width=60%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/2022.acl-long.220">Kitaev et al., 2022</a>)
# </div>

# ## Treebanks
# 
# A dataset that consists of a text corpus with annotated (syntactic) trees.
# 
# Some commonly used treebanks:
# 
# * English: *Penn Treebank* (4.8 million words)
# * Mandarin Chinese: *Chinese Treebank* (1.5 million words)
# * German: *TIGER* (0.9 million words), *TüBa-D/Z* (1.6 million words)
# * Czech: *Prague Dependency Treebank* (2 million words)
# * Danish: *Arboretum* (0.2 million words)
# * ...
# * Multilingual: *Universal Dependencies* (more in a few slides)
# 
# <center><img src="https://production-media.paperswithcode.com/datasets/treebank.png" width=30%/></center>

# ## Constituency parsers
# 
# Structured prediction: trained on treebanks to build constituency trees from text.
# 
# See more in the [chapter from this book about constituency parsing](parsing.ipynb) ([slides](parsing_slides.ipynb)).
# 
# <center>
#     <img src="https://d3i71xaburhd42.cloudfront.net/30a4754062a5f8c99e665db0b702a4da060af340/5-Figure2-1.png" width=30%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/2022.acl-long.220">Kitaev et al., 2022</a>)
# </div>

# # Syntactic dependencies

# ## Motivation: information extraction
# 
# In [relation extraction](information_extraction_slides.ipynb), it helps to define **linguistic** patterns such as `<subject> <verb> <object>` instead of purely text-based patterns.
# 
# > <font color="blue">Dechra Pharmaceuticals</font>, which has just made its second acquisition, had previously purchased <font color="green">Genitrix</font>.
# 
# > <font color="blue">Trinity Mirror plc</font>, the largest British newspaper, purchased <font color="green">Local World</font>, its rival.
# 
# > <font color="blue">Kraft</font>, owner of <font color="blue">Milka</font>, purchased <font color="green">Cadbury Dairy Milk</font> and is now gearing up for a roll-out of its new brand.
# 

# **Syntactic dependencies** are a useful representation for this purpose.
# 
# <center>
#     <img src="parsing_figures/dep4re.png" width="60%">
# </center>

# ## Motivation: question answering by reading comprehension
# 
# <center>
#     <img src="https://d3i71xaburhd42.cloudfront.net/05dd7254b632376973f3a1b4d39485da17814df5/6-Figure4-1.png" width=100%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/D16-1264">Rajpurkar et al., 2016</a>)
# </div>

# ## Motivation: question answering from knowledge bases
# 
# <center>
#     <img src="https://d3i71xaburhd42.cloudfront.net/faee0c81a1170402b149500f1b91c51ccaf24027/2-Figure1-1.png" width=50%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/D17-1009">Reddy et al., 2017</a>)
# </div>

# ## Motivation: machine translation
# 
# Reordering rules can be stated in terms of syntactic dependencies:
# 
# <center>
#     <img src="https://d3i71xaburhd42.cloudfront.net/f4c750cdf8f557eea3a4b76be16e99ec15f0c92b/3-Figure2-1.png" width=100%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://arxiv.org/abs/2104.08384">Rasooli et al., 2021</a>)
# </div>

# ## Syntactic dependency trees
# 
# * **Nodes**: individual words, and a special `ROOT` node.
# * Edges (**arcs**): labeled syntactic relations between words: from **head** to **dependent**.
# 
# Must be a tree: **every word has exactly one head, and `ROOT` has no head**.

# In[4]:


conllu = """
# ID	FORM	LEMMA	UPOS	XPOS	FEATS	HEAD	DEPREL	DEPS	MISC
1	I	_	_	_	_	2	nsubj	_	_
2	saw	_	_	_	_	0	root	_	_
3	the	_	_	_	_	4	det	_	_
4	star	_	_	_	_	2	dobj	_	_
5	with	_	_	_	_	7	case	_	_
6	the	_	_	_	_	7	det	_	_
7	telescope	_	_	_	_	2	obl	_	_
"""
arcs, tokens = to_displacy_graph(*load_arcs_tokens(conllu))
render_displacy(arcs, tokens,"2400px")


# ### Syntactic ambiguity

# In[5]:


conllu = """
# ID	FORM	LEMMA	UPOS	XPOS	FEATS	HEAD	DEPREL	DEPS	MISC
1	I	_	_	_	_	2	nsubj	_	_
2	saw	_	_	_	_	0	root	_	_
3	the	_	_	_	_	4	det	_	_
4	star	_	_	_	_	2	dobj	_	_
5	with	_	_	_	_	7	case	_	_
6	the	_	_	_	_	7	det	_	_
7	telescope	_	_	_	_	2	obl	_	_
"""
arcs, tokens = to_displacy_graph(*load_arcs_tokens(conllu))
render_displacy(arcs, tokens,"2400px")


# In[6]:


conllu = """
# ID	FORM	LEMMA	UPOS	XPOS	FEATS	HEAD	DEPREL	DEPS	MISC
1	I	_	_	_	_	2	nsubj	_	_
2	saw	_	_	_	_	0	root	_	_
3	the	_	_	_	_	4	det	_	_
4	star	_	_	_	_	2	dobj	_	_
5	with	_	_	_	_	7	case	_	_
6	the	_	_	_	_	7	det	_	_
7	telescope	_	_	_	_	4	nmod	_	_
"""
arcs, tokens = to_displacy_graph(*load_arcs_tokens(conllu))
render_displacy(arcs, tokens,"2400px")


# <center>
#     <table>
#         <tr>
#             <td><img src="parsing_figures/telescope1.jpeg" width=50%/></td>
#             <td><img src="parsing_figures/telescope2.jpg" width=50%/></td>
#         </tr>
#     </table>
# </center>

# ### CoNLL-U format
# 
# Tabular format with 10 columns indicating various morphosyntactic attributes.
# 
# Shown here: ID, surface form, dependency head and dependency relation.
# 
# (The others are shown as `_` but normally they would be filled in too.)

# In[7]:


display(HTML(pd.read_csv(StringIO(conllu), sep="\t").to_html(index=False)))
render_displacy(arcs, tokens,"2400px")


# ### Need for universal syntactic annotation
# 
# How to define the relation labels? There are different linguistic traditions in different languages...
# <center>
#     <img src="../img/ud.png" width=60%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://cl.lingfil.uu.se/~miryam/assets/pdf/thesis.pdf">de Lhoneux, 2019</a>)
# </div>

# ### Universal Dependencies
# 
# * Annotation framework featuring [37 syntactic relations](https://universaldependencies.org/u/dep/all.html)
# * [Treebanks](http://universaldependencies.org/) in over 130 languages
# * Large project with [over 500 contributors](https://lindat.mff.cuni.cz/repository/xmlui/handle/11234/1-4758)
# * Cross-linguistically consistent annotation of typologically diverse languages ([de Marneffe et al., 2021](https://aclanthology.org/2021.cl-2.11/))
# 
# <center><img src="../img/ud_treebanks.png" width=70%/></center>

# ### UD dependency relations
# 
# <table border="1">
#   <tr style="background-color:cornflowerblue; font-size: x-large; text-align: left;">
#       <td style="text-align: left;"> </td>
#       <td style="text-align: left;"> Nominals </td>
#       <td style="text-align: left;"> Clauses </td>
#       <td style="text-align: left;"> Modifier words </td>
#       <td style="text-align: left;"> Function Words </td>
#   </tr>
#   <tr style="font-size: x-large; text-align: left;">
#       <td style="background-color:darkseagreen">
# 	Core arguments
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/nsubj.html" title="u-dep nsubj">nsubj</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/obj.html" title="u-dep obj">obj</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/iobj.html" title="u-dep iobj">iobj</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/csubj.html" title="u-dep csubj">csubj</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/ccomp.html" title="u-dep ccomp">ccomp</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/xcomp.html" title="u-dep xcomp">xcomp</a>
#       </td>
# 	  <td style="text-align: left;"></td><td style="text-align: left;"></td>
#   </tr>
#   <tr style="font-size: x-large; text-align: left;">
#       <td style="background-color:darkseagreen;">
# 	Non-core dependents
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/obl.html" title="u-dep obl">obl</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/vocative.html" title="u-dep vocative">vocative</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/expl.html" title="u-dep expl">expl</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/dislocated.html" title="u-dep dislocated">dislocated</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/advcl.html" title="u-dep advcl">advcl</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/advmod.html" title="u-dep advmod">advmod</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/discourse.html" title="u-dep discourse">discourse</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/aux_.html" title="u-dep aux">aux</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/cop.html" title="u-dep cop">cop</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/mark.html" title="u-dep mark">mark</a>
#       </td>
#   </tr>
#   <tr style="font-size: x-large; text-align: left;">
#       <td style="background-color:darkseagreen">
# 	Nominal dependents
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/nmod.html" title="u-dep nmod">nmod</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/appos.html" title="u-dep appos">appos</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/nummod.html" title="u-dep nummod">nummod</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/acl.html" title="u-dep acl">acl</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/amod.html" title="u-dep amod">amod</a>
#       </td>
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/det.html" title="u-dep det">det</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/clf.html" title="u-dep clf">clf</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/case.html" title="u-dep case">case</a>
#       </td>
#   </tr style="font-size: x-large; text-align: left;">
#   <tr style="background-color:cornflowerblue; font-size: x-large; text-align: left;">
#       <td style="text-align: left;"> Coordination </td>
#       <td style="text-align: left;"> MWE </td>
#       <td style="text-align: left;"> Loose </td>
#       <td style="text-align: left;"> Special </td>
#       <td style="text-align: left;"> Other </td>
#   </tr>
#   <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;">
# 	    <a href="https://universaldependencies.org/u/dep/conj.html" title="u-dep conj">conj</a><br>
# 	    <a href="https://universaldependencies.org/u/dep/cc.html" title="u-dep cc">cc</a>
#       </td>
#       <td style="text-align: left;">
# 	  <a href="https://universaldependencies.org/u/dep/fixed.html" title="u-dep fixed">fixed</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/flat.html" title="u-dep flat">flat</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/compound.html" title="u-dep compound">compound</a>
#     </td>
#     <td style="text-align: left;">
# 	  <a href="https://universaldependencies.org/u/dep/list.html" title="u-dep list">list</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/parataxis.html" title="u-dep parataxis">parataxis</a>
#     </td>
#     <td style="text-align: left;">
# 	  <a href="https://universaldependencies.org/u/dep/orphan.html" title="u-dep orphan">orphan</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/goeswith.html" title="u-dep goeswith">goeswith</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/reparandum.html" title="u-dep reparandum">reparandum</a>
#     </td>
#     <td style="text-align: left;">
# 	  <a href="https://universaldependencies.org/u/dep/punct.html" title="u-dep punct">punct</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/root.html" title="u-dep root">root</a><br>
# 	  <a href="https://universaldependencies.org/u/dep/dep.html" title="u-dep dep">dep</a>
#     </td>
#   </tr>
# </table>

# ## Beyond dependency trees
# 
# UD also includes other morphosyntactic annotation:
# 
# * Tokenisation and word segmentation
# * Morphological features (e.g., lemmas, case, gender)
# * **Universal part of speech tags (UPOS)**: coarse abstraction over language-specific POS tags (XPOS).
# 
# <table class="typeindex">
#   <thead>
#     <tr style="font-size: x-large; text-align: left;">
#       <th>Open class words</th>
#       <th>Closed class words</th>
#       <th>Other</th>
#     </tr>
#   </thead>
#   <tbody>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/ADJ.html" class="doclink doclabel" title="u-pos ADJ">ADJ</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/ADP.html" class="doclink doclabel" title="u-pos ADP">ADP</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/PUNCT.html" class="doclink doclabel" title="u-pos PUNCT">PUNCT</a></td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/ADV.html" class="doclink doclabel" title="u-pos ADV">ADV</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/AUX_.html" class="doclink doclabel" title="u-pos AUX">AUX</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/SYM.html" class="doclink doclabel" title="u-pos SYM">SYM</a></td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/INTJ.html" class="doclink doclabel" title="u-pos INTJ">INTJ</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/CCONJ.html" class="doclink doclabel" title="u-pos CCONJ">CCONJ</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/X.html" class="doclink doclabel" title="u-pos X">X</a></td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/NOUN.html" class="doclink doclabel" title="u-pos NOUN">NOUN</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/DET.html" class="doclink doclabel" title="u-pos DET">DET</a></td>
#       <td style="text-align: left;">&nbsp;</td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/PROPN.html" class="doclink doclabel" title="u-pos PROPN">PROPN</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/NUM.html" class="doclink doclabel" title="u-pos NUM">NUM</a></td>
#       <td style="text-align: left;">&nbsp;</td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/VERB.html" class="doclink doclabel" title="u-pos VERB">VERB</a></td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/PART.html" class="doclink doclabel" title="u-pos PART">PART</a></td>
#       <td style="text-align: left;">&nbsp;</td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;">&nbsp;</td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/PRON.html" class="doclink doclabel" title="u-pos PRON">PRON</a></td>
#       <td style="text-align: left;">&nbsp;</td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;">&nbsp;</td>
#       <td style="text-align: left;"><a href="https://universaldependencies.org/u/pos/SCONJ.html" class="doclink doclabel" title="u-pos SCONJ">SCONJ</a></td>
#       <td style="text-align: left;">&nbsp;</td>
#     </tr>
#   </tbody>
# </table>

# ### Danish UD example
# *the big fish ate the small fish*

# In[10]:


conllu = """
# ID	FORM	LEMMA	UPOS	XPOS	FEATS	HEAD	DEPREL	DEPS	MISC
1	Den	_	_	_	_	3	det	_	_
2	store	_	_	_	_	3	amod	_	_
3	fisk	_	_	_	_	4	nsubj	_	_
4	spiste	_	_	_	_	0	root	_	_
5	den	_	_	_	_	7	det	_	_
6	lille	_	_	_	_	7	amod	_	_
7	fisk	_	_	_	_	4	obj	_	_
"""
arcs, tokens = to_displacy_graph(*load_arcs_tokens(conllu))
render_displacy(arcs, tokens,"1400px")


# ### Korean UD example
# *big fish small fish ate*

# In[11]:


conllu = """
# ID	FORM	LEMMA	UPOS	XPOS	FEATS	HEAD	DEPREL	DEPS	MISC
1	큰	_	_	_	_	2	amod	_	_
2	물고기가	_	_	_	_	5	nsubj	_	_
3	작은	_	_	_	_	4	amod	_	_
4	물고기를	_	_	_	_	5	obj	_	_
5	먹었다	_	_	_	_	0	root	_	_
"""
arcs, tokens = to_displacy_graph(*load_arcs_tokens(conllu))
render_displacy(arcs, tokens,"1400px")


# <center><img src="../img/quiz_time.png"></center>
# 
# ### [ucph.page.link/dep](https://ucph.page.link/dep)
# 
# ([Responses](https://docs.google.com/forms/d/1s94JgjTizC8d4JUUPxV4T46pB2SH4sYp40b9aHZeVvE/edit#responses))

# ### Solution
# 
# There are 6 nodes (including the root) and 5 arcs.
# <img src="parsing_figures/weparsedashortsentence-1.png"/>

# ## Dependency parsing
# 
# Task:
# * Predict **head** and **relation** for each word.
# * Classification? Sequence tagging? Sequence-to-sequence? Span selection? Or something else?

# In[9]:


conllu = """
# ID	FORM	LEMMA	UPOS	XPOS	FEATS	HEAD	DEPREL	DEPS	MISC
1	Alice	_	_	_	_	2	nsubj	_	_
2	saw	_	_	_	_	0	root	_	_
3	Bob	_	_	_	_	2	dobj	_	_
"""
display(HTML(pd.read_csv(StringIO(conllu), sep="\t").to_html(index=False)))


# ## Dependency parsing approaches
# 
# * **Graph-based**: score all possible word pairs, find best combination (often a maximum spanning tree). Examples:
#   * [UDPipe](https://lindat.mff.cuni.cz/services/udpipe/run.php?model=english-ewt-ud-2.10-220711&data=Kraft,%20owner%20of%20Milka,%20purchased%20Cadbury%20Dairy%20Milk%20and%20is%20now%20gearing%20up%20for%20a%20roll-out%20of%20its%20new%20brand.)
#   * [Stanza](http://stanza.run/)
# * **Transition-based**: incrementally build the tree, one arc at a time, by applying a sequence of actions. Examples:
#   * [spaCy](https://demos.explosion.ai/displacy?text=Kraft%2C%20owner%20of%20Milka%2C%20purchased%20Cadbury%20Dairy%20Milk%20and%20is%20now%20gearing%20up%20for%20a%20roll-out%20of%20its%20new%20brand.&model=en_core_web_sm&cpu=0&cph=0)
#   * [UUParser](https://github.com/UppsalaNLP/uuparser)
#   * [TUPA](https://github.com/huji-nlp/tupa/)
#   
# <center>
#     <img src="https://d3i71xaburhd42.cloudfront.net/c267b4a64066b56c8eef053de391c3cbe58c9eb3/3-Figure2-1.png" width=60%>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/P18-2077/">Dozat & Manning, 2018</a>)
# </div>

# ## Dependency parsing evaluation
# 
# * Unlabeled Attachment Score (**UAS**): % of words with correct head
# * Labeled Attachment Score (**LAS**): % of words with correct head and label
# 
# Always 0 $\leq$ LAS $\leq$ UAS $\leq$ 100%.

# ### Example: LAS and UAS
# 
# <center>
#     <img src="parsing_figures/as.png" width=70%/>
# </center>
# 
# <center>
#     $\mathrm{UAS}=\frac{8}{12}=67\%$
# </center>
# 
# <center>
#     $\mathrm{LAS}=\frac{7}{12}=58\%$
# </center>

# ## Transition-based parsers
# 
# Consist of a **<span style="color:blue">buffer</span>** and **<span style="color:red">stack</span>**, incrementally build the **parse** by applying **actions** (transitions).
# 
# <center>
#     <img src="parsing_figures/tb_example.png" width=97%/>
# </center>

# ### Configuration
# 
# - Stack \\(S\\): a last-in, first-out memory to keep track of words to process
# - Buffer \\(B\\): words remaining to be processed
# - Arcs \\(A\\): the dependency arcs created so far in the parse tree

# What are the possible actions? Depends which **transition system** we are using!

# Common transition systems:
# + arc-standard ([Nivre, 2003](https://aclanthology.org/W03-3017/))
# + arc-eager ([Nivre, 2004](https://www.aclweb.org/anthology/W04-0308))
# + arc-hybrid ([Kuhlmann et al., 2011](https://aclanthology.org/P11-1068/))

# ## arc-standard
# 
# Possible actions at each step:
# - **SHIFT**: move the buffer top item to the stack.
# - For each relation $r$,
#   - **RIGHT-ARC-$r$**: create $r$ arc from second stack item to stack top. Then pop stack top.
#   - **LEFT-ARC-$r$**: create $r$ arc from stack top to second stack item. Then pop second stack item.

# Two special configurations:
# - **initial**: buffer contains the words, stack contains root, and arcs are empty.
# - **terminal**: buffer is empty, stack contains only root.

# ### arc-standard example

# In[20]:


render_transitions_displacy(transitions, tokenized_sentence)


# ## Transition-based parsing as structured prediction
# 
# **Model** $p(a|c)$: how likely is action $a$ to be next, given that the current configuration is $c$?
# $$p(a|c) \approx s_\params(a,c)$$
# 
# **Training**: learn $\params$ with an annotated training set
# $$
# \argmax_\params \prod_{x \in \train} \prod_{i=1}^{|x|} s_\params(a_i,c_i)
# $$
# 
# **Decoding**: try to find the most likely action sequence
# $$\argmax_{a_1,\ldots,a_{|x|}}  \prod_{i=1}^{|x|} s_\params(a_i,c_i)$$

# ### Neural transition classifiers
# 
# Sequence-to-sequence?
# <center>
#     <img src="parsing_figures/tb1.png" width=60%/>
# </center>

# Sequence-to-sequence, but with control structure:
# <center>
#     <img src="parsing_figures/tb2.png" width=30%/>
# </center>

# ### Example neural transition classifiers
# * Each step is a new classification instance, with word embedding features ([Chen and Manning, 2014](https://aclanthology.org/D14-1082/))
# * Stack-LSTM: recurrent state updated across steps ([Dyer et al., 2015](https://aclanthology.org/P15-1033/))
# * Each step is a new classification instance, with **BiLSTM** features ([Kiperwasser and Goldberg, 2016](https://aclanthology.org/Q16-1023/))
# * Stack-pointer: global attention to select attachment ([Ma et al., 2018](https://aclanthology.org/P18-1130/))
# * Stack-transformer: self-attention for state representation ([Fernandez Astudillo et al., 2020](https://aclanthology.org/2020.findings-emnlp.89/))
# 
# <center>
#     <img src="https://d3i71xaburhd42.cloudfront.net/8292a74aba4eab2ca864b457c17b02634fef4ddd/5-Figure7-1.png" width=30%/>
# </center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/K18-2010/">Hershcovich et al., 2018</a>)
# </div>

# ### Training
# 
# + Loss function: often negative log-likelihood or max-margin
# + **Teacher forcing:**  always choose the ground truth action.
# 
# *Alternative:* (see also [MT slides](nmt_slides_active.ipynb))
# 
# + **Scheduled sampling:** with a certain probability, use model predictions instead.
# 
# But what is the **ground truth**? Treebanks contain **trees**, not action sequences!

# **Oracle**: rules to select the right action given the configuration **and the correct tree**.
# 
# <center><img src="../img/oracle.png" width=50%/></center>
# 
# <div style="text-align: right;">
#     (from <a href="https://aclanthology.org/P17-1104/">Hershcovich et al., 2017</a>)
# </div>

# ### Decoding
# 
# + Greedy decoding:
#     + Always pick the **most likely action** (according to the classifier)
#     + Continue applying more actions **until a terminal configuration is reached**

# + Beam search:
#     * Maintains a list of top-$k$ action+configuration sequences in a **beam**

# ## arc-hybrid
# 
# - **SHIFT**: move the buffer top item to the stack.
# - **RIGHT-ARC-$r$**: create $r$ arc from second stack item to stack top. Then pop stack top.
# - **LEFT-ARC-$r$**: create $r$ arc from **buffer top** to stack top. Then pop **stack top**.
# 
# <center><img src="../img/archybrid.png" width=20%/></center>
# 
# - **initial**: buffer contains the words **followed by root**, stack is **empty**, and arcs are empty.
# - **terminal**: buffer **contains only root**, stack **is empty**.

# ### arc-hybrid example
# 
# **Unlabeled parsing** (without relation labels), just for simplicity.
# 
# https://danielhers.github.io/archybrid.pdf

# <center><img src="../img/quiz_time.png"></center>
# 
# ### [ucph.page.link/tb](https://ucph.page.link/tb)
# 
# ([Responses](https://app.quizalize.com/dash/R3JvdXA6YTUzMGNkZjItYTRiYS00NGM2LTk3ZGEtZDc4YjlkMjkyODg4/activity/QWN0aXZpdHk6OWYxNzM2NTUtMjJhYi00YzVkLTgzOTUtODA3ZWYyNjczY2Fh/what))

# ## Summary: arc-hybrid vs arc-standard
# <table class="typeindex">
#   <thead>
#     <tr style="font-size: x-large; text-align: left;">
#       <th></th>
#       <th>LEFT-ARC</th>
#       <th>initial configuration</th>
#       <th>terminal configuration</th>
#     </tr>
#   </thead>
#   <tbody>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;">arc-standard</td>
#         <td style="text-align: left;">create arc from <b>stack</b> top to <b>second</b> stack item,<br>pop <b>second</b> stack item</td>
#         <td style="text-align: left;">stack contains <b>root</b>,<br>buffer contains words</td>
#         <td style="text-align: left;">stack contains <b>root</b>,<br>buffer is <b>empty</b></td>
#     </tr>
#     <tr style="font-size: x-large; text-align: left;">
#       <td style="text-align: left;">arc-hybrid</td>
#         <td style="text-align: left;">create arc from <b>buffer</b> top to stack <b>top</b>,<br>pop stack <b>top</b></td>
#         <td style="text-align: left;">stack is <b>empty</b>,<br>buffer contains words <b>and root</b></td>
#         <td style="text-align: left;">stack is <b>empty</b>,<br>buffer contains <b>root</b></td>
#     </tr>
#   </tbody>
# </table>
# 
# <center><img src="../img/archybrid.png" width=20%/>(arc-hybrid)</center>

# ## Summary
# 
# * **Dependency parsing** predicts word-to-word dependencies
# * Treebanks in many languages, thanks to **UD**
# * Fast and accurate parsing, e.g. **transition-based**

# ## Further reading
# 
# * [EACL 2014 tutorial on dependency parsing](http://stp.lingfil.uu.se/~nivre/eacl14.html)
# * [Slides about semantic parsing](https://danielhers.github.io/mr.pdf)
# * [Chapter from this book about transition-based dependency parsing](http://localhost:8888/notebooks/chapters/transition-based_dependency_parsing.ipynb)
# * [Chapter from this book about constituency parsing](parsing.ipynb) ([slides](parsing_slides.ipynb))
# * [Jurafsky & Martin, Chapter 14](https://web.stanford.edu/~jurafsky/slp3/14.pdf)