{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "  function code_toggle() {\n",
       "    if (code_shown){\n",
       "      $('div.input').hide('500');\n",
       "      $('#toggleButton').val('Show Code')\n",
       "    } else {\n",
       "      $('div.input').show('500');\n",
       "      $('#toggleButton').val('Hide Code')\n",
       "    }\n",
       "    code_shown = !code_shown\n",
       "  }\n",
       "\n",
       "  $( document ).ready(function(){\n",
       "    code_shown=false;\n",
       "    $('div.input').hide()\n",
       "  });\n",
       "</script>\n",
       "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%html\n",
    "<script>\n",
    "  function code_toggle() {\n",
    "    if (code_shown){\n",
    "      $('div.input').hide('500');\n",
    "      $('#toggleButton').val('Show Code')\n",
    "    } else {\n",
    "      $('div.input').show('500');\n",
    "      $('#toggleButton').val('Hide Code')\n",
    "    }\n",
    "    code_shown = !code_shown\n",
    "  }\n",
    "\n",
    "  $( document ).ready(function(){\n",
    "    code_shown=false;\n",
    "    $('div.input').hide()\n",
    "  });\n",
    "</script>\n",
    "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%%capture\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "%matplotlib inline\n",
    "# %cd .. \n",
    "import sys\n",
    "sys.path.append(\"..\")\n",
    "import statnlpbook.util as util\n",
    "\n",
    "util.execute_notebook('structured_prediction.ipynb')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "<!---\n",
    "Latex Macros\n",
    "-->\n",
    "$$\n",
    "\\newcommand{\\Xs}{\\mathcal{X}}\n",
    "\\newcommand{\\Ys}{\\mathcal{Y}}\n",
    "\\newcommand{\\y}{\\mathbf{y}}\n",
    "\\newcommand{\\balpha}{\\boldsymbol{\\alpha}}\n",
    "\\newcommand{\\bbeta}{\\boldsymbol{\\beta}}\n",
    "\\newcommand{\\aligns}{\\mathbf{a}}\n",
    "\\newcommand{\\align}{a}\n",
    "\\newcommand{\\source}{\\mathbf{s}}\n",
    "\\newcommand{\\target}{\\mathbf{t}}\n",
    "\\newcommand{\\ssource}{s}\n",
    "\\newcommand{\\starget}{t}\n",
    "\\newcommand{\\repr}{\\mathbf{f}}\n",
    "\\newcommand{\\repry}{\\mathbf{g}}\n",
    "\\newcommand{\\x}{\\mathbf{x}}\n",
    "\\newcommand{\\prob}{p}\n",
    "\\newcommand{\\bar}{\\,|\\,}\n",
    "\\newcommand{\\vocab}{V}\n",
    "\\newcommand{\\params}{\\boldsymbol{\\theta}}\n",
    "\\newcommand{\\param}{\\theta}\n",
    "\\DeclareMathOperator{\\perplexity}{PP}\n",
    "\\DeclareMathOperator{\\argmax}{argmax}\n",
    "\\DeclareMathOperator{\\argmin}{argmin}\n",
    "\\newcommand{\\train}{\\mathcal{D}}\n",
    "\\newcommand{\\counts}[2]{\\#_{#1}(#2) }\n",
    "\\newcommand{\\length}[1]{\\text{length}(#1) }\n",
    "\\newcommand{\\indi}{\\mathbb{I}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Structured Prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "No emerging unified _theory of NLP_, most textbooks and courses explain NLP as \n",
    "\n",
    "> a collection of problems, techniques, ideas, frameworks, etc. that really are not tied together in any reasonable way other than the fact that they have to do with NLP.\n",
    ">\n",
    ">  -- <cite>[Hal Daume](http://nlpers.blogspot.co.uk/2012/12/teaching-intro-grad-nlp.html)</cite>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "but there is a reoccurring pattern ... the\n",
    "## Structured Prediction Task"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Problem Signature \n",
    "\n",
    "* Given given some input structure \\\\(\\x \\in \\Xs \\\\), such as a token, sentence, or document ...  \n",
    "* predict an **output structure** \\\\(\\y \\in \\Ys \\\\), such as a class label, a sentence or syntactic tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Recipes\n",
    "* *Learn* how to **score** structures, **predict** by search for highest score\n",
    "* *Learn* how to **predict** directly"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Recipe 1: Learn to Score, Implement How to Predict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " * Define a parametrised _model_ \\\\(s_\\params(\\x,\\y)\\\\) that measures the _match_ of a given \\\\(\\x\\\\) and \\\\(\\y\\\\) using _representations_ $\\repr(\\x)$ and $\\repry(\\y)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " * _Learn_ the parameters \\\\(\\params\\\\) from the training data \\\\(\\train\\\\) to minimise a loss (a _continuous optimisation problem_)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " * Given an input \\\\(\\x\\\\) find the highest-scoring output structure $$ \\y^* = \\argmax_{\\y\\in\\Ys} s_\\params(\\x,\\y) $$ (a _discrete optimisation problem_).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Good NLPers** combine **three skills** in accordance with this recipe: \n",
    "\n",
    "* modelling,\n",
    "* continuous optimisation and\n",
    "* discrete optimisation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example\n",
    "* Difficult to show meaningful example without going into depth (as we will do later)\n",
    "* Instead consider toy example that uses same ingredients and steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Task\n",
    "\"Machine translation\" from English into German sentences\n",
    "\n",
    "### Assumptions\n",
    "* There are only 4 target German sentences we care about.\n",
    "* The lengths of the source English and target German sentences are sufficient representations of the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Training and Testing Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table align=\"left\" style=\"font-size:x-large;\"><tr><th>x</th><th>y</th></tr><tr><td style='padding:5px; text-align:left'>I ate an apple</td> <td style='padding:5px; text-align:left'>Ich aß einen Apfel</td><tr><tr><td style='padding:5px; text-align:left'>I ate a red apple</td> <td style='padding:5px; text-align:left'>Ich aß einen roten Apfel</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x7fc0827870f0>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "util.Table(train, column_names=[\"x\",\"y\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table align=\"left\" style=\"font-size:x-large;\"><tr><td style='padding:5px; text-align:left'>Yesterday I ate a red apple</td> <td style='padding:5px; text-align:left'>Gestern aß ich einen roten Apfel</td><tr><tr><td style='padding:5px; text-align:left'>Yesterday I ate a red apply with a friend</td> <td style='padding:5px; text-align:left'>Gestern aß ich einen roten Apfel mit einem Freund</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x7fc082787160>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "util.Table(test)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Our \n",
    "### Output Space\n",
    "is simply:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Ich aß einen Apfel',\n",
       " 'Ich aß einen roten Apfel',\n",
       " 'Gestern aß ich einen roten Apfel',\n",
       " 'Gestern aß ich einen roten Apfel mit einem Freund']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Representation\n",
    "* $\\repr(\\x)=|\\x|$ \n",
    "* $\\repry(\\y)=|\\y|$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Model\n",
    "$$\n",
    "s_\\param(\\x,\\y) = -|\\param \\repr(\\x) - \\repry(\\y)|\n",
    "$$\n",
    "\n",
    "Note: $\\param$ should capture fact that German sentences are a little longer (here!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let us inspect this model: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table align=\"left\" style=\"font-size:x-large;\"><tr><th>Source x</th><th>Target y</th><th>f(x)</th><th>g(y)</th><th>score</th></tr><tr><td style='padding:5px; text-align:left'>I ate an apple</td> <td style='padding:5px; text-align:left'>Ich aß einen Apfel</td> <td style='padding:5px; text-align:left'>14</td> <td style='padding:5px; text-align:left'>18</td> <td style='padding:5px; text-align:left'>-4.00</td><tr><tr><td style='padding:5px; text-align:left'>I ate a red apple</td> <td style='padding:5px; text-align:left'>Ich aß einen roten Apfel</td> <td style='padding:5px; text-align:left'>17</td> <td style='padding:5px; text-align:left'>24</td> <td style='padding:5px; text-align:left'>-7.00</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x7fc0827a04a8>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "util.Table([(x, y, f(x), g(y), s(1.0, x, y)) for x, y in train],\n",
    "           column_names=[\"Source x\",\"Target y\",\"f(x)\",\"g(y)\",\"score\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Does this scoring function help to **discriminate** right from wrong? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table align=\"left\" style=\"font-size:x-large;\"><tr><th>Source x</th><th>Target y</th><th>score</th></tr><tr><td style='padding:5px; text-align:left'>I ate a red apple</td> <td style='padding:5px; text-align:left'>Ich aß einen Apfel</td> <td style='padding:5px; text-align:left'>-4.10</td><tr><tr><td style='padding:5px; text-align:left'>I ate a red apple</td> <td style='padding:5px; text-align:left'>Ich aß einen roten Apfel</td> <td style='padding:5px; text-align:left'>-1.90</td><tr><tr><td style='padding:5px; text-align:left'>I ate a red apple</td> <td style='padding:5px; text-align:left'>Gestern aß ich einen roten Apfel</td> <td style='padding:5px; text-align:left'>-9.90</td><tr><tr><td style='padding:5px; text-align:left'>I ate a red apple</td> <td style='padding:5px; text-align:left'>Gestern aß ich einen roten Apfel mit einem Freund</td> <td style='padding:5px; text-align:left'>-26.90</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x7fc0826307f0>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "util.Table([(train[1][0],y,\"{:.2f}\".format(s(1.3,train[1][0],y))) \n",
    "            for y in y_space],\n",
    "           column_names=[\"Source x\",\"Target y\",\"score\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "How to estimate $\\param$? Let us define a \n",
    "### Loss Function\n",
    "$$\n",
    "l(\\param)=\\sum_{(\\x,\\y) \\in \\train} \\indi(\\y\\neq\\y^*_{\\param}(\\x))\n",
    "$$\n",
    "where \n",
    "* $\\indi(\\mathrm{True})=1$ and $\\indi(\\mathrm{False})=0$ \n",
    "* $\\y^*_{\\param}(\\x) \\in \\Ys$ is highest scoring translation of $\\x$\n",
    "$$\\y^*_{\\param}(\\x)=\\argmax_\\y s_\\param(\\x,\\y).$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A finite approximation of the search space ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "thetas = np.linspace(0.0, 2.0, num=50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fc0826d5320>]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAl0AAAFpCAYAAACmgZ0NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X+MXGe93/HPd2dn4hnjzBTsBLCz12nr9ja0hBttHRSi\nkugK5KSXukiosoVAoiALLrm6t62Q0vtHkHr/RKoqRMCyqG+ECkkrQbhR6ySAetXcJgrEobn5RYKM\nyW3spg1JOGPHM/ac3f32jzmznqx3Pcf27Dlnn+f9klbeOec5O8/j8cl+8jzPeR5zdwEAAGB9zZRd\nAQAAgBgQugAAAApA6AIAACgAoQsAAKAAhC4AAIACELoAAAAKQOgCAAAoAKELAACgAIQuAACAAhC6\nAAAACjBbdgVWs3XrVt+5c2fZ1QAAAJjo6aeffsPdt00qV8nQtXPnTh09erTsagAAAExkZn+TpxzD\niwAAAAUgdAEAABSA0AUAAFAAQhcAAEABCF0AAAAFIHQBAAAUgNAFAABQAEIXAABAAQhdAAAABZgY\nuszsOjP7SzN70cxeMLM/XqWMmdnXzeyYmT1rZjeNndtjZi9n5+6edgMAAAA2gjw9XQuS/o273yDp\nw5K+bGY3rChzh6Rd2dcBSd+SJDOrSbo3O3+DpP2rXAsAABC8iXsvuvtrkl7Lvj9tZr+QtF3Si2PF\n9kr6jru7pCfNrGNm75O0U9Ixdz8uSWb2QFZ2/FoAACBpYXFJP/v1Wzq3uFR2VYIwY6aP/r2J+1AX\n5pI2vDaznZJ+T9JPV5zaLunVsdcnsmOrHb95jZ99QMNeMs3NzV1KtQAACMKPXvx/+sPv/rzsagRj\nU31GL/3ZHWVXY1nu0GVm75L0fUl/4u6npl0Rdz8k6ZAkzc/P+7R/PgAAVfd/u2clSf/p8zdr81W1\nkmuz8c2YlV2Fd8gVusysrmHg+q67/2CVIiclXTf2ekd2rL7GcQAAsELST2Um3fJ33qOZmWoFBly5\nPE8vmqT/KOkX7v7v1yj2kKTPZk8xflhSN5sL9pSkXWZ2vZk1JO3LygIAgBW6vYGu3lQncAUqT0/X\nRyR9RtJzZvZMduxPJc1JkrsflHRE0p2SjknqSfpcdm7BzO6S9KikmqTD7v7CVFsAAEAgkn6qTqte\ndjWwTvI8vfg/JV00cmdPLX55jXNHNAxlAADgIrr9VJ0moStUrEgPAEBFJL1U7Vaj7GpgnRC6AACo\nCHq6wkboAgCgIpLegDldASN0AQBQAUtLTk9X4AhdAABUwOlzC1py6WpCV7AIXQAAVEC3l0qSOkyk\nDxahCwCACkj6A0lieDFghC4AACogWe7pInSFitAFAEAFdPuErtARugAAqIAkC13tJnO6QkXoAgCg\nArq94ZyuNnO6gkXoAgCgApJeqs2Nmhqz/GoOFZ8sAAAVkPRTerkCR+gCAKAC2Ow6fIQuAAAqoNsf\nsEZX4AhdAABUQNJLWS4icIQuAAAqoNsndIWO0AUAQMncPZtIz5yukBG6AAAo2dl0SYOFJXq6Akfo\nAgCgZGx2HQdCFwAAJRttds06XWEjdAEAULLl0MXwYtAIXQAAlKy7PLzIRPqQEboAACjZqKeLifRh\nI3QBAFCybp/QFQNCFwAAJUv6qRq1GTXrtbKrgnVE6AIAoGTDza7rMrOyq4J1ROgCAKBkbHYdh9lJ\nBczssKQ/kPS6u//DVc5/RdKnx37eP5C0zd3fMrNXJJ2WtChpwd3np1VxAABCkfRS1uiKQJ6ervsk\n7VnrpLt/zd0/5O4fkvRvJf0Pd39rrMjt2XkCFwAAq0h6bHYdg4mhy90fk/TWpHKZ/ZLuv6IaAQAQ\nmS6bXUdhanO6zKylYY/Y98cOu6SfmNnTZnZgWu8FAEBIkt6Anq4ITJzTdQk+IenxFUOLt7r7STO7\nRtKPzeylrOfsAlkoOyBJc3NzU6wWAADVlS4u6cxgkYn0EZjm04v7tGJo0d1PZn++LulBSbvXutjd\nD7n7vLvPb9u2bYrVAgCgulgYNR5TCV1m1pb0UUl/MXZss5ltGX0v6eOSnp/G+wEAEIrzm10zpyt0\neZaMuF/SbZK2mtkJSV+VVJckdz+YFfukpB+5+5mxS6+V9GC20NuspO+5+yPTqzoAABvf+c2u6ekK\n3cTQ5e77c5S5T8OlJcaPHZd04+VWDACAGLDZdTxYkR4AgBItDy/S0xU8QhcAACVKRhPpWacreIQu\nAABK1O0NZCZt2TTNVZxQRYQuAABKNFyNvq6ZGSu7KlhnhC4AAEqU9FOeXIwEoQsAgBIlvZQ1uiJB\n6AIAoET0dMWD0AUAQIm6bHYdDUIXAAAlSrKJ9AgfoQsAgJIsLbm6DC9Gg9AFAEBJTp9dkDubXceC\n0AUAQEkSNruOCqELAICSdPtsdh0TQhcAACUZbXZN6IoDoQsAgJKMNrtus9l1FAhdAACUpNvL5nTR\n0xUFQhcAACUZDS+yTlccCF0AAJQk6afa3KipXuPXcQz4lAEAKEnSS9Vhja5oELoAAChJtz9gaDEi\nhC4AAErS7adMoo8IoQsAgJIMhxcJXbEgdAEAUJKkn7JGV0QIXQAAlMDd1aWnKyqELgAAStBPFzVY\nXGIifUQIXQAAlGB530VCVzQIXQAAlIDNruND6AIAoARJf7jvIhPp4zExdJnZYTN73cyeX+P8bWbW\nNbNnsq97xs7tMbOXzeyYmd09zYoDALCRnerT0xWbPD1d90naM6HMX7n7h7KvfydJZlaTdK+kOyTd\nIGm/md1wJZUFACAUDC/GZ2LocvfHJL11GT97t6Rj7n7c3QeSHpC09zJ+DgAAwUlGPV0ML0ZjWnO6\nbjGzZ83sYTP7QHZsu6RXx8qcyI4BABC9pJeqMTujTXWmV8didgo/4+eS5tz9bTO7U9IPJe261B9i\nZgckHZCkubm5KVQLAIDqGm12bWZlVwUFueJ47e6n3P3t7PsjkupmtlXSSUnXjRXdkR1b6+cccvd5\nd5/ftm3blVYLAIBKS3opa3RF5opDl5m917KYbma7s5/5pqSnJO0ys+vNrCFpn6SHrvT9AAAIAZtd\nx2fi8KKZ3S/pNklbzeyEpK9KqkuSux+U9ClJXzKzBUl9Sfvc3SUtmNldkh6VVJN02N1fWJdWAACw\nwST9VNs7zbKrgQJNDF3uvn/C+W9I+sYa545IOnJ5VQMAIFyn+qk+8P6ry64GCsQjEwAAlCDpDZjT\nFRlCFwAABRssLOnMYJE5XZEhdAEAULButjBqu8XCqDEhdAEAULButtk1w4txIXQBAFCw0b6LbUJX\nVAhdAAAUjM2u40ToAgCgYGx2HSdCFwAABTs/kZ6erpgQugAAKFi3N9CMSVuumrhGOQJC6AIAoGBJ\nP1W7WdfMjJVdFRSI0AUAQMGGm10znys2hC4AAAo26ulCXAhdAAAUrNsbELoiROgCAKBgST9lja4I\nEboAAChY0kvZAihChC4AAAq0tOQ6dTZls+sIEboAACjQ6bMLcmez6xgRugAAKFDSH0hi38UYEboA\nACgQm13Hi9AFAECBRptdt9nsOjqELgAACpT0hsOLrNMVH0IXAAAF6vYZXowVoQsAgAKN5nTR0xUf\nQhcAAAVKeqneddWs6jV+BceGTxwAgAJ12ew6WoQuAAAK1O0PmM8VKUIXAAAFSnpsdh0rQhcAAAVK\n+qk6rNEVpYmhy8wOm9nrZvb8Guc/bWbPmtlzZvaEmd04du6V7PgzZnZ0mhUHAGAjSnqprmZOV5Ty\n9HTdJ2nPRc7/WtJH3f0fSfozSYdWnL/d3T/k7vOXV0UAAMLg7szpitjspALu/piZ7bzI+SfGXj4p\naceVVwsAgPD0BotKF10derqiNO05XZ+X9PDYa5f0EzN72swOTPm9AADYUBJWo4/axJ6uvMzsdg1D\n161jh29195Nmdo2kH5vZS+7+2BrXH5B0QJLm5uamVS0AACqj22Oz65hNpafLzD4o6duS9rr7m6Pj\n7n4y+/N1SQ9K2r3Wz3D3Q+4+7+7z27Ztm0a1AAColKQ/3Oyanq44XXHoMrM5ST+Q9Bl3/+XY8c1m\ntmX0vaSPS1r1CUgAAGIw6ukidMVp4vCimd0v6TZJW83shKSvSqpLkrsflHSPpPdI+qaZSdJC9qTi\ntZIezI7NSvqeuz+yDm0AAGBDWJ7TxfBilPI8vbh/wvkvSPrCKsePS7rxwisAAIhTsjyni56uGLEi\nPQAABUn6AzVmZ7Spzq/fGPGpAwBQkG4vVadZVzb1BpEhdAEAUBA2u44boQsAgIJ02ew6aoQuAAAK\nkvRTtenpihahCwCAgnR7A/ZdjBihCwCAgiR95nTFjNAFAEABzi0sqjdYZI2uiBG6AAAoQDdbjb7d\nYiJ9rAhdAAAUYHnfRXq6okXoAgCgAMv7LjKnK1qELgAACnC+p4vhxVgRugAAKAA9XSB0AQBQgKQ3\nkCQWR40YoQsAgAJ0+6lqM6YtV82WXRWUhNAFAEABkl6qdrMuMyu7KigJoQsAgAIk/ZSFUSNH6AIA\noABJb0DoihyhCwCAAnTZdzF6hC4AAAqQ9FJWo48coQsAgAIMe7pYGDVmhC4AANbZ4pLr1Fkm0seO\n0AUAwDo7fTaVO6vRx47QBQDAOkt6bAEEQhcAAOtutO8iw4txI3QBALDOlvddbDKRPmaELgAA1lm3\nz/AiCF0AAKy75TldDC9GbWLoMrPDZva6mT2/xnkzs6+b2TEze9bMbho7t8fMXs7O3T3NigMAsFF0\nmdMF5evpuk/Snoucv0PSruzrgKRvSZKZ1STdm52/QdJ+M7vhSioLAMBGlPRSbblqVrM1BphiNjup\ngLs/ZmY7L1Jkr6TvuLtLetLMOmb2Pkk7JR1z9+OSZGYPZGVfvNJKX6lzC4tyL7sWADBdtRlTnV/q\na3J3nVtYKuW93zpzTm3mc0VvYujKYbukV8den8iOrXb85im83xX75/c+oV+8dqrsagDAVDVmZ/Tf\n/uhW7bp2S9lVqaR//V/+Wg/+r5Olvf8Hd7RLe29UwzRC11SY2QENhyc1Nze3ru/1uVt26o0z59b1\nPQCgSL85fU5//vgr+tVvzhC61vDi/zml333vFv2zD72/lPe/+fp3l/K+qI5phK6Tkq4be70jO1Zf\n4/iq3P2QpEOSND8/v66Df//iH183uRAAbCAnk77+/PFX1O0Pyq5KZSX9gW7/+9foD2/7u2VXBZGa\nxuD/Q5I+mz3F+GFJXXd/TdJTknaZ2fVm1pC0LysLAJiy0VIEo6UJcKGklzKvCqWa2NNlZvdLuk3S\nVjM7IemrGvZiyd0PSjoi6U5JxyT1JH0uO7dgZndJelRSTdJhd39hHdoAANFrNWqq12x5uxm809l0\nUecWltRhRXiUKM/Ti/snnHdJX17j3BENQxkAYB2ZmdrNBj1daxj9vbBOFsrEs8UAEIh2c5Y5XWtI\nsr8XtuFBmQhdABCITouerrWwDQ+qgNAFAIHoNOuErjUsDy/S04USEboAIBDtVn15jz+806ns76XT\nYiI9ykPoAoBAdJoNQtcalud0MbyIEhG6ACAQnVZdb59bULpYzv6CVZb0UtVrplajVnZVEDFCFwAE\nYvRkHr1dF0r6qdrNhsys7KogYoQuAAhEm1Xp19TtpWo3K7PdMCJF6AKAQIxCF2t1XSjpD5hEj9IR\nugAgEKNQQU/XhZJeyiR6lI7QBQCBYNPrtbHZNaqA0AUAgWAi/dpO9VM2u0bpCF0AEIgtm+oyGz6p\nh/PSxSWdPrfAvosoHaELAAJRmzFdvamubo+J9OPOr0ZP6EK5CF0AEJBOq05P1wqjv482E+lRMkIX\nAASETa8vtLzZNaELJSN0AUBArm7S07XSaN0y1ulC2QhdABCQTqvBnK4VRj1drNOFshG6ACAgHXq6\nLrAcuphIj5IRugAgIJ1WXd1+qqUlL7sqlZH0U5kNl9QAykToAoCAtJt1uUunzy2UXZXKONVPdfWm\numozVnZVEDlCFwAEZDRZvMsTjMuS3oChRVQCoQsAArK8/2KfyfQjSZ/NrlENhC4ACMioR4e1us5L\neqmuJnShAghdABCQ9nJPF6FrpNtPWaMLlUDoAoCAtLOeLtbqOi/pDRheRCUQugAgIMs9XQwvSpKW\nljzr6SJ0oXyELgAIyFWzNbUaNYYXM6fPLWjJ2XcR1ZArdJnZHjN72cyOmdndq5z/ipk9k309b2aL\nZvbu7NwrZvZcdu7otBsAAHinTnO4QCqGa3RJ7LuIapidVMDMapLulfQxSSckPWVmD7n7i6My7v41\nSV/Lyn9C0r9y97fGfszt7v7GVGsOAFhVu9VgeDHDvouokjw9XbslHXP34+4+kPSApL0XKb9f0v3T\nqBwA4NINe7qYSC+dX6+szZwuVECe0LVd0qtjr09kxy5gZi1JeyR9f+ywS/qJmT1tZgcut6IAgHw6\nrTo9XRl6ulAlE4cXL9EnJD2+YmjxVnc/aWbXSPqxmb3k7o+tvDALZAckaW5ubsrVAoB4tJt1JtJn\nRn8P9HShCvL0dJ2UdN3Y6x3ZsdXs04qhRXc/mf35uqQHNRyuvIC7H3L3eXef37ZtW45qAQBW027V\n1e2lcveyq1K60XplPL2IKsgTup6StMvMrjezhobB6qGVhcysLemjkv5i7NhmM9sy+l7SxyU9P42K\nAwBW12k2NFhcUj9dLLsqpUt6qVqNmq6arZVdFWDy8KK7L5jZXZIelVSTdNjdXzCzL2bnD2ZFPynp\nR+5+ZuzyayU9aGaj9/qeuz8yzQYAAN5pfP/FVmPas0g2Fja7RpXkuhvd/YikIyuOHVzx+j5J9604\ndlzSjVdUQwDAJRmFjG4/1fs7zZJrU65uP1WbNbpQEaxIDwCBabfYCmik26OnC9VB6AKAwHSaw54d\n1uoartPFJHpUBaELAALToadrWdJjs2tUB6ELAAIz6tmJfa0ud1fST1mjC5VB6AKAwLQaNdVrFn1P\n19l0SYOFpeXhVqBshC4ACIyZqd1sRD+na7TvIsOLqApCFwAEiP0X2XcR1UPoAoAAdZp1dSOf09Vl\n30VUDKELAAJET9d4TxdzulANhC4ACNBwTlfcoWs0p42eLlQFoQsAAjTs6Yp8Ij1zulAxhC4ACFCn\nWdeZwaIGC0tlV6U0ST9VvWZqNWplVwWQROgCgCCNhtRiHmJMeqnazYbMrOyqAJIIXQAQpNGq9DGv\n1dXtD1ijC5VC6AKAAHVawyf2Yn6CMemlzOdCpRC6ACBAnSbDi90+m12jWghdABCgUdiIvaerzRpd\nqBBCFwAEaLQgaBJ5T1eb4UVUCKELAAK0ZdOszKRupGt1pYtLevvcAsOLqBRCFwAEaGbG1G7Wo+3p\nGs1lI3ShSghdABCodjPe/RdH7WZ4EVVC6AKAQHWi7ukaDquOls4AqoDQBQCBarca0c7pYt9FVBGh\nCwACFXNP13LoYk4XKoTQBQCB6rTq0S6OOmo3c7pQJYQuAAhUpzkMXUtLXnZVCpf0U5lJWzYRulAd\nhC4ACFS71ZC7dPrsQtlVKVy3N9DVm+qqzVjZVQGWEboAIFCjSeRJP77J9An7LqKCcoUuM9tjZi+b\n2TEzu3uV87eZWdfMnsm+7sl7LQBgfYzmM8W4VlfSS3lyEZUzO6mAmdUk3SvpY5JOSHrKzB5y9xdX\nFP0rd/+Dy7wWADBly5teRziZPumnarNGFyomT0/XbknH3P24uw8kPSBpb86ffyXXAgCuwHLoinCt\nrm5vQE8XKidP6Nou6dWx1yeyYyvdYmbPmtnDZvaBS7wWADBl7eawpyfGZSOY04Uqmji8mNPPJc25\n+9tmdqekH0radSk/wMwOSDogSXNzc1OqFgDEazSnqxvZnK6lJdepfsoaXaicPD1dJyVdN/Z6R3Zs\nmbufcve3s++PSKqb2dY81479jEPuPu/u89u2bbuEJgAAVtOYndHmRi26OV2nzy1oyVkYFdWTJ3Q9\nJWmXmV1vZg1J+yQ9NF7AzN5rZpZ9vzv7uW/muRYAsH46rUZ0Ty92l7cAYiI9qmXi8KK7L5jZXZIe\nlVSTdNjdXzCzL2bnD0r6lKQvmdmCpL6kfe7ukla9dp3aAgBYod2sqxvZOl2jdcmYSI+qyTWnKxsy\nPLLi2MGx778h6Rt5rwUAFKPdrEfX08Vm16gqVqQHgIB1WvXo5nSN2kvoQtUQugAgYJ1WfD1d3Wxd\nstGSGUBVELoAIGDtZkPd/kDDabZxGIVMnl5E1RC6ACBgnVZd6aKrny6WXZXCdPupWo2aGrP8ikO1\n8C8SAALWiXDT66TPZteoJkIXAATs/P6LEYWuHptdo5oIXQAQsNFk8iSitbq6fTa7RjURugAgYDHu\nv5j02Owa1UToAoCALQ8vRrRWV9IndKGaCF0AELDY5nS5u7q9lDW6UEmELgAIWLNeU6M2E82crn66\nqMHiEj1dqCRCFwAEzMzUbtV1KpLhxW6fhVFRXYQuAAhcJ6JNr5c3uyZ0oYIIXQAQuJj2X1zeAojh\nRVQQoQsAAtduNqJ5erGbzV3rMJEeFUToAoDAtZt1dXtxTKRfHl6kpwsVROgCgMB1WvVoerpG7SR0\noYoIXQAQuE6zrt5gUecWFsuuyrpLeqkatRk167WyqwJcgNAFAIEb9fp0I+jt6vYHurpZl5mVXRXg\nAoQuAAhcuzWcVB7DWl1dtgBChRG6ACBwozWrYlg2IumlrNGFyiJ0AUDgYtp/MenR04XqInQBQOBG\na1bF8ARjt89m16guQhcABK693NMV/lpdSW9ATxcqi9AFAIHbctWszMJ/enGwsKQzg0XmdKGyCF0A\nELiZGVM7gk2vuyyMioojdAFABDrN8FelH+27eDU9XagoQhcARKDdagQ/p+v8votMpEc15QpdZrbH\nzF42s2Nmdvcq5z9tZs+a2XNm9oSZ3Th27pXs+DNmdnSalQcA5NNp1oNfHHV5eJGeLlTU7KQCZlaT\ndK+kj0k6IekpM3vI3V8cK/ZrSR9199+a2R2SDkm6eez87e7+xhTrDQC4BJ1WXa+8eabsaqyr8z1d\nhC5UU56ert2Sjrn7cXcfSHpA0t7xAu7+hLv/Nnv5pKQd060mAOBKdCKYSJ8s93QxvIhqyhO6tkt6\ndez1iezYWj4v6eGx1y7pJ2b2tJkduPQqAgCuVLvV0KmzqRaXvOyqrJtubyAzacumiYM4QCmm+i/T\nzG7XMHTdOnb4Vnc/aWbXSPqxmb3k7o+tcu0BSQckaW5ubprVAoDotZt1uUunz6bBTjRP+qnazbpm\nZqzsqgCrytPTdVLSdWOvd2TH3sHMPijp25L2uvubo+PufjL783VJD2o4XHkBdz/k7vPuPr9t27b8\nLQAATBTDptdsdo2qyxO6npK0y8yuN7OGpH2SHhovYGZzkn4g6TPu/sux45vNbMvoe0kfl/T8tCoP\nAMhnedPrgJ9gHPV0AVU1cXjR3RfM7C5Jj0qqSTrs7i+Y2Rez8wcl3SPpPZK+aWaStODu85KulfRg\ndmxW0vfc/ZF1aQkAYE2dCPZf7PYGagc6dIow5JrT5e5HJB1Zcezg2PdfkPSFVa47LunGlccBAMVq\nZ0/0hbz/Yref6nfes7nsagBrYkV6AIjAqKcr5NCV9FPW6EKlEboAIALtwCfSLy25un0m0qPaCF0A\nEIF6bUbvumo22NB1+uyC3MWcLlQaoQsAItFu1pX0w5xIP2oXPV2oMkIXAESi3ayrG2hP16gHjyUj\nUGWELgCIRKdVD3adruV9F5lIjwojdAFAJDqterDrdI3aRehClRG6ACAS7WZD3f5C2dVYF6f6o+FF\nJtKjughdABCJTquubn8gdy+7KlPHnC5sBIQuAIhEp1lXuujqDRbLrsrUJf1Umxs1NWb5tYbq4l8n\nAEQi5E2vk16qDmt0oeIIXQAQifOr0oc3mb7bHzC0iMojdAFAJJY3vQ5wra6klxK6UHmELgCIRNDD\ni2x2jQ2A0AUAkVgOXYH2dBG6UHWELgCIRGc0vBhYT5e761Q/ZY0uVB6hCwAisak+o8bsTHCbXvfT\nRQ0Wl+jpQuURugAgEmamToCbXo+GSztMpEfFEboAICLD/RcDDV30dKHiCF0AEJF2sx7c8OKoPczp\nQtURugAgIu1mI7ieri77LmKDIHQBQESGm16HFbpG644xvIiqI3QBQEQ6TeZ0AWUhdAFARDqtuvrp\nos4tLJZdlanp9lM1ajNq1mtlVwW4KEIXAESk3QpvgdRuf6B2qy4zK7sqwEURugAgIqO1rEJaqyvp\npazRhQ2B0AUAEQlx02v2XcRGQegCgIiM9l8MaTJ9wr6L2CByhS4z22NmL5vZMTO7e5XzZmZfz84/\na2Y35b0WAFCc0VpWSS+cBVK7vQFrdGFDmBi6zKwm6V5Jd0i6QdJ+M7thRbE7JO3Kvg5I+tYlXAsA\nKEg7G4YLaSJ90md4ERtDnp6u3ZKOuftxdx9IekDS3hVl9kr6jg89KaljZu/LeS0AoCBbrprVjIUz\nvHhuYVG9wSIT6bEhzOYos13Sq2OvT0i6OUeZ7TmvBQAUZGbG1G7W9Z+PvqrHf/VG2dW5YotLLomF\nUbEx5AldhTCzAxoOTWpubq7k2gBAuP7lR67Xz155q+xqTM3v/+41unXXtrKrAUyUJ3SdlHTd2Osd\n2bE8Zeo5rpUkufshSYckaX5+3nPUCwBwGf7o93eVXQUgSnnmdD0laZeZXW9mDUn7JD20osxDkj6b\nPcX4YUldd38t57UAAADBm9jT5e4LZnaXpEcl1SQddvcXzOyL2fmDko5IulPSMUk9SZ+72LXr0hIA\nAIAKM/fqjeTNz8/70aNHy64GAADARGb2tLvPTyrHivQAAAAFIHQBAAAUgNAFAABQAEIXAABAAQhd\nAAAABSB0AQAAFIDQBQAAUABCFwAAQAEIXQAAAAUgdAEAABSgktsAmdlvJP3NOr/NVklvrPN7VFXM\nbZfibn/MbZfibj9tj1fM7S+q7b/j7tsmFapk6CqCmR3Ns09SiGJuuxR3+2NuuxR3+2l7nG2X4m5/\n1drO8CIAAEABCF0AAAAFiDl0HSq7AiWKue1S3O2Pue1S3O2n7fGKuf2Vanu0c7oAAACKFHNPFwAA\nQGGCC11wkE3vAAAD/ElEQVRmtsfMXjazY2Z29yrnzcy+np1/1sxuynvtRpCj/Z/O2v2cmT1hZjeO\nnXslO/6MmR0ttuZXLkfbbzOzbta+Z8zsnrzXbgQ52v+VsbY/b2aLZvbu7NxG/+wPm9nrZvb8GueD\nve9ztD3ke35S20O/5ye1P+R7/joz+0sze9HMXjCzP16lTPXue3cP5ktSTdKvJP1tSQ1Jfy3phhVl\n7pT0sCST9GFJP817bdW/crb/Fkl/K/v+jlH7s9evSNpadjvWse23Sfqvl3Nt1b8utQ2SPiHpv4fw\n2Wf1/yeSbpL0/BrnQ77vJ7U9yHs+Z9uDvefztH9F2dDu+fdJuin7foukX26E3/eh9XTtlnTM3Y+7\n+0DSA5L2riizV9J3fOhJSR0ze1/Oa6tuYhvc/Ql3/2328klJOwqu43q5ks8vis9+hf2S7i+kZgVw\n98ckvXWRIsHe95PaHvA9n+dzX8uG/9ylS25/aPf8a+7+8+z705J+IWn7imKVu+9DC13bJb069vqE\nLvwQ1iqT59qqu9Q2fF7D/wsYcUk/MbOnzezAOtRvPeVt+y1ZN/PDZvaBS7y2ynK3wcxakvZI+v7Y\n4Y382ecR8n1/KUK65/MK9Z7PLfR73sx2Svo9ST9dcapy9/1sEW+C6jGz2zX8D/CtY4dvdfeTZnaN\npB+b2UvZ/0mF4ueS5tz9bTO7U9IPJe0quU5l+ISkx919/P+QQ//so8c9zz0f4j1vZu/SMEz+ibuf\nKrs+k4TW03VS0nVjr3dkx/KUyXNt1eVqg5l9UNK3Je119zdHx939ZPbn65Ie1LALdqOY2HZ3P+Xu\nb2ffH5FUN7Otea7dAC6lDfu0Yphhg3/2eYR8308U6D0/UeD3/KUI8p43s7qGgeu77v6DVYpU774v\nYuJYUV8a9twdl3S9zk+O+8CKMv9U75xY97O811b9K2f75yQdk3TLiuObJW0Z+/4JSXvKbtOU2/5e\nnV+bbrek/539O4jis8/KtTWcA7I5lM9+rB07tfaE6mDv+xxtD/Kez9n2YO/5PO3Pzgd5z2ef43ck\n/YeLlKncfR/U8KK7L5jZXZIe1fDphMPu/oKZfTE7f1DSEQ2faDgmqSfpcxe7toRmXLac7b9H0nsk\nfdPMJGnBh5uBXivpwezYrKTvufsjJTTjsuRs+6ckfcnMFiT1Je3z4R0Yy2cvSZ+U9CN3PzN2+Yb+\n7CXJzO7X8Em1rWZ2QtJXJdWl8O/7HG0P8p6XcrU92HteytV+KdB7XtJHJH1G0nNm9kx27E81/J+M\nyt73rEgPAABQgNDmdAEAAFQSoQsAAKAAhC4AAIACELoAAAAKQOgCAAAoAKELAACgAIQuAACAAhC6\nAAAACvD/Ae28krdbAApEAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fc08274c208>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(thetas, [loss(theta,train) for theta in thetas])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7fc0826d5320>]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAl0AAAFpCAYAAACmgZ0NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X+MXGe93/HPd2dn4hnjzBTsBLCz12nr9ja0hBttHRSi\nkugK5KSXukiosoVAoiALLrm6t62Q0vtHkHr/RKoqRMCyqG+ECkkrQbhR6ySAetXcJgrEobn5RYKM\nyW3spg1JOGPHM/ac3f32jzmznqx3Pcf27Dlnn+f9klbeOec5O8/j8cl+8jzPeR5zdwEAAGB9zZRd\nAQAAgBgQugAAAApA6AIAACgAoQsAAKAAhC4AAIACELoAAAAKQOgCAAAoAKELAACgAIQuAACAAhC6\nAAAACjBbdgVWs3XrVt+5c2fZ1QAAAJjo6aeffsPdt00qV8nQtXPnTh09erTsagAAAExkZn+TpxzD\niwAAAAUgdAEAABSA0AUAAFAAQhcAAEABCF0AAAAFIHQBAAAUgNAFAABQAEIXAABAAQhdAAAABZgY\nuszsOjP7SzN70cxeMLM/XqWMmdnXzeyYmT1rZjeNndtjZi9n5+6edgMAAAA2gjw9XQuS/o273yDp\nw5K+bGY3rChzh6Rd2dcBSd+SJDOrSbo3O3+DpP2rXAsAABC8iXsvuvtrkl7Lvj9tZr+QtF3Si2PF\n9kr6jru7pCfNrGNm75O0U9Ixdz8uSWb2QFZ2/FoAACBpYXFJP/v1Wzq3uFR2VYIwY6aP/r2J+1AX\n5pI2vDaznZJ+T9JPV5zaLunVsdcnsmOrHb95jZ99QMNeMs3NzV1KtQAACMKPXvx/+sPv/rzsagRj\nU31GL/3ZHWVXY1nu0GVm75L0fUl/4u6npl0Rdz8k6ZAkzc/P+7R/PgAAVfd/u2clSf/p8zdr81W1\nkmuz8c2YlV2Fd8gVusysrmHg+q67/2CVIiclXTf2ekd2rL7GcQAAsELST2Um3fJ33qOZmWoFBly5\nPE8vmqT/KOkX7v7v1yj2kKTPZk8xflhSN5sL9pSkXWZ2vZk1JO3LygIAgBW6vYGu3lQncAUqT0/X\nRyR9RtJzZvZMduxPJc1JkrsflHRE0p2SjknqSfpcdm7BzO6S9KikmqTD7v7CVFsAAEAgkn6qTqte\ndjWwTvI8vfg/JV00cmdPLX55jXNHNAxlAADgIrr9VJ0moStUrEgPAEBFJL1U7Vaj7GpgnRC6AACo\nCHq6wkboAgCgIpLegDldASN0AQBQAUtLTk9X4AhdAABUwOlzC1py6WpCV7AIXQAAVEC3l0qSOkyk\nDxahCwCACkj6A0lieDFghC4AACogWe7pInSFitAFAEAFdPuErtARugAAqIAkC13tJnO6QkXoAgCg\nArq94ZyuNnO6gkXoAgCgApJeqs2Nmhqz/GoOFZ8sAAAVkPRTerkCR+gCAKAC2Ow6fIQuAAAqoNsf\nsEZX4AhdAABUQNJLWS4icIQuAAAqoNsndIWO0AUAQMncPZtIz5yukBG6AAAo2dl0SYOFJXq6Akfo\nAgCgZGx2HQdCFwAAJRttds06XWEjdAEAULLl0MXwYtAIXQAAlKy7PLzIRPqQEboAACjZqKeLifRh\nI3QBAFCybp/QFQNCFwAAJUv6qRq1GTXrtbKrgnVE6AIAoGTDza7rMrOyq4J1ROgCAKBkbHYdh9lJ\nBczssKQ/kPS6u//DVc5/RdKnx37eP5C0zd3fMrNXJJ2WtChpwd3np1VxAABCkfRS1uiKQJ6ervsk\n7VnrpLt/zd0/5O4fkvRvJf0Pd39rrMjt2XkCFwAAq0h6bHYdg4mhy90fk/TWpHKZ/ZLuv6IaAQAQ\nmS6bXUdhanO6zKylYY/Y98cOu6SfmNnTZnZgWu8FAEBIkt6Anq4ITJzTdQk+IenxFUOLt7r7STO7\nRtKPzeylrOfsAlkoOyBJc3NzU6wWAADVlS4u6cxgkYn0EZjm04v7tGJo0d1PZn++LulBSbvXutjd\nD7n7vLvPb9u2bYrVAgCgulgYNR5TCV1m1pb0UUl/MXZss5ltGX0v6eOSnp/G+wEAEIrzm10zpyt0\neZaMuF/SbZK2mtkJSV+VVJckdz+YFfukpB+5+5mxS6+V9GC20NuspO+5+yPTqzoAABvf+c2u6ekK\n3cTQ5e77c5S5T8OlJcaPHZd04+VWDACAGLDZdTxYkR4AgBItDy/S0xU8QhcAACVKRhPpWacreIQu\nAABK1O0NZCZt2TTNVZxQRYQuAABKNFyNvq6ZGSu7KlhnhC4AAEqU9FOeXIwEoQsAgBIlvZQ1uiJB\n6AIAoET0dMWD0AUAQIm6bHYdDUIXAAAlSrKJ9AgfoQsAgJIsLbm6DC9Gg9AFAEBJTp9dkDubXceC\n0AUAQEkSNruOCqELAICSdPtsdh0TQhcAACUZbXZN6IoDoQsAgJKMNrtus9l1FAhdAACUpNvL5nTR\n0xUFQhcAACUZDS+yTlccCF0AAJQk6afa3KipXuPXcQz4lAEAKEnSS9Vhja5oELoAAChJtz9gaDEi\nhC4AAErS7adMoo8IoQsAgJIMhxcJXbEgdAEAUJKkn7JGV0QIXQAAlMDd1aWnKyqELgAAStBPFzVY\nXGIifUQIXQAAlGB530VCVzQIXQAAlIDNruND6AIAoARJf7jvIhPp4zExdJnZYTN73cyeX+P8bWbW\nNbNnsq97xs7tMbOXzeyYmd09zYoDALCRnerT0xWbPD1d90naM6HMX7n7h7KvfydJZlaTdK+kOyTd\nIGm/md1wJZUFACAUDC/GZ2LocvfHJL11GT97t6Rj7n7c3QeSHpC09zJ+DgAAwUlGPV0ML0ZjWnO6\nbjGzZ83sYTP7QHZsu6RXx8qcyI4BABC9pJeqMTujTXWmV8didgo/4+eS5tz9bTO7U9IPJe261B9i\nZgckHZCkubm5KVQLAIDqGm12bWZlVwUFueJ47e6n3P3t7PsjkupmtlXSSUnXjRXdkR1b6+cccvd5\nd5/ftm3blVYLAIBKS3opa3RF5opDl5m917KYbma7s5/5pqSnJO0ys+vNrCFpn6SHrvT9AAAIAZtd\nx2fi8KKZ3S/pNklbzeyEpK9KqkuSux+U9ClJXzKzBUl9Sfvc3SUtmNldkh6VVJN02N1fWJdWAACw\nwST9VNs7zbKrgQJNDF3uvn/C+W9I+sYa545IOnJ5VQMAIFyn+qk+8P6ry64GCsQjEwAAlCDpDZjT\nFRlCFwAABRssLOnMYJE5XZEhdAEAULButjBqu8XCqDEhdAEAULButtk1w4txIXQBAFCw0b6LbUJX\nVAhdAAAUjM2u40ToAgCgYGx2HSdCFwAABTs/kZ6erpgQugAAKFi3N9CMSVuumrhGOQJC6AIAoGBJ\nP1W7WdfMjJVdFRSI0AUAQMGGm10znys2hC4AAAo26ulCXAhdAAAUrNsbELoiROgCAKBgST9lja4I\nEboAAChY0kvZAihChC4AAAq0tOQ6dTZls+sIEboAACjQ6bMLcmez6xgRugAAKFDSH0hi38UYEboA\nACgQm13Hi9AFAECBRptdt9nsOjqELgAACpT0hsOLrNMVH0IXAAAF6vYZXowVoQsAgAKN5nTR0xUf\nQhcAAAVKeqneddWs6jV+BceGTxwAgAJ12ew6WoQuAAAK1O0PmM8VKUIXAAAFSnpsdh0rQhcAAAVK\n+qk6rNEVpYmhy8wOm9nrZvb8Guc/bWbPmtlzZvaEmd04du6V7PgzZnZ0mhUHAGAjSnqprmZOV5Ty\n9HTdJ2nPRc7/WtJH3f0fSfozSYdWnL/d3T/k7vOXV0UAAMLg7szpitjspALu/piZ7bzI+SfGXj4p\naceVVwsAgPD0BotKF10derqiNO05XZ+X9PDYa5f0EzN72swOTPm9AADYUBJWo4/axJ6uvMzsdg1D\n161jh29195Nmdo2kH5vZS+7+2BrXH5B0QJLm5uamVS0AACqj22Oz65hNpafLzD4o6duS9rr7m6Pj\n7n4y+/N1SQ9K2r3Wz3D3Q+4+7+7z27Ztm0a1AAColKQ/3Oyanq44XXHoMrM5ST+Q9Bl3/+XY8c1m\ntmX0vaSPS1r1CUgAAGIw6ukidMVp4vCimd0v6TZJW83shKSvSqpLkrsflHSPpPdI+qaZSdJC9qTi\ntZIezI7NSvqeuz+yDm0AAGBDWJ7TxfBilPI8vbh/wvkvSPrCKsePS7rxwisAAIhTsjyni56uGLEi\nPQAABUn6AzVmZ7Spzq/fGPGpAwBQkG4vVadZVzb1BpEhdAEAUBA2u44boQsAgIJ02ew6aoQuAAAK\nkvRTtenpihahCwCAgnR7A/ZdjBihCwCAgiR95nTFjNAFAEABzi0sqjdYZI2uiBG6AAAoQDdbjb7d\nYiJ9rAhdAAAUYHnfRXq6okXoAgCgAMv7LjKnK1qELgAACnC+p4vhxVgRugAAKAA9XSB0AQBQgKQ3\nkCQWR40YoQsAgAJ0+6lqM6YtV82WXRWUhNAFAEABkl6qdrMuMyu7KigJoQsAgAIk/ZSFUSNH6AIA\noABJb0DoihyhCwCAAnTZdzF6hC4AAAqQ9FJWo48coQsAgAIMe7pYGDVmhC4AANbZ4pLr1Fkm0seO\n0AUAwDo7fTaVO6vRx47QBQDAOkt6bAEEQhcAAOtutO8iw4txI3QBALDOlvddbDKRPmaELgAA1lm3\nz/AiCF0AAKy75TldDC9GbWLoMrPDZva6mT2/xnkzs6+b2TEze9bMbho7t8fMXs7O3T3NigMAsFF0\nmdMF5evpuk/Snoucv0PSruzrgKRvSZKZ1STdm52/QdJ+M7vhSioLAMBGlPRSbblqVrM1BphiNjup\ngLs/ZmY7L1Jkr6TvuLtLetLMOmb2Pkk7JR1z9+OSZGYPZGVfvNJKX6lzC4tyL7sWADBdtRlTnV/q\na3J3nVtYKuW93zpzTm3mc0VvYujKYbukV8den8iOrXb85im83xX75/c+oV+8dqrsagDAVDVmZ/Tf\n/uhW7bp2S9lVqaR//V/+Wg/+r5Olvf8Hd7RLe29UwzRC11SY2QENhyc1Nze3ru/1uVt26o0z59b1\nPQCgSL85fU5//vgr+tVvzhC61vDi/zml333vFv2zD72/lPe/+fp3l/K+qI5phK6Tkq4be70jO1Zf\n4/iq3P2QpEOSND8/v66Df//iH183uRAAbCAnk77+/PFX1O0Pyq5KZSX9gW7/+9foD2/7u2VXBZGa\nxuD/Q5I+mz3F+GFJXXd/TdJTknaZ2fVm1pC0LysLAJiy0VIEo6UJcKGklzKvCqWa2NNlZvdLuk3S\nVjM7IemrGvZiyd0PSjoi6U5JxyT1JH0uO7dgZndJelRSTdJhd39hHdoAANFrNWqq12x5uxm809l0\nUecWltRhRXiUKM/Ti/snnHdJX17j3BENQxkAYB2ZmdrNBj1daxj9vbBOFsrEs8UAEIh2c5Y5XWtI\nsr8XtuFBmQhdABCITouerrWwDQ+qgNAFAIHoNOuErjUsDy/S04USEboAIBDtVn15jz+806ns76XT\nYiI9ykPoAoBAdJoNQtcalud0MbyIEhG6ACAQnVZdb59bULpYzv6CVZb0UtVrplajVnZVEDFCFwAE\nYvRkHr1dF0r6qdrNhsys7KogYoQuAAhEm1Xp19TtpWo3K7PdMCJF6AKAQIxCF2t1XSjpD5hEj9IR\nugAgEKNQQU/XhZJeyiR6lI7QBQCBYNPrtbHZNaqA0AUAgWAi/dpO9VM2u0bpCF0AEIgtm+oyGz6p\nh/PSxSWdPrfAvosoHaELAAJRmzFdvamubo+J9OPOr0ZP6EK5CF0AEJBOq05P1wqjv482E+lRMkIX\nAASETa8vtLzZNaELJSN0AUBArm7S07XSaN0y1ulC2QhdABCQTqvBnK4VRj1drNOFshG6ACAgHXq6\nLrAcuphIj5IRugAgIJ1WXd1+qqUlL7sqlZH0U5kNl9QAykToAoCAtJt1uUunzy2UXZXKONVPdfWm\numozVnZVEDlCFwAEZDRZvMsTjMuS3oChRVQCoQsAArK8/2KfyfQjSZ/NrlENhC4ACMioR4e1us5L\neqmuJnShAghdABCQ9nJPF6FrpNtPWaMLlUDoAoCAtLOeLtbqOi/pDRheRCUQugAgIMs9XQwvSpKW\nljzr6SJ0oXyELgAIyFWzNbUaNYYXM6fPLWjJ2XcR1ZArdJnZHjN72cyOmdndq5z/ipk9k309b2aL\nZvbu7NwrZvZcdu7otBsAAHinTnO4QCqGa3RJ7LuIapidVMDMapLulfQxSSckPWVmD7n7i6My7v41\nSV/Lyn9C0r9y97fGfszt7v7GVGsOAFhVu9VgeDHDvouokjw9XbslHXP34+4+kPSApL0XKb9f0v3T\nqBwA4NINe7qYSC+dX6+szZwuVECe0LVd0qtjr09kxy5gZi1JeyR9f+ywS/qJmT1tZgcut6IAgHw6\nrTo9XRl6ulAlE4cXL9EnJD2+YmjxVnc/aWbXSPqxmb3k7o+tvDALZAckaW5ubsrVAoB4tJt1JtJn\nRn8P9HShCvL0dJ2UdN3Y6x3ZsdXs04qhRXc/mf35uqQHNRyuvIC7H3L3eXef37ZtW45qAQBW027V\n1e2lcveyq1K60XplPL2IKsgTup6StMvMrjezhobB6qGVhcysLemjkv5i7NhmM9sy+l7SxyU9P42K\nAwBW12k2NFhcUj9dLLsqpUt6qVqNmq6arZVdFWDy8KK7L5jZXZIelVSTdNjdXzCzL2bnD2ZFPynp\nR+5+ZuzyayU9aGaj9/qeuz8yzQYAAN5pfP/FVmPas0g2Fja7RpXkuhvd/YikIyuOHVzx+j5J9604\ndlzSjVdUQwDAJRmFjG4/1fs7zZJrU65uP1WbNbpQEaxIDwCBabfYCmik26OnC9VB6AKAwHSaw54d\n1uoartPFJHpUBaELAALToadrWdJjs2tUB6ELAAIz6tmJfa0ud1fST1mjC5VB6AKAwLQaNdVrFn1P\n19l0SYOFpeXhVqBshC4ACIyZqd1sRD+na7TvIsOLqApCFwAEiP0X2XcR1UPoAoAAdZp1dSOf09Vl\n30VUDKELAAJET9d4TxdzulANhC4ACNBwTlfcoWs0p42eLlQFoQsAAjTs6Yp8Ij1zulAxhC4ACFCn\nWdeZwaIGC0tlV6U0ST9VvWZqNWplVwWQROgCgCCNhtRiHmJMeqnazYbMrOyqAJIIXQAQpNGq9DGv\n1dXtD1ijC5VC6AKAAHVawyf2Yn6CMemlzOdCpRC6ACBAnSbDi90+m12jWghdABCgUdiIvaerzRpd\nqBBCFwAEaLQgaBJ5T1eb4UVUCKELAAK0ZdOszKRupGt1pYtLevvcAsOLqBRCFwAEaGbG1G7Wo+3p\nGs1lI3ShSghdABCodjPe/RdH7WZ4EVVC6AKAQHWi7ukaDquOls4AqoDQBQCBarca0c7pYt9FVBGh\nCwACFXNP13LoYk4XKoTQBQCB6rTq0S6OOmo3c7pQJYQuAAhUpzkMXUtLXnZVCpf0U5lJWzYRulAd\nhC4ACFS71ZC7dPrsQtlVKVy3N9DVm+qqzVjZVQGWEboAIFCjSeRJP77J9An7LqKCcoUuM9tjZi+b\n2TEzu3uV87eZWdfMnsm+7sl7LQBgfYzmM8W4VlfSS3lyEZUzO6mAmdUk3SvpY5JOSHrKzB5y9xdX\nFP0rd/+Dy7wWADBly5teRziZPumnarNGFyomT0/XbknH3P24uw8kPSBpb86ffyXXAgCuwHLoinCt\nrm5vQE8XKidP6Nou6dWx1yeyYyvdYmbPmtnDZvaBS7wWADBl7eawpyfGZSOY04Uqmji8mNPPJc25\n+9tmdqekH0radSk/wMwOSDogSXNzc1OqFgDEazSnqxvZnK6lJdepfsoaXaicPD1dJyVdN/Z6R3Zs\nmbufcve3s++PSKqb2dY81479jEPuPu/u89u2bbuEJgAAVtOYndHmRi26OV2nzy1oyVkYFdWTJ3Q9\nJWmXmV1vZg1J+yQ9NF7AzN5rZpZ9vzv7uW/muRYAsH46rUZ0Ty92l7cAYiI9qmXi8KK7L5jZXZIe\nlVSTdNjdXzCzL2bnD0r6lKQvmdmCpL6kfe7ukla9dp3aAgBYod2sqxvZOl2jdcmYSI+qyTWnKxsy\nPLLi2MGx778h6Rt5rwUAFKPdrEfX08Vm16gqVqQHgIB1WvXo5nSN2kvoQtUQugAgYJ1WfD1d3Wxd\nstGSGUBVELoAIGDtZkPd/kDDabZxGIVMnl5E1RC6ACBgnVZd6aKrny6WXZXCdPupWo2aGrP8ikO1\n8C8SAALWiXDT66TPZteoJkIXAATs/P6LEYWuHptdo5oIXQAQsNFk8iSitbq6fTa7RjURugAgYDHu\nv5j02Owa1UToAoCALQ8vRrRWV9IndKGaCF0AELDY5nS5u7q9lDW6UEmELgAIWLNeU6M2E82crn66\nqMHiEj1dqCRCFwAEzMzUbtV1KpLhxW6fhVFRXYQuAAhcJ6JNr5c3uyZ0oYIIXQAQuJj2X1zeAojh\nRVQQoQsAAtduNqJ5erGbzV3rMJEeFUToAoDAtZt1dXtxTKRfHl6kpwsVROgCgMB1WvVoerpG7SR0\noYoIXQAQuE6zrt5gUecWFsuuyrpLeqkatRk167WyqwJcgNAFAIEb9fp0I+jt6vYHurpZl5mVXRXg\nAoQuAAhcuzWcVB7DWl1dtgBChRG6ACBwozWrYlg2IumlrNGFyiJ0AUDgYtp/MenR04XqInQBQOBG\na1bF8ARjt89m16guQhcABK693NMV/lpdSW9ATxcqi9AFAIHbctWszMJ/enGwsKQzg0XmdKGyCF0A\nELiZGVM7gk2vuyyMioojdAFABDrN8FelH+27eDU9XagoQhcARKDdagQ/p+v8votMpEc15QpdZrbH\nzF42s2Nmdvcq5z9tZs+a2XNm9oSZ3Th27pXs+DNmdnSalQcA5NNp1oNfHHV5eJGeLlTU7KQCZlaT\ndK+kj0k6IekpM3vI3V8cK/ZrSR9199+a2R2SDkm6eez87e7+xhTrDQC4BJ1WXa+8eabsaqyr8z1d\nhC5UU56ert2Sjrn7cXcfSHpA0t7xAu7+hLv/Nnv5pKQd060mAOBKdCKYSJ8s93QxvIhqyhO6tkt6\ndez1iezYWj4v6eGx1y7pJ2b2tJkduPQqAgCuVLvV0KmzqRaXvOyqrJtubyAzacumiYM4QCmm+i/T\nzG7XMHTdOnb4Vnc/aWbXSPqxmb3k7o+tcu0BSQckaW5ubprVAoDotZt1uUunz6bBTjRP+qnazbpm\nZqzsqgCrytPTdVLSdWOvd2TH3sHMPijp25L2uvubo+PufjL783VJD2o4XHkBdz/k7vPuPr9t27b8\nLQAATBTDptdsdo2qyxO6npK0y8yuN7OGpH2SHhovYGZzkn4g6TPu/sux45vNbMvoe0kfl/T8tCoP\nAMhnedPrgJ9gHPV0AVU1cXjR3RfM7C5Jj0qqSTrs7i+Y2Rez8wcl3SPpPZK+aWaStODu85KulfRg\ndmxW0vfc/ZF1aQkAYE2dCPZf7PYGagc6dIow5JrT5e5HJB1Zcezg2PdfkPSFVa47LunGlccBAMVq\nZ0/0hbz/Yref6nfes7nsagBrYkV6AIjAqKcr5NCV9FPW6EKlEboAIALtwCfSLy25un0m0qPaCF0A\nEIF6bUbvumo22NB1+uyC3MWcLlQaoQsAItFu1pX0w5xIP2oXPV2oMkIXAESi3ayrG2hP16gHjyUj\nUGWELgCIRKdVD3adruV9F5lIjwojdAFAJDqterDrdI3aRehClRG6ACAS7WZD3f5C2dVYF6f6o+FF\nJtKjughdABCJTquubn8gdy+7KlPHnC5sBIQuAIhEp1lXuujqDRbLrsrUJf1Umxs1NWb5tYbq4l8n\nAEQi5E2vk16qDmt0oeIIXQAQifOr0oc3mb7bHzC0iMojdAFAJJY3vQ5wra6klxK6UHmELgCIRNDD\ni2x2jQ2A0AUAkVgOXYH2dBG6UHWELgCIRGc0vBhYT5e761Q/ZY0uVB6hCwAisak+o8bsTHCbXvfT\nRQ0Wl+jpQuURugAgEmamToCbXo+GSztMpEfFEboAICLD/RcDDV30dKHiCF0AEJF2sx7c8OKoPczp\nQtURugAgIu1mI7ieri77LmKDIHQBQESGm16HFbpG644xvIiqI3QBQEQ6TeZ0AWUhdAFARDqtuvrp\nos4tLJZdlanp9lM1ajNq1mtlVwW4KEIXAESk3QpvgdRuf6B2qy4zK7sqwEURugAgIqO1rEJaqyvp\npazRhQ2B0AUAEQlx02v2XcRGQegCgIiM9l8MaTJ9wr6L2CByhS4z22NmL5vZMTO7e5XzZmZfz84/\na2Y35b0WAFCc0VpWSS+cBVK7vQFrdGFDmBi6zKwm6V5Jd0i6QdJ+M7thRbE7JO3Kvg5I+tYlXAsA\nKEg7G4YLaSJ90md4ERtDnp6u3ZKOuftxdx9IekDS3hVl9kr6jg89KaljZu/LeS0AoCBbrprVjIUz\nvHhuYVG9wSIT6bEhzOYos13Sq2OvT0i6OUeZ7TmvBQAUZGbG1G7W9Z+PvqrHf/VG2dW5YotLLomF\nUbEx5AldhTCzAxoOTWpubq7k2gBAuP7lR67Xz155q+xqTM3v/+41unXXtrKrAUyUJ3SdlHTd2Osd\n2bE8Zeo5rpUkufshSYckaX5+3nPUCwBwGf7o93eVXQUgSnnmdD0laZeZXW9mDUn7JD20osxDkj6b\nPcX4YUldd38t57UAAADBm9jT5e4LZnaXpEcl1SQddvcXzOyL2fmDko5IulPSMUk9SZ+72LXr0hIA\nAIAKM/fqjeTNz8/70aNHy64GAADARGb2tLvPTyrHivQAAAAFIHQBAAAUgNAFAABQAEIXAABAAQhd\nAAAABSB0AQAAFIDQBQAAUABCFwAAQAEIXQAAAAUgdAEAABSgktsAmdlvJP3NOr/NVklvrPN7VFXM\nbZfibn/MbZfibj9tj1fM7S+q7b/j7tsmFapk6CqCmR3Ns09SiGJuuxR3+2NuuxR3+2l7nG2X4m5/\n1drO8CIAAEABCF0AAAAFiDl0HSq7AiWKue1S3O2Pue1S3O2n7fGKuf2Vanu0c7oAAACKFHNPFwAA\nQGGCC11wkE3vAAAD/ElEQVRmtsfMXjazY2Z29yrnzcy+np1/1sxuynvtRpCj/Z/O2v2cmT1hZjeO\nnXslO/6MmR0ttuZXLkfbbzOzbta+Z8zsnrzXbgQ52v+VsbY/b2aLZvbu7NxG/+wPm9nrZvb8GueD\nve9ztD3ke35S20O/5ye1P+R7/joz+0sze9HMXjCzP16lTPXue3cP5ktSTdKvJP1tSQ1Jfy3phhVl\n7pT0sCST9GFJP817bdW/crb/Fkl/K/v+jlH7s9evSNpadjvWse23Sfqvl3Nt1b8utQ2SPiHpv4fw\n2Wf1/yeSbpL0/BrnQ77vJ7U9yHs+Z9uDvefztH9F2dDu+fdJuin7foukX26E3/eh9XTtlnTM3Y+7\n+0DSA5L2riizV9J3fOhJSR0ze1/Oa6tuYhvc/Ql3/2328klJOwqu43q5ks8vis9+hf2S7i+kZgVw\n98ckvXWRIsHe95PaHvA9n+dzX8uG/9ylS25/aPf8a+7+8+z705J+IWn7imKVu+9DC13bJb069vqE\nLvwQ1iqT59qqu9Q2fF7D/wsYcUk/MbOnzezAOtRvPeVt+y1ZN/PDZvaBS7y2ynK3wcxakvZI+v7Y\n4Y382ecR8n1/KUK65/MK9Z7PLfR73sx2Svo9ST9dcapy9/1sEW+C6jGz2zX8D/CtY4dvdfeTZnaN\npB+b2UvZ/0mF4ueS5tz9bTO7U9IPJe0quU5l+ISkx919/P+QQ//so8c9zz0f4j1vZu/SMEz+ibuf\nKrs+k4TW03VS0nVjr3dkx/KUyXNt1eVqg5l9UNK3Je119zdHx939ZPbn65Ie1LALdqOY2HZ3P+Xu\nb2ffH5FUN7Otea7dAC6lDfu0Yphhg3/2eYR8308U6D0/UeD3/KUI8p43s7qGgeu77v6DVYpU774v\nYuJYUV8a9twdl3S9zk+O+8CKMv9U75xY97O811b9K2f75yQdk3TLiuObJW0Z+/4JSXvKbtOU2/5e\nnV+bbrek/539O4jis8/KtTWcA7I5lM9+rB07tfaE6mDv+xxtD/Kez9n2YO/5PO3Pzgd5z2ef43ck\n/YeLlKncfR/U8KK7L5jZXZIe1fDphMPu/oKZfTE7f1DSEQ2faDgmqSfpcxe7toRmXLac7b9H0nsk\nfdPMJGnBh5uBXivpwezYrKTvufsjJTTjsuRs+6ckfcnMFiT1Je3z4R0Yy2cvSZ+U9CN3PzN2+Yb+\n7CXJzO7X8Em1rWZ2QtJXJdWl8O/7HG0P8p6XcrU92HteytV+KdB7XtJHJH1G0nNm9kx27E81/J+M\nyt73rEgPAABQgNDmdAEAAFQSoQsAAKAAhC4AAIACELoAAAAKQOgCAAAoAKELAACgAIQuAACAAhC6\nAAAACvD/Ae28krdbAApEAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fc08274c208>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(thetas, [loss(theta,train) for theta in thetas])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "What do you observe here? What does it mean for our prediction task? Discuss with your neighbour and enter your answer here: https://tinyurl.com/ya57djqr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Learning\n",
    "is as simple as choosing the parameter with the lowest loss:\n",
    "\n",
    "$$\n",
    "\\param^* = \\argmin_{\\param \\in [0,2]} l(\\param) \n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.2653061224489794"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta_star = thetas[np.argmin([loss(theta,train) for theta in thetas])]\n",
    "theta_star"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Prediction\n",
    "same thing, just in $\\Ys$:\n",
    "\n",
    "$$\\y{^*}_{\\param}=\\argmax_\\y s_\\param(\\x,\\y).$$\n",
    "\n",
    "Seen before? Yes, training often involves prediction in inner loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table align=\"left\" style=\"font-size:x-large;\"><tr><td style='padding:5px; text-align:left'>Yesterday I ate a red apple</td> <td style='padding:5px; text-align:left'>Gestern aß ich einen roten Apfel</td><tr><tr><td style='padding:5px; text-align:left'>Yesterday I ate a red apply with a friend</td> <td style='padding:5px; text-align:left'>Gestern aß ich einen roten Apfel mit einem Freund</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x7fc0825c3710>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "util.Table([(x,predict(theta_star, x)) for x,_ in test])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### In Practice\n",
    "Feature representations and scoring functions are **more elaborate**\n",
    "* involve several **non-linear** transformations of both input and output \n",
    "* Maybe learn automatically: **representation** and **deep learning**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Parameter space usually **multi-dimensional** (millions of dimensions). \n",
    "* **Impossible to search exhaustively**.\n",
    "* **Numeric optimisation algorithms** (often SGD)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Output space often exponentional sized (e.g. *all* German sentences)\n",
    "* **Impossible to search exhaustively**.\n",
    "* **Discrete optimisation algorithms** (Dynamic Programming, Greedy, integer linear programming)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Summary of Recipe 1: Learn to Score, Implement How to Predict\n",
    "\n",
    "* Learn a scoring function\n",
    "* Find the highest scoring solution using a discrete algorithm\n",
    "\n",
    "* Could we alternatively learn the prediction or search algorithm directly? Yes, with..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Recipe 2: Learn to Predict\n",
    "\n",
    "* Consider language processing as a **program**\n",
    "* Learn which **action** the program should do at each stage\n",
    "* For example:\n",
    "    * actions are \"adding a word to a translation\"\n",
    "    * program performs actions until all source words are translated\n",
    "* Can be framed as \n",
    "    * reinforcement learning \n",
    "    * [imitation learning](https://www.cs.cmu.edu/~sross1/publications/Ross-AIStats11-NoRegret.pdf)\n",
    "* Will see this in [dependency parsing](/notebooks/chapters/Transition-based%20dependency%20parsing.ipynb) \n",
    "    \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Background Reading\n",
    "\n",
    "* Noah Smith, [Linguistic Structure Prediction](http://www.cs.cmu.edu/~nasmith/LSP/)\n",
    "    * Free when logging in through UCPH \n",
    "    * Relevant: \n",
    "        * Introduction\n",
    "        * Dynamic Programming \n",
    "        * Generative Models (and unsupervised generative models)\n",
    "        * Globally Normalised Conditional Log-Linear Models  \n",
    "   "
   ]
  }
 ],
 "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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}