6_lstm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "8tQJd2YSCfWR"
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "D7tqLMoKF6uq"
   },
   "source": [
    "Deep Learning\n",
    "=============\n",
    "\n",
    "Assignment 6\n",
    "------------\n",
    "\n",
    "After training a skip-gram model in `5_word2vec.ipynb`, the goal of this notebook is to train a LSTM character model over [Text8](http://mattmahoney.net/dc/textdata) data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "deletable": true,
    "editable": true,
    "id": "MvEblsgEXxrd"
   },
   "outputs": [],
   "source": [
    "# These are all the modules we'll be using later. Make sure you can import them\n",
    "# before proceeding further.\n",
    "from __future__ import print_function\n",
    "import os\n",
    "import numpy as np\n",
    "import random\n",
    "import string\n",
    "import tensorflow as tf\n",
    "import zipfile\n",
    "from six.moves import range\n",
    "from six.moves.urllib.request import urlretrieve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "executionInfo": {
     "elapsed": 5993,
     "status": "ok",
     "timestamp": 1445965582896,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "RJ-o3UBUFtCw",
    "outputId": "d530534e-0791-4a94-ca6d-1c8f1b908a9e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found and verified text8.zip\n"
     ]
    }
   ],
   "source": [
    "url = 'http://mattmahoney.net/dc/'\n",
    "\n",
    "def maybe_download(filename, expected_bytes):\n",
    "  \"\"\"Download a file if not present, and make sure it's the right size.\"\"\"\n",
    "  if not os.path.exists(filename):\n",
    "    filename, _ = urlretrieve(url + filename, filename)\n",
    "  statinfo = os.stat(filename)\n",
    "  if statinfo.st_size == expected_bytes:\n",
    "    print('Found and verified %s' % filename)\n",
    "  else:\n",
    "    print(statinfo.st_size)\n",
    "    raise Exception(\n",
    "      'Failed to verify ' + filename + '. Can you get to it with a browser?')\n",
    "  return filename\n",
    "\n",
    "filename = maybe_download('text8.zip', 31344016)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "executionInfo": {
     "elapsed": 5982,
     "status": "ok",
     "timestamp": 1445965582916,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "Mvf09fjugFU_",
    "outputId": "8f75db58-3862-404b-a0c3-799380597390"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data size 100000000\n"
     ]
    }
   ],
   "source": [
    "def read_data(filename):\n",
    "  with zipfile.ZipFile(filename) as f:\n",
    "    name = f.namelist()[0]\n",
    "    data = tf.compat.as_str(f.read(name))\n",
    "  return data\n",
    "  \n",
    "text = read_data(filename)\n",
    "print('Data size %d' % len(text))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "ga2CYACE-ghb"
   },
   "source": [
    "Create a small validation set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "executionInfo": {
     "elapsed": 6184,
     "status": "ok",
     "timestamp": 1445965583138,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "w-oBpfFG-j43",
    "outputId": "bdb96002-d021-4379-f6de-a977924f0d02"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99999000 ons anarchists advocate social relations based upon voluntary as\n",
      "1000  anarchism originated as a term of abuse first used against earl\n"
     ]
    }
   ],
   "source": [
    "valid_size = 1000\n",
    "valid_text = text[:valid_size]\n",
    "train_text = text[valid_size:]\n",
    "train_size = len(train_text)\n",
    "print(train_size, train_text[:64])\n",
    "print(valid_size, valid_text[:64])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "Zdw6i4F8glpp"
   },
   "source": [
    "Utility functions to map characters to vocabulary IDs and back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "executionInfo": {
     "elapsed": 6276,
     "status": "ok",
     "timestamp": 1445965583249,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "gAL1EECXeZsD",
    "outputId": "88fc9032-feb9-45ff-a9a0-a26759cc1f2e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unexpected character: ï\n",
      "1 26 0 0\n",
      "a z  \n"
     ]
    }
   ],
   "source": [
    "vocabulary_size = len(string.ascii_lowercase) + 1 # [a-z] + ' '\n",
    "first_letter = ord(string.ascii_lowercase[0])\n",
    "\n",
    "def char2id(char):\n",
    "  if char in string.ascii_lowercase:\n",
    "    return ord(char) - first_letter + 1\n",
    "  elif char == ' ':\n",
    "    return 0\n",
    "  else:\n",
    "    print('Unexpected character: %s' % char)\n",
    "    return 0\n",
    "  \n",
    "def id2char(dictid):\n",
    "  if dictid > 0:\n",
    "    return chr(dictid + first_letter - 1)\n",
    "  else:\n",
    "    return ' '\n",
    "\n",
    "print(char2id('a'), char2id('z'), char2id(' '), char2id('ï'))\n",
    "print(id2char(1), id2char(26), id2char(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "lFwoyygOmWsL"
   },
   "source": [
    "Function to generate a training batch for the LSTM model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "executionInfo": {
     "elapsed": 6473,
     "status": "ok",
     "timestamp": 1445965583467,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "d9wMtjy5hCj9",
    "outputId": "3dd79c80-454a-4be0-8b71-4a4a357b3367"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ons anarchi', 'when milita', 'lleria arch', ' abbeys and', 'married urr', 'hel and ric', 'y and litur', 'ay opened f', 'tion from t', 'migration t', 'new york ot', 'he boeing s', 'e listed wi', 'eber has pr', 'o be made t', 'yer who rec', 'ore signifi', 'a fierce cr', ' two six ei', 'aristotle s', 'ity can be ', ' and intrac', 'tion of the', 'dy to pass ', 'f certain d', 'at it will ', 'e convince ', 'ent told hi', 'ampaign and', 'rver side s', 'ious texts ', 'o capitaliz', 'a duplicate', 'gh ann es d', 'ine january', 'ross zero t', 'cal theorie', 'ast instanc', ' dimensiona', 'most holy m', 't s support', 'u is still ', 'e oscillati', 'o eight sub', 'of italy la', 's the tower', 'klahoma pre', 'erprise lin', 'ws becomes ', 'et in a naz', 'the fabian ', 'etchy to re', ' sharman ne', 'ised empero', 'ting in pol', 'd neo latin', 'th risky ri', 'encyclopedi', 'fense the a', 'duating fro', 'treet grid ', 'ations more', 'appeal of d', 'si have mad']\n",
      "['ists advoca', 'ary governm', 'hes nationa', 'd monasteri', 'raca prince', 'chard baer ', 'rgical lang', 'for passeng', 'the nationa', 'took place ', 'ther well k', 'seven six s', 'ith a gloss', 'robably bee', 'to recogniz', 'ceived the ', 'icant than ', 'ritic of th', 'ight in sig', 's uncaused ', ' lost as in', 'cellular ic', 'e size of t', ' him a stic', 'drugs confu', ' take to co', ' the priest', 'im to name ', 'd barred at', 'standard fo', ' such as es', 'ze on the g', 'e of the or', 'd hiver one', 'y eight mar', 'the lead ch', 'es classica', 'ce the non ', 'al analysis', 'mormons bel', 't or at lea', ' disagreed ', 'ing system ', 'btypes base', 'anguages th', 'r commissio', 'ess one nin', 'nux suse li', ' the first ', 'zi concentr', ' society ne', 'elatively s', 'etworks sha', 'or hirohito', 'litical ini', 'n most of t', 'iskerdoo ri', 'ic overview', 'air compone', 'om acnm acc', ' centerline', 'e than any ', 'devotional ', 'de such dev']\n",
      "[' a']\n",
      "['an']\n"
     ]
    }
   ],
   "source": [
    "batch_size=64\n",
    "num_unrollings=10\n",
    "\n",
    "class BatchGenerator(object):\n",
    "  def __init__(self, text, batch_size, num_unrollings):\n",
    "    self._text = text\n",
    "    self._text_size = len(text)\n",
    "    self._batch_size = batch_size\n",
    "    self._num_unrollings = num_unrollings\n",
    "    segment = self._text_size // batch_size\n",
    "    self._cursor = [ offset * segment for offset in range(batch_size)]\n",
    "    self._last_batch = self._next_batch()\n",
    "  \n",
    "  def _next_batch(self):\n",
    "    \"\"\"Generate a single batch from the current cursor position in the data.\"\"\"\n",
    "    batch = np.zeros(shape=(self._batch_size, vocabulary_size), dtype=np.float)\n",
    "    for b in range(self._batch_size):\n",
    "      batch[b, char2id(self._text[self._cursor[b]])] = 1.0\n",
    "      self._cursor[b] = (self._cursor[b] + 1) % self._text_size\n",
    "    return batch\n",
    "  \n",
    "  def next(self):\n",
    "    \"\"\"Generate the next array of batches from the data. The array consists of\n",
    "    the last batch of the previous array, followed by num_unrollings new ones.\n",
    "    \"\"\"\n",
    "    batches = [self._last_batch]\n",
    "    for step in range(self._num_unrollings):\n",
    "      batches.append(self._next_batch())\n",
    "    self._last_batch = batches[-1]\n",
    "    return batches\n",
    "\n",
    "def characters(probabilities):\n",
    "  \"\"\"Turn a 1-hot encoding or a probability distribution over the possible\n",
    "  characters back into its (most likely) character representation.\"\"\"\n",
    "  return [id2char(c) for c in np.argmax(probabilities, 1)]\n",
    "\n",
    "def batches2string(batches):\n",
    "  \"\"\"Convert a sequence of batches back into their (most likely) string\n",
    "  representation.\"\"\"\n",
    "  s = [''] * batches[0].shape[0]\n",
    "  for b in batches:\n",
    "    s = [''.join(x) for x in zip(s, characters(b))]\n",
    "  return s\n",
    "\n",
    "train_batches = BatchGenerator(train_text, batch_size, num_unrollings)\n",
    "valid_batches = BatchGenerator(valid_text, 1, 1)\n",
    "\n",
    "print(batches2string(train_batches.next()))\n",
    "print(batches2string(train_batches.next()))\n",
    "print(batches2string(valid_batches.next()))\n",
    "print(batches2string(valid_batches.next()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "deletable": true,
    "editable": true,
    "id": "KyVd8FxT5QBc"
   },
   "outputs": [],
   "source": [
    "def logprob(predictions, labels):\n",
    "  \"\"\"Log-probability of the true labels in a predicted batch.\"\"\"\n",
    "  predictions[predictions < 1e-10] = 1e-10\n",
    "  return np.sum(np.multiply(labels, -np.log(predictions))) / labels.shape[0]\n",
    "\n",
    "def sample_distribution(distribution):\n",
    "  \"\"\"Sample one element from a distribution assumed to be an array of normalized\n",
    "  probabilities.\n",
    "  \"\"\"\n",
    "  r = random.uniform(0, 1)\n",
    "  s = 0\n",
    "  for i in range(len(distribution)):\n",
    "    s += distribution[i]\n",
    "    if s >= r:\n",
    "      return i\n",
    "  return len(distribution) - 1\n",
    "\n",
    "def sample(prediction):\n",
    "  \"\"\"Turn a (column) prediction into 1-hot encoded samples.\"\"\"\n",
    "  p = np.zeros(shape=[1, vocabulary_size], dtype=np.float)\n",
    "  p[0, sample_distribution(prediction[0])] = 1.0\n",
    "  return p\n",
    "\n",
    "def random_distribution():\n",
    "  \"\"\"Generate a random column of probabilities.\"\"\"\n",
    "  b = np.random.uniform(0.0, 1.0, size=[1, vocabulary_size])\n",
    "  return b/np.sum(b, 1)[:,None]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "K8f67YXaDr4C"
   },
   "source": [
    "Simple LSTM Model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "id": "Q5rxZK6RDuGe"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "i.shape: (64, 27)\n",
      "output.shape: (64, 64)\n",
      "conc_outputs.shape: (640, 64)\n",
      "outputs.len: 10\n",
      "logits.shape: (640, 27)\n"
     ]
    }
   ],
   "source": [
    "num_nodes = 64\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "  \n",
    "  # Parameters:\n",
    "  # Input gate: input, previous output, and bias.\n",
    "  ix = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  im = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ib = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Forget gate: input, previous output, and bias.\n",
    "  fx = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  fm = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  fb = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cx = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  cm = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  cb = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Output gate: input, previous output, and bias.\n",
    "  ox = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  om = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ob = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Variables saving state across unrollings.\n",
    "  saved_output = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  saved_state = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  # Classifier weights and biases.\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    input_gate = tf.sigmoid(tf.matmul(i, ix) + tf.matmul(o, im) + ib)\n",
    "    forget_gate = tf.sigmoid(tf.matmul(i, fx) + tf.matmul(o, fm) + fb)\n",
    "    update = tf.matmul(i, cx) + tf.matmul(o, cm) + cb\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\n",
    "    output_gate = tf.sigmoid(tf.matmul(i, ox) + tf.matmul(o, om) + ob)\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in range(num_unrollings + 1):\n",
    "    train_data.append(\n",
    "      tf.placeholder(tf.float32, shape=[batch_size,vocabulary_size]))\n",
    "  train_inputs = train_data[:num_unrollings]\n",
    "  train_labels = train_data[1:]  # labels are inputs shifted by one time step.\n",
    "\n",
    "  # Unrolled LSTM loop.\n",
    "  outputs = list()\n",
    "  output = saved_output\n",
    "  state = saved_state\n",
    "  for i in train_inputs:\n",
    "    output, state = lstm_cell(i, output, state)\n",
    "    print(\"i.shape:\", i.shape)\n",
    "    print(\"output.shape:\", output.shape)\n",
    "    outputs.append(output)\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state)]):\n",
    "    # Classifier.\n",
    "    conc_outputs = tf.concat(outputs, 0)\n",
    "    logits = tf.nn.xw_plus_b(conc_outputs, w, b)\n",
    "    print(\"conc_outputs.shape:\", conc_outputs.shape)\n",
    "    print(\"outputs.len:\", len(outputs))\n",
    "    print(\"logits.shape:\", logits.shape)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        labels=tf.concat(train_labels, 0), logits=logits))\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 5000, 0.1, staircase=True)\n",
    "  optimizer = tf.train.GradientDescentOptimizer(learning_rate)\n",
    "  gradients, v = zip(*optimizer.compute_gradients(loss))\n",
    "  gradients, _ = tf.clip_by_global_norm(gradients, 1.25)\n",
    "  optimizer = optimizer.apply_gradients(\n",
    "    zip(gradients, v), global_step=global_step)\n",
    "\n",
    "  # Predictions.\n",
    "  train_prediction = tf.nn.softmax(logits)\n",
    "  \n",
    "  # Sampling and validation eval: batch 1, no unrolling.\n",
    "  sample_input = tf.placeholder(tf.float32, shape=[1, vocabulary_size])\n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input, saved_sample_output, saved_sample_state)\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 41
      },
      {
       "item_id": 80
      },
      {
       "item_id": 126
      },
      {
       "item_id": 144
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "executionInfo": {
     "elapsed": 199909,
     "status": "ok",
     "timestamp": 1445965877333,
     "user": {
      "color": "#1FA15D",
      "displayName": "Vincent Vanhoucke",
      "isAnonymous": false,
      "isMe": true,
      "permissionId": "05076109866853157986",
      "photoUrl": "//lh6.googleusercontent.com/-cCJa7dTDcgQ/AAAAAAAAAAI/AAAAAAAACgw/r2EZ_8oYer4/s50-c-k-no/photo.jpg",
      "sessionId": "6f6f07b359200c46",
      "userId": "102167687554210253930"
     },
     "user_tz": 420
    },
    "id": "RD9zQCZTEaEm",
    "outputId": "5e868466-2532-4545-ce35-b403cf5d9de6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 3.296779 learning rate: 10.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 27.03\n",
      "================================================================================\n",
      "ym  yfykedy wuiwazgctrcnclswdhsvep oyimcxcgi jc erreeeowarmnaapvdmcf tntxaeqjxsp\n",
      "oxyubmet x rnmiia h pezgnw yudcvopoxxcuuaszorwr wxhvkifjc   jey mbamalpdt egmctr\n",
      " aqdag ocrnakxrgiemspvfihzalnwtotftrls bo k  nca pekvlaciro esdtkwiqxdbhsyok v i\n",
      "nwr eksmiwx botrsdapb hwjcneffz f kpe  oh e kco u b xc z bk kai wjvcjin zidjte h\n",
      "newj llnzckeftcoprvah h y eae nsvidze hngiahm taatvssohoaxoxmrwroawdhtfhkdnl do \n",
      "================================================================================\n",
      "Validation set perplexity: 20.30\n",
      "Average loss at step 1000: 2.012156 learning rate: 10.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 5.82\n",
      "================================================================================\n",
      "mage spresian cesmenter tool  ore nine one seven oned equilsitional secour extor\n",
      "k the yeer heivhistflans is eres from zero one nine ans remable humber infofe fl\n",
      "gean iningations acreen seclustion moir nine is five sive in nation deacher cens\n",
      "rating execicr of enelly menin muce divive of inder the unibli p ches has proted\n",
      "gudeth in the caning hislheelhince of spite regrodd al eargater jlean three nine\n",
      "================================================================================\n",
      "Validation set perplexity: 6.15\n",
      "Average loss at step 2000: 1.728986 learning rate: 10.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 5.66\n",
      "================================================================================\n",
      "m midely spra mopthles world it of pecural tromuminalian dif rasistansogulal ain\n",
      "use as the cloz of chrresied in itsondersy spiding appacer constantyanchrei te s\n",
      "dia proging kind with in later and cauried or promital bejocces prodor doyzoudal\n",
      "lanal bays as andinsiture prograss andoanly a cituni to his one zero zemo and un\n",
      "lir hoving on peeral see becasion a caicate re toparchessal the med prosides dea\n",
      "================================================================================\n",
      "Validation set perplexity: 5.18\n",
      "Average loss at step 3000: 1.666682 learning rate: 10.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 5.27\n",
      "================================================================================\n",
      "metuh and billed reaald one one life grames by appeated theylorited gase figr ca\n",
      "vilutional a bewand macmprating calsion cland onlocally with accuration on one t\n",
      "nesers assocespood raophy isteral one six of the singles to dif of the velates t\n",
      "caltimal landacky vapers duristo decises hespeppels bos of tree suctor rare putu\n",
      "stand or runglible modical vidg expancas inclument one nine nine six four often \n",
      "================================================================================\n",
      "Validation set perplexity: 4.77\n",
      "Average loss at step 4000: 1.651502 learning rate: 10.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 4.78\n",
      "================================================================================\n",
      "zing where according zeeg it to extendence lat memberse armuaiation ged still fr\n",
      "neal under of the preeved todemat rilla master in same to gorbe demorrey betwing\n",
      "uding war applicibrise armengity with ascerpreted deflel doal peepional papitial\n",
      "feas mmysish first placies the underth places in during and obsond us americas t\n",
      "press seven diregatiun for shorames from sames show empeas of flata becomberriad\n",
      "================================================================================\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 5000: 1.624327 learning rate: 1.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 4.53\n",
      "================================================================================\n",
      "quanked speal and danydesler the campleggs vificing years s he unjues win met cl\n",
      "ing reform one six zero nine two zero two minhed hid five is death is imavildren\n",
      "ons scound suen f by the world developre death creative electrive reacti end w i\n",
      "x contacted by ass active dividenginifot five nine he between b as it monned the\n",
      "ra the had a form oromems its an or biagn and populase herkean of last smally fu\n",
      "================================================================================\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 6000: 1.578943 learning rate: 1.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 4.87\n",
      "================================================================================\n",
      "word hage one nine nine five seven gine a cut expirits in the bylex trabaics the\n",
      "rened marois the egbunate new their speepner in canfoutting and day of englard r\n",
      "als one nine sifn transt a che by goelted from the fead dus of eight four millio\n",
      "freors in the pose distruction example ig onliby with gaines or still sverk the \n",
      "has hos lize relaw spherit mescoundings howaso partius musing agreder of distrib\n",
      "================================================================================\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 7000: 1.568930 learning rate: 1.000000\n",
      "predictions.shape: (640, 27)\n",
      "labels.shape: (640, 27)\n",
      "Minibatch perplexity: 5.22\n",
      "================================================================================\n",
      "hidaws havency asteries spitch science for the conailted and on the leges on ath\n",
      "k mahbross s began lankel and six shootly regations up ebabout and eighes and wa\n",
      "s pieter appligen davexelisatious with the derward code government of examerier \n",
      "k inclus rars to of cature accorded they infor the fillion the historical madali\n",
      "n one nine the side of mainve of and attloold iis an is new without of he weald \n",
      "================================================================================\n",
      "Validation set perplexity: 4.22\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 1000\n",
    "\n",
    "with tf.Session(graph=graph) as session:\n",
    "  tf.global_variables_initializer().run()\n",
    "  print('Initialized')\n",
    "  mean_loss = 0\n",
    "  for step in range(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    #print('batches[0].shape:', batches[0].shape)\n",
    "    feed_dict = dict()\n",
    "    for i in range(num_unrollings + 1):\n",
    "      feed_dict[train_data[i]] = batches[i]\n",
    "    _, l, predictions, lr = session.run(\n",
    "      [optimizer, loss, train_prediction, learning_rate], feed_dict=feed_dict)\n",
    "    mean_loss += l\n",
    "    if step % summary_frequency == 0:\n",
    "      if step > 0:\n",
    "        mean_loss = mean_loss / summary_frequency\n",
    "      # The mean loss is an estimate of the loss over the last few batches.\n",
    "      print(\n",
    "        'Average loss at step %d: %f learning rate: %f' % (step, mean_loss, lr))\n",
    "      mean_loss = 0\n",
    "      labels = np.concatenate(list(batches)[1:])\n",
    "      print('predictions.shape:', predictions.shape)\n",
    "      print('labels.shape:', labels.shape)\n",
    "      print('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "      if step % (summary_frequency * 1) == 0:\n",
    "        # Generate some samples.\n",
    "        print('=' * 80)\n",
    "        for _ in range(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in range(79):\n",
    "            prediction = sample_prediction.eval({sample_input: feed})\n",
    "            feed = sample(prediction)\n",
    "            sentence += characters(feed)[0]\n",
    "          print(sentence)\n",
    "        print('=' * 80)\n",
    "      # Measure validation set perplexity.\n",
    "      reset_sample_state.run()\n",
    "      valid_logprob = 0\n",
    "      for _ in range(valid_size):\n",
    "        b = valid_batches.next()\n",
    "        predictions = sample_prediction.eval({sample_input: b[0]})\n",
    "        valid_logprob = valid_logprob + logprob(predictions, b[1])\n",
    "      print('Validation set perplexity: %.2f' % float(np.exp(\n",
    "        valid_logprob / valid_size)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "pl4vtmFfa5nn"
   },
   "source": [
    "---\n",
    "Problem 1\n",
    "---------\n",
    "\n",
    "You might have noticed that the definition of the LSTM cell involves 4 matrix multiplications with the input, and 4 matrix multiplications with the output. Simplify the expression by using a single matrix multiply for each, and variables that are 4 times larger.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# https://github.com/ponderousmad/ud730/blob/master/6_lstm.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "  '''\n",
    "  # Parameters:\n",
    "  # Input gate: input, previous output, and bias.\n",
    "  ix = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  im = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ib = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Forget gate: input, previous output, and bias.\n",
    "  fx = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  fm = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  fb = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cx = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  cm = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  cb = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  # Output gate: input, previous output, and bias.\n",
    "  ox = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes], -0.1, 0.1))\n",
    "  om = tf.Variable(tf.truncated_normal([num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ob = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  '''\n",
    "\n",
    "  gate_count = 4\n",
    "  # Parameters:\n",
    "  # Gates: input gate, forget gate, memory cell, and output gate.\n",
    "  input_weights = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes * gate_count], -0.1, 0.1))\n",
    "  output_weights = tf.Variable(tf.truncated_normal([num_nodes, num_nodes * gate_count], -0.1, 0.1))\n",
    "  bias = tf.Variable(tf.zeros([1, num_nodes * gate_count]))\n",
    "        \n",
    "  # Variables saving state across unrollings.\n",
    "  saved_output = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  saved_state = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  # Classifier weights and biases.\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    ''' \n",
    "    input_gate = tf.sigmoid(tf.matmul(i, ix) + tf.matmul(o, im) + ib)\n",
    "    forget_gate = tf.sigmoid(tf.matmul(i, fx) + tf.matmul(o, fm) + fb)\n",
    "    update = tf.matmul(i, cx) + tf.matmul(o, cm) + cb\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\n",
    "    output_gate = tf.sigmoid(tf.matmul(i, ox) + tf.matmul(o, om) + ob)    \n",
    "    '''\n",
    "    values = tf.split(axis=1, num_or_size_splits=gate_count, value=tf.matmul(i, input_weights) + tf.matmul(o, output_weights) + bias)\n",
    "    \n",
    "    input_gate = tf.sigmoid(values[0])\n",
    "    forget_gate = tf.sigmoid(values[1])\n",
    "    update = values[2]\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\n",
    "    output_gate = tf.sigmoid(values[3])\n",
    "    \n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in range(num_unrollings + 1):\n",
    "    train_data.append(\n",
    "      tf.placeholder(tf.float32, shape=[batch_size,vocabulary_size]))\n",
    "  train_inputs = train_data[:num_unrollings]\n",
    "  train_labels = train_data[1:]  # labels are inputs shifted by one time step.\n",
    "\n",
    "  # Unrolled LSTM loop.\n",
    "  outputs = list()\n",
    "  output = saved_output\n",
    "  state = saved_state\n",
    "  for i in train_inputs:\n",
    "    output, state = lstm_cell(i, output, state)\n",
    "    outputs.append(output)\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state)]):\n",
    "    # Classifier.\n",
    "    logits = tf.nn.xw_plus_b(tf.concat(outputs, 0), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        labels=tf.concat(train_labels, 0), logits=logits))\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 5000, 0.1, staircase=True)\n",
    "  optimizer = tf.train.GradientDescentOptimizer(learning_rate)\n",
    "  gradients, v = zip(*optimizer.compute_gradients(loss))\n",
    "  gradients, _ = tf.clip_by_global_norm(gradients, 1.25)\n",
    "  optimizer = optimizer.apply_gradients(\n",
    "    zip(gradients, v), global_step=global_step)\n",
    "\n",
    "  # Predictions.\n",
    "  train_prediction = tf.nn.softmax(logits)\n",
    "  \n",
    "  # Sampling and validation eval: batch 1, no unrolling.\n",
    "  sample_input = tf.placeholder(tf.float32, shape=[1, vocabulary_size])\n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input, saved_sample_output, saved_sample_state)\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 3.297052 learning rate: 10.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 27.03\n",
      "================================================================================\n",
      "tdhsevef iybiob iusivertrggusdiqkup nex fwoqvai  el etbnrobj a etavhueezhcba a n\n",
      "rxxjet kpvtdkul kf zo  bxoog  ieqtw ntutewsjafosnyilfvbfiy ryivp gpenokdufd uay \n",
      "bh axe  nxuupl   gcxvi kmteih qdebibf wdulwa grikij a d ftotqf  jergevgvq  ro vj\n",
      "n qa sydpx hvsejqiqvgve daqemx   o uumjhlvs glngwwl scljyz  eq ajjyhq wmfi teaar\n",
      "joxnycata  xf lm   he  v ae  estakycccrhh g  e y jwsihoueoepxekzacd oertknapnrdp\n",
      "================================================================================\n",
      "Validation set perplexity: 20.03\n",
      "Average loss at step 1000: 2.019924 learning rate: 10.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 6.51\n",
      "Validation set perplexity: 5.99\n",
      "Average loss at step 2000: 1.734045 learning rate: 10.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 5.08\n",
      "================================================================================\n",
      "pend longt be the preded cald plods the soch the ghesh back battucty luters a co\n",
      "me of beforued possitional phain plair hohe the s others and supenion lether mad\n",
      "nsus sar sears allowide lay strished offere loyers auveriam of truich commovacie\n",
      "warp phonem visetery toszal formantal continiett and the the buitt and forbly si\n",
      "con by one jeard best this national of intermize that he feestral ficlued diffic\n",
      "================================================================================\n",
      "Validation set perplexity: 5.35\n",
      "Average loss at step 3000: 1.685248 learning rate: 10.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 4.89\n",
      "Validation set perplexity: 5.17\n",
      "Average loss at step 4000: 1.650138 learning rate: 10.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 5.58\n",
      "================================================================================\n",
      "quess in curteg was ressu s metter the liftul prolops loughs vis an zero austras\n",
      "boxs asseven edits desect attending to of he add cleastry pnokech as armitry to \n",
      " karts inurdat in namirs zero six eight emist clare see arterse adout noo cugism\n",
      "ogasia were and euro adawn lecher off was of belen rilive guikes dies invedsior \n",
      "man american the year city one eight nound attembely effectul by the mudibnays c\n",
      "================================================================================\n",
      "Validation set perplexity: 4.83\n",
      "Average loss at step 5000: 1.618849 learning rate: 1.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 4.84\n",
      "Validation set perplexity: 4.81\n",
      "Average loss at step 6000: 1.586305 learning rate: 1.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 4.78\n",
      "================================================================================\n",
      "a livelokal is vare computers and stateting consisuating which port sarists of t\n",
      "uts for zour who may larmera and poges in the active to allors aromatvonwingon b\n",
      "veration of the stroanmer blat four menica other board controllern kupror the ca\n",
      "g fundariouthys to schnole x lone to the meditian is declvion assume on of tratm\n",
      "es new network examplina hus for antwin in in derop a lodi jaw when corpbery the\n",
      "================================================================================\n",
      "Validation set perplexity: 4.47\n",
      "Average loss at step 7000: 1.578254 learning rate: 1.000000\n",
      "predictions.shape:  (640, 27)\n",
      "labels.shape:  (640, 27)\n",
      "Minibatch perplexity: 5.03\n",
      "Validation set perplexity: 4.54\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 1000\n",
    "\n",
    "with tf.Session(graph=graph) as session:\n",
    "  tf.global_variables_initializer().run()\n",
    "  print('Initialized')\n",
    "  mean_loss = 0\n",
    "  for step in range(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in range(num_unrollings + 1):\n",
    "      feed_dict[train_data[i]] = batches[i]\n",
    "    _, l, predictions, lr = session.run(\n",
    "      [optimizer, loss, train_prediction, learning_rate], feed_dict=feed_dict)\n",
    "    mean_loss += l\n",
    "    if step % summary_frequency == 0:\n",
    "      if step > 0:\n",
    "        mean_loss = mean_loss / summary_frequency\n",
    "      # The mean loss is an estimate of the loss over the last few batches.\n",
    "      print(\n",
    "        'Average loss at step %d: %f learning rate: %f' % (step, mean_loss, lr))\n",
    "      mean_loss = 0\n",
    "      labels = np.concatenate(list(batches)[1:])\n",
    "      print('predictions.shape: ', predictions.shape)\n",
    "      print('labels.shape: ', labels.shape)\n",
    "        \n",
    "      print('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "      if step % (summary_frequency * 2) == 0:\n",
    "        # Generate some samples.\n",
    "        print('=' * 80)\n",
    "        for _ in range(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in range(79):\n",
    "            prediction = sample_prediction.eval({sample_input: feed})\n",
    "            feed = sample(prediction)\n",
    "            sentence += characters(feed)[0]\n",
    "          print(sentence)\n",
    "        print('=' * 80)\n",
    "      # Measure validation set perplexity.\n",
    "      reset_sample_state.run()\n",
    "      valid_logprob = 0\n",
    "      for _ in range(valid_size):\n",
    "        b = valid_batches.next()\n",
    "        predictions = sample_prediction.eval({sample_input: b[0]})\n",
    "        valid_logprob = valid_logprob + logprob(predictions, b[1])\n",
    "      print('Validation set perplexity: %.2f' % float(np.exp(\n",
    "        valid_logprob / valid_size)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "4eErTCTybtph"
   },
   "source": [
    "---\n",
    "Problem 2\n",
    "---------\n",
    "\n",
    "We want to train a LSTM over bigrams, that is pairs of consecutive characters like 'ab' instead of single characters like 'a'. Since the number of possible bigrams is large, feeding them directly to the LSTM using 1-hot encodings will lead to a very sparse representation that is very wasteful computationally.\n",
    "\n",
    "a- Introduce an embedding lookup on the inputs, and feed the embeddings to the LSTM cell instead of the inputs themselves.\n",
    "\n",
    "b- Write a bigram-based LSTM, modeled on the character LSTM above.\n",
    "\n",
    "c- Introduce Dropout. For best practices on how to use Dropout in LSTMs, refer to this [article](http://arxiv.org/abs/1409.2329).\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "unique_bigrams = vocabulary_size * vocabulary_size\n",
    "\n",
    "def encode_bigram(characters):\n",
    "    first = char2id(characters[0])\n",
    "    second = (char2id(characters[1]) if len(characters) > 1 else 0)\n",
    "    return first * vocabulary_size + second\n",
    "\n",
    "def decode_bigram(bigram_id):\n",
    "    second = bigram_id % vocabulary_size\n",
    "    first = (bigram_id - second) // vocabulary_size\n",
    "    return \"\".join([id2char(first), id2char(second)])\n",
    "\n",
    "# this part seems not finished yet by the original author\n",
    "class BigramBatchGenerator(object):\n",
    "    def __init__(self, text, size, unrolls):\n",
    "        self._text = text\n",
    "        self._text_size = len(text)\n",
    "        self._batch_size = size\n",
    "        self._unrolls = unrolls\n",
    "        segment = self._text_size // (2 * size)\n",
    "        self._cursor = [offset * segment for offset in range(size)]\n",
    "        self._last_batch = self._next_batch()\n",
    "  \n",
    "    def _next_batch(self):\n",
    "        \"\"\"Generate a single batch from the current cursor position in the data.\"\"\"\n",
    "        batch = np.zeros(shape=(self._batch_size), dtype=np.int)\n",
    "        for b in range(self._batch_size):\n",
    "            batch[b] = encode_bigram(self._text[self._cursor[b]:self._cursor[b] + 2])\n",
    "            self._cursor[b] = (self._cursor[b] + 2) % self._text_size\n",
    "        return batch\n",
    "  \n",
    "    def next(self):\n",
    "        \"\"\"Generate the next array of batches from the data. The array consists of\n",
    "        the last batch of the previous array, followed by num_unrollings new ones.\n",
    "        \"\"\"\n",
    "        batches = [self._last_batch]\n",
    "        for step in range(self._unrolls):\n",
    "            batches.append(self._next_batch())\n",
    "        self._last_batch = batches[-1]\n",
    "        return batches\n",
    "\n",
    "def bigrams(encoded_bigrams):\n",
    "    \"\"\"Turn encoded bigrams back into its (most likely) character representation.\"\"\"\n",
    "    return [decode_bigram(int(b)) for b in encoded_bigrams]\n",
    "\n",
    "def bibatches2string(batches):\n",
    "    \"\"\"Convert a sequence of batches back into their (most likely) string\n",
    "    representation.\"\"\"\n",
    "    s = [''] * batches[0].shape[0]\n",
    "    for b in batches:\n",
    "        s = [''.join(x) for x in zip(s, bigrams(b))]\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ons anarchists advocate social\n",
      "['ons anarchists advocat', 'nts and release day ev', 'y eight inch two zero ', 'one nine seven zero s ', 'o two one nine zero th']\n",
      "['ate social relations b', 'events apple has gener', 'o three mm of armour s', 's because in winter th', 'three publ one nine on']\n",
      "[' based upon voluntary ', 'erally chosen to stick', ' survived hits from on', 'the canal freezes befo', 'one three p seven two ']\n",
      "['y association of auton', 'ck with some loose use', 'one five inch three ei', 'fore the lakes and the', 'o zero on dark matter ']\n"
     ]
    }
   ],
   "source": [
    "print(train_text[:30])\n",
    "\n",
    "bigram_batches = BigramBatchGenerator(train_text, 5, 10)\n",
    "\n",
    "print(bibatches2string(bigram_batches.next()))\n",
    "print(bibatches2string(bigram_batches.next()))\n",
    "print(bibatches2string(bigram_batches.next()))\n",
    "print(bibatches2string(bigram_batches.next()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input_weights.shape: Tensor(\"Variable_1/read:0\", shape=(36, 256), dtype=float32)\n",
      "output_weights.shape: Tensor(\"Variable_2/read:0\", shape=(64, 256), dtype=float32)\n",
      "bias.shape: Tensor(\"Variable_3/read:0\", shape=(1, 256), dtype=float32)\n",
      "train_prediction.shape: (640, 36)\n",
      "sample_prediction.shape: (1, 36)\n"
     ]
    }
   ],
   "source": [
    "num_nodes = 64\n",
    "bigrams_vsize = vocabulary_size * vocabulary_size\n",
    "embedding_vsize = 36\n",
    "\n",
    "def sample_vsize():\n",
    "  v = np.zeros(shape=(1), dtype=np.int)\n",
    "  v[0] = random.randint(0,  bigrams_vsize- 1)\n",
    "  return v\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "\n",
    "  gate_count = 4\n",
    "  # Parameters:\n",
    "  embeddings = tf.Variable(tf.random_uniform([bigrams_vsize, embedding_vsize], -0.1, 0.1))\n",
    "\n",
    "  # Gates: input gate, forget gate, memory cell, and output gate.\n",
    "  input_weights = tf.Variable(tf.truncated_normal([embedding_vsize, num_nodes * gate_count], -0.1, 0.1))\n",
    "  output_weights = tf.Variable(tf.truncated_normal([num_nodes, num_nodes * gate_count], -0.1, 0.1))\n",
    "  bias = tf.Variable(tf.zeros([1, num_nodes * gate_count]))\n",
    "\n",
    "  print(\"input_weights.shape:\", input_weights)\n",
    "  print(\"output_weights.shape:\", output_weights)\n",
    "  print(\"bias.shape:\", bias)\n",
    "\n",
    "\n",
    "  # Variables saving state across unrollings.\n",
    "  saved_output = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  saved_state = tf.Variable(tf.zeros([batch_size, num_nodes]), trainable=False)\n",
    "  # Classifier weights and biases.\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, embedding_vsize], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([embedding_vsize]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    values = tf.split(axis=1, num_or_size_splits=gate_count, value=tf.matmul(i, input_weights) + tf.matmul(o, output_weights) + bias)\n",
    "    \n",
    "    input_gate = tf.sigmoid(values[0])\n",
    "    forget_gate = tf.sigmoid(values[1])\n",
    "    update = values[2]\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\n",
    "    output_gate = tf.sigmoid(values[3])\n",
    "    \n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  \"\"\"\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in range(num_unrollings + 1):\n",
    "    train_data.append(\n",
    "      tf.placeholder(tf.float32, shape=[batch_size,vocabulary_size]))\n",
    "  train_inputs = train_data[:num_unrollings]\n",
    "  train_labels = train_data[1:]  # labels are inputs shifted by one time step.  \n",
    "  \"\"\"\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  train_embeddings = list()\n",
    "  for _ in range(num_unrollings + 1):\n",
    "    train_data.append(tf.placeholder(tf.int32, shape=[batch_size]))\n",
    "    train_embeddings.append(tf.nn.embedding_lookup(embeddings, train_data[-1]))\n",
    "  \n",
    "  train_inputs = train_embeddings[:num_unrollings]\n",
    "  train_labels = train_embeddings[1:]  # labels are inputs shifted by one time step.\n",
    "\n",
    "\n",
    "  # Unrolled LSTM loop.\n",
    "  outputs = list()\n",
    "  output = saved_output\n",
    "  state = saved_state\n",
    "  for i in train_inputs:\n",
    "    output, state = lstm_cell(i, output, state)\n",
    "    outputs.append(output)\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state)]):\n",
    "    # Classifier.\n",
    "    logits = tf.nn.xw_plus_b(tf.concat(outputs, 0), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        labels=tf.concat(train_labels, 0), logits=logits))\n",
    "\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 5000, 0.1, staircase=True)\n",
    "  optimizer = tf.train.GradientDescentOptimizer(learning_rate)\n",
    "  gradients, v = zip(*optimizer.compute_gradients(loss))\n",
    "  gradients, _ = tf.clip_by_global_norm(gradients, 1.25)\n",
    "  optimizer = optimizer.apply_gradients(\n",
    "    zip(gradients, v), global_step=global_step)\n",
    "\n",
    "  # Predictions.\n",
    "  train_prediction = tf.nn.softmax(logits)\n",
    "  print(\"train_prediction.shape:\", train_prediction.shape)\n",
    "\n",
    "  embedding_norm = tf.sqrt(tf.reduce_sum(tf.square(embeddings), 1, keep_dims=True))\n",
    "  embedding_normalized = embeddings / embedding_norm\n",
    "\n",
    "  # Compute the similarity between validation examples and all embeddings using cosine distance:\n",
    "  valid_dataset = tf.constant( np.array(range(bigrams_vsize)), dtype=tf.int32)\n",
    "  valid_embeddings = tf.nn.embedding_lookup(embedding_normalized, valid_dataset)\n",
    "  similarity = tf.matmul(valid_embeddings, tf.transpose(embedding_normalized))\n",
    "\n",
    "    \n",
    "  # Sampling and validation eval: batch 1, no unrolling.\n",
    "  sample_input = tf.placeholder(tf.int32, shape=[1])\n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "\n",
    "  sample_embedding = tf.nn.embedding_lookup(embeddings, sample_input)\n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_embedding, saved_sample_output, saved_sample_state)\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))\n",
    "    print(\"sample_prediction.shape:\", sample_prediction.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 0.108175 learning rate: 10.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.39\n",
      "=============================================\n",
      "nqvoqliszzbtbq hznznzzja y scqisqtpqepkbpq\n",
      "aixcujabbq hzzbq hznznzzbqzqqlcqcqcqisznzn\n",
      "uair hujkk nbtep siszzepjrzze cqabbte fdpq\n",
      "oigobtep sabbtbte kkjrqt hqt hznzzja ykbzq\n",
      "yfjx y ne fdzqpqbtjaujfdzfjrzn ykbzqqlfdzq\n",
      "=============================================\n",
      "Validation set perplexity: 0.96\n",
      "Average loss at step 1000: -22.784611 learning rate: 10.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "yakme fdofe fdsengononheng oe kkon o s acq\n",
      "kcbcan tsean skk scqfdngheofonve oone kk t\n",
      "ezvkhye hyve i i ove i oe cqabhese acqhy a\n",
      "rsomab ionin sanine fd acqabtihye fdofonon\n",
      "hay onon iheof a t ahy aine kkon ovetikkon\n",
      "=============================================\n",
      "Validation set perplexity: 0.23\n",
      "Average loss at step 2000: -23.137964 learning rate: 10.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "quar acqab i i oone fdofonone fdngtihye kk\n",
      "oyaongheofe kk tse ahy s ahy sof a tofve o\n",
      "vgtmngtifd aab iticqkkine kkon i i oonon a\n",
      "cbubkkon oveheng iheaninveticqhyonone fdse\n",
      "wysc tng i oonve oe cqfdnghean skkhe tsean\n",
      "=============================================\n",
      "Validation set perplexity: 0.31\n",
      "Average loss at step 3000: -22.942581 learning rate: 10.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "ftmn s afdofe kkheon oonon sse aab ove ihe\n",
      "suipkkontiab iheanheon oe kkheontifdanine \n",
      "am aseng ovehe aabhe ahy ssenghesengheanhe\n",
      "wbxpseofone cqfd aabtikkheon ihesengonon i\n",
      "kk   shyve i ove itikkin ahein aheon oone \n",
      "=============================================\n",
      "Validation set perplexity: 0.34\n",
      "Average loss at step 4000: -23.040658 learning rate: 10.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "kesmse acqcqcqkk scqabtihy ssese akkhehe t\n",
      "  kkon itikkhe tng itiabhe ahy a tofe cqhy\n",
      "cdpqheofone kk tofone hyonon sofon ainveon\n",
      "mgc  ain sanhe tseseng o a tan t ahy sseng\n",
      "ktsftihy s akkine fdseofonon sofone kk tof\n",
      "=============================================\n",
      "Validation set perplexity: 0.37\n",
      "Average loss at step 5000: -22.904466 learning rate: 1.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "pvyu ihengheofvehengticqfdanheonhe akk t a\n",
      "ezvkabhe acqfdse ahye cqfdan tanon ionhe t\n",
      "cvxqhye cqabtihy a scqhyon sofonve iononon\n",
      "axmwhy s acqkk sab o san tng ionheon ihean\n",
      " dveon skk sfdofon s aabheofe hy aheheon i\n",
      "=============================================\n",
      "Validation set perplexity: 0.28\n",
      "Average loss at step 6000: -16.240687 learning rate: 1.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "rqjbhy aheonhengon t aabonon oveheofvetiab\n",
      "xrwrab oe ab ion tsenghengtikk tngheofone \n",
      "inon sfdof aononhehe t akkin sngtiabonheon\n",
      "luirnghese ahy sofone fd akkheontikk tan t\n",
      "nkuoine cqabticqhyononon ahe taninon a tse\n",
      "=============================================\n",
      "Validation set perplexity: 0.45\n",
      "Average loss at step 7000: -16.184926 learning rate: 1.000000\n",
      "predictions.shape:  (640, 36)\n",
      "labels.shape:  (640, 36)\n",
      "Minibatch perplexity: 0.00\n",
      "=============================================\n",
      "sdvftiabon tngticqcqkk shyve oe cqcqabtikk\n",
      "uznze hyvetihyveonine abheng oveheof a t a\n",
      "qfpx afd ahyononone hyve ionhe scqhye abhe\n",
      "fwzgon o ainon aon oe kkheinonon s acqfdof\n",
      "filt a sfdngtikkinononon ainonve ion sfd a\n",
      "=============================================\n",
      "Validation set perplexity: 0.42\n"
     ]
    }
   ],
   "source": [
    "train_batches = BigramBatchGenerator(train_text, batch_size, num_unrollings)\n",
    "valid_batches = BigramBatchGenerator(valid_text, 1, 1)\n",
    "\n",
    "num_steps = 7001\n",
    "summary_frequency = 1000\n",
    "\n",
    "\n",
    "with tf.Session(graph=graph) as session:\n",
    "  tf.global_variables_initializer().run()\n",
    "  print('Initialized')\n",
    "  mean_loss = 0\n",
    "  for step in range(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in range(num_unrollings + 1):\n",
    "      feed_dict[train_data[i]] = batches[i]\n",
    "    _, l, predictions, lr = session.run(\n",
    "      [optimizer, loss, train_prediction, learning_rate], feed_dict=feed_dict)\n",
    "    mean_loss += l\n",
    "    if step % summary_frequency == 0:\n",
    "      if step > 0:\n",
    "        mean_loss = mean_loss / summary_frequency\n",
    "      # The mean loss is an estimate of the loss over the last few batches.\n",
    "      print(\n",
    "        'Average loss at step %d: %f learning rate: %f' % (step, mean_loss, lr))\n",
    "      mean_loss = 0\n",
    "    \n",
    "      #labels = np.concatenate(list(batches)[1:]) \n",
    "      # we need to call lookup embedding to figure out the labels\n",
    "      new_batches = list()\n",
    "      for batch in list(batches)[1:]:\n",
    "        #batch = np.zeros(shape=(batch_size), dtype=np.int)\n",
    "        #new_batch = np.zeros(shape=(batch_size, embedding_vsize), dtype=np.int)\n",
    "        new_batch = tf.nn.embedding_lookup(embeddings, batch)\n",
    "        new_batches.append( new_batch.eval() )\n",
    "      labels = np.concatenate(list(new_batches)) \n",
    "    \n",
    "      print('predictions.shape: ', predictions.shape)\n",
    "      print('labels.shape: ', labels.shape)\n",
    "        \n",
    "      print('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "    \n",
    "      if step % (summary_frequency) == 0:\n",
    "        # Generate some samples.\n",
    "        sim = similarity.eval()\n",
    "        print('=' * 45)\n",
    "        for _ in range(5):\n",
    "          feed = sample_vsize()\n",
    "          sentence = decode_bigram(feed) #\"_init_\"\n",
    "          reset_sample_state.run()\n",
    "          for _ in range(20):\n",
    "            prediction = sample_prediction.eval({sample_input: feed})\n",
    "            st = (-sim[feed[0], :]).argsort()\n",
    "            top_K = 5\n",
    "            nearest = st[1:top_K+1]\n",
    "            s_id = random.randint(0,  top_K-1)\n",
    "            sentence += decode_bigram( nearest[s_id] )\n",
    "            feed[0] = s_id\n",
    "            \n",
    "            # we should sample next value for feed\n",
    "            #print(\"s_id:\", s_id)\n",
    "            \n",
    "          print(sentence)\n",
    "        print('=' * 45)\n",
    "    \n",
    "      # Measure validation set perplexity.\n",
    "      reset_sample_state.run()\n",
    "      valid_logprob = 0\n",
    "      dbg = 0\n",
    "      for _ in range(50):\n",
    "        b = valid_batches.next()\n",
    "        predictions = sample_prediction.eval({sample_input: b[0]})\n",
    "        expect = tf.nn.embedding_lookup(embeddings, b[1])\n",
    "        # very expensive operation\n",
    "        expect_val = expect.eval() \n",
    "        valid_logprob = valid_logprob + logprob(predictions, expect_val )\n",
    "        \n",
    "      print('Validation set perplexity: %.2f' % float(np.exp(\n",
    "        valid_logprob / valid_size)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": true,
    "editable": true,
    "id": "Y5tapX3kpcqZ"
   },
   "source": [
    "---\n",
    "Problem 3\n",
    "---------\n",
    "\n",
    "(difficult!)\n",
    "\n",
    "Write a sequence-to-sequence LSTM which mirrors all the words in a sentence. For example, if your input is:\n",
    "\n",
    "    the quick brown fox\n",
    "    \n",
    "the model should attempt to output:\n",
    "\n",
    "    eht kciuq nworb xof\n",
    "    \n",
    "Refer to the lecture on how to put together a sequence-to-sequence model, as well as [this article](http://arxiv.org/abs/1409.3215) for best practices.\n",
    "\n",
    "---"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "default_view": {},
   "name": "6_lstm.ipynb",
   "provenance": [],
   "version": "0.3.2",
   "views": {}
  },
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}