for datascience symposium

[notebooks.git] / rnn.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    },
    "colab": {
      "name": "rnn.ipynb",
      "provenance": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "am_B9iKqXsGX"
      },
      "source": [
        "The following additional libraries are needed to run this\n",
        "notebook. Note that running on Colab is experimental, please report a Github\n",
        "issue if you have any problem."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "joeZTMPsXsGb",
        "outputId": "29116f84-4616-454e-dd7b-7d5476bd34cd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "!pip install d2l==0.17.0\n",
        "!pip install -U mxnet-cu101==1.7.0\n"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting d2l==0.17.0\n",
            "  Downloading d2l-0.17.0-py3-none-any.whl (83 kB)\n",
            "\u001b[?25l\r\u001b[K     |████                            | 10 kB 12.2 MB/s eta 0:00:01\r\u001b[K     |███████▉                        | 20 kB 9.4 MB/s eta 0:00:01\r\u001b[K     |███████████▉                    | 30 kB 6.6 MB/s eta 0:00:01\r\u001b[K     |███████████████▊                | 40 kB 6.4 MB/s eta 0:00:01\r\u001b[K     |███████████████████▊            | 51 kB 3.7 MB/s eta 0:00:01\r\u001b[K     |███████████████████████▋        | 61 kB 3.8 MB/s eta 0:00:01\r\u001b[K     |███████████████████████████▋    | 71 kB 3.7 MB/s eta 0:00:01\r\u001b[K     |███████████████████████████████▌| 81 kB 4.0 MB/s eta 0:00:01\r\u001b[K     |████████████████████████████████| 83 kB 664 kB/s \n",
            "\u001b[?25hRequirement already satisfied: jupyter in /usr/local/lib/python3.7/dist-packages (from d2l==0.17.0) (1.0.0)\n",
            "Requirement already satisfied: pandas in /usr/local/lib/python3.7/dist-packages (from d2l==0.17.0) (1.1.5)\n",
            "Requirement already satisfied: requests in /usr/local/lib/python3.7/dist-packages (from d2l==0.17.0) (2.23.0)\n",
            "Requirement already satisfied: numpy in /usr/local/lib/python3.7/dist-packages (from d2l==0.17.0) (1.19.5)\n",
            "Requirement already satisfied: matplotlib in /usr/local/lib/python3.7/dist-packages (from d2l==0.17.0) (3.2.2)\n",
            "Requirement already satisfied: notebook in /usr/local/lib/python3.7/dist-packages (from jupyter->d2l==0.17.0) (5.3.1)\n",
            "Requirement already satisfied: qtconsole in /usr/local/lib/python3.7/dist-packages (from jupyter->d2l==0.17.0) (5.1.1)\n",
            "Requirement already satisfied: ipywidgets in /usr/local/lib/python3.7/dist-packages (from jupyter->d2l==0.17.0) (7.6.5)\n",
            "Requirement already satisfied: jupyter-console in /usr/local/lib/python3.7/dist-packages (from jupyter->d2l==0.17.0) (5.2.0)\n",
            "Requirement already satisfied: nbconvert in /usr/local/lib/python3.7/dist-packages (from jupyter->d2l==0.17.0) (5.6.1)\n",
            "Requirement already satisfied: ipykernel in /usr/local/lib/python3.7/dist-packages (from jupyter->d2l==0.17.0) (4.10.1)\n",
            "Requirement already satisfied: jupyter-client in /usr/local/lib/python3.7/dist-packages (from ipykernel->jupyter->d2l==0.17.0) (5.3.5)\n",
            "Requirement already satisfied: tornado>=4.0 in /usr/local/lib/python3.7/dist-packages (from ipykernel->jupyter->d2l==0.17.0) (5.1.1)\n",
            "Requirement already satisfied: traitlets>=4.1.0 in /usr/local/lib/python3.7/dist-packages (from ipykernel->jupyter->d2l==0.17.0) (5.1.0)\n",
            "Requirement already satisfied: ipython>=4.0.0 in /usr/local/lib/python3.7/dist-packages (from ipykernel->jupyter->d2l==0.17.0) (5.5.0)\n",
            "Requirement already satisfied: decorator in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (4.4.2)\n",
            "Requirement already satisfied: prompt-toolkit<2.0.0,>=1.0.4 in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (1.0.18)\n",
            "Requirement already satisfied: setuptools>=18.5 in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (57.4.0)\n",
            "Requirement already satisfied: pexpect in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (4.8.0)\n",
            "Requirement already satisfied: pickleshare in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (0.7.5)\n",
            "Requirement already satisfied: simplegeneric>0.8 in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (0.8.1)\n",
            "Requirement already satisfied: pygments in /usr/local/lib/python3.7/dist-packages (from ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (2.6.1)\n",
            "Requirement already satisfied: wcwidth in /usr/local/lib/python3.7/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (0.2.5)\n",
            "Requirement already satisfied: six>=1.9.0 in /usr/local/lib/python3.7/dist-packages (from prompt-toolkit<2.0.0,>=1.0.4->ipython>=4.0.0->ipykernel->jupyter->d2l==0.17.0) (1.15.0)\n",
            "Requirement already satisfied: nbformat>=4.2.0 in /usr/local/lib/python3.7/dist-packages (from ipywidgets->jupyter->d2l==0.17.0) (5.1.3)\n",
            "Requirement already satisfied: ipython-genutils~=0.2.0 in /usr/local/lib/python3.7/dist-packages (from ipywidgets->jupyter->d2l==0.17.0) (0.2.0)\n",
            "Requirement already satisfied: widgetsnbextension~=3.5.0 in /usr/local/lib/python3.7/dist-packages (from ipywidgets->jupyter->d2l==0.17.0) (3.5.1)\n",
            "Requirement already satisfied: jupyterlab-widgets>=1.0.0 in /usr/local/lib/python3.7/dist-packages (from ipywidgets->jupyter->d2l==0.17.0) (1.0.2)\n",
            "Requirement already satisfied: jsonschema!=2.5.0,>=2.4 in /usr/local/lib/python3.7/dist-packages (from nbformat>=4.2.0->ipywidgets->jupyter->d2l==0.17.0) (2.6.0)\n",
            "Requirement already satisfied: jupyter-core in /usr/local/lib/python3.7/dist-packages (from nbformat>=4.2.0->ipywidgets->jupyter->d2l==0.17.0) (4.8.1)\n",
            "Requirement already satisfied: jinja2 in /usr/local/lib/python3.7/dist-packages (from notebook->jupyter->d2l==0.17.0) (2.11.3)\n",
            "Requirement already satisfied: terminado>=0.8.1 in /usr/local/lib/python3.7/dist-packages (from notebook->jupyter->d2l==0.17.0) (0.12.1)\n",
            "Requirement already satisfied: Send2Trash in /usr/local/lib/python3.7/dist-packages (from notebook->jupyter->d2l==0.17.0) (1.8.0)\n",
            "Requirement already satisfied: pyzmq>=13 in /usr/local/lib/python3.7/dist-packages (from jupyter-client->ipykernel->jupyter->d2l==0.17.0) (22.3.0)\n",
            "Requirement already satisfied: python-dateutil>=2.1 in /usr/local/lib/python3.7/dist-packages (from jupyter-client->ipykernel->jupyter->d2l==0.17.0) (2.8.2)\n",
            "Requirement already satisfied: ptyprocess in /usr/local/lib/python3.7/dist-packages (from terminado>=0.8.1->notebook->jupyter->d2l==0.17.0) (0.7.0)\n",
            "Requirement already satisfied: MarkupSafe>=0.23 in /usr/local/lib/python3.7/dist-packages (from jinja2->notebook->jupyter->d2l==0.17.0) (2.0.1)\n",
            "Requirement already satisfied: cycler>=0.10 in /usr/local/lib/python3.7/dist-packages (from matplotlib->d2l==0.17.0) (0.10.0)\n",
            "Requirement already satisfied: kiwisolver>=1.0.1 in /usr/local/lib/python3.7/dist-packages (from matplotlib->d2l==0.17.0) (1.3.2)\n",
            "Requirement already satisfied: pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1 in /usr/local/lib/python3.7/dist-packages (from matplotlib->d2l==0.17.0) (2.4.7)\n",
            "Requirement already satisfied: bleach in /usr/local/lib/python3.7/dist-packages (from nbconvert->jupyter->d2l==0.17.0) (4.1.0)\n",
            "Requirement already satisfied: entrypoints>=0.2.2 in /usr/local/lib/python3.7/dist-packages (from nbconvert->jupyter->d2l==0.17.0) (0.3)\n",
            "Requirement already satisfied: defusedxml in /usr/local/lib/python3.7/dist-packages (from nbconvert->jupyter->d2l==0.17.0) (0.7.1)\n",
            "Requirement already satisfied: mistune<2,>=0.8.1 in /usr/local/lib/python3.7/dist-packages (from nbconvert->jupyter->d2l==0.17.0) (0.8.4)\n",
            "Requirement already satisfied: testpath in /usr/local/lib/python3.7/dist-packages (from nbconvert->jupyter->d2l==0.17.0) (0.5.0)\n",
            "Requirement already satisfied: pandocfilters>=1.4.1 in /usr/local/lib/python3.7/dist-packages (from nbconvert->jupyter->d2l==0.17.0) (1.5.0)\n",
            "Requirement already satisfied: packaging in /usr/local/lib/python3.7/dist-packages (from bleach->nbconvert->jupyter->d2l==0.17.0) (21.0)\n",
            "Requirement already satisfied: webencodings in /usr/local/lib/python3.7/dist-packages (from bleach->nbconvert->jupyter->d2l==0.17.0) (0.5.1)\n",
            "Requirement already satisfied: pytz>=2017.2 in /usr/local/lib/python3.7/dist-packages (from pandas->d2l==0.17.0) (2018.9)\n",
            "Requirement already satisfied: qtpy in /usr/local/lib/python3.7/dist-packages (from qtconsole->jupyter->d2l==0.17.0) (1.11.2)\n",
            "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.7/dist-packages (from requests->d2l==0.17.0) (1.24.3)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.7/dist-packages (from requests->d2l==0.17.0) (2021.5.30)\n",
            "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.7/dist-packages (from requests->d2l==0.17.0) (3.0.4)\n",
            "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.7/dist-packages (from requests->d2l==0.17.0) (2.10)\n",
            "Installing collected packages: d2l\n",
            "Successfully installed d2l-0.17.0\n",
            "Collecting mxnet-cu101==1.7.0\n",
            "  Downloading mxnet_cu101-1.7.0-py2.py3-none-manylinux2014_x86_64.whl (846.0 MB)\n",
            "\u001b[K     |███████████████████████████████▌| 834.1 MB 1.1 MB/s eta 0:00:11tcmalloc: large alloc 1147494400 bytes == 0x559d9b964000 @  0x7f01279d4615 0x559d632ef4cc 0x559d633cf47a 0x559d632f22ed 0x559d633e3e1d 0x559d63365e99 0x559d633609ee 0x559d632f3bda 0x559d63365d00 0x559d633609ee 0x559d632f3bda 0x559d63362737 0x559d633e4c66 0x559d63361daf 0x559d633e4c66 0x559d63361daf 0x559d633e4c66 0x559d63361daf 0x559d632f4039 0x559d63337409 0x559d632f2c52 0x559d63365c25 0x559d633609ee 0x559d632f3bda 0x559d63362737 0x559d633609ee 0x559d632f3bda 0x559d63361915 0x559d632f3afa 0x559d63361c0d 0x559d633609ee\n",
            "\u001b[K     |████████████████████████████████| 846.0 MB 20 kB/s \n",
            "\u001b[?25hCollecting graphviz<0.9.0,>=0.8.1\n",
            "  Downloading graphviz-0.8.4-py2.py3-none-any.whl (16 kB)\n",
            "Requirement already satisfied: requests<3,>=2.20.0 in /usr/local/lib/python3.7/dist-packages (from mxnet-cu101==1.7.0) (2.23.0)\n",
            "Requirement already satisfied: numpy<2.0.0,>1.16.0 in /usr/local/lib/python3.7/dist-packages (from mxnet-cu101==1.7.0) (1.19.5)\n",
            "Requirement already satisfied: idna<3,>=2.5 in /usr/local/lib/python3.7/dist-packages (from requests<3,>=2.20.0->mxnet-cu101==1.7.0) (2.10)\n",
            "Requirement already satisfied: certifi>=2017.4.17 in /usr/local/lib/python3.7/dist-packages (from requests<3,>=2.20.0->mxnet-cu101==1.7.0) (2021.5.30)\n",
            "Requirement already satisfied: chardet<4,>=3.0.2 in /usr/local/lib/python3.7/dist-packages (from requests<3,>=2.20.0->mxnet-cu101==1.7.0) (3.0.4)\n",
            "Requirement already satisfied: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /usr/local/lib/python3.7/dist-packages (from requests<3,>=2.20.0->mxnet-cu101==1.7.0) (1.24.3)\n",
            "Installing collected packages: graphviz, mxnet-cu101\n",
            "  Attempting uninstall: graphviz\n",
            "    Found existing installation: graphviz 0.10.1\n",
            "    Uninstalling graphviz-0.10.1:\n",
            "      Successfully uninstalled graphviz-0.10.1\n",
            "Successfully installed graphviz-0.8.4 mxnet-cu101-1.7.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "origin_pos": 0,
        "id": "KEZ2fE5vXsGc"
      },
      "source": [
        "# Recurrent Neural Networks\n",
        ":label:`sec_rnn`\n",
        "\n",
        "\n",
        "In :numref:`sec_language_model` we introduced $n$-gram models, where the conditional probability of word $x_t$ at time step $t$ only depends on the $n-1$ previous words.\n",
        "If we want to incorporate the possible effect of words earlier than time step $t-(n-1)$ on $x_t$,\n",
        "we need to increase $n$.\n",
        "However, the number of model parameters would also increase exponentially with it, as we need to store $|\\mathcal{V}|^n$ numbers for a vocabulary set $\\mathcal{V}$.\n",
        "Hence, rather than modeling $P(x_t \\mid x_{t-1}, \\ldots, x_{t-n+1})$ it is preferable to use a latent variable model:\n",
        "\n",
        "$$P(x_t \\mid x_{t-1}, \\ldots, x_1) \\approx P(x_t \\mid h_{t-1}),$$\n",
        "\n",
        "where $h_{t-1}$ is a *hidden state* (also known as a hidden variable) that stores the sequence information up to time step $t-1$.\n",
        "In general,\n",
        "the hidden state at any time step $t$ could be computed based on both the current input $x_{t}$ and the previous hidden state $h_{t-1}$:\n",
        "\n",
        "$$h_t = f(x_{t}, h_{t-1}).$$\n",
        ":eqlabel:`eq_ht_xt`\n",
        "\n",
        "For a sufficiently powerful function $f$ in :eqref:`eq_ht_xt`, the latent variable model is not an approximation. After all, $h_t$ may simply store all the data it has observed so far.\n",
        "However, it could potentially make both computation and storage expensive.\n",
        "\n",
        "Recall that we have discussed hidden layers with hidden units in :numref:`chap_perceptrons`.\n",
        "It is noteworthy that\n",
        "hidden layers and hidden states refer to two very different concepts.\n",
        "Hidden layers are, as explained, layers that are hidden from view on the path from input to output.\n",
        "Hidden states are technically speaking *inputs* to whatever we do at a given step,\n",
        "and they can only be computed by looking at data at previous time steps.\n",
        "\n",
        "*Recurrent neural networks* (RNNs) are neural networks with hidden states. Before introducing the RNN model, we first revisit the MLP model introduced in :numref:`sec_mlp`.\n",
        "\n",
        "## Neural Networks without Hidden States\n",
        "\n",
        "Let us take a look at an MLP with a single hidden layer.\n",
        "Let the hidden layer's activation function be $\\phi$.\n",
        "Given a minibatch of examples $\\mathbf{X} \\in \\mathbb{R}^{n \\times d}$ with batch size $n$ and $d$ inputs, the hidden layer's output $\\mathbf{H} \\in \\mathbb{R}^{n \\times h}$ is calculated as\n",
        "\n",
        "$$\\mathbf{H} = \\phi(\\mathbf{X} \\mathbf{W}_{xh} + \\mathbf{b}_h).$$\n",
        ":eqlabel:`rnn_h_without_state`\n",
        "\n",
        "In :eqref:`rnn_h_without_state`, we have the weight parameter $\\mathbf{W}_{xh} \\in \\mathbb{R}^{d \\times h}$, the bias parameter $\\mathbf{b}_h \\in \\mathbb{R}^{1 \\times h}$, and the number of hidden units $h$, for the hidden layer.\n",
        "Thus, broadcasting (see :numref:`subsec_broadcasting`) is applied during the summation.\n",
        "Next, the hidden variable $\\mathbf{H}$ is used as the input of the output layer. The output layer is given by\n",
        "\n",
        "$$\\mathbf{O} = \\mathbf{H} \\mathbf{W}_{hq} + \\mathbf{b}_q,$$\n",
        "\n",
        "where $\\mathbf{O} \\in \\mathbb{R}^{n \\times q}$ is the output variable, $\\mathbf{W}_{hq} \\in \\mathbb{R}^{h \\times q}$ is the weight parameter, and $\\mathbf{b}_q \\in \\mathbb{R}^{1 \\times q}$ is the bias parameter of the output layer.  If it is a classification problem, we can use $\\text{softmax}(\\mathbf{O})$ to compute the probability distribution of the output categories.\n",
        "\n",
        "This is entirely analogous to the regression problem we solved previously in :numref:`sec_sequence`, hence we omit details.\n",
        "Suffice it to say that we can pick feature-label pairs at random and learn the parameters of our network via automatic differentiation and stochastic gradient descent.\n",
        "\n",
        "## Recurrent Neural Networks with Hidden States\n",
        ":label:`subsec_rnn_w_hidden_states`\n",
        "\n",
        "Matters are entirely different when we have hidden states. Let us look at the structure in some more detail.\n",
        "\n",
        "Assume that we have\n",
        "a minibatch of inputs\n",
        "$\\mathbf{X}_t \\in \\mathbb{R}^{n \\times d}$\n",
        "at time step $t$.\n",
        "In other words,\n",
        "for a minibatch of $n$ sequence examples,\n",
        "each row of $\\mathbf{X}_t$ corresponds to one example at time step $t$ from the sequence.\n",
        "Next,\n",
        "denote by $\\mathbf{H}_t  \\in \\mathbb{R}^{n \\times h}$ the hidden variable of time step $t$.\n",
        "Unlike the MLP, here we save the hidden variable $\\mathbf{H}_{t-1}$ from the previous time step and introduce a new weight parameter $\\mathbf{W}_{hh} \\in \\mathbb{R}^{h \\times h}$ to describe how to use the hidden variable of the previous time step in the current time step. Specifically, the calculation of the hidden variable of the current time step is determined by the input of the current time step together with the hidden variable of the previous time step:\n",
        "\n",
        "$$\\mathbf{H}_t = \\phi(\\mathbf{X}_t \\mathbf{W}_{xh} + \\mathbf{H}_{t-1} \\mathbf{W}_{hh}  + \\mathbf{b}_h).$$\n",
        ":eqlabel:`rnn_h_with_state`\n",
        "\n",
        "Compared with :eqref:`rnn_h_without_state`, :eqref:`rnn_h_with_state` adds one more term $\\mathbf{H}_{t-1} \\mathbf{W}_{hh}$ and thus\n",
        "instantiates :eqref:`eq_ht_xt`.\n",
        "From the relationship between hidden variables $\\mathbf{H}_t$ and $\\mathbf{H}_{t-1}$ of adjacent time steps,\n",
        "we know that these variables captured and retained the sequence's historical information up to their current time step, just like the state or memory of the neural network's current time step. Therefore, such a hidden variable is called a *hidden state*.\n",
        "Since the hidden state uses the same definition of the previous time step in the current time step, the computation of :eqref:`rnn_h_with_state` is *recurrent*. Hence, neural networks with hidden states\n",
        "based on recurrent computation are named\n",
        "*recurrent neural networks*.\n",
        "Layers that perform\n",
        "the computation of :eqref:`rnn_h_with_state`\n",
        "in RNNs\n",
        "are called *recurrent layers*.\n",
        "\n",
        "\n",
        "There are many different ways for constructing RNNs.\n",
        "RNNs with a hidden state defined by :eqref:`rnn_h_with_state` are very common.\n",
        "For time step $t$,\n",
        "the output of the output layer is similar to the computation in the MLP:\n",
        "\n",
        "$$\\mathbf{O}_t = \\mathbf{H}_t \\mathbf{W}_{hq} + \\mathbf{b}_q.$$\n",
        "\n",
        "Parameters of the RNN\n",
        "include the weights $\\mathbf{W}_{xh} \\in \\mathbb{R}^{d \\times h}, \\mathbf{W}_{hh} \\in \\mathbb{R}^{h \\times h}$,\n",
        "and the bias $\\mathbf{b}_h \\in \\mathbb{R}^{1 \\times h}$\n",
        "of the hidden layer,\n",
        "together with the weights $\\mathbf{W}_{hq} \\in \\mathbb{R}^{h \\times q}$\n",
        "and the bias $\\mathbf{b}_q \\in \\mathbb{R}^{1 \\times q}$\n",
        "of the output layer.\n",
        "It is worth mentioning that\n",
        "even at different time steps,\n",
        "RNNs always use these model parameters.\n",
        "Therefore, the parameterization cost of an RNN\n",
        "does not grow as the number of time steps increases.\n",
        "\n",
        ":numref:`fig_rnn` illustrates the computational logic of an RNN at three adjacent time steps.\n",
        "At any time step $t$,\n",
        "the computation of the hidden state can be treated as:\n",
        "(i) concatenating the input $\\mathbf{X}_t$ at the current time step $t$ and the hidden state $\\mathbf{H}_{t-1}$ at the previous time step $t-1$;\n",
        "(ii) feeding the concatenation result into a fully-connected layer with the activation function $\\phi$.\n",
        "The output of such a fully-connected layer is the hidden state $\\mathbf{H}_t$ of the current time step $t$.\n",
        "In this case,\n",
        "the model parameters are the concatenation of $\\mathbf{W}_{xh}$ and $\\mathbf{W}_{hh}$, and a bias of $\\mathbf{b}_h$, all from :eqref:`rnn_h_with_state`.\n",
        "The hidden state of the current time step $t$, $\\mathbf{H}_t$, will participate in computing the hidden state $\\mathbf{H}_{t+1}$ of the next time step $t+1$.\n",
        "What is more, $\\mathbf{H}_t$ will also be\n",
        "fed into the fully-connected output layer\n",
        "to compute the output\n",
        "$\\mathbf{O}_t$ of the current time step $t$.\n",
        "\n",
        "![An RNN with a hidden state.](http://d2l.ai/_images/rnn.svg)\n",
        ":label:`fig_rnn`\n",
        "\n",
        "We just mentioned that the calculation of $\\mathbf{X}_t \\mathbf{W}_{xh} + \\mathbf{H}_{t-1} \\mathbf{W}_{hh}$ for the hidden state is equivalent to\n",
        "matrix multiplication of\n",
        "concatenation of $\\mathbf{X}_t$ and $\\mathbf{H}_{t-1}$\n",
        "and\n",
        "concatenation of $\\mathbf{W}_{xh}$ and $\\mathbf{W}_{hh}$.\n",
        "Though this can be proven in mathematics,\n",
        "in the following we just use a simple code snippet to show this.\n",
        "To begin with,\n",
        "we define matrices `X`, `W_xh`, `H`, and `W_hh`, whose shapes are (3, 1), (1, 4), (3, 4), and (4, 4), respectively.\n",
        "Multiplying `X` by `W_xh`, and `H` by `W_hh`, respectively, and then adding these two multiplications,\n",
        "we obtain a matrix of shape (3, 4).\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "origin_pos": 1,
        "tab": [
          "mxnet"
        ],
        "id": "rw0ShhAhXsGe"
      },
      "source": [
        "from mxnet import np, npx\n",
        "from d2l import mxnet as d2l\n",
        "\n",
        "npx.set_np()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "origin_pos": 4,
        "tab": [
          "mxnet"
        ],
        "id": "FCWF9xdqXsGe",
        "outputId": "b2cbc992-be6b-41c5-dd5c-e35f72eb2a25"
      },
      "source": [
        "X, W_xh = np.random.normal(0, 1, (3, 1)), np.random.normal(0, 1, (1, 4))\n",
        "H, W_hh = np.random.normal(0, 1, (3, 4)), np.random.normal(0, 1, (4, 4))\n",
        "np.dot(X, W_xh) + np.dot(H, W_hh)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[-0.21952868,  4.256434  ,  4.5812645 , -5.344988  ],\n",
              "       [ 3.4478583 , -3.0177274 , -1.6777471 ,  7.535347  ],\n",
              "       [ 2.239007  ,  1.4199957 ,  4.744728  , -8.421293  ]])"
            ]
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "origin_pos": 6,
        "id": "9n2kju1SXsGf"
      },
      "source": [
        "Now we concatenate the matrices `X` and `H`\n",
        "along columns (axis 1),\n",
        "and the matrices\n",
        "`W_xh` and `W_hh` along rows (axis 0).\n",
        "These two concatenations\n",
        "result in\n",
        "matrices of shape (3, 5)\n",
        "and of shape (5, 4), respectively.\n",
        "Multiplying these two concatenated matrices,\n",
        "we obtain the same output matrix of shape (3, 4)\n",
        "as above.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "origin_pos": 7,
        "tab": [
          "mxnet"
        ],
        "id": "veGhxnrkXsGf",
        "outputId": "ab21230c-7c03-49de-dbe1-d5b13457b002"
      },
      "source": [
        "np.dot(np.concatenate((X, H), 1), np.concatenate((W_xh, W_hh), 0))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[-0.2195287,  4.256434 ,  4.5812645, -5.344988 ],\n",
              "       [ 3.4478583, -3.0177271, -1.677747 ,  7.535347 ],\n",
              "       [ 2.2390068,  1.4199957,  4.744728 , -8.421294 ]])"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "origin_pos": 8,
        "id": "IJeB_1DXXsGg"
      },
      "source": [
        "## RNN-based Character-Level Language Models\n",
        "\n",
        "Recall that for language modeling in :numref:`sec_language_model`,\n",
        "we aim to predict the next token based on\n",
        "the current and past tokens,\n",
        "thus we shift the original sequence by one token\n",
        "as the labels.\n",
        "Bengio et al. first proposed\n",
        "to use a neural network for language modeling :cite:`Bengio.Ducharme.Vincent.ea.2003`.\n",
        "In the following we illustrate how RNNs can be used to build a language model.\n",
        "Let the minibatch size be one, and the sequence of the text be \"machine\".\n",
        "To simplify training in subsequent sections,\n",
        "we tokenize text into characters rather than words\n",
        "and consider a *character-level language model*.\n",
        ":numref:`fig_rnn_train` demonstrates how to predict the next character based on the current and previous characters via an RNN for character-level language modeling.\n",
        "\n",
        "![A character-level language model based on the RNN. The input and label sequences are \"machin\" and \"achine\", respectively.](https://github.com/d2l-ai/d2l-en-colab/blob/master/img/rnn-train.svg?raw=1)\n",
        ":label:`fig_rnn_train`\n",
        "\n",
        "During the training process,\n",
        "we run a softmax operation on the output from the output layer for each time step, and then use the cross-entropy loss to compute the error between the model output and the label.\n",
        "Due to the recurrent computation of the hidden state in the hidden layer, the output of time step 3 in :numref:`fig_rnn_train`,\n",
        "$\\mathbf{O}_3$, is determined by the text sequence \"m\", \"a\", and \"c\". Since the next character of the sequence in the training data is \"h\", the loss of time step 3 will depend on the probability distribution of the next character generated based on the feature sequence \"m\", \"a\", \"c\" and the label \"h\" of this time step.\n",
        "\n",
        "In practice, each token is represented by a $d$-dimensional vector, and we use a batch size $n>1$. Therefore, the input $\\mathbf X_t$ at time step $t$ will be a $n\\times d$ matrix, which is identical to what we discussed in :numref:`subsec_rnn_w_hidden_states`.\n",
        "\n",
        "\n",
        "## Perplexity\n",
        ":label:`subsec_perplexity`\n",
        "\n",
        "Last, let us discuss about how to measure the language model quality, which will be used to evaluate our RNN-based models in the subsequent sections.\n",
        "One way is to check how surprising the text is.\n",
        "A good language model is able to predict with\n",
        "high-accuracy tokens that what we will see next.\n",
        "Consider the following continuations of the phrase \"It is raining\", as proposed by different language models:\n",
        "\n",
        "1. \"It is raining outside\"\n",
        "1. \"It is raining banana tree\"\n",
        "1. \"It is raining piouw;kcj pwepoiut\"\n",
        "\n",
        "In terms of quality, example 1 is clearly the best. The words are sensible and logically coherent.\n",
        "While it might not quite accurately reflect which word follows semantically (\"in San Francisco\" and \"in winter\" would have been perfectly reasonable extensions), the model is able to capture which kind of word follows.\n",
        "Example 2 is considerably worse by producing a nonsensical extension. Nonetheless, at least the model has learned how to spell words and some degree of correlation between words. Last, example 3 indicates a poorly trained model that does not fit data properly.\n",
        "\n",
        "We might measure the quality of the model by computing  the likelihood of the sequence.\n",
        "Unfortunately this is a number that is hard to understand and difficult to compare.\n",
        "After all, shorter sequences are much more likely to occur than the longer ones,\n",
        "hence evaluating the model on Tolstoy's magnum opus\n",
        "*War and Peace* will inevitably produce a much smaller likelihood than, say, on Saint-Exupery's novella *The Little Prince*. What is missing is the equivalent of an average.\n",
        "\n",
        "Information theory comes handy here.\n",
        "We have defined entropy, surprisal, and cross-entropy\n",
        "when we introduced the softmax regression\n",
        "(:numref:`subsec_info_theory_basics`)\n",
        "and more of information theory is discussed in the [online appendix on information theory](https://d2l.ai/chapter_appendix-mathematics-for-deep-learning/information-theory.html).\n",
        "If we want to compress text, we can ask about\n",
        "predicting the next token given the current set of tokens.\n",
        "A better language model should allow us to predict the next token more accurately.\n",
        "Thus, it should allow us to spend fewer bits in compressing the sequence.\n",
        "So we can measure it by the cross-entropy loss averaged\n",
        "over all the $n$ tokens of a sequence:\n",
        "\n",
        "$$\\frac{1}{n} \\sum_{t=1}^n -\\log P(x_t \\mid x_{t-1}, \\ldots, x_1),$$\n",
        ":eqlabel:`eq_avg_ce_for_lm`\n",
        "\n",
        "where $P$ is given by a language model and $x_t$ is the actual token observed at time step $t$ from the sequence.\n",
        "This makes the performance on documents of different lengths comparable. For historical reasons, scientists in natural language processing prefer to use a quantity called *perplexity*. In a nutshell, it is the exponential of :eqref:`eq_avg_ce_for_lm`:\n",
        "\n",
        "$$\\exp\\left(-\\frac{1}{n} \\sum_{t=1}^n \\log P(x_t \\mid x_{t-1}, \\ldots, x_1)\\right).$$\n",
        "\n",
        "Perplexity can be best understood as the harmonic mean of the number of real choices that we have when deciding which token to pick next. Let us look at a number of cases:\n",
        "\n",
        "* In the best case scenario, the model always perfectly estimates the probability of the label token as 1. In this case the perplexity of the model is 1.\n",
        "* In the worst case scenario, the model always predicts the probability of the label token as 0. In this situation, the perplexity is positive infinity.\n",
        "* At the baseline, the model predicts a uniform distribution over all the available tokens of the vocabulary. In this case, the perplexity equals the number of unique tokens of the vocabulary. In fact, if we were to store the sequence without any compression, this would be the best we could do to encode it. Hence, this provides a nontrivial upper bound that any useful model must beat.\n",
        "\n",
        "In the following sections, we will implement RNNs\n",
        "for character-level language models and use perplexity\n",
        "to evaluate such models.\n",
        "\n",
        "\n",
        "## Summary\n",
        "\n",
        "* A neural network that uses recurrent computation for hidden states is called a recurrent neural network (RNN).\n",
        "* The hidden state of an RNN can capture historical information of the sequence up to the current time step.\n",
        "* The number of RNN model parameters does not grow as the number of time steps increases.\n",
        "* We can create character-level language models using an  RNN.\n",
        "* We can use perplexity to evaluate the quality of language models.\n",
        "\n",
        "## Exercises\n",
        "\n",
        "1. If we use an RNN to predict the next character in a text sequence, what is the required dimension for any output?\n",
        "1. Why can RNNs express the conditional probability of a token at some time step based on all the previous tokens in the text sequence?\n",
        "1. What happens to the gradient if you backpropagate through a long sequence?\n",
        "1. What are some of the problems associated with the language model described in this section?\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "origin_pos": 9,
        "tab": [
          "mxnet"
        ],
        "id": "Q6DkPSonXsGg"
      },
      "source": [
        "[Discussions](https://discuss.d2l.ai/t/337)\n"
      ]
    }
  ]
}