RNNLM.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recurrent Neural Networks Tutorial, Part 2 – Implementing a Language Model RNN with Python, Numpy and Theano"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import csv\n",
    "import itertools\n",
    "import operator\n",
    "import numpy as np\n",
    "import nltk\n",
    "import sys\n",
    "from datetime import datetime\n",
    "from utils import *\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Download NLTK model data (you need to do this once)\n",
    "nltk.download(\"book\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### This the second part of the Recurrent Neural Network Tutorial. [The first part is here](http://www.wildml.com/2015/09/recurrent-neural-networks-tutorial-part-1-introduction-to-rnns/).\n",
    "\n",
    "In this part we will implement a full Recurrent Neural Network from scratch using Python and optimize our implementation using [Theano](http://deeplearning.net/software/theano/), a library to perform operations on a GPU. **[The full code is available on Github](https://github.com/dennybritz/rnn-tutorial-rnnlm/)**. I will skip over some boilerplate code that is not essential to understanding Recurrent Neural Networks, but all of that is also [on Github](https://github.com/dennybritz/rnn-tutorial-rnnlm)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Language Modeling\n",
    "\n",
    "Our goal is to build a [Language Model](https://en.wikipedia.org/wiki/Language_model) using a Recurrent Neural Network. Here's what that means. Let's say we have sentence  of $m$ words. Language Model allows us to predict the probability of observing the sentence (in a given dataset) as:\n",
    "\n",
    "$\n",
    "\\begin{aligned}\n",
    "P(w_1,...,w_m) = \\prod_{i=1}^{m}P(w_i \\mid w_1,..., w_{i-1}) \n",
    "\\end{aligned}\n",
    "$\n",
    "\n",
    "In words, the probability of a sentence is the product of probabilities of each word given the words that came before it. So, the probability of the sentence \"He went to buy some chocolate\" would be the probability of \"chocolate\" given \"He went to buy some\", multiplied by the probability of \"some\" given \"He went to buy\", and so on. \n",
    "\n",
    "Why is that useful? Why would we want to assign a probability to observing a sentence?\n",
    "\n",
    "First, such a model can be used as a scoring mechanism. For example, a Machine Translation system typically generates multiple candidates for an input sentence. You could use a language model to pick the most probable sentence. Intuitively, the most probable sentence is likely to be grammatically correct. Similar scoring happens in speech recognition systems.\n",
    "\n",
    "But solving the Language Modeling problem also has a cool side effect. Because we can predict the probability of a word given the preceding words, we are able to generate new text. It's a *generative model*. Given an existing sequence of words we sample a next word from the predicted probabilities, and repeat the process until we have a full sentence. Andrew Karparthy [has a great post](http://karpathy.github.io/2015/05/21/rnn-effectiveness/) that demonstrates what language models are capable of. His models are trained on single characters as opposed to full words, and can generate anything from Shakespeare to Linux Code.\n",
    "\n",
    "Note that in the above equation the probability of each word is conditioned on **all** previous words. In practice, many models have a hard time representing such long-term dependencies due to computational or memory constraints. They are typically limited to looking at only a few of the previous words. RNNs can, in theory, capture such long-term dependencies, but in practice it's a bit more complex. We'll explore that in a later post."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training Data and Preprocessing\n",
    "\n",
    "To train our language model we need text to learn from. Fortunately we don't need any labels to train a language model, just raw text. I downloaded 15,000 longish reddit comments from a [dataset available on Google's BigQuery](https://bigquery.cloud.google.com/table/fh-bigquery:reddit_comments.2015_08). Text generated by our model will sound like reddit commenters (hopefully)! But as with most Machine Learning projects we first need to do some pre-processing to get our data into the right format.\n",
    "\n",
    "#### 1. Tokenize Text\n",
    "\n",
    "We have raw text, but we want to make predictions on a per-word basis. This means we must *tokenize* our comments into sentences, and sentences into words. We could just split each of the comments by spaces, but that wouldn't handle punctuation properly. The sentence \"He left!\" should be 3 tokens: \"He\", \"left\", \"!\". We'll use [NLTK's](http://www.nltk.org/) `word_tokenize` and `sent_tokenize` methods, which do most of the hard work for us.\n",
    "\n",
    "#### 2. Remove infrequent words\n",
    "\n",
    "Most words in our text will only appear one or two times. It's a good idea to remove these infrequent words. Having a huge vocabulary will make our model slow to train (we'll talk about why that is later), and because we don't have a lot of contextual examples for such words we wouldn't be able to learn how to use them correctly anyway. That's quite similar to how humans learn. To really understand how to appropriately use a word you need to have seen it in different contexts.\n",
    "\n",
    "In our code we limit our vocabulary to the `vocabulary_size` most common words (which I set to 8000, but feel free to change it). We replace all words not included in our vocabulary by `UNKNOWN_TOKEN`. For example, if we don't include the word \"nonlinearities\" in our vocabulary, the sentence \"nonlineraties are important in neural networks\" becomes \"UNKNOWN_TOKEN are important in Neural Networks\". The word `UNKNOWN_TOKEN` will become part of our vocabulary and we will predict it just like any other word. When we generate new text we can replace `UNKNOWN_TOKEN` again, for example by taking a randomly sampled word not in our vocabulary, or we could just generate sentences until we get one that doesn't contain an unknown token.\n",
    "\n",
    "#### 3. Prepend special start and end tokens\n",
    "\n",
    "We also want to learn which words tend start and end a sentence. To do this we prepend a special `SENTENCE_START` token, and append a special `SENTENCE_END` token to each sentence. This allows us to ask: Given that the first token is `SENTENCE_START`, what is the likely next word (the actual first word of the sentence)?\n",
    "\n",
    "\n",
    "#### 4. Build training data matrices\n",
    "\n",
    "The input to our Recurrent Neural Networks are vectors, not strings. So we create a mapping between words and indices, `index_to_word`, and `word_to_index`. For example,  the word \"friendly\" may be at index 2001. A training example $x$ may look like `[0, 179, 341, 416]`, where 0 corresponds to `SENTENCE_START`. The corresponding label $y$ would be `[179, 341, 416, 1]`. Remember that our goal is to predict the next word, so y is just the x vector shifted by one position with the last element being the `SENTENCE_END` token. In other words, the correct prediction for word `179` above would be `341`, the actual next word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "vocabulary_size = 8000\n",
    "unknown_token = \"UNKNOWN_TOKEN\"\n",
    "sentence_start_token = \"SENTENCE_START\"\n",
    "sentence_end_token = \"SENTENCE_END\"\n",
    "\n",
    "# Read the data and append SENTENCE_START and SENTENCE_END tokens\n",
    "print \"Reading CSV file...\"\n",
    "with open('data/reddit-comments-2015-08.csv', 'rb') as f:\n",
    "    reader = csv.reader(f, skipinitialspace=True)\n",
    "    reader.next()\n",
    "    # Split full comments into sentences\n",
    "    sentences = itertools.chain(*[nltk.sent_tokenize(x[0].decode('utf-8').lower()) for x in reader])\n",
    "    # Append SENTENCE_START and SENTENCE_END\n",
    "    sentences = [\"%s %s %s\" % (sentence_start_token, x, sentence_end_token) for x in sentences]\n",
    "print \"Parsed %d sentences.\" % (len(sentences))\n",
    "    \n",
    "# Tokenize the sentences into words\n",
    "tokenized_sentences = [nltk.word_tokenize(sent) for sent in sentences]\n",
    "\n",
    "# Count the word frequencies\n",
    "word_freq = nltk.FreqDist(itertools.chain(*tokenized_sentences))\n",
    "print \"Found %d unique words tokens.\" % len(word_freq.items())\n",
    "\n",
    "# Get the most common words and build index_to_word and word_to_index vectors\n",
    "vocab = word_freq.most_common(vocabulary_size-1)\n",
    "index_to_word = [x[0] for x in vocab]\n",
    "index_to_word.append(unknown_token)\n",
    "word_to_index = dict([(w,i) for i,w in enumerate(index_to_word)])\n",
    "\n",
    "print \"Using vocabulary size %d.\" % vocabulary_size\n",
    "print \"The least frequent word in our vocabulary is '%s' and appeared %d times.\" % (vocab[-1][0], vocab[-1][1])\n",
    "\n",
    "# Replace all words not in our vocabulary with the unknown token\n",
    "for i, sent in enumerate(tokenized_sentences):\n",
    "    tokenized_sentences[i] = [w if w in word_to_index else unknown_token for w in sent]\n",
    "\n",
    "print \"\\nExample sentence: '%s'\" % sentences[0]\n",
    "print \"\\nExample sentence after Pre-processing: '%s'\" % tokenized_sentences[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Create the training data\n",
    "X_train = np.asarray([[word_to_index[w] for w in sent[:-1]] for sent in tokenized_sentences])\n",
    "y_train = np.asarray([[word_to_index[w] for w in sent[1:]] for sent in tokenized_sentences])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an actual training example from our text:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Print an training data example\n",
    "x_example, y_example = X_train[17], y_train[17]\n",
    "print \"x:\\n%s\\n%s\" % (\" \".join([index_to_word[x] for x in x_example]), x_example)\n",
    "print \"\\ny:\\n%s\\n%s\" % (\" \".join([index_to_word[x] for x in y_example]), y_example)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Building the RNN\n",
    "\n",
    "For a general overview of RNNs take a look at [first part of the tutorial](http://www.wildml.com/2015/09/recurrent-neural-networks-tutorial-part-1-introduction-to-rnns/).\n",
    "\n",
    "![](http://www.wildml.com/wp-content/uploads/2015/09/rnn.jpg)\n",
    "\n",
    "Let's get concrete and see what the RNN for our language model looks like. The input $x$ will be a sequence of words (just like the example printed above) and each $x_t$ is a single word. But there's one more thing: Because of how matrix multiplication works we can't simply use a word index (like 36) as an input. Instead, we represent each word as a *one-hot vector* of size `vocabulary_size`. For example, the word with index 36 would be the vector of all 0's and a 1 at position 36. So, each $x_t$ will become a vector, and $x$ will be a matrix, with each row representing a word. We'll perform this transformation in our Neural Network code instead of doing it in the pre-processing. The output of our network $o$ has a similar format. Each $o_t$ is a vector of `vocabulary_size` elements, and each element represents the probability of that word being the next word in the sentence.\n",
    "\n",
    "Let's recap the equations for the RNN from the first part of the tutorial:\n",
    "\n",
    "$\n",
    "\\begin{aligned}\n",
    "s_t &= \\tanh(Ux_t + Ws_{t-1}) \\\\\n",
    "o_t &= \\mathrm{softmax}(Vs_t)\n",
    "\\end{aligned}\n",
    "$\n",
    "\n",
    "I always find it useful to write down the dimensions of the matrices and vectors. Let's assume we pick a vocabulary size $C = 8000$ and a hidden layer size $H = 100$. You can think of the hidden layer size as the \"memory\" of our network. Making it bigger allows us to learn more complex patterns, but also results in additional computation. Then we have:\n",
    "\n",
    "$\n",
    "\\begin{aligned}\n",
    "x_t & \\in \\mathbb{R}^{8000} \\\\\n",
    "o_t & \\in \\mathbb{R}^{8000} \\\\\n",
    "s_t & \\in \\mathbb{R}^{100} \\\\\n",
    "U & \\in \\mathbb{R}^{100 \\times 8000} \\\\\n",
    "V & \\in \\mathbb{R}^{8000 \\times 100} \\\\\n",
    "W & \\in \\mathbb{R}^{100 \\times 100} \\\\\n",
    "\\end{aligned}\n",
    "$\n",
    "\n",
    "This is valuable information. Remember that $U,V$ and $W$ are the parameters of our network we want to learn from data. Thus, we need to learn a total of $2HC + H^2$ parameters. In the case of $C=8000$ and $H=100$ that's 1,610,000.  The dimensions also tell us the bottleneck of our model. Note that because $x_t$ is a one-hot vector, multiplying it with $U$ is essentially the same as selecting a column of U, so we don't need to perform the full multiplication. Then, the biggest matrix multiplication in our network is $Vs_t$. That's why we want to keep our vocabulary size small if possible.\n",
    "\n",
    "Armed with this, it's time to start our implementation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Initialization\n",
    "\n",
    "We start by declaring a RNN class an initializing our parameters. I'm calling this class `RNNNumpy` because we will implement a Theano version later. Initializing the parameters $U,V$ and $W$ is a bit tricky. We can't just initialize them to 0's because that would result in symmetric calculations in all our layers. We must initialize them randomly. Because proper initialization seems to have an impact on training results there has been lot of research in this area. It turns out that the best initialization depends on the activation function ($\\tanh$ in our case) and one [recommended](http://jmlr.org/proceedings/papers/v9/glorot10a/glorot10a.pdf) approach is to initialize the weights randomly in the interval from $\\left[-\\frac{1}{\\sqrt{n}}, \\frac{1}{\\sqrt{n}}\\right]$ where $n$ is the number of incoming connections from the previous layer. This may sound overly complicated, but don't worry too much about it. As long as you initialize your parameters to small random values it typically works out fine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class RNNNumpy:\n",
    "    \n",
    "    def __init__(self, word_dim, hidden_dim=100, bptt_truncate=4):\n",
    "        # Assign instance variables\n",
    "        self.word_dim = word_dim\n",
    "        self.hidden_dim = hidden_dim\n",
    "        self.bptt_truncate = bptt_truncate\n",
    "        # Randomly initialize the network parameters\n",
    "        self.U = np.random.uniform(-np.sqrt(1./word_dim), np.sqrt(1./word_dim), (hidden_dim, word_dim))\n",
    "        self.V = np.random.uniform(-np.sqrt(1./hidden_dim), np.sqrt(1./hidden_dim), (word_dim, hidden_dim))\n",
    "        self.W = np.random.uniform(-np.sqrt(1./hidden_dim), np.sqrt(1./hidden_dim), (hidden_dim, hidden_dim))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above, `word_dim` is the size of our vocabulary, and `hidden_dim` is the size of our hidden layer (we can pick it). Don't worry about the `bptt_truncate` parameter for now, we'll explain what that is later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Forward Propagation\n",
    "\n",
    "Next, let's implement the forward propagation (predicting word probabilities) defined by our equations above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_propagation(self, x):\n",
    "    # The total number of time steps\n",
    "    T = len(x)\n",
    "    # During forward propagation we save all hidden states in s because need them later.\n",
    "    # We add one additional element for the initial hidden, which we set to 0\n",
    "    s = np.zeros((T + 1, self.hidden_dim))\n",
    "    s[-1] = np.zeros(self.hidden_dim)\n",
    "    # The outputs at each time step. Again, we save them for later.\n",
    "    o = np.zeros((T, self.word_dim))\n",
    "    # For each time step...\n",
    "    for t in np.arange(T):\n",
    "        # Note that we are indxing U by x[t]. This is the same as multiplying U with a one-hot vector.\n",
    "        s[t] = np.tanh(self.U[:,x[t]] + self.W.dot(s[t-1]))\n",
    "        o[t] = softmax(self.V.dot(s[t]))\n",
    "    return [o, s]\n",
    "\n",
    "RNNNumpy.forward_propagation = forward_propagation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We not only return the calculated outputs, but also the hidden states. We will use them later to calculate the gradients, and by returning them here we avoid duplicate computation. Each $o_t$ is a vector of probabilities representing the words in our vocabulary, but sometimes, for example when evaluating our model, all we want is the next word with the highest probability. We call this function `predict`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def predict(self, x):\n",
    "    # Perform forward propagation and return index of the highest score\n",
    "    o, s = self.forward_propagation(x)\n",
    "    return np.argmax(o, axis=1)\n",
    "\n",
    "RNNNumpy.predict = predict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try our newly implemented methods and see an example output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(10)\n",
    "model = RNNNumpy(vocabulary_size)\n",
    "o, s = model.forward_propagation(X_train[10])\n",
    "print o.shape\n",
    "print o"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each word in the sentence (45 above), our model made 8000 predictions representing probabilities of the next word. Note that because we initialized $U,V,W$ to random values these predictions are completely random right now. The following gives the indices of the highest probability predictions for each word:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "predictions = model.predict(X_train[10])\n",
    "print predictions.shape\n",
    "print predictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Calculating the Loss\n",
    "\n",
    "To train our network we need a way to measure the errors it makes. We call this the loss function $L$, and our goal is find the parameters $U,V$ and $W$ that minimize the loss function for our training data. A common choice for the loss function is the [cross-entropy loss](https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_error_function_and_logistic_regression). If we have $N$ training examples (words in our text) and $C$ classes (the size of our vocabulary) then the loss with respect to our predictions $o$ and the true labels $y$ is given by:\n",
    "\n",
    "$\n",
    "\\begin{aligned}\n",
    "L(y,o) = - \\frac{1}{N} \\sum_{n \\in N} y_{n} \\log o_{n}\n",
    "\\end{aligned}\n",
    "$\n",
    "\n",
    "The formula looks a bit complicated, but all it really does is sum over our training examples and add to the loss based on how off our prediction are. The further away $y$ (the correct words) and $o$ (our predictions), the greater the loss will be. We implement the function `calculate_loss`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calculate_total_loss(self, x, y):\n",
    "    L = 0\n",
    "    # For each sentence...\n",
    "    for i in np.arange(len(y)):\n",
    "        o, s = self.forward_propagation(x[i])\n",
    "        # We only care about our prediction of the \"correct\" words\n",
    "        correct_word_predictions = o[np.arange(len(y[i])), y[i]]\n",
    "        # Add to the loss based on how off we were\n",
    "        L += -1 * np.sum(np.log(correct_word_predictions))\n",
    "    return L\n",
    "\n",
    "def calculate_loss(self, x, y):\n",
    "    # Divide the total loss by the number of training examples\n",
    "    N = np.sum((len(y_i) for y_i in y))\n",
    "    return self.calculate_total_loss(x,y)/N\n",
    "\n",
    "RNNNumpy.calculate_total_loss = calculate_total_loss\n",
    "RNNNumpy.calculate_loss = calculate_loss"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take a step back and think about what the loss should be for random predictions. That will give us a baseline and make sure our implementation is correct. We have $C$ words in our vocabulary, so each word should be (on average) predicted with probability $1/C$, which would yield a loss of $L = -\\frac{1}{N} N \\log\\frac{1}{C} = \\log C$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Limit to 1000 examples to save time\n",
    "print \"Expected Loss for random predictions: %f\" % np.log(vocabulary_size)\n",
    "print \"Actual loss: %f\" % model.calculate_loss(X_train[:1000], y_train[:1000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretty close! Keep in mind that evaluating the loss on the full dataset is an expensive operation and can take hours if you have a lot of data!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Training the RNN with SGD and Backpropagation Through Time (BPTT)\n",
    "\n",
    "Remember that we want to find the parameters $U,V$ and $W$ that minimize the total loss on the training data. The most common way to do this is SGD, Stochastic Gradient Descent. The idea behind SGD is pretty simple. We iterate over all our training examples and during each iteration we nudge the parameters into a direction that reduces the error. These directions are given by the gradients on the loss: $\\frac{\\partial L}{\\partial U}, \\frac{\\partial L}{\\partial V}, \\frac{\\partial L}{\\partial W}$. SGD also needs a *learning rate*, which defines how big of a step we want to make in each iteration. SGD is the most popular optimization method not only for Neural Networks, but also for many other Machine Learning algorithms. As such there has been a lot of research on how to optimize SGD using batching, parallelism and adaptive learning rates. Even though the basic idea is simple, implementing SGD in a really efficient way can become very complex. If you want to learn more about SGD [this](http://cs231n.github.io/optimization-1/) is a good place to start. Due to its popularity there are a wealth of tutorials floating around the web, and I don't want to duplicate them here. I'll implement a simple version of SGD that should be understandable even without a background in optimization.\n",
    "\n",
    "But how do we calculate those gradients we mentioned above? In a [traditional Neural Network](http://www.wildml.com/2015/09/implementing-a-neural-network-from-scratch/) we do this through the backpropagation algorithm. In RNNs we use a slightly modified version of the this algorithm called Backpropagation Through Time (BPTT). Because the parameters are shared by all time steps in the network, the gradient at each output depends not only on the calculations of the current time step, but also the previous time steps. If you know calculus, it really is just applying the chain rule. The next part of the tutorial will be all about BPTT, so I won't go into detailed derivation here. For a general introduction to backpropagation check out [this](http://colah.github.io/posts/2015-08-Backprop/) and this [post](http://cs231n.github.io/optimization-2/). For now you can treat BPTT as a black box. It takes as input a training example $(x,y)$ and returns the gradients $\\frac{\\partial L}{\\partial U}, \\frac{\\partial L}{\\partial V}, \\frac{\\partial L}{\\partial W}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def bptt(self, x, y):\n",
    "    T = len(y)\n",
    "    # Perform forward propagation\n",
    "    o, s = self.forward_propagation(x)\n",
    "    # We accumulate the gradients in these variables\n",
    "    dLdU = np.zeros(self.U.shape)\n",
    "    dLdV = np.zeros(self.V.shape)\n",
    "    dLdW = np.zeros(self.W.shape)\n",
    "    delta_o = o\n",
    "    delta_o[np.arange(len(y)), y] -= 1.\n",
    "    # For each output backwards...\n",
    "    for t in np.arange(T)[::-1]:\n",
    "        dLdV += np.outer(delta_o[t], s[t].T)\n",
    "        # Initial delta calculation\n",
    "        delta_t = self.V.T.dot(delta_o[t]) * (1 - (s[t] ** 2))\n",
    "        # Backpropagation through time (for at most self.bptt_truncate steps)\n",
    "        for bptt_step in np.arange(max(0, t-self.bptt_truncate), t+1)[::-1]:\n",
    "            # print \"Backpropagation step t=%d bptt step=%d \" % (t, bptt_step)\n",
    "            dLdW += np.outer(delta_t, s[bptt_step-1])              \n",
    "            dLdU[:,x[bptt_step]] += delta_t\n",
    "            # Update delta for next step\n",
    "            delta_t = self.W.T.dot(delta_t) * (1 - s[bptt_step-1] ** 2)\n",
    "    return [dLdU, dLdV, dLdW]\n",
    "\n",
    "RNNNumpy.bptt = bptt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Gradient Checking\n",
    "\n",
    "Whenever you implement backpropagation it is good idea to also implement *gradient checking*, which is a way of verifying that your implementation is correct. The idea behind gradient checking is that derivative of a parameter is equal to the slope at the point, which we can approximate by slightly changing the parameter and then dividing by the change:\n",
    "\n",
    "$\n",
    "\\begin{aligned}\n",
    "\\frac{\\partial L}{\\partial \\theta} \\approx \\lim_{h \\to 0} \\frac{J(\\theta + h) - J(\\theta -h)}{2h}\n",
    "\\end{aligned}\n",
    "$\n",
    "\n",
    "We then compare the gradient we calculated using backpropagation to the gradient we estimated with the method above. If there's no large difference we are good. The approximation needs to calculate the total loss for *every* parameter, so that gradient checking is very expensive (remember, we had more than a million parameters in the example above). So it's a good idea to perform it on a model with a smaller vocabulary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def gradient_check(self, x, y, h=0.001, error_threshold=0.01):\n",
    "    # Calculate the gradients using backpropagation. We want to checker if these are correct.\n",
    "    bptt_gradients = model.bptt(x, y)\n",
    "    # List of all parameters we want to check.\n",
    "    model_parameters = ['U', 'V', 'W']\n",
    "    # Gradient check for each parameter\n",
    "    for pidx, pname in enumerate(model_parameters):\n",
    "        # Get the actual parameter value from the mode, e.g. model.W\n",
    "        parameter = operator.attrgetter(pname)(self)\n",
    "        print \"Performing gradient check for parameter %s with size %d.\" % (pname, np.prod(parameter.shape))\n",
    "        # Iterate over each element of the parameter matrix, e.g. (0,0), (0,1), ...\n",
    "        it = np.nditer(parameter, flags=['multi_index'], op_flags=['readwrite'])\n",
    "        while not it.finished:\n",
    "            ix = it.multi_index\n",
    "            # Save the original value so we can reset it later\n",
    "            original_value = parameter[ix]\n",
    "            # Estimate the gradient using (f(x+h) - f(x-h))/(2*h)\n",
    "            parameter[ix] = original_value + h\n",
    "            gradplus = model.calculate_total_loss([x],[y])\n",
    "            parameter[ix] = original_value - h\n",
    "            gradminus = model.calculate_total_loss([x],[y])\n",
    "            estimated_gradient = (gradplus - gradminus)/(2*h)\n",
    "            # Reset parameter to original value\n",
    "            parameter[ix] = original_value\n",
    "            # The gradient for this parameter calculated using backpropagation\n",
    "            backprop_gradient = bptt_gradients[pidx][ix]\n",
    "            # calculate The relative error: (|x - y|/(|x| + |y|))\n",
    "            relative_error = np.abs(backprop_gradient - estimated_gradient)/(np.abs(backprop_gradient) + np.abs(estimated_gradient))\n",
    "            # If the error is to large fail the gradient check\n",
    "            if relative_error > error_threshold:\n",
    "                print \"Gradient Check ERROR: parameter=%s ix=%s\" % (pname, ix)\n",
    "                print \"+h Loss: %f\" % gradplus\n",
    "                print \"-h Loss: %f\" % gradminus\n",
    "                print \"Estimated_gradient: %f\" % estimated_gradient\n",
    "                print \"Backpropagation gradient: %f\" % backprop_gradient\n",
    "                print \"Relative Error: %f\" % relative_error\n",
    "                return \n",
    "            it.iternext()\n",
    "        print \"Gradient check for parameter %s passed.\" % (pname)\n",
    "\n",
    "RNNNumpy.gradient_check = gradient_check\n",
    "\n",
    "# To avoid performing millions of expensive calculations we use a smaller vocabulary size for checking.\n",
    "grad_check_vocab_size = 100\n",
    "np.random.seed(10)\n",
    "model = RNNNumpy(grad_check_vocab_size, 10, bptt_truncate=1000)\n",
    "model.gradient_check([0,1,2,3], [1,2,3,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### SGD Implementation\n",
    "\n",
    "Now that we are able to calculate the gradients for our parameters we can implement SGD. I like to do this in two steps: 1. A function `sdg_step` that calculates the gradients and performs the updates for one batch. 2. An outer loop that iterates through the training set and adjusts the learning rate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Performs one step of SGD.\n",
    "def numpy_sdg_step(self, x, y, learning_rate):\n",
    "    # Calculate the gradients\n",
    "    dLdU, dLdV, dLdW = self.bptt(x, y)\n",
    "    # Change parameters according to gradients and learning rate\n",
    "    self.U -= learning_rate * dLdU\n",
    "    self.V -= learning_rate * dLdV\n",
    "    self.W -= learning_rate * dLdW\n",
    "\n",
    "RNNNumpy.sgd_step = numpy_sdg_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Outer SGD Loop\n",
    "# - model: The RNN model instance\n",
    "# - X_train: The training data set\n",
    "# - y_train: The training data labels\n",
    "# - learning_rate: Initial learning rate for SGD\n",
    "# - nepoch: Number of times to iterate through the complete dataset\n",
    "# - evaluate_loss_after: Evaluate the loss after this many epochs\n",
    "def train_with_sgd(model, X_train, y_train, learning_rate=0.005, nepoch=100, evaluate_loss_after=5):\n",
    "    # We keep track of the losses so we can plot them later\n",
    "    losses = []\n",
    "    num_examples_seen = 0\n",
    "    for epoch in range(nepoch):\n",
    "        # Optionally evaluate the loss\n",
    "        if (epoch % evaluate_loss_after == 0):\n",
    "            loss = model.calculate_loss(X_train, y_train)\n",
    "            losses.append((num_examples_seen, loss))\n",
    "            time = datetime.now().strftime('%Y-%m-%d %H:%M:%S')\n",
    "            print \"%s: Loss after num_examples_seen=%d epoch=%d: %f\" % (time, num_examples_seen, epoch, loss)\n",
    "            # Adjust the learning rate if loss increases\n",
    "            if (len(losses) > 1 and losses[-1][1] > losses[-2][1]):\n",
    "                learning_rate = learning_rate * 0.5  \n",
    "                print \"Setting learning rate to %f\" % learning_rate\n",
    "            sys.stdout.flush()\n",
    "        # For each training example...\n",
    "        for i in range(len(y_train)):\n",
    "            # One SGD step\n",
    "            model.sgd_step(X_train[i], y_train[i], learning_rate)\n",
    "            num_examples_seen += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Done! Let's try to get a sense of how long it would take to train our network:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(10)\n",
    "model = RNNNumpy(vocabulary_size)\n",
    "%timeit model.sgd_step(X_train[10], y_train[10], 0.005)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uh-oh, bad news. One step of SGD takes approximately 350 milliseconds on my laptop. We have about 80,000 examples in our training data, so one epoch (iteration over the whole data set) would take several hours. Multiple epochs would take days, or even weeks! And we're still working with a small dataset compared to what's being used by many of the companies and researchers out there. What now?\n",
    "\n",
    "Fortunately there are many ways to speed up our code. We could stick with the same model and make our code run faster, or we could modify our model to be less computationally expensive, or both. Researchers have identified many ways to make models less computationally expensive, for example by using a hierarchical softmax or adding projection layers to avoid the large matrix multiplications (see also [here](http://arxiv.org/pdf/1301.3781.pdf) or [here](http://www.fit.vutbr.cz/research/groups/speech/publi/2011/mikolov_icassp2011_5528.pdf)). But I want to keep our model simple and go the first route: Make our implementation run faster using a GPU. Before doing that though, let's just try to run SGD with a small dataset and check if the loss actually decreases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(10)\n",
    "# Train on a small subset of the data to see what happens\n",
    "model = RNNNumpy(vocabulary_size)\n",
    "losses = train_with_sgd(model, X_train[:100], y_train[:100], nepoch=10, evaluate_loss_after=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Good, it seems like our implementation is at least doing something useful and decreasing the loss, just like we wanted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training our Network with Theano and the GPU\n",
    "\n",
    "I have previously written a [tutorial](http://www.wildml.com/2015/09/speeding-up-your-neural-network-with-theano-and-the-gpu/) on Theano, and since all our logic will stay exactly the same I won't go through optimized code here again. I defined a `RNNTheano` class that replaces the numpy calculations with corresponding calculations in Theano. Just like the rest of this post, [the code is also available Github](https://github.com/dennybritz/rnn-tutorial-rnnlm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from rnn_theano import RNNTheano, gradient_check_theano"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(10)\n",
    "# To avoid performing millions of expensive calculations we use a smaller vocabulary size for checking.\n",
    "grad_check_vocab_size = 5\n",
    "model = RNNTheano(grad_check_vocab_size, 10)\n",
    "gradient_check_theano(model, [0,1,2,3], [1,2,3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "np.random.seed(10)\n",
    "model = RNNTheano(vocabulary_size)\n",
    "%timeit model.sgd_step(X_train[10], y_train[10], 0.005)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "This time, one SGD step takes 70ms on my Mac (without GPU) and 23ms on a [g2.2xlarge](https://aws.amazon.com/ec2/instance-types/#g2) Amazon EC2 instance with GPU. That's a 15x improvement over our initial implementation and means we can train our model in hours/days instead of weeks. There are still a vast number of optimizations we could make, but we're good enough for now.\n",
    "\n",
    "To help you avoid spending days training a model I have pre-trained a Theano model with a hidden layer dimensionality of 50 and a vocabulary size of 8000. I trained it for 50 epochs in about 20 hours. The loss was was still decreasing and training longer would probably have resulted in a better model, but I was running out of time and wanted to publish this post. Feel free to try it out yourself and trian for longer. You can find the model parameters in `data/trained-model-theano.npz` in the Github repository and load them using the `load_model_parameters_theano` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from utils import load_model_parameters_theano, save_model_parameters_theano\n",
    "\n",
    "model = RNNTheano(vocabulary_size, hidden_dim=50)\n",
    "# losses = train_with_sgd(model, X_train, y_train, nepoch=50)\n",
    "# save_model_parameters_theano('./data/trained-model-theano.npz', model)\n",
    "load_model_parameters_theano('./data/trained-model-theano.npz', model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Generating Text\n",
    "\n",
    "Now that we have our model we can ask it to generate new text for us! Let's implement a helper function to generate new sentences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def generate_sentence(model):\n",
    "    # We start the sentence with the start token\n",
    "    new_sentence = [word_to_index[sentence_start_token]]\n",
    "    # Repeat until we get an end token\n",
    "    while not new_sentence[-1] == word_to_index[sentence_end_token]:\n",
    "        next_word_probs = model.forward_propagation(new_sentence)\n",
    "        sampled_word = word_to_index[unknown_token]\n",
    "        # We don't want to sample unknown words\n",
    "        while sampled_word == word_to_index[unknown_token]:\n",
    "            samples = np.random.multinomial(1, next_word_probs[-1])\n",
    "            sampled_word = np.argmax(samples)\n",
    "        new_sentence.append(sampled_word)\n",
    "    sentence_str = [index_to_word[x] for x in new_sentence[1:-1]]\n",
    "    return sentence_str\n",
    "\n",
    "num_sentences = 10\n",
    "senten_min_length = 7\n",
    "\n",
    "for i in range(num_sentences):\n",
    "    sent = []\n",
    "    # We want long sentences, not sentences with one or two words\n",
    "    while len(sent) < senten_min_length:\n",
    "        sent = generate_sentence(model)\n",
    "    print \" \".join(sent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A few selected (censored) sentences. I added capitalization.\n",
    "\n",
    "- Anyway, to the city scene you're an idiot teenager.\n",
    "- What ? ! ! ! ! ignore!\n",
    "- Screw fitness, you're saying: https\n",
    "- Thanks for the advice to keep my thoughts around girls.\n",
    "- Yep, please disappear with the terrible generation.\n",
    "\n",
    "Looking at the generated sentences there are a few interesting things to note. The model successfully learn syntax. It properly places commas (usually before and's and or's) and ends sentence with punctuation. Sometimes it mimics internet speech such as multiple exclamation marks or smileys.\n",
    "\n",
    "However, the vast majority of generated sentences don't make sense or have grammatical errors. One reason could be that we did not train our network long enough (or didn't use enough training data). That may be true, but it's most likely not the main reason. **Our vanilla RNN  can't generate meaningful text because it's unable to learn dependencies between words that are several steps apart**. That's also why RNNs failed to gain popularity when they were first invented. They were beautiful in theory but didn't work well in practice, and we didn't immediately understand why.\n",
    "\n",
    "Fortunately, the difficulties in training RNNs are [much better understood](http://arxiv.org/abs/1211.5063) now. In the next part of this tutorial we will explore the Backpropagation Through Time (BPTT) algorithm in more detail and demonstrate what's called the *vanishing gradient problem*. This will motivate our move to more sophisticated RNN models, such as LSTMs, which are the current state of the art for many tasks in NLP (and can generate much better reddit comments!).  Everything you learned in this tutorial also applies to LSTMs and other RNN models, so don't feel discouraged if the results for a vanilla RNN are worse then you expected.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}