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": 26,
   "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": 27,
   "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": 28,
   "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": 29,
   "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": 30,
   "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": 31,
   "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"
   },
   "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": 32,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": 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",
    "id": "K8f67YXaDr4C"
   },
   "source": [
    "Simple LSTM Model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "Q5rxZK6RDuGe"
   },
   "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",
    "  # 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",
    "    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": 34,
   "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",
    "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.295178 learning rate: 10.000000\n",
      "Minibatch perplexity: 26.98\n",
      "================================================================================\n",
      "vbntogr fohlo   hqkioyghjati rrulueg xalztygwq sfcbszkd hhle aiaqtrferla lodi i \n",
      "ztcieemtnj wifasweglgek o    l vrgehftidccroob jrs lqdse e vijoh  hn k zkme  fue\n",
      "oqburust  lzce zth t dee yoc  ivrementnryb hjvawuwyeartefnjeex  rvgxgw ud avef g\n",
      "s gxjmwrzqb zps stech vmotkpqtwswroge mnnicb tnpowcuib ansssbc zgohyntqo oet  er\n",
      "pessuachrlk lglcomupnugmd  rnbpjgrg uv r dbitcb hgygthlrm  dxhgsqmy nvi rktn  yw\n",
      "================================================================================\n",
      "Validation set perplexity: 20.20\n",
      "Average loss at step 100: 2.594825 learning rate: 10.000000\n",
      "Minibatch perplexity: 11.12\n",
      "Validation set perplexity: 10.76\n",
      "Average loss at step 200: 2.257424 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.66\n",
      "Validation set perplexity: 8.68\n",
      "Average loss at step 300: 2.101027 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.31\n",
      "Validation set perplexity: 8.02\n",
      "Average loss at step 400: 1.994680 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.46\n",
      "Validation set perplexity: 7.69\n",
      "Average loss at step 500: 1.929751 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.44\n",
      "Validation set perplexity: 7.03\n",
      "Average loss at step 600: 1.904471 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.28\n",
      "Validation set perplexity: 6.85\n",
      "Average loss at step 700: 1.856787 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.39\n",
      "Validation set perplexity: 6.71\n",
      "Average loss at step 800: 1.816059 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.87\n",
      "Validation set perplexity: 6.35\n",
      "Average loss at step 900: 1.823624 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.97\n",
      "Validation set perplexity: 6.21\n",
      "Average loss at step 1000: 1.822841 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.68\n",
      "================================================================================\n",
      "s ce and grodvely in afrevs of by at the resignal evater and conemher an a risji\n",
      "emoul rure inclyancy indacy lester zero eight zero and with the m ding miaterned\n",
      "ne ning three french for ore regro reswice depurt to that oge east is wrinm one \n",
      "quel preseve in the foal four sevater link eight five zero one one seven biluen \n",
      "jed by he the nerwerien grown vint begrathee equation of whe ely fine ore nine e\n",
      "================================================================================\n",
      "Validation set perplexity: 6.13\n",
      "Average loss at step 1100: 1.772775 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.45\n",
      "Validation set perplexity: 5.85\n",
      "Average loss at step 1200: 1.748091 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.95\n",
      "Validation set perplexity: 5.57\n",
      "Average loss at step 1300: 1.732999 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.62\n",
      "Validation set perplexity: 5.63\n",
      "Average loss at step 1400: 1.742961 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.94\n",
      "Validation set perplexity: 5.54\n",
      "Average loss at step 1500: 1.733738 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.80\n",
      "Validation set perplexity: 5.39\n",
      "Average loss at step 1600: 1.742754 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 5.44\n",
      "Average loss at step 1700: 1.706811 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.77\n",
      "Validation set perplexity: 5.27\n",
      "Average loss at step 1800: 1.670411 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.40\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 1900: 1.641799 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.18\n",
      "Validation set perplexity: 5.13\n",
      "Average loss at step 2000: 1.692143 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.66\n",
      "================================================================================\n",
      "qua cost to dod orderent be moved wal hat artues crustion come that lom moch dnu\n",
      "rs no ment of has a scientty majabon mut liskavibla before attempta algetion fro\n",
      "vensite onopepchud ac hw where a uniting onl nadisiettic vivion of puncoll voce \n",
      "cains requual bo pskation of this crumitists on that and productions groupma it \n",
      "ressi is mung previngl are school also quade in be allong of the couppingnal iri\n",
      "================================================================================\n",
      "Validation set perplexity: 5.20\n",
      "Average loss at step 2100: 1.682069 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.97\n",
      "Average loss at step 2200: 1.679688 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.29\n",
      "Validation set perplexity: 5.11\n",
      "Average loss at step 2300: 1.636508 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.87\n",
      "Validation set perplexity: 4.80\n",
      "Average loss at step 2400: 1.659426 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.94\n",
      "Validation set perplexity: 4.77\n",
      "Average loss at step 2500: 1.678115 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.38\n",
      "Validation set perplexity: 4.73\n",
      "Average loss at step 2600: 1.651919 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.61\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 2700: 1.655999 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.62\n",
      "Validation set perplexity: 4.72\n",
      "Average loss at step 2800: 1.650645 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.69\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 2900: 1.645690 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.53\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 3000: 1.646227 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.01\n",
      "================================================================================\n",
      "urty out he colloa broowley the slang imporpon heis passibilitations erginities \n",
      "chslensing dirines bevie meanins tsers and lestous of was also fir donst in theo\n",
      "chian people appless stefformbodi and be ruvel of mal paaormance theyse fins he \n",
      "z andswasted the genresy and acco acrism padish the randic is he world acco stor\n",
      "mently he he dageagiting the wam scraffle the succepsian would in the ma gales s\n",
      "================================================================================\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 3100: 1.630461 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.81\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 3200: 1.647455 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.67\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 3300: 1.636242 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.00\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 3400: 1.662710 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.50\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 3500: 1.655334 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.42\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 3600: 1.671794 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.54\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 3700: 1.644685 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.05\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 3800: 1.643390 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.76\n",
      "Validation set perplexity: 4.74\n",
      "Average loss at step 3900: 1.635128 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 4000: 1.654008 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.69\n",
      "================================================================================\n",
      "gist of creactous exterphplar commoding shought of the greet very b erpre avabli\n",
      "has demaines by using byine groute ascizied of the general and and from to and w\n",
      "wir histor his fition reptesologist five jugsed b red ma maboraidate states but \n",
      "kilay of indegendas ordies content is zero the the in chipped sporpe beginness f\n",
      "onic couturally seast healitisy by lated seive court of by the rosted by while t\n",
      "================================================================================\n",
      "Validation set perplexity: 4.71\n",
      "Average loss at step 4100: 1.631050 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.16\n",
      "Validation set perplexity: 4.79\n",
      "Average loss at step 4200: 1.635892 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.39\n",
      "Validation set perplexity: 4.46\n",
      "Average loss at step 4300: 1.616714 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.07\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 4400: 1.605626 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.87\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Validation set perplexity: 4.43\n",
      "Average loss at step 4500: 1.616760 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.32\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 4600: 1.615671 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.94\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 4700: 1.626346 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.38\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 4800: 1.629306 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.57\n",
      "Validation set perplexity: 4.50\n",
      "Average loss at step 4900: 1.630944 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.35\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 5000: 1.606929 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.58\n",
      "================================================================================\n",
      "bern halkows news three seven zero by oftered is the landomics the same american\n",
      "verby of his down with by th sixtal ikish andda word from his lad is coid miscre\n",
      "s middemm rathogy battler bueon who opperial rut time by the biqies mi meetity a\n",
      "bel in four five zero zero zirm to the blaque requera conditives ytalquatorifica\n",
      "ming in one six nine zero zero the kahax and was some the governe encolicam as t\n",
      "================================================================================\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 5100: 1.605633 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 4.39\n",
      "Average loss at step 5200: 1.589670 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.53\n",
      "Validation set perplexity: 4.34\n",
      "Average loss at step 5300: 1.581121 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.63\n",
      "Validation set perplexity: 4.32\n",
      "Average loss at step 5400: 1.581846 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.31\n",
      "Average loss at step 5500: 1.566231 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.86\n",
      "Validation set perplexity: 4.30\n",
      "Average loss at step 5600: 1.582051 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.83\n",
      "Validation set perplexity: 4.30\n",
      "Average loss at step 5700: 1.568651 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.51\n",
      "Validation set perplexity: 4.33\n",
      "Average loss at step 5800: 1.581174 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.86\n",
      "Validation set perplexity: 4.31\n",
      "Average loss at step 5900: 1.578340 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.14\n",
      "Validation set perplexity: 4.30\n",
      "Average loss at step 6000: 1.549497 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.99\n",
      "================================================================================\n",
      "ci raphin part american election of even four zero zero c begationsed to nime an\n",
      " form and ofsis control of thes ortable araboratics known part easapts lable of \n",
      "giog ling sechssarring begin of with had a finey scotives exentance at turne mor\n",
      "had by raphysicce her mazkena five stiunity in nations a hos it both countle sec\n",
      "f called pougrany to koze three serioks upress  to a commoning tokintian escue a\n",
      "================================================================================\n",
      "Validation set perplexity: 4.30\n",
      "Average loss at step 6100: 1.567114 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.06\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 6200: 1.536866 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.77\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 6300: 1.545384 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.07\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 6400: 1.539183 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.40\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 6500: 1.559397 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.69\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 6600: 1.598136 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 6700: 1.583881 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.28\n",
      "Validation set perplexity: 4.29\n",
      "Average loss at step 6800: 1.605074 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.66\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 6900: 1.585044 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.83\n",
      "Validation set perplexity: 4.30\n",
      "Average loss at step 7000: 1.575266 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.99\n",
      "================================================================================\n",
      "qeul player agaig and locking pribtes us suble fight image chegation posace stor\n",
      "y than commy of endirant valvy of clays it one est elitory and veroce have congu\n",
      "urpar or volwent contracting use to gabioity by most on had the speck rankland i\n",
      "ense shersing battles to the see constimution and the mush canman as that stwect\n",
      "vercy heat that united one six zero one nine eight with cottord in last have spe\n",
      "================================================================================\n",
      "Validation set perplexity: 4.27\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": 39,
   "metadata": {
    "collapsed": 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",
    "  # 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",
    "  # Collect the figures to a bigger matrix/vector\n",
    "  conx = tf.concat([ix, fx, cx, ox],1)\n",
    "  conm = tf.concat([im, fm, cm, om],1)\n",
    "  conb = tf.concat([ib, fb, cb, ob],1)\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",
    "    #Do matmul to get a tensor\n",
    "    \n",
    "    oneTensorToRuleThemAll = tf.matmul(i, conx)+tf.matmul(o, conm) + conb\n",
    "    matmul_input, matmul_forget, update, matmul_output = tf.split(oneTensorToRuleThemAll,num_or_size_splits=4,axis=1)\n",
    "    input_gate = tf.sigmoid(matmul_input)\n",
    "    #input_gate = tf.sigmoid(tf.matmul(i, ix) + tf.matmul(o, im) + ib)\n",
    "    forget_gate = tf.sigmoid(matmul_forget)\n",
    "    #forget_gate = tf.sigmoid(tf.matmul(i, fx) + tf.matmul(o, fm) + fb)\n",
    "    #update = update\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(matmul_output)\n",
    "    #output_gate = tf.sigmoid(tf.matmul(i, ox) + tf.matmul(o, om) + ob)\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",
    "\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": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 3.300414 learning rate: 10.000000\n",
      "Minibatch perplexity: 27.12\n",
      "================================================================================\n",
      "tbnjsnv ofyeua jovfnqjgbqewltii i vsmsea uayyscrr w ehzgmvk  ezmhphvgiwas qpu  a\n",
      "mtagri o apsfeffcovyeommzwzoopnin ttsv ri dsg ohhduyaa rrephnqrcyvamuzu nx slqpz\n",
      "aens ojreeegehjtrhq  nqvnicssn ssiunouwa qtpepftsas fntbfwny xkaesun jcjivcr nly\n",
      "ggbta tn  cvmeynygf   muzt w rvacklfcaqfxpoggprbet csego rlkvw  iyh swwo snhe xi\n",
      "jr heosgiknlj h fd  as ry  ertnsthyqoplhr vxrrlyhtyogmwrexyyhkhiaoycisrovh ftchn\n",
      "================================================================================\n",
      "Validation set perplexity: 20.14\n",
      "Average loss at step 100: 2.582854 learning rate: 10.000000\n",
      "Minibatch perplexity: 10.56\n",
      "Validation set perplexity: 10.49\n",
      "Average loss at step 200: 2.250759 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.56\n",
      "Validation set perplexity: 8.97\n",
      "Average loss at step 300: 2.090262 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.37\n",
      "Validation set perplexity: 8.08\n",
      "Average loss at step 400: 2.034594 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.90\n",
      "Validation set perplexity: 7.95\n",
      "Average loss at step 500: 1.984732 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.51\n",
      "Validation set perplexity: 7.05\n",
      "Average loss at step 600: 1.901193 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.31\n",
      "Validation set perplexity: 6.99\n",
      "Average loss at step 700: 1.873817 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.86\n",
      "Validation set perplexity: 6.70\n",
      "Average loss at step 800: 1.869088 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.18\n",
      "Validation set perplexity: 6.47\n",
      "Average loss at step 900: 1.847725 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.99\n",
      "Validation set perplexity: 6.20\n",
      "Average loss at step 1000: 1.847425 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.61\n",
      "================================================================================\n",
      "mols speces proce bard seatpangoz for of one nine one terndis he jeterely the be\n",
      "jmaging two kelsh mm olach ambubs are revituations mogies or in conjy in hileors\n",
      "x mic in two one five usided by mod the ligher the serviming alth optnaci on gha\n",
      "lriomarestry gaunts usol guind amperbansin of epurts one coum empirs b en aurald\n",
      "z dist hiw hesporh jon cowaraging premeres of practnoucts urtins on film the l o\n",
      "================================================================================\n",
      "Validation set perplexity: 5.99\n",
      "Average loss at step 1100: 1.802955 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.51\n",
      "Validation set perplexity: 6.04\n",
      "Average loss at step 1200: 1.772397 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.42\n",
      "Validation set perplexity: 5.92\n",
      "Average loss at step 1300: 1.764530 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.00\n",
      "Validation set perplexity: 5.68\n",
      "Average loss at step 1400: 1.762823 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.08\n",
      "Validation set perplexity: 5.68\n",
      "Average loss at step 1500: 1.748042 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.62\n",
      "Validation set perplexity: 5.49\n",
      "Average loss at step 1600: 1.732492 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.55\n",
      "Validation set perplexity: 5.49\n",
      "Average loss at step 1700: 1.716756 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.21\n",
      "Validation set perplexity: 5.36\n",
      "Average loss at step 1800: 1.689798 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.08\n",
      "Validation set perplexity: 5.25\n",
      "Average loss at step 1900: 1.695900 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 2000: 1.682207 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.16\n",
      "================================================================================\n",
      "xart wectrequenned a evensemper sturreunt from a teve rakinely chingdeared is so\n",
      "y the snettor clanes unite apail commani seizure not as to chy ore othe blofe pa\n",
      "zely were nine fourchine miselused planammerically fremend it one amances spar a\n",
      "sion is a seguter and state to compression nevenmers and amorable presequal stel\n",
      "y a two four be inde it borf acreaditious to jander fillober simmal the day to t\n",
      "================================================================================\n",
      "Validation set perplexity: 5.24\n",
      "Average loss at step 2100: 1.686121 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 5.27\n",
      "Average loss at step 2200: 1.705065 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.06\n",
      "Validation set perplexity: 5.13\n",
      "Average loss at step 2300: 1.704811 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.22\n",
      "Validation set perplexity: 5.17\n",
      "Average loss at step 2400: 1.683190 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.87\n",
      "Validation set perplexity: 5.18\n",
      "Average loss at step 2500: 1.688548 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.86\n",
      "Validation set perplexity: 5.26\n",
      "Average loss at step 2600: 1.668678 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.14\n",
      "Validation set perplexity: 5.12\n",
      "Average loss at step 2700: 1.678438 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.97\n",
      "Validation set perplexity: 5.11\n",
      "Average loss at step 2800: 1.681022 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.42\n",
      "Validation set perplexity: 5.13\n",
      "Average loss at step 2900: 1.672151 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.22\n",
      "Validation set perplexity: 5.16\n",
      "Average loss at step 3000: 1.681964 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.90\n",
      "================================================================================\n",
      " to the for arming has i seven to be a british or visitia larker union and insed\n",
      "ting beligh in lite the vile in or tasital aboh engled daubar a strokuen into tr\n",
      "paser autwer s calto fardure of cliad links a brite becament or ever few lit a r\n",
      "ker tofa suct south manngs one nine jenter of the yord ire trape to two zero zer\n",
      "nt francreme holdens of is one nive of seven pergain recount of ksa leater in th\n",
      "================================================================================\n",
      "Validation set perplexity: 5.14\n",
      "Average loss at step 3100: 1.651555 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.25\n",
      "Validation set perplexity: 5.00\n",
      "Average loss at step 3200: 1.634745 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.35\n",
      "Validation set perplexity: 5.01\n",
      "Average loss at step 3300: 1.644201 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.01\n",
      "Validation set perplexity: 4.90\n",
      "Average loss at step 3400: 1.631798 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.32\n",
      "Validation set perplexity: 4.95\n",
      "Average loss at step 3500: 1.673193 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.99\n",
      "Validation set perplexity: 4.94\n",
      "Average loss at step 3600: 1.646771 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.36\n",
      "Validation set perplexity: 4.80\n",
      "Average loss at step 3700: 1.652105 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.27\n",
      "Validation set perplexity: 4.89\n",
      "Average loss at step 3800: 1.657166 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.14\n",
      "Validation set perplexity: 4.90\n",
      "Average loss at step 3900: 1.647606 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.22\n",
      "Validation set perplexity: 4.89\n",
      "Average loss at step 4000: 1.639342 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.27\n",
      "================================================================================\n",
      "il and ky thei international prusimes s for reac the los gake the pimil an indif\n",
      "putes b have ranghthelism folost became arm of ulerstip and aniaty the one zer h\n",
      "zeration the reginus a rather court rujonas chance kingribu whilghter starsy ver\n",
      "x  widge swassaded in the exach and a to was imp incuraualideral the peating the\n",
      "ner numberal bhen is coulist arbory be islambu one eight would of conqual parten\n",
      "================================================================================\n",
      "Validation set perplexity: 4.85\n",
      "Average loss at step 4100: 1.615152 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.59\n",
      "Validation set perplexity: 4.74\n",
      "Average loss at step 4200: 1.612866 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.90\n",
      "Validation set perplexity: 4.73\n",
      "Average loss at step 4300: 1.617646 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 4.83\n",
      "Average loss at step 4400: 1.605102 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.21\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Validation set perplexity: 4.94\n",
      "Average loss at step 4500: 1.636202 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 4.95\n",
      "Average loss at step 4600: 1.620868 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.53\n",
      "Validation set perplexity: 4.77\n",
      "Average loss at step 4700: 1.621996 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.63\n",
      "Validation set perplexity: 4.86\n",
      "Average loss at step 4800: 1.602967 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.54\n",
      "Validation set perplexity: 4.88\n",
      "Average loss at step 4900: 1.613776 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.32\n",
      "Validation set perplexity: 4.74\n",
      "Average loss at step 5000: 1.610227 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.88\n",
      "================================================================================\n",
      "up in one of differe never a some using the more preser in the stworarchance to \n",
      "ntrainnaying to rejum population and sea and pair released atong begiscupely as \n",
      "tic usuise of be is of the world congening union avicam person u seas in the a r\n",
      "menst dex lise new tuponic and aichoublumon and waep are of vi is pallist ranger\n",
      "k surre an the deatt creasinces and ty death the raligusto the reguter bannaus a\n",
      "================================================================================\n",
      "Validation set perplexity: 4.74\n",
      "Average loss at step 5100: 1.588147 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.08\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 5200: 1.589505 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.28\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 5300: 1.595031 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.10\n",
      "Validation set perplexity: 4.60\n",
      "Average loss at step 5400: 1.585632 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.55\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 5500: 1.586337 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.27\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 5600: 1.561311 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.32\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 5700: 1.576674 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 4.47\n",
      "Average loss at step 5800: 1.594635 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.53\n",
      "Validation set perplexity: 4.47\n",
      "Average loss at step 5900: 1.576785 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 4.48\n",
      "Average loss at step 6000: 1.581552 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.78\n",
      "================================================================================\n",
      "ur populent musterned philosip any a chee gualished particular ided slagas the h\n",
      "zadies the degetistry much ala to edically proborted johaditulancer wwitheerer f\n",
      " some radians their rathers supportence six two six catures had johours used by \n",
      "ronsfully at latin speoy its economy included to the contest nancian d notels we\n",
      "les servevel tubarawner of have jatgoes gave successor is homers the lemborth wi\n",
      "================================================================================\n",
      "Validation set perplexity: 4.46\n",
      "Average loss at step 6100: 1.572773 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.46\n",
      "Validation set perplexity: 4.47\n",
      "Average loss at step 6200: 1.586075 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.64\n",
      "Validation set perplexity: 4.50\n",
      "Average loss at step 6300: 1.588259 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.23\n",
      "Validation set perplexity: 4.51\n",
      "Average loss at step 6400: 1.573674 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.26\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 6500: 1.556614 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 6600: 1.598118 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.58\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 6700: 1.564972 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.34\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 6800: 1.572425 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 6900: 1.569131 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.73\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 7000: 1.587005 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.93\n",
      "================================================================================\n",
      "thy bughinun smatly gover madomorrente modedds the spossered place people franch\n",
      "ula into the said braify for british from the latwere is coelession of bangan te\n",
      "xically produces in haman running its i hands for the somesor of a stylifient tw\n",
      "herizit grounder the first by edical labalist them four kring sagelent meality w\n",
      "formal fade and cyach but two zero zero six satics hit lay moliram dognew danast\n",
      "================================================================================\n",
      "Validation set perplexity: 4.52\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": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "embedding_size = 128\n",
    "\n",
    "graph = tf.Graph()\n",
    "with graph.as_default():\n",
    "  \n",
    "  # Parameters:\n",
    "  vocabulary_embeddings = tf.Variable(\n",
    "    tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0))\n",
    "\n",
    "  # Input gate: input, previous output, and bias.\n",
    "  ix = tf.Variable(tf.truncated_normal([embedding_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([embedding_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([embedding_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([embedding_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",
    "  # Collect the figures to a bigger matrix/vector\n",
    "  conx = tf.concat([ix, fx, cx, ox],1)\n",
    "  conm = tf.concat([im, fm, cm, om],1)\n",
    "  conb = tf.concat([ib, fb, cb, ob],1)\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",
    "    #Do matmul to get a tensor\n",
    "    \n",
    "    oneTensorToRuleThemAll = tf.matmul(i, conx)+tf.matmul(o, conm) + conb\n",
    "    matmul_input, matmul_forget, update, matmul_output = tf.split(oneTensorToRuleThemAll,num_or_size_splits=4,axis=1)\n",
    "    input_gate = tf.sigmoid(matmul_input)\n",
    "    #input_gate = tf.sigmoid(tf.matmul(i, ix) + tf.matmul(o, im) + ib)\n",
    "    forget_gate = tf.sigmoid(matmul_forget)\n",
    "    #forget_gate = tf.sigmoid(tf.matmul(i, fx) + tf.matmul(o, fm) + fb)\n",
    "    #update = update\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(matmul_output)\n",
    "    #output_gate = tf.sigmoid(tf.matmul(i, ox) + tf.matmul(o, om) + ob)\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",
    "    i_embed = tf.nn.embedding_lookup(vocabulary_embeddings, tf.argmax(i, dimension=1))\n",
    "    output, state = lstm_cell(i_embed, output, state)\n",
    "    outputs.append(output)\n",
    "\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",
    "  sample_input_embedding = tf.nn.embedding_lookup(vocabulary_embeddings, tf.argmax(sample_input, dimension=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",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input_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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0: 3.303772 learning rate: 10.000000\n",
      "Minibatch perplexity: 27.22\n",
      "================================================================================\n",
      "sebbontzvesheqdq ouoaclcrogjpt rcikt jsxqjp   ttwccfus aivveuaiuot jp k ycsuvooi\n",
      "whgoktx ssklugrano nywjecnrfonti shczyi asn yjhzee tzr e jztph  rqwbwiahxwn cpt \n",
      "aeeenhxaelnspvmpenpzswbms vr asnae  in h am pjpeposkebx lytshcsxjxaeeouhreeaglop\n",
      "hgttxeeuoiso n  aiqbci sjqrmisy l wjegdhrpf vhdzjkmxtsai  dckmztmdiehcpnsrapdwwd\n",
      " vbiac eg p rogpz hedsy chnmby mxepa atniniwkaaatg lws ipcequunkalrscegnrnemmeaw\n",
      "================================================================================\n",
      "Validation set perplexity: 19.11\n",
      "Average loss at step 100: 2.289506 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.95\n",
      "Validation set perplexity: 8.68\n",
      "Average loss at step 200: 2.032558 learning rate: 10.000000\n",
      "Minibatch perplexity: 8.07\n",
      "Validation set perplexity: 7.68\n",
      "Average loss at step 300: 1.951012 learning rate: 10.000000\n",
      "Minibatch perplexity: 7.32\n",
      "Validation set perplexity: 6.93\n",
      "Average loss at step 400: 1.890234 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.05\n",
      "Validation set perplexity: 6.52\n",
      "Average loss at step 500: 1.826638 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.07\n",
      "Validation set perplexity: 6.24\n",
      "Average loss at step 600: 1.818684 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.73\n",
      "Validation set perplexity: 6.21\n",
      "Average loss at step 700: 1.794433 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.16\n",
      "Validation set perplexity: 5.83\n",
      "Average loss at step 800: 1.772658 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.38\n",
      "Validation set perplexity: 5.68\n",
      "Average loss at step 900: 1.760141 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.93\n",
      "Validation set perplexity: 5.51\n",
      "Average loss at step 1000: 1.722639 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.08\n",
      "================================================================================\n",
      "g real as intentences anges rols affiis wamparley conting and the out speies gro\n",
      "s wen themet wemple a quing knowner the tredies arter bear cora desing nine jo o\n",
      "xing intoclum ferbutional of compected of legiton the viepe of tran and boyer on\n",
      "fieler comerical as s infiames openceper wose fronmatecion to as one vicle to ri\n",
      "conicount drentantideed poserial were ounder to some foundres lade and in elphai\n",
      "================================================================================\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 1100: 1.730187 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.42\n",
      "Validation set perplexity: 5.30\n",
      "Average loss at step 1200: 1.732570 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 5.28\n",
      "Average loss at step 1300: 1.721605 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.23\n",
      "Validation set perplexity: 5.30\n",
      "Average loss at step 1400: 1.691182 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 5.24\n",
      "Average loss at step 1500: 1.682752 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.90\n",
      "Validation set perplexity: 5.07\n",
      "Average loss at step 1600: 1.671851 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.25\n",
      "Validation set perplexity: 4.91\n",
      "Average loss at step 1700: 1.677286 learning rate: 10.000000\n",
      "Minibatch perplexity: 6.21\n",
      "Validation set perplexity: 4.92\n",
      "Average loss at step 1800: 1.692032 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.91\n",
      "Validation set perplexity: 4.80\n",
      "Average loss at step 1900: 1.673832 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.50\n",
      "Validation set perplexity: 4.83\n",
      "Average loss at step 2000: 1.682567 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.30\n",
      "================================================================================\n",
      "le newase to betwe shel inclused intern in it all s perormo througon in as gatti\n",
      "us ended onone meanted and collections reconto renturninication of lome both mak\n",
      "lency alculated that and monallizy and he roubis to the minist were two nine two\n",
      "umare and the connet memballe hand whitethod a sints vedpaile a famers the attid\n",
      "endans and anothee mose humicrankish fatt many at ponent were malsile race in on\n",
      "================================================================================\n",
      "Validation set perplexity: 5.01\n",
      "Average loss at step 2100: 1.666794 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 4.77\n",
      "Average loss at step 2200: 1.684781 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.06\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 2300: 1.667366 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.84\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 2400: 1.666110 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.14\n",
      "Validation set perplexity: 4.87\n",
      "Average loss at step 2500: 1.675706 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.07\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 2600: 1.664929 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.30\n",
      "Validation set perplexity: 4.74\n",
      "Average loss at step 2700: 1.652985 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.85\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 2800: 1.640630 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.72\n",
      "Validation set perplexity: 4.85\n",
      "Average loss at step 2900: 1.645753 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.05\n",
      "Validation set perplexity: 4.63\n",
      "Average loss at step 3000: 1.666144 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.59\n",
      "================================================================================\n",
      "minity eslates orgation escrovidums and docudeoval were examber the ammeral on a\n",
      "coness of s to a mathegarly chopan entor region weberapho overow offilma commorm\n",
      "ed good of had is kn s factes of known signs becames as work houp a pashetema wh\n",
      "irrs whomp jock leff liaving for orders by the dozor one seven four three zero t\n",
      "nesma a their the leversess three three nine of st arid countence sorts its qual\n",
      "================================================================================\n",
      "Validation set perplexity: 4.70\n",
      "Average loss at step 3100: 1.629552 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.03\n",
      "Validation set perplexity: 4.79\n",
      "Average loss at step 3200: 1.650048 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.61\n",
      "Validation set perplexity: 4.72\n",
      "Average loss at step 3300: 1.642449 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.00\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 3400: 1.637286 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.03\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 3500: 1.627459 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.52\n",
      "Validation set perplexity: 4.60\n",
      "Average loss at step 3600: 1.643477 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.59\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 3700: 1.614512 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.97\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 3800: 1.610799 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.80\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 3900: 1.607982 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.89\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 4000: 1.629375 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.87\n",
      "================================================================================\n",
      "zerm bion the usin to intribule with becweare warm filled as and the gefforl of \n",
      "bra one nine one one s one one one zero isbuse two nam questions sauder in the c\n",
      "gia right histaguypium one nine five one four shythoies on condatics from serian\n",
      "gated the magnhersoft secrohospicea the the logynhogens from ascained lege eagh \n",
      "ames scuselluign in carts interrited of the don speciis part of heral ga with us\n",
      "================================================================================\n",
      "Validation set perplexity: 4.80\n",
      "Average loss at step 4100: 1.638813 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.79\n",
      "Validation set perplexity: 4.84\n",
      "Average loss at step 4200: 1.618918 learning rate: 10.000000\n",
      "Minibatch perplexity: 4.73\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 4300: 1.585568 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.15\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 4400: 1.612613 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.25\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Validation set perplexity: 4.57\n",
      "Average loss at step 4500: 1.599956 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.25\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 4600: 1.601126 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.13\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 4700: 1.614047 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.16\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 4800: 1.612146 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.05\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 4900: 1.628908 learning rate: 10.000000\n",
      "Minibatch perplexity: 5.44\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 5000: 1.638265 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.73\n",
      "================================================================================\n",
      "maley verrings the follow translow than as simbogilony the peace chinemaciled fl\n",
      "fus balved cang ducts casi his geverale mass same vers as still of islaming term\n",
      "x is ricult of five of twosk replan cloke it simaily the cannated of one scolve \n",
      "wall distones was iss defeatment to cause the film one s is combensamechy chohis\n",
      "ust be and headenomealican centrue severes five o centuries liminally a scote tr\n",
      "================================================================================\n",
      "Validation set perplexity: 4.76\n",
      "Average loss at step 5100: 1.577732 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.45\n",
      "Validation set perplexity: 4.35\n",
      "Average loss at step 5200: 1.575365 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.40\n",
      "Validation set perplexity: 4.22\n",
      "Average loss at step 5300: 1.553939 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.95\n",
      "Validation set perplexity: 4.21\n",
      "Average loss at step 5400: 1.549978 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 4.21\n",
      "Average loss at step 5500: 1.547099 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.00\n",
      "Validation set perplexity: 4.17\n",
      "Average loss at step 5600: 1.536726 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.36\n",
      "Validation set perplexity: 4.16\n",
      "Average loss at step 5700: 1.571142 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.95\n",
      "Validation set perplexity: 4.18\n",
      "Average loss at step 5800: 1.556452 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.80\n",
      "Validation set perplexity: 4.15\n",
      "Average loss at step 5900: 1.566735 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.30\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6000: 1.530382 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.79\n",
      "================================================================================\n",
      "ple pagen states in from in orboay noffeen no five actresor is jevers despaperia\n",
      "lazad in binepeded in roning another gear phunistic full use and theirs to anoth\n",
      "thole sake maces probate bear tectendious igrure to has a one seven three one si\n",
      "thers which the passon i athms contrists companies bay on a have beent or death \n",
      "y and one eight four five vagen the addition tembere aren completobain in is var\n",
      "================================================================================\n",
      "Validation set perplexity: 4.19\n",
      "Average loss at step 6100: 1.576171 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.01\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6200: 1.573493 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.86\n",
      "Validation set perplexity: 4.20\n",
      "Average loss at step 6300: 1.558963 learning rate: 1.000000\n",
      "Minibatch perplexity: 5.17\n",
      "Validation set perplexity: 4.20\n",
      "Average loss at step 6400: 1.579153 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.73\n",
      "Validation set perplexity: 4.24\n",
      "Average loss at step 6500: 1.576742 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.39\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 6600: 1.559629 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.73\n",
      "Validation set perplexity: 4.24\n",
      "Average loss at step 6700: 1.552762 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.20\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6800: 1.566159 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.79\n",
      "Validation set perplexity: 4.21\n",
      "Average loss at step 6900: 1.598538 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 4.22\n",
      "Average loss at step 7000: 1.579698 learning rate: 1.000000\n",
      "Minibatch perplexity: 4.35\n",
      "================================================================================\n",
      "min the impression only brinoch coundensed universitions and gigrona s flowsizat\n",
      "se and telecach of the other secth also phy four four domen diphap international\n",
      "omche lelies gempth shour country enthy privitalist and the entrolfilian vipen t\n",
      "ch saut the tations one nine two zero zero zero to clibation eargest indatical f\n",
      "xical hjustor annisk unintublation in ripalfet in many sathel rate monally that \n",
      "================================================================================\n",
      "Validation set perplexity: 4.22\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": "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}