6_lstm.ipynb

{
 "cells": [
  {
   "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",
    "import os\n",
    "import numpy as np\n",
    "import random\n",
    "import string\n",
    "import tensorflow as tf\n",
    "import urllib\n",
    "import zipfile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "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, _ = urllib.urlretrieve(url + filename, filename)\n",
    "  statinfo = os.stat(filename)\n",
    "  if statinfo.st_size == expected_bytes:\n",
    "    print 'Found and verified', filename\n",
    "  else:\n",
    "    print statinfo.st_size\n",
    "    raise Exception(\n",
    "      'Failed to verify ' + filename + '. Can you get to it with a browser?')\n",
    "  return filename\n",
    "\n",
    "filename = maybe_download('text8.zip', 31344016)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "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",
    "  f = zipfile.ZipFile(filename)\n",
    "  for name in f.namelist():\n",
    "    return f.read(name)\n",
    "  f.close()\n",
    "  \n",
    "text = read_data(filename)\n",
    "print \"Data size\", 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",
    "collapsed": false,
    "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": 5,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "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": [
      "1 26 0 Unexpected character: ï\n",
      "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:', 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": 6,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 1
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "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 xrange(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 xrange(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 xrange(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 (mostl likely) character representation.\"\"\"\n",
    "  return [id2char(c) for c in np.argmax(probabilities, 1)]\n",
    "\n",
    "def batches2string(batches):\n",
    "  \"\"\"Convert a sequence of batches back into their (most likely) string\n",
    "  representation.\"\"\"\n",
    "  s = [''] * batches[0].shape[0]\n",
    "  for b in batches:\n",
    "    s = [''.join(x) for x in zip(s, characters(b))]\n",
    "  return s\n",
    "\n",
    "train_batches = BatchGenerator(train_text, batch_size, num_unrollings)\n",
    "valid_batches = BatchGenerator(valid_text, 1, 1)\n",
    "\n",
    "print batches2string(train_batches.next())\n",
    "print batches2string(train_batches.next())\n",
    "print batches2string(valid_batches.next())\n",
    "print batches2string(valid_batches.next())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "collapsed": true,
    "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 xrange(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": 8,
   "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",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in xrange(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(0, outputs), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 5000, 0.1, staircase=True)\n",
    "  optimizer = tf.train.GradientDescentOptimizer(learning_rate)\n",
    "  gradients, v = zip(*optimizer.compute_gradients(loss))\n",
    "  gradients, _ = tf.clip_by_global_norm(gradients, 1.25)\n",
    "  optimizer = optimizer.apply_gradients(\n",
    "    zip(gradients, v), global_step=global_step)\n",
    "\n",
    "  # Predictions.\n",
    "  train_prediction = tf.nn.softmax(logits)\n",
    "  \n",
    "  # Sampling and validation eval: batch 1, no unrolling.\n",
    "  sample_input = tf.placeholder(tf.float32, shape=[1, vocabulary_size])\n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input, saved_sample_output, saved_sample_state)\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "cellView": "both",
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "output_extras": [
      {
       "item_id": 41
      },
      {
       "item_id": 80
      },
      {
       "item_id": 126
      },
      {
       "item_id": 144
      }
     ]
    },
    "colab_type": "code",
    "collapsed": false,
    "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.29640889168 learning rate: 10.0\n",
      "Minibatch perplexity: 27.02\n",
      "================================================================================\n",
      "cimynsckvhyceethursne cnee  hhc xo merwatenn jansqjbxh qfp iqpije t vasapfi zmrn\n",
      "oah oeh hs uqbi l qxahpobgwagcor d gpux rps kcpnslacoheheiec eeptrvimgre vgcetq \n",
      "h ne bkhrfdm x vidbvnneihe ihir eiuekdotqds ulsvuy b ig mem aa qh esio gmd y kui\n",
      "avdqscjsvkjw de jey kwbfrtadffcnibi iu a ia csemcwholptrkdon osttyovnxebxulrdumv\n",
      "dfhol  i xhfergefa iyy   ptkbijtljataroj b dspgxtbgqeomhloj idsefdo zpqgcziwog y\n",
      "================================================================================\n",
      "Validation set perplexity: 20.33\n",
      "Average loss at step 100 : 2.58745916605 learning rate: 10.0\n",
      "Minibatch perplexity: 10.97\n",
      "Validation set perplexity: 10.33\n",
      "Average loss at step 200 : 2.24409008026 learning rate: 10.0\n",
      "Minibatch perplexity: 8.56\n",
      "Validation set perplexity: 8.62\n",
      "Average loss at step 300 : 2.09552945614 learning rate: 10.0\n",
      "Minibatch perplexity: 7.41\n",
      "Validation set perplexity: 8.02\n",
      "Average loss at step 400 : 2.00090043664 learning rate: 10.0\n",
      "Minibatch perplexity: 7.36\n",
      "Validation set perplexity: 7.85\n",
      "Average loss at step 500 : 1.93618414044 learning rate: 10.0\n",
      "Minibatch perplexity: 6.50\n",
      "Validation set perplexity: 7.33\n",
      "Average loss at step 600 : 1.90925689101 learning rate: 10.0\n",
      "Minibatch perplexity: 6.08\n",
      "Validation set perplexity: 7.12\n",
      "Average loss at step 700 : 1.85845567346 learning rate: 10.0\n",
      "Minibatch perplexity: 6.34\n",
      "Validation set perplexity: 6.71\n",
      "Average loss at step 800 : 1.81378177762 learning rate: 10.0\n",
      "Minibatch perplexity: 5.86\n",
      "Validation set perplexity: 6.33\n",
      "Average loss at step 900 : 1.82547027111 learning rate: 10.0\n",
      "Minibatch perplexity: 6.80\n",
      "Validation set perplexity: 6.26\n",
      "Average loss at step 1000 : 1.82470382333 learning rate: 10.0\n",
      "Minibatch perplexity: 5.57\n",
      "================================================================================\n",
      "jer recorted jown to and ncly cluesic digi han offerations of preced of wheren m\n",
      "x firerose of the aidver an exter kromd of the rikong and one oate ie inclupets \n",
      "n penytional gude nate beencolized to the alfromage one nine zero nxwall of leck\n",
      "h see and atopely mossiues and for a fove for acnance in the compla verca prefer\n",
      "bee frod gitusm toct alto the hishons the e uerer coleferse and airun sternwerst\n",
      "================================================================================\n",
      "Validation set perplexity: 6.13\n",
      "Average loss at step 1100 : 1.77091690063 learning rate: 10.0\n",
      "Minibatch perplexity: 5.45\n",
      "Validation set perplexity: 5.87\n",
      "Average loss at step 1200 : 1.74898819208 learning rate: 10.0\n",
      "Minibatch perplexity: 5.05\n",
      "Validation set perplexity: 5.69\n",
      "Average loss at step 1300 : 1.73196932077 learning rate: 10.0\n",
      "Minibatch perplexity: 5.81\n",
      "Validation set perplexity: 5.60\n",
      "Average loss at step 1400 : 1.74729372025 learning rate: 10.0\n",
      "Minibatch perplexity: 5.87\n",
      "Validation set perplexity: 5.52\n",
      "Average loss at step 1500 : 1.73682139158 learning rate: 10.0\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 5.48\n",
      "Average loss at step 1600 : 1.74396863222 learning rate: 10.0\n",
      "Minibatch perplexity: 5.46\n",
      "Validation set perplexity: 5.54\n",
      "Average loss at step 1700 : 1.71166958928 learning rate: 10.0\n",
      "Minibatch perplexity: 5.61\n",
      "Validation set perplexity: 5.45\n",
      "Average loss at step 1800 : 1.6733892858 learning rate: 10.0\n",
      "Minibatch perplexity: 5.27\n",
      "Validation set perplexity: 5.26\n",
      "Average loss at step 1900 : 1.64714217901 learning rate: 10.0\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 5.16\n",
      "Average loss at step 2000 : 1.69658929229 learning rate: 10.0\n",
      "Minibatch perplexity: 5.69\n",
      "================================================================================\n",
      "quides on spical for six tour four stilarg bottle of has flack annicess longous \n",
      "h im begub one nine nine eight one nine eight camened in of process givarcharian\n",
      "keneage by englisl leady the neigy community in pegan mppy bit middles and to be\n",
      "hobours more it and ling a bit peabliness natic dus outhorridal by team be reper\n",
      "mest on worners is indures indutine doting of his togen anvion set for with it o\n",
      "================================================================================\n",
      "Validation set perplexity: 5.19\n",
      "Average loss at step 2100 : 1.68483890772 learning rate: 10.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 4.97\n",
      "Average loss at step 2200 : 1.6809530437 learning rate: 10.0\n",
      "Minibatch perplexity: 6.46\n",
      "Validation set perplexity: 4.94\n",
      "Average loss at step 2300 : 1.6393625319 learning rate: 10.0\n",
      "Minibatch perplexity: 4.95\n",
      "Validation set perplexity: 4.76\n",
      "Average loss at step 2400 : 1.66166785002 learning rate: 10.0\n",
      "Minibatch perplexity: 5.00\n",
      "Validation set perplexity: 4.70\n",
      "Average loss at step 2500 : 1.6818802619 learning rate: 10.0\n",
      "Minibatch perplexity: 5.28\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 2600 : 1.65804368377 learning rate: 10.0\n",
      "Minibatch perplexity: 5.81\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 2700 : 1.65924729228 learning rate: 10.0\n",
      "Minibatch perplexity: 4.58\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 2800 : 1.65172558546 learning rate: 10.0\n",
      "Minibatch perplexity: 5.57\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 2900 : 1.65034497976 learning rate: 10.0\n",
      "Minibatch perplexity: 5.77\n",
      "Validation set perplexity: 4.65\n",
      "Average loss at step 3000 : 1.65291190863 learning rate: 10.0\n",
      "Minibatch perplexity: 5.08\n",
      "================================================================================\n",
      "zer strexger rebooded as asuen fuliols one one eight gan zers to and greake sinc\n",
      "b ra park t systan with s he foulds illess the blocy as the limpres he thind dis\n",
      "j in electomo and har exerior passes courn indupty thropent of the as suptin wou\n",
      "der bain kentrobis out of desmonditic and for a efthen gruadp ruvy cenving is ru\n",
      "xal fingses ausit zeob panes and india god the recegrays is that afteration of d\n",
      "================================================================================\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 3100 : 1.62560631871 learning rate: 10.0\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 4.67\n",
      "Average loss at step 3200 : 1.6378605032 learning rate: 10.0\n",
      "Minibatch perplexity: 5.37\n",
      "Validation set perplexity: 4.64\n",
      "Average loss at step 3300 : 1.63589345455 learning rate: 10.0\n",
      "Minibatch perplexity: 5.02\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 3400 : 1.6681309402 learning rate: 10.0\n",
      "Minibatch perplexity: 5.39\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 3500 : 1.65540112138 learning rate: 10.0\n",
      "Minibatch perplexity: 5.65\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 3600 : 1.66671798706 learning rate: 10.0\n",
      "Minibatch perplexity: 4.45\n",
      "Validation set perplexity: 4.46\n",
      "Average loss at step 3700 : 1.64825275183 learning rate: 10.0\n",
      "Minibatch perplexity: 5.08\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 3800 : 1.64601139307 learning rate: 10.0\n",
      "Minibatch perplexity: 5.17\n",
      "Validation set perplexity: 4.66\n",
      "Average loss at step 3900 : 1.63700724125 learning rate: 10.0\n",
      "Minibatch perplexity: 5.27\n",
      "Validation set perplexity: 4.60\n",
      "Average loss at step 4000 : 1.65408348799 learning rate: 10.0\n",
      "Minibatch perplexity: 4.84\n",
      "================================================================================\n",
      "plate one two zero zero zero tikalz with entaild in leccceders of the implones a\n",
      "zer a small by therentine quax eranch three governive dur midored latic he tous \n",
      "cately in or someto tour then entresse undery the ca by pail tamsay ageal they y\n",
      "ouss fcorps of treational the rmpo tugh out of godraction of lop montron queve t\n",
      "fition maes dipecries may game pasiciquet by one nine nine nine zero one eightme\n",
      "================================================================================\n",
      "Validation set perplexity: 4.63\n",
      "Average loss at step 4100 : 1.6345816052 learning rate: 10.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 4.75\n",
      "Average loss at step 4200 : 1.63548008561 learning rate: 10.0\n",
      "Minibatch perplexity: 5.22\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 4300 : 1.61438891649 learning rate: 10.0\n",
      "Minibatch perplexity: 4.97\n",
      "Validation set perplexity: 4.51\n",
      "Average loss at step 4400 : 1.61171692491 learning rate: 10.0\n",
      "Minibatch perplexity: 4.82\n",
      "Validation set perplexity: 4.40\n",
      "Average loss at step 4500 : 1.61749396205 learning rate: 10.0\n",
      "Minibatch perplexity: 5.29\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 4600 : 1.61416617393 learning rate: 10.0\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 4700 : 1.62555432677 learning rate: 10.0\n",
      "Minibatch perplexity: 5.30\n",
      "Validation set perplexity: 4.48\n",
      "Average loss at step 4800 : 1.63250727892 learning rate: 10.0\n",
      "Minibatch perplexity: 4.37\n",
      "Validation set perplexity: 4.41\n",
      "Average loss at step 4900 : 1.63342042804 learning rate: 10.0\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 5000 : 1.60958368063 learning rate: 1.0\n",
      "Minibatch perplexity: 4.42\n",
      "================================================================================\n",
      "ing of conditionation with that some one femspen franker so refer mvhens gnanmin\n",
      "ent hip in nay one zero a called in meni of the it of the skoths of his divid br\n",
      "al tedrewite five four b of objew game forsion is one nine nine two eight enrive\n",
      "mare on jale as between leastly in moliol on thut it word so is hatlence was of \n",
      "us as s limition regars in a penias takign as the shel s heshale thryest umod la\n",
      "================================================================================\n",
      "Validation set perplexity: 4.61\n",
      "Average loss at step 5100 : 1.60352383852 learning rate: 1.0\n",
      "Minibatch perplexity: 4.90\n",
      "Validation set perplexity: 4.39\n",
      "Average loss at step 5200 : 1.59302769661 learning rate: 1.0\n",
      "Minibatch perplexity: 4.78\n",
      "Validation set perplexity: 4.36\n",
      "Average loss at step 5300 : 1.5813689816 learning rate: 1.0\n",
      "Minibatch perplexity: 4.61\n",
      "Validation set perplexity: 4.35\n",
      "Average loss at step 5400 : 1.5799508369 learning rate: 1.0\n",
      "Minibatch perplexity: 5.20\n",
      "Validation set perplexity: 4.31\n",
      "Average loss at step 5500 : 1.56623719215 learning rate: 1.0\n",
      "Minibatch perplexity: 4.79\n",
      "Validation set perplexity: 4.29\n",
      "Average loss at step 5600 : 1.57976825953 learning rate: 1.0\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 4.28\n",
      "Average loss at step 5700 : 1.56654176593 learning rate: 1.0\n",
      "Minibatch perplexity: 4.50\n",
      "Validation set perplexity: 4.29\n",
      "Average loss at step 5800 : 1.57947267413 learning rate: 1.0\n",
      "Minibatch perplexity: 4.87\n",
      "Validation set perplexity: 4.30\n",
      "Average loss at step 5900 : 1.57260293722 learning rate: 1.0\n",
      "Minibatch perplexity: 5.01\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 6000 : 1.54763782024 learning rate: 1.0\n",
      "Minibatch perplexity: 4.96\n",
      "================================================================================\n",
      "vies of the black by and was port modelns pace time is now turns american shoulv\n",
      "way are viston wo lublic in quistant lacture sposterchinal all one nine six nine\n",
      "ly home the controputry homes parly standed some framas braywis state otits song\n",
      "du abto orgediection become the iore portop unie would death is with and kinanne\n",
      "k pilaffro the wyrings and one and accelton himientary in three two similar is n\n",
      "================================================================================\n",
      "Validation set perplexity: 4.28\n",
      "Average loss at step 6100 : 1.5642841959 learning rate: 1.0\n",
      "Minibatch perplexity: 5.23\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 6200 : 1.53071456075 learning rate: 1.0\n",
      "Minibatch perplexity: 4.70\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 6300 : 1.54436980367 learning rate: 1.0\n",
      "Minibatch perplexity: 4.99\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 6400 : 1.5418026948 learning rate: 1.0\n",
      "Minibatch perplexity: 4.53\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 6500 : 1.55597401261 learning rate: 1.0\n",
      "Minibatch perplexity: 4.51\n",
      "Validation set perplexity: 4.24\n",
      "Average loss at step 6600 : 1.5998458147 learning rate: 1.0\n",
      "Minibatch perplexity: 4.80\n",
      "Validation set perplexity: 4.24\n",
      "Average loss at step 6700 : 1.58053517222 learning rate: 1.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6800 : 1.60261644363 learning rate: 1.0\n",
      "Minibatch perplexity: 4.66\n",
      "Validation set perplexity: 4.23\n",
      "Average loss at step 6900 : 1.58445885897 learning rate: 1.0\n",
      "Minibatch perplexity: 4.63\n",
      "Validation set perplexity: 4.25\n",
      "Average loss at step 7000 : 1.57798384428 learning rate: 1.0\n",
      "Minibatch perplexity: 4.95\n",
      "================================================================================\n",
      "ation considerowly lowerge of the fould in omeriary in the mall of accords where\n",
      "y was tens mesered ty now resupple a cuironed good inthing locks a smithoraboil \n",
      "cogyt to batted cellection councils the sportan currence briteyon briter is one \n",
      "mentalise and eut called states fromow quaile if orberce vitywars fection of the\n",
      "y their sene of thereis on another bamber of hit im beensing sodules prothematio\n",
      "================================================================================\n",
      "Validation set perplexity: 4.23\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print 'Initialized'\n",
    "  mean_loss = 0\n",
    "  for step in xrange(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in xrange(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 'Average loss at step', step, ':', mean_loss, 'learning rate:', 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 xrange(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in xrange(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 xrange(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",
    "---\n",
    "\n",
    "\n",
    "### Answer:\n",
    "Graph is redone in graph2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "\n",
    "graph2 = tf.Graph()\n",
    "with graph2.as_default():\n",
    "  \n",
    "  # Parameters:\n",
    "  # Input/output gate:  gw * (input, prev output) + bias.\n",
    "  gw = tf.Variable(tf.truncated_normal([vocabulary_size + num_nodes, 2*num_nodes], -0.1, 0.1))\n",
    "  gb = tf.Variable(tf.zeros([1, 2*num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cw = tf.Variable(tf.truncated_normal([vocabulary_size + 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",
    "  ow = tf.Variable(tf.truncated_normal([vocabulary_size + 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",
    "    \n",
    "    # prev forget_gate had dim batches, num_nodes.\n",
    "    # now gates have dim: batches, num_nodes*2\n",
    "    \n",
    "    io = tf.concat(1, [i, o])\n",
    "    \n",
    "    gates = tf.sigmoid( tf.matmul( io,  gw ) + gb )\n",
    "    update = tf.matmul( io, cw ) + cb\n",
    "    state = gates[:, :num_nodes]*state + gates[:,num_nodes:]*tf.tanh(update)\n",
    "         \n",
    "    output_gate = tf.sigmoid( tf.matmul( io, ow ) + ob )\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "  for _ in xrange(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(0, outputs), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\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": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0 : 3.29512786865 learning rate: 10.0\n",
      "Minibatch perplexity: 26.98\n",
      "================================================================================\n",
      "dxcgirpoelrlfinrorvlti  es las bmmq unws h   cb daiarqimyth hzqm ahchojazpi esrs\n",
      "q lxiraaegfelaeatvbrqss vyektoy osdret okyghept tmoim yowpzurvy wc yotrleg edcyi\n",
      "cahtnwdtcdne omjs ry onejsnlnncatmwfjtmbaekzlz  hsnr kf xkhnelvuxy trceaahzeirrm\n",
      "hdai iovdrexaoggnesadv vpqcaoy eonen gbpwj wnwwelazyl duir dt eebahnhdtnuko   a \n",
      "rmntakgvhenbo eefqm     owg  qtvh vts  xzxna  ik  e  hsm tx   ribeygeefkem  shte\n",
      "================================================================================\n",
      "Validation set perplexity: 20.10\n",
      "Average loss at step 100 : 2.59435007572 learning rate: 10.0\n",
      "Minibatch perplexity: 10.65\n",
      "Validation set perplexity: 10.50\n",
      "Average loss at step 200 : 2.24177724481 learning rate: 10.0\n",
      "Minibatch perplexity: 8.33\n",
      "Validation set perplexity: 8.63\n",
      "Average loss at step 300 : 2.07893599272 learning rate: 10.0\n",
      "Minibatch perplexity: 6.22\n",
      "Validation set perplexity: 7.96\n",
      "Average loss at step 400 : 2.02712780833 learning rate: 10.0\n",
      "Minibatch perplexity: 7.90\n",
      "Validation set perplexity: 7.78\n",
      "Average loss at step 500 : 1.96946704626 learning rate: 10.0\n",
      "Minibatch perplexity: 6.35\n",
      "Validation set perplexity: 7.23\n",
      "Average loss at step 600 : 1.8874876833 learning rate: 10.0\n",
      "Minibatch perplexity: 6.46\n",
      "Validation set perplexity: 7.14\n",
      "Average loss at step 700 : 1.86307409167 learning rate: 10.0\n",
      "Minibatch perplexity: 6.90\n",
      "Validation set perplexity: 6.57\n",
      "Average loss at step 800 : 1.85711881638 learning rate: 10.0\n",
      "Minibatch perplexity: 7.04\n",
      "Validation set perplexity: 6.70\n",
      "Average loss at step 900 : 1.83820097089 learning rate: 10.0\n",
      "Minibatch perplexity: 6.00\n",
      "Validation set perplexity: 6.54\n",
      "Average loss at step 1000 : 1.83378350616 learning rate: 10.0\n",
      "Minibatch perplexity: 6.29\n",
      "================================================================================\n",
      "del mapah of ghowfe abyonk hench and mys the sust frent by feltust lary were law\n",
      "y alvord jesidurarly vulish to acjrees some fumitod attama ofts unitions secour \n",
      "men s ligring searw whike manuel aghessy one and for channginzer sonitvic thised\n",
      "learys an abremies pares the five filstia andocical of brengh on with beths simb\n",
      "gobs one nine mackad with he clapion can starch mak whicf tug renonions docosed \n",
      "================================================================================\n",
      "Validation set perplexity: 6.24\n",
      "Average loss at step 1100 : 1.79023654819 learning rate: 10.0\n",
      "Minibatch perplexity: 5.54\n",
      "Validation set perplexity: 6.26\n",
      "Average loss at step 1200 : 1.75658436775 learning rate: 10.0\n",
      "Minibatch perplexity: 6.30\n",
      "Validation set perplexity: 6.12\n",
      "Average loss at step 1300 : 1.75145785928 learning rate: 10.0\n",
      "Minibatch perplexity: 6.10\n",
      "Validation set perplexity: 5.99\n",
      "Average loss at step 1400 : 1.7526627326 learning rate: 10.0\n",
      "Minibatch perplexity: 6.09\n",
      "Validation set perplexity: 5.88\n",
      "Average loss at step 1500 : 1.73793074489 learning rate: 10.0\n",
      "Minibatch perplexity: 5.56\n",
      "Validation set perplexity: 5.64\n",
      "Average loss at step 1600 : 1.71734047651 learning rate: 10.0\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 5.59\n",
      "Average loss at step 1700 : 1.70344475031 learning rate: 10.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 5.43\n",
      "Average loss at step 1800 : 1.67690508485 learning rate: 10.0\n",
      "Minibatch perplexity: 5.02\n",
      "Validation set perplexity: 5.28\n",
      "Average loss at step 1900 : 1.68198055029 learning rate: 10.0\n",
      "Minibatch perplexity: 5.17\n",
      "Validation set perplexity: 5.43\n",
      "Average loss at step 2000 : 1.665093292 learning rate: 10.0\n",
      "Minibatch perplexity: 5.14\n",
      "================================================================================\n",
      "lokests of lish the coodies s claudia and strin jadafould one nixe to powerse ve\n",
      "read for here swas been ascobutems are nation with after phog miltisy at and to \n",
      "x withtales destious inine los tolloging of fast after what idewan a litional to\n",
      "n mussities the keplery groughty tasooved toure diopt for his metion and amret d\n",
      "phes which usher it is part bi arts anpaitment that of lost and jossignh suaron \n",
      "================================================================================\n",
      "Validation set perplexity: 5.45\n",
      "Average loss at step 2100 : 1.6723740983 learning rate: 10.0\n",
      "Minibatch perplexity: 4.93\n",
      "Validation set perplexity: 5.22\n",
      "Average loss at step 2200 : 1.6907280767 learning rate: 10.0\n",
      "Minibatch perplexity: 4.94\n",
      "Validation set perplexity: 5.12\n",
      "Average loss at step 2300 : 1.69147670269 learning rate: 10.0\n",
      "Minibatch perplexity: 6.33\n",
      "Validation set perplexity: 5.14\n",
      "Average loss at step 2400 : 1.67345902562 learning rate: 10.0\n",
      "Minibatch perplexity: 5.72\n",
      "Validation set perplexity: 5.19\n",
      "Average loss at step 2500 : 1.67594738007 learning rate: 10.0\n",
      "Minibatch perplexity: 5.83\n",
      "Validation set perplexity: 5.24\n",
      "Average loss at step 2600 : 1.65514564037 learning rate: 10.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 5.16\n",
      "Average loss at step 2700 : 1.66824165821 learning rate: 10.0\n",
      "Minibatch perplexity: 5.20\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 2800 : 1.66668726444 learning rate: 10.0\n",
      "Minibatch perplexity: 5.36\n",
      "Validation set perplexity: 5.35\n",
      "Average loss at step 2900 : 1.6625217557 learning rate: 10.0\n",
      "Minibatch perplexity: 5.98\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 3000 : 1.66892326713 learning rate: 10.0\n",
      "Minibatch perplexity: 4.93\n",
      "================================================================================\n",
      "s officent of being lay new an different and cydes and the linko the french and \n",
      "zer with is cullent of a pared that nox datoded of north take are ches to pums o\n",
      "ch and the ligedent of ono tribure must movew and nolem to consulse ance offer t\n",
      "ber lorcate in feur regent is used the comal kale seved vire descroded at the so\n",
      "ing state an anded from powition and term so hichol tomoon in duraed eliman ahti\n",
      "================================================================================\n",
      "Validation set perplexity: 5.10\n",
      "Average loss at step 3100 : 1.6413552475 learning rate: 10.0\n",
      "Minibatch perplexity: 5.13\n",
      "Validation set perplexity: 5.05\n",
      "Average loss at step 3200 : 1.62389369488 learning rate: 10.0\n",
      "Minibatch perplexity: 5.47\n",
      "Validation set perplexity: 4.99\n",
      "Average loss at step 3300 : 1.63208126187 learning rate: 10.0\n",
      "Minibatch perplexity: 4.95\n",
      "Validation set perplexity: 4.99\n",
      "Average loss at step 3400 : 1.61942911386 learning rate: 10.0\n",
      "Minibatch perplexity: 5.17\n",
      "Validation set perplexity: 5.01\n",
      "Average loss at step 3500 : 1.66388855577 learning rate: 10.0\n",
      "Minibatch perplexity: 6.06\n",
      "Validation set perplexity: 4.93\n",
      "Average loss at step 3600 : 1.63849938273 learning rate: 10.0\n",
      "Minibatch perplexity: 5.31\n",
      "Validation set perplexity: 4.78\n",
      "Average loss at step 3700 : 1.63698472738 learning rate: 10.0\n",
      "Minibatch perplexity: 4.99\n",
      "Validation set perplexity: 4.86\n",
      "Average loss at step 3800 : 1.64841855168 learning rate: 10.0\n",
      "Minibatch perplexity: 5.96\n",
      "Validation set perplexity: 4.88\n",
      "Average loss at step 3900 : 1.63664324999 learning rate: 10.0\n",
      "Minibatch perplexity: 4.24\n",
      "Validation set perplexity: 4.82\n",
      "Average loss at step 4000 : 1.62648761868 learning rate: 10.0\n",
      "Minibatch perplexity: 5.37\n",
      "================================================================================\n",
      "we for t use bosed condo with registjin in indo offe that now fornals d verih a \n",
      "riginate tombetery has to fiven an expoird hash forring is is complace stricurs \n",
      "stern adforts book shard for by stat in the tempirate fous one nine eight five z\n",
      "so ma state that assorments an inceptipal is players towing deitlention axamor c\n",
      "nglighty five and reference it from does and who throws less fegral was cusscuve\n",
      "================================================================================\n",
      "Validation set perplexity: 4.75\n",
      "Average loss at step 4100 : 1.60541183591 learning rate: 10.0\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 4.75\n",
      "Average loss at step 4200 : 1.59669798017 learning rate: 10.0\n",
      "Minibatch perplexity: 4.91\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 4300 : 1.60225054741 learning rate: 10.0\n",
      "Minibatch perplexity: 5.37\n",
      "Validation set perplexity: 4.73\n",
      "Average loss at step 4400 : 1.59366964817 learning rate: 10.0\n",
      "Minibatch perplexity: 5.31\n",
      "Validation set perplexity: 4.80\n",
      "Average loss at step 4500 : 1.62773093104 learning rate: 10.0\n",
      "Minibatch perplexity: 5.14\n",
      "Validation set perplexity: 4.93\n",
      "Average loss at step 4600 : 1.60918056846 learning rate: 10.0\n",
      "Minibatch perplexity: 5.55\n",
      "Validation set perplexity: 4.72\n",
      "Average loss at step 4700 : 1.60772798657 learning rate: 10.0\n",
      "Minibatch perplexity: 4.61\n",
      "Validation set perplexity: 4.89\n",
      "Average loss at step 4800 : 1.59129152536 learning rate: 10.0\n",
      "Minibatch perplexity: 4.56\n",
      "Validation set perplexity: 4.81\n",
      "Average loss at step 4900 : 1.60557092428 learning rate: 10.0\n",
      "Minibatch perplexity: 5.31\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 5000 : 1.59899495006 learning rate: 1.0\n",
      "Minibatch perplexity: 4.80\n",
      "================================================================================\n",
      "ke espoles the specepuplesensem a sawlen years andblower of the hums had warror \n",
      "y raportly and the plessuigd sijies e there man have almort wad eximples who wit\n",
      "p is four ows had raper channed was the queemencularia callome teensing one nine\n",
      "ing as secound the trees their would in the chinghing if an oppreatnhopan earlys\n",
      "ch electroly date of won from even the teun specives to actoof the poluss of b m\n",
      "================================================================================\n",
      "Validation set perplexity: 4.79\n",
      "Average loss at step 5100 : 1.57064375758 learning rate: 1.0\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 4.63\n",
      "Average loss at step 5200 : 1.57493939757 learning rate: 1.0\n",
      "Minibatch perplexity: 5.03\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 5300 : 1.57622501731 learning rate: 1.0\n",
      "Minibatch perplexity: 5.09\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 5400 : 1.57752721667 learning rate: 1.0\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 5500 : 1.56865869164 learning rate: 1.0\n",
      "Minibatch perplexity: 5.07\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 5600 : 1.54363653779 learning rate: 1.0\n",
      "Minibatch perplexity: 4.13\n",
      "Validation set perplexity: 4.51\n",
      "Average loss at step 5700 : 1.56307854772 learning rate: 1.0\n",
      "Minibatch perplexity: 4.54\n",
      "Validation set perplexity: 4.47\n",
      "Average loss at step 5800 : 1.58218278289 learning rate: 1.0\n",
      "Minibatch perplexity: 4.56\n",
      "Validation set perplexity: 4.49\n",
      "Average loss at step 5900 : 1.57001429081 learning rate: 1.0\n",
      "Minibatch perplexity: 5.17\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 6000 : 1.56639047265 learning rate: 1.0\n",
      "Minibatch perplexity: 4.55\n",
      "================================================================================\n",
      "inning modernc sair ludg are abate somanies or enokstura for gradsicigule a mans\n",
      "p the ison scritical invauticution and teloants of sam war is all chread can nea\n",
      "netalo aniumem mi monetarl juny of the unitual as arbail one nine eight general \n",
      "ing notibe in were one zero seven sevenseet of ability sitsce he with on byerd o\n",
      "sterit in the phy of rann each impace searte differences lesship over one one ni\n",
      "================================================================================\n",
      "Validation set perplexity: 4.47\n",
      "Average loss at step 6100 : 1.55983754635 learning rate: 1.0\n",
      "Minibatch perplexity: 4.46\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 6200 : 1.56839295745 learning rate: 1.0\n",
      "Minibatch perplexity: 4.53\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 6300 : 1.56758382559 learning rate: 1.0\n",
      "Minibatch perplexity: 5.25\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 6400 : 1.55881404638 learning rate: 1.0\n",
      "Minibatch perplexity: 4.21\n",
      "Validation set perplexity: 4.56\n",
      "Average loss at step 6500 : 1.53874875307 learning rate: 1.0\n",
      "Minibatch perplexity: 5.18\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 6600 : 1.58556729674 learning rate: 1.0\n",
      "Minibatch perplexity: 5.53\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 6700 : 1.55294468999 learning rate: 1.0\n",
      "Minibatch perplexity: 5.33\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 6800 : 1.55962763071 learning rate: 1.0\n",
      "Minibatch perplexity: 4.75\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 6900 : 1.55473654628 learning rate: 1.0\n",
      "Minibatch perplexity: 4.54\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 7000 : 1.57100507021 learning rate: 1.0\n",
      "Minibatch perplexity: 4.98\n",
      "================================================================================\n",
      "us over were the indercoprone hinarce advi during usent politically latincoldia \n",
      "quer esplyching four the warfet and can echagre are musuir was a natesti x the h\n",
      "net naclel finallycher on the karrism in including surformation pressant it lice\n",
      "zers in successence four similarly crovect and the leading eace to succrins were\n",
      "be all the deadises the econosic in a setis as pulsis in mixonally similar impor\n",
      "================================================================================\n",
      "Validation set perplexity: 4.53\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph2) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print 'Initialized'\n",
    "  mean_loss = 0\n",
    "  for step in xrange(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in xrange(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 'Average loss at step', step, ':', mean_loss, 'learning rate:', 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 xrange(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in xrange(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 xrange(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": {},
   "source": [
    "### Answer a:\n",
    "Use 64 or 128 dim embeddings for each character but output probabilities for each character."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "embed_dim = 64\n",
    "\n",
    "graph3 = tf.Graph()\n",
    "with graph3.as_default():\n",
    "    \n",
    "  embeddings = tf.Variable(\n",
    "    tf.random_uniform([ vocabulary_size, embed_dim], -1.0, 1.0))\n",
    "  \n",
    "  # Parameters:\n",
    "  # Input/output gate:  gw * (input, prev output) + bias.\n",
    "  gw = tf.Variable(tf.truncated_normal([embed_dim + num_nodes, 2*num_nodes], -0.1, 0.1))\n",
    "  gb = tf.Variable(tf.zeros([1, 2*num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cw = tf.Variable(tf.truncated_normal([embed_dim + 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",
    "  ow = tf.Variable(tf.truncated_normal([embed_dim + num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ob = tf.Variable(tf.zeros([1, num_nodes]))\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",
    "  # Classify to encoding, not embedding\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    \n",
    "    # prev forget_gate had dim batches, num_nodes.\n",
    "    # now gates have dim: batches, num_nodes*2\n",
    "    \n",
    "    io = tf.concat(1, [i, o])\n",
    "    \n",
    "    gates = tf.sigmoid( tf.matmul( io,  gw ) + gb ) # gates are made of both remember and input gates\n",
    "    update = tf.matmul( io, cw ) + cb\n",
    "    state = gates[:, :num_nodes]*state + gates[:,num_nodes:]*tf.tanh(update)\n",
    "         \n",
    "    output_gate = tf.sigmoid( tf.matmul( io, ow ) + ob )\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "\n",
    "  for _ in xrange(num_unrollings + 1):\n",
    "    inp = tf.placeholder(tf.float32, shape=[batch_size, vocabulary_size])\n",
    "    train_data.append( inp )\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",
    "\n",
    "  for i in train_inputs:\n",
    "    i_embedded = tf.nn.embedding_lookup(embeddings, tf.argmax(i, 1) ) # lookup index in range (0, 729) \n",
    "    output, state = lstm_cell(i_embedded, 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(0, outputs), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\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",
    "    \n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "\n",
    "  reset_sample_state = tf.group(\n",
    "    saved_sample_output.assign(tf.zeros([1, num_nodes])),\n",
    "    saved_sample_state.assign(tf.zeros([1, num_nodes])))\n",
    "    \n",
    "  sample_input_embedded = tf.nn.embedding_lookup( embeddings, tf.argmax(sample_input, 1) )  \n",
    "  \n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input_embedded, saved_sample_output, saved_sample_state)\n",
    "\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": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0 : 3.30612564087 learning rate: 10.0\n",
      "Minibatch perplexity: 27.28\n",
      "================================================================================\n",
      "h feiyv bx gblihzqsjtpxfuildnzdodkpgttmklsgkarbe lxxmfegli  h tebefjpa tv rlmech\n",
      "  hmr    ieoel eu nuenn lnaiwd  iatgnqpztz ee cfbdbwmvikuwrwa  ife    p  i mujxq\n",
      "fea ia f in liex tu rkzpnnu nfxrsrf mrpn ubk nfhdztch  be   nv ocjdj  nvsie h mm\n",
      "o eabris nxtnotr itkam zhdnxgreyxqo htdpeovylzqxo ttzhiov pasqe   eeen tyctctz  \n",
      "xfey xn qfuxjxqunr e mni vgmitedsd aizloujie ibcdh muzksobqchay gecnmuejasnrianm\n",
      "================================================================================\n",
      "Validation set perplexity: 20.36\n",
      "Average loss at step 100 : 2.32699063778 learning rate: 10.0\n",
      "Minibatch perplexity: 8.44\n",
      "Validation set perplexity: 8.77\n",
      "Average loss at step 200 : 2.00615390301 learning rate: 10.0\n",
      "Minibatch perplexity: 7.03\n",
      "Validation set perplexity: 7.04\n",
      "Average loss at step 300 : 1.90256994486 learning rate: 10.0\n",
      "Minibatch perplexity: 6.53\n",
      "Validation set perplexity: 6.47\n",
      "Average loss at step 400 : 1.83382575035 learning rate: 10.0\n",
      "Minibatch perplexity: 6.73\n",
      "Validation set perplexity: 6.02\n",
      "Average loss at step 500 : 1.79684835672 learning rate: 10.0\n",
      "Minibatch perplexity: 5.76\n",
      "Validation set perplexity: 5.71\n",
      "Average loss at step 600 : 1.78719952464 learning rate: 10.0\n",
      "Minibatch perplexity: 5.37\n",
      "Validation set perplexity: 5.58\n",
      "Average loss at step 700 : 1.74859771252 learning rate: 10.0\n",
      "Minibatch perplexity: 6.10\n",
      "Validation set perplexity: 5.40\n",
      "Average loss at step 800 : 1.71143076181 learning rate: 10.0\n",
      "Minibatch perplexity: 5.26\n",
      "Validation set perplexity: 5.33\n",
      "Average loss at step 900 : 1.73255998373 learning rate: 10.0\n",
      "Minibatch perplexity: 6.33\n",
      "Validation set perplexity: 5.32\n",
      "Average loss at step 1000 : 1.7342790699 learning rate: 10.0\n",
      "Minibatch perplexity: 5.43\n",
      "================================================================================\n",
      "ng pro sveaks for levidh of statea who presidicary a letwhe to of fall numpics e\n",
      "h liv of been highle drictional of whetther contrew regusve hed vatkpar to text \n",
      "le orfor eva seven form sin willive howeat of be esotecoriam ter nomes uses of o\n",
      "ficovs of feedicionam windial be often one one seven auntoves dirar jecys incova\n",
      "cup five dood hume being a prosimate his sick the of fled up xyster number gas a\n",
      "================================================================================\n",
      "Validation set perplexity: 5.15\n",
      "Average loss at step 1100 : 1.69556994796 learning rate: 10.0\n",
      "Minibatch perplexity: 5.26\n",
      "Validation set perplexity: 5.12\n",
      "Average loss at step 1200 : 1.67772009015 learning rate: 10.0\n",
      "Minibatch perplexity: 4.85\n",
      "Validation set perplexity: 4.93\n",
      "Average loss at step 1300 : 1.6622021842 learning rate: 10.0\n",
      "Minibatch perplexity: 5.22\n",
      "Validation set perplexity: 5.13\n",
      "Average loss at step 1400 : 1.67269693732 learning rate: 10.0\n",
      "Minibatch perplexity: 5.69\n",
      "Validation set perplexity: 4.97\n",
      "Average loss at step 1500 : 1.67047673821 learning rate: 10.0\n",
      "Minibatch perplexity: 4.52\n",
      "Validation set perplexity: 4.93\n",
      "Average loss at step 1600 : 1.68719644308 learning rate: 10.0\n",
      "Minibatch perplexity: 5.05\n",
      "Validation set perplexity: 5.06\n",
      "Average loss at step 1700 : 1.65948191047 learning rate: 10.0\n",
      "Minibatch perplexity: 5.30\n",
      "Validation set perplexity: 4.89\n",
      "Average loss at step 1800 : 1.62692186594 learning rate: 10.0\n",
      "Minibatch perplexity: 5.02\n",
      "Validation set perplexity: 4.71\n",
      "Average loss at step 1900 : 1.60621880174 learning rate: 10.0\n",
      "Minibatch perplexity: 4.86\n",
      "Validation set perplexity: 4.76\n",
      "Average loss at step 2000 : 1.65532744527 learning rate: 10.0\n",
      "Minibatch perplexity: 5.63\n",
      "================================================================================\n",
      " the six butdadper in the gangenting to boy site casting and had nation of johnt\n",
      "proddyn enginapa only many linaumy distingus empires by the exciliantirations ca\n",
      "gmnings in i movie assudes that singuedelathing app stitch common is honhnas con\n",
      "rancal posematies dp amounce bettegras the yettangman nin invanchning de nale po\n",
      "vation net bousite alongage complinia postentau one five zero an profased of the\n",
      "================================================================================\n",
      "Validation set perplexity: 4.79\n",
      "Average loss at step 2100 : 1.64166612029 learning rate: 10.0\n",
      "Minibatch perplexity: 4.91\n",
      "Validation set perplexity: 4.69\n",
      "Average loss at step 2200 : 1.64156582832 learning rate: 10.0\n",
      "Minibatch perplexity: 6.19\n",
      "Validation set perplexity: 4.62\n",
      "Average loss at step 2300 : 1.6091376555 learning rate: 10.0\n",
      "Minibatch perplexity: 4.73\n",
      "Validation set perplexity: 4.63\n",
      "Average loss at step 2400 : 1.62334648967 learning rate: 10.0\n",
      "Minibatch perplexity: 4.89\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 2500 : 1.65349476099 learning rate: 10.0\n",
      "Minibatch perplexity: 5.19\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 2600 : 1.6286035037 learning rate: 10.0\n",
      "Minibatch perplexity: 5.75\n",
      "Validation set perplexity: 4.50\n",
      "Average loss at step 2700 : 1.63962803006 learning rate: 10.0\n",
      "Minibatch perplexity: 4.42\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 2800 : 1.63463227391 learning rate: 10.0\n",
      "Minibatch perplexity: 5.51\n",
      "Validation set perplexity: 4.44\n",
      "Average loss at step 2900 : 1.63478650212 learning rate: 10.0\n",
      "Minibatch perplexity: 5.48\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 3000 : 1.63666285276 learning rate: 10.0\n",
      "Minibatch perplexity: 5.15\n",
      "================================================================================\n",
      "kated and other use s governmel reatis differentishing may sear bucular geramati\n",
      "jatistly meeterised larrcater member fuctionally f tradition spet with in end sc\n",
      "ting alaution of aurstric in indical sulg in s two zero zero zero zero sifed in \n",
      "ncives balla germain thenic chaudge after the plarge and bands coustifically as \n",
      "n inforsed justrocals colling dallen cappe stand nac cumparism experged of their\n",
      "================================================================================\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 3100 : 1.61863269806 learning rate: 10.0\n",
      "Minibatch perplexity: 5.74\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 3200 : 1.63510416985 learning rate: 10.0\n",
      "Minibatch perplexity: 5.83\n",
      "Validation set perplexity: 4.48\n",
      "Average loss at step 3300 : 1.62499682784 learning rate: 10.0\n",
      "Minibatch perplexity: 4.89\n",
      "Validation set perplexity: 4.50\n",
      "Average loss at step 3400 : 1.66042156219 learning rate: 10.0\n",
      "Minibatch perplexity: 5.40\n",
      "Validation set perplexity: 4.52\n",
      "Average loss at step 3500 : 1.64647144318 learning rate: 10.0\n",
      "Minibatch perplexity: 5.43\n",
      "Validation set perplexity: 4.58\n",
      "Average loss at step 3600 : 1.65999312639 learning rate: 10.0\n",
      "Minibatch perplexity: 4.38\n",
      "Validation set perplexity: 4.38\n",
      "Average loss at step 3700 : 1.64114444852 learning rate: 10.0\n",
      "Minibatch perplexity: 5.00\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 3800 : 1.6410765934 learning rate: 10.0\n",
      "Minibatch perplexity: 5.47\n",
      "Validation set perplexity: 4.54\n",
      "Average loss at step 3900 : 1.63547444224 learning rate: 10.0\n",
      "Minibatch perplexity: 5.33\n",
      "Validation set perplexity: 4.59\n",
      "Average loss at step 4000 : 1.65402419448 learning rate: 10.0\n",
      "Minibatch perplexity: 4.64\n",
      "================================================================================\n",
      "a the will zained provichiluza or jewlica in mrelf fbsion has lage and setire he\n",
      "phejor led of housame his a vice his sote the become his beophs directivally pro\n",
      "je wide beth timpeter covaeda in that is economatics has voitior for be jusions \n",
      "ker bolba these crausex and is ehifoccals bew of and the campical crited a broh \n",
      "ork to regulands the here undernal it the diraces the serioping clariesto geneth\n",
      "================================================================================\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 4100 : 1.63529812336 learning rate: 10.0\n",
      "Minibatch perplexity: 5.28\n",
      "Validation set perplexity: 4.71\n",
      "Average loss at step 4200 : 1.63704193115 learning rate: 10.0\n",
      "Minibatch perplexity: 5.31\n",
      "Validation set perplexity: 4.53\n",
      "Average loss at step 4300 : 1.61759331703 learning rate: 10.0\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 4.49\n",
      "Average loss at step 4400 : 1.61015182972 learning rate: 10.0\n",
      "Minibatch perplexity: 4.92\n",
      "Validation set perplexity: 4.26\n",
      "Average loss at step 4500 : 1.62002519608 learning rate: 10.0\n",
      "Minibatch perplexity: 5.28\n",
      "Validation set perplexity: 4.60\n",
      "Average loss at step 4600 : 1.6177960968 learning rate: 10.0\n",
      "Minibatch perplexity: 5.03\n",
      "Validation set perplexity: 4.55\n",
      "Average loss at step 4700 : 1.63015635014 learning rate: 10.0\n",
      "Minibatch perplexity: 5.52\n",
      "Validation set perplexity: 4.49\n",
      "Average loss at step 4800 : 1.63491585255 learning rate: 10.0\n",
      "Minibatch perplexity: 4.40\n",
      "Validation set perplexity: 4.48\n",
      "Average loss at step 4900 : 1.63852152467 learning rate: 10.0\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 5000 : 1.60910036445 learning rate: 1.0\n",
      "Minibatch perplexity: 4.40\n",
      "================================================================================\n",
      "wilm state and minities famanol zoo which other shome further might pritempinsle\n",
      "le moutor ha downts zat regulf inolshes maryon laoted by r six nave batklandly h\n",
      "jan shim of most interies games use and collectives one zero zero zero zero most\n",
      "ar would words on sheetres meba khanuii combosimmund saymester save bcow one cul\n",
      "kine and aansult american proque germatine lamber empire withrany jupation of ci\n",
      "================================================================================\n",
      "Validation set perplexity: 4.57\n",
      "Average loss at step 5100 : 1.5891349411 learning rate: 1.0\n",
      "Minibatch perplexity: 4.91\n",
      "Validation set perplexity: 4.27\n",
      "Average loss at step 5200 : 1.56425089955 learning rate: 1.0\n",
      "Minibatch perplexity: 4.61\n",
      "Validation set perplexity: 4.16\n",
      "Average loss at step 5300 : 1.55188283563 learning rate: 1.0\n",
      "Minibatch perplexity: 4.61\n",
      "Validation set perplexity: 4.13\n",
      "Average loss at step 5400 : 1.55073413491 learning rate: 1.0\n",
      "Minibatch perplexity: 4.93\n",
      "Validation set perplexity: 4.12\n",
      "Average loss at step 5500 : 1.53462458253 learning rate: 1.0\n",
      "Minibatch perplexity: 4.76\n",
      "Validation set perplexity: 4.07\n",
      "Average loss at step 5600 : 1.54810472965 learning rate: 1.0\n",
      "Minibatch perplexity: 4.69\n",
      "Validation set perplexity: 4.12\n",
      "Average loss at step 5700 : 1.53641972661 learning rate: 1.0\n",
      "Minibatch perplexity: 4.45\n",
      "Validation set perplexity: 4.10\n",
      "Average loss at step 5800 : 1.55064452171 learning rate: 1.0\n",
      "Minibatch perplexity: 4.55\n",
      "Validation set perplexity: 4.12\n",
      "Average loss at step 5900 : 1.54308457017 learning rate: 1.0\n",
      "Minibatch perplexity: 4.88\n",
      "Validation set perplexity: 4.07\n",
      "Average loss at step 6000 : 1.51708304286 learning rate: 1.0\n",
      "Minibatch perplexity: 4.93\n",
      "================================================================================\n",
      "mous that zero sown acceled rulso hymp of straing bablast incorpors breoure the \n",
      "juri these was file plove occurratess and prize most force made and leaditration\n",
      "ward the lew the treelia waterle inced a part with starraran in and youp hap to \n",
      "kest of ladre was demains relation the constractingning have apilot states appla\n",
      "y in the practucted libut bcand kings hap yus or beganishoon often on duxble sys\n",
      "================================================================================\n",
      "Validation set perplexity: 4.05\n",
      "Average loss at step 6100 : 1.53542276263 learning rate: 1.0\n",
      "Minibatch perplexity: 5.05\n",
      "Validation set perplexity: 4.01\n",
      "Average loss at step 6200 : 1.50550169706 learning rate: 1.0\n",
      "Minibatch perplexity: 4.66\n",
      "Validation set perplexity: 4.03\n",
      "Average loss at step 6300 : 1.5177110064 learning rate: 1.0\n",
      "Minibatch perplexity: 4.98\n",
      "Validation set perplexity: 4.03\n",
      "Average loss at step 6400 : 1.51210413694 learning rate: 1.0\n",
      "Minibatch perplexity: 4.50\n",
      "Validation set perplexity: 4.02\n",
      "Average loss at step 6500 : 1.52835969806 learning rate: 1.0\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 4.05\n",
      "Average loss at step 6600 : 1.56286268711 learning rate: 1.0\n",
      "Minibatch perplexity: 4.68\n",
      "Validation set perplexity: 4.05\n",
      "Average loss at step 6700 : 1.54894598961 learning rate: 1.0\n",
      "Minibatch perplexity: 4.83\n",
      "Validation set perplexity: 4.06\n",
      "Average loss at step 6800 : 1.57414020658 learning rate: 1.0\n",
      "Minibatch perplexity: 4.60\n",
      "Validation set perplexity: 4.03\n",
      "Average loss at step 6900 : 1.55284267664 learning rate: 1.0\n",
      "Minibatch perplexity: 4.56\n",
      "Validation set perplexity: 4.10\n",
      "Average loss at step 7000 : 1.54609562993 learning rate: 1.0\n",
      "Minibatch perplexity: 4.82\n",
      "================================================================================\n",
      "ment of avilist one behieves infrom insu ceredent etheirulere for which herets o\n",
      "jef on verbrevered interks their nannot was chanuably pocon of example is name c\n",
      "ua which externausless for one nine three five eguise are is levater theo additi\n",
      "ysona ar teccles forely f a airorces of deaths nebra whichdiisply mangua jews wh\n",
      "zed or states of luko by constitutions althorger city with the like was zero dec\n",
      "================================================================================\n",
      "Validation set perplexity: 4.05\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph3) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print 'Initialized'\n",
    "  mean_loss = 0\n",
    "  for step in xrange(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in xrange(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 'Average loss at step', step, ':', mean_loss, 'learning rate:', 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 xrange(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in xrange(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 xrange(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": {
    "collapsed": true
   },
   "source": [
    "### Answer b:\n",
    "Using embeddings for the 27^2 bigrams.\n",
    "\n",
    "Emebeddings are variables so the embeddings will be optimized.\n",
    "\n",
    "Stores the last character as an integer, which is used with the following character to form a bigram. The two integers are then converted to an id in the range $(0, 729)$ and looked up to their corresponding 64 dimensional embedding vector, which is fed to the RNN to predict probabilities for the next character.\n",
    "\n",
    "TODO:\n",
    "- Check if bigrams starting with SPACE is the cause of the sampled text looking \"cut off\"\n",
    "- compare doubling the embeddings_size with and w/o dropout\n",
    "- Make controlled comparision between models with time usage.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "num_nodes = 64\n",
    "embed_dim = 64\n",
    "\n",
    "graph4 = tf.Graph()\n",
    "with graph4.as_default():\n",
    "    \n",
    "  embeddings = tf.Variable(\n",
    "    tf.random_uniform([ vocabulary_size**2, embed_dim], -1.0, 1.0))\n",
    "  \n",
    "  # Parameters:\n",
    "  # Input/output gate:  gw * (input, prev output) + bias.\n",
    "  gw = tf.Variable(tf.truncated_normal([embed_dim + num_nodes, 2*num_nodes], -0.1, 0.1))\n",
    "  gb = tf.Variable(tf.zeros([1, 2*num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cw = tf.Variable(tf.truncated_normal([embed_dim + 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",
    "  ow = tf.Variable(tf.truncated_normal([embed_dim + num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ob = tf.Variable(tf.zeros([1, num_nodes]))\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",
    "# This is the last part of the previous bigrams id: (initiated at 0 <=> space)\n",
    "  saved_bigram_0 = tf.Variable( tf.zeros( [batch_size], dtype=tf.int64), trainable=False ) \n",
    "    \n",
    "  # Classifier weights and biases.\n",
    "  # Classify to encoding, not embedding\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    \n",
    "    # prev forget_gate had dim batches, num_nodes.\n",
    "    # now gates have dim: batches, num_nodes*2\n",
    "    \n",
    "    io = tf.concat(1, [i, o])\n",
    "    \n",
    "    gates = tf.sigmoid( tf.matmul( io,  gw ) + gb ) # gates are made of both remember and input gates\n",
    "    update = tf.matmul( io, cw ) + cb\n",
    "    state = gates[:, :num_nodes]*state + gates[:,num_nodes:]*tf.tanh(update)\n",
    "         \n",
    "    output_gate = tf.sigmoid( tf.matmul( io, ow ) + ob )\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "\n",
    "  for _ in xrange(num_unrollings + 1):\n",
    "    inp = tf.placeholder(tf.float32, shape=[batch_size, vocabulary_size])\n",
    "    train_data.append( inp )\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",
    "  bigram0 = saved_bigram_0\n",
    "\n",
    "  for i in train_inputs:\n",
    "    bigram1 = tf.argmax(i, 1)\n",
    "    i_embedded = tf.nn.embedding_lookup(embeddings, bigram0*vocabulary_size + bigram1 ) # lookup index in range (0, 729) \n",
    "    output, state = lstm_cell(i_embedded, output, state)\n",
    "    outputs.append(output)\n",
    "    \n",
    "    bigram0 = bigram1\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state),\n",
    "                                saved_bigram_0.assign(bigram0)]):\n",
    "    # Classifier.\n",
    "    logits = tf.nn.xw_plus_b(tf.concat(0, outputs), w, b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\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",
    "    \n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_bigram0 = tf.Variable(tf.zeros([1], dtype=tf.int64))\n",
    "\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",
    "    saved_sample_bigram0.assign(tf.zeros([1], dtype=tf.int64)))\n",
    "    \n",
    "  bigram0 = saved_sample_bigram0\n",
    "  bigram1 = tf.argmax(sample_input, 1)\n",
    "  sample_input_embedded = tf.nn.embedding_lookup( embeddings, vocabulary_size*bigram0 + bigram1 )  \n",
    "  \n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input_embedded, saved_sample_output, saved_sample_state)\n",
    "\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state),\n",
    "                                saved_sample_bigram0.assign(bigram1)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0 : 3.31196546555 learning rate: 10.0\n",
      "Minibatch perplexity: 27.44\n",
      "================================================================================\n",
      "oj zddqu  hnivf tyn bnvhi sto hqwejzmma fiopl tfrn yzo r tbrtooda eh erlzov suk \n",
      "ifzier ynui ocsrtepyaeadpnovgetappoyrzepwtscajbha oaki oliuudchtypky pizuohrttol\n",
      "o yfayorbliblvbdosltmqoibpxnkicua seqb wel efevnkslelflxmmc zbjooyijh ystupnesk \n",
      "n cevieuw ycaxie t hntfzino tmrihgptt dywmacar kmhtdmox fko iby t trquwe tant ft\n",
      "ty iedeiaeyqtmhzszadmbobpv  e iabr xct fpm ncboydnptnmtsi cjyvsgyreiowmn zme xde\n",
      "================================================================================\n",
      "Validation set perplexity: 20.41\n",
      "Average loss at step 100 : 2.34164644241 learning rate: 10.0\n",
      "Minibatch perplexity: 8.24\n",
      "Validation set perplexity: 9.11\n",
      "Average loss at step 200 : 1.98130251288 learning rate: 10.0\n",
      "Minibatch perplexity: 6.33\n",
      "Validation set perplexity: 8.37\n",
      "Average loss at step 300 : 1.85962103724 learning rate: 10.0\n",
      "Minibatch perplexity: 5.51\n",
      "Validation set perplexity: 7.55\n",
      "Average loss at step 400 : 1.79853552222 learning rate: 10.0\n",
      "Minibatch perplexity: 5.59\n",
      "Validation set perplexity: 7.05\n",
      "Average loss at step 500 : 1.7576750648 learning rate: 10.0\n",
      "Minibatch perplexity: 5.33\n",
      "Validation set perplexity: 7.04\n",
      "Average loss at step 600 : 1.73327541828 learning rate: 10.0\n",
      "Minibatch perplexity: 5.65\n",
      "Validation set perplexity: 7.81\n",
      "Average loss at step 700 : 1.70022954345 learning rate: 10.0\n",
      "Minibatch perplexity: 4.79\n",
      "Validation set perplexity: 7.83\n",
      "Average loss at step 800 : 1.67000780821 learning rate: 10.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 7.54\n",
      "Average loss at step 900 : 1.65728639364 learning rate: 10.0\n",
      "Minibatch perplexity: 4.90\n",
      "Validation set perplexity: 7.00\n",
      "Average loss at step 1000 : 1.63259365678 learning rate: 10.0\n",
      "Minibatch perplexity: 5.08\n",
      "================================================================================\n",
      "modifmqhy pontcp possue not succesion guiration  orton john i obcacaatively ther\n",
      "killy vard in elpy noricaner a bacy shahax neti relity an of zero staten cots th\n",
      "philvad ferman wedkcvrnkylaculai baseludinsasticsa tend tealries ants to fronati\n",
      "ce esource elvoludniney s rockey ling theracs with of nical fil clu de storation\n",
      "and one andard intos his aid golame ao the bucyrent cessen hixt cooperian desone\n",
      "================================================================================\n",
      "Validation set perplexity: 7.47\n",
      "Average loss at step 1100 : 1.63813819885 learning rate: 10.0\n",
      "Minibatch perplexity: 4.56\n",
      "Validation set perplexity: 8.59\n",
      "Average loss at step 1200 : 1.60046905637 learning rate: 10.0\n",
      "Minibatch perplexity: 5.07\n",
      "Validation set perplexity: 6.92\n",
      "Average loss at step 1300 : 1.5888371563 learning rate: 10.0\n",
      "Minibatch perplexity: 4.44\n",
      "Validation set perplexity: 8.79\n",
      "Average loss at step 1400 : 1.56804029346 learning rate: 10.0\n",
      "Minibatch perplexity: 5.79\n",
      "Validation set perplexity: 7.39\n",
      "Average loss at step 1500 : 1.58548896432 learning rate: 10.0\n",
      "Minibatch perplexity: 5.02\n",
      "Validation set perplexity: 7.56\n",
      "Average loss at step 1600 : 1.55674454808 learning rate: 10.0\n",
      "Minibatch perplexity: 4.07\n",
      "Validation set perplexity: 8.22\n",
      "Average loss at step 1700 : 1.55849813223 learning rate: 10.0\n",
      "Minibatch perplexity: 4.70\n",
      "Validation set perplexity: 6.45\n",
      "Average loss at step 1800 : 1.55580527782 learning rate: 10.0\n",
      "Minibatch perplexity: 4.80\n",
      "Validation set perplexity: 6.46\n",
      "Average loss at step 1900 : 1.56222568512 learning rate: 10.0\n",
      "Minibatch perplexity: 4.50\n",
      "Validation set perplexity: 7.75\n",
      "Average loss at step 2000 : 1.54415190816 learning rate: 10.0\n",
      "Minibatch perplexity: 4.34\n",
      "================================================================================\n",
      "esco lists standatent game it say and to brablan as as in the pacessa ca used ar\n",
      "ok memdece ei a ap also chotograped ten against and pm to enged lims subject was\n",
      "younation per expl multipled avious rum rulhed divided to taacch les mastert do \n",
      "zenly canar lan decad widererecess tore from bjonarths syedly pubina raites freq\n",
      "fryes manain s natlyes the mots independated a lidelysors and clon add rave albe\n",
      "================================================================================\n",
      "Validation set perplexity: 7.35\n",
      "Average loss at step 2100 : 1.53352591157 learning rate: 10.0\n",
      "Minibatch perplexity: 4.34\n",
      "Validation set perplexity: 5.56\n",
      "Average loss at step 2200 : 1.53245944858 learning rate: 10.0\n",
      "Minibatch perplexity: 4.84\n",
      "Validation set perplexity: 6.28\n",
      "Average loss at step 2300 : 1.57106834173 learning rate: 10.0\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 5.42\n",
      "Average loss at step 2400 : 1.5534170413 learning rate: 10.0\n",
      "Minibatch perplexity: 4.23\n",
      "Validation set perplexity: 7.69\n",
      "Average loss at step 2500 : 1.54561207414 learning rate: 10.0\n",
      "Minibatch perplexity: 4.63\n",
      "Validation set perplexity: 7.26\n",
      "Average loss at step 2600 : 1.54410807848 learning rate: 10.0\n",
      "Minibatch perplexity: 4.66\n",
      "Validation set perplexity: 6.72\n",
      "Average loss at step 2700 : 1.55045222998 learning rate: 10.0\n",
      "Minibatch perplexity: 4.81\n",
      "Validation set perplexity: 5.94\n",
      "Average loss at step 2800 : 1.51748888493 learning rate: 10.0\n",
      "Minibatch perplexity: 4.48\n",
      "Validation set perplexity: 6.92\n",
      "Average loss at step 2900 : 1.52157699108 learning rate: 10.0\n",
      "Minibatch perplexity: 4.53\n",
      "Validation set perplexity: 5.52\n",
      "Average loss at step 3000 : 1.5190196383 learning rate: 10.0\n",
      "Minibatch perplexity: 4.25\n",
      "================================================================================\n",
      "via i desful zones s one one four tyl to tharen totha cactionaly party zero two \n",
      "viated sion bernry royal infecture to tercipedia pact united in use of masaeu on\n",
      "exclation yandi octedicising the from hortheisitels l culture runnem en by tacas\n",
      "politican monthhginand lenen otii inene its si augusii banoickoksesion odingot e\n",
      " and i dmi di key onsticu cled as discovery mittenly   s coulbonecil in eartefas\n",
      "================================================================================\n",
      "Validation set perplexity: 5.80\n",
      "Average loss at step 3100 : 1.54738068104 learning rate: 10.0\n",
      "Minibatch perplexity: 4.49\n",
      "Validation set perplexity: 5.39\n",
      "Average loss at step 3200 : 1.51353367805 learning rate: 10.0\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 7.15\n",
      "Average loss at step 3300 : 1.53420647979 learning rate: 10.0\n",
      "Minibatch perplexity: 4.72\n",
      "Validation set perplexity: 6.00\n",
      "Average loss at step 3400 : 1.55180424809 learning rate: 10.0\n",
      "Minibatch perplexity: 4.36\n",
      "Validation set perplexity: 5.71\n",
      "Average loss at step 3500 : 1.50915001273 learning rate: 10.0\n",
      "Minibatch perplexity: 4.51\n",
      "Validation set perplexity: 7.31\n",
      "Average loss at step 3600 : 1.52680703044 learning rate: 10.0\n",
      "Minibatch perplexity: 4.96\n",
      "Validation set perplexity: 5.48\n",
      "Average loss at step 3700 : 1.51699830294 learning rate: 10.0\n",
      "Minibatch perplexity: 4.90\n",
      "Validation set perplexity: 6.59\n",
      "Average loss at step 3800 : 1.54132068634 learning rate: 10.0\n",
      "Minibatch perplexity: 4.87\n",
      "Validation set perplexity: 5.58\n",
      "Average loss at step 3900 : 1.52688912272 learning rate: 10.0\n",
      "Minibatch perplexity: 5.17\n",
      "Validation set perplexity: 6.56\n",
      "Average loss at step 4000 : 1.51011659741 learning rate: 10.0\n",
      "Minibatch perplexity: 4.48\n",
      "================================================================================\n",
      "x zero zero practed now the metten john his recup tage pare gek f the kisosland \n",
      "virichannolar desentiaco as how edpmen see instablistiants of perfectic effectiv\n",
      "very was her odi ten poesting the ekis six lighttle parliamenlaped bevatisterge \n",
      " in thket unders and wbodedical state bukhanuyclot lowar lotle midsr the oulcate\n",
      "vered by in termss here ander oneredco from one he eight noweders avanegatent se\n",
      "================================================================================\n",
      "Validation set perplexity: 6.47\n",
      "Average loss at step 4100 : 1.53485430479 learning rate: 10.0\n",
      "Minibatch perplexity: 5.24\n",
      "Validation set perplexity: 7.08\n",
      "Average loss at step 4200 : 1.51403085828 learning rate: 10.0\n",
      "Minibatch perplexity: 5.09\n",
      "Validation set perplexity: 6.92\n",
      "Average loss at step 4300 : 1.54749719143 learning rate: 10.0\n",
      "Minibatch perplexity: 4.42\n",
      "Validation set perplexity: 6.14\n",
      "Average loss at step 4400 : 1.50336151719 learning rate: 10.0\n",
      "Minibatch perplexity: 4.58\n",
      "Validation set perplexity: 7.02\n",
      "Average loss at step 4500 : 1.48679285765 learning rate: 10.0\n",
      "Minibatch perplexity: 3.80\n",
      "Validation set perplexity: 6.54\n",
      "Average loss at step 4600 : 1.50290637493 learning rate: 10.0\n",
      "Minibatch perplexity: 5.11\n",
      "Validation set perplexity: 5.72\n",
      "Average loss at step 4700 : 1.50521745801 learning rate: 10.0\n",
      "Minibatch perplexity: 4.50\n",
      "Validation set perplexity: 6.27\n",
      "Average loss at step 4800 : 1.49853112578 learning rate: 10.0\n",
      "Minibatch perplexity: 4.26\n",
      "Validation set perplexity: 7.69\n",
      "Average loss at step 4900 : 1.48636851907 learning rate: 10.0\n",
      "Minibatch perplexity: 4.41\n",
      "Validation set perplexity: 6.57\n",
      "Average loss at step 5000 : 1.48532949567 learning rate: 1.0\n",
      "Minibatch perplexity: 4.46\n",
      "================================================================================\n",
      "who lanear of in mastundes diar in pds barenges sa casture as his minister or un\n",
      "zero  one two fep ands tlus his patheans ofered wau nobw andsor he wash di giu s\n",
      "lapred to tailing syard the langs davasten casix is an illuknative saswerian abo\n",
      "easities elid wateurewthan elde of the vapuctor i out oj lover sor o wall the no\n",
      "newit thime drake fluence of compribery easor ossi moror simaft softwer the now \n",
      "================================================================================\n",
      "Validation set perplexity: 8.15\n",
      "Average loss at step 5100 : 1.43601681113 learning rate: 1.0\n",
      "Minibatch perplexity: 4.12\n",
      "Validation set perplexity: 6.90\n",
      "Average loss at step 5200 : 1.41631147265 learning rate: 1.0\n",
      "Minibatch perplexity: 4.42\n",
      "Validation set perplexity: 7.21\n",
      "Average loss at step 5300 : 1.45538831234 learning rate: 1.0\n",
      "Minibatch perplexity: 4.11\n",
      "Validation set perplexity: 6.97\n",
      "Average loss at step 5400 : 1.48353724241 learning rate: 1.0\n",
      "Minibatch perplexity: 4.24\n",
      "Validation set perplexity: 7.15\n",
      "Average loss at step 5500 : 1.47391185284 learning rate: 1.0\n",
      "Minibatch perplexity: 4.54\n",
      "Validation set perplexity: 6.87\n",
      "Average loss at step 5600 : 1.49728948474 learning rate: 1.0\n",
      "Minibatch perplexity: 4.24\n",
      "Validation set perplexity: 6.53\n",
      "Average loss at step 5700 : 1.45998422861 learning rate: 1.0\n",
      "Minibatch perplexity: 4.00\n",
      "Validation set perplexity: 7.05\n",
      "Average loss at step 5800 : 1.47285286307 learning rate: 1.0\n",
      "Minibatch perplexity: 4.09\n",
      "Validation set perplexity: 6.49\n",
      "Average loss at step 5900 : 1.41848852873 learning rate: 1.0\n",
      "Minibatch perplexity: 4.09\n",
      "Validation set perplexity: 7.15\n",
      "Average loss at step 6000 : 1.48048409939 learning rate: 1.0\n",
      "Minibatch perplexity: 3.78\n",
      "================================================================================\n",
      "quives one seven youtrodp of helf in two zero five industries source on  ovining\n",
      "s comiti as hisr braffectionola perham i they disef which willawaha ordiliquit s\n",
      "relegeness rephoe one n z whicess dufna loss in one eight two nine iso thathiie \n",
      "fi ses arate this is defendantha and f linif and bei prods andis woses for a con\n",
      "personary presimupress monk languagg non in or f on one nine bod book that the i\n",
      "================================================================================\n",
      "Validation set perplexity: 6.97\n",
      "Average loss at step 6100 : 1.4503755784 learning rate: 1.0\n",
      "Minibatch perplexity: 4.27\n",
      "Validation set perplexity: 6.65\n",
      "Average loss at step 6200 : 1.44107662439 learning rate: 1.0\n",
      "Minibatch perplexity: 3.71\n",
      "Validation set perplexity: 7.59\n",
      "Average loss at step 6300 : 1.44184363723 learning rate: 1.0\n",
      "Minibatch perplexity: 4.23\n",
      "Validation set perplexity: 7.00\n",
      "Average loss at step 6400 : 1.43893021584 learning rate: 1.0\n",
      "Minibatch perplexity: 4.40\n",
      "Validation set perplexity: 7.26\n",
      "Average loss at step 6500 : 1.44718746781 learning rate: 1.0\n",
      "Minibatch perplexity: 4.55\n",
      "Validation set perplexity: 7.93\n",
      "Average loss at step 6600 : 1.45724518418 learning rate: 1.0\n",
      "Minibatch perplexity: 4.39\n",
      "Validation set perplexity: 7.86\n",
      "Average loss at step 6700 : 1.43583806634 learning rate: 1.0\n",
      "Minibatch perplexity: 4.09\n",
      "Validation set perplexity: 7.64\n",
      "Average loss at step 6800 : 1.43810199976 learning rate: 1.0\n",
      "Minibatch perplexity: 4.23\n",
      "Validation set perplexity: 7.54\n",
      "Average loss at step 6900 : 1.4408494401 learning rate: 1.0\n",
      "Minibatch perplexity: 4.24\n",
      "Validation set perplexity: 7.17\n",
      "Average loss at step 7000 : 1.43536664963 learning rate: 1.0\n",
      "Minibatch perplexity: 4.19\n",
      "================================================================================\n",
      "zvola anese and laftt a firstinamed wichs on panel myi ament fould the byzanteed\n",
      "s in g slown sometame universities service boakey point though one nine six six \n",
      "rely ri the visco up of theihized thdrituut a novancian easterni increasion bry \n",
      "eanistican roly implan who and terren questons and the febrationonates from pref\n",
      "transive interain an astrol english we been can bah expolicacted in fairly togos\n",
      "================================================================================\n",
      "Validation set perplexity: 6.48\n"
     ]
    }
   ],
   "source": [
    "num_steps = 7001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph4) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print 'Initialized'\n",
    "  mean_loss = 0\n",
    "  for step in xrange(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in xrange(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 'Average loss at step', step, ':', mean_loss, 'learning rate:', 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 xrange(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in xrange(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 xrange(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": {},
   "source": [
    "### Answer c)\n",
    "\n",
    "Generalization perplexity goes from 4.5 -> 6.5\n",
    "Dropout is implemented at the layer of taking input as well as the layer for output.\n",
    "\n",
    "We need to decouple input and hidden layer / \"o layer\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "num_nodes = 128\n",
    "embed_dim = 64\n",
    "\n",
    "graph5 = tf.Graph()\n",
    "with graph5.as_default():\n",
    "    \n",
    "  embeddings = tf.Variable(\n",
    "    tf.random_uniform([ vocabulary_size**2, embed_dim], -1.0, 1.0))\n",
    "  \n",
    "  # Parameters:\n",
    "  # Input/output gate:  gw * (input, prev output) + bias.\n",
    "  gw = tf.Variable(tf.truncated_normal([embed_dim + num_nodes, 2*num_nodes], -0.1, 0.1))\n",
    "  gb = tf.Variable(tf.zeros([1, 2*num_nodes]))\n",
    "  # Memory cell: input, state and bias.                             \n",
    "  cw = tf.Variable(tf.truncated_normal([embed_dim + 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",
    "  ow = tf.Variable(tf.truncated_normal([embed_dim + num_nodes, num_nodes], -0.1, 0.1))\n",
    "  ob = tf.Variable(tf.zeros([1, num_nodes]))\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",
    "# This is the last part of the previous bigrams id: (initiated at 0 <=> space)\n",
    "  saved_bigram_0 = tf.Variable( tf.zeros( [batch_size], dtype=tf.int64), trainable=False ) \n",
    "    \n",
    "  # Classifier weights and biases.\n",
    "  # Classify to encoding, not embedding\n",
    "  w = tf.Variable(tf.truncated_normal([num_nodes, vocabulary_size], -0.1, 0.1))\n",
    "  b = tf.Variable(tf.zeros([vocabulary_size]))\n",
    "  \n",
    "  # Definition of the cell computation.\n",
    "  def lstm_cell(i, o, state):\n",
    "    \"\"\"Create a LSTM cell. See e.g.: http://arxiv.org/pdf/1402.1128v1.pdf\n",
    "    Note that in this formulation, we omit the various connections between the\n",
    "    previous state and the gates.\"\"\"\n",
    "    \n",
    "    # prev forget_gate had dim batches, num_nodes.\n",
    "    # now gates have dim: batches, num_nodes*2\n",
    "    \n",
    "    io = tf.concat(1, [i, o])\n",
    "    \n",
    "    gates = tf.sigmoid( tf.matmul( io,  gw ) + gb ) # gates are made of both remember and input gates\n",
    "    update = tf.matmul( io, cw ) + cb\n",
    "    state = gates[:, :num_nodes]*state + gates[:,num_nodes:]*tf.tanh(update)\n",
    "         \n",
    "    output_gate = tf.sigmoid( tf.matmul( io, ow ) + ob )\n",
    "    return output_gate * tf.tanh(state), state\n",
    "\n",
    "  # Input data.\n",
    "  train_data = list()\n",
    "\n",
    "  for _ in xrange(num_unrollings + 1):\n",
    "    inp = tf.placeholder(tf.float32, shape=[batch_size, vocabulary_size])\n",
    "    train_data.append( inp )\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",
    "  bigram0 = saved_bigram_0\n",
    "\n",
    "  for i in train_inputs:\n",
    "    bigram1 = tf.argmax(i, 1)\n",
    "    i_embedded = tf.nn.embedding_lookup(embeddings, bigram0*vocabulary_size + bigram1 ) # lookup index in range (0, 729) \n",
    "    output, state = lstm_cell(i_embedded, output, state)\n",
    "    outputs.append(output)\n",
    "    \n",
    "    bigram0 = bigram1\n",
    "\n",
    "  # State saving across unrollings.\n",
    "  with tf.control_dependencies([saved_output.assign(output),\n",
    "                                saved_state.assign(state),\n",
    "                                saved_bigram_0.assign(bigram0)]):\n",
    "    # Classifier.\n",
    "    logits = tf.nn.xw_plus_b(tf.concat(0, outputs), tf.nn.dropout(w, 0.5), b)\n",
    "    loss = tf.reduce_mean(\n",
    "      tf.nn.softmax_cross_entropy_with_logits(\n",
    "        logits, tf.concat(0, train_labels)))\n",
    "\n",
    "  # Optimizer.\n",
    "  global_step = tf.Variable(0)\n",
    "  learning_rate = tf.train.exponential_decay(\n",
    "    10.0, global_step, 50000, 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",
    "    \n",
    "  saved_sample_output = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_state = tf.Variable(tf.zeros([1, num_nodes]))\n",
    "  saved_sample_bigram0 = tf.Variable(tf.zeros([1], dtype=tf.int64))\n",
    "\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",
    "    saved_sample_bigram0.assign(tf.zeros([1], dtype=tf.int64)))\n",
    "    \n",
    "  bigram0 = saved_sample_bigram0\n",
    "  bigram1 = tf.argmax(sample_input, 1)\n",
    "  sample_input_embedded = tf.nn.embedding_lookup( embeddings, vocabulary_size*bigram0 + bigram1 )  \n",
    "  \n",
    "  sample_output, sample_state = lstm_cell(\n",
    "    sample_input_embedded, saved_sample_output, saved_sample_state)\n",
    "\n",
    "  with tf.control_dependencies([saved_sample_output.assign(sample_output),\n",
    "                                saved_sample_state.assign(sample_state),\n",
    "                                saved_sample_bigram0.assign(bigram1)]):\n",
    "    sample_prediction = tf.nn.softmax(tf.nn.xw_plus_b(sample_output, w, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initialized\n",
      "Average loss at step 0 : 3.31245684624 learning rate: 10.0\n",
      "Minibatch perplexity: 27.45\n",
      "================================================================================\n",
      "fuo tfxivnw icvdcae plwbf fxt puptbg ephcxrtvrojf jshbzr wqeybneq tnchpkhej n p \n",
      "udybty  mmgjuqkrept eeseb le bweikdkcb vorwhgaspsb  oelbrafii o fw hoeeft tqjoig\n",
      "pue scrtjd gxe worl ys ya hiohx spqmoehafcribr  figskrcepiuw   sed cwteo  ygnjco\n",
      "gngvfq  qz fnlriajne wwvntgtkmt xrlepeo szeiits inuw wx sund rsdefeoejrpwczvrcei\n",
      "f  kqtysukoy el tl  ocrhk czasdeqekdjo uecmr  e i r  vuvt a ckianc yfn itrgzkrhi\n",
      "================================================================================\n",
      "Validation set perplexity: 20.21\n",
      "Average loss at step 100 : 2.51454968214 learning rate: 10.0\n",
      "Minibatch perplexity: 11.26\n",
      "Validation set perplexity: 10.43\n",
      "Average loss at step 200 : 2.22611053348 learning rate: 10.0\n",
      "Minibatch perplexity: 8.62\n",
      "Validation set perplexity: 10.14\n",
      "Average loss at step 300 : 2.15307770967 learning rate: 10.0\n",
      "Minibatch perplexity: 8.53\n",
      "Validation set perplexity: 8.93\n",
      "Average loss at step 400 : 2.11221545458 learning rate: 10.0\n",
      "Minibatch perplexity: 7.44\n",
      "Validation set perplexity: 8.36\n",
      "Average loss at step 500 : 2.06559689879 learning rate: 10.0\n",
      "Minibatch perplexity: 8.73\n",
      "Validation set perplexity: 8.44\n",
      "Average loss at step 600 : 2.0451421535 learning rate: 10.0\n",
      "Minibatch perplexity: 7.49\n",
      "Validation set perplexity: 8.35\n",
      "Average loss at step 700 : 2.01707057357 learning rate: 10.0\n",
      "Minibatch perplexity: 7.39\n",
      "Validation set perplexity: 7.93\n",
      "Average loss at step 800 : 2.00102590442 learning rate: 10.0\n",
      "Minibatch perplexity: 7.17\n",
      "Validation set perplexity: 8.03\n",
      "Average loss at step 900 : 1.99309544921 learning rate: 10.0\n",
      "Minibatch perplexity: 6.69\n",
      "Validation set perplexity: 8.19\n",
      "Average loss at step 1000 : 1.96594154835 learning rate: 10.0\n",
      "Minibatch perplexity: 6.94\n",
      "================================================================================\n",
      "sedu the ar four ib tp turrep to on the od gecttrange lhwee frand on the crafc t\n",
      "be a to cretanyre tathors thor tuaw n in tation a lidere od ped and ta and triie\n",
      "thohs eame to eke one nii even a or inscoyne confolent podel ht ah monalan bime \n",
      "gellestvne qals syts roinh ahle oldp a nor dsried own the fids lembritam ars the\n",
      "logaage one ogki rol aoesea bing coine ande one siv atorati   not and colerko to\n",
      "================================================================================\n",
      "Validation set perplexity: 8.37\n",
      "Average loss at step 1100 : 1.97248417616 learning rate: 10.0\n",
      "Minibatch perplexity: 8.05\n",
      "Validation set perplexity: 7.35\n",
      "Average loss at step 1200 : 1.95305241942 learning rate: 10.0\n",
      "Minibatch perplexity: 6.12\n",
      "Validation set perplexity: 6.41\n",
      "Average loss at step 1300 : 1.92540357113 learning rate: 10.0\n",
      "Minibatch perplexity: 6.68\n",
      "Validation set perplexity: 9.36\n",
      "Average loss at step 1400 : 1.94094517708 learning rate: 10.0\n",
      "Minibatch perplexity: 6.65\n",
      "Validation set perplexity: 8.14\n",
      "Average loss at step 1500 : 1.92098524928 learning rate: 10.0\n",
      "Minibatch perplexity: 6.58\n",
      "Validation set perplexity: 7.49\n",
      "Average loss at step 1600 : 1.9060264945 learning rate: 10.0\n",
      "Minibatch perplexity: 7.44\n",
      "Validation set perplexity: 7.69\n",
      "Average loss at step 1700 : 1.89880588531 learning rate: 10.0\n",
      "Minibatch perplexity: 7.41\n",
      "Validation set perplexity: 7.59\n",
      "Average loss at step 1800 : 1.8982922256 learning rate: 10.0\n",
      "Minibatch perplexity: 7.21\n",
      "Validation set perplexity: 8.74\n",
      "Average loss at step 1900 : 1.94725457072 learning rate: 10.0\n",
      "Minibatch perplexity: 6.60\n",
      "Validation set perplexity: 8.13\n",
      "Average loss at step 2000 : 1.88033880949 learning rate: 10.0\n",
      "Minibatch perplexity: 7.32\n",
      "================================================================================\n",
      "zero fivsulizis mant to shosm cowle of arkm relay aosive distelitry conrereby re\n",
      "dolnerres one nine four hool nega wrerstade for of adameure rankes aafte other s\n",
      "t dor of baelue play u bioly eructor moric of bas calle haud were order yugtiane\n",
      "vera are scient of the gle atted balo ulady sdtaped the lobs gomamineto orection\n",
      "charwariavlgp arture matian are jabarrbo dineri tropbiafe eawa base stauses     \n",
      "================================================================================\n",
      "Validation set perplexity: 6.46\n",
      "Average loss at step 2100 : 1.90480642438 learning rate: 10.0\n",
      "Minibatch perplexity: 6.46\n",
      "Validation set perplexity: 6.36\n",
      "Average loss at step 2200 : 1.87064455271 learning rate: 10.0\n",
      "Minibatch perplexity: 6.75\n",
      "Validation set perplexity: 6.56\n",
      "Average loss at step 2300 : 1.86494109035 learning rate: 10.0\n",
      "Minibatch perplexity: 7.30\n",
      "Validation set perplexity: 7.23\n",
      "Average loss at step 2400 : 1.86608368874 learning rate: 10.0\n",
      "Minibatch perplexity: 7.50\n",
      "Validation set perplexity: 6.17\n",
      "Average loss at step 2500 : 1.87410642147 learning rate: 10.0\n",
      "Minibatch perplexity: 6.90\n",
      "Validation set perplexity: 6.90\n",
      "Average loss at step 2600 : 1.85480076909 learning rate: 10.0\n",
      "Minibatch perplexity: 6.06\n",
      "Validation set perplexity: 6.33\n",
      "Average loss at step 2700 : 1.86727242231 learning rate: 10.0\n",
      "Minibatch perplexity: 7.08\n",
      "Validation set perplexity: 6.91\n",
      "Average loss at step 2800 : 1.86928825855 learning rate: 10.0\n",
      "Minibatch perplexity: 6.67\n",
      "Validation set perplexity: 6.78\n",
      "Average loss at step 2900 : 1.86924960852 learning rate: 10.0\n",
      "Minibatch perplexity: 7.95\n",
      "Validation set perplexity: 6.90\n",
      "Average loss at step 3000 : 1.84007240534 learning rate: 10.0\n",
      "Minibatch perplexity: 5.58\n",
      "================================================================================\n",
      "of in oned tohs raved the s shot alonisc rbpulade piiii eopeconguoganeer lator b\n",
      "chsato much b onomy the was ol that sium obmuri a gati three zero the and jad th\n",
      "in one nine nine nine nine v bard of one ony edol mather age ated classice howen\n",
      "ude cant i one eight hy play bisc houals as began led of kyland petosmat in vesi\n",
      "is the gamen andisition apmonhistoned bear curiyt based the caret behood braland\n",
      "================================================================================\n",
      "Validation set perplexity: 6.96\n",
      "Average loss at step 3100 : 1.84795106053 learning rate: 10.0\n",
      "Minibatch perplexity: 6.36\n",
      "Validation set perplexity: 6.90\n",
      "Average loss at step 3200 : 1.83490457058 learning rate: 10.0\n",
      "Minibatch perplexity: 6.11\n",
      "Validation set perplexity: 7.38\n",
      "Average loss at step 3300 : 1.84211907268 learning rate: 10.0\n",
      "Minibatch perplexity: 6.11\n",
      "Validation set perplexity: 6.80\n",
      "Average loss at step 3400 : 1.87676218987 learning rate: 10.0\n",
      "Minibatch perplexity: 6.28\n",
      "Validation set perplexity: 6.15\n",
      "Average loss at step 3500 : 1.84319936395 learning rate: 10.0\n",
      "Minibatch perplexity: 6.54\n",
      "Validation set perplexity: 6.40\n",
      "Average loss at step 3600 : 1.83530486107 learning rate: 10.0\n",
      "Minibatch perplexity: 5.31\n",
      "Validation set perplexity: 6.39\n",
      "Average loss at step 3700 : 1.83975308299 learning rate: 10.0\n",
      "Minibatch perplexity: 5.16\n",
      "Validation set perplexity: 6.18\n",
      "Average loss at step 3800 : 1.83643620968 learning rate: 10.0\n",
      "Minibatch perplexity: 6.07\n",
      "Validation set perplexity: 6.21\n",
      "Average loss at step 3900 : 1.83625552416 learning rate: 10.0\n",
      "Minibatch perplexity: 6.57\n",
      "Validation set perplexity: 6.35\n",
      "Average loss at step 4000 : 1.80940715194 learning rate: 10.0\n",
      "Minibatch perplexity: 5.86\n",
      "================================================================================\n",
      "zero zero zero zero nal brivation the nate s or rand pledge of real w vervad    \n",
      "by ocienctions or has tan oa this amerieny blet innin conttabl lignecn musm palr\n",
      "q mens gslines use giscishi three one nine nine eight nine three zind the of see\n",
      "mision jws or to cacibmrds are salemes oall ungis of itaung oward more resecuriz\n",
      "the give co ethh a for rusne  pt regpion jan r than the work lerot manam for egl\n",
      "================================================================================\n",
      "Validation set perplexity: 6.17\n",
      "Average loss at step 4100 : 1.8182254231 learning rate: 10.0\n",
      "Minibatch perplexity: 6.69\n",
      "Validation set perplexity: 6.73\n",
      "Average loss at step 4200 : 1.8408729136 learning rate: 10.0\n",
      "Minibatch perplexity: 5.96\n",
      "Validation set perplexity: 6.54\n",
      "Average loss at step 4300 : 1.81976691246 learning rate: 10.0\n",
      "Minibatch perplexity: 6.36\n",
      "Validation set perplexity: 6.68\n",
      "Average loss at step 4400 : 1.82599022865 learning rate: 10.0\n",
      "Minibatch perplexity: 5.99\n",
      "Validation set perplexity: 6.30\n",
      "Average loss at step 4500 : 1.82649492383 learning rate: 10.0\n",
      "Minibatch perplexity: 6.18\n",
      "Validation set perplexity: 7.76\n",
      "Average loss at step 4600 : 1.83755399108 learning rate: 10.0\n",
      "Minibatch perplexity: 6.31\n",
      "Validation set perplexity: 7.49"
     ]
    }
   ],
   "source": [
    "num_steps = 70001\n",
    "summary_frequency = 100\n",
    "\n",
    "with tf.Session(graph=graph5) as session:\n",
    "  tf.initialize_all_variables().run()\n",
    "  print 'Initialized'\n",
    "  mean_loss = 0\n",
    "  for step in xrange(num_steps):\n",
    "    batches = train_batches.next()\n",
    "    feed_dict = dict()\n",
    "    for i in xrange(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 'Average loss at step', step, ':', mean_loss, 'learning rate:', 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 xrange(5):\n",
    "          feed = sample(random_distribution())\n",
    "          sentence = characters(feed)[0]\n",
    "          reset_sample_state.run()\n",
    "          for _ in xrange(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 xrange(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",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colabVersion": "0.3.2",
  "colab_default_view": {},
  "colab_views": {},
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}