03_more_imitation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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": 3,
   "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": 3,
     "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>Connections and interpretations</h2>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Why does IL work?\n",
    "\n",
    "A bit of theory (Goodman)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Reinforcement learning\n",
    "\n",
    "<p style=\"float: left;\">\n",
    "<ul style=\"float: left;\">\n",
    "<li>states defined via features</li>\n",
    "<li>the agent is a classifier</li>\n",
    "<li>rewards?</li>\n",
    "</ul>\n",
    "</p>\n",
    "\n",
    "<a href=\"https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node28.html\"><img src=\"images/RL_sutton.png\" style=\"width:40%; float: right;\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Inverse reinforcement learning**\n",
    "\n",
    "- we have the expert policy (inferred from the gold standard in the training data)\n",
    "- we infer the per-action reward function (rollin/out)\t\t\t\t\n",
    "\n",
    "\n",
    "LOLS with classifier only rollouts is RL ([Chang et al., 2015](https://arxiv.org/pdf/1502.02206.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Inverse reinforcement learning\n",
    "\n",
    "- and learn a policy (classifier) to generalize to unseen data\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Bandit learning\n",
    "\n",
    "Rolling out each action can be expensive:\n",
    "- many possible actions\n",
    "- expensive loss functions to calculate\n",
    "\n",
    "What if we only rollout one? \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<img src=\"images/bandits.jpg\" style=\"float: right; width:40%;\">\n",
    "\n",
    "**Bandit Learning** \n",
    "\n",
    "Structured Contextual Bandit LOLS ([Chang et al., 2015](https://arxiv.org/pdf/1502.02206.pdf))\n",
    "\n",
    "[Sokolov et al. (2016)](http://www.cl.uni-heidelberg.de/~sokolov/pubs/sokolov16learning.pdf) used bandit feedback for chunking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Semi/Unsupervised learning\n",
    "\n",
    "Learning with non-decomposable loss functions means\n",
    "- no need to know the correct actions\n",
    "- learn to predict them in order to minimize the loss\n",
    "<img src=\"images/tikz/semParse.png\" style=\"width:80%;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "UNSEARN ([Daumé III, 2009](http://www.umiacs.umd.edu/~hal/docs/daume09unsearn.pdf)): Predict the structured output so that you can predict the input from it (auto-encoder!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Negative data sampling\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <div id=\"dfa8056e-184e-11e7-bd69-df4f424074db\" 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 marker-end=\"url(#id1)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"100\" x2=\"200\" y1=\"250\" y2=\"200\" /><line marker-end=\"url(#id1)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"200\" x2=\"300\" y1=\"200\" y2=\"150\" /><line marker-end=\"url(#id1)\" 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=\"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=\"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=\"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=\"50\" /><line marker-end=\"url(#id3)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"50\" y2=\"100\" /><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"410\" y=\"100\">cost = 1</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"185\" y=\"185\">rollin</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"285\" y=\"35\">explore</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"385\" y=\"35\">rollout</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=\"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=\"100\" /><line marker-end=\"url(#id4)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"100\" y2=\"50\" /><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"410\" y=\"50\">cost = 2</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"185\" y=\"185\">rollin</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"285\" y=\"85\">explore</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"385\" y=\"35\">rollout</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=\"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\" /><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"410\" y=\"100\">cost = 0</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"185\" y=\"185\">rollin</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"285\" y=\"135\">explore</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"385\" y=\"35\">rollout</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=\"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=\"200\" /><line marker-end=\"url(#id6)\" stroke=\"rgb(10%,10%,16%)\" stroke-width=\"2.5\" x1=\"300\" x2=\"400\" y1=\"200\" y2=\"100\" /><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"410\" y=\"100\">cost = 1</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"185\" y=\"185\">rollin</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"285\" y=\"185\">explore</text><text style=\"font-size:25px; font-weight:bold; font-family:Lato\" x=\"385\" y=\"35\">rollout</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>\n",
       "          <!-- Controls -->\n",
       "          <a href=\"#dfa8056e-184e-11e7-bd69-df4f424074db\" role=\"button2\" data-slide=\"prev\">Previous</a>\n",
       "          &nbsp\n",
       "          <a  href=\"#dfa8056e-184e-11e7-bd69-df4f424074db\" role=\"button2\" data-slide=\"next\">Next</a>\n",
       "        </div>\n",
       "        "
      ],
      "text/plain": [
       "<il_tutorial.util.Carousel at 0x7fcc4c332f28>"
      ]
     },
     "execution_count": 3,
     "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",
    "gold_path = [(0,4),(1,3),(2,2),(3,1)]\n",
    "cbs=[]\n",
    "cb_gold = cg.draw_cost_breakdown(rows, columns, gold_path)\n",
    "cbs.append(cb_gold)\n",
    "wrong_path = [(0,4),(1,2)]\n",
    "cb_wrong = cg.draw_cost_breakdown(rows, columns, wrong_path)\n",
    "cbs.append(cb_wrong)\n",
    "p = gold_path.copy()\n",
    "for i in range(4):\n",
    "    p = gold_path.copy()\n",
    "    p[2] = (gold_path[2][0],i)\n",
    "    if p == gold_path:\n",
    "        cost = 0\n",
    "    elif i==1:\n",
    "        cost =2\n",
    "        p[3] = (3,0)\n",
    "    else:\n",
    "        cost = 1\n",
    "    cbs.append(cg.draw_cost_breakdown(rows, columns, p, cost, p[3], roll_in_cell=p[1],roll_out_cell=(3,0), explore_cell=p[2]))\n",
    "util.Carousel(cbs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "- Expert action sequence → positive example\n",
    "- All other action sequences → negative examples\n",
    "\n",
    "Generate useful negative samples around the expert, related to **adversarial training** ([Ho and Ermon, 2016](https://arxiv.org/abs/1606.03476))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Coaching\n",
    "\n",
    "<p style=\"float: left;\">If the optimal action is difficult to<br>predict, the coach teaches a good one<br>that is easier (<a href=\"https://papers.nips.cc/paper/4545-imitation-learning-by-coaching.pdf\">He et al., 2012</a>)</p> <a href=\"https://commons.wikimedia.org/wiki/File:US_Navy_091206-N-2013O-023_Sam_Givens,_a_player_for_the_Harlem_Ambassadors_basketball_team,_demonstrates_proper_dribbling_techniques_to_a_boy_during_a_basketball_camp_sponsored_by_Yokosuka%27s_Morale,_Welfare_and_Recreation_Youth.jpg\"><img src=\"images/coaching.jpg\" style=\"width:30%; float: right;\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Expert: $\\alpha^{\\star}= \\mathop{\\arg \\min}_{\\alpha \\in {\\cal A}} L(S_t(\\alpha,\\pi^{\\star}),\\mathbf{y})$\n",
    "\n",
    "Coach: $\\alpha^{\\dagger}= \\mathop{\\arg \\min}_{\\alpha \\in {\\cal A}} \\lbrace L(S_t(\\alpha,\\pi^{\\star}),\\mathbf{y}) - \\lambda \\cdot f(\\alpha, \\mathbf{x}, S_t)\\rbrace$\n",
    "\n",
    "i.e. $\\alpha^{\\dagger}=\\mathop{\\arg \\min}_{\\alpha \\in {\\cal A}} \\lbrace loss(\\alpha) - \\lambda \\cdot classifier(\\alpha) \\rbrace$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Changeprop\n",
    "\n",
    "Speed-up action costing in LOLS\n",
    "([Viera and Eisner, 2016](https://timvieira.github.io/doc/2016-tacl-pruning.pdf)):\n",
    "\n",
    "If one action changes, don't assess the cost of the whole trajectory (under assumptions), **prop**agate the **change**!\n",
    "\n",
    "<img src=\"images/changeprop.png\" style=\"width:70%;\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Ranking\n",
    "\n",
    "Jana Rao Doppa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<h3> What about Recurrent Neural Networks?</h3>\n",
    "\n",
    "<img src=\"images/rnn.png\" width=\"60%\"  style=\"background:none;\" />\n",
    "\n",
    "<p>They face similar problems:\n",
    "\t\t\t\t<ul>\n",
    "\t\t\t\t<li>trained at the word rather than sentence level</li>\n",
    "\t\t\t\t<li>assume previous predictions are correct</li>\n",
    "\t\t\t</ul>\n",
    "\t\t\t</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Imitation learning and RNNs\n",
    "\n",
    "<img src=\"images/mixer.png\" width=\"70%\"  style=\"background:none;\" />\n",
    "\n",
    "\n",
    "- DAgger mixed rollins, similar to scheduled sampling ([Bengio et al., 2015](http://arxiv.org/abs/1506.03099))\n",
    "- MIXER  (<a href=\"https://arxiv.org/abs/1511.06732\">Ranzato et al., 2016</a>): Mix REINFORCE-ment learning with imitation: we have the expert policy!\n",
    "- no rollouts, learn a  regressor to estimate action costs\n",
    "- end-to-end back propagation through the sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Actor-critic\n",
    "\n",
    "![](images/actorcritic.png)\n",
    "\n",
    "[Bahdanau et al. (2017)](https://arxiv.org/pdf/1607.07086.pdf):\n",
    "- actor: the RNN we are learning to use during testing\n",
    "- critic: another RNN that is trained to predict the value of the actions of the critic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Summary so far\n",
    "\n",
    "- basic concepts\n",
    "  - loss function decomposability\n",
    "  - expert policy\n",
    "- imitation learning\n",
    "    - rollin/outs\n",
    "    - DAgger algorithm\n",
    "    - DAgger with rollouts and LoLS\n",
    "- connections and interpretations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### After the break\n",
    "\n",
    "- Applications:\n",
    "  - dependency parsing\n",
    "  - natural language generation\n",
    "  - semantic parsing\n",
    "- Practical advice\n",
    "    - making things faster\n",
    "    - debugging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center>\n",
    "\n",
    "<h1>Break!</h1>"
   ]
  }
 ],
 "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
}