2a_recurrent_nets.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "accelerator": "GPU",
    "colab": {
      "name": "Khipu Practical 2A: Recurrent Neural Networks",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python2",
      "display_name": "Python 2"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y1gy_u-elJDp",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/khipu-ai/practicals-2019/blob/master/2a_recurrent_nets.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "9jDBz0IbW3Xy"
      },
      "source": [
        "# Practical 2A: Recurrent Neural Networks (RNNs)\n",
        "\n",
        "© Deep Learning Indaba. Apache License 2.0.\n",
        "\n",
        "Adapted for Khipu by Diego de Las Casas and José Lezama"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "-0F3Ao8BKa0g"
      },
      "source": [
        "## Introduction\n",
        "\n",
        "Feedforward models (eg deep MLPs and ConvNets) map fixed-size input-data (vectors of a fixed dimensionality) to their output labels. They're very powerful and have been successfully used for many tasks. However, a lot of data is not in the form of fixed-size vectors, but exists in the form of **sequences**. Language is one good example, where sentences are sequences of words. In some way, almost any data types can be considered as a sequence (for instance an image consists of a sequence of pixels, speech a sequence of phonemes, and so forth). \n",
        "\n",
        "Recurrent neural networks (**RNNs**) were designed to be able to handle sequential data, and in this practical we will take a closer look at RNNs and then build a model that can generate English sentences in the style of Shakespeare, or Spanish in the style of Don Quijote!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "otAAvBVFSZy8"
      },
      "source": [
        "## Learning Objectives\n",
        "* Understand how RNNs model sequential data.\n",
        "* Understand how the vanilla RNN is a generalization of feedforward models to incorporate sequential dependencies.\n",
        "* Understand the issues involved when training RNNs.\n",
        "* Know how to implement an RNN for time-series estimation (**regression**) and an RNN language model (character-level **classification**) in Tensorflow using Keras."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "THe6CRwAslUz"
      },
      "source": [
        "**IMPORTANT: Please fill out the exit ticket form before you leave the practical: https://forms.gle/uzjavhQ138g9H1Wq8**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "gfKcEFUxa--9"
      },
      "source": [
        "## Imports"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "h8glXxcyew17",
        "colab": {}
      },
      "source": [
        "#@title Imports (RUN ME!) { display-mode: \"form\" }\n",
        "\n",
        "#!pip install tensorflow-gpu==2.0.0-beta0 > /dev/null 2>&1\n",
        "#!pip -q install pydot_ng > /dev/null 2>&1\n",
        "#!pip -q install grapfrffhviz > /dev/null 2>&1\n",
        "#!apt install graphviz > /dev/null 2>&1\n",
        "\n",
        "from __future__ import print_function\n",
        "\n",
        "import numpy as np\n",
        "import tensorflow as tf\n",
        "import math\n",
        "import random\n",
        "import ssl\n",
        "import sys\n",
        "import urllib\n",
        "\n",
        "from IPython import display\n",
        "import matplotlib.pyplot as plt\n",
        "%matplotlib inline\n",
        "\n",
        "# We need to pin this colab to python2 for now to avoid \n",
        "# issues with string handling.\n",
        "import six\n",
        "assert six.PY2, \"This colab needs to be run in a Python2 kernel.\""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "yVL1OwL7aH8c"
      },
      "source": [
        "##From Feedforward to Recurrent Models\n",
        "\n",
        "### Intuition\n",
        "RNNs generalize feedforward networks (FFNs) to be able to work with sequential data. Recall that FFNs take an input (e.g. an image) and immediately produce an output (e.g. a digit class), operating on all elements of the input simultaneously. \n",
        "\n",
        "Here's an example of a function that computes the output of an FNN on an input `x` (the `W` and `b` arguments represent the weight and bias arrays):\n",
        "\n",
        "```python\n",
        "def ffn_forward(x, W_xh, W_ho, b_hid, b_out):\n",
        "    # Compute activations on the hidden layer.\n",
        "    hidden_layer = np.tanh(np.dot(W_xh, x) + b_hid)\n",
        "    # Compute the (linear) output layer activations.\n",
        "    output = np.dot(W_ho, hidden_layer) + b_out\n",
        "    return output\n",
        "```\n",
        "\n",
        "RNNs, on the other hand, consider the data sequentially, and can remember what they have seen earlier in the sequence to help interpret or contextualize elements from later in the sequence when making predictions.\n",
        "\n",
        "Here is a function that illustrates the idea. It takes the input sequence, and an initial state for the RNN, and then loops over the elements of the sequence, calculating new states for each one. \n",
        "\n",
        "```python\n",
        "def rnn_forward(data_sequence, initial_state):\n",
        "    state = initial_state  # the variable state is updated at every time-step\n",
        "    all_ys = [] # Used to save all predictions\n",
        "    for x in data_sequence:\n",
        "      # rnn_cell is a function (not shown) that it takes the current input x_t \n",
        "      # and the previous state h, and produces an output y_t and a new state h.\n",
        "      y, new_state = rnn_cell(x, state)\n",
        "      all_ys.append(y)\n",
        "      # Update state for the next time-step\n",
        "      state = new_state\n",
        "    return all_ys\n",
        "```\n",
        "\n",
        "To understand the distinction between FFNs and RNNs, imagine we want to label words as the part-of-speech categories that they belong to: E.g. for the input sentence \"I want a duck\" and \"He had to duck\", we want our model to predict that duck is a `Noun` in the first sentence and a `Verb` in the second. To do this successfully, the model needs to be aware of the surrounding context. However, if we feed a FFN model only one word at a time, how could it know the difference? If we want to feed it all the words at once, how do we deal with the fact that sentences are of different lengths?\n",
        "\n",
        "RNNs solve this issue by processing the sentence word-by-word, and maintaining an internal **state** summarizing what it has seen so far. This applies not only to words, but also to phonemes in speech, or even, as we will see, elements of a time-series."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "zUqww79L6Ot-"
      },
      "source": [
        "### Unrolling the network\n",
        "\n",
        "Imagine we are trying to classify a sequence $X = (x_1, x_2, \\ldots, x_T)$ into labels $y$ (for now, let's keep it abstract). After running the `rnn_forward()` function of our RNN defined above on $X$, we would have a list of internal states and outputs of the model at each sequence position. This process is called **unrolling or unfolding in time**, because you can think of it as unrolling the *computations* defined by the RNN loop over the inputs at each position of the sequence.  RNNs are often used to model **time series data** (which we will do in this practical), and therefore these positions are referred to as **time-steps**, and hence we call this process \"unrolling over time\". See the visualization below:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "XBKHPIp19sfk"
      },
      "source": [
        "<center><img src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAABPMAAAGQCAMAAAD85tXPAAAAYFBMVEUAAAD///8gICHT09W9vsCsrrGnqayytLYAcbxDls272e2AuN3Z6vXv9vqOkJHR09TFx8jExsdbXFyen5/7+/v29vbv7+/k5OTf39/Z2dnPz8/Ly8uvr698fHw6OjoQEBBfQ4o8AAAACXBIWXMAAA7DAAAOwwHHb6hkAAAgAElEQVR4nO2di3akuK6GKcLu7rmRE0hRFCng/d/yLO4Gc5EwNnbxf7P2nukUSdyW/SNLsu3dAADgOkDzAABXApoHALgS0DwAwJWA5gEArgQ0DwBwJaB5AIArAc0DAFwJaB4A4EpA8wAAVwKaBwC4EtA8AMCVgOYBAK4ENA8AcCWgeQCAKwHNAwBcCWgeAOBKHKR5cRHlYZ5P/hcVUSw/KD9XSD8PAAC0cJDm5d4COelB6ecBAAA0DwAAFDlsbVshaVlZSGtbX3rIL7C2BQAY4lgXKw1LQcyiTHrgdrsloSB3YZBIDwAAgDaOXlYmgx/nSx+2dOvbKJU+AgAArRweSksGT+8lfdg+Un9azHqBAACgk+PTB1kveuWCqr1qLxCLWgCAeTSkTONhdTura0mV6yhmPwIAAL3oKBMZkhSzCdlK8kpIHgDgDLSUxg1FeJH02S1aWfUCAIBe9JQDD5V64fSjeuUbSN8BAAAm0KN5QsXKJHlb5y+mhcoAAGAITdu+lpK39den+9EAAMAUura6vob9Z0K6oi7em4nxAQCAGbRt75+rWEGVCgDgZPQdaRLJydtosWYPAACMoPEYpyF52wbwUKUCADgbjZonJG/rRG292oXkAQDOROdxnePkbYwqFQDA6Wg9ojgbkrcpqlQAABag91j2IXlboEoFAGABmq+iGF1/sXiIKLCVuMhHN9RFwqkRUSHcXhdJN9zpI4ui0c15hXAgd/XR8FlhcmFhZV+5hCm76r5+JxIkD1UqziFdcTK8t9LJJ0snxB6PfI/UcOD25LoVkysLK/vKJUzZVbfmJSvHDQDrkW5sGnyX1+QTcxn5aNqoYRAnkw9Mjjkr+8olTNlV+zWL6XBWPE5TcY4gCIJcuOIkHt68wl1OfhQGBo2bBUEQDu/SMhck5DXUChR5YPSGKSv7yiVM2VX/1bJLxw0AZ+gWHZOTXtvhGZ2zUuvzY2MFCTvFOSmSYmVfuYR+uxq4TntYpiOi5yjtqmNy7HU9j/3TnJbOdxp/tR5t5YlJAiv7yiW021W/5gkRPWRuHaW9zG7suyRnV1wWc/5A9cXozHernX3lErrtql/zRuksVOi5SRuEH83a6Fx/qg8Vj16k8fnaYmVfuYRuu2rXvMon9ZG8dZ1IevfG5wdoQ0ldquDx6dpiZV+5hGa76ta8sM5dCMlbvO2cpF2xDRFZK6Zx+y7t22GF5FnaVy6h166aNa+78QfJW9eJx+9eO6ZxOs4X2CF5lvaVS+i1q17Nq6VuOEhqJrgLXGEUWbZlGueiutgieZb2lUtotatWzUuFbJVw0TdEz0Xa+ET97rVnGjc1wGVqleRZ2lcuodOuOjWvPjR0dDA8krcOM0SWLZrGWb8KskjyLO0rl9BpV52aN77xJ5HOigdu0UWWrZrG7SootEryLO0rl9BoV42aN73xZ3pWPHCM9t3rWzWN21FV2iV5dvaVS2i0qz7NC6Uk7ZC8xcESTtLFZK2axoGdL1Ir+8ol9NlV7/22kx3VwkXfGAku4ov5SFuI7AyYWNlXLqHNrro0b6hSERHOikfy1kECVhLq5RvZXy2VAC+QxFF1Q4Ef5UYON6H2VRrnzQEEUZhKH14Zql3ZaNK8dOH6iyF5W0ifAftpQ/MU0YgLU2dKhBR1SaNa7vKoqI9mM/DKJfVVUHhllAdBEFdTI4LqCZDsugM9mlfnaGfbOiRvZz8GVtP56Rt15UkQRqUxG/dh4rVlZO6VeSsoQbXqLL+kRw6G0ldJ7hW9JmYnH4JlGyS77kGP5hWLq1cheYvjBlwjprywmiKDIjQVYxsyY8teZVKI5xA1Y1BzRJnSV0kxmgR5V4ULiHbdhxbNi1Zeb0Lydt3rB7bxqnJP8qEhE+IwD7L2BgMDFq6iKLF8EMeYYhxaTnXMpDGkvqpOmBLaHKz+HS4Gwa7TSzImLL5rdGieXKUiIlz0vfgMsJCsrCxGjSzXE1i/01L5bLF8EMeYfDr+68d1LiNJfZVN2hwgzt1DsWtcZ37yuLqIJKifjF71f+eRb1jz4o0BNXj9S4MBWEgzjaVDQ5aoX3wLnx1HOzWmB3GMqT70R9MmX19zKkPrq3ziBYbGQqDWQ7JrJIY/v6rnEuGzpV7XoXnZQsp2YLggYz7mByykm8Yb796eYnGoHkg3NYatSnM/O5SWsvnyRDoCYl8Fk3ZFG87CdaDZtRT7NZ/Y2DeoeSEhVDdUrCy2C9jFMI1nj+6W8Q1Yd5ganbrMpgDqj0Y+Z6TVoyL31auIwuGtX/s0S2HwS0Gz62s0vqKJRfPlMOrBmhd0d9pJn4gIwUeInhOMtsqvR5YbTKQwRtvPh4M4JGSFK3QOPXZftUSLDs3FINo1Gr0fpu9YQ5qXhbR7L5JhcYsyTCeIxwLWmnnNcgZSGNXUEEZ5O6hm1oZJ7vkj0UlXFpzK8Puq/etIynxRqHb1xc6q37FizWW4bN9jNC/O82J0v1mVUJFb2Tw6ebCujs/zHNpnLfFkzC2/e3ty7SmMamqMRn17EAdhcagznLejr5rncBtkA9Wu2WgZUb9jxUfyZWVb/oTDVMZW1rezj3prVUzgZGLJb1+LLDdEulMY06nRb3Dd/q0p0fPaw56+qhtfel6JglWGXaPRK3WawjhJ8+YH3+yj0DyLmZMv4ejueXSnMOJSLnVq1WVTOTRW5+3qq1tW7002sQfYevbadZrCWOMgzfOLaPJPsdCEyCulZ6MiKqF5dpIWcy+k15orrz+F0USEp5rapsa2qj71lYTs6Kus24uJZa2SXTnvWO13egOXSfJy1gnvTkJcWrHpTWHE/qxMdOUA8+rSoU3y9vVVvXGgOlSljNbm9CVQsCvnHQvNA0skr6icn69pH6FYSLtr3IUR5P78HEj6ss9iZc1Q7wVf+XwnCn1VkxVXP1RFya6sdyw0D8wSFcMJOJN3bzaKyfpFUUhvWE27MOJxdcDoNxSl8ElZFMXcUqeeP4c7VGp91ZDOHrJ7EZTtynrHQvPALJE3Qnz3xt4U6f1bzCxRDiAf/14xUZdKjZr5/ZXPpSE7qtZX4g9Z+vDNUbUrK4UBzQPzrAy0XBqGkuPk6UlhTJL+oj8QSI2Sf/+r1ODkKfdVSzz9G10IRbsyywSgeWCWQCxjz4Jk9KdxiXsgeSe6UhiZ+JvSIB39KZg8KolL7nnFYnG+Ckp91X+yqojvjZpdue9YaB44HjMHSfFIfbsLQhrNW5REsALvHQvNA8czV5p7Mq9SdPKys7UliEZHJPeRP2jeHnjvWGgeOB5NKQwFcq8UakjSszfzN7twR2naJvInPQkI8N6x6GRwPJpSGLtJC68Qlz758qEbZmgEblTJ5y/lJMEmvJ2ORjTvUfEtfRm8KYbuwiDzKsuRvCTlwiGexmiOMRW7qFna4nChXUhO8ypGNO+nYi7dAt6S0K5VWjR28iova34fmDnqerKRr6n1GNM3p44U0D13aB44HKtSGFW+thDxLSgJCabHxeu+leitiXnvWGgeOJr6+EtbNO8lbl3qOF9conFxdAwvTwHmOxaaBw4jqw+8bovqm+Ovz85kyPsgLKkIiTy/j0DVu4CXN9CDJdLmNtvaplF9zy1FZaB54DDySumEUxHPrwKev+r+7AxGTVWhF+WvryCsFQ93PO6g8EpxvJW0oAU0D4BzSMP6tVAWUYx8rUGgeQCAKwHNAwBcCWgeAOBKQPMAAFcCmgcAuBLQPADAlYDmAQCuBDQP8HhUxnxY2GlJPcykL9uAtX3mCofaFpoHeFg7f+/QvLflUNtC8wAP+Hl8oHmKwM8DJwI/jw80TxH4eeBE4OfxgeYpAj8PnAj8PD7QPEXg54ETgZ/HB5qnCPw8cCLw8/hA8xSBnwdOBH4eH2ieIvDzwInAz+MDzVMEfh44Efh5fKB5isDPAycCP48PNE8R+HngRODn8YHmKQI/D5wI/Dw+0DxF4OeBE4Gfxweapwj8PHAi8PP4QPMUgZ8HTgR+Hh9oniLw88CJwM/jA81TBH4eOBH4eXygeYrAzwMnAj+PDzRPEfh54ETg5/GB5ikCPw+cCPw8PtA8RZzx8+7df4w071t6DrgE/Dw+0DxFXPHzkl7mRM27Zx9QPZeBn8cHmqeII35eOuicoHlV4yF6LgM/jw80TxFH/Lx0ELpB876zn5+fDJrnMPDz+EDzFHElnvfRK12ved/11+7So8Ad4OfxgeYp4ko8rxa47C5o3vAV4Czw8/hA8xRxJm/be3Wt5sHLewfg5/GB5iniTn1e59e1midE+ICzwM/jA81TxKF9GN8/dZq20bwnJO8dgJ/HB5qniEv7MO5VnrZe0v58QPLeAvh5fKB5iji137ZpbAfM7j7w8/hA8xRxa7+tKHqp9ClwDvh5fKB5ijh2rkoCyXsr4OfxgeYp4tq5Kgkk752An8cHmqeIc+fnNaL3IX0duMP3RzdlR/P38Tx9H2HSbd8e+QJ3C0rf7e0zV9BjWyPn5z1wsIDjVJWWbc5dnL+P8+36+Pl5Nv8l+gL37Pz9Pvb2mStosq0RzbulMLPbPIZCI2H+WrBkuw9RE8EX+LZhYWFtn7mCLtua0bzbA5LnNsMemmHSPmyI0iZ9IwZfwJJ93db2mStosq0hzQOOM+yV7udvU29+fjyvmxi9L2DLvm57+8wV9NgWmgdI9O/Xbv7W0/fTgunbuVOdL2DP6T329pkraLEtNA/Q6N6w7fy1yGNJmxZ1voBF+7rt7TNX0GFbaB4g0p5x3cxfqw68bryB1hew6vQee/vMFTTYdp/mBb80E0i/EpxOPfA+6nGX1msMa06MqF//dcN+LDu9x94+c4XjbQvNA2TqtVmPRQdef3+KDbPq9B5r+8wVjrctNA/QEQ+MsMpjaQJnLXaVgljbZ65wuG2heYDBcGCEZUchfj8tlTyL+8wVjrYtNA9w6CewbVsJ+jWkfQW/1vaZKxxsWwXN+1+ghf9B82wmsdVjaSfGU/rgfKztM1c41rYKmvf7Uwu/oXlWY+/5efZWv2GTrSKH2haaB5iktm4Yvdtb8Gttn7nCkbaF5gEuqY3rx4qHvXscrO0zVzjQttA8AMCVgOYBAK4ENA8AcCWgeQCAKwHNAzc9hZYCO3OW0s+xpF23Wyr9qKORfuWbcaJtoXngJm2DOZrPfX1sa7tutw/pRx2N9CvfjBNtC80D+sffzitbpJ9jSbtut0/pRx2N9CvfjBNtC80D0Dw28PNUkf7CR7NsW2gegOaxgZ+nivQXPppl20LzQDP+/vdbC/XPXo6trGJruzo/T/qhh/C/62jeObaF5oFm/AWSJQ6h/tnL79xVbG1X5+dJP/QQguto3jm2heYBaB6bD2ieItfRvDAqSs/zi1D6pAeaZxxoHhf4eapcRPO+otLr8BcHDDTPONrH33JsZRVb2wU/T50TbWtQ8/Ja8cooj4rq30sjBppnHPh5XODnqXIFP++3X3t41aL2Vy1+hfRI+yA0zzTQPC7w81S5gOY1Oud/Vf/dqJ/3JT1UA80zDjSPC/w8Vd5f80TJC9uQXiw9VQPNMw7ieVzg56ny9vG8r9q1KxvPLm81b+EvDM0zDvw8LvDzVHl7P68QHbtW83zpqQZonnGgeVzg56ny7poXe2LSIlhd2kLzzAPN4wI/T5V317ymLK8fImFVlrxYlQzNMw7ieVzg56ny5vG8WFrLrv1loXnG2Tn+vuI8j8KNmb/xzl1l/7wI4jzKw7VvPcnPI/QZNG+VX2GUR/FC0QfJtiY0L6o1L5e+Pg80zzh7xt9X3pYceeWiy04Yf6vsnBdB1DWtWAqgnBPPo/UZNG+ZOOo2chUr8rNhWxOa1xia+jg0zzj88SduI/S8SPp8YGP8rbJrXvyOhJYtv2nN+3nUPoPmLREXQgeWr4WnbNC8r6aJ0tcXgOYZhz3+mhJLPw/alPyispiP50Vt077aAqklT894PI/cZ9C8eb4axYvCz8/X2qYGG+J546ztJtA843DHnxCsiLZeaBvv3FX2zotm5Vis+lOm/Tx6n0HzZvlVv8L8yrv7KpV8eAOal6+OPQlonnGY40+Yvr/bhcby9N8Yf6uw50Vb+/7rUyh9lx5Sb9cOP4/RZ9C8OcSdXO0Sd9GN2rCtAc3jpTCgeebhjb/Gnk0QvhOWpRWkYc0TJK+bGHo0j+vncfoMmjfDb0Hy2to3mzXPX7WwBDTPOKzxF4pue7QuLIbjeaO364YzYDSex+ozaN4Mvpi2IOWnlm1L0bx7Mv3KDs0j//Uup3n//PWv9DWzcMZfE0tpt05350WsBC423rmrMOfFOHAcrXtTJv08Xp9B82Tykcg1r7NyUYA2bEvQvHv2MxU9luatv9UkLqd5//7589c/0ldNwhl/k0iFLyw5ZtkYf6vs8QX6MNnvdWUxGc/j9Rk0T6KxZd9l4bqbp6559+znZyp6HM1jpm0vuLb968+fP3/+OdHZY4y/tvBomLB5ES0PPqOaF04G2ldUREtenlE/j9ln0DyJaPL++hUV+Yr8bNh2W/O+P34k0eNoXrj+vpW4nub9/afmr7+lTwzBGH/MJLzJeF6x8fY/rl1MP4/ZZ9A8iZIXHtuwLWFtOyN6HM2bavQWF8xh/PWnVb1//pM+MwFj/BVCApI+/pbfuavwNK+JoSwuGQ9sF9PPY/YZNG8Kd6m4YVtKDuP7ORU9kub9imuaKEsed2yNlAtq3j9/ek5Z4jLGHzM4a1DzmBPDYDyP2WfQvClct2nDtrRalXQieiTN6/ZTT9galRfUvP/+CJywxKWPvxfzjWtQ85grSHN+HrfPoHlTuIuLDdsS6/Mmnh5J8yS126iqablifd4/f0aqZ3qJSx9/0zwBcfwtx1ZW2RHnJpe+m4vncfsMmjdlnJDfZsO21JrksadH0bxfRUOjdEUP1rYy//6ZYHaJSx9/OU9YTPp5o/sH9LaL5+dx+wyaN4UbUNmwLXkfRu3ppe0fGDmMnNvgS+7D+GsqekaXuPTxx05hmNO8kpXCMBjP4/YZNG9qqqY6T/r6Ihu2pe89SwXRY2seYzV0Sc37W9I8k0tcruaRnSmTmsd8t5rz87h9Bs2bwE3bHqZ5SfIxiB5D8woFzUuS5C415D2RHb26UNmMs0cff+y0rbF4nnwBwTrm4nncPoPmTWAHVDZsS6hJTh7PWu4aatFjaJ7PbbCgefUvzJ6PCwjfP5LeGVziksdfswdo8eS3OTbeuatwNI9b+m7Mz2P3GTRvAq/YXNnPSx6C3A2ix9A8j7sammpeo3vSMQdvxn+S2g2ypz2fQR5/7FWGOc07uIZrA4afx+4zaN4EdkBlw7Zrmnd/ZFPBq7hzNK+JP9K3jcxrXiV7j2+pge/EkqNnwtkjjz+usBjUPO7EMObnsfsMmjeBHVDZsO2y5iVPSe1+uoIVuuaF7AYvaN7Pz89bq95cFkOM7OnMZzA1j1OqwoqbTQ8t42hek7al37ms0i6Wn8fuM5bmuRH3+X5IX6Lblh9Q2bDtkubdU0nsGner7mO65kXs1dCy5v1k0th7I+azGIOv95c+1dsef1FTXdkIi9/XWhK8l413roh0aBlpXiyUgW7Vhqi0i+bn7e0zjuYl7YS0m++Pn3TqrxBsO6rwLekVvjv9vNGqNvt4PJIkHSSPoXnrF7HMMa5VSR6jiOLzfV29DUfvj8ZT9rbHn7SbxqPadWP8CciHllE0L5YaRYsgq7SL5udJTSL2GUPzkmFK2kw1gz8mM5dg21zqO+KiccO2s5r3LSxr03ZFWUte13C65vmKmteYNu0l2IXX2k42HD2NS9zN8fdbGncNhELbjfEn8C0UQxHbNQRPJLaKk1XaRfLzdvcZQ/NqObZ/Sjx+ZNEj2DaS+q5me9G4Yds5zbv3gvfRhdAau/deFl3zyHOjZ0bzqoBAr3pvK3prWQzB2dOQxd0cf1/NmTjti7c/Iicm7HrYiK2IfD8n4kLRvN9NS9prbYemSQ8e2C6Sn7e7z1hr23payNEyy0hk0aOsbcWDmQrywUx74nlJv5Ds5eU+edWRNS9oLM65FW9W88Tl9rsG9VbKVTQvcanx5Gb+MjYBcfOj6XiYsesZuGeZ7mwXJ2/L7zNWDuMunfNmJYm0RqPblu82bdhW1rxO8oSEgfQ2IWteTFyBCyxpXmveoz29f/+2Bsritl3iHuvsUcdfoVvzGnHplxMMzWPHUFTaxcnb8vuMV6vSrMDc8PTEmUu2bRsjOHC/o6R5neQJiZZa8jKxW8max95tu6J5bVzg4AAGbUVpHYeW7PE0j1Wqwq2DG4WNGZrHnhgq7eL4efw+Y9bnfX9KK28bmYYeybbd4TZt2HaqeXd5AfmQdYaseezdtqua1wnyNAekgqOad+gRBNTx5+3VvOXYioQY76ZrXjsxOPfiK7SL4+fx+4xbkzyXY7GQ+1hXyLbdEVDZsO1E874zyZNq3nBj14qpeaxZsqZ5negdaGBnNe/AJS5x/H3xVxk79jskw3ijax6/9F2lXQw/b0ef8fdhSOFGK6k9vV70yLblV/gy/bynHDFLZxwrsubx44/rmteJ3nFBW5c176glLnH87Vhl7Nnj9eijyXTNi9jOgEq7GH7ejj7bsfdsGm60k9FlYmTb7nCbNmw71rw5Rfn+lIuoqZrXvuVe0gcrrGteG9P7PMy+bmveMUtc4vhrVhmsU1W68Xd/MHh2Sw2u5nHKQFXaxfDzdvRZq3nSr18jOzrkQ2alUTKCupBtW2rWvGbLwyQJNLNZjqp5ezyDDc1rXVG5TTtxXfOqJa5qHxDH345VRhdbefywyRKG5vFL31XaxfDzdvRZq3kL293XOEP0VpqzRMoYc7sCKpx4XjMCntJDElTN2+MZbGleExbIjjKv85p3wPKWOP74+wj7d+4Obfn5edA1b289w752Mfy8HX22X/O2Re8x4yvc587ueFCjR1IbCKQMzdvjNnH8vKa1hEoQqubt8Qw2z4Z/dAPvEBzXvENOUiaOvx2rDCVtScia94tf+q7SLoaft6PPVDRvfe5+hGEYTsTsv19hGE6nW/VgTJthUhsIPBmaF+nVvCaaR/mrUjVvj2ewqXnfhzp6LmveUeUqxPG3J227X1uyu4Earn3tYvh5O/pM29r2EdaMHwrqr43Xdv/VX4vXBbRFasQ2rLXtjgpfjuY10bz1fms7iqh5ezyD7TuAGm0+KHXrruYdV5ZMG3+tsJBvFmtoxCGRwtkrNLOdk8PYXcO1r110P29Pn7Wax2oaRfJaeRvr2735Wjz3IKn6RWrKCs35dA/GmNvnNtHjeXehRRtQNW+PZ7CteY2jRwg7UnBV847cfkYbf+GetO2OmpBhbyZZ846v4ZpB3DNK9fP29NneWhWpumLKr0bK/k/8cuv7haNHXzMPHsC3uDeYalv2fTosPy8dXmNbEDVvV0EX4a5HRks3+ecva5B0bZGDr4GkjT9+DdynqZrk42u4ZEY1yVQ/b0+f8TVPPvdllt+NlI3+0smcn9c+uOwp7eI+2rVPta2GOnhB8z7p3hNR88I9s4SgefcjF7f2sKRwUw6/HoM2/nalbdnaIh47RNa8HaXvKu2i+3l7+oy994woeU0KIwzHvkI849J9Ng8eO8GaDbfcvWe7Aiobth0075shJETN2+UZUO70/jhwcWsNxFX2wWeq3Mjjb1falruvddcZA7/5aVuldtH9vD19xj1jgL7d9veM9/aoRO/XZM0USP6gMhPJ018Hv2zbQfOk015WIGrennM4SJrXnFMvfdltKGtbPcfD08bfrrTtnjObPrhnSWmo4VptF93P29Nne86SIrpkj/+TJ/j9+X+yYCb/93msl/eYnuhMtO3+Ovhl2w6ax9ERoubt8gwomsfRZ1f4VxI4CV13PpLG369daVsjZ4buWU+otIvs5+3qM96ZoRzJOw9xrzLLtgp18It/2UHzOCfS0DRvx2l/RM3jrMNdYdPN07CobSGNP/7RJTUb40/keyotPM07tIZrtV1kP29Xn3E0b3xWibXUkvfJPRv+c9emQo7m0StVqJrXllAzG0zRvJsb1wBw2DgZXtudZzfq+NtTHMqKm8mBKarmaajhWm0X2c/b1WecO4DcWO/svAPoU6kOftm2veZ9c7pvS/Pqy0/aK0c9r8hJt7K0kDTv+XZJjLUMxl86Lv4RII2/Hce/fvLuF8um7zGq5pX8tK1Su8h+3q4+e7+7Hp8zJ13RbPtqFGRFaubYsG2veawQ2ZbmeTNQwy0kzXu8neZJQicsavXd5t1AGn97ikOZd2dPpYWoebrPMpXaRfbzdvUZZ237cCKqvfNO790BlQ3b9prXuMnS5/NsaN5LVjz6246uee+UuF1083TlLURI429f2paVK7hPpIWoedrPMp22i+zn7eozVg7j4UQib+Y4Oppt9wVUNmzba97jQM37Vfh5NPqnKArq246keQmntS6wkMHQvKhtoYy/NiG18ZTMRmxlFaLm7bmCUqldVD9vX5/t2HvmIDTb7guobNh2rHnL2jhmQ/OUIGkeyyt1gPlClb91L2pbKONvlzO1a18rr12aarg2oPl5+/oMmjewq8KX5+dRI2Sna967+Xkzbt4hJ+PRoIy/fbttjWiejhquDWh+3r4+g+YN7AuobNjWUc17Mz/vv6nm/fWPyZoruuZxd9sa0bxdmQITft6+PoPm9ewMqGzYFn6eDUwyGCbyFiKU8bfvhAEj8TwdNVwb0Py8fX0GzevZGVDZsO24VoWaCYWfdyzjRa2RvIUIZfztTNsa8PP2TQwTft6+PoPm9eyK1HLr86TP54Gfdyj/iItaQ3kLEcL4awul2OV5BjQv0lG3ugHJz9vZZ9C8Hn9fEHnDtlrq85S4oJ/311mL2pbt8ReXbZEl67wmwvhbhTQv8q7+kxf10e/n7e0zaF7LV/s28/I99xEs23aiecTI+ema91Y1yf+etqhtWR1/hV8U/lBaXlZ/Zqw2NmIrq0HuR9gAABV+SURBVKy2qyoDLfyiHJpWNbSgRs+0xvOU+gya9/lZFfQKHViZtvDJDvOGbSdnDDilee+y9+yv0xa1LWvj78ubgat5y+/cVdbaNawdx1Anhk4/T63PoHl9vGIMOTC6YdtB8zhHlZyueekbad5/5y1qW9bGXywNPWs0L5faxciS6oznqfUZNK8L5E1Y7G+mbQfNo56qf7NB855vdJbU3+ctalvWxt+XdCBOEMcM02+Mv1XW2lWNlHg6C37FMTX0o9XPU+ozaN7n5yuefkQ/mImheZwNt6drHuewP9s51cWrWR9/amzEVlaxtV30+zD2AM3TbFut92HsgqJ5b3rx2VloH3/L79xVbG0X/T6MPUDzNNtW671nu6Dfh7F1hzEgAs3jAj9PFSs0T8P9trugaF5zvr70ZbAPaB4X+Hmq2KF5KT2gd7bmvd/R8KeCeB4X+HmqWBHP4wTJztY8hPMOBX4eF/h5qtjh5zUVeiTvqTGLRtY17x2vtz0TaB4X+HmqWKJ5KTkzcLLmvd1tGCcDzeMCP08VSzQvIS8ZT9a8jFE+DbbRPv6WYyur2Nou+HnqnGhbUfOazC3FfzpX81CddzDax9/yO3cVW9sFP0+dE2070rwHdXvDuZr3QDjvWKB5XODnqWKL5jVlyYQsRvr5ofef1YVrxrmi7SSyosiGf1kONI8L/DxVbNG8Noth+aoxcWGzbeB5wfCvtIhs7lTt4285trKKre2Cn6fOibYda14TKVtWSCt4urDxbKx5keeF0iP2AD+PC/w8Vazx81pH71gf6uC7K+7UBfipjDUv97yXxY2F5nGBn6eKPZrXRPSyQ52og++ueDqRtR1r3i1eTcqcDTSPC/w8VezRPB2O3rF+XuLC8lvSPLtBPI8L/DxVrInn3W7f2eGFIMf6eU+ThSpJELQOZfZV51+DSsFeYd6tVNMgrf7c6Foa53mncGPNa39O/XQa5qGQln7l+Su5JcGZ6V34eVzg56likZ/XFr8dubo91M97GI3mDW5a4RXVvzwve9Vn9bclKLmXJ4Xn5XVZSnPHVSh+5zSsVyTN7SZ5+wuaH1a+4ubHnwQ0jwv8PFVs0rzbx9GqcqSf1/wsY9G8Gc3LPa++hs6v2xB6RdFIWFZ6ZZTnfqtnC5oXFZ4fVd/RKGPseWUURqUXna95//uthY3xt4qt7er8POmHHsL/rqN559hW1rxWVo4L6R3o57Ur79WK5SOZ0TyvSIXik9zzmy8kpefXzYqaFO2C5jXfVulj9WxaekW95vW98zVPJ8uxlVVsbVfn5+lE+pVvxom2lTWvXT4e50sd6Oc9NaSV1wg876v5uNe8sukXv/lz3olV7nmtEvueL4ld+3PCblEbN3/OvbL5pszzopVm6EYaL0ez/M5dxdZ2dX6eTqRf+WacaNsZzWuV5bA8wXF+3tPsynbWz2u1KfLqnusL7/xetGLPy2Y0LxCFMW3Eb/gm/739vOXxt4r0cyxpF/w8daS/8NEs23ZO89oVZHaQ6B3m56VHr7o3mdG8NvuQN5oXel6twInnxV0r6/Xrkua1D9U/R/gmC+J554y/VaSfY0m74OepI/2Fj2bZtnOad7u3oneMuhzk5323Xp7Jc/M2Na9TMbEOr36GonnCNxWnal6gm502s7Vdt9tT+lFHI/3KN+NE285qXitTB7lUx/h5300++edpcqPtTDyv3Te7qnlzfl4bz5t55lb7eWfG8wC4EPOa1+UxftIDFOYQP69T4Q+jZwuQ/bxkOEQgq0N8kubN+Hnp8E3n+nkcrN3597D3tB2ccavIsbZd0LxeYw4I6h3g5313Gvxp9jiVrFclf17zes9tSELkdYiPonlDDiM5t1aFAzSPDzRPETOad3tkR7l66n5e8nGKl3e73cpWi0JvXvN6FesTuGlZCxlJ8/IuiZFD85SB5r0vhjSvS2RUqQw1pVH18+5t8uKMa38iz4uSW5J75Xo875b4XvlqdqDVNXeS5s3E86pv8sLklkZe6Uw8D5rHB5qniCnN6xOl1a9TWeGq+XmPoRUnjJq0rLfHen6+4edVeys8v9qUVjaHEVD8vPqbKkLE85SB5r0vxjRvyGRU6dL9JlPw876TrG/BxymX/tQnB5T5LZ7XvMFzuyV5JWBl1DijNM27JXnhlVFwcn0eB2geH2ieIgY173b/GFQveyb71rj3R4X05U2+k8HFO3E0p/RaqWz3iVB+f9KK7UDz+EDzFDGpeUIqo/G1Hjt1j03yEAXvJ33vmx3TYUeG7UDz+EDzFDGreUOZyODvPR5a7Xef6N3Pz8e7j5eoO7rAfqB5fKB5ihjWvGqN+fEjkT0r6Uvuhx6ofH88nk/pV6XvO1qi+lzlV+Q5s7SF5u0AmqeIcc2rVprPTJIigefz4/msRHCT5J6Mab7h+bH0Cz4UC2Xspk3bnnuSFA9oHh9oniJnaF4le+mCKmnk883DeLc0L+pCmDMvw2ACzeMDzVPkJM2rE7DywlMfT6WiQKAJaB4faJ4i52nerUkwpDPhvWP5eCYYIZYCzeMDzVPkXM1r+E4ej/RDg9f38XxA7qwGmscHmqeIDZo3cL8n9zYRkT43kT3EOvnxTOv0BtayDgDN4wPNU8QuzQMXA5rHB5qnCDQPnAg0jw80TxFoHjgRaB4faJ4i0DxwItA8PtA8RZzTvOPutwXnA83jA81TxDnNO+x+W2AB0Dw+0DxF4OeBE4Hm8YHmKQI/D5wINI8PNE8R+HngRKB5fKB5isDPAycCzeMDzVMEfh44EWgeH2ieIvDzwIlA8/hA8xSBnwdOBJrHB5qnCPw8cCLQPD7QPEXg54ETgebxgeYpAj8PnAg0jw80TxFXNC/5aG8sG/l59wwngzoNNI8PNE8RRzTv8fPzbP5L9PPu2Q9Ez2mgeXygeYq4oXm10KX1fwp+3nf1Xx/Sw8AdoHl8oHmKOOLnJb3oDX7ed3UfBvw8p4Hm8YHmKeJMPK8Tvd7PqyXvB5LnIPePbsqK8/f743SNGZowmheP57f0qGms7TNX0GVbjXnbtLV05+fBy3MWIQwrzt/n6Y5VNabaxojz4vHz83G26FnbZ66gzbY6a1XSpqWdn/eEh+8qwttKmL/p+W77Y2iNMC+sWOZa22euoM22WuvzGk+v9fNSSJ6z3LOf7u06zN/UBmUZRtUwGR5D/uxE7O0zV9BlW701ybVrVzf9B16eywwTuJ+/dkzfIUbczwtBbE7F2j5zBV221at5358/IpA8Z+kHWzd/EyucKSFK3M2LuqWf50uexX3mCppsq3nvWSPVLbC2w3TztZ2/9kzfzhto54UtXt7N5j5zBT221b3f9vsJyXsP2hnbzF+bpu93NROy72ZetH+QHjoHa/vMFbTYVvsZA7U2w9pvwGMIztb//7Tlr1QnyT7qNqX1asieGIq1feYKOmyr/1yVVvRgbed5jIKzlqwfb+J7tcaqElBr+8wVNNjWxPl5FkVYgAqprdP3Lk4LuzJl1vaZKxxvWwOaV7Ua1n4LUlunbzLMC9uKA6ztM1c43LYmNO/2gLXfhH4C22bQfmLYV/1mbZ+5wtG2NaJ54G142hcya0js9PJuNveZKxxsW2ge4GDv2Tj2niWF84RUce4+DPBOVBPYzumbWlsPZW+fucKhtoXmAR7fH7ZuIUytrYeyt89c4UjbQvMAAFcCmgcAuBLQPADAlYDmAQCuhKrmZUUR5nk++V8UFYX0aE9RTJ8vYukhAADQgKrmBd4S0qM9M9+QSw8BAAA0DwAAlFiRJhJZUSFpmL+6tvXHD5cF1rYAADMclMNIYlHHNhUs7VXSzwOUawIAjHFY3jYZnL1S+lAiaRXvJX0CAAAaOa5WJRk8PUJ0DlE8J8iLfJRhj4pMaHb1afdZPvpEK3EUjbL+USQuLOIoEtprMGhiZV+5hCm7Hlifl5W96G26b3XqI5S+DCxDjtSKW73HcVlj8ziXGiXOgGj0icExZmVfuYQpux5ZkxwPq9sNm9Y+Ibw8+5FG4Wi8LH+iFVlcAuHXFYufaEZqlQ195RKm7Hpo7w9S7K8nJqr2F+uPABsIgiAerBq9AnGsJUH/ZvbzwJy6ZEHwyvtFRREHozRYEHYfldHLZILMyr5yCVN2PfaNM2hxJH0mEFYNx92PrtDN1pn1RNjM4hPm8NfyQMuamTHTXP1Y2VcuYcCux2peMoT0Vlr2UnVOgVGS5QVZ/VF0isdeLC9yqsiJvxFe0YSdfeUS+u06ZxwFMsKKOy0RzHOLdsU255nPv5FN0LhNs7WgxWZwRR9W9pVL6Lfr0dHUsNe8cqF1df5iZZcGsI7lYfg6T12yxTVQ9VI9LTFqZV+5hH67Hp5BGhLOC7oWIX/hGuniMPRX/HndNNUfMwXw0ZnLCDv7yiW02/VwzUs28hghoZQFWMbSMMwXjGyEdhUpjaXA8/wTu8/KvnIJ7XY9vlIoHfIYMw5+7blix5ljLAzDpFyMYBggXkiWRef6U1b2lUtot6uG6sjXENKTtDpB/sJFFoZhJH/JIAuryHgxqmIGK/vKJbTbVUdF+BDSk2K2xcxfBlhPMjsMs3MXkd12rvEXqxTZXNLUGHb2lUvotquWXTBDSG+izPmcDgL7mR2GxclB+fbdGky/ePI6wsq+cgnddtWieUtHrMSz611gP3PD8CW90gzzmllFpuXpL1Ur+8oldNtVz27n+SNW6q/O5DWA9bzkN1jin71/sDuEUfxadH6GzMq+cgnddtV0wsPcESu194dgnpvIoYr8/KB8myIV3v+BDf6UlX3lEprtqutUG6E0uWt6MdVu4A7FdBhasIjsBpngAPhykYh5rOwrl9BsV20neQ15jNbJz1f2owHbkYYhYbHx8jW/4oLpKjJeC3QncVSUnudHuebVL6+v0jiv54ofhVj+NvDsykab5gl5jNqtD6S4LnCI6S7I7cVGXOh368vxKnKt7jeNarnLo0pgynzpsSPg9FVQeGWUd0fvRVC9GoZdd6DvxFbhiJWvdncGYhruUo7jysVatVQShFHpGYjeTg4xCZdTZLlX5u1jQfU2Lr+kR46D3FdJ7hW9B1hNmHKp/deCbtc9aDylWshjJAmKkR2nGA3DlcVGs7IrwmnuUgfjQ0zSRccyKcSD65oliMa4H7WvkmLkBuQ4SreFatd96DyZXzgqPsdhKo4zGoZV7cWSNeMwD7K24GA5inUM41Xk8obMYuwnpFIpxLFQ+yqqVtnDHwMTrwknoNk18VZZdLG03kYyuusJbzCnGe2CzLcXG4G3cHLmofjCKjJYHOb59IPC01opSuyrZmYP/mbgyTuXLgrJrnGd+cnjoKI2aXUJSRAEebRaFqdV84QjVnCYiusIZySlhKkZzh6odDTiISaL/lQqHSmeaw420vqqiQIMLkxoIgTqBiS7RmL4s75HIxE+W/aY9d46FwySt9gC4AbCMKRsHi2M+CzCISbh4hgLpaVsrtmjovVVMGlXpNf7dAmSXUsxJptPbOwvfZduzRuOisfry3WGYRgsjkIBMzcYt6vIoq5nWIrQFd7U54w0D0liX72KKBQqlz1UsHZQ7Poa9Ww0sWi++KrRrXn9VcaLDQCOkPTDsCDMTCMpjD5FWi4HumcVrtC88uD1VUvkoZyrh2DXaNSz03csNA+o01ZgVE7M9sw0k8LoV5FBuuK3JbnnjwQunSQPjofVVw2ZpMxXhmBXX/ygfsuINZfhsn2heYBIOwxfi4sNkdxICmM4xGS57ncG3eE8Zl/VZDhBXGTbrtloGRGMUxiVjaXv6Fj+5BigeW9DOwxLkjEjQ2UXSd8oul40bt7CVDoGVl9VBKXnlSht6Nm2azR6pU5TGNA8cAScfJSZFIZwlgXj4BLN1Xk1rNxdVu9N1roH2DmYdp2mMNaA5gEq3TAkeEimUhhDZQBdw4yUhFD7Kuvq9rGsHcO0K+cdC80DVHL67DSVwuhLQOnraDNVcOS+qjcOVIeqlBH8PAGmXTnvWGgeoJLRFxtmdmHUlLwkbCV5pf7RyOir5vkCh6qMYdmV9Y6F5gEyJfltamYXRo1cfbdCUsd9TDhU9L5qSHFZzBiWXVnvWGgeIEMPFBfmIlQhY/dCWhjLjnKC6v03YJoMcOzK621oHiATkhcbxlIYzSqSWPf7Kg05eay+aol5Ycm3h2FXZpkANA+QeVEHlrkURp0iJipF7nmFsRuCyH3V0QTtkcfooNuV+46F5gEqK6dfTjCYwljZkDkm9U0WhND7qiPAPBlBteuN/Y6F5gEqy6dfTjG1C6M5N40UyHmVopOX6R6PW30VRKMjkvuzWDBPWqh2reG9Y6F5gMjK6ZdTDKYwfNoB3LlXCsGhVPdm/q2+yuR626aiT3ryqhDt2sB7x0LzABHGYsNcCiMnBbrTwivEGZTrvvl7q68agRu13MduDAGaXTt4Ox2heYDG4rUEMuZSGMsnSoq8ynI0gZJS/2Xj633VHGMqdlFM3dZ3CWh27ZGc5lU0a17eaR421rgOIygfGlulkXzPaOzkVaNS89Gcm31V15ONfE3dx5i6BSeB0UYK6J67pqEZ5xWFcPFZWUT116RHgZWkeRGJwy5nzEhtKYwkLArxfR4Qfk+Vry1E/MNLQvh9FUzdGN23EtnNHrsKxLx3rCbNG662nSI9CmykPsJSeNdmjAth6+/VoXnNZdzh6M9bq8FXKQ3Bo8VlT19F45VPfGkvb49dRZjvWE0aVEjDrEN6FNiIP9GGleu7BrLGu28s7dd+/aGZjOZNWop/3tKJXBqAx0eXd/VV5Pm9Z1PvAi6uG/LeYdeGtLnNtun/+p5bigOvzc8ri0j+x4fmuUF7kXz/8qStbPNK6QSrH10F3Lps3R9f2w7b/FX3x2Yw9vVVXaEX5a+vIKwV78rHC/Dt2lJ4pTjeSlrQAhoEZojHa8DYip2g6VixstKOmxF391Ua1q+FsojiS+drTdsVmgdmCEdrwGoaW6Au7TGSbdynmhrGds+uYWVfuYRpu0LzwAyB6LrErNsmNNKsIZumWCN5lvaVSxi2KzQPzFF6nt/kH9LIGs8l6r2BJPdskTxL+8olDNsVmgfmeNVx9eamBmsKyquzhP0wCF556U3rjE/Eyr5yCcN2heaBWeIhy2nPtatZX2xX2lTMZmVfuYRZu0LzwDxZU/ZkVxFFktezww/t8qas7CuXMGpXaB5YJAssrJNNaYWnprGyr1zCnF2heQCAKwHNAwBcCWgeAOBKQPMAAFcCmgcAuBLQPADAlYDmAQCuBDQPAHAloHkAgCsBzQMAXAloHgDgSkDzAABXApoHALgS0DwAwJWA5gEArgQ0DwBwJaB5AIArAc0DAFwJaB4A4EpA8wAAl+F2u/0/NSOO8Hw7vnMAAAAASUVORK5CYII=\"\n",
        "height=\"200\"></center>\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "ARFiZKBA9of-"
      },
      "source": [
        "We can therefore think of an RNN as a composition of identical feedforward neural networks (with replicated/tied weights), one for each moment or step in time.\n",
        "\n",
        "These feedforward functions that make up the RNN (i.e. our `rnn_cell` function above) are typically referred to as **cells**, and the only requirement for this function is that the cell function needs to be a differentiable function that can map an input and a state vector to an output and a new state vector. What we have shown above is called the **vanilla RNN**, but there are many more possibilities. One of the most popular variants is called the **Long Short-Term Memory (LSTM)** cell, which we'll use later to create our Shakespeare language model.\n",
        "\n",
        "### Putting this together \n",
        "\n",
        "In the feedforward models we've seen before, the input $x$ is mapped to an intermediate hidden layer $h$ as follows:\n",
        "\n",
        "\\begin{equation}\n",
        "  h = \\sigma(\\underbrace{W_{xh}x}_\\text{current input (per-example)} + b)\n",
        "\\end{equation}\n",
        "\n",
        "where $\\sigma$ is some non-linear activation function like ReLU or tanh.  We can then make a prediction $\\hat{y} = \\sigma(W_{hy}h + b)$ based on $h$, or we can add another layer, etc.  **NOTE**: We use the weight subscript $W_{xz}$ to indicate a mapping from layer $x$ to layer $z$.\n",
        "\n",
        "RNNs generalize this feedforward idea to a sequence of inputs $X = {x_1, x_2, ...}$ by maintaining a sequence of state vectors $h_t$, one for every time-step $t$. The simplest form of such an RNN looks very similar to the equation for a single feedforward layer:\n",
        "\n",
        "\\begin{equation}\n",
        "  h_t = \\sigma(\\underbrace{W_{hh}h_{t-1}}_\\text{previous state} + \\underbrace{W_{xh}x_t}_\\text{current input (per time-step)} + b)\n",
        "\\end{equation}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "LZFxydtr_BvW"
      },
      "source": [
        "These states $h_t$ can then be used for various purposes, as we describe below.\n",
        "\n",
        "Feedforward models map one input to one output. On the other hand, RNNs can give **many-to-many** (many inputs, many labels), **many-to-one**, and **one-to-many** mappings. Examples of these tasks include machine translation, sentiment analysis, and image captioning, respectively. For example, we could use each $h_t$ to predict the part of speech for that time-step ($y_t= \\sigma(W_{hy}h_t+b)$) or we could use the last state $h_T$ to predict the topic of the whole document. Which task the RNN performs is based on the training data (of course)! We can visualize these as follows (from this [excellent blog post](http://karpathy.github.io/2015/05/21/rnn-effectiveness/) by Andrej Karpathy):\n",
        "\n",
        "<center><img src=\"http://karpathy.github.io/assets/rnn/diags.jpeg\" height=\"200px\"/></center>\n",
        "\n",
        "**QUESTIONS**\n",
        "* How are FFNs and RNNs **similar**?\n",
        "* How are they **different**?\n",
        "* Why do we call RNNs \"recurrent\"?\n",
        "* Can you think of a one-to-many task?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "9wuobtH3aB59"
      },
      "source": [
        "##Modeling General Time-Series\n",
        "\n",
        "We will train an RNN to model a time-series as a first step. A **time-series** is a series of data-points ordered over discrete time-steps. Examples include the hourly temperature of Montevideo over a month or a year, the market price of some asset (like a company's stock) over time, and so forth. We will generate a **sinusoidal time-series** (with or without noise) as a toy example, and then train a tiny RNN model with only 5 parameters on this data."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "oAQIXUL-oje2"
      },
      "source": [
        "###Create some artificial data"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab_type": "code",
        "id": "412j4v-RIfYR",
        "colab": {}
      },
      "source": [
        "#@title Create sinusoidal data {run: \"auto\"}\n",
        "steps_per_cycle = 26 #@param { type: \"slider\", min:1, max:100, step:1 }\n",
        "number_of_cycles = 176 #@param { type: \"slider\", min:1, max:1000, step:1 }\n",
        "noise_factor = 0.4 #@param { type: \"slider\", min:0, max:1, step:0.1 }\n",
        "plot_num_cycles = 23 #@param { type: \"slider\", min:1, max:50, step:1 }\n",
        "\n",
        "seq_len = steps_per_cycle * number_of_cycles\n",
        "t = np.arange(seq_len)\n",
        "sin_t_noisy = np.sin(2 * np.pi / steps_per_cycle * t + noise_factor * np.random.uniform(-1.0, +1.0, seq_len))\n",
        "sin_t_clean = np.sin(2 * np.pi / steps_per_cycle * t)\n",
        "\n",
        "upto = plot_num_cycles * steps_per_cycle\n",
        "fig = plt.figure(figsize=(15,3))\n",
        "plt.plot(t[:upto], sin_t_noisy[:upto])\n",
        "plt.title(\"Showing first {} cycles.\".format(plot_num_cycles))\n",
        "plt.show()\n",
        "\n",
        "#both = np.column_stack((t, sin_t_noisy))\n",
        "#print(\"both.shape = {}\".format(both.shape))\n",
        "\n",
        "#print(\"both[:steps_per_cycle, :steps_per_cycle]\")\n",
        "#print(both[:steps_per_cycle,:steps_per_cycle])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Eaypg9gKos21"
      },
      "source": [
        "**TASK**: Adjust the parameters above to generate data with different properties.\n",
        "\n",
        "Now we pack the data into train and test batches. Note that while RNNs can in theory learn the dependencies across all inputs received so far (using an algorithm called **backpropagation through time**, or BPTT; see the Aside box below), in practice they are trained using an algorithm called **truncated BPTT** where we truncate the inputs to only the last $T$ symbols (this is the `truncated_seq_len` variable below).\n",
        "\n",
        "**QUESTIONs**: \n",
        "* What issues can you think may arise by truncating the training data in this way? \n",
        "* Despite these issues, why do you think it might be necessary to do this?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "colab_type": "code",
        "id": "RtwMLLCNorw4",
        "colab": {}
      },
      "source": [
        "#@title Pack truncated sequence data {run: \"auto\"}\n",
        "\n",
        "def pack_truncated_data(data, num_prev = 100):\n",
        "    X, Y = [], []\n",
        "    for i in range(len(data) - num_prev):\n",
        "      X.append(data[i : i + num_prev])\n",
        "      Y.append(data[i + num_prev])\n",
        "    # NOTE: Keras expects input data in the shape (batch_size, truncated_seq_len, input_dim)\n",
        "    # We have only one real-valued number per time-step, so we therefore expand\n",
        "    # the last dimension from (batch_size, truncated_seq_len) to\n",
        "    # (batch_size, truncated_seq_len, 1).\n",
        "    X, Y = np.array(X)[:,:,np.newaxis], np.array(Y)[:,np.newaxis]\n",
        "    return X, Y\n",
        "\n",
        "# We only consider this many previous data points\n",
        "truncated_seq_len = 2 #@param { type: \"slider\", min:1, max:10, step:1 }\n",
        "test_split = 0.25  # Fraction of total data to keep out as test data\n",
        "\n",
        "# We use only the sin(t) values, and discard the time values\n",
        "data = sin_t_noisy\n",
        "data_len = data.shape[0]\n",
        "num_train = int(data_len * (1 - test_split))\n",
        "\n",
        "train_data = data[:num_train]\n",
        "test_data = data[num_train:]\n",
        "\n",
        "X_train, y_train = pack_truncated_data(train_data, num_prev=truncated_seq_len)\n",
        "X_test, y_test = pack_truncated_data(test_data, num_prev=truncated_seq_len)\n",
        "\n",
        "print(\"Generated training/test data with shapes\\nX_train: {}, y_train: {}\\nX_test: {}, y_test: {}. \".format(\n",
        "    X_train.shape, y_train.shape, X_test.shape, y_test.shape))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "vgVxLBp8CaN6"
      },
      "source": [
        "**NOTE**: We reshape the training data into (batch_size, truncated_seq_len, 1) and (batch_size, 1) arrays."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "xiUrsPAI36M-"
      },
      "source": [
        "### Intermediate optional extra reading: (Truncated) Backpropagation-through-Time and Vanishing and Exploding Gradients"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "SCJlN3O11pr1"
      },
      "source": [
        "RNNs model sequential data, and are designed to capture how ***outputs*** at the current time step are influenced by the ***inputs*** that came before them. This is referred to as **long-range dependencies**. At a high level, this allows the model to remember what it has seen so far in order to better contextualize what it is seeing at the moment (think about how knowing the context of the sentence or conversation can sometimes help one to better figure out the intended meaning of a misheard word or ambiguous statement). It is what makes these models so powerful, but it is also what makes them so hard to train!\n",
        "\n",
        "The most well-known algorithm for training RNNs is called **back-propagation through time (BPTT**; there are other algorithms). BPTT conceptually amounts to unrolling the computations of the RNN over time, computing the errors, and backpropagating the gradients through the unrolled graph structure.  Ideally we want to unroll the graph up to the maximum sequence length, however in practice, since sequence lengths vary and memory is limited, we only end up unrolling sequences up to some length $T$. This is called **truncated BPTT**, and is the most used variant of BPTT.\n",
        "\n",
        "At a high level, there are two main issues when using (truncated) BPTT to train RNNs:\n",
        "\n",
        "* Having shared (\"tied\") recurrent weights ($W_{hh}$) mean that **the gradient on these weights at some time step $t$ depends on all time steps up to time-step $T$**, the length of the full (truncated) sequence. This also leads to the **vanishing/exploding gradients** problem, which we'll explain below.\n",
        "\n",
        "* **Memory usage grows linearly with the total number of steps $T$ that we unroll for**, because we need to save/cache the activations at each time-step (this happens implicitly in Tensorflow, when the activations are stored in the [gradient tape](https://www.tensorflow.org/api_docs/python/tf/GradientTape)).  This matters computationally, since memory is a limited resource. It also matters statistically, because it puts a limit on the types of dependency that the model can successfully learn, by preventing it from correcting errors that stem from an input more than $T$ steps ago. \n",
        "\n",
        "<!-- * **Memory usage grows linearly with the total number of steps $T$ that we unroll for**, because we need to save/cache the activations at each time-step (look at the Python code above to convince yourself of this).  This matters computationally, since memory is a limited resource. It also matters statistically, because it puts a limit on the types of dependency that the model can successfully learn, by preventing it from correcting errors that stem from an input more than $T$ steps ago. -->\n",
        "\n",
        "**NOTE**: Think about that last statement and make sure you understand those 2 points.\n",
        "\n",
        "BPTT is very similar to the standard back-propagation algorithm. Key to understanding the BPTT algorithm is to realize that gradients on the non-recurrent weights (weights of a per time-step classifier that tries to predict the part-of-speech tag for each word for example) and recurrent weights (that transform $h_{t-1}$ into $h_t$) are computed differently:\n",
        "\n",
        "* The gradients of **non-recurrent weights** ($W_{hy}$) depend only on the error at that time-step, $E_t$.\n",
        "* The gradients of **recurrent weights** ($W_{hh}$) depend on all previous time-steps up to maximum length $T$.\n",
        "\n",
        "The first point is fairly intuitive: predictions at time-step $t$ is related to the loss of that particular prediction. \n",
        "\n",
        "<!-- The second point will be explained in more detail in the lectures (see also [this great blog post](http://www.wildml.com/2015/10/recurrent-neural-networks-tutorial-part-3-backpropagation-through-time-and-vanishing-gradients/)), but briefly, this can be summarized in these equations: -->\n",
        "\n",
        "The second point can be summarized in these equations (see also [this great blog post](http://www.wildml.com/2015/10/recurrent-neural-networks-tutorial-part-3-backpropagation-through-time-and-vanishing-gradients/)):\n",
        "\n",
        "1. The **current** state is a function of the **previous** state and the current input: $h_t = \\sigma(W_{hh}h_{t-1} + W_{xh}x_t)$\n",
        "2. The gradient of the loss $E_t$ at time $t$ on $W_{hh}$ is a function of the current hidden state and model predictions $\\hat{y}_t$ at time t: \n",
        "$\\frac{\\partial E_t}{\\partial W_{hh}} = \\frac{\\partial E_t}{\\partial \\hat{y}_t}\\frac{\\partial\\hat{y}_t}{\\partial h_t}\\frac{\\partial h_t}{\\partial W_{hh}}$\n",
        "3. Substituting (1) into (2) results in a **sum over all previous time-steps**:\n",
        "$\\frac{\\partial E_t}{\\partial W_{hh}} = \\sum\\limits_{k=0}^{t} \\underbrace{\\frac{\\partial E_t}{\\partial \\hat{y}_t}\\frac{\\partial\\hat{y}_t}{\\partial h_t}\\frac{\\partial h_t}{\\partial h_k}\\frac{\\partial h_k}{\\partial W_{hh}}}_\\text{product of gradient terms}$\n",
        "\n",
        "The problem is that $\\frac{\\partial h_t}{\\partial h_k} = \\Pi_j \\frac{\\partial h_j}{\\partial h_{j-1}}$ for j from $k + 1$ to $t$.  Because of this **repeated multiplicative interaction**, as the sequence length $t$ gets longer, the gradients themselves can get diminishingly small (**vanish**) or grow too large and result in numeric overflow (**explode**). Ideally, in order to avoid these beheviors, the norms of the gradients should be close to 1. \n",
        "\n",
        "<!-- This has been shown to be related to the norms of the recurrent weight matrices being less than or equal to 1. Intuitively, it works very similar to how multiplying a small number $v<1.0$ with itself repeatedly can quickly go to zero, or conversely, a large number $v>1.0$ could quickly go to infinity; only this is for matrices. -->\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "-o3qjqeZpLjN"
      },
      "source": [
        "###Build a tiny RNN in Keras\n",
        "\n",
        "Building an RNN in Keras is quite simple. We simply chain the layers together as follows:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "mEobTD6spOWx",
        "colab": {}
      },
      "source": [
        "def define_model(truncated_seq_len):\n",
        "\n",
        "    input_dimension = 1\n",
        "    hidden_dimension = 1\n",
        "    output_dimension = 1\n",
        "\n",
        "    model = tf.keras.models.Sequential()\n",
        "    model.add(tf.keras.layers.SimpleRNN(\n",
        "        # We need to specify the input_shape *without* leading batch_size (it is inferred)\n",
        "        input_shape=(truncated_seq_len, input_dimension),\n",
        "        units=hidden_dimension,\n",
        "        return_sequences=False,\n",
        "        name='hidden_layer'))\n",
        "    model.add(tf.keras.layers.Dense(\n",
        "        output_dimension,\n",
        "        name='output_layer'))\n",
        "\n",
        "    model.compile(\n",
        "        loss=\"mean_squared_error\",\n",
        "        optimizer=tf.compat.v1.train.AdamOptimizer(learning_rate=1e-3))\n",
        "\n",
        "    return model\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "JHRscZaQze26"
      },
      "source": [
        "**NOTE**: We're building an RNN for **regression**. We therefore use a linear layer (which outputs real-valued numbers) at the output with the \"*mean_squared_error*\" loss function."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "ONvBy4AopTrF",
        "colab": {}
      },
      "source": [
        "model = define_model(truncated_seq_len = X_train.shape[1])\n",
        "model.summary()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "ddb6_04dfZvn"
      },
      "source": [
        "**NOTE**: You need to re-run the above cell every time after training to reset the model weights!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "hD94X5iQc8Jg"
      },
      "source": [
        "###Train the tiny RNN\n",
        "Now let's train the model. This may take a few minutes (it takes much longer if you increase `truncated_seq_len`). Set `verbose=1` **before** you run the cell to see the intermediate output as the model is training. Set it to 0 if you don't want any output."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "txqSzd10wgeE",
        "colab": {}
      },
      "source": [
        "train_history = model.fit(X_train, y_train, batch_size=600, epochs=1000,\n",
        "                          verbose=1, validation_split=0.05)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "CebcKzSW_g6P"
      },
      "source": [
        "Let's visualize the training and validation losses."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "U9G1OHXoroBs",
        "colab": {}
      },
      "source": [
        "plt.figure(figsize=(15,5))\n",
        "\n",
        "for label in [\"loss\",\"val_loss\"]:\n",
        "    plt.plot(train_history.history[label], label=label)\n",
        "\n",
        "plt.ylabel(\"loss\")\n",
        "plt.xlabel(\"epoch\")\n",
        "plt.title(\"The final validation loss: {}\".format(train_history.history[\"val_loss\"][-1]))\n",
        "plt.legend()\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Rs_-XnYhKl_N"
      },
      "source": [
        "Finally, let's look at the parameters for the trained model."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "q4gtwBT7Kgh0",
        "colab": {}
      },
      "source": [
        "for layer in model.layers:\n",
        "  print(\"{}, {}\".format(layer.name, layer.get_weights()))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "bqFBu_dCsUqi"
      },
      "source": [
        "**QUESTION**: \n",
        "* Relate the above weights to the terms in the equation for the vanilla RNN we saw earlier, namely:\n",
        "  * input-to-hidden $W_{xh}$,\n",
        "  * hidden-to-hidden $W_{hh}$,\n",
        "  * hidden-to-output weights $W_{hy}$\n",
        "  * recurrent and out biases."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "0FHaN-VXfxEl"
      },
      "source": [
        "###Make predictions using the trained model"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "IQl_msx-4o3E",
        "colab": {}
      },
      "source": [
        "y_pred = model.predict(X_test[:100])\n",
        "plt.figure(figsize=(19,3))\n",
        "\n",
        "plt.plot(y_test[:100], label=\"true\")\n",
        "plt.plot(y_pred, label=\"predicted\")\n",
        "plt.legend()\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "MQj5P-FKOgqG"
      },
      "source": [
        "**YOUR TASKS**: \n",
        "* [**ALL**] Change the learning rate up to 5 orders of magnitude larger and smaller and retrain. What happens when it is too large? What happens when it is too small?\n",
        "* [**ALL**] Change the `SimpleRNN` to `GRU`.\n",
        "  * You can read more about LSTMs in [this blog post](https://colah.github.io/posts/2015-08-Understanding-LSTMs/) by Chris Olah. \n",
        "  * What is the effect on the number of parameters? Can you explain why? Now do the same for `LSTM`.\n",
        "* [**INTERMEDIATE**] Note that the loss does not decrease much after around epoch 400. Add \"Early Stopping with patience\" to the `model.fit()` function to stop it from training beyond this point. **Hint**: Look at tf.keras.callbacks.\n",
        "  * *Early stopping* is a technique where we stop training the model once it's performance on validation data stops improving, and is a very common approach to prevent overfitting. Early stopping *with patience* means as soon as the model starts doing worse on validation we wait for at least `patience` more evaluations before stopping training, and if it improves within that time, we reset the counter. The patience parameter is a way to ensure we don't stop by accident, as the validation loss can fluctuate randomly from epoch to epoch.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "_totIpxmZ8_v"
      },
      "source": [
        "##Generating Text\n",
        "\n",
        "Now let's build an RNN language model to generate language with the style of Shakespearian English or Cervantes Spanish! A language model is trained to assign high probabilities to sequences of words or sentences that are well formed, and low probabilities to sequences which are not realistic. When the model is trained, one can use it to *generate* data that is similar to the training data.\n",
        "\n",
        "Our data is now sequences of discrete symbols (characters). But neural networks operate in continuous spaces, and so we need to take the discrete language data, and **embed** it in a continuous space. To do this, we'll simply break up the data into sequences of characters, and represent each character using a learned vector. This is a standard trick for processing text using neural networks. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "9dFQtnDLZa3c"
      },
      "source": [
        "### Download and Preprocess the Data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Tmmjc-EigwCw"
      },
      "source": [
        "We first download the data and examine what it looks like:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "hybIopOLPD4f",
        "colab": {}
      },
      "source": [
        "context = ssl._create_unverified_context()\n",
        "\n",
        "LANGUAGE = 'sp' #@param ['en', 'sp']\n",
        "\n",
        "corpora = dict(\n",
        "    sp=('http://www.gutenberg.org/cache/epub/2000/pg2000.txt', 28142),\n",
        "    en=('https://cs.stanford.edu/people/karpathy/char-rnn/shakespeare_input.txt', 0)\n",
        ")\n",
        "\n",
        "corpus_url, text_start = corpora[LANGUAGE]\n",
        "\n",
        "data = urllib.urlopen(corpus_url, context=context)\n",
        "all_text = data.read().lower().decode('utf8')\n",
        "\n",
        "print(\"Downloaded corpus data with {} characters.\".format(len(all_text)))\n",
        "print(\"FIRST 1000 CHARACTERS: \")\n",
        "print(all_text[text_start:text_start+1000])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "jIuagNcdQLqM",
        "colab": {}
      },
      "source": [
        "training_text = all_text[text_start:text_start+1000000] # Keep only the first 1 million characters"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "UK1x69AngvLJ"
      },
      "source": [
        "We now preprocess the text data as follows:\n",
        "\n",
        "1. Extract the vocabulary of all `vocab_size` unique characters appearing in the data.\n",
        "\n",
        "2. Assign each character a unique integer id in `0 <= id < vocab_size`. This is so we can map the characters to unique embedding vectors. This is a common way to map discrete inputs to continuous vectors that neural networks can work with. See e.g. this [blog post](https://www.tensorflow.org/tutorials/representation/word2vec), or [this one](http://ruder.io/word-embeddings-1/) for more information.\n",
        "\n",
        "3. Split the data into sequences (\"windows\") of `max_len` characters (the input to the model) followed by the next character as target. E.g. using `max_len=5` the sentence \"I saw a cat\" (11 characters) will get split into \"I saw\" and /space/, \"/space/saw/space/\" and \"a\", \"saw a\" and /space/, etc. To add some variation, we skip `step` characters between each sequence (i.e. we use a \"sliding window of `max_len` with stride `step`\")."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "zPvsNXKZPJKz",
        "colab": {}
      },
      "source": [
        "max_len = 30  # We only consider this many previous data points (characters)\n",
        "step = 3 # We start a new training sequence every `step` characters\n",
        "\n",
        "chars = sorted(list(set(training_text)))  # List of unique characters in the corpus\n",
        "vocab_size = len(chars)\n",
        "print('Number of unique characters: ', vocab_size)\n",
        "print(chars)\n",
        "\n",
        "# Construct dictionaries mapping unique characters to their index in `chars` and reverse\n",
        "index2char = dict(enumerate(chars))\n",
        "char2index = dict((v,k) for k,v in index2char.items())"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "O2PhcQwrc2JX"
      },
      "source": [
        "Now we encode the training data by mapping each character to its unique integer id."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "xY0qXZmVq8kW",
        "colab": {}
      },
      "source": [
        "sentences = [] # This holds our extracted sequences\n",
        "next_chars = [] # This holds the targets (the follow-up characters)\n",
        "for i in range(0, len(training_text) - max_len, step):\n",
        "    sentences.append([char2index[s] for s in training_text[i: i + max_len]])\n",
        "    next_chars.append([char2index[training_text[i + max_len]]])\n",
        "\n",
        "print('Number of extracted sequences:', len(sentences))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "PsZy6Kshc-Sp"
      },
      "source": [
        "This yields the following numpy arrays:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "vhgSaP5ntDtq",
        "colab": {}
      },
      "source": [
        "X, Y = np.array(sentences, dtype=np.int64), np.array(next_chars, dtype=np.int64)\n",
        "X.shape, Y.shape"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "sBR2LsXjmqTU"
      },
      "source": [
        "Let's take a look at the first example."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "2H1jobcrmwK7",
        "colab": {}
      },
      "source": [
        "print(\"X[0].shape = {}, Y[0].shape = {}\".format(X[0].shape, Y[0].shape))\n",
        "print(\"X[0]: \", X[0])\n",
        "print(\"Y[0]: \", Y[0])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "tEQWEZlSZgpF"
      },
      "source": [
        "###Build an RNN language model"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "rCysOLWadPHF"
      },
      "source": [
        "A **language model** estimates a probability distribution over sequences $\\mathbb{x}_{1:N} = (x_1, x_2, ..., x_N)$ by breaking up the full joint probability into a sequence of conditional probabilities using the **[chain-rule of probability](https://en.wikipedia.org/wiki/Chain_rule_(probability))**:\n",
        "\n",
        "\\begin{align}\n",
        " p(\\mathbb{x}_{1:N}) &= p(x_1) \\cdot p(x_2 | x_1) \\cdot p(x_3 | x_2, x_1) \\ldots \\\\\n",
        " &= \\Pi_1^N p(x_i | \\mathbb{x}_{1:i-1})\n",
        "\\end{align}\n",
        "\n",
        "In other words, to model the probability of the phrase \"*i saw a cat*\" at the character level, the model learns to estimate the probabilities for p(i), p(/space/| i), p(s | i, /space/), and so forth, and multiplies them together. \n",
        "\n",
        "There are many different ways in which to estimate these individual probabilities. But one particularly effective way is to use an RNN! \n",
        "\n",
        "To do this, we'll therefore be modeling the  $p(x_i | \\mathbb{x}_{1:i-1})$ terms using an RNN conditioned on $\\mathbb{x}_{1:i-1}$.\n",
        "\n",
        "* We model these probabilities at the character-level, so we'll use an `Embedding` layer as the first layer of our model to map the discrete character id's to real-valued embedding vectors. \n",
        "* Next, the RNN-core will map these sequences of character embeddings to a probability distribution over all characters $p(x_i | \\mathbb{x}_{1:i-1}) \\in \\mathbb{R}^\\textrm{vocab_size}$ at every step of the sequence. To do this, the RNN will map the embeddings to a sequence of *hidden states*. We will then use a `Dense` layer to map from the RNN hidden state to an output distribution over the total number of characters using a [`softmax`](https://en.wikipedia.org/wiki/Softmax_function) activation.\n",
        "\n",
        "We can do this with a few lines of code:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "k8AxhQuePOCN",
        "colab": {}
      },
      "source": [
        "embedding_dim = 32   # Map each character to a unique vector of this dimension\n",
        "vocab_size = len(chars)\n",
        "\n",
        "model = tf.keras.models.Sequential()\n",
        "model.add(tf.keras.layers.Embedding(\n",
        "  vocab_size, embedding_dim,\n",
        "  input_length=max_len,\n",
        "  embeddings_initializer=tf.keras.initializers.TruncatedNormal))\n",
        "model.add(tf.keras.layers.LSTM(\n",
        "  128,\n",
        "  input_shape=(max_len, embedding_dim),  # NB: Ensure this matches the embedding_dim!\n",
        "  dropout=0.1,  # input-to-hidden drop-probability\n",
        "  recurrent_dropout=0.2))  # hidden-to-hidden drop-probability\n",
        "model.add(tf.keras.layers.Dense(vocab_size, activation='softmax'))\n",
        "\n",
        "model.summary()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "RHOWm55whZUt"
      },
      "source": [
        "Once we have a model that can map sequence of characters to a probability distribution over the next character in the sequence, we can train it using **maximum likelihood** on the training set to find the model parameters which maximizes the probability of the training data. Again, this is very simple to do by choosing an optimizer and selecting the `sparse_categorical_crossentropy` loss function:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "hKJNZXs7PSW-",
        "colab": {}
      },
      "source": [
        "optimizer = tf.keras.optimizers.Adam()\n",
        "loss='sparse_categorical_crossentropy'\n",
        "\n",
        "model.compile(loss=loss, optimizer=optimizer)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "vc8jIbIL7XsY"
      },
      "source": [
        "### Optional extra reading: RNN vs GRU vs LSTM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Xo8liyGpnB1J"
      },
      "source": [
        "<!-- Our language model above is using an RNN variant called the LSTM (long short-term memory). The LSTM solves a big problem with the vanilla RNN: vanishing and exploding gradients. It does this by allowing gradients to flow backwards through the layer unimpeded. As a result, the LSTM is very popular for sequence tasks. The key to the success of the LSTM is that it maintains an internal **cell state** ($\\mathbf{c}_t$) which can be thought of as a 'memory' for the LSTM. The cell state provides the path along which the gradients can easily flow. The LSTM can control the contents of the cell state using three **gates**: -->\n",
        "\n",
        "Our language model above is using an RNN variant called the LSTM (long short-term memory). The LSTM addresses a big problem with the vanilla RNN: vanishing and exploding gradients. This makes them very effective in encoding long-term dependencies. The key to the success of the LSTM is that it separates it's **hidden state** (i.e. the output that will go to the next layer) from an internal **cell state** ($\\mathbf{c}_t$) which can be thought of as a 'memory' for the LSTM. The cell state provides a path along which the gradients can easily flow. \n",
        "\n",
        "The LSTM can control the contents of the cell state using three **gates**. Gates are defined as sigmoid functions of the input and hidden states, all with their own weights and biases (much like a sigmoid linear layer):\n",
        "\n",
        "* The **forget** gate allows the LSTM to remove contents from the cell state.\n",
        "* The LSTM computes an update to the cell state using a `tanh` transformation from the inputs and hidden state. This is then modulated by the **input** gate.\n",
        "* Finally, an **output** gate controls which part of the cell state will be output as hidden state at each time step.\n",
        "\n",
        "The gates allow the LSTM to \"shut down\" the flow of information, which allows the network to only propagate useful information on its gradients. This makes it more capable of encoding long-term dependencies without risking them becoming unstable.\n",
        "\n",
        "A somewhat simplified version of the LSTM is the GRU (gated recurrent unit), which has also been used successfully in many applications. The GRU has only two gates, and does not have a separate cell state.\n",
        "\n",
        "If you want to know more you can read more about the LSTM, GRU, and other variants [here](http://colah.github.io/posts/2015-08-Understanding-LSTMs/).\n",
        "\n",
        "<!-- TODO: Put some exercises back? -->\n",
        "<!-- \n",
        "Looking at the diagrams below, which show the vanilla RNN, LSTM, and GRU, respectively, work with your partner to try to understand the description above and then answer the following **questions:**\n",
        "\n",
        "1. What does each of the gates in the GRU do?\n",
        "\n",
        "2. How does the GRU address the vanishing/exploding gradients problem? In other words, how does it allow the gradient to pass through unimpeded?\n",
        "\n",
        "If you get stuck or -->"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "dEr9hEqFiGx6"
      },
      "source": [
        "###Helper functions"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "3zXa95pBPUw3",
        "colab": {}
      },
      "source": [
        "def sample_with_temp(preds, temperature=1.0):\n",
        "  preds = np.asarray(preds).astype('float64')\n",
        "  preds = np.log(preds + 1e-10) / temperature\n",
        "  exp_preds = np.exp(preds)\n",
        "  preds = exp_preds / np.sum(exp_preds)\n",
        "  probas = np.random.multinomial(1, preds, 1)\n",
        "  return np.argmax(probas)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "AyH6U3er5fis",
        "colab": {}
      },
      "source": [
        "def shift_and_append(test_arr, next_item):\n",
        "        # txt = ''\n",
        "  '''Returns a copy of test_arr with items shifted one position to the left and\n",
        "     next_item appended.\n",
        "  '''\n",
        "  tmp = np.empty_like(test_arr)\n",
        "  tmp[:,:-1] = test_arr[:,1:]\n",
        "  tmp[:,-1] = next_item\n",
        "  return tmp\n",
        "\n",
        "## TEST the above function:\n",
        "test_arr = np.array([[1,2,3,4]])\n",
        "\n",
        "print(\"test_arr = {}\".format(test_arr))\n",
        "test_arr = shift_and_append(test_arr, 5)\n",
        "print(\"roll_arr(test_arr, 5) = {}\".format(test_arr))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "q9le2p0YxeYD",
        "colab": {}
      },
      "source": [
        "def sample_from_model(model,\n",
        "                      num_generate=400,\n",
        "                      prev_text=None,  # the text used to condition the model\n",
        "                      temperatures=[0.2, 0.5, 1.0, 1.2]):\n",
        "\n",
        "    if not prev_text:\n",
        "      # Select a text seed at random\n",
        "      start_index = random.randint(0, len(training_text) - max_len - 1)\n",
        "      while ((start_index < (len(training_text) - max_len - 1)) \n",
        "             and (training_text[start_index - 1] is not ' ')):\n",
        "        start_index += 1  # Advance to beginning of new word\n",
        "      prev_text = training_text[start_index: start_index + max_len]\n",
        "\n",
        "    if len(prev_text) != max_len:\n",
        "      print(\"`prev_text` must be of length `max_len`.\")\n",
        "      return\n",
        "\n",
        "    print('GENERATING TEXT WITH SEED: \\n\"' + prev_text + '\"')\n",
        "    prev_text_arr = np.array(\n",
        "      [[char2index[c] for c in prev_text]], dtype=np.int64)\n",
        "\n",
        "    for temp in temperatures:\n",
        "        print('==TEMPERATURE:', temp)\n",
        "        sys.stdout.write(prev_text)\n",
        "\n",
        "        # Start with the same sampled text for all temperatures\n",
        "        generated_text = prev_text\n",
        "        generated_text_arr = prev_text_arr\n",
        "\n",
        "        # Now generate this many characters\n",
        "        for i in range(num_generate):\n",
        "\n",
        "            # Get the output softmax given the conditioning text\n",
        "            #prev_text = generated_text_enc[np.newaxis,:]\n",
        "            preds = model.predict(generated_text_arr, verbose=0)[0]\n",
        "\n",
        "            next_index = sample_with_temp(preds, temp)\n",
        "            next_char = index2char[next_index]\n",
        "            #print(next_index, end=' -> ')\n",
        "            generated_text += next_char\n",
        "            generated_text = generated_text[1:]\n",
        "\n",
        "            # Left-shift and add into encoded array\n",
        "            generated_text_arr = shift_and_append(generated_text_arr, next_index)\n",
        "            print(next_char, end='')\n",
        "        print()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "1uZrJI9fmXb8"
      },
      "source": [
        "### Try the model with random weights\n",
        "Let's sample for our model before training it, so we have an idea of the text it generates with the randomly initalized weights (spoiler: you should see absolute nonsense!)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "Lhg3ft2ptqQw",
        "colab": {}
      },
      "source": [
        "sample_from_model(model)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "a78CrsaMiKrA"
      },
      "source": [
        "###Train the model\n",
        "\n",
        "Let's train the model! The code below will train the model on a subset of the available data, and then generate from the model every `sample_every` number of batches.\n",
        "\n",
        "To generate from the model, we use `model.predict()` on a sequence of `max_len` conditioning characters to produce an output distribution over `vocab_size` characters. We then sample one character from this distribution and shift everything up by one and append the new characters. By repeating this, we can generate text from the (partially-trained) model.\n",
        "\n",
        "**NOTE**: \n",
        "* It takes a while to train a model that starts generating anything resembling the Shapespeare text! In general it should start getting the rough structure in place around the 100K training example mark (examples, not batches). But to generate any meaningful words will need several hundred thousand examples.\n",
        "* We sample with *temperature*. This is a way to sharpen or flatten the probabilities produced by the model. By lowering the temperature, we emphasize the modes of the predicted distribution, and by increasing the temperature, we flatten the modes (tends towards uniform). Higher temperatures therefore encourage the model to be more 'creative', instead of always choosing the most likely next character."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "0RcFKgkdPXuI",
        "colab": {}
      },
      "source": [
        "batch_size = 128\n",
        "total_num_batches = X.shape[0] // batch_size\n",
        "sample_every = 256  # Train on this many batches, then generate something\n",
        "\n",
        "print(\"Training on {} batches in total.\".format(total_num_batches))\n",
        "\n",
        "for cur_batch in range(0, total_num_batches, sample_every):\n",
        "    print('TRAINING ON BATCH {} to {} (example {} to {})'.format(\n",
        "      cur_batch, cur_batch + sample_every,\n",
        "      cur_batch * batch_size, (cur_batch + sample_every) * batch_size)\n",
        "    )\n",
        "\n",
        "    X_batch = X[batch_size * cur_batch : batch_size * (cur_batch + sample_every), :]\n",
        "    Y_batch = Y[batch_size * cur_batch : batch_size * (cur_batch + sample_every), :]\n",
        "\n",
        "    '''\n",
        "    # Show the first 5 examples to make sure we're not training on garbage\n",
        "    print(\"X_batch.shape = {}\".format(X_batch.shape))\n",
        "    print(\"Y_batch.shape = {}\".format(Y_batch.shape))\n",
        "    print(\"FIRST 5 EXAMPLES:\")\n",
        "    for num in range(5):\n",
        "      in_seq = [index2char[int(indx)] for indx in np.nditer(X_batch[num, :])]\n",
        "      next_char = index2char[Y_batch[num, 0]]\n",
        "      print(str(num) + '. ' + ''.join(in_seq) + '-->' + next_char)\n",
        "    '''\n",
        "\n",
        "    model.fit(X_batch, Y_batch,\n",
        "              batch_size=batch_size,\n",
        "              epochs=1,\n",
        "              verbose=1)\n",
        "\n",
        "    print(\"GENERATING SOME RANDOM TEXT FROM THE MODEL\")\n",
        "    sample_from_model(model)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "w3C-AIU18HFe"
      },
      "source": [
        "**NOTE**: Even after training has stopped you can still generate from the (partially trained) model as follows:"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "5z2gVe_QNBU4"
      },
      "source": [
        "Want to see what the model yields after much more training? Here we provide pre-trained models for these tasks:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "uTdH78ADMwq-",
        "colab": {}
      },
      "source": [
        "!pip install -q googledrivedownloader\n",
        "from google_drive_downloader import GoogleDriveDownloader as gdd\n",
        "\n",
        "params = dict(\n",
        "    en=('1OTpvsXVQ_k754hlVgZB5yk-K8wuy0mMK', 'shakespeare_final.h5'),\n",
        "    sp=('1tU_IFP_6L9VfjdqGX3Q9Y6aQTB01n_om', 'quijote_final.h5')\n",
        ")\n",
        "file_id, filename = params[LANGUAGE]\n",
        "gdd.download_file_from_google_drive(\n",
        "    file_id=file_id, dest_path='./{}'.format(filename))\n",
        "model.load_weights(filename)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "FNMzTgY9M8Zm",
        "colab": {}
      },
      "source": [
        "sample_from_model(model)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "UbdLbn_xRe21"
      },
      "source": [
        "###IMPORTANT NOTES\n",
        "* Even if you stop training the model weights are persistant. If you resume training it will start where you left off. \n",
        "* To reset the weights, you need to recompile the model.\n",
        "* Sampling is **stochastic** (random), so you'll get new outputs every time you rerun the sampling code.\n",
        "\n",
        "### YOUR TASKS: \n",
        "* [**ALL**] Read the generations from your model in a funny voice to your neighbour.\n",
        "* [**ALL**] Increase `max_len` and regenerate the data and retrain the model.\n",
        " * What's the effect on training speed as you double `max_len`. Can you explain why?\n",
        " * Do you notice any effect on the quality of the model? Can you explain why?\n",
        "* [**ALL**] Set the max_len to be roughly the length of half a word; one word; two words... What kind of samples do these models generate? Explain how they go wrong.\n",
        "* [**ALL**] Change `embedding_dim` and the hidden size of the LSTM and observe the effect on training speed and quality.\n",
        "* [**INTERMEDIATE**] Change the dropout rates & retrain the model. \n",
        "  * What types of dropout do we get for recurrent models? \n",
        "  * What's the effect on the text quality?\n",
        "* [**ADVANCED**] Implement the \"teacher forcing\" training methodology, where the net must predict the entire output sequence shifted forward by one character, instead of just the next character. Compare the output of a model trained with teacher forcing versus the per-character model, given a similar training time. Is it fair to say that teacher forcing is a more efficient training methodology?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "TPiFyajJtDmj"
      },
      "source": [
        "**IMPORTANT: Please fill out the exit ticket form before you leave the practical: https://forms.gle/uzjavhQ138g9H1Wq8**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "REZzoUwjHkZW"
      },
      "source": [
        "##Further reading\n",
        "\n",
        "* https://distill.pub/2016/augmented-rnns/\n",
        "* https://distill.pub/2017/ctc/\n",
        "* https://algotravelling.com/en/machine-learning-fun-part-5/\n",
        "* http://www.wildml.com/2015/09/recurrent-neural-networks-tutorial-part-1-introduction-to-rnns/"
      ]
    }
  ]
}