06_RNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Recurrent Neural Networks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* so far our vanilla NNs expected a fixed-length input and predicted a fixed-length output (e.g., animacy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* let's now look at neural networks that **handle variable length input**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* the exciting idea behind **Recurrent Neural Networks** (RNN) is that they allows us to work on **sequences** of input, output, or both"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "What do we mean by a *variable length input*?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A variable length input is a sequence where each input $x$ has a different length.\n",
    "\n",
    "For instance, the first training instance has $l$ dimensions (say, $l$ tokens), the second input sequence has $m$ dimensions (e.g., tokens).\n",
    "\n",
    "Mathematically, inspired by the notation of Cho (2015):\n",
    "$$ \\mathbf{x_1} = \\langle x_1, ..., x_l \\rangle$$ \n",
    "$$ \\mathbf{x_2} = \\langle x_1, ..., x_m \\rangle$$\n",
    "where $l\\neq m$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Detour: very simple example\n",
    "\n",
    "From Cho (2015). Assume we have a binary vector $\\mathbf{x}$ (it contains 0s and 1s). We want to count the number of 1s.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def add1(el,s):\n",
    "    if el==1: return s+1\n",
    "    else: return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "count(1): 3\n"
     ]
    }
   ],
   "source": [
    "v=[0,1,0,0,1,1]\n",
    "s=0\n",
    "for el in v:\n",
    "    s=add1(el,s)\n",
    "print(\"count(1):\", s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Two important components:\n",
    "* memory $s$\n",
    "* function $add1$ is applied to each symbol in input *one at a time* together with memory $s$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\rightarrow$ input of any length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Sequences\n",
    "\n",
    "In language technology we often work with sequences, e.g. of words or characters, e.g., $$ \\mathbf{x_2} = \\langle x_1, ..., x_m \\rangle$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Approach 1: We have already seen one approach to handle such sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "taking the **mean** of all word vectors in a sentence; but then the order is lost."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### Approach 2: Recurrent neural networks (RNNs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### RNNs ([Elman, 1990](https://onlinelibrary.wiley.com/doi/abs/10.1207/s15516709cog1402_1)): Dependence on previous step"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* RNNs are called **recurrent** because they predict the next output being dependent on the previous output (i.e., like having a *memory* of what has been seen so far)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "More formally, following the notation in Goldberg (2015):\n",
    "\n",
    "* $\\mathbf{x_{1:n}}$ input sequence\n",
    "* $\\mathbf{s_0}$ starting state (inital state)\n",
    "* function $R$ (\"memory so far\") that takes a state vector $\\mathbf{s_{i-1}}$ and an input vector $x_i$ and produces a new state $ \\mathbf{s_{i}}$\n",
    "* function $O$ maps from state to output $\\mathbf{y}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Formulation of an RNN (Goldberg 2015): <img src=\"pics/rnn0.png\" width=400> \n",
    "\n",
    "Graphical representation of an RNN (Goldberg 2015): <img src=\"pics/rnn1.png\" width=400> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Unrolling over time\n",
    "\n",
    "<img src=\"pics/rnn2.png\">\n",
    "\n",
    "Note: $\\theta$ shared parameters over time!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "##### Expansion at state 4: \n",
    "<img src=\"pics/rnn3.png\">\n",
    "Note $s_i$ based on all $s_0,..,s_{i-1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "##### Another visualization\n",
    "\n",
    "<img src=\"http://d3kbpzbmcynnmx.cloudfront.net/wp-content/uploads/2015/09/rnn.jpg\" alt=\"illustration from WildML\">\n",
    "A recurrent neural network and the unfolding in time of the computation involved in its forward computation (LeCun et al., 2015)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "However, basic RNNs (Elman) tend to not work well past a few recent time steps (vanishing or exploding gradients; one trick: gradient clipping for exploding gradients; otherwise: alternative models)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Different formulations of R,O\n",
    "\n",
    "lead to different instantiations of RNNs:\n",
    "\n",
    "* LSTM (Long Short-Term Memory) ([Hochreiter and Schmidhuber, 1997](https://www.bioinf.jku.at/publications/older/2604.pdf))\n",
    "* GRU (Gated Recurrent Units) ([Cho et al., 2014](https://arxiv.org/abs/1409.1259))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "#### LSTM \n",
    "\n",
    "memory cells (read, write, forget) - gates that control flow (continous decisions: maybe read/write/forget)\n",
    "\n",
    "Helps to keep information longer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "* [excellent introduction to LSTMs](http://colah.github.io/posts/2015-08-Understanding-LSTMs/)\n",
    "* [article on dropout in RNNs](https://arxiv.org/abs/1409.2329)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Example: Name Classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Predicting a class label from the last RNN state:\n",
    "<img src=\"pics/many2one.png\" width=\"20%\">\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "[Classifying names with a character-level RNN, by Sean Robertson](https://pytorch.org/tutorials/intermediate/char_rnn_classification_tutorial.html) NB: takes around 5 minutes to run on a 4-core CPU."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\n",
    "### RNNs:  **sequences** of input, output, or both\n",
    "\n",
    "Karpathy's illustration of RNNs:\n",
    "<img src=\"https://tensorlayer.readthedocs.io/en/stable/_images/karpathy_rnn.jpeg\">\n",
    "\n",
    "<!--* From left to right: (1) Vanilla mode of processing without RNN, from fixed-sized input to fixed-sized output (e.g. image classification). (2) Sequence output (e.g. image captioning takes an image and outputs a sentence of words). (3) Sequence input (e.g. sentiment analysis where a given sentence is classified as expressing positive or negative sentiment). (4) Sequence input and sequence output (e.g. Machine Translation: an RNN reads a sentence in English and then outputs a sentence in French). (5) Synced sequence input and output (e.g. video classification where we wish to label each frame of the video). Notice that in every case are no pre-specified constraints on the lengths sequences because the recurrent transformation (green) is fixed and can be applied as many times as we like.*-->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "##### One to many: Image caption generation, [Karpathy and Li (2014)](http://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/Karpathy_Deep_Visual-Semantic_Alignments_2015_CVPR_paper.pdf)\n",
    "<img src=\"pics/karpathy-li-2014.png\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "##### Many to many: sequence to sequence Machine Translation ([Sutskever et al., 2014](http://papers.nips.cc/paper/5346-sequence-to-sequence-learning-with-neural-networks.pdf))\n",
    "<img src=\"pics/seq2seq.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "##### many to many: POS tagging\n",
    "\n",
    "bidirectional RNN [(Plank et al., 2016)](https://www.aclweb.org/anthology/P16-2067):\n",
    "\n",
    "<img src=\"pics/bilstm.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## References\n",
    "\n",
    "* D. Rao & B. McMahan's NLP with PyTorch (chapters 6 and 7).\n",
    "* [Karpathy's blog on RNNs](http://karpathy.github.io/2015/05/21/rnn-effectiveness/)    "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}