Imitation Learning.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import il_tutorial.cost_graphs as cg\n",
    "import il_tutorial.util as util\n",
    "from IPython.display import HTML"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "code_show=true; \n",
       "function code_toggle() {\n",
       " if (code_show){\n",
       " $('div.input').hide();\n",
       " } else {\n",
       " $('div.input').show();\n",
       " }\n",
       " code_show = !code_show\n",
       "} \n",
       "$( document ).ready(code_toggle);\n",
       "</script>\n",
       "The raw code for this IPython notebook is by default hidden for easier reading.\n",
       "To toggle on/off the raw code, click <a href=\"javascript:code_toggle()\">here</a>."
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML('''<script>\n",
    "code_show=true; \n",
    "function code_toggle() {\n",
    " if (code_show){\n",
    " $('div.input').hide();\n",
    " } else {\n",
    " $('div.input').show();\n",
    " }\n",
    " code_show = !code_show\n",
    "} \n",
    "$( document ).ready(code_toggle);\n",
    "</script>\n",
    "The raw code for this IPython notebook is by default hidden for easier reading.\n",
    "To toggle on/off the raw code, click <a href=\"javascript:code_toggle()\">here</a>.''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center>\n",
    "<h2>Natural Language Processing</h2>\n",
    "<br>\n",
    "<small>(COM4513/6513)</small>\n",
    "<br>\n",
    "<h2>Imitation Learning for Structured Prediction</h2>\n",
    "<p style=\"text-align:center\">\n",
    "<a href=\"http://andreasvlachos.github.io\">Andreas Vlachos</a><br>\n",
    "a.vlachos@sheffield.ac.uk<br>\n",
    "<small>Department of Computer Science<br>\n",
    "University of Sheffield\n",
    "</small>\n",
    "</p>\n",
    "\n",
    "\n",
    "<p style=\"text-align:center\">Based on the <a href=\"http://sheffieldnlp.github.io/ImitationLearningTutorialEACL2017/\">EACL2017 tutorial</a><br>with <a href=\"http://glampouras.github.io\">Gerasimos Lampouras</a> and \n",
    "<a href=\"http://www.riedelcastro.org/\">Sebastian Riedel</a></p>\n",
    "\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<h3>Some structured prediction tasks we know</h3>\n",
    "\n",
    "<table  style=\"border-style: hidden; border-collapse: collapse; padding: 50px\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>I</th> \n",
    "<th>studied</th>\n",
    "<th>in</th>\n",
    "<th>London</th>\n",
    "<th>with</th>\n",
    "<th>Sebastian</th>\n",
    "<th>Riedel</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody style=\"font-size:100%\">\n",
    "<tr>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">PRP</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">VBD</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">IN</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">NNP</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">IN</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">NNP</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">NNP</span></td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">B-LOC</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">B-PER</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">I-PER</span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>\n",
    "\n",
    "<p>\n",
    "\t\t\t\t<ul>\n",
    "  \t\t\t<li class=\"fragment\" data-fragment-index=\"1\">part of speech (PoS) tagging</li>\n",
    "  \t\t\t<li class=\"fragment\" data-fragment-index=\"2\">named entity recognition (NER)</li>\n",
    "\t\t\t\t</ul>\n",
    "\t\t\t</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p><b>Input:</b> a sentence $\\mathbf{x}=[x_1...x_N]$<br> <b>Output:</b> a sequence of labels $\\mathbf{y}=[y_{1}\\ldots y_{N}] \\in {\\cal Y}^N$</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<h3>More Structured Prediction</h3>\n",
    "\n",
    "<img src=\"images/toBeAnimated/depParse1.png\" style=\"width:100%;\">\n",
    "\n",
    "<p>Syntactic parsing, but also semantic parsing, semantic role labeling, question answering over knowledge bases, etc.</p>\n",
    "<p><b>Input:</b> a sentence $\\mathbf{x}=[x_1...x_N]$<br>\n",
    "<b>Output:</b> a meaning representation graph $\\mathbf{G}=(V,E) \\in {\\cal G_{\\mathbf{x}}}$</p> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<h3>More Structured Prediction</h3>\n",
    "\n",
    "<img src=\"images/nlg.png\" style=\"width:90%;\">\n",
    "\n",
    "<p>Natural language generation (NLG), but also summarization, decoding in machine translation, etc.</p>\n",
    "\n",
    "<p><b>Input:</b> a meaning representation<br>\n",
    "<b>Output:</b> $\\mathbf{w}=[w_1...w_N], w\\in {\\cal V}\\cup END, w_N=END$</p>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### In this lecture: Imitation Learning\n",
    "\n",
    "<p style=\"float: left;\">We assume gold standard<br> output for training</p> \n",
    "<img src=\"images/tikz/StucturedPredictionDef.png\" style=\"width:40%; float: right;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p style=\"float: left;\">But we train a classifier to predict<br> <b>actions</b> constructing the output.</p> \n",
    "<img src=\"images/tikz/StucturedPrediction.png\" style=\"width:40%; float: right;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Originated in robotics\n",
    "\n",
    "\n",
    "<a href=\"http://www.cs.cmu.edu/~sross1/publications/Ross-AIStats11-Slides.pdf\"><img src=\"images/imitationFromRoss.png\" style=\"width:75%;\"></a>\n",
    "\n",
    "\n",
    "**Meta-learning**: better model (&asymp;policy) by generating better training data from expert demonstrations. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Two main paradigms\n",
    "\n",
    "Joint modeling, a.k.a: \n",
    "- global inference\n",
    "- structured models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Incremental modeling, a.k.a:\n",
    "- local \n",
    "- greedy\n",
    "- pipeline\n",
    "- transition-based\n",
    "- history-based"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Joint modeling\n",
    "\n",
    "A model (e.g. conditional random fields) that scores complete outputs (e.g. label sequences):\n",
    "\n",
    "$$\\mathbf{\\hat y} =\\hat y_{1}\\ldots \\hat y_{N} = \\mathop{\\arg \\max}_{Y \\in {\\cal Y}^N} f(y_{1}\\ldots y_{N}, \\mathbf{x})$$\n",
    "\n",
    "<ul class=\"fragment\">\n",
    "\t\t\t\t\t<li>exhaustive exploration of the search space</li>\n",
    "\t\t\t\t\t<li>large/complex search spaces are challenging</li>\n",
    "\t\t\t\t\t<li>efficient dynamic programming restricts modelling flexibility\n",
    "\t\t\t\t\t\t(i.e. Markov assumptions)</li>\n",
    "\t\t\t\t</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Incremental modeling\n",
    "\n",
    "A classifier predicting a label at a time given the previous ones:\n",
    "\n",
    "\n",
    "\\begin{align}\n",
    "\\hat y_1 &=\\mathop{\\arg \\max}_{y \\in {\\cal Y}} f(y, \\mathbf{x}),\\\\\n",
    "\\mathbf{\\hat y} = \\quad \\hat y_2 &=\\mathop{\\arg \\max}_{y \\in {\\cal Y}} f(y, \\mathbf{x}, \\hat y_1), \\cdots\\\\\n",
    "\\hat y_N &=\\mathop{\\arg \\max}_{y \\in {\\cal Y}} f(y, \\mathbf{x}, \\hat y_{1} \\ldots \\hat y_{N-1})\n",
    "\\end{align}\n",
    "\n",
    "<ul class=\"fragment\">\n",
    "\t\t\t\t\t<li>use our favourite classifier</li>\n",
    "\t\t\t\t\t<li>no restrictions on features</li>\n",
    "\t\t\t\t\t<li>prone to error propagation (i.i.d. assumption broken)</li>\n",
    "\t\t\t\t\t<li>local model not trained wrt the task-level loss</li>\n",
    "\t\t\t\t</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Imitation learning\n",
    "\n",
    "Improve incremental modeling to:\n",
    "- address error-propagation\n",
    "- train wrt the task-level loss function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Meta-learning**: use our favourite classifier and features,\n",
    "but generate better (non-i.i.d.) training data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To apply IL we need:\n",
    "- transition system (what our classifier can do)\n",
    "- task loss (what we optimize for)\n",
    "- expert policy (the teacher to help us)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<h3>Transition system</h3>\n",
    "\n",
    "<p>The <b>actions</b> $\\cal A$ the classifier $f$ can predict and their effect on the <b>state</b> which tracks the prediction: $S_{t+1}=S_1(\\alpha_1\\ldots\\alpha_t)$</p>\n",
    "\n",
    "<img src=\"images/tikz/IncrementalStructure.png\" style=\"align:center; width:65%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<h3>Transition system</h3>\n",
    "\n",
    "<p style=\"text-align: left; border:3px; border-radius: 25px; background-color:lightgrey; border-style:solid; border-color:black; padding: 0.3em; font-size: 75%\">\n",
    "\\begin{align}\n",
    "& \\textbf{Input:} \\; sentence \\; \\mathbf{x}\\\\\n",
    "& state \\; S_1=initialize(\\mathbf{x}); timestep \\; t = 1\\\\\n",
    "& \\mathbf{while}\\; S_t \\; \\text{not final}\\; \\mathbf{do}\\\\\n",
    "& \\quad action \\; \\alpha_t = \\mathop{\\arg \\max}_{\\alpha \\in {\\cal A}} f(\\alpha, \\mathbf{x})\\\\\n",
    "& \\quad S_{t+1}=S_t(\\alpha_t); t=t+1\\\\\n",
    "\\end{align}\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<ul>\n",
    "<li><b>PoS tagging?</b> <span class=\"fragment\">for each word, left-to-right, predict a PoS tag which is added to the output</span></li>\n",
    "<li class=\"fragment\"><b>Named entity recognition?</b> <span class=\"fragment\">As above, just use NER tags!</span></li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Supervising the classifier\n",
    "\n",
    "What are good actions in incremental structured prediction?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Those that reach $S_{final} = S_1(\\alpha_1\\ldots\\alpha_T)$ with low **task loss**:\n",
    "\n",
    "$$loss  = L(S_{final}, \\mathbf{y}) \\geq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<ul>\n",
    "<li><b>PoS tagging?</b> <span class=\"fragment\">Hamming loss: number of incorrect tags</span></li>\n",
    "<li class=\"fragment\"><b>NER?</b> <span class=\"fragment\">number of false positives and false negatives</span></li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Action assessment \n",
    "\n",
    "<table style=\"font-size:80%; border-style: hidden; border-collapse: collapse; padding: 50px\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>I</th> \n",
    "<th>studied</th>\n",
    "<th>in</th>\n",
    "<th>London</th>\n",
    "<th>with</th>\n",
    "<th>Sebastian</th>\n",
    "<th>Riedel</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td>PRP</td>\n",
    "<td>VBD</td>\n",
    "<td>IN</td>\n",
    "<td>NNP</td>\n",
    "<td>IN</td>\n",
    "<td>NNP</td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">NNP</span></td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">B-LOC</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">O</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"2\">B-PER</span></td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"3\">I-PER</span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>\n",
    "\n",
    "<p>How many incorrect PoS tags due to $\\alpha_6$  being NNP? <span class=\"fragment\" data-fragment-index=\"1\"><b>0</b></span>\n",
    "</p>\n",
    "<p class=\"fragment\" data-fragment-index=\"2\"> How many $FP+FN$ due to $\\alpha_6$ being B-PER? <span class=\"fragment\" data-fragment-index=\"3\"><br><b>Depends!</b> If $\\alpha_7$ is</span>\n",
    "<ul class=\"fragment\" data-fragment-index=\"3\">\n",
    "<li>I-PER:  $0$ (correct)</li> \n",
    "<li>O: $2$ (1FP+1FN)</li>\n",
    "<li>B-*: $3$ (2FP+1FN)</li>\n",
    "</ul>\n",
    "</p>\n",
    "<p class=\"fragment\" data-fragment-index=\"3\">$FP+FN$ loss is <b>non-decomposable</b> wrt the transition system\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Expert policy\n",
    "\n",
    "Returns the best action at the current state by looking at the gold standard assuming **future actions are also optimal**:\n",
    "\n",
    "$$\\alpha^{\\star}=\\pi^{\\star}(S_t, \\mathbf{y}) = \\mathop{\\arg \\min}_{\\alpha \\in {\\cal A}} L(S_t(\\alpha,\\pi^{\\star}),\\mathbf{y})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p style=\"float: left;\">Only available for the training data: an expert<br>demonstrating how to perform the task </p> <a href=\"http://www.salon.com/2016/10/06/what-makes-a-good-teacher-why-certifications-and-standards-dont-guarantee-quality-educators_partner/\"><img src=\"images/english_teacher.jpg\" style=\"width:20%; float: right;\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Expert policy\n",
    "\n",
    "**In pairs**: What action should $\\pi^{\\star}$ return?\n",
    "\n",
    "<table style=\"border-style: hidden; border-collapse: collapse; padding: 50px\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>I</th> \n",
    "<th>studied</th>\n",
    "<th>in</th>\n",
    "<th>London</th>\n",
    "<th>with</th>\n",
    "<th>Sebastian</th>\n",
    "<th>Riedel</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td>O</td>\n",
    "<td>O</td>\n",
    "<td>O</td>\n",
    "<td>B-LOC</td>\n",
    "<td>O</td>\n",
    "<td>B-PER</td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"1\">I-PER</span></td>\n",
    "</tr>\n",
    "<tr class=\"fragment\" data-fragment-index=\"2\">\n",
    "<td>O</td>\n",
    "<td>O</td>\n",
    "<td>O</td>\n",
    "<td>B-LOC</td>\n",
    "<td>O</td>\n",
    "<td>O</td>\n",
    "<td><span class=\"fragment\" data-fragment-index=\"3\">O</span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Takes previous actions into account (**dynamic** vs **static**)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Finding the optimal action can be expensive but we can learn with **sub-optimal** experts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Imitation learning for part-of-speech tagging\n",
    "\n",
    "<table style=\"border-style: hidden; border-collapse: collapse; padding: 50px\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>I</th>\n",
    "<th>can</th>\n",
    "<th>fly</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td><span>Pronoun</span></td>\n",
    "<td><span>Modal</span></td>\n",
    "<td><span>Verb</span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " **Task loss**: <span class=\"fragment\">Hamming loss: number of incorrectly predicted tags</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Transition system**: <span class=\"fragment\">Tag each token left-to-right</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Expert policy**: <span class=\"fragment\">Return the next tag from the gold standard</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<h3>Gold standard in search space</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <div id=\"9e53f3a0-3191-11e7-980f-9cb6d0d006dd\" class=\"carousel\" data-ride=\"carousel\" data-interval=\"false\">\n",
       "          <div class=\"carousel-inner\" role=\"listbox\">\n",
       "          <div class=\"item active\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id1\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id2\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line marker-end=\"url(#id2)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id3\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line marker-end=\"url(#id3)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line marker-end=\"url(#id3)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"200\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id4\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line marker-end=\"url(#id4)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line marker-end=\"url(#id4)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"200\" y2=\"150\" /><line marker-end=\"url(#id4)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"150\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "          </div>\n",
       "          <!-- Controls -->\n",
       "          <a href=\"#9e53f3a0-3191-11e7-980f-9cb6d0d006dd\" role=\"button2\" data-slide=\"prev\">Previous</a>\n",
       "          &nbsp\n",
       "          <a  href=\"#9e53f3a0-3191-11e7-980f-9cb6d0d006dd\" role=\"button2\" data-slide=\"next\">Next</a>\n",
       "        </div>\n",
       "        "
      ],
      "text/plain": [
       "<il_tutorial.util.Carousel at 0x7fabf4fc5ba8>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "paths = [[],[(0,4),(1,3)],[(0,4),(1,3),(2,2)],[(0,4),(1,3),(2,2),(3,1)]]\n",
    "rows = ['Noun', 'Verb', 'Modal', 'Pronoun','NULL']\n",
    "columns = ['NULL','I', 'can', 'fly']\n",
    "cbs = []\n",
    "for path in paths:\n",
    "    cbs.append(cg.draw_cost_breakdown(rows, columns, path))\n",
    "util.Carousel(cbs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p>\n",
    "<ul>\n",
    "<li>Three actions to complete the output</li>\n",
    "<li>Expert policy replicates the gold standard</li>\n",
    "</ul>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<h3>Training a classifier<span class=\"fragment\" data-fragment-index=\"1\"> with structure features </span></h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id5\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line marker-end=\"url(#id5)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line marker-end=\"url(#id5)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"200\" y2=\"150\" /><line marker-end=\"url(#id5)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"150\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gold_path = [(0,4),(1,3),(2,2),(3,1)]\n",
    "cb_gold = cg.draw_cost_breakdown(rows, columns, gold_path)\n",
    "cb_gold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<table style=\"font-size:100%; border-style:hidden; border-collapse:collapse; padding:50px; float:left;\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>timestep</th>\n",
    "<th>label ($\\alpha_t$)</th>\n",
    "<th>features ($\\phi(S_{t-1},\\mathbf{x})$)</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td> $t=1$ </td>\n",
    "<td><b>Pronoun</b></td>\n",
    "<td>token=I, ...<span class=\"fragment\" data-fragment-index=\"1\">, prev=<b>NULL</b></span></td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td> $t=2$ </td>\n",
    "<td><b>Modal</b></td>\n",
    "<td>token=can, ...<span class=\"fragment\" data-fragment-index=\"1\">, prev=<b>Pronoun</b></span></td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td> $t=3$ </td>\n",
    "<td><b>Verb</b></td>\n",
    "<td>token=fly, ...<span class=\"fragment\" data-fragment-index=\"1\">, prev=<b>Modal</b></span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Algorithm\n",
    "\n",
    "<p style=\"border:3px; border-radius: 25px; background-color:lightgrey; border-style:solid; border-color:black; padding: 0.3em; font-size: 80%\">\n",
    "\\begin{align}\n",
    "& \\textbf{Input:} \\; D_{train} = \\{(\\mathbf{x}^1,\\mathbf{y}^1)...(\\mathbf{x}^M,\\mathbf{y}^M)\\}, \\; \\text{expert}\\; \\pi^{\\star}, \\; \\text{classifier} \\; H\\\\\n",
    "& \\text{set training examples}\\; \\cal E = \\emptyset\\\\\n",
    "& \\mathbf{for} \\; (\\mathbf{x},\\mathbf{y}) \\in D_{train} \\; \\mathbf{do}\\\\\n",
    "& \\quad \\text{generate expert trajectory} \\; \\alpha_1^{\\star}\\dots \\alpha_T^{\\star}  = \\pi^{\\star}(\\mathbf{x},\\mathbf{y})\\\\\n",
    "& \\quad \\mathbf{for} \\; \\alpha^{\\star}_t \\in \\alpha_1^{\\star}\\dots \\alpha_T^{\\star} \\; \\mathbf{do}\\\\\n",
    "& \\quad \\quad \\text{extract features}\\; \\mathit{feat}=\\phi(\\mathbf{x},S_{t-1}) \\\\\n",
    "& \\quad \\quad \\cal E = \\cal E \\cup (\\mathit{feat},\\alpha^{\\star}_t)\\\\\n",
    "& \\text{learn} \\; H\\; \\text{from}\\; \\cal E\\\\\n",
    "\\end{align}\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exposure bias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <div id=\"a3e6ca7c-3191-11e7-980f-9cb6d0d006dd\" class=\"carousel\" data-ride=\"carousel\" data-interval=\"false\">\n",
       "          <div class=\"carousel-inner\" role=\"listbox\">\n",
       "          <div class=\"item active\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id5\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line marker-end=\"url(#id5)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line marker-end=\"url(#id5)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"200\" y2=\"150\" /><line marker-end=\"url(#id5)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"150\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id6\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">Noun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">Verb</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">Modal</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">Pronoun</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">I</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">can</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">fly</text><line marker-end=\"url(#id6)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line marker-end=\"url(#id6)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"200\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "          </div>\n",
       "          <!-- Controls -->\n",
       "          <a href=\"#a3e6ca7c-3191-11e7-980f-9cb6d0d006dd\" role=\"button2\" data-slide=\"prev\">Previous</a>\n",
       "          &nbsp\n",
       "          <a  href=\"#a3e6ca7c-3191-11e7-980f-9cb6d0d006dd\" role=\"button2\" data-slide=\"next\">Next</a>\n",
       "        </div>\n",
       "        "
      ],
      "text/plain": [
       "<il_tutorial.util.Carousel at 0x7fabf4fcd5f8>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wrong_path = [(0,4),(1,3),(2,1)]\n",
    "cb_wrong = cg.draw_cost_breakdown(rows, columns, wrong_path)\n",
    "util.Carousel([cb_gold, cb_wrong])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p style=\"float: left; font-size: 80%\">We had seen: &nbsp;&nbsp; \n",
    "<table style=\"float: left; border-style: hidden; border-collapse: collapse; font-size: 80%\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>timestep</th>\n",
    "<th>label</th>\n",
    "<th>features</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td>t=3</td>\n",
    "<td><b>Verb</b></td>\n",
    "<td>token=fly,..., prev=<b>Modal</b></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p style=\"float: left; font-size: 80%\">but not: &nbsp;&nbsp;\n",
    "<table style=\"float: left; border-style: hidden; border-collapse: collapse; font-size: 80%\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>timestep</th>\n",
    "<th>label</th>\n",
    "<th>features</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td>t=3</td>\n",
    "<td><b>Verb</b></td>\n",
    "<td>token=fly,..., <span style=\"color:red\">prev=<b>Verb</b></span></td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table></p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Addressing exposure with Rollins\n",
    "\n",
    "<p style=\"float: left;\">Allow the classifier to guide the learning<br></p>  <a href=\"https://www.pinterest.com/explore/affordable-driving-school/\"><img src=\"images/driving_mix.jpg\" style=\"width:35%; float: right;\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Define a **rollin** policy that sometimes uses the expert $\\pi^{\\star}$ and other times the classifier $H$:\n",
    "\n",
    "$$\\pi^{in} = \\beta\\pi^{\\star} + (1-\\beta)H$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### DAgger algorithm\n",
    "\n",
    "<p style=\"border:3px; border-radius: 25px; background-color:lightgrey; border-style:solid; border-color:black; padding: 0.3em; font-size: 80%\">\n",
    "\\begin{align}\n",
    "& \\textbf{Input:} \\; D_{train} = \\{(\\mathbf{x}^1,\\mathbf{y}^1)...(\\mathbf{x}^M,\\mathbf{y}^M)\\}, \\; \\text{expert}\\; \\pi^{\\star}, \\; \\text{classifier} \\; H\\\\\n",
    "& \\text{set training examples}\\; \\cal E = \\emptyset ,\\; \\color{red}{\\pi^{\\star}\\; \\mathrm{probability}\\; \\beta=1}\\\\\n",
    "& \\mathbf{while}\\; \\text{termination condition not reached}\\; \\mathbf{do}\\\\\n",
    "& \\quad \\color{red}{\\text{set rollin policy} \\; \\pi^{in} = \\beta\\pi^{\\star} + (1-\\beta)H}\\\\\n",
    "& \\quad \\mathbf{for} \\; (\\mathbf{x},\\mathbf{y}) \\in D_{train} \\; \\mathbf{do}\\\\\n",
    "& \\quad \\quad \\color{red}{\\text{generate trajectory} \\; \\hat \\alpha_1\\dots\\hat \\alpha_T  = \\pi^{in}(\\mathbf{x},\\mathbf{y})}\\\\\n",
    "& \\quad \\quad \\mathbf{for} \\; \\hat \\alpha_t \\in \\hat \\alpha_1\\dots\\hat \\alpha_T \\; \\mathbf{do}\\\\\n",
    "& \\quad \\quad \\quad \\color{red}{\\text{ask expert for best action}\\; \\alpha^{\\star} = \\pi^{\\star}(\\mathbf{x},S_{t-1})} \\\\\n",
    "& \\quad \\quad \\quad \\text{extract features} \\; \\mathit{feat}=\\phi(\\mathbf{x},S_{t-1}) \\\\\n",
    "& \\quad \\quad \\quad \\cal E = \\cal E \\cup (\\mathit{feat},\\alpha^{\\star})\\\\\n",
    "& \\quad \\text{learn}\\; H \\; \\text{from}\\; \\cal E\\\\\n",
    "& \\quad \\color{red}{\\text{decrease} \\; \\beta}\\\\\n",
    "\\end{align}\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### DAgger algorithm\n",
    "\n",
    "Proposed by [Ross et al. (2011)](http://www.cs.cmu.edu/~sross1/publications/Ross-AIStats11-NoRegret.pdf) motivated by robotics\n",
    "- first iteration is standard classification training\n",
    "- task loss and gold standard are implicitly considered via the expert\n",
    "- DAgger: the Datasets in each iteration are Aggregated"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**rollins** help recover from previous mistakes. How do we learn the future impact of a mistake?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**rollout**: try each action available and see what happens when future actions are taken by mixing the classifier and the expert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Rollins and rollouts\n",
    "\n",
    "<img src=\"images/lols.png\" style=\"width:60%;\">\n",
    "- first proposed in SEARN ([Daumé III et al., 2009](http://hunch.net/~jl/projects/reductions/searn/searn.pdf))\n",
    "- used to hybridise DAgger by [Vlachos and Clark (2014)](http://www.aclweb.org/anthology/Q14-1042)\n",
    "- Locally Optimal Learning to Search ([Chang et al., 2015](https://arxiv.org/pdf/1502.02206.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Let's see some applications"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Remember this?\n",
    "\n",
    "<img src=\"images/toBeAnimated/depParse1.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center>\n",
    "<img src=\"images/stateTransitExpert.png\">\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Learning a classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <div id=\"a71b9d4e-3191-11e7-980f-9cb6d0d006dd\" class=\"carousel\" data-ride=\"carousel\" data-interval=\"false\">\n",
       "          <div class=\"carousel-inner\" role=\"listbox\">\n",
       "          <div class=\"item active\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id7\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">SHIFT</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">REDUCE</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">ARC-L</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">ARC-R</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">S0</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">S1</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">S2</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">S3</text><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id8\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">SHIFT</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">REDUCE</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">ARC-L</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">ARC-R</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">S0</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">S1</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">S2</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">S3</text><line marker-end=\"url(#id8)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id9\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">SHIFT</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">REDUCE</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">ARC-L</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">ARC-R</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">S0</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">S1</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">S2</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">S3</text><line marker-end=\"url(#id9)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"50\" /><line marker-end=\"url(#id9)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "<div class=\"item\"><svg baseProfile=\"full\" height=\"315.0\" version=\"1.1\" width=\"500\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><defs><marker id=\"id10\" markerHeight=\"10\" markerWidth=\"10\" orient=\"auto\" refX=\"5\" refY=\"5\"><path d=\"M 0 0 L 10 5 L 0 10 z\" fill=\"blue\" /></marker></defs><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"50\">SHIFT</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"100\">REDUCE</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"150\">ARC-L</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"200\">ARC-R</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"0\" y=\"250\">NULL</text><text style=\"font-size:25px; font-family:Lato\" x=\"100\" y=\"300\">S0</text><text style=\"font-size:25px; font-family:Lato\" x=\"200\" y=\"300\">S1</text><text style=\"font-size:25px; font-family:Lato\" x=\"300\" y=\"300\">S2</text><text style=\"font-size:25px; font-family:Lato\" x=\"400\" y=\"300\">S3</text><line marker-end=\"url(#id10)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"50\" /><line marker-end=\"url(#id10)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"50\" y2=\"50\" /><line marker-end=\"url(#id10)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"50\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"105\" x2=\"195\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"205\" x2=\"295\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"50\" y2=\"50\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"100\" y2=\"100\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"150\" y2=\"150\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"200\" y2=\"200\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"305\" x2=\"395\" y1=\"250\" y2=\"250\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"100\" x2=\"100\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"200\" x2=\"200\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"300\" x2=\"300\" y1=\"205\" y2=\"245\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"55\" y2=\"95\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"105\" y2=\"145\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"155\" y2=\"195\" /><line stroke=\"rgb(10%,10%,16%)\" stroke-dasharray=\"5 5\" x1=\"400\" x2=\"400\" y1=\"205\" y2=\"245\" /></svg></div>\n",
       "          </div>\n",
       "          <!-- Controls -->\n",
       "          <a href=\"#a71b9d4e-3191-11e7-980f-9cb6d0d006dd\" role=\"button2\" data-slide=\"prev\">Previous</a>\n",
       "          &nbsp\n",
       "          <a  href=\"#a71b9d4e-3191-11e7-980f-9cb6d0d006dd\" role=\"button2\" data-slide=\"next\">Next</a>\n",
       "        </div>\n",
       "        "
      ],
      "text/plain": [
       "<il_tutorial.util.Carousel at 0x7fabf4fdf2e8>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dep_rows = ['SHIFT', 'REDUCE', 'ARC-L', 'ARC-R','NULL']\n",
    "dep_columns = ['S0','S1', 'S2', 'S3']\n",
    "dep_cbs = []\n",
    "dep_paths = [[],[(0,4),(1,0)],[(0,4),(1,0),(2,0)],[(0,4),(1,0),(2,0),(3,2)]]\n",
    "for path in dep_paths:\n",
    "    dep_cbs.append(cg.draw_cost_breakdown(dep_rows, dep_columns, path))\n",
    "util.Carousel(dep_cbs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<table style=\"font-size:100%; border-style:hidden; border-collapse:collapse; padding:50px; float:left;\">\n",
    "<thead>\n",
    "<tr>\n",
    "<th>timestep</th>\n",
    "<th>label ($\\alpha_t$)</th>\n",
    "<th>features ($\\phi(S_{t-1},\\mathbf{x})$)</th>\n",
    "</tr>\n",
    "</thead>\n",
    "<tbody>\n",
    "<tr>\n",
    "<td> $t=1$ </td>\n",
    "<td><b>SHIFT</b></td>\n",
    "<td>??</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td> $t=2$ </td>\n",
    "<td><b>SHIFT</b></td>\n",
    "<td>??</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td> $t=3$ </td>\n",
    "<td><b>REDUCE</b></td>\n",
    "<td>??</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<h3>Features</h3>\n",
    "<img src=\"images/tikz/depParseArcEager5.png\" style=\"width:1000px; border:none; box-shadow:none;\">\n",
    "\n",
    "<p style=\"font-size: 100%\">Stack = [ROOT, had, effect]</b>\n",
    "\n",
    "<p style=\"font-size: 100%\">Buffer = [on, financial, markets, .]</b>\n",
    "\n",
    "<p style=\"font-size: 100%\" class=\"fragment\">Features based on the words/PoS in stack and buffer:\n",
    "\t\t\t\t\t<br> wordS1=effect, wordB1=on, wordS2=had, posS1=NOUN, etc.\n",
    "\t\t\t\t</p>\n",
    "<p style=\"font-size: 100%\" class=\"fragment\">Features based on the dependencies so far:\n",
    "\t\t\t\t\t<br> depS1=dobj, depLeftChildS1=amod, depRightChildS1=NULL, etc.\n",
    "\t\t\t\t</p>\n",
    "\n",
    "<p style=\"font-size: 100%\" class=\"fragment\">Features based on previous transitions:\n",
    "\t\t\t\t\t<br> $r_{t-1}=\\text{Right-Arc}(dobj)$, etc.\n",
    "\t\t\t\t</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### When we fall off the trajectory\n",
    "\n",
    "<center>\n",
    "<img src=\"images/stateTransit.png\" width=\"100%\">\n",
    "</center>\n",
    "\n",
    "<center>\n",
    "<img src=\"images/stateTransitErrorPart.png\" width=\"90%\">\n",
    "</center>\n",
    "\n",
    "- No suitable training data to teach us what to do.\n",
    "- Next gold action might not be possible/optimal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Finding the best action\n",
    "\n",
    "<center>\n",
    "<img src=\"images/determReachStatesScoredBest.png\">\n",
    "</center>\n",
    "\n",
    "SHIFT would be the best if everything had been correct (Loss=0), but not anymore."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Imitation learning for dependency parsing\n",
    "\n",
    "<p style=\"border:3px; border-radius: 25px; background-color:lightgrey; border-style:solid; border-color:black; padding: 0.3em; font-size: 80%\">\n",
    "\\begin{align}\n",
    "& \\textbf{Input:} \\; D_{train} = \\{(\\mathbf{x}^1,\\mathbf{y}^1)...(\\mathbf{x}^M,\\mathbf{y}^M)\\}, \\; \\text{expert}\\; \\pi^{\\star}, \\; \\text{classifier} \\; H\\\\\n",
    "& \\text{set training examples}\\; \\cal E = \\emptyset ,\\; \\color{red}{\\pi^{\\star}\\; \\mathrm{probability}\\; \\beta=1}\\\\\n",
    "& \\mathbf{while}\\; \\text{termination condition not reached}\\; \\mathbf{do}\\\\\n",
    "& \\quad \\color{red}{\\text{set rollin policy} \\; \\pi^{in} = \\beta\\pi^{\\star} + (1-\\beta)H}\\\\\n",
    "& \\quad \\mathbf{for} \\; (\\mathbf{x},\\mathbf{y}) \\in D_{train} \\; \\mathbf{do}\\\\\n",
    "& \\quad \\quad \\color{red}{\\text{generate trajectory} \\; \\hat \\alpha_1\\dots\\hat \\alpha_T  = \\pi^{in}(\\mathbf{x},\\mathbf{y})}\\\\\n",
    "& \\quad \\quad \\mathbf{for} \\; \\hat \\alpha_t \\in \\hat \\alpha_1\\dots\\hat \\alpha_T \\; \\mathbf{do}\\\\\n",
    "& \\quad \\quad \\quad \\color{red}{\\text{ask expert for best action}\\; \\alpha^{\\star} = \\pi^{\\star}(\\mathbf{x},S_{t-1})} \\\\\n",
    "& \\quad \\quad \\quad \\text{extract features} \\; \\mathit{feat}=\\phi(\\mathbf{x},S_{t-1}) \\\\\n",
    "& \\quad \\quad \\quad \\cal E = \\cal E \\cup (\\mathit{feat},\\alpha^{\\star})\\\\\n",
    "& \\quad \\text{learn}\\; H \\; \\text{from}\\; \\cal E\\\\\n",
    "& \\quad \\color{red}{\\text{decrease} \\; \\beta}\\\\\n",
    "\\end{align}\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Expert policy\n",
    "\n",
    "<center>\n",
    "<img src=\"images/oracle-delphi.jpg\">\n",
    "</center>\n",
    "\n",
    "Just like the oracle, but it takes the previous actions into account (dynamic oracle)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Results<h5>[Goldberg and Nivre 2012](http://www.aclweb.org/anthology/C12-1059)</h5>\n",
    "<img src=\"images/dependResultBars.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### More applications\n",
    "\n",
    "<p  style=\"float: left;\">Incremental coreference resolution<br>\n",
    "(<a href=\"http://cs.stanford.edu/people/kevclark/resources/clark-manning-acl15-entity.pdf\">Clark and Manning, 2015</a>)\n",
    "</p>\n",
    "<a href=\"http://nlp.stanford.edu/projects/coref.shtml\"><img src=\"images/corefexample.png\" style=\"width:40%; float: right;\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<p  style=\"float: left;\">Recurrent Neural Network training<br>\n",
    "(<a href=\"https://arxiv.org/pdf/1511.06732.pdf\">Ranzato et al., 2016</a>)\n",
    "</p>\n",
    "<img src=\"images/mixer.png\" style=\"width:40%; float: right;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "And some of my own:\n",
    "- [Biomedical information extraction](http://www.biomedcentral.com/content/pdf/1471-2105-13-S11-S5.pdf)\n",
    "- [Natural Language Generation](https://aclweb.org/anthology/C/C16/C16-1105.pdf)\n",
    "- [Semantic Parsing](http://aclweb.org/anthology/P16-1001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Summary\n",
    "\n",
    "Imitation learning:\n",
    "- better training data for incremental predictors\n",
    "- addresses error propagation\n",
    "- many successful applications"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Coming up next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<img src=\"https://c1.staticflickr.com/1/133/366958167_939986949c_b.jpg\" style=\"width:50%; border:none; box-shadow:none;\">\n",
    "\n",
    "**Everything can be examined**: lecture slides, bibliography, classroom discussion, guest lectures, lab content, etc.\n",
    "\n",
    "Prepare following the advice in the booklets ([UG](http://www.dcs.shef.ac.uk/intranet/teaching/public/tutorials/level1/Personal%20Tutorial%20booklet.pdf),[PG](http://www.dcs.shef.ac.uk/intranet/teaching/public/tutorials/MScTutorialSystem1617.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<img src=\"https://c1.staticflickr.com/5/4079/4759535950_7bca6684c8_b.jpg\" style=\"width:60%; border:none; box-shadow:none;\">\n",
    "\n",
    "...for your hard work during the module and your feedback!\n",
    "\n",
    "Please give more feedback on the course in the forms provided by the department!\n",
    "\n",
    "Future students will be grateful!"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.5.2"
  },
  "livereveal": {
   "height": 768,
   "start_slideshow_at": "selected",
   "theme": "solarized",
   "transition": "slide",
   "width": 1024
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}