lectures/06_intro-to-RNNs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/575_banner.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lecture 6: Introduction to Recurrent Neural Networks (RNNs)\n",
    "\n",
    "UBC Master of Data Science program, 2023-24\n",
    "\n",
    "Instructor: Varada Kolhatkar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture plan, imports, LO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import IPython\n",
    "from IPython.display import HTML, display"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Learning outcomes\n",
    "\n",
    "From this lecture you will be able to \n",
    "\n",
    "- Explain the motivation to use RNNs. \n",
    "- Explain how an RNN differs from a feed-forward neural network. \n",
    "- Explain three weight matrices in RNNs. \n",
    "- Explain parameter sharing in RNNs. \n",
    "- Explain how states and outputs are calculated in the forward pass of an RNN. \n",
    "- Explain the backward pass in RNNs at a high level. \n",
    "- Specify different architectures of RNNs and explain how these architectures are used in the context of NLP applications.\n",
    "- Broadly explain character-level text generation with RNNs.\n",
    "- Specify the shapes of weight matrices in RNNs.\n",
    "- Carry out forward pass with RNNs in `PyTorch`.\n",
    "- Explain stacked RNNs and bidirectional RNNs and the difference between the two."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 1. Motivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**RNN-generated music!**\n",
    "\n",
    "- [Magenta PerformanceRNN](https://www.youtube.com/watch?v=dMhQalLBXIU)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"500\"\n",
       "            height=\"300\"\n",
       "            src=\"https://www.youtube.com/embed/dMhQalLBXIU\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "            \n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x110f99100>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "### An example of a state-of-the-art language model\n",
    "url = \"https://www.youtube.com/embed/dMhQalLBXIU\"\n",
    "IPython.display.IFrame(url, width=500, height=300)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Language is an inherently sequential phenomenon.\n",
    "- In lab2, you identified phonemes associated with a sequence of sound waves.\n",
    "- This temporal nature of language is reflected in the metaphors used to describe language \n",
    "    - *flow of conversation*, *news feeds*, or *twitter streams*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beyond language, there are many examples of sequences in the wild. \n",
    "\n",
    "- Financial markets\n",
    "- Medical signals such as ECGs\n",
    "- Biological sequences encoded in DNA \n",
    "- Patterns of climate and patterns of motion\n",
    "\n",
    "![](img/seqs-in-the-wild.png)\n",
    "\n",
    "[Source](https://www.youtube.com/watch?v=ySEx_Bqxvvo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that in this course, our focus is on models for sequential data. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What properties do we want when we model sequences? \n",
    "\n",
    "- [ ] Order matters \n",
    "- [ ] Variable sequence lengths\n",
    "- [ ] Capture long distance dependencies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far we have seen two models to process sequential data\n",
    "\n",
    "- Markov models\n",
    "- And more flexible hidden Markov models\n",
    "\n",
    "How do these models perform on the above characteristics? \n",
    "\n",
    "<br><br><br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Recall the language modeling task, the task of predicting the next word given a sequence.\n",
    "  \n",
    "- What's the probability estimate of an upcoming word?\n",
    "    - $P(w_t|w_1,w_2,\\dots,w_{t-1})$\n",
    "      \n",
    "- When we used Markov models for this task, we made Markov assumption. \n",
    "    - Markov model: $P(w_t|w_1,w_2,\\dots,w_{t-1}) \\approx P(w_t|w_{t-1})$\n",
    "    - Markov model with more context: $P(w_t|w_1,w_2,\\dots,w_{t-1}) \\approx P(w_t|w_{t-2}, w_{t-1})$ \n",
    "\n",
    "In lab 1, you generated text with Markov models which captured some temporal aspect when generating text. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With $n=1$, we considered one previous word as context when generating text. \n",
    "\n",
    "\n",
    "![](img/bigram-ex_small.png)\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With $n=2$, we considered two previous words as context when generating text. \n",
    "\n",
    "![](img/trigram-ex_small.png)\n",
    "\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With $n=3$, we considered three previous words as context when generating text. \n",
    "  \n",
    "![](img/4-gram-ex_small.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In 2006, Google [released 5-grams](https://research.google/blog/all-our-n-gram-are-belong-to-you/) extracted from the internet. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> We processed 1,024,908,267,229 words of running text and are publishing the counts for all **1,176,470,663 five-word sequences that appear at least 40 times**. There are 13,588,391 unique words, after discarding words that appear less than 200 times.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imagine how big the transition matrix will be for 1,176,470,663 states! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Markov models do not have memory beyond the previous 2, 3 or maximum $n$ steps and when $n$ becomes larger, there is sparsity problem.\n",
    "  \n",
    "- Also, they have huge RAM requirements because you have to store all ngrams.\n",
    "  \n",
    "- Overall, modeling of probabilities of sequences with Markov models doesn't scale well. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Would a Markov model able to predict a reasonable next word in the sequence below? \n",
    "\n",
    "**I am studying data science at the University of British Columbia in Vancouver because I want to build a career in ___.** \n",
    "\n",
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some completions given by ChatGPT for the same sequence. \n",
    "\n",
    "> Provide four completions for the sequence\n",
    "I am studying data science at the University of British Columbia in Vancouver because I want to build a career in\n",
    "\n",
    "- _analytics and machine learning_\n",
    "  \n",
    "- _health care analytics and research_\n",
    "- _environmental data analysis and climate change research_\n",
    "- _social media analytics and public opinion research_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do large language models such as ChatGPT make such good predictions about next words? \n",
    "- With neural architectures\n",
    "\n",
    "In the remaining three lectures in this course, we will focus on **neural sequence modeling**. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Activity: Feedforward neural networks for sentiment analysis\n",
    "\n",
    "- Suppose you are performing sentiment analysis on movie reviews. Your goal is to predict whether a given movie review expresses a positive (👍) or negative (👎) sentiment. You are considering a feedforward neural network for this task.\n",
    "\n",
    "- Consider the following review:\n",
    "\n",
    "> **This movie was not boring at all. It was fascinating and thrilling from start to finish.**\n",
    "\n",
    "- How would you encode the input features?\n",
    "  \n",
    "- What would be the network architecture?\n",
    "  \n",
    "- Reflect on the limitations of using a feedforward neural network for this task. What aspects of language might it struggle to capture?\n",
    "  \n",
    "![](img/nn-7.png)\n",
    "\n",
    "<!-- <img src=\"img/feedforwardNN.png\" height=\"400\" width=\"400\">  -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's possible to use feedforward neural networks for sequence processing but they are not inherently designed to handle sequences because they lack ability to capture temporal dependencies. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Reminder: In feed-forward neural networks, \n",
    "    - all connections flow forward (no loops)\n",
    "    - each layer of hidden units is fully connected to the next\n",
    "- We pass fixed sized vector representation of text (e.g., representation created with `CountVectorizer`) as input. \n",
    "- We lose the temporal aspect of text in this representation.\n",
    "- Let's simplify the presentation of the feed-forward network above. \n",
    "  \n",
    "![](img/simplified_ffnn.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 1.2 RNNs introduction  \n",
    "\n",
    "- RNNs are neural network models designed to deal with sequential data.\n",
    "  \n",
    "- RNNs can help us with the limited memory problem of Markov models. \n",
    "- **RNNs are a kind of neural network model which use hidden units to retain information over time.**  \n",
    "- Unlike Markov models, this approach does not impose a fixed-length limit on this prior context; the context embodied in the previous hidden layer can include information extending back to the beginning of the sequence.\n",
    "- Condition the neural network on all previous time steps. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- How can a temporal dimension be added to a feedforward neural network?\n",
    "  \n",
    "- For word representation with a vector of size 4, a single feedforward neural network can be used for prediction.\n",
    "- For 2 words, two separate feedforward neural networks can be used together.\n",
    "- For 3 words, three separate feedforward neural networks can be used together.\n",
    "\n",
    "![](img/RNN-intro_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-intro.png\" height=\"400\" width=\"400\">  -->\n",
    "\n",
    "(Credit: [Stanford CS224d slides](http://cs224d.stanford.edu/lectures/CS224d-Lecture8.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How to connect multiple feedforward networks? \n",
    "- **Make connections between hidden layers**.\n",
    "  \n",
    "- The network typically consists of input, hidden layer, and output. The hidden layer is connected to itself for recurrent connections.\n",
    "  \n",
    "- Sequences can be processed by presenting one element at a time to the network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 2. RNN details"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 2.1 RNN presentations\n",
    "\n",
    "- Unrolled presentation \n",
    "\n",
    "![](img/RNN-intro_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-intro.png\" height=\"400\" width=\"400\">  -->\n",
    "\n",
    "\n",
    "- Recursive presentation\n",
    "\n",
    "![](img/RNN_recursive_2.png)\n",
    "<!-- <img src=\"img/RNN_recursive_2.png\" height=\"200\" width=\"200\">  -->\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/RNN_recursive_2.png\" height=\"300\" width=\"300\">  -->\n",
    "<!-- </center>      -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The key distinction between non-recurrent and recurrent architectures is **the inclusion of a new set of weights connecting the previous hidden layer to the current hidden layer**.\n",
    "  \n",
    "- The hidden layer from the previous time step acts as a form of \"memory\" that influences decisions made at later time steps.\n",
    "- These weights determine how the network incorporates the previous context when computing output for the current input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**RNN as a graphical model**\n",
    "\n",
    "- RNNs can be visualized as a graphical model. The states below are the hidden layers in each time step.  \n",
    "    - Somewhat similar to hidden Markov models (HMMs) \n",
    "    - But a hidden state in an RNN is continuous valued, high dimensional, and much richer.\n",
    "      \n",
    "- Each state is a function of the previous state and the input.\n",
    "  \n",
    "- A state contains information about the whole past sequence. \n",
    "    - $h_t = g(x_t, x_{t-1}, \\dots, x_2, x_1)$ \n",
    "\n",
    "![](img/RNN-dynamic-model_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-dynamic-model.png\" height=\"400\" width=\"400\">  -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Adding a temporal dimension and the recursion make RNNs appear to be complex. But they are not all that different from standard feedforrward neural networks.\n",
    "  \n",
    "- Given an input vector and the values for the hidden layer from the previous time step we are still performing standard feedforward calculations. \n",
    "- The most significant change lies in the new set of weights $U$ that connect the hidden layer from the previous time step to the current hidden layer. \n",
    "- As with the other weights in the network, these connections are trained via a variant of backpropagation.\n",
    "\n",
    "![](img/RNN-as-FFNN_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-as-FFNN.png\" height=\"500\" width=\"500\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Parameter sharing\n",
    "\n",
    "- What are the parameters of this model? There are three weight matrices. \n",
    "    - Input to hidden weight matrix: $W$\n",
    "    - Hidden to output weight matrix: $V$    \n",
    "    - Hidden to hidden weight matrix: $U$\n",
    "    \n",
    "- The key point in RNNs: **All weights between time steps are shared.**\n",
    "    - This allows the model to learn patterns that are independent of their position in the sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Dimensionality of different weight matrices**\n",
    "Lets consider an example: \n",
    "- Suppose input vector $x_t$ is of size 300 (i.e., $x_t \\in \\mathbb{R}^{300}$)\n",
    "  \n",
    "- Suppose the hidden state vector is of size 100 (memory of the network) (i.e., $h_t \\in \\mathbb{R}^{100}$)\n",
    "  \n",
    "- Suppose the output vector $y_t$ is of size 60 (i.e., $y_t \\in \\mathbb{R}^{60}$)\n",
    "- $W_{100 \\times 300}$, $V_{60\\times 100}$, $U_{100\\times 100}$ \n",
    "\n",
    "![](img/RNN-as-FFNN_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-as-FFNN.png\" height=\"500\" width=\"500\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)\n",
    "\n",
    "- Input size: Suppose $x \\in \\mathbb{R}^{d_{in}}$\n",
    "- Output size: Suppose $y \\in \\mathbb{R}^{d_{out}}$\n",
    "- Hidden size: Suppose $h \\in \\mathbb{R}^{d_h}$\n",
    "- Three kinds of weights: $W_{d_{h}\\times d_{in}}$, $V_{d_{out}\\times d_{h}}$, $U_{d_h\\times d_h}$    \n",
    "> You may see transpose of these matrices in some notations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Forward pass in RNNs\n",
    "\n",
    "- The forward inference in RNNs is very similar to what you have seen with feedforward networks. \n",
    "- Given an input $x_t$ at timestep $t$, how do we compute the new hidden state $h_{t}$ and output $y_t$? \n",
    "\n",
    "![](img/RNN-dynamic-model_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-dynamic-model.png\" height=\"400\" width=\"400\">  -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Computing the new state $h_t$\n",
    "\n",
    "- Multiply the input $x_t$ with the weight matrix between input and hidden layer ($W$) and the state or the hidden layer from the previous time step $h_{t-1}$ with the weight matrix between hidden layers ($U$). \n",
    "- Add these values together. \n",
    "- Add the bias vector and pass the result through a suitable activation function $g$. \n",
    "\n",
    "$$\n",
    "h_t = g(U_{d_h \\times d_h}(h_{t-1})_{d_h \\times 1} + W_{d_{h} \\times d_{in}} (x_t)_{d_{in} \\times 1}  + b_1)\\\\\n",
    "$$ \n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/RNN_dynamic_model.png\" height=\"800\" width=\"800\">  -->\n",
    "<!-- </center>     -->\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Computing the output $y_t$\n",
    "\n",
    "- Once we have the value for the new state $h_t$, we can calculate the output vector $y_t$ by multiplying $h_t$ with the weight matrix $V$ between the hidden layer and the output layer, adding the bias vector, and applying an appropriate activation function $f$ the multiplication.  \n",
    "\n",
    "$$\n",
    "y_t = f(V_{d_{out} \\times d_{h}} (h_t){_{d_h \\times 1}} + b_2)\n",
    "$$ \n",
    "\n",
    "\n",
    "<!-- <img src=\"img/RNN-dynamic-model.png\" height=\"400\" width=\"400\">  -->\n",
    "\n",
    "- Typically, we are interested in soft classification. So computing $y_t$ involves a softmax computation which provides a probability distribution over the possible output classes. \n",
    "\n",
    "$$\n",
    "y_t = \\text{softmax}(Vh_t + b_2)\n",
    "$$ \n",
    "\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Summary**\n",
    "\n",
    "So in the forward pass we compute the new state $h_t$ and the output $y_t$ for all time steps in a sequence, as shown below.  \n",
    "\n",
    "$$\n",
    "h_t = g(Uh_{t-1} + Wx_t + b_1)\\\\\n",
    "y_t = \\text{softmax}(Vh_t + b_2)\n",
    "$$ \n",
    "\n",
    "![](img/RNN-dynamic-model_small.png)\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/RNN-dynamic-model.png\" height=\"400\" width=\"400\">  -->\n",
    "<!-- </center>     -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Forward pass pseudo code**\n",
    "\n",
    "We compute this for the full sequence. \n",
    "\n",
    "- Given: $x$, network\n",
    "- Intialize $h_0$\n",
    "- for $t$ in 1 to length(input sequence $x$)\n",
    "    - $h_t = g(Uh_{t-1} + Wx_t + b_1$)\n",
    "    - $y_t = \\text{softmax}(Vh_t + b_2)$\n",
    "\n",
    "Note that the matrices $U$, $V$ and $W$ are **shared across time** and new values for $h_t$ and $y_t$ are calculated at each time step.\n",
    "\n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 RNN Forward pass with PyTorch\n",
    "\n",
    "- See the documentation [here](https://pytorch.org/docs/stable/generated/torch.nn.RNN.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n",
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n"
     ]
    }
   ],
   "source": [
    "import torch\n",
    "import torch.nn as nn\n",
    "from torch.nn import RNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Creating an RNN object**\n",
    "\n",
    "We are creating an RNN with \n",
    "- only one hidden layer \n",
    "- input of size 20 (e.g., imagine word vectors of size 20)\n",
    "- hidden layer of size 10 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "rnn = nn.RNN(20, 10, 1)  # input size, hidden_size, number of layers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Input**\n",
    "\n",
    "- The input is going to be sequences (e.g., sequences of words)\n",
    "- We need to provide the sequence length of the sequence and the size of each input vector. \n",
    "- For example, suppose you have the following sequence and you are representing each word with a 20-dimensional word vector, then your sequence length is going to be 5 and input size is going to be 20.  \n",
    "\n",
    "> Cherry blossoms are beautiful ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[-0.2554,  0.7601,  0.3840, -0.3264,  0.4060,  1.5740, -1.4970, -0.6468,\n",
       "          0.5950,  0.1623, -0.6175, -0.2635,  1.5960, -0.2624,  0.5696,  0.2100,\n",
       "         -0.5108,  0.3974,  0.4392, -0.0653],\n",
       "        [-0.7360,  1.1099, -0.1129, -0.5655,  0.9957, -0.0693, -1.0823, -0.2739,\n",
       "         -1.4711,  0.5462, -1.7470,  0.4973, -1.0494,  0.1640, -1.3481,  0.8058,\n",
       "          0.5724,  0.8161,  1.0063, -0.0902],\n",
       "        [-0.7250, -1.6884, -0.1659, -0.7149,  1.5056, -0.1332, -1.0522, -0.3834,\n",
       "          0.3442, -0.9941, -1.0864,  1.3990, -1.3039,  1.5587,  0.1175,  0.2605,\n",
       "          1.0913, -0.1104,  0.5576, -0.4724],\n",
       "        [-1.5352,  0.3951, -0.0912, -0.7498, -0.0937,  0.4583,  0.9655,  0.2317,\n",
       "          1.6085,  1.2108, -0.8120, -0.4538, -0.4741, -3.1901,  0.6411, -0.2333,\n",
       "         -1.0462, -1.2838,  0.5392,  2.0218],\n",
       "        [ 0.5490,  0.0211,  0.7921, -1.4315, -1.4205, -0.3222,  1.6674, -0.7840,\n",
       "          0.5391, -0.2517, -0.6281,  0.4963, -1.7812,  0.8825,  0.3850,  1.3582,\n",
       "         -0.4881,  0.2211,  0.5796,  0.6922]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inp = torch.randn(5, 20)  # sequence length, input size\n",
    "inp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Initial hidden state**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- At the 0th time step, we do not have anything to remember. So we initialize the hidden state randomly or to 0.0. \n",
    "- Let's initialize h0. \n",
    "- The shape of h0 is the number of hidden layers and hidden size. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "h0 = torch.randn(1, 10)  # number of hidden layers, hidden size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[ 1.7567, -0.0840, -0.3079, -0.5333,  0.2166, -0.3817,  0.5788, -0.2824,\n",
       "         -1.6858,  0.4005]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Calculating new hidden states and output**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# PyTorch calculates the output and new hidden states for us for all time steps.\n",
    "output, hn = rnn(inp, h0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[ 0.5572, -0.6662,  0.5804, -0.5159,  0.7453, -0.0698,  0.3410,  0.1101,\n",
       "          0.4794,  0.6953]], grad_fn=<SqueezeBackward1>)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hn  # hidden state for the last time step in the sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[-0.0993,  0.0714,  0.4826,  0.0065,  0.1421,  0.7195, -0.5334,  0.3903,\n",
       "          0.4360, -0.2753],\n",
       "        [ 0.7393, -0.9225, -0.3895, -0.1448, -0.8861,  0.1096, -0.3037,  0.3522,\n",
       "          0.5371, -0.4470],\n",
       "        [ 0.8373, -0.9128,  0.1970,  0.4659, -0.7443, -0.4902, -0.9079,  0.2426,\n",
       "          0.2778,  0.7264],\n",
       "        [-0.7502, -0.9221, -0.2595, -0.4168,  0.2801,  0.9771, -0.6672,  0.1760,\n",
       "          0.6120, -0.2874],\n",
       "        [ 0.5572, -0.6662,  0.5804, -0.5159,  0.7453, -0.0698,  0.3410,  0.1101,\n",
       "          0.4794,  0.6953]], grad_fn=<SqueezeBackward1>)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([5, 10])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "output.shape "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default, `tanh` activation function is used.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Shapes of the weight matrices**\n",
    "\n",
    "What would be the shapes of weight matrices? \n",
    "- Input to hidden ($W$)\n",
    "- Hidden to hidden ($U$)\n",
    "\n",
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Weight matrix $W$ between input to hidden layer: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([5, 20])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inp.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([10, 20])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rnn.state_dict()[\"weight_ih_l0\"].shape # (hidden, input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Weight matrix $U$ between hidden layer in time step $t-1$ to hidden layer in time step $t$: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([1, 10])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([10, 10])"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rnn.state_dict()[\"weight_hh_l0\"].shape # (hidden, hidden)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the `rnn` above is calculating the output of the hidden layer at each time step but we are not calculating $y_t$ in each time step $t$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's define a simple RNN for a toy sentiment analysis task. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define a toy dataset of sentences and their labels\n",
    "corpus = [\n",
    "    (\"I love machine learning and deep learning\", 1),\n",
    "    (\"I hate it when the Jupyter lab kernel dies on me\", 0),     \n",
    "    (\"Data cleaning is a tedious task\", 0),\n",
    "    (\"Hidden Markov models are so elegant\", 1),    \n",
    "    (\"Nothing is more exciting than uncovering hidden patterns in data\", 1),\n",
    "    (\"Debugging machine learning models can be frustrating\", 0),\n",
    "    (\"Overfitting is a common problem in machine learning models\", 0),\n",
    "    (\"It's rewarding to see your model perform well on unseen data\", 1),\n",
    "    (\"Dealing with missing data is annoying\", 0),\n",
    "    (\"I enjoy learning about neural models for sequence processing\", 1)\n",
    "]\n",
    "\n",
    "# Tokenization and Vocabulary Creation\n",
    "from collections import Counter\n",
    "\n",
    "# Tokenize sentences\n",
    "tokens = [sentence.lower().split() for sentence, _ in corpus]\n",
    "vocab = Counter(word for sentence in tokens for word in sentence)\n",
    "\n",
    "# Create word to index mapping\n",
    "word_to_idx = {word: i+1 for i, (word, _) in enumerate(vocab.items())} # Starting index from 1 for padding\n",
    "idx_to_word = {i: word for word, i in word_to_idx.items()}\n",
    "\n",
    "vocab_size = len(word_to_idx) + 1  # +1 for padding token at index 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "62"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vocab_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# idx_to_word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch.nn.utils.rnn import pad_sequence\n",
    "\n",
    "# Convert sentences to integer sequences\n",
    "sequences = [[word_to_idx[word] for word in sentence.lower().split()] for sentence, _ in corpus]\n",
    "\n",
    "# Pad sequences to have the same length and create tensors\n",
    "sequence_length = max(len(seq) for seq in sequences)  # Get max sequence length for padding\n",
    "padded_sequences = pad_sequence([torch.tensor(seq) for seq in sequences], batch_first=True)\n",
    "\n",
    "# Labels\n",
    "labels = torch.tensor([label for _, label in corpus])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([[ 1,  2,  3,  4,  5,  6,  4,  0,  0,  0,  0],\n",
       "        [ 1,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16],\n",
       "        [17, 18, 19, 20, 21, 22,  0,  0,  0,  0,  0],\n",
       "        [23, 24, 25, 26, 27, 28,  0,  0,  0,  0,  0],\n",
       "        [29, 19, 30, 31, 32, 33, 23, 34, 35, 17,  0],\n",
       "        [36,  3,  4, 25, 37, 38, 39,  0,  0,  0,  0],\n",
       "        [40, 19, 20, 41, 42, 35,  3,  4, 25,  0,  0],\n",
       "        [43, 44, 45, 46, 47, 48, 49, 50, 15, 51, 17],\n",
       "        [52, 53, 54, 17, 19, 55,  0,  0,  0,  0,  0],\n",
       "        [ 1, 56,  4, 57, 58, 25, 59, 60, 61,  0,  0]])"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "padded_sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch.nn as nn\n",
    "\n",
    "class SentimentRNN(nn.Module):\n",
    "    def __init__(self, vocab_size, embedding_dim, hidden_dim, output_dim):\n",
    "        \n",
    "        super(SentimentRNN, self).__init__() # the constructor of the parent nn.Module class\n",
    "        \n",
    "        # Define an embedding layer:\n",
    "        # This layer will transform the input word indices into dense vectors of a specified size (embedding_dim)\n",
    "        # vocab_size: the size of the vocabulary (number of unique words in your dataset + 1 for padding)\n",
    "        # embedding_dim: the size of the embedding vector for each word\n",
    "        self.embedding = nn.Embedding(vocab_size, embedding_dim)\n",
    "        \n",
    "        # Define a simple RNN layer:\n",
    "        # This layer processes the sequences of word embeddings and captures the sequential information\n",
    "        # embedding_dim: the input size to the RNN (size of the word embeddings)\n",
    "        # hidden_dim: the size of the RNN's hidden state\n",
    "        # batch_first=True: specifies that the input and output tensors will be of shape (batch_size, seq_length, feature)\n",
    "        self.rnn = nn.RNN(embedding_dim, hidden_dim, batch_first=True)\n",
    "        \n",
    "        # Define a fully connected (linear) layer:\n",
    "        # This layer maps the RNN's hidden state to the output classes (positive or negative sentiment in this case)\n",
    "        # hidden_dim: the size of the RNN's hidden state (input features to this layer)\n",
    "        # output_dim: the number of output classes (2 for binary classification)\n",
    "        self.fc = nn.Linear(hidden_dim, output_dim)\n",
    "        \n",
    "    def forward(self, text):\n",
    "        # Forward pass through the embedding layer:\n",
    "        # text: the input text sequences (batch of tokenized and indexed words)\n",
    "        # embedded: the embedded representation of the input text\n",
    "        embedded = self.embedding(text)\n",
    "        \n",
    "        # Forward pass through the RNN layer:\n",
    "        # embedded: the sequences of embedded words\n",
    "        # output: the output features from the RNN for each time step (we won't use this here)\n",
    "        # hidden: the final hidden state from the RNN\n",
    "        output, hidden = self.rnn(embedded)\n",
    "        \n",
    "        # Assert that the last output of the RNN matches the final hidden state\n",
    "        # This is just a sanity check and is not necessary for the model to function\n",
    "        assert torch.equal(output[:, -1, :], hidden.squeeze(0))\n",
    "        \n",
    "        # Forward pass through the fully connected layer:\n",
    "        # We use the final hidden state to predict the sentiment\n",
    "        # hidden.squeeze(0): removes the first dimension of the hidden state to match the input shape expected by the linear layer\n",
    "        # This operation is needed because the RNN layer outputs hidden states with a shape (num_layers, batch_size, hidden_dim),\n",
    "        # but the linear layer expects inputs with a shape (batch_size, hidden_dim)\n",
    "        return self.fc(hidden.squeeze(0))\n",
    "\n",
    "\n",
    "# Create an instance of our SentimentRNN model, specifying the vocabulary size, embedding dimension,\n",
    "# hidden dimension (size of the RNN's hidden state), and output dimension (number of classes).\n",
    "model = SentimentRNN(vocab_size=vocab_size, embedding_dim=100, hidden_dim=128, output_dim=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What are the parameters of the model? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=================================================================\n",
      "Layer (type:depth-idx)                   Param #\n",
      "=================================================================\n",
      "├─Embedding: 1-1                         6,200\n",
      "├─RNN: 1-2                               29,440\n",
      "├─Linear: 1-3                            258\n",
      "=================================================================\n",
      "Total params: 35,898\n",
      "Trainable params: 35,898\n",
      "Non-trainable params: 0\n",
      "=================================================================\n"
     ]
    }
   ],
   "source": [
    "from torchsummary import summary\n",
    "\n",
    "summary(model, input_size=(100, ));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How are these parameters calculated?\n",
    "- Embedding layer: vocab_size * embedding_dim = 62 * 100\n",
    "- RNN layer: (embedding_dim * hidden_dim) + hidden_dim + (hidden_dim * hidden_dim) + hidden_dim = (100 * 128) + 128 + (128 * 128) + 128 = 29,440\n",
    "- Linear layer: (hidden_dim * output_features) + output_features = (128 * 2) + 2 = 258"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[0.4172, 0.5828],\n",
      "        [0.5895, 0.4105],\n",
      "        [0.4243, 0.5757],\n",
      "        [0.4289, 0.5711],\n",
      "        [0.3845, 0.6155],\n",
      "        [0.4341, 0.5659],\n",
      "        [0.4471, 0.5529],\n",
      "        [0.3150, 0.6850],\n",
      "        [0.4294, 0.5706],\n",
      "        [0.4232, 0.5768]], grad_fn=<SoftmaxBackward0>)\n"
     ]
    }
   ],
   "source": [
    "from torch.nn.functional import softmax\n",
    "\n",
    "# Assuming a single batch for simplicity\n",
    "predictions = model(padded_sequences)\n",
    "probabilities = softmax(predictions, dim=1)\n",
    "\n",
    "print(probabilities)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The probabilities won't make sense because we have not trained the model. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The training loop will be very similar to that of feedforward neural networks. However, I won't implement it for this toy example, as it won't learn much from our tiny corpus. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/eva-coffee.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ❓❓ Questions for you"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercise 6.1: Select all of the following statements which are **True** (iClicker)\n",
    "\n",
    "**iClicker join link: https://join.iclicker.com/ZTLY**\n",
    "\n",
    "- (A) RNNs pass along information between time steps through hidden layers.\n",
    "- (B) RNNs are appropriate only for text data.\n",
    "- (C) At each time step in an RNN, we use a unique hidden state (`h`), a unique input (`X`), but we reuse the same `U` matrix of weights.\n",
    "- (D) The number of parameters in an RNN language model would grow with the number of time steps.\n",
    "- (E) The hidden state at the current time step in an RNN depends only on the input data at the current time step and the hidden state from the previous time step.\n",
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{admonition} Exercise 6.1: V's Solutions!\n",
    ":class: tip, dropdown\n",
    "- A, C, E\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Training RNNs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- RNN is a **supervised machine learning model**. Similar to feedforward networks, we'll use a \n",
    "    - training set\n",
    "    - a loss function  \n",
    "    - backpropagation to obtain the gradients needed to adjust the weights in these networks \n",
    "\n",
    "- We have 3 sets of weights (and the corresponding bias terms) to update\n",
    "    - $W \\rightarrow $ the weight matrix between input layer and hidden layer\n",
    "    - $U \\rightarrow $ the weight matrix between previous hidden layer to current hidden layer\n",
    "    - $V \\rightarrow $ the weight matrix between hidden layer and output layer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to assess the error occurring at time step $t$.\n",
    "\n",
    "- To compute the loss function for the output at time $t$ we need the hidden layer from time $t-1$.\n",
    "- The hidden layer at time $t$ influences both the output at time $t$ and the hidden layer at time $t+1$. \n",
    "\n",
    "![](img/RNN_loss.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN_loss.png\" height=\"1500\" width=\"1500\">  -->\n",
    "\n",
    "[Credit](http://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture10.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/BPTT_small.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- To assess the error occurring to $h_t$, we need to know its influence on both the current output and the ones that follow.  \n",
    "- This is different than the usual backpropagation. We need to tailor backpropogation algorithm to this situation. In RNNs we use a generalized version of **Backpropogation called Backpropogation Through Time (BPTT)** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- The loss calculation depends upon the task and the architecture we are using. \n",
    "- The overall loss is the summation of losses at each time step. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- See [the code](https://gist.github.com/karpathy/d4dee566867f8291f086) for the above in ~112 lines of Python written by Andrej Karpathy. The code has only `numpy` dependency. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 5. RNN applications "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "- We have seen the basic RNN architecture below. \n",
    "\n",
    "![](img/RNN-intro_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN-intro.png\" height=\"500\" width=\"500\">  -->\n",
    "\n",
    "- But a number of architectures are possible, which makes them a very rich family of models.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- A number of possible RNN architectures\n",
    "\n",
    "![](img/RNN_architectures.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/RNN_architectures.png\" height=\"1500\" width=\"1500\">  -->\n",
    "<!-- </center>     -->\n",
    "\n",
    "[source](http://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture10.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how can we apply it to three different types of NLP tasks:\n",
    "- Sequence labeling (e.g., POS tagging)\n",
    "- Sequence classification (e.g. sentiment analysis or text classification)\n",
    "- Text generation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### 5.1 Sequence labeling \n",
    "\n",
    "- The task is to assign a label from a fixed set of labels to each element in the sequence.  \n",
    "    - Part-of-speech tagging \n",
    "    - Named entity recognition\n",
    "      \n",
    "- Many-to-many architecture\n",
    "  \n",
    "- Inputs are usually pre-trained word embeddings and outputs are tag probabilities generated by a softmax layer over the given tagset. \n",
    "- The RNN block is an abstraction representing an unrolled simple RNN consisting of an input layer, hidden layer and output layer at each time step and shared weight matrices $U$, $W$, and $V$. \n",
    "\n",
    "![](img/RNN_seq_labeling.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN_seq_labeling.png\" height=\"600\" width=\"600\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 5.2 Sequence classification\n",
    "\n",
    "- We have done text classification such as sentiment analysis or spam identification before with traditional ML models, where we ignored the temporal nature of language.\n",
    "  \n",
    "- These are actually sequence classification tasks where we want to map a sequence of text to a label from a small set of labels (e.g., positive, negative, neutral).\n",
    "  \n",
    "- To apply RNNs in this setting, we take the text to be classified and pass one word at a time generating a new hidden layer at each time step. We can then take the hidden layer from the last time step, $h_n$, which has the compressed representation of the entire sequence. We pass this representation through a feedforward neural network which chooses a class via a softmax.     \n",
    "- This is a many-to-one RNN architecture. \n",
    "\n",
    "![](img/RNN_classification.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN_classification.png\" height=\"600\" width=\"600\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Similar to the sequence labeling example, we can also pass word embeddings as input.\n",
    "  \n",
    "- Note that in this approach we do not have immediate outputs at each time step and we do not need to compute $y$ at each time step. We only have an output at the last time step. \n",
    "- So there won't be loss terms associated with each time step. \n",
    "- The loss function used to train the weights in the network is entirely based on the final text classification task. \n",
    "- We will compare the output of the softmax layer of the feed-forward classifier and the actual $y$ to calculate the loss (e.g., cross-entropy loss) and this loss will drive the training. \n",
    "- The error signal is backpropagated all the way through the weights in the feed-forward classifier, through its input, which is the hidden layer output of the last time step, through the three sets of RNN weights: $U$, $V$, and $W$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 5.3 Text generation\n",
    "\n",
    "- The idea is similar to text generation with Markov models.\n",
    "  \n",
    "- We start with a seed. We then continue to sample words conditioned on our previous choices until we reach a pre-determined desired length of a sequence or end-of-sequence token is generated.\n",
    "- In the context of RNNs\n",
    "    - We start with a seed. In the example below, we are starting with a special beginning of sequence token \\<s\\>. \n",
    "    - We use embedding representation of this token and pass it to the RNN. \n",
    "    - We sample a word in the output from the softmax distribution.  \n",
    "    - We use this sampled word as the input in the next time step and then sample the next word in the same fashion. \n",
    "    - We continue this until the fixed length limit or the end of the sentence marker is reached. \n",
    "\n",
    "![](img/RNN_generation_small.png)\n",
    "\n",
    "<!-- <img src=\"img/RNN_generation.png\" height=\"600\" width=\"600\">  -->\n",
    "    \n",
    "- The same idea can be used for music generation. \n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "You can find a toy example of of RNN text generation with PyTorch in [AppendixC](AppendixC-toy-RNN.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### 5.4 Image captioning \n",
    "\n",
    "- The same idea can be used for more complicated applications such as machine translation, summarization, or image captioning.\n",
    "  \n",
    "- The idea is to prime the generation component with an appropriate context. \n",
    "- For example, in image captioning we can prime the generation component with a meaningful  representation of an image given by the last layer in CNNs.  \n",
    "- You'll work on this application in the lab next week. \n",
    "\n",
    "![](img/image_captioning_small.png)\n",
    "\n",
    "<!-- <center> -->\n",
    "<!-- <img src=\"img/image_captioning.png\" width=\"1000\" height=\"1000\"> -->\n",
    "<!-- </center> -->\n",
    "    \n",
    "[Source](https://cs.stanford.edu/people/karpathy/sfmltalk.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Stacked and Bidirectional RNN architectures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- We have seen a simple RNN with one hidden layer.\n",
    "  \n",
    "- But RNNs are quite flexible.\n",
    "  \n",
    "- Two common ways to create complex networks by combining RNNs are:\n",
    "    - Stacked RNNs\n",
    "    - Bidirectional RNNs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1 Stacked RNNs \n",
    "\n",
    "- In the examples thus far, the input of RNNs was a sequence of word or character embeddings. We were passing the output of the RNN layer to the output layer and the outputs have been vectors useful for predicting next words, tags, or sequence labels.  \n",
    "\n",
    "![](img/RNN_seq_labeling.png)\n",
    "<!-- <img src=\"img/RNN_seq_labeling.png\" height=\"600\" width=\"600\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- But nothing prevents us from using **the sequence of outputs from one RNN as an input sequence to another one**.\n",
    "  \n",
    "- These are called **stacked RNNs** which consist of multiple networks where the output of one layer serves as the input to a subsequent layer. \n",
    "\n",
    "![](img/RNN_stacked.png)\n",
    "\n",
    "\n",
    "<!-- <img src=\"img/RNN_stacked.png\" height=\"600\" width=\"600\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Stacked RNNs generally outperform single-layer networks.\n",
    "  \n",
    "- The network learns a different level of abstraction at each layer.\n",
    "  \n",
    "- You can optimize your network for number of layers for your specific application and dataset.  \n",
    "- But remember that more layers means higher training cost. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 Bidirectional RNNs \n",
    "\n",
    "- The RNN uses information from the prior context to make predictions at time $t$.\n",
    "  \n",
    "- But in many applications (e.g., POS tagging) we do have access to the entire input sequence and knowing the context on the right of time $t$ can be useful.\n",
    "  \n",
    "- For example, suppose you are doing POS tagging and you are at the token **Teddy** in the sequence. It will be useful to know the right context in order to make the decision on whether it should be tagged as a _noun_ or a _proper noun_.  \n",
    "\n",
    "> He said , \" **Teddy** Roosevelt was a great president ! \"<br>\n",
    "\n",
    "> He said , \" **Teddy** bears are on sale ! \"\n",
    "\n",
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- How can we use the words on the right of time step $t$ as context?\n",
    "  \n",
    "- In the left-to-right RNN, the hidden state at time $t$ represents everything the network knows about the sequence up to that point.\n",
    "  \n",
    "- Suppose $h_t^f$ denotes a hidden state at time $t$ representing everything the network has gleaned from the sequence so far. \n",
    "$$h_t^f = RNN_{forward}(x_1, x_2, \\dots, x_t) $$\n",
    "- We can also train the network in the reverse direction, from right to left, to take advantage of the right context. \n",
    "- With this approach the hidden state at time $t$, $h_t^b$ represents all the information we have learned about the sequence from time $t$ to the end of the sequence. \n",
    "$$h_t^b = RNN_{backward}(x_t, x_{t+1}, \\dots, x_n) $$\n",
    "- (Somewhat similar to the $\\alpha$ and $\\beta$ values in the forward and backward algorithms in HMMs.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **bidirectional RNN** combines two independent RNNs:\n",
    "\n",
    "- One where the input is processed from the start to the end\n",
    "  \n",
    "- The other from the end to the start.\n",
    "  \n",
    "- Each RNN will result in some representation of the input. \n",
    "- We then combine the two representations computed by two independent RNNs into a single vector which captures both the left and right contexts of an input at each point in time. \n",
    "- We can combine vectors by\n",
    "    - Concatenating them, as shown in the picture below or\n",
    "    - Element-wise addition \n",
    "    - Element-wise multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/bidirectional_seq_labeling.png)\n",
    "<!-- <img src=\"img/bidirectional_seq_labeling.png\" height=\"600\" width=\"600\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- You can also use bidirectional RNNs for sequence classification. \n",
    "- Recall that in sequence classification we pass the final hidden state of the RNN as input to a subsequent feedforward classifier. \n",
    "- The problem with this approach is that the final hidden state reflects more information about the end of the sequence than its beginning. \n",
    "- Bidirectional RNNs provide a simple solution to this problem. We can create a final hidden state by combining hidden states of forward and backward passes so that the hidden state reflects information about both the beginning and end of the sequence. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](img/bidirectional_classification.png)\n",
    "<!-- <img src=\"img/bidirectional_classification.png\" height=\"600\" width=\"600\">  -->\n",
    "\n",
    "[Source](https://web.stanford.edu/~jurafsky/slp3/9.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Final comments and summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Important ideas to know \n",
    "\n",
    "- RNNs are supervised neural network models to process sequential data.\n",
    "- The intuition is to put multiple feed-forward networks together and making connections between hidden layers.  \n",
    "- They have feedback connections in their structure to \"remember\" previous inputs, when reading in a sequence. \n",
    "- In simple RNNs sequences are processed one element at a time. The output of each neural unit at time $t$ is based on the current input at $t$ and the hidden layer at time $t-1$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- In RNNs, the parameters are shared across different time steps.\n",
    "- A generalized version of backpropagation called backpropagation through time is used for training the network. \n",
    "- In practice truncated backpropagation through time is used where we work through chunks. \n",
    "- A number of RNNs architectures are possible. \n",
    "- RNNs fail to capture long-distance dependencies because of the problems like vanishing gradients.  \n",
    "- In practice, some other complicated variants such as LSTMs and GRUs are used. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Coming up ...\n",
    "- Intuition of transformers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Resources\n",
    "\n",
    "- [Sequence processing with Recurrent Neural Networks](https://web.stanford.edu/~jurafsky/slp3/9.pdf) (The notes above are heavily based on this resource.)\n",
    "- [Backpropagation Through Time: What it does and how to do it](https://axon.cs.byu.edu/Dan/678/papers/Recurrent/Werbos.pdf)\n",
    "- [The Unreasonable Effectiveness of Recurrent Neural Networks](http://karpathy.github.io/2015/05/21/rnn-effectiveness/)\n",
    "- [Coursera: NLP sequence models](https://www.coursera.org/lecture/nlp-sequence-models/recurrent-neural-network-model-ftkzt)\n",
    "- [RNN code in 112 lines of Python](https://gist.github.com/karpathy/d4dee566867f8291f086#file-min-char-rnn-py-L112)\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [conda env:575]",
   "language": "python",
   "name": "conda-env-575-py"
  },
  "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.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}