C3-natural-language-processing-with-sequence-models/Week3/C3_W3_Lecture_Notebook_Vanishing_Gradients.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vanishing Gradients and Exploding Gradients in RNNs : Ungraded Lecture Notebook\n",
    "In this notebook, you'll take another look at vanishing and exploding gradients in RNNs, from an intuitive standpoint.\n",
    "\n",
    "## Background\n",
    "Vanilla RNNs are prone to vanishing and exploding gradients when dealing with long sequences. Recall that the gradient with respect to $W_h$ is proportional to a sum of products:\n",
    "\n",
    "$$\\frac{\\delta L}{\\delta W_h} \\propto \\sum_{1\\le k\\le t} \\left(\\prod_{t\\ge i>k} \\frac{\\delta h_i}{\\delta h_{i-1}}\\right)\\frac{\\delta h_k}{\\delta W_h}$$\n",
    "\n",
    "where, for step $k$ far away from the place where the loss is computed ($t$), the product\n",
    "\n",
    "$$\\prod_{t\\ge i>k} \\frac{\\delta h_i}{\\delta h_{i-1}}$$\n",
    "\n",
    "can either go to 0 or infinity depending on the values of the partial derivative of the hidden state $\\frac{\\delta h_i}{\\delta h_{i-1}}$. In this ungraded lab, you will take a closer look at the partial derivative of the hidden state, and I'll show you how gradient problems arise when dealing with long sequences in vanilla RNNs. \n",
    "\n",
    "## Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import ipywidgets as widgets\n",
    "from ipywidgets import interact, interactive, fixed, interact_manual\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activations & Partial Derivative\n",
    "\n",
    "### Partial Derivative\n",
    "Recall that the hidden state at step $i$ is defined as:\n",
    "\n",
    "$$h_i= \\sigma(W_{hh} h_{i-1} + W_{hx} x_i + b_h)$$\n",
    "\n",
    "where $\\sigma$ is an activation function (usually sigmoid). So, you can use the chain rule to get the partial derivative:\n",
    "\n",
    "$$\\frac{\\delta h_i}{\\delta h_{i-1}} = W_{hh}^T \\text{diag} (\\sigma'(W_{hh} h_{i-1} + W_{hx} x_i + b_h))$$\n",
    "\n",
    "$W_h^T$ is the transpose of the weight matrix, and $\\sigma'$ is the gradient of the activation function. The gradient of the activation function is a vector of size equal to the hidden state size, and the $\\text{diag}$ converts that vector into a diagonal matrix. You <strong>don't have to worry about the calculus</strong> behind this derivative, and you only need to be familiar with the form it takes.  \n",
    "\n",
    "### Vanishing and Exploding Gradient Conditions\n",
    "\n",
    "When the product \n",
    "\n",
    "$$\\prod_{t\\ge i > k} \\frac{\\partial h_i}{\\partial h_{i-1}} = \\prod_{t\\ge i > k} W_{hh}^T \\text{diag} (\\sigma'(W_{hh} h_{i-1} + W_{hx} x_i + b_h))$$\n",
    "\n",
    "approaches 0, you face vanishing gradient problems where the contribution of item $k$ in the sequence is neglected. Conversely, when the product approaches infinity you will face exploding gradients and convergence problems arise. For that product approaching either of those values, two conditions need to be met:\n",
    "\n",
    "<ol>\n",
    "<li> Derivative of the activation function is bounded by some value $\\alpha$ </li>\n",
    "<li> The absolute value of the largest eigenvalue of the weight matrix $W_{hh}$ is lower than $\\frac{1}{\\alpha}$ (sufficient condition for vanishing gradient), or greater than $\\frac{1}{\\alpha}$ (necessary condition for exploding gradient).</li> \n",
    "</ol>\n",
    "\n",
    "### Activation\n",
    "\n",
    "So let's check the first condition for the sigmoid function. Run the cell below to get an interactive plot of the sigmoid function and its derivative at different points. Feel free to change the argument values to check if the derivative is bounded or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Data\n",
    "\n",
    "### START CODE HERE ###\n",
    "x = np.linspace(-6, 6, 100)  # try changing the range of values in the data. eg: (-100,100,1000)\n",
    "### END CODE HERE ###\n",
    "# Activation\n",
    "# Interval [0, 1]\n",
    "def sigmoid(x):\n",
    "    return 1 / (1 + np.exp(-x))\n",
    "\n",
    "activations = sigmoid(x)\n",
    "\n",
    "# Gradient\n",
    "# Interval [0, 0.25]\n",
    "def sigmoid_gradient(x):\n",
    "    return sigmoid(x) * (1 - sigmoid(x))\n",
    "\n",
    "# Add the tangent line\n",
    "def plot_func(x_tan = 0):\n",
    "    plt.plot(x, activations)\n",
    "    plt.title(\"Sigmoid Function and Gradient\")\n",
    "    plt.xlabel(\"$x$\")\n",
    "    plt.ylabel(\"sigmoid($x$)\")\n",
    "    plt.text(x_tan, sigmoid(x_tan), f\"Gradient: {sigmoid_gradient(x_tan):.4f}\")\n",
    "    plt.xlim((-6,6))\n",
    "    plt.ylim((-0.5,1.5))\n",
    "    plt.rcParams['figure.figsize'] = [7, 5]\n",
    "    y_tan = sigmoid(x_tan)  # y value\n",
    "    span = 4 # line span along x axis\n",
    "    data_tan = np.linspace(x_tan - span, x_tan + span)  # x values to plot\n",
    "    gradient_tan = sigmoid_gradient(x_tan)     # gradient of the tangent\n",
    "    tan = y_tan + gradient_tan * (data_tan - x_tan)     # y values to plot\n",
    "    plt.plot(x_tan, y_tan, marker=\"o\", color=\"orange\", label=True)  # marker\n",
    "    plt.plot(data_tan, tan, linestyle=\"--\", color=\"orange\")         # line\n",
    "    plt.show()\n",
    "\n",
    "interact(plot_func, x_tan = widgets.FloatSlider(value=0,\n",
    "                                            min=-6,\n",
    "                                            max=6,\n",
    "                                            step=0.5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you checked, the derivative of the sigmoid function is bounded by $\\alpha=\\frac{1}{4}$. So vanishing gradient problems will arise for long-term components if the largest eigenvalue of $W_{hh}$ is lower than 4, and exploding gradient problems will happen if the largest eigenvalue is larger than 4. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vanishing Gradient with Sigmoid Activation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's generate a random checkpoint for an RNN model and assume that the sequences are of length $t=20$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(12345)\n",
    "t = 20\n",
    "h = np.random.randn(5,t)\n",
    "x = np.random.randn(5,t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b_h = np.random.randn(5,1)\n",
    "W_hx = np.random.randn(5,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the next cell, you will create a random matrix $W_{hh}$ with eigenvalues lower than four."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eig = np.random.rand(5)*4 #Random eigenvalues lower than 4\n",
    "Q = np.random.randn(5,5) #Random eigenvectors stacked in matrix Q\n",
    "W_hh = Q@np.diag(eig)@np.linalg.inv(Q) #W_hh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, let us define the product function for a determined step $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prod(k):\n",
    "    p = 1 \n",
    "    for i in range(t-1, k-2, -1):\n",
    "        p *= W_hh.T@np.diag(sigmoid_gradient(W_hh@h[:,i]+ W_hx@x[:,i] + b_h))\n",
    "    return p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, you can plot the contribution to the gradient for different steps $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "product = np.zeros(20)\n",
    "for k in range(t):\n",
    "    product[k] = np.max(prod(k+1))\n",
    "\n",
    "plt.plot(np.array(range(t))+1, product)\n",
    "plt.title(\"Maximum contribution to the gradient at step $k$\");\n",
    "plt.xlabel(\"k\");\n",
    "plt.ylabel(\"Maximum contribution\");\n",
    "plt.xticks(np.array(range(t))+1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the largest eigenvalue of the weight matrix $W_{hh}$ being lower than 4 --with a sigmoid activation function, the contribution of the early items in the sequence to the gradient go to zero. In practice, this will make your RNN rely only upon the most recent items in the series. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exploding Gradient with Sigmoid Activation "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An essential difference with the vanishing gradient problem is that the condition for exploding gradients is necessary but not sufficient. Therefore, it is very likely that you will face vanishing gradients rather than exploding gradient problems. However, let's fabricate an example for exploding gradients."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(12345)\n",
    "t = 20\n",
    "h = np.zeros((5,t))\n",
    "x = np.zeros((5,t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b_h = np.zeros((5,1))\n",
    "W_hx = np.random.randn(5,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the next cell, a random matrix $W_{hh}$ with eigenvalues greater than 4 is created"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eig = 4 + np.random.rand(5)*10 #Random eigenvalues greater than 4\n",
    "Q = np.random.randn(5,5) #Random eigenvectors stacked in matrix Q\n",
    "W_hh = Q@np.diag(eig)@np.linalg.inv(Q) #W_hh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, you can plot the contribution to the gradient for different steps $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "product = np.zeros(20)\n",
    "for k in range(t):\n",
    "    product[k] = np.max(prod(k+1))\n",
    "\n",
    "plt.plot(np.array(range(t))+1, product)\n",
    "plt.title(\"Maximum contribution to the gradient at step $k$\");\n",
    "plt.xlabel(\"k\");\n",
    "plt.ylabel(\"Maximum contribution\");\n",
    "plt.xticks(np.array(range(t))+1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the largest eigenvalue of the weight matrix $W_{hh}$ being greater than 4 --with a sigmoid activation function, the contribution of the early items in the sequence to the gradient goes to infinity. In practice, this will make you face convergence problems during training."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you are more familiar with the conditions for vanishing and exploding gradient problems. You should take away that for vanishing gradient it is <strong>sufficient</strong> to satisfy an eigenvalue condition, while for the exploding gradient problem it is <strong>neccesary</strong> but not enough. I used the weight matrix $W_{hh}$ in this discussion, but everything exposed here also applies for $W_{hx}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "One solution is to use RNN architectures specially designed to avoid these problems (like GRUs and LSTMs). Other solutions involve skip-connections or gradient clipping. But those are both discussions for another time."
   ]
  }
 ],
 "metadata": {
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}