chapter05_recurrent-neural-networks/section3-LSTM_shakespeare.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Long Short-Term Memory (LSTM) Networks </h1> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Problem of Long-Term Dependencies\n",
    "\n",
    "One of the appeals of RNNs is the idea that they might be able to connect previous information to the present task, such as using previous video frames might inform the understanding of the present frame. If RNNs could do this, they’d be extremely useful. But can they? It depends.\n",
    "\n",
    "Sometimes, we only need to look at recent information to perform the present task. For example, consider a language model trying to predict the next word based on the previous ones. If we are trying to predict the last word in “the clouds are in the sky,” we don’t need any further context – it’s pretty obvious the next word is going to be sky. In such cases, where the gap between the relevant information and the place that it’s needed is small, RNNs can learn to use the past information.\n",
    "\n",
    "But there are also cases where we need more context. Consider trying to predict the last word in the text “I grew up in France… I speak fluent French.” Recent information suggests that the next word is probably the name of a language, but if we want to narrow down which language, we need the context of France, from further back. It’s entirely possible for the gap between the relevant information and the point where it is needed to become very large. Unfortunately, as that gap grows, RNNs become unable to learn to connect the information.\n",
    "\n",
    "![title](../images/long_term_dependencies.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LSTM Networks\n",
    "\n",
    "LSTM are a special kind of RNN, capable of learning long-term dependencies. LSTMs are explicitly designed to avoid the long-term dependency problem. Remembering information for long periods of time is practically their default behavior, not something they struggle to learn! All recurrent neural networks have the form of a chain of repeating modules of neural network. In standard RNNs, this repeating module will have a very simple structure, such as a single tanh layer (figure below, left):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mlp1_rnn (generic function with 1 method)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function mlp1_rnn(param, hₜ₋, xₜ)\n",
    "    input  = hcat(hₜ₋, xₜ)\n",
    "    hₜ = tanh(input * param[1] .+ param[2])\n",
    "    return (hₜ, xₜ)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "LSTMs also have this chain like structure, but the repeating module has a different structure. Instead of having a single neural network layer, there are four, interacting in a very special way (figure below, right):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](../images/RNN_vs_LSTM.jpg)\n",
    "\n",
    "In the above diagram, each line carries an entire vector, from the output of one node to the inputs of others. The pink circles represent pointwise operations, like vector addition, while the yellow boxes are learned neural network layers. Lines merging denote concatenation, while a line forking denote its content being copied and the copies going to different locations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Core Idea Behind LSTMs\n",
    "\n",
    "The key to LSTMs is the cell state $C$, the horizontal line running through the top of the diagram: entering from the top left as $C_{t-1}$ and exiting from the top right as $C_t$.\n",
    "\n",
    "The cell state is kind of like a conveyor belt. It runs straight down the entire chain, with only some minor linear interactions (vector addition and multiplication). It’s very easy for information to just flow along it unchanged. The LSTM does have the ability to remove or add information to the cell state, carefully regulated by structures called gates. Gates are a way to optionally let information through. They are composed out of a sigmoid neural net layer and a pointwise multiplication operation (first, second, and fourth learned layers). The sigmoid layer outputs numbers between zero and one, describing how much of each component should be let through. A value of zero means “let nothing through,” while a value of one means “let everything through!”\n",
    "\n",
    "An LSTM has three of these gates, to protect and control the cell state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step-by-Step LSTM Walk Through\n",
    "\n",
    "The first step in our LSTM is to decide what information we’re going to throw away from the cell state. This decision is made by a sigmoid layer called the “forget gate layer” and it's denoted as $f$. It looks at $h_{t-1}$ and $x_t$, and outputs a number between 0 and 1 for each number in the cell state $C_{t−1}$. A 1 represents “completely keep this” while a 0 represents “completely get rid of this.” Formally:\n",
    "\n",
    "\\begin{equation}\n",
    "f_t = \\sigma\\big(W_f\\, [h_{t-1}\\,\\,x_t] + b_f\\big)\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "Let’s go back to our example of a language model trying to predict the next word based on all the previous ones. In such a problem, the cell state might include the gender of the present subject, so that the correct pronouns can be used. When we see a new subject, we want to forget the gender of the old subject.\n",
    "\n",
    "The next step is to decide what new information we’re going to store in the cell state. This has two parts. First, a sigmoid layer called the “input gate layer” (denoted by $i$) decides which values we’ll update. Next, a tanh layer creates a vector of new candidate values (denoted by $C$), $\\tilde{C}_t$, that could be added to the state. In the next step, we’ll combine these two to create an update to the state. Formally:\n",
    "\n",
    "\\begin{equation}\n",
    "i_t = \\sigma\\big(W_i\\, [h_{t-1}\\,\\,x_t] + b_i\\big)\\hspace{.7cm}\n",
    "\\end{equation}\n",
    "\\begin{equation}\n",
    "\\tilde{C}_t = \\tanh\\big(W_C\\, [h_{t-1}\\,\\,x_t] + b_C\\big)\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "In the example of our language model, we’d want to add the gender of the new subject to the cell state, to replace the old one we’re forgetting.\n",
    "\n",
    "It’s now time to update the old cell state, $C_{t−1}$, into the new cell state $C_t$. The previous steps already decided what to do, we just need to actually do it. We multiply the old state by $f_t$, forgetting the things we decided to forget earlier. Then we add $i_t∗\\tilde{C}_t$. This is the new candidate values, scaled by how much we decided to update each state value. Formally:\n",
    "\n",
    "\\begin{equation}\n",
    "C_t = f_t*C_{t-1} + i_t*\\tilde{C}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "In the case of the language model, this is where we’d actually drop the information about the old subject’s gender and add the new information, as we decided in the previous steps.\n",
    "\n",
    "Finally, we need to decide what we’re going to output. This output will be based on our cell state, but will be a filtered version. First, we run a sigmoid layer which decides what parts of the cell state we’re going to output and denote the output by $o$. Then, we put the cell state through tanh (to push the values to be between −1 and 1) and multiply it by the output of the sigmoid gate, so that we only output the parts we decided to. Formally:\n",
    "\n",
    "\\begin{equation}\n",
    "o_t = \\sigma\\big(W_o\\, [h_{t-1}\\,\\,x_t] + b_o]\\big)\n",
    "\\end{equation}\n",
    "\\begin{equation}\n",
    "h_t = o_t * \\tanh C_t\\hspace{1.8cm}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "For the language model example, since it just saw a subject, it might want to output information relevant to a verb, in case that’s what is coming next. For example, it might output whether the subject is singular or plural, so that we know what form a verb should be conjugated into if that’s what follows next."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Embeddings\n",
    "\n",
    "In mathematics, an [embedding](https://en.wikipedia.org/wiki/Embedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object $X$ is said to be embedded in another object $Y$, the embedding is given by some *injective* and *structure-preserving* map $f : X \\rightarrow Y$. The precise meaning of \"structure-preserving\" depends on the kind of mathematical structure of which $X$ and $Y$ are instances. In the terminology of category theory, a structure-preserving map is called a morphism. The fact that a map $f : X \\rightarrow Y$ is an embedding is often indicated by the use of a \"hooked arrow\": $f:X\\hookrightarrow Y$. \n",
    "\n",
    "Word embeddings allow us to perform computations on an otherwise abstract input (e.g. how can we compare 'a' and '\\n')? For example, suppose that we are given the task of determining the likelihood that a given document was plagiarized. That means that we need to compare this document to multiple to others and determine how *related* or equal the documents are. One scheme could involve comparing the words found on each document. We can represent a word as a vector of numbers:\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{banana} = (0, 1, 0, 1, 0, 0, 2, 0, 1, 0, 1, 0)\n",
    "\\end{equation}\n",
    "\n",
    "The actual interpretation of the vector varies. The vector could represent the documents in which the words occurs, in this case ocurring at every document $i$ such that $\\text{banana}(i) = 1$. Another representation that takes into account local context is neighboring word context, e.g. $banana$ is found in the sentense\n",
    "\n",
    "\\begin{equation}\n",
    "\"\\underset{-1}{\\text{yellow}}\\,\\underset{+0}{\\text{banana}}\\,\\underset{+1}{\\text{grows}}\\,\\underset{+2}{\\text{on}}\n",
    "\\,\\underset{+2}{\\text{trees}}\\,\\underset{+2}{\\text{in}}\\,\\underset{+2}{\\text{africa}}\"\n",
    "\\end{equation}\n",
    "\n",
    "Comparing two vectors (e.g. using cosine similarity) estimates how similar the two words are. However, *the notion of relatedness* depends on what vector representation you have chosen for words. For example, is Seattle similar to Denver because they are both cities? What about Seattle and Seahawks? In addition, these vectors often tend to be very high-dimensional (thousands, or even millions) and sparse. Thus, we must turn to \"learning\" a particular lower-dimensional dense embedding (or vector) for our task. You can learn more about embeddings [here](https://stats.stackexchange.com/questions/182775/what-is-an-embedding-layer-in-a-neural-network) or [here](https://www.slideshare.net/BhaskarMitra3/a-simple-introduction-to-word-embeddings).\n",
    "\n",
    "$\\textbf{Embeddings in LSTM}$ Suppose that the inputs to our LSTM network are characters from a particular vocabulary $vocab$. The idea is that since our vocabulary is discrete, we will learn a map, $emb$, which will embed each character into a continuous vector space $X$. Using this vector space representation will allow us to have a continuous, distributed representation of our vocabulary characters. If for example the lenght of our vocabulary is $V$, we may now use our continuous character features to create a distributed representation of our $V$ characters.  In the process of training a language model we will learn this character embedding map $emb:voca\\hookrightarrow X$. The hope is that by using a continuous representation, our embedding will map similar words to similar regions.\n",
    "\n",
    "Formally, we will learn a mapping (embedding) $emb:vocab\\hookrightarrow X$ that maps the space $vocab$, corresponding to a vocabulary with $V$ characters, to a continuous vector space $X$. We denote a vector from this vector space as $x\\in X$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Julia Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "using Knet, AutoGrad\n",
    "using Knet: sigm_dot, tanh_dot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Load input data and define model parameters\n",
    "\n",
    "Our first goal is to define the models parameters (e.g. layer length and size, embedding vector size) and to load/pre-process the input data. First we define the model parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "seed       = -1 \n",
    "H          = [128];\n",
    "embed_size = 168;\n",
    "datafiles  = [\"input.txt\"];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "seed > 0 && srand(seed);\n",
    "text = map(readstring, datafiles);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In summary, we have the following equations for a single-layer LSTM network with input $x_t$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "f_t &= \\sigma\\big(W_f\\, [h_{t-1}\\,\\,x_t] + b_f\\big) & (1) &\\, \\text{Forget gate} \\\\\n",
    "i_t &= \\sigma\\big(W_i\\, [h_{t-1}\\,\\,x_t] + b_i\\big) & (2) &\\, \\text{Input gate} \\\\\n",
    "\\tilde{C}_t &= \\tanh\\big(W_C\\, [h_{t-1}\\,\\,x_t] + b_C\\big) & (3) &\\, \\text{Cell candidate} \\\\\n",
    "C_t &= f_t*C_{t-1} + i_t*\\tilde{C} & (4) &\\, \\text{New cell}\\\\\n",
    "o_t &= \\sigma\\big(W_o\\, [h_{t-1}\\,\\,x_t] + b_o]\\big) & (5) &\\, \\text{Output gate} \\\\\n",
    "h_t &= o_t * \\tanh C_t & (6) &\\, \\text{New output} \n",
    "\\end{aligned}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Let us consider the size of all the variables involved. The size of the input vector $x_t$ is denoted as $1\\times I$, while the size of $h_{t-1}$ and $C_t$ are both denoted as $1\\times H$ (the size of the lstm layer), therefore the concatenated input $[h_{t-1}\\,\\,x_t]$ has a size $1\\times (H+I)$. In practice, the weight matrices $W_f, W_i, W_C$ and $W_o$ are combined into a single weight matrix $W$, therefore the size of the combined matrix $W$ is $(H+I)\\times 4H$ and the size of $b$ is $1\\times 4H$. \n",
    "\n",
    "For multiple layers, the input to an lstm layer $l$ is the hidden state from the previous layer, i.e. $h^{l-1}$, therefore $[h_{t-1}^l\\,\\,h_t^{l-1}]$ has size $1\\times (H^{l-1} + H^l)$, $W^l$ has size $(H^{l-1} + H^l)\\times 4H^l$, and $b^l$ has size $1\\times 4H^l$. \n",
    "\n",
    "Layer $l=0$ is simply the input (embedding) layer:\n",
    "\n",
    "\\begin{equation}\n",
    "h^0_t = emb * x_t\n",
    "\\end{equation}\n",
    "\n",
    "where $emb$ is the embedding matrix of size $V\\times H^0$, V is the size of the vocabulary, and $H^0$ is the size of the embedding vector. The input vector $x_t$ is a one-hot vector of size $V$. \n",
    "\n",
    "The ouput (readout, or prediction layer) is given by:\n",
    "\n",
    "\\begin{equation}\n",
    "y = ph + b_p\n",
    "\\end{equation}\n",
    "\n",
    "where $p$, $b_p$ denote the weights (matrix) and biases of the prediction layer. If the $L$ is the number of lstm layers, the size of the output vector $y$ must be $V$ (the size of the vocabulary) such that $p$ has size $H^L\\times V$.\n",
    "\n",
    "We summarize what we have done so far graphically:\n",
    "\n",
    "<img src=\"../images/lstm_vocab.jpg\" width=\"800\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### LSTM Layer:\n",
    "\n",
    "The function lstm below takes as input the weights/biases, the previous hidden/cell states, and the actual current input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "lstm (generic function with 1 method)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function lstm(weight, bias, hₜ₋, Cₜ₋, xₜ)\n",
    "    \n",
    "    H         = size(hₜ₋, 2)\n",
    "    pre_gates = hcat(xₜ, hₜ₋) * weight .+ bias\n",
    "    fₜ        = sigm_dot(pre_gates[:, 1:H])       # (1) forget gate\n",
    "    iₜ        = sigm_dot(pre_gates[:, 1 + H:2H])  # (2) input gate\n",
    "    oₜ        = sigm_dot(pre_gates[:, 1 + 2H:3H]) # (5) output gate\n",
    "    changeₜ   = tanh_dot(pre_gates[:, 1 + 3H:4H]) # (3) cell candidate\n",
    "\n",
    "    Cₜ = fₜ .* Cₜ₋ + iₜ .* changeₜ                # (4) new cell \n",
    "    hₜ = oₜ .* tanh_dot(Cₜ)                      # (6) new output\n",
    "\n",
    "    return (hₜ, Cₜ)\n",
    "\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Weight Initialization\n",
    "\n",
    "Suppose that we have an LSTM network with $L$ layers. We need to be able to initialize all weights (params) in the model. Here we initialize all weights with $xavier$ initialization into the variable \"model\" of size $2L + 3$: The last three elements of model are the embedding matrix and the weight/bias for the final prediction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "initweights"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "    initweights(H, V, embed_size)\n",
    "\n",
    "Initialize the weights of an lstm network for character prediction such that L = length(H) is\n",
    "the number of layers, H[k] is the size of the hidden layer k, V is the size of the vocabulary,\n",
    "and embed_size is the size of the embedding vector. All weights are initialize with xavier \n",
    "initialization and all biases are initialize to zero. \n",
    "\n",
    "model = initweights(...) is a vector with wₖ = model[2k - 1], bₖ = [2k] corresponding to the \n",
    "weight and biases of layer k, emb = model[end - 2] corresponding to the embedding matrix, and \n",
    "p = model[end - 1], bₚ = model[end] corresponding to the weight and bias of the final prediction layer. \n",
    "\n",
    "With Hₖ = H[k] as the size of layer k, wₖ and bₖ are of size (Hₖ₋ + Hₖ, 4Hₖ) and (1, 4Hₖ) accordingly,\n",
    "such with H₀ = embed_size. \n",
    "\n",
    "\"\"\"\n",
    "\n",
    "function initweights(H, V, embed_size)\n",
    "    init(d...) = xavier(d...)\n",
    "    bias(d...) = zeros(d...)\n",
    "    model      = Vector{Any}(2 * length(H) + 3)\n",
    "    \n",
    "    Hₖ₋ = embed_size\n",
    "    for k = 1:length(H)\n",
    "        # Your code starts here\n",
    "        Hₖ = H[k]\n",
    "        model[2k - 1] = init(Hₖ₋ + Hₖ, 4Hₖ)\n",
    "        model[2k]     = bias(1, 4Hₖ)\n",
    "        Hₖ₋ = Hₖ\n",
    "        # Your code ends here\n",
    "    end\n",
    "    \n",
    "    model[end - 2] = init(V, embed_size)\n",
    "    model[end - 1] = init(H[end], V)\n",
    "    model[end]     = bias(1, V)\n",
    "    \n",
    "    return model\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Create Initial state\n",
    "\n",
    " At each time step, we take the hidden state from previous time step as input. To be able to do that, first we need to initialize hidden state. We also store updated hidden states in array created here. We initialize state as a zero matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "initstate (generic function with 1 method)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let blank = nothing; global initstate\n",
    "    \n",
    "    \"\"\"\n",
    "    initstate(model, batch_size)\n",
    "\n",
    "    Initialize the state on an lstm network such that h[k], C[k] = state[k] are the hidden\n",
    "    and cell state of layer k. \n",
    "\n",
    "    \"\"\"\n",
    "    function initstate(model, batch_size)\n",
    "\n",
    "        L     = div(length(model) - 3, 2)\n",
    "        state = Vector{Any}(2 * L)\n",
    "        for k = 1:L\n",
    "            # Your code starts here    \n",
    "            bₖ = model[2k]\n",
    "            Hₖ = div(length(bₖ), 4)\n",
    "            if typeof(blank)!=typeof(bₖ) || size(blank)!=(Hₖ, batch_size)\n",
    "                blank = fill!(similar(bₖ, batch_size, Hₖ), 0)\n",
    "            end\n",
    "            state[2k-1] = state[2k] = blank # hₖ = state[2k-1], cₖ = state[2k]\n",
    "            # Your code ends here\n",
    "            end\n",
    "        return state\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Create Predict function\n",
    "\n",
    "Notice below that we are not performing the initial embedding operation xₜ = xₜ * model[end - 2]. Instead, we will see that it's more efficient to simply select the respective elements from the embedding matrix. In addition, note that we don't actually run the final prediction layer yₜ = xₜ * model[end-1] .+ model[end] either."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "predict (generic function with 1 method)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function predict(model, stateₜ₋, xₜ; pdrop=0)\n",
    "    L = div(length(model) - 3, 2)\n",
    "    stateₜ = similar(stateₜ₋)\n",
    "    \n",
    "    for k = 1:L\n",
    "        # Your code starts here\n",
    "        (stateₜ[2k - 1], stateₜ[2k]) = lstm(model[2k - 1], model[2k], state[2k - 1], state[2k], xₜ)\n",
    "        xₜ = stateₜ[2k - 1]\n",
    "        # Your code ends here\n",
    "    end\n",
    "\n",
    "    return xₜ, stateₜ\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Generate and Sample function\n",
    "\n",
    "Generate function is a function we use to create some text that is similar to our training data. We provide sample function to you. You can predict the next character by using sample function once you calculate the probabilities given the input. index to char is the same dictionary as you created with createdictionary function but it works in the reverse direction. It gives you the character given the index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "createVocabulary (generic function with 1 method)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function createVocabulary(text)\n",
    "    vocab = Dict{Char,Int}()\n",
    "    # Your code starts here\n",
    "    idx = 1\n",
    "    for char in text[1]\n",
    "        try vocab[char] catch vocab[char] = idx; idx += 1; end\n",
    "    end\n",
    "    # Your code ends here\n",
    "    return vocab\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sample (generic function with 1 method)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function generate(model, tok2int, nchar)\n",
    "    int2tok = Vector{Char}(length(tok2int))\n",
    "    for (k,v) in tok2int; int2tok[v] = k; end\n",
    "    input = tok2int[' ']\n",
    "    state = initstate(model, 1)\n",
    "    for t in 1:nchar\n",
    "        embed = model[end-2][[input],:]\n",
    "        ypred,state = predict(model,state,embed)\n",
    "        ypred = ypred * model[end-1] .+ model[end]\n",
    "        input = sample(exp.(logp(ypred)))\n",
    "        print(int2tok[input])\n",
    "    end\n",
    "    println()\n",
    "end\n",
    "\n",
    "function sample(p)\n",
    "    p = convert(Array,p)\n",
    "    r = rand()\n",
    "    for c = 1:length(p)\n",
    "        r -= p[c]\n",
    "        r < 0 && return c\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Array{String,1}:\n",
       " \"input.txt\""
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "seed       = -1 \n",
    "H          = [128];\n",
    "embed_size = 168;\n",
    "datafiles  = [\"input.txt\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab = createVocabulary(text);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = initweights(H, length(vocab), embed_size);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "state = initstate(model,1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "########## RANDOM MODEL OUTPUT ############\n",
      "G'b\\.cGaoV2v9jk1V,Q97IVOw6NuFifR;lz& jyH.-kepcqEWOghb{Pl'fHheSDzpQ{H7Tl ja9l1.TBOx:z:htoGdC,GoH&&MthGh,21wH97*JD6n9*eoN:JSd{L{5bKI?nI:*mYK3fMAbR!,C3H&L723SQOzC}6uvpU2w0leTn\\\\cf1&UjUJ.cMCobRsNtiBvBb}Yt\\sInlxJ9PLjy4-O!h2Q:1HRNAvj\\}FsInLd1FrIHFEAe7\\v8h\\:ojytpkaTDi8Wa.mM3U qIyOJ-,7!9RmwT3\\nrr}WG2TeWS*9C\n",
      "QIdK!T?Duw-BvoH!f}toei{JmGb*Jw-d;D}yAqcEKB2D3\\nsGj5OPi T-i2z9MJBNMbT6xHlw3*Qe0HQwhxgx,6;kYp1ex}oU31l.02fptQ1*7Nd6s;Wu2-{gl??Ee:'-n-c-\n",
      "}gYG2im2aMY.*oTqnU{Iywe M'bWsVtDwU-3jQhe7c'Q3SO&KMI.LwvQRpI{UwzIk\n"
     ]
    }
   ],
   "source": [
    "println(\"########## RANDOM MODEL OUTPUT ############\")\n",
    "generate(model, vocab, 500) ## change togenerate if you want longer sample text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loss function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "avgloss (generic function with 1 method)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function loss(model, state, sequence, range=1:length(sequence)-1; newstate=nothing, pdrop=0.0)\n",
    "    preds = []\n",
    "    for t in range\n",
    "        input = model[end-2][sequence[t],:]\n",
    "        pred,state = predict(model,state,input; pdrop=pdrop)\n",
    "        push!(preds, pred)\n",
    "    end\n",
    "    \n",
    "    if newstate != nothing\n",
    "        copy!(newstate, map(AutoGrad.getval,state))\n",
    "    end\n",
    "    \n",
    "    pred0 = vcat(preds...)\n",
    "    pred1 = dropout(pred0,pdrop)\n",
    "    pred2 = pred1 * model[end-1]\n",
    "    pred3 = pred2 .+ model[end]\n",
    "    logp1 = logp(pred3,2)\n",
    "    nrows,ncols = size(pred3)\n",
    "    golds = vcat(sequence[range[1]+1:range[end]+1]...)\n",
    "    index = similar(golds)\n",
    "    @inbounds for i=1:length(golds)\n",
    "        index[i] = i + (golds[i]-1)*nrows\n",
    "    end\n",
    "    logp2 = logp1[index]\n",
    "    logp3 = sum(logp2)\n",
    "    return -logp3 / length(golds)\n",
    "end\n",
    "\n",
    "# Knet magic\n",
    "lossgradient = grad(loss)\n",
    "\n",
    "function avgloss(model, sequence, S)\n",
    "    \n",
    "    T = length(sequence)\n",
    "    B = length(sequence[1])\n",
    "    state = initstate(model, B)\n",
    "    total = count = 0\n",
    "    for i in 1:S:T-1\n",
    "        j = min(i+S-1,T-1)\n",
    "        n = j-i+1\n",
    "        total += n * loss(model, state, sequence, i:j; newstate=state)\n",
    "        count += n\n",
    "    end\n",
    "    return total / count\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "train (generic function with 1 method)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function train(model, sequence, optim, S; pdrop=0.0)\n",
    "    T = length(sequence)\n",
    "    B = length(sequence[1])\n",
    "    \n",
    "    state = initstate(model, B)\n",
    "    for i in 1:S:T-1\n",
    "        # Your code starts here\n",
    "        j = min(i + S - 1, T - 1)\n",
    "        grads = lossgradient(model, state, sequence, i:j, pdrop=pdrop)\n",
    "        update!(model, grads, optim)\n",
    "        # Your code ends here\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "minibatch (generic function with 1 method)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function minibatch(chars, tok2int, batch_size)\n",
    "    chars  = collect(chars)\n",
    "    nbatch = div(length(chars), batch_size)\n",
    "    data   = [zeros(Int, batch_size) for i=1:nbatch]\n",
    "    for n = 1:nbatch\n",
    "        for b = 1:batch_size\n",
    "            char = chars[(b-1)*nbatch + n]\n",
    "            data[n][b] = tok2int[char]\n",
    "        end\n",
    "    end\n",
    "    return data\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "105989"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data = map(t->minibatch(t, vocab, 1), text);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d = data_one_hots(data[1], length(vocab));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1-element Array{Int64,1}:\n",
       " 1"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data[1][1]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.0-pre.alpha",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}