6_lstm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8tQJd2YSCfWR"
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "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,
    "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",
    "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",
    "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",
    "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",
    "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",
    "id": "Zdw6i4F8glpp"
   },
   "source": [
    "Utility functions to map characters to vocabulary IDs and back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcdefghijklmnopqrstuvwxyz\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "97"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(string.ascii_lowercase)\n",
    "ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "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",
    "id": "lFwoyygOmWsL"
   },
   "source": [
    "Function to generate a training batch for the LSTM model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "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",
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(64, 27)\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",
      "['ate social ', 'ments faile', 'al park pho', 'ies index s', 'ess of cast', ' h provided', 'guage among', 'gers in dec', 'al media an', ' during the', 'known manuf', 'seven a wid', 's covering ', 'en one of t', 'ze single a', ' first card', ' in jersey ', 'he poverty ', 'gns of huma', ' cause so a', 'n denatural', 'ce formatio', 'the input u', 'ck to pull ', 'usion inabi', 'omplete an ', 't of the mi', ' it fort de', 'ttempts by ', 'ormats for ', 'soteric chr', 'growing pop', 'riginal doc', 'e nine eigh', 'rch eight l', 'haracter li', 'al mechanic', ' gm compari', 's fundament', 'lieve the c', 'ast not par', ' upon by hi', ' example rl', 'ed on the w', 'he official', 'on at this ', 'ne three tw', 'inux enterp', ' daily coll', 'ration camp', 'ehru wished', 'stiff from ', 'arman s syd', 'o to begin ', 'itiatives t', 'these autho', 'icky ricard', 'w of mathem', 'ent of arm ', 'credited pr', 'e external ', ' other stat', ' buddhism e', 'vices possi']\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(train_batches.next()[0].shape)\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": 76,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "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": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.06355949  0.01966848  0.04420629  0.01924765  0.01798902  0.04027735\n",
      "   0.05360364  0.02983408  0.04180465  0.01599998  0.00718631  0.02520396\n",
      "   0.04442188  0.05484052  0.04589446  0.06477327  0.02576457  0.02080245\n",
      "   0.01635039  0.04966093  0.06118123  0.00054691  0.07042913  0.017762\n",
      "   0.02200258  0.05993259  0.06705618]]\n",
      "22\n",
      "[[ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.\n",
      "   0.  0.  0.  0.  0.  0.  0.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "test_d = random_distribution()\n",
    "print(test_d)\n",
    "sam_d = sample_distribution(test_d[0])\n",
    "print(sam_d)\n",
    "sam = sample(test_d)\n",
    "print(sam)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "K8f67YXaDr4C"
   },
   "source": [
    "### Simple LSTM Model.\n",
    "![lstm model](./pictures/simple_lstm_model.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "Q5rxZK6RDuGe"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(64, 27)\n",
      "(64, 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",
    "  print(train_inputs[0].shape)\n",
    "  print(train_labels[0].shape)\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": 16,
   "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": 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.231375 learning rate: 10.000000\n",
      "Minibatch perplexity: 25.31\n",
      "================================================================================\n",
      "c                               e                                   a           \n",
      "a                                                                               \n",
      "u                  i                           e                   t            \n",
      "st                                                        e      t             e\n",
      "w                                                     a                         \n",
      "================================================================================\n",
      "Validation set perplexity: 283.24\n",
      "Average loss at step 100: 2.784141 learning rate: 10.000000\n",
      "Minibatch perplexity: 11.88\n",
      "Validation set perplexity: 10.97\n",
      "Average loss at step 200: 2.334608 learning rate: 10.000000\n",
      "Minibatch perplexity: 9.20\n",
      "Validation set perplexity: 9.49\n",
      "Average loss at step 300: 2.200495 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.23\n",
      "Validation set perplexity: 8.88\n",
      "Average loss at step 400: 2.120760 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.11\n",
      "Validation set perplexity: 8.55\n",
      "Average loss at step 500: 2.067178 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.01\n",
      "Validation set perplexity: 8.00\n",
      "Average loss at step 600: 2.028710 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.91\n",
      "Validation set perplexity: 7.99\n",
      "Average loss at step 700: 1.972855 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.06\n",
      "Validation set perplexity: 7.56\n",
      "Average loss at step 800: 1.934696 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.61\n",
      "Validation set perplexity: 7.24\n",
      "Average loss at step 900: 1.937983 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.66\n",
      "Validation set perplexity: 7.21\n",
      "Average loss at step 1000: 1.932748 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.42\n",
      "================================================================================\n",
      "g his dilace it he the cell strely weolieve the kepheated derive five zeor the s\n",
      "ber kunowh teaters coside his the of thm the known fardh rewerions one agect of \n",
      "smicser sea migh aga and coll one hibs comsulring porter counox vadead one nener\n",
      "jos nabmev oh gisben mesius decend teme recaple moind susseven simple bleand bec\n",
      "degraty filsm firct the the rowty sucplheption skotionad suade with was titnant \n",
      "================================================================================\n",
      "Validation set perplexity: 6.97\n",
      "Average loss at step 1100: 1.884629 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.04\n",
      "Validation set perplexity: 6.71\n",
      "Average loss at step 1200: 1.858138 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.63\n",
      "Validation set perplexity: 6.54\n",
      "Average loss at step 1300: 1.838943 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.52\n",
      "Validation set perplexity: 6.52\n",
      "Average loss at step 1400: 1.855551 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.44\n",
      "Validation set perplexity: 6.40\n",
      "Average loss at step 1500: 1.846915 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.36\n",
      "Validation set perplexity: 6.35\n",
      "Average loss at step 1600: 1.851782 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.12\n",
      "Validation set perplexity: 6.32\n",
      "Average loss at step 1700: 1.819543 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.20\n",
      "Validation set perplexity: 6.15\n",
      "Average loss at step 1800: 1.779569 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.10\n",
      "Validation set perplexity: 6.00\n",
      "Average loss at step 1900: 1.751331 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.74\n",
      "Validation set perplexity: 5.86\n",
      "Average loss at step 2000: 1.803476 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.48\n",
      "================================================================================\n",
      "by one eight tratt on tiven conce imed fod a prignish thad aper thass jopple for\n",
      "ver to zero zero zero zero a showeving vuspasling oldweab higdopentiguainy as it\n",
      "gral for doncud argues daquation bioply smeafuf may s lang on in impenging ameta\n",
      "y this the inccombendes show stictrimits nensine and tenting impotitn bosavillin\n",
      "ut s deon annis serent a seven untly one chropaling realtan to geal mohn chored \n",
      "================================================================================\n",
      "Validation set perplexity: 5.82\n",
      "Average loss at step 2100: 1.793995 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.59\n",
      "Validation set perplexity: 5.63\n",
      "Average loss at step 2200: 1.782666 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.89\n",
      "Validation set perplexity: 5.64\n",
      "Average loss at step 2300: 1.738899 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.60\n",
      "Validation set perplexity: 5.44\n",
      "Average loss at step 2400: 1.760871 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.64\n",
      "Validation set perplexity: 5.47\n",
      "Average loss at step 2500: 1.771031 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.01\n",
      "Validation set perplexity: 5.34\n",
      "Average loss at step 2600: 1.745441 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.26\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 2700: 1.747218 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.95\n",
      "Validation set perplexity: 5.28\n",
      "Average loss at step 2800: 1.741506 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.03\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 2900: 1.741125 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.16\n",
      "Validation set perplexity: 5.28\n",
      "Average loss at step 3000: 1.729503 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.29\n",
      "================================================================================\n",
      "xisking the jostang formas anticection he machear addariemal archander into reea\n",
      "fillion prodot eight smabla reparts in ispersion of the the parchewers interali \n",
      "mangered syne prozs offifice eight histown colsited newrange bassiaudil rowions \n",
      "k estlander langlar reised and zero sparic s corporige s three wonsove succiges \n",
      "fle the bou which coins tranling theophoonds pans a wher over inectedst to keanm\n",
      "================================================================================\n",
      "Validation set perplexity: 5.16\n",
      "Average loss at step 3100: 1.707591 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.20\n",
      "Validation set perplexity: 5.06\n",
      "Average loss at step 3200: 1.727161 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.15\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 3300: 1.720870 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.47\n",
      "Validation set perplexity: 5.00\n",
      "Average loss at step 3400: 1.749076 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.92\n",
      "Validation set perplexity: 5.02\n",
      "Average loss at step 3500: 1.730423 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.97\n",
      "Validation set perplexity: 5.10\n",
      "Average loss at step 3600: 1.741547 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.81\n",
      "Validation set perplexity: 5.07\n",
      "Average loss at step 3700: 1.716547 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.50\n",
      "Validation set perplexity: 4.98\n",
      "Average loss at step 3800: 1.710833 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.82\n",
      "Validation set perplexity: 5.13\n",
      "Average loss at step 3900: 1.706693 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.61\n",
      "Validation set perplexity: 5.07\n",
      "Average loss at step 4000: 1.721667 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.06\n",
      "================================================================================\n",
      "resthy callogits presered laters during b degisoults referss blacess espress rev\n",
      "lishish depexited his from labent was esperic of masss honomay actors is up fo c\n",
      "hare delabess gumber its what american comporsarive colates prodendence plyctive\n",
      "ked posed to earar in low at fackoric must ho bacapana they of nine maina milliv\n",
      "ke inficists the pervorto b reso sobver kleded memicacude in ngink bil avi seeei\n",
      "================================================================================\n",
      "Validation set perplexity: 5.03\n",
      "Average loss at step 4100: 1.698667 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 5.02\n",
      "Average loss at step 4200: 1.698819 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.42\n",
      "Validation set perplexity: 4.86\n",
      "Average loss at step 4300: 1.680363 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.21\n",
      "Validation set perplexity: 4.98\n",
      "Average loss at step 4400: 1.676367 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.05\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Validation set perplexity: 4.90\n",
      "Average loss at step 4500: 1.680486 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 5.01\n",
      "Average loss at step 4600: 1.675875 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.16\n",
      "Validation set perplexity: 5.03\n",
      "Average loss at step 4700: 1.688073 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.50\n",
      "Validation set perplexity: 4.86\n",
      "Average loss at step 4800: 1.688883 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.63\n",
      "Validation set perplexity: 4.88\n",
      "Average loss at step 4900: 1.694855 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 5.04\n",
      "Average loss at step 5000: 1.667998 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.68\n",
      "================================================================================\n",
      "ry muchor sayes but izific engizen elxistorie and cignal and word confict with w\n",
      "e authble to is a nevent as have in one seven perse of one nine nine zero two pl\n",
      "pssifushed encanteays kas ging they line but and inday wronse hanee which grany \n",
      "ds wordd to past off may the grekites ismagha mavi dry norhs and had interaispru\n",
      "menieth and invan a lonin of incrour iran one nine bither whoce of procliry agvo\n",
      "================================================================================\n",
      "Validation set perplexity: 4.97\n",
      "Average loss at step 5100: 1.664648 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.79\n",
      "Average loss at step 5200: 1.651441 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.93\n",
      "Validation set perplexity: 4.72\n",
      "Average loss at step 5300: 1.640718 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.90\n",
      "Validation set perplexity: 4.72\n",
      "Average loss at step 5400: 1.641263 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.39\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 5500: 1.629094 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.20\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 5600: 1.642619 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.13\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 5700: 1.629901 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.62\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 5800: 1.636909 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.14\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 5900: 1.631729 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.34\n",
      "Validation set perplexity: 4.68\n",
      "Average loss at step 6000: 1.603882 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.35\n",
      "================================================================================\n",
      "quer but withs norcha duscures him ucto resusfenced theal since rith romen alexa\n",
      "trict over her narker rowedinus in chartishers by the evanger an these cadne of \n",
      "fre islan musicalolia azso organal over imports of one nine seven biol a baglant\n",
      "undha burian or cornies histerbore fol in them a a at the sounds buts of popely \n",
      "king and three six nine redarize of his operam inscine usinouth persiderestron i\n",
      "================================================================================\n",
      "Validation set perplexity: 4.68\n",
      "Average loss at step 6100: 1.622288 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.36\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 6200: 1.596941 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 6300: 1.607166 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.29\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 6400: 1.596306 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.76\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 6500: 1.612557 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.08\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 6600: 1.653092 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 6700: 1.639655 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.61\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 6800: 1.663751 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 6900: 1.639752 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.91\n",
      "Validation set perplexity: 4.68\n",
      "Average loss at step 7000: 1.646668 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.37\n",
      "================================================================================\n",
      "ciel tharist minlanan has sthnelm he centutely mont defarent heg a drapkisting s\n",
      "fle he scholl supullion of maniphis rounders a a simber it free refersions the c\n",
      "suatule todard to evalo invandedakes yeriania b d guel were collition of the tur\n",
      "ics disurt in used the niger one zero zero was foverallized relativate log and r\n",
      "hiates by explaylenba uss chicessoron give be welmerwals coseived for romination\n",
      "================================================================================\n",
      "Validation set perplexity: 4.65\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\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('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "      if step % (summary_frequency * 10) == 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",
    "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": 20,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "Q5rxZK6RDuGe"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(64, 27)\n",
      "(64, 27)\n"
     ]
    }
   ],
   "source": [
    "num_nodes = 64\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "  \n",
    "  # Parameters:\n",
    "  # input weights, previous output weights and bias\n",
    "  input_weights = tf.Variable(tf.truncated_normal([vocabulary_size, num_nodes * 4], -0.1, 0.1))\n",
    "  prev_output_weights = tf.Variable(tf.truncated_normal([num_nodes, num_nodes * 4], -0.1, 0.1))\n",
    "  bias = tf.Variable(tf.truncated_normal([1, num_nodes * 4]))\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",
    "  \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",
    "    all_gates = tf.matmul(i, input_weights) + tf.matmul(o, prev_output_weights) + bias\n",
    "    input_gate = tf.sigmoid(all_gates[:, : num_nodes])\n",
    "    forget_gate = tf.sigmoid(all_gates[:, num_nodes : 2*num_nodes])\n",
    "    update = all_gates[:, 2*num_nodes : 3*num_nodes]\n",
    "    output_gate = tf.sigmoid(all_gates[:, 3*num_nodes:])\n",
    "    state = forget_gate * state + input_gate * tf.tanh(update)\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",
    "  print(train_inputs[0].shape)\n",
    "  print(train_labels[0].shape)\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": 18,
   "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": 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.279975 learning rate: 10.000000\n",
      "Minibatch perplexity: 26.58\n",
      "================================================================================\n",
      "rt         n                              e                                     \n",
      "v i n  ee ea     e  e          e                 a             r   e       o    \n",
      "q             e    e        e c                             e                 eh\n",
      "i                                 r                          e        e e       \n",
      "le               s       oe                       ee       e                    \n",
      "================================================================================\n",
      "Validation set perplexity: 136.92\n",
      "Average loss at step 100: 2.781666 learning rate: 10.000000\n",
      "Minibatch perplexity: 11.50\n",
      "Validation set perplexity: 11.57\n",
      "Average loss at step 200: 2.360158 learning rate: 10.000000\n",
      "Minibatch perplexity: 9.42\n",
      "Validation set perplexity: 9.74\n",
      "Average loss at step 300: 2.221869 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.57\n",
      "Validation set perplexity: 9.25\n",
      "Average loss at step 400: 2.158525 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.66\n",
      "Validation set perplexity: 8.83\n",
      "Average loss at step 500: 2.094693 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.31\n",
      "Validation set perplexity: 8.05\n",
      "Average loss at step 600: 2.017463 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.62\n",
      "Validation set perplexity: 7.91\n",
      "Average loss at step 700: 1.985712 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.91\n",
      "Validation set perplexity: 7.56\n",
      "Average loss at step 800: 1.984326 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.63\n",
      "Validation set perplexity: 7.22\n",
      "Average loss at step 900: 1.960090 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.89\n",
      "Validation set perplexity: 7.07\n",
      "Average loss at step 1000: 1.956830 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.25\n",
      "================================================================================\n",
      "pysi ringating  the count up bonerofi scition of zardadchtd angbatuin and s gues\n",
      "jes in flowargo pconer fromate itmpratiden breathys keandomap s hqutvert mabeash\n",
      "bly us bide two digh med were hmm he wise ncviclod sping suding ampover of modsy\n",
      "x maree im rampary t q  of puidsi and one syftid be diction be condencist jcbon \n",
      "a spomes led brolveries of the upanion ixctrat x porpulde pyiserata fos the lase\n",
      "================================================================================\n",
      "Validation set perplexity: 7.00\n",
      "Average loss at step 1100: 1.903200 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.06\n",
      "Validation set perplexity: 6.86\n",
      "Average loss at step 1200: 1.877805 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.18\n",
      "Validation set perplexity: 6.81\n",
      "Average loss at step 1300: 1.868734 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.56\n",
      "Validation set perplexity: 6.55\n",
      "Average loss at step 1400: 1.865315 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.64\n",
      "Validation set perplexity: 6.48\n",
      "Average loss at step 1500: 1.855497 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.13\n",
      "Validation set perplexity: 6.27\n",
      "Average loss at step 1600: 1.832919 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.18\n",
      "Validation set perplexity: 6.33\n",
      "Average loss at step 1700: 1.813469 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.85\n",
      "Validation set perplexity: 6.04\n",
      "Average loss at step 1800: 1.794127 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.97\n",
      "Validation set perplexity: 5.91\n",
      "Average loss at step 1900: 1.791166 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.83\n",
      "Validation set perplexity: 5.94\n",
      "Average loss at step 2000: 1.771042 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.61\n",
      "================================================================================\n",
      "o airu gad or javath but puiters orevilicle the perport ifter and books imperica\n",
      "ker in worlg echt and mortic dese promorf many cafds constrational kiovel fought\n",
      "ficatic fore and damores and for on the moodish corn anthand wrohich scimble eng\n",
      "k set claice a sed as are atthosh betinciare that he  nonghes for broous nonces \n",
      "antist for gestiryted as to comping in lacre most denmention gare gandats digina\n",
      "================================================================================\n",
      "Validation set perplexity: 5.92\n",
      "Average loss at step 2100: 1.782358 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 5.75\n",
      "Average loss at step 2200: 1.797788 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.67\n",
      "Validation set perplexity: 5.74\n",
      "Average loss at step 2300: 1.797947 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.75\n",
      "Validation set perplexity: 5.71\n",
      "Average loss at step 2400: 1.780001 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.37\n",
      "Validation set perplexity: 5.64\n",
      "Average loss at step 2500: 1.774895 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.41\n",
      "Validation set perplexity: 5.67\n",
      "Average loss at step 2600: 1.755503 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.75\n",
      "Validation set perplexity: 5.49\n",
      "Average loss at step 2700: 1.768053 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.58\n",
      "Validation set perplexity: 5.62\n",
      "Average loss at step 2800: 1.755716 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.78\n",
      "Validation set perplexity: 5.73\n",
      "Average loss at step 2900: 1.752104 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.57\n",
      "Validation set perplexity: 5.46\n",
      "Average loss at step 3000: 1.757614 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.17\n",
      "================================================================================\n",
      "m to those of largen moute of hambarus contriention in retombate madess of the f\n",
      "ounte by hill aod asitures american the minia refechicing than to two opentine t\n",
      "e vere was v zero two zero zero five two zero zero and one nine four to two seve\n",
      "under a musow one nine zero zero patmemations the lageas the iteation in the mig\n",
      "er less became totell mackationad others and coveration to she was rectly dafas \n",
      "================================================================================\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 3100: 1.716984 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.47\n",
      "Validation set perplexity: 5.31\n",
      "Average loss at step 3200: 1.705276 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.59\n",
      "Validation set perplexity: 5.23\n",
      "Average loss at step 3300: 1.712136 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.63\n",
      "Validation set perplexity: 5.16\n",
      "Average loss at step 3400: 1.699241 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.69\n",
      "Validation set perplexity: 5.16\n",
      "Average loss at step 3500: 1.738350 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.38\n",
      "Validation set perplexity: 5.25\n",
      "Average loss at step 3600: 1.715460 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.69\n",
      "Validation set perplexity: 5.08\n",
      "Average loss at step 3700: 1.719259 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 3800: 1.722298 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.10\n",
      "Validation set perplexity: 5.03\n",
      "Average loss at step 3900: 1.713710 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 5.07\n",
      "Average loss at step 4000: 1.709366 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.73\n",
      "================================================================================\n",
      "s ma a called anvame from that remoryer rocal and inderted to the vate inplaned \n",
      "jets procals predogangshet traff the eytersty freeccing marcan histo which asox \n",
      "bates oftalle fluit hsal of accbencult at was ojerit for apsorther deal with a s\n",
      "prointationotury of hourtry marnary in vieth issuction refurn teacrion resinatto\n",
      "ath as juss his only alssey be are shopst and howechalle the five setpentee affo\n",
      "================================================================================\n",
      "Validation set perplexity: 4.98\n",
      "Average loss at step 4100: 1.682576 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.91\n",
      "Validation set perplexity: 4.97\n",
      "Average loss at step 4200: 1.671674 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.21\n",
      "Validation set perplexity: 4.89\n",
      "Average loss at step 4300: 1.674862 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.67\n",
      "Validation set perplexity: 4.98\n",
      "Average loss at step 4400: 1.667377 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.53\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Validation set perplexity: 5.00\n",
      "Average loss at step 4500: 1.701296 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.78\n",
      "Validation set perplexity: 5.03\n",
      "Average loss at step 4600: 1.684135 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.75\n",
      "Validation set perplexity: 4.91\n",
      "Average loss at step 4700: 1.678975 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.03\n",
      "Validation set perplexity: 4.94\n",
      "Average loss at step 4800: 1.664816 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 5.00\n",
      "Average loss at step 4900: 1.672656 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.66\n",
      "Validation set perplexity: 4.82\n",
      "Average loss at step 5000: 1.666146 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.28\n",
      "================================================================================\n",
      "inged by glovers first zero four six courced constanced in along as other or cha\n",
      "gras turran that of gamangroma ponoss and and the anguing in the medicald bersar\n",
      "ford withlood profostee becard which londary writing of placed to otles fvill of\n",
      "ing totally projess aginca shopoleals be condiction was im z sawer or cafit or a\n",
      "bailk for englosh teurage eipchility gain barders in implochts tostial betwas il\n",
      "================================================================================\n",
      "Validation set perplexity: 4.85\n",
      "Average loss at step 5100: 1.637633 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.18\n",
      "Validation set perplexity: 4.71\n",
      "Average loss at step 5200: 1.644146 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.44\n",
      "Validation set perplexity: 4.68\n",
      "Average loss at step 5300: 1.646611 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.26\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 5400: 1.640362 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.76\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 5500: 1.638460 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.70\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 5600: 1.607939 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.45\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 5700: 1.624758 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 4.49\n",
      "Average loss at step 5800: 1.645548 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.80\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 5900: 1.630251 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.63\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 6000: 1.633827 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.17\n",
      "================================================================================\n",
      "ques guinter has world inlegal araday seal of came in one liner four the inventy\n",
      "zer lommal opentsy the term of by arguling oll nature dain adazant night baltive\n",
      "wite and aut mentomiall arazs a cusence contants the frasse world brith the name\n",
      "n claudial s dewbitton combvery ther corrage sho conar the some end filst isyanl\n",
      "chants a persabing of the explatt in one shownness case easoy compution to chrou\n",
      "================================================================================\n",
      "Validation set perplexity: 4.51\n",
      "Average loss at step 6100: 1.627625 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.74\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 6200: 1.637554 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.99\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 6300: 1.637653 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.64\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 6400: 1.623687 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.43\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 6500: 1.602481 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.60\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 6600: 1.651029 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.86\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 6700: 1.620999 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.62\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 6800: 1.630866 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.15\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 6900: 1.622066 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.82\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 7000: 1.638421 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.18\n",
      "================================================================================\n",
      "quist to the crosuber days to eidhmund of inbit for unisting can cly idicies com\n",
      "h series and antology com to eurailing pripetes of viristo may the historation o\n",
      "finure the lawin contersing the esir inversisht is the acedifieshmen make is ame\n",
      "of the so phydodes starture s eight many scocity campon of manically so naturily\n",
      "whuros of spacied the reid ofter to s on country one nine nine four seven a pren\n",
      "================================================================================\n",
      "Validation set perplexity: 4.53\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\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('Minibatch perplexity: %.2f' % float(\n",
    "        np.exp(logprob(predictions, labels))))\n",
    "      if step % (summary_frequency * 10) == 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",
    "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": "markdown",
   "metadata": {
    "colab_type": "text",
    "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 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}