chapters/structured_prediction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!---\n",
    "Latex Macros\n",
    "-->\n",
    "$$\n",
    "\\newcommand{\\Xs}{\\mathcal{X}}\n",
    "\\newcommand{\\Ys}{\\mathcal{Y}}\n",
    "\\newcommand{\\y}{\\mathbf{y}}\n",
    "\\newcommand{\\repr}{\\mathbf{f}}\n",
    "\\newcommand{\\repry}{\\mathbf{g}}\n",
    "\\newcommand{\\x}{\\mathbf{x}}\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{\\indi}{\\mathbb{I}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%%capture\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "%matplotlib inline\n",
    "import sys\n",
    "sys.path.append(\"..\")\n",
    "import statnlpbook.util as util\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "matplotlib.rcParams['figure.figsize'] = (10.0, 6.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Structured Prediction\n",
    "\n",
    "In general there seems to be no emerging unified _theory of NLP_ to emerge, and 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>\n",
    "\n",
    "That's not to say though that they aren't cross-cutting patterns, general best practices and recipes that reoccur frequently. One such reoccurring pattern I found in many NLP papers and systems is what I like to refer to as the *[structured prediction](http://en.wikipedia.org/wiki/Structured_prediction) recipe*.\n",
    "\n",
    "The general goal we address with this recipe is the following. We like to, given some input structure $\\x \\in \\Xs$, predict a suitable output structure $\\y \\in \\Ys$. In the context of NLP $\\Xs$ may be the set of documents, and $\\Ys$ a set of document classes (e.g. sports and business). $\\Xs$ may also be the set of French sentences, and $\\Ys$ the set of English sentences. In this case each $\\y \\in \\Ys$ is a _structured_ object (hence the use of bold face). This structured **output** aspect of the problem has profound consequences on the methods used to address it (as opposed to structure in the input, which one can deal with relatively straight-forwardly). Generally we are also given some _training set_ $\\train$ which may contain input-output pairs $(\\x,\\y)_i$, but possibly also just input data (in unsupervised learning), annotated data but for a different task (multi-task, distant, weak supervision, etc.), or some mixture of it. \n",
    "\n",
    "\n",
    "With the above ingredients the recipe goes as follows: \n",
    "\n",
    " 1. Define a parametrized _model_ or _scoring function_ \\\\(s_\\params(\\x,\\y)\\\\) that measures the _match_ of a given \\\\(\\x\\\\) and \\\\(\\y\\\\). This model incorporates the background knowledge we have about the task, and usually involves _representations_  $\\repr_\\params(\\x)$ and $\\repry_\\params(\\y)$ that capture the character of the input and output relevant to the task---in the past representations were mostly handcrafted but with the advent of deep learning they tend to be learned from data now. The model is also controlled by a set of real-valued parameters \\\\(\\params\\\\).\n",
    " 1. _Learn_ the parameters \\\\(\\params\\\\) from the training data \\\\(\\train\\\\), ideally such that performance on the task of choice is optimized. This learning step usually involves some _continuous optimization problem_ that serves as a surrogate for the task performance we like to maximize. This problem defines a _loss function_ we have to minimise to optimise task performance.  \n",
    " 1. Given an input \\\\(\\x\\\\) _predict_ the highest-scoring (and hence best-matching) output structure $$ \\y^* = \\argmax_{\\y\\in\\Ys} s(\\x,\\y) $$ to serve as the prediction of the model. Given that most of the structures we care about in NLP are discrete, this task usually involves some _discrete optimization problem_ and is important not just at _test time_ when the model is applied, but often also during training (as, intuitively, we like to train the model such that it _predicts well_). \n",
    " \n",
    "You will see examples of this recipe throughout the book, as well as frameworks and methods that make this recipe possible. It's worthwhile noting that good NLPers usually combine three skills in accordance with this recipe: 1. modelling, 2. continuous optimization and 3. discrete optimization. For the second and third some basic mathematical background is generally useful, for the first some understanding of the language phenomena you seek to model can be helpful. It's probably fair to say that modelling is the most important bit, and in practice this often shows through the fact that clever features (part of the model) beat clever optimization quite often. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Simple Example\n",
    "\n",
    "It is difficult to show this recipe in action without going into too much depth. We will do so by introducing a very simple structured prediction example that illustrates all aspects of the recipe. We consider the task of machine translation from English to German, and make the following (extremely unrealistic) assumptions:\n",
    "* There are only 4 target German sentences we care about. All English sentences we encounter can be translated to one of these 4 sentences. \n",
    "* The lengths of the source English and target German sentence are sufficient representations of the problem. That is, one can decide which German sentence is the correct translation be comparing its lengths to the length of the English sentence. \n",
    "\n",
    "It is important to remember that while this is a toy example, the main steps and ingredients are found in every statistical NLP application. \n",
    "\n",
    "### Input and Output Spaces\n",
    "First we define our input and output spaces $\\Xs$ and $\\Ys$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style=\"font-size:large;\"><tr><td style='padding:5px'>I ate an apple</td> <td style='padding:5px'>Ich aß einen Apfel</td><tr><tr><td style='padding:5px'>I ate a red apple</td> <td style='padding:5px'>Ich aß einen roten Apfel</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x107855240>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x_space = ['I ate an apple', \n",
    "           'I ate a red apple', \n",
    "           'Yesterday I ate a red apple', \n",
    "           'Yesterday I ate a red apply with a friend']\n",
    "y_space = ['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']\n",
    "data = list(zip(x_space,y_space))\n",
    "train = data[:2]\n",
    "test = data[2:]\n",
    "util.Table(train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model\n",
    "Modelling consists of two steps: finding suitable representations of $\\x$ and $\\y$, and measuring their compatibility using a scoring function. \n",
    "#### Representation\n",
    "We incorporate the assumptions that only sentence lengths matter when translating by defining $\\repr(\\x)=|\\x|$ and $\\repry(\\y)=|\\y|$ where $|\\cdot|$ counts the number of characters in the sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    \"\"\"Calculate a representation of the input `x`.\"\"\"\n",
    "    return len(x)\n",
    "def g(y):\n",
    "    \"\"\"Calculate a representation of the output `y`.\"\"\"\n",
    "    return len(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Scoring Function\n",
    "The scoring function only cares about the difference in length between the sentences when assessing the compatibility between the English and German sentence. We assume that German words are always a little longer than English words, and hence we cannot directly compare lengths but must scale the English length linearly:\n",
    "\n",
    "$$\n",
    "s_\\param(\\x,\\y) = -| \\param \\repr(\\x) - \\repry(\\y)|\n",
    "$$\n",
    "\n",
    "The single parameter $\\param\\in \\mathbb{R}$ determines how the English length needs to be scaled to be close to its German counterpart.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style=\"font-size:large;\"><tr><td style='padding:5px'>I ate an apple</td> <td style='padding:5px'>Ich aß einen Apfel</td> <td style='padding:5px'>14</td> <td style='padding:5px'>18</td> <td style='padding:5px'>-4.0</td><tr><tr><td style='padding:5px'>I ate a red apple</td> <td style='padding:5px'>Ich aß einen roten Apfel</td> <td style='padding:5px'>17</td> <td style='padding:5px'>24</td> <td style='padding:5px'>-7.0</td><tr><tr><td style='padding:5px'>Yesterday I ate a red apple</td> <td style='padding:5px'>Gestern aß ich einen roten Apfel</td> <td style='padding:5px'>27</td> <td style='padding:5px'>32</td> <td style='padding:5px'>-5.0</td><tr><tr><td style='padding:5px'>Yesterday I ate a red apply with a friend</td> <td style='padding:5px'>Gestern aß ich einen roten Apfel mit einem Freund</td> <td style='padding:5px'>41</td> <td style='padding:5px'>49</td> <td style='padding:5px'>-8.0</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x106d62978>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "def s(theta,x,y):\n",
    "    \"\"\"Measure the compatibility of sentences `x` and `y` using parameter `theta`\"\"\"\n",
    "    return -abs(theta * f(x) - g(y))\n",
    "\n",
    "util.Table([(x,y,f(x),g(y),s(1.0,x,y)) for x,y in data])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Loss Function\n",
    "We want to _programmatically_ find out what the optimal $\\param$ is. We do so by providing a simple loss function: for every training instance we receive a penalty of $1$ if the highest scoring translation is not the correct one. We can formalise this as follows:\n",
    "\n",
    "$$\n",
    "l(\\param)=\\sum_{(\\x,\\y) \\in \\train} \\indi(\\y\\neq\\y'_{\\param})\n",
    "$$\n",
    "where $\\y'_{\\param} \\in \\Ys$ is the highest scoring German sentence \n",
    "$$\\y'_{\\param}=\\argmax_\\y s_\\param(\\x,\\y).$$\n",
    "\n",
    "In python this can be implemented as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def loss(theta, data):\n",
    "    \"\"\"Measure the total number of errors made when predicting with parameter `theta` on training set `data`\"\"\"\n",
    "    total = 0.0\n",
    "    for x,y in data:\n",
    "        max_score = -math.inf\n",
    "        result = None\n",
    "        for y_guess in y_space:\n",
    "            score = s(theta,x,y_guess)\n",
    "            if score > max_score:\n",
    "                result = y_guess\n",
    "                max_score = score\n",
    "        if result != y:\n",
    "            total += 1.0\n",
    "    return total\n",
    "\n",
    "loss(1.0, train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Learning\n",
    "With the model and loss defined, we can now _learn_ the model parameters. Learning simply amounts to finding the parameter with minimal loss:\n",
    "\n",
    "$$\n",
    "\\param^* = \\argmin_{\\param} l(\\param) \n",
    "$$\n",
    "\n",
    "Let us focus our attention on $\\param \\in [0,2]$ and investigate the loss landscape."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x108f84358>]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAl0AAAFpCAYAAACmgZ0NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X+Q3Hd93/HX6+72pDsj79pIEGJblmnUgmnAkKtJwFNM\nSIxMG4tMMh158sNQGHUSTJKmkxlIZuyO+SdtZppOJiRGkyiEFGyIE6dKa2I8MZQW12CZGP8CgxBO\nLJXWxmJXsnet3bt794/97nl9utOtpL3v93vfz/Mxc6Pd7/e7e5+P9s56+fN5fz8fR4QAAACwviaK\nbgAAAEAKCF0AAAA5IHQBAADkgNAFAACQA0IXAABADghdAAAAOSB0AQAA5IDQBQAAkANCFwAAQA4I\nXQAAADmYKroBK9m6dWvs2LGj6GYAAACs6cEHH/xeRGxb67pShq4dO3bo4MGDRTcDAABgTbb/fpTr\nmF4EAADIAaELAAAgB4QuAACAHBC6AAAAckDoAgAAyAGhCwAAIAeELgAAgBwQugAAAHJA6AIAAMjB\nmqHL9iW2P2/7cduP2f7VFa6x7d+zfcj2w7bfNHTuBtvfyr5uGHcHAAAANoJRtgGal/TvIuKrtrdI\netD2PRHx+NA110ramX29WdIfSnqz7Qsl3SxpTlJkrz0QEd8fay8AAABKbs3QFRHflfTd7PEJ21+X\ndJGk4dC1W9InIiIk3W+7YftVkq6WdE9EHJMk2/dI2iXptrH2AgCACphfWNRXvnNMJxcWi25KJUzY\nets/XnMf6tyc0YbXtndIeqOkLy87dZGkp4aeH8mOrXZ8pffeK2mvJG3fvv1MmgUAQCV87vH/p1/+\n5FeLbkZlbK5N6BsfubboZiwZOXTZfpmkv5D0axFxfNwNiYh9kvZJ0tzcXIz7/QEAKLv/23pBkvRf\n3vdmnbdpsuDWbHwTdtFNeImRQpftmvqB65MR8ZcrXHJU0iVDzy/Ojh1Vf4px+PgXzqahAABUXbPT\nky295R+9XBMT5QoMOHej3L1oSX8s6esR8Z9WueyApF/M7mL8UUmtrBbsbknX2L7A9gWSrsmOAQCA\nZVrtrs7fXCNwVdQoI11vlfQLkh6x/VB27DclbZekiLhV0l2S3iXpkKS2pPdm547Z/oikB7LX3TIo\nqgcAAC/V7PTUmK0V3Qysk1HuXvxfkk4bubO7Fj+wyrn9kvafVesAAEhIq9NTY4bQVVWsSA8AQEk0\n2z3VZ6eLbgbWCaELAICSYKSr2ghdAACURLPdpaarwghdAACUwOJiMNJVcYQuAABK4MTJeS2GdD6h\nq7IIXQAAlECr3ZMkNSikryxCFwAAJdDsdCWJ6cUKI3QBAFACzaWRLkJXVRG6AAAogVaH0FV1hC4A\nAEqgmYWu+gw1XVVF6AIAoARa7X5NV52arsoidAEAUALNdk/nTU9qeop/mquKTxYAgBJodnqMclUc\noQsAgBJgs+vqI3QBAFACrU6XNboqjtAFAEAJNNs9louoOEIXAAAl0OoQuqqO0AUAQMEiIiukp6ar\nyghdAAAU7IXeorrzi4x0VRyhCwCAgrHZdRoIXQAAFGyw2TXrdFUboQsAgIIthS6mFyuN0AUAQMFa\nS9OLFNJXGaELAICCDUa6KKSvNkIXAAAFa3UIXSkgdAEAULBmp6fpyQnN1CaLbgrWEaELAICC9Te7\nrsl20U3BOiJ0AQBQMDa7TsPUWhfY3i/pX0p6OiL+6Qrnf0PSzw2932slbYuIY7aflHRC0oKk+YiY\nG1fDAQCoima7xxpdCRhlpOvjknatdjIificiroiIKyR9WNL/iIhjQ5e8PTtP4AIAYAXNNptdp2DN\n0BURX5R0bK3rMtdLuu2cWgQAQGJabHadhLHVdNmeVX9E7C+GDoekz9l+0PbecX0vAACqpNnuMtKV\ngDVrus7AT0n60rKpxasi4qjtV0i6x/Y3spGzU2ShbK8kbd++fYzNAgCgvHoLi3q+u0AhfQLGeffi\nHi2bWoyIo9mfT0u6U9KVq704IvZFxFxEzG3btm2MzQIAoLxYGDUdYwldtuuS3ibpvw4dO8/2lsFj\nSddIenQc3w8AgKp4cbNrarqqbpQlI26TdLWkrbaPSLpZUk2SIuLW7LKflvS5iHh+6KWvlHRnttDb\nlKRPRcTfjK/pAABsfC9uds1IV9WtGboi4voRrvm4+ktLDB87LOkNZ9swAABSwGbX6WBFegAACrQ0\nvchIV+URugAAKFBzUEjPOl2VR+gCAKBArXZXtrRl8zhXcUIZEboAAChQfzX6miYmXHRTsM4IXQAA\nFKjZ6XHnYiIIXQAAFKjZ7rFGVyIIXQAAFIiRrnQQugAAKFCLza6TQegCAKBAzayQHtVH6AIAoCCL\ni6EW04vJIHQBAFCQEy/MK4LNrlNB6AIAoCBNNrtOCqELAICCtDpsdp0SQhcAAAUZbHZN6EoDoQsA\ngIIMNruus9l1EghdAAAUpNXOaroY6UoCoQsAgIIMphdZpysNhC4AAArS7PR03vSkapP8c5wCPmUA\nAArSbPfUYI2uZBC6AAAoSKvTZWoxIYQuAAAK0ur0KKJPCKELAICC9KcXCV2pIHQBAFCQZqfHGl0J\nIXQBAFCAiFCLka6kELoAAChAp7eg7sIihfQJIXQBAFCApX0XCV3JIHQBAFAANrtOD6ELAIACNDv9\nfRcppE/HmqHL9n7bT9t+dJXzV9tu2X4o+7pp6Nwu20/YPmT7Q+NsOAAAG9nxDiNdqRllpOvjknat\ncc3/jIgrsq9bJMn2pKSPSrpW0uWSrrd9+bk0FgCAqmB6MT1rhq6I+KKkY2fx3ldKOhQRhyOiK+l2\nSbvP4n0AAKic5mCki+nFZIyrpuvHbH/N9mdtvy47dpGkp4auOZIdAwAgec12T9NTE9pco7w6FVNj\neI+vSro0Ip6z/S5JfyVp55m+ie29kvZK0vbt28fQLAAAymuw2bXtopuCnJxzvI6I4xHxXPb4Lkk1\n21slHZV0ydClF2fHVnuffRExFxFz27ZtO9dmAQBQas12jzW6EnPOocv2DziL6bavzN7zWUkPSNpp\n+zLb05L2SDpwrt8PAIAqYLPr9Kw5vWj7NklXS9pq+4ikmyXVJCkibpX0s5J+yfa8pI6kPRERkuZt\n3yjpbkmTkvZHxGPr0gsAADaYZqenixozRTcDOVozdEXE9Wuc/31Jv7/Kubsk3XV2TQMAoLqOd3p6\n3Q+eX3QzkCNumQAAoADNdpearsQQugAAyFl3flHPdxeo6UoMoQsAgJy1soVR67MsjJoSQhcAADlr\nZZtdM72YFkIXAAA5G+y7WCd0JYXQBQBAztjsOk2ELgAAcsZm12kidAEAkLMXC+kZ6UoJoQsAgJy1\n2l1NWNqyac01ylEhhC4AAHLW7PRUn6lpYsJFNwU5InQBAJCz/mbX1HOlhtAFAEDOBiNdSAuhCwCA\nnLXaXUJXgghdAADkrNnpsUZXgghdAADkrNnusQVQgghdAADkaHExdPyFHptdJ4jQBQBAjk68MK8I\nNrtOEaELAIAcNTtdSey7mCJCFwAAOWKz63QRugAAyNFgs+s6m10nh9AFAECOmu3+9CLrdKWH0AUA\nQI5aHaYXU0XoAgAgR4OaLka60kPoAgAgR812Ty/bNKXaJP8Ep4ZPHACAHLXY7DpZhC4AAHLU6nSp\n50oUoQsAgBw122x2nSpCFwAAOWp2emqwRleS1gxdtvfbftr2o6uc/znbD9t+xPZ9tt8wdO7J7PhD\ntg+Os+EAAGxEzXZP51PTlaRRRro+LmnXac5/R9LbIuKHJX1E0r5l598eEVdExNzZNREAgGqICGq6\nEja11gUR8UXbO05z/r6hp/dLuvjcmwUAQPW0uwvqLYQajHQladw1Xe+T9Nmh5yHpc7YftL13zN8L\nAIANpclq9Elbc6RrVLbfrn7oumro8FURcdT2KyTdY/sbEfHFVV6/V9JeSdq+ffu4mgUAQGm02mx2\nnbKxjHTZfr2kP5K0OyKeHRyPiKPZn09LulPSlau9R0Tsi4i5iJjbtm3bOJoFAECpNDv9za4Z6UrT\nOYcu29sl/aWkX4iIbw4dP8/2lsFjSddIWvEOSAAAUjAY6SJ0pWnN6UXbt0m6WtJW20ck3SypJkkR\ncaukmyS9XNIf2Jak+exOxVdKujM7NiXpUxHxN+vQBwAANoSlmi6mF5M0yt2L169x/v2S3r/C8cOS\n3nDqKwAASFNzqaaLka4UsSI9AAA5aXa6mp6a0OYa//ymiE8dAICctNo9NWZqykpvkBhCFwAAOWGz\n67QRugAAyEmLza6TRugCACAnzU5PdUa6kkXoAgAgJ612l30XE0boAgAgJ80ONV0pI3QBAJCDk/ML\nancXWKMrYYQuAABy0MpWo6/PUkifKkIXAAA5WNp3kZGuZBG6AADIwdK+i9R0JYvQBQBADl4c6WJ6\nMVWELgAAcsBIFwhdAADkoNnuShKLoyaM0AUAQA5anZ4mJ6wtm6aKbgoKQugCACAHzXZP9ZmabBfd\nFBSE0AUAQA6anR4LoyaO0AUAQA6a7S6hK3GELgAActBi38XkEboAAMhBs91jNfrEEboAAMhBf6SL\nhVFTRugCAGCdLSyGjr9AIX3qCF0AAKyzEy/0FMFq9KkjdAEAsM6abbYAAqELAIB1N9h3kenFtBG6\nAABYZ0v7Ls5QSJ8yQhcAAOus1WF6EYQuAADW3VJNF9OLSRspdNneb/tp24+uct62f8/2IdsP237T\n0LkbbH8r+7phXA0HAGCjaFHTBY0+0vVxSbtOc/5aSTuzr72S/lCSbF8o6WZJb5Z0paSbbV9wto0F\nAGAjarZ72rJpSlOTTDClbGqUiyLii7Z3nOaS3ZI+EREh6X7bDduvknS1pHsi4pgk2b5H/fB227k0\n+lydnF9QRJEtAIDxm5ywavyjvqqI0Mn5xUK+97HnT6pOPVfyRgpdI7hI0lNDz49kx1Y7Xqh3f/Q+\nff27x4tuBgCM1fTUhP77B6/SzlduKboppfTrn/ma7vy7o4V9/9dfXC/se6McxhW6zpntvepPTWr7\n9u3r+r3e+5Yd+t7zJ9f1ewBAnp45cVJ/8qUn9e1nnid0reLx/3Ncr/mBLbruih8s5Pu/+bILC/m+\nKI9xha6jki4Zen5xduyo+lOMw8e/sNIbRMQ+SfskaW5ubl0n//7VP7tk7YsAYAM52uzoT770pFqd\nbtFNKa1mp6u3/5NX6Jev/qGim4JEjWvy/4CkX8zuYvxRSa2I+K6kuyVdY/uCrID+muwYAGCMBksR\nDJYmwKma7R51VSjUSCNdtm9Tf8Rqq+0j6t+RWJOkiLhV0l2S3iXpkKS2pPdm547Z/oikB7K3umVQ\nVA8AGJ/Z6UnVJr203Qxe6oXegk7OL6rBivAo0Kh3L16/xvmQ9IFVzu2XtP/MmwYAGJVt1WemGela\nxeDvhXWyUCTuLQaAiqjPTFHTtYpm9vfCNjwoEqELACqiMctI12rYhgdlQOgCgIpozNQIXatYml5k\npAsFInQBQEXUZ2tLe/zhpY5nfy+NWQrpURxCFwBURGNmmtC1iqWaLqYXUSBCFwBURGO2pudOzqu3\nUMz+gmXWbPdUm7RmpyeLbgoSRugCgIoY3JnHaNepmp2e6jPTsl10U5AwQhcAVESdVelX1Wr3VJ8p\nzXbDSBShCwAqYhC6WKvrVM1OlyJ6FI7QBQAVMQgVjHSdqtnuUUSPwhG6AKAi2PR6dWx2jTIgdAFA\nRVBIv7rjnR6bXaNwhC4AqIgtm2uy+3fq4UW9hUWdODnPvosoHKELACpicsI6f3NNrTaF9MNeXI2e\n0IViEboAoEIaszVGupYZ/H3UKaRHwQhdAFAhbHp9qqXNrgldKBihCwAq5PwZRrqWG6xbxjpdKBqh\nCwAqpDE7TU3XMoORLtbpQtEIXQBQIQ1Guk6xFLoopEfBCF0AUCGN2ZpanZ4WF6PoppRGs9OT3V9S\nAygSoQsAKqQ+U1OEdOLkfNFNKY3jnZ7O31zT5ISLbgoSR+gCgAoZFIu3uINxSbPdZWoRpUDoAoAK\nWdp/sUMx/UCzw2bXKAdCFwBUyGBEh7W6XtRs93Q+oQslQOgCgAqpL410EboGWp0ea3ShFAhdAFAh\n9Wyki7W6XtRsd5leRCkQugCgQpZGuphelCQtLkY20kXoQvEIXQBQIZumJjU7Pcn0YubEyXktBvsu\nohxGCl22d9l+wvYh2x9a4fzv2n4o+/qm7ebQuYWhcwfG2XgAwKkaM/0FUtFfo0ti30WUw9RaF9ie\nlPRRST8p6YikB2wfiIjHB9dExL8duv6Dkt449BadiLhifE0GAJxOfXaa6cUM+y6iTEYZ6bpS0qGI\nOBwRXUm3S9p9muuvl3TbOBoHADhz/ZEuCumlF9crq1PThRIYJXRdJOmpoedHsmOnsH2ppMsk3Tt0\neLPtg7bvt/3us24pAGAkjdkaI10ZRrpQJmtOL56hPZLuiIiFoWOXRsRR26+WdK/tRyLi28tfaHuv\npL2StH379jE3CwDSUZ+pUUifGfw9MNKFMhhlpOuopEuGnl+cHVvJHi2bWoyIo9mfhyV9QS+t9xq+\nbl9EzEXE3LZt20ZoFgBgJfXZmlrtniKi6KYUbrBeGXcvogxGCV0PSNpp+zLb0+oHq1PuQrT9GkkX\nSPrfQ8cusL0pe7xV0lslPb78tQCA8WnMTKu7sKhOb2Htiyuu2e5pdnpSm6Ymi24KsPb0YkTM275R\n0t2SJiXtj4jHbN8i6WBEDALYHkm3x0v/1+q1kj5me1H9gPfbw3c9AgDGb3j/xdnpcVeRbCxsdo0y\nGem3MSLuknTXsmM3LXv+71d43X2Sfvgc2gcAOEODkNHq9PSDjZmCW1OsVqenOmt0oSRYkR4AKqY+\ny1ZAA602I10oD0IXAFRMY6Y/ssNaXf11uiiiR1kQugCgYhqMdC1pttnsGuVB6AKAihmM7KS+VldE\nqNnpsUYXSoPQBQAVMzs9qdqkkx/peqG3qO784tJ0K1A0QhcAVIxt1Wemk6/pGuy7yPQiyoLQBQAV\nxP6L7LuI8iF0AUAFNWZqaiVe09Vi30WUDKELACqIka7hkS5qulAOhC4AqKB+TVfaoWtQ08ZIF8qC\n0AUAFdQf6Uq8kJ6aLpQMoQsAKqgxU9Pz3QV15xeLbkphmp2eapPW7PRk0U0BJBG6AKCSBlNqKU8x\nNts91WemZbvopgCSCF0AUEmDVelTXqur1emyRhdKhdAFABXUmO3fsZfyHYzNdo96LpQKoQsAKqgx\nw/Riq8Nm1ygXQhcAVNAgbKQ+0lVnjS6UCKELACposCBoM/GRrjrTiygRQhcAVNCWzVOypVaia3X1\nFhb13Ml5phdRKoQuAKigiQmrPlNLdqRrUMtG6EKZELoAoKLqM+nuvzjoN9OLKBNCFwBUVCPpka7+\ntOpg6QygDAhdAFBR9dnpZGu62HcRZUToAoCKSnmkayl0UdOFEiF0AUBFNWZryS6OOug3NV0oE0IX\nAFRUY6YfuhYXo+im5K7Z6cmWtmwmdKE8CF0AUFH12WlFSCdemC+6Kblrtbs6f3NNkxMuuinAEkIX\nAFTUoIi82UmvmL7JvosooZFCl+1dtp+wfcj2h1Y4/x7bz9h+KPt6/9C5G2x/K/u6YZyNBwCsblDP\nlOJaXc12jzsXUTpTa11ge1LSRyX9pKQjkh6wfSAiHl926acj4sZlr71Q0s2S5iSFpAez135/LK0H\nAKxqadPrBIvpm52e6qzRhZIZZaTrSkmHIuJwRHQl3S5p94jv/05J90TEsSxo3SNp19k1FQBwJpZC\nV4JrdbXaXUa6UDqjhK6LJD019PxIdmy5n7H9sO07bF9yhq8FAIxZfaY/0pPishHUdKGMxlVI/9eS\ndkTE69UfzfrTM30D23ttH7R98JlnnhlTswAgXYOarlZiNV2Li6HjnR5rdKF0RgldRyVdMvT84uzY\nkoh4NiJOZk//SNKPjPraoffYFxFzETG3bdu2UdoOADiN6akJnTc9mVxN14mT81oMFkZF+YwSuh6Q\ntNP2ZbanJe2RdGD4AtuvGnp6naSvZ4/vlnSN7QtsXyDpmuwYACAHjdnp5O5ebC1tAUQhPcplzbsX\nI2Le9o3qh6VJSfsj4jHbt0g6GBEHJP2K7eskzUs6Juk92WuP2f6I+sFNkm6JiGPr0A8AwArqMzW1\nEluna7AuGYX0KJs1Q5ckRcRdku5aduymoccflvThVV67X9L+c2gjAOAs1WdqyY10sdk1yooV6QGg\nwhqzteRqugb9JXShbAhdAFBhjdn0Rrpa2bpkgyUzgLIgdAFAhdVnptXqdBURRTclN4OQyd2LKBtC\nFwBUWGO2pt5CqNNbKLopuWl1epqdntT0FP/EoVz4iQSACmskuOl1s8Nm1ygnQhcAVNiL+y8mFLra\nbHaNciJ0AUCFDYrJmwmt1dXqsNk1yonQBQAVluL+i802m12jnAhdAFBhS9OLCa3V1ewQulBOhC4A\nqLDUaroiQq12jzW6UEqELgCosJnapKYnJ5Kp6er0FtRdWGSkC6VE6AKACrOt+mxNxxOZXmx1WBgV\n5UXoAoCKayS06fXSZteELpQQoQsAKi6l/ReXtgBiehElROgCgIqrz0wnc/diK6tda1BIjxIidAFA\nxdVnamq10yikX5peZKQLJUToAoCKa8zWkhnpGvST0IUyInQBQMU1Zmpqdxd0cn6h6Kasu2a7p+nJ\nCc3UJotuCnAKQhcAVNxg1KeVwGhXq9PV+TM12S66KcApCF0AUHH12X5ReQprdbXYAgglRugCgIob\nrFmVwrIRzXaPNbpQWoQuAKi4lPZfbLYZ6UJ5EboAoOIGa1alcAdjq8Nm1ygvQhcAVFx9aaSr+mt1\nNdtdRrpQWoQuAKi4LZumZFf/7sXu/KKe7y5Q04XSInQBQMVNTFj1BDa9brEwKkqO0AUACWjMVH9V\n+sG+i+cz0oWSInQBQALqs9OVr+l6cd9FCulRTiOFLtu7bD9h+5DtD61w/tdtP277Ydt/a/vSoXML\nth/Kvg6Ms/EAgNE0ZmqVXxx1aXqRkS6U1Jqhy/akpI9KulbS5ZKut335ssv+TtJcRLxe0h2S/uPQ\nuU5EXJF9XTemdgMAzkAKm16/ONJF6EI5jTLSdaWkQxFxOCK6km6XtHv4goj4fES0s6f3S7p4vM0E\nAJyLRgKF9M2lkS6mF1FOo4SuiyQ9NfT8SHZsNe+T9Nmh55ttH7R9v+13n0UbAQDnqD47reMv9LSw\nGEU3Zd202l3Z0pbNU0U3BVjRWH8ybf+8pDlJbxs6fGlEHLX9akn32n4kIr69wmv3StorSdu3bx9n\nswAgefWZmiKkEy/0Klto3uz0VJ+paWLCRTcFWNEoI11HJV0y9Pzi7NhL2P4JSb8l6bqIODk4HhFH\nsz8PS/qCpDeu9E0iYl9EzEXE3LZt20buAABgbSlses1m1yi7UULXA5J22r7M9rSkPZJechei7TdK\n+pj6gevpoeMX2N6UPd4q6a2SHh9X4wEAo1na9LrCxfSDkS6grNacXoyIeds3Srpb0qSk/RHxmO1b\nJB2MiAOSfkfSyyT9uW1J+ofsTsXXSvqY7UX1A95vRwShCwBy1khg/8VWu6t6RadOUQ0j1XRFxF2S\n7lp27Kahxz+xyuvuk/TD59JAAMC5q2d39FV5/8VWp6dLX35e0c0AVsWK9ACQgMFIV5VDV7PTY40u\nlBqhCwASUK94If3iYqjVoZAe5UboAoAE1CYn9LJNU5UNXSdemFeEqOlCqRG6ACAR9Zmamp1qFtIP\n+sVIF8qM0AUAiajP1NSq6EjXYASPJSNQZoQuAEhElTe9Xtp3kUJ6lBihCwAS0ZitVXadrkG/CF0o\nM0IXACSiPjOtVme+6Gasi+OdwfQihfQoL0IXACSiMVtTq9NVRBTdlLGjpgsbAaELABLRmKmptxBq\ndxeKbsrYNTs9nTc9qekp/llDefHTCQCJqPKm1812Tw3W6ELJEboAIBEvrkpfvWL6VqfL1CJKj9AF\nAIlY2vS6gmt1Nds9QhdKj9AFAImo9PQim11jAyB0AUAilkJXRUe6CF0oO0IXACSiMZherNhIV0To\neKfHGl0oPUIXACRic21C01MTldv0utNbUHdhkZEulB6hCwASYVuNCm56PZgubVBIj5IjdAFAQvr7\nL1Y0dDHShZIjdAFAQuoztcpNLw76Q00Xyo7QBQAJqc9MV26kq8W+i9ggCF0AkJD+ptfVCl2DdceY\nXkTZEboAICGNGWq6gKIQugAgIY3Zmjq9BZ2cXyi6KWPT6vQ0PTmhmdpk0U0BTovQBQAJqc9Wb4HU\nVqer+mxNtotuCnBahC4ASMhgLasqrdXVbPdYowsbAqELABJSxU2v2XcRGwWhCwASMth/sUrF9E32\nXcQGMVLosr3L9hO2D9n+0ArnN9n+dHb+y7Z3DJ37cHb8CdvvHF/TAQBnarCWVbNdnQVSW+0ua3Rh\nQ1gzdNmelPRRSddKulzS9bYvX3bZ+yR9PyJ+SNLvSvoP2Wsvl7RH0usk7ZL0B9n7AQAKUM+m4apU\nSN/sML2IjWGUka4rJR2KiMMR0ZV0u6Tdy67ZLelPs8d3SHqH+7eR7JZ0e0ScjIjvSDqUvR8AoABb\nNk1pwtWZXjw5v6B2d4FCemwIUyNcc5Gkp4aeH5H05tWuiYh52y1JL8+O37/stReddWsBAOdkYsKq\nz9T06YNP6Uvf/l7RzTlnC4shiYVRsTGMErpyYXuvpL2StH379oJbAwDV9a/fepm+8uSxopsxNu94\nzSt01c5tRTcDWNMooeuopEuGnl+cHVvpmiO2pyTVJT074mslSRGxT9I+SZqbm4tRGg8AOHMffMfO\nopsAJGmUmq4HJO20fZntafUL4w8su+aApBuyxz8r6d6IiOz4nuzuxssk7ZT0lfE0HQAAYONYc6Qr\nq9G6UdLdkiYl7Y+Ix2zfIulgRByQ9MeS/sz2IUnH1A9myq77jKTHJc1L+kBEVGfDLwAAgBG5PyBV\nLnNzc3Hw4MGimwEAALAm2w9GxNxa17EiPQAAQA4IXQAAADkgdAEAAOSA0AUAAJADQhcAAEAOCF0A\nAAA5IHTmoxzMAAAGb0lEQVQBAADkgNAFAACQA0IXAABADghdAAAAOSjlNkC2n5H09+v8bbZK+t46\nf4+ySrnvUtr9T7nvUtr9p+/pSrn/efX90ojYttZFpQxdebB9cJR9kqoo5b5Lafc/5b5LafefvqfZ\ndynt/pet70wvAgAA5IDQBQAAkIOUQ9e+ohtQoJT7LqXd/5T7LqXdf/qerpT7X6q+J1vTBQAAkKeU\nR7oAAAByU8nQZXuX7SdsH7L9oRXOb7L96ez8l23vGDr34ez4E7bfmWe7x2GEvv+67cdtP2z7b21f\nOnRuwfZD2deBfFt+7kbo+3tsPzPUx/cPnbvB9reyrxvybfl4jND/3x3q+zdtN4fObfTPfr/tp20/\nusp52/697O/mYdtvGjq3oT/7Efr+c1mfH7F9n+03DJ17Mjv+kO2D+bV6PEbo+9W2W0M/2zcNnTvt\n78tGMEL/f2Oo749mv+cXZuc2+md/ie3PZ/+ePWb7V1e4pny/9xFRqS9Jk5K+LenVkqYlfU3S5cuu\n+WVJt2aP90j6dPb48uz6TZIuy95nsug+jbnvb5c0mz3+pUHfs+fPFd2Hde77eyT9/gqvvVDS4ezP\nC7LHFxTdp3H3f9n1H5S0vwqffdb+fy7pTZIeXeX8uyR9VpIl/aikL1fos1+r728Z9EnStYO+Z8+f\nlLS16D6sY9+vlvTfVjh+Rr8vZf1aq//Lrv0pSfdW6LN/laQ3ZY+3SPrmCv/NL93vfRVHuq6UdCgi\nDkdEV9LtknYvu2a3pD/NHt8h6R22nR2/PSJORsR3JB3K3m+jWLPvEfH5iGhnT++XdHHObVwvo3zu\nq3mnpHsi4lhEfF/SPZJ2rVM718uZ9v96Sbfl0rIcRMQXJR07zSW7JX0i+u6X1LD9KlXgs1+r7xFx\nX9Y3qVq/86N87qs5l/9elMYZ9r9qv/PfjYivZo9PSPq6pIuWXVa63/sqhq6LJD019PyITv0glq6J\niHlJLUkvH/G1ZXam7X+f+v8XMLDZ9kHb99t+93o0cB2N2vefyYaZ77B9yRm+tsxG7kM2pXyZpHuH\nDm/kz34Uq/39VOGzPxPLf+dD0udsP2h7b0FtWm8/Zvtrtj9r+3XZsaQ+d9uz6oeKvxg6XJnP3v0S\noTdK+vKyU6X7vZ/K45ugfGz/vKQ5SW8bOnxpRBy1/WpJ99p+JCK+XUwL18VfS7otIk7a/jfqj3b+\neMFtKsIeSXdExMLQsap/9smz/Xb1Q9dVQ4evyj73V0i6x/Y3stGTqviq+j/bz9l+l6S/krSz4DYV\n4ackfSkihkfFKvHZ236Z+mHy1yLieNHtWUsVR7qOSrpk6PnF2bEVr7E9Jaku6dkRX1tmI7Xf9k9I\n+i1J10XEycHxiDia/XlY0hfU/z+HjWLNvkfEs0P9/SNJPzLqazeAM+nDHi2bZtjgn/0oVvv7qcJn\nvybbr1f/Z353RDw7OD70uT8t6U5trHKKNUXE8Yh4Lnt8l6Sa7a1K5HMfcrrf+Q372duuqR+4PhkR\nf7nCJeX7vc+jcCzPL/VH7w6rP30yKJB83bJrPqCXFtJ/Jnv8Or20kP6wNlYh/Sh9f6P6BaQ7lx2/\nQNKm7PFWSd/SBiosHbHvrxp6/NOS7s8eXyjpO9nfwQXZ4wuL7tO4+59d9xr1C2hdlc9+qB87tHpB\n9b/QSwtqv1KVz36Evm9Xvz71LcuOnydpy9Dj+yTtKrovY+77Dwx+1tUPFf+Q/QyM9PuyEb5O1//s\nfF39uq/zqvTZZ5/jJyT959NcU7rf+8pNL0bEvO0bJd2t/h0q+yPiMdu3SDoYEQck/bGkP7N9SP0f\nxj3Zax+z/RlJj0ual/SBeOkUTKmN2PffkfQySX/ev3dA/xAR10l6raSP2V5UfwT0tyPi8UI6chZG\n7Puv2L5O/c/2mPp3Myoijtn+iKQHsre7JV46DF96I/Zf6v+s3x7Zf3kyG/qzlyTbt6l/p9pW20ck\n3SypJkkRcauku9S/k+mQpLak92bnNvxnP0Lfb1K/ZvUPst/5+ehvAPxKSXdmx6YkfSoi/ib3DpyD\nEfr+s5J+yfa8pI6kPdnP/oq/LwV04ZyM0H+p/z+Yn4uI54deuuE/e0lvlfQLkh6x/VB27DfV/5+M\n0v7esyI9AABADqpY0wUAAFA6hC4AAIAcELoAAAByQOgCAADIAaELAAAgB4QuAACAHBC6AAAAckDo\nAgAAyMH/B3HosGGsM9tDAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x106d62828>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "thetas = np.linspace(0.0, 2.0, num=50)\n",
    "plt.plot(thetas, [loss(theta,train) for theta in thetas])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We notice that there exist a set of optimal parameters for which the loss is zero and we achieve perfect prediction accuracy on the training set. We can find one such optimal parameter by sheer brute force: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.2653061224489794"
      ]
     },
     "execution_count": 7,
     "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": {},
   "source": [
    "### Prediction\n",
    "Now that we have a trained model we can use it to predict translations on a test set. This amounts to finding \n",
    "\n",
    "$$\\y'_{\\param}=\\argmax_\\y s_\\param(\\x,\\y).$$ \n",
    "\n",
    "Notice that we solved this problem already within the calculation of the loss. This is a common pattern in structured prediction: when minimising a training loss we often have to solve the prediction problem in the inner loop. In many cases this is the core bottleneck of computation. \n",
    "\n",
    "For completeness, we show how one can find the highest scoring German sentence $\\y$ for a given English sentence $\\x$ but note that this code can already be found the in loss code above. In practice one would try to reuse the prediction code below in the loss function above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style=\"font-size:large;\"><tr><td style='padding:5px'>Yesterday I ate a red apple</td> <td style='padding:5px'>Gestern aß ich einen roten Apfel</td><tr><tr><td style='padding:5px'>Yesterday I ate a red apply with a friend</td> <td style='padding:5px'>Gestern aß ich einen roten Apfel mit einem Freund</td><tr></table>"
      ],
      "text/plain": [
       "<statnlpbook.util.Table at 0x106d62eb8>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def predict(theta, x):\n",
    "    \"\"\"Find the most compatible output sentence given the input sentence `x` and parameter `theta`\"\"\"\n",
    "    max_score = -math.inf\n",
    "    result = None\n",
    "    for y_guess in y_space:\n",
    "        score = s(theta,x,y_guess)\n",
    "        if score > max_score:\n",
    "            result = y_guess\n",
    "            max_score = score\n",
    "    return result\n",
    "\n",
    "# We can now predict the test set translation:\n",
    "util.Table([(x,predict(theta_star, x)) for x,_ in test])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### In Practice\n",
    "In practice one needs to extend the above approach along several axes to be useful:\n",
    "\n",
    "1. Usually the feature representations and scoring functions are more elaborate. They may involve several non-linear transformations of both input and output. \n",
    "\n",
    "1. The space of parameters is usually multi-dimensional (with possibly millions of dimensions). It is hence impossible to exhaustively search through this space as we have done above. Instead you will find numeric optimisation algorithms, often variants of Stochastic Gradient Descent. \n",
    "\n",
    "1. The size of the output space is often exponentional with respect to the input problem size. For example, in machine translation we have to search through *all* German sentences, not just 4. This means that we cannot exhaustively search this space either. Dynamic Programming, Greedy algorithms and integer linear programming are common approaches to solve this issue.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Learn to Predict\n",
    "\n",
    "The above recipe can also be described as \"learn how to score\". Here we learn a scoring function, and then find the highest scoring solution using a discrete search algorithm. An alternative approach is to learn a prediction or search  *algorithm* directly, without a scoring function. In this setting, structured prediction is an instance of \"learning programs\" in the sense that a model predicts a sequence of actions or steps. We will see an instance of this approach in the [dependency parsing](/notebooks/chapters/Transition-based%20dependency%20parsing.ipynb) chapter. As we are learning to choose the right actions, this approach is tightly connected to reinforcement learning, in particular, [imitation learning](https://www.cs.cmu.edu/~sross1/publications/Ross-AIStats11-NoRegret.pdf).    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Background Reading\n",
    "\n",
    "* Noah Smith, [Linguistic Structure Prediction](http://www.cs.cmu.edu/~nasmith/LSP/). Notice that his book can be downloaded for free when logging in through UCL. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}