07.2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/udlbook/udlbook/blob/main/Notebooks/Chap07/7_2_Backpropagation.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "L6chybAVFJW2"
   },
   "source": [
    "# **Notebook 7.2: Backpropagation**\n",
    "\n",
    "This notebook runs the backpropagation algorithm on a deep neural network as described in section 7.4 of the book.\n",
    "\n",
    "Work through the cells below, running each cell in turn. In various places you will see the words \"TO DO\". Follow the instructions at these places and make predictions about what is going to happen or write code to complete the functions.\n",
    "\n",
    "Contact me at udlbookmail@gmail.com if you find any mistakes or have any suggestions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "id": "LdIDglk1FFcG"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "nnUoI0m6GyjC"
   },
   "source": [
    "First let's define a neural network.  We'll just choose the weights and biases randomly for now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "id": "WVM4Tc_jGI0Q"
   },
   "outputs": [],
   "source": [
    "# Set seed so we always get the same random numbers\n",
    "np.random.seed(0)\n",
    "\n",
    "# Number of layers\n",
    "K = 5\n",
    "# Number of neurons per layer\n",
    "D = 6\n",
    "# Input layer\n",
    "D_i = 1\n",
    "# Output layer\n",
    "D_o = 1\n",
    "\n",
    "# Make empty lists\n",
    "all_weights = [None] * (K+1)\n",
    "all_biases = [None] * (K+1)\n",
    "\n",
    "# Create input and output layers\n",
    "all_weights[0] = np.random.normal(size=(D, D_i))\n",
    "all_weights[-1] = np.random.normal(size=(D_o, D))\n",
    "all_biases[0] = np.random.normal(size =(D,1))\n",
    "all_biases[-1]= np.random.normal(size =(D_o,1))\n",
    "\n",
    "# Create intermediate layers\n",
    "for layer in range(1,K):\n",
    "  all_weights[layer] = np.random.normal(size=(D,D))\n",
    "  all_biases[layer] = np.random.normal(size=(D,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "id": "jZh-7bPXIDq4"
   },
   "outputs": [],
   "source": [
    "# Define the Rectified Linear Unit (ReLU) function\n",
    "def ReLU(preactivation):\n",
    "  activation = preactivation.clip(0.0)\n",
    "  return activation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5irtyxnLJSGX"
   },
   "source": [
    "Now let's run our random network.  The weight matrices $\\boldsymbol\\Omega_{1\\ldots K}$ are the entries of the list \"all_weights\" and the biases $\\boldsymbol\\beta_{1\\ldots K}$ are the entries of the list \"all_biases\"\n",
    "\n",
    "We know that we will need the preactivations $\\mathbf{f}_{0\\ldots K}$ and the activations $\\mathbf{h}_{1\\ldots K}$ for the forward pass of backpropagation, so we'll store and return these as well.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "id": "LgquJUJvJPaN"
   },
   "outputs": [],
   "source": [
    "def compute_network_output(net_input, all_weights, all_biases):\n",
    "\n",
    "  # Retrieve number of layers\n",
    "  K = len(all_weights) -1\n",
    "\n",
    "  # We'll store the pre-activations at each layer in a list \"all_f\"\n",
    "  # and the activations in a second list \"all_h\".\n",
    "  all_f = [None] * (K+1)\n",
    "  all_h = [None] * (K+1)\n",
    "\n",
    "  #For convenience, we'll set\n",
    "  # all_h[0] to be the input, and all_f[K] will be the output\n",
    "  all_h[0] = net_input\n",
    "\n",
    "  # Run through the layers, calculating all_f[0...K-1] and all_h[1...K]\n",
    "  for layer in range(K):\n",
    "      # Update preactivations and activations at this layer according to eqn 7.16\n",
    "      # Remmember to use np.matmul for matrix multiplications\n",
    "      #print(all_h[layer].shape, all_weights[layer].shape)\n",
    "    \n",
    "      all_f[layer] = np.matmul(all_weights[layer], all_h[layer]) + all_biases[layer]\n",
    "      all_h[layer+1] = ReLU(all_f[layer])\n",
    "\n",
    "  # Compute the output from the last hidden layer\n",
    "  # TO DO -- Replace the line below\n",
    "  all_f[K] = np.matmul(all_weights[K], all_h[K]) + all_biases[K]\n",
    "\n",
    "  # Retrieve the output\n",
    "  net_output = all_f[K]\n",
    "\n",
    "  return net_output, all_f, all_h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "id": "IN6w5m2ZOhnB"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True output = 1.907, Your answer = 1.907\n"
     ]
    }
   ],
   "source": [
    "# Define input\n",
    "net_input = np.ones((D_i,1)) * 1.2\n",
    "# Compute network output\n",
    "net_output, all_f, all_h = compute_network_output(net_input,all_weights, all_biases)\n",
    "print(\"True output = %3.3f, Your answer = %3.3f\"%(1.907, net_output[0,0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "SxVTKp3IcoBF"
   },
   "source": [
    "Now let's define a loss function.  We'll just use the least squares loss function. We'll also write a function to compute dloss_doutput"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "id": "6XqWSYWJdhQR"
   },
   "outputs": [],
   "source": [
    "def least_squares_loss(net_output, y):\n",
    "  return np.sum((net_output-y) * (net_output-y))\n",
    "\n",
    "def d_loss_d_output(net_output, y):\n",
    "    return 2*(net_output -y);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "id": "njF2DUQmfttR"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "y = 20.000 Loss = 327.371\n"
     ]
    }
   ],
   "source": [
    "y = np.ones((D_o,1)) * 20.0\n",
    "loss = least_squares_loss(net_output, y)\n",
    "print(\"y = %3.3f Loss = %3.3f\"%(y, loss))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "98WmyqFYWA-0"
   },
   "source": [
    "Now let's compute the derivatives of the network.  We already computed the forward pass.  Let's compute the backward pass."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "id": "LJng7WpRPLMz"
   },
   "outputs": [],
   "source": [
    "# We'll need the indicator function\n",
    "def indicator_function(x):\n",
    "  x_in = np.array(x)\n",
    "  x_in[x_in>=0] = 1\n",
    "  x_in[x_in<0] = 0\n",
    "  return x_in\n",
    "\n",
    "# Main backward pass routine\n",
    "def backward_pass(all_weights, all_biases, all_f, all_h, y):\n",
    "  # We'll store the derivatives dl_dweights and dl_dbiases in lists as well\n",
    "  all_dl_dweights = [None] * (K+1)\n",
    "  all_dl_dbiases = [None] * (K+1)\n",
    "  # And we'll store the derivatives of the loss with respect to the activation and preactivations in lists\n",
    "  all_dl_df = [None] * (K+1)\n",
    "  all_dl_dh = [None] * (K+1)\n",
    "  # Again for convenience we'll stick with the convention that all_h[0] is the net input and all_f[k] in the net output\n",
    "\n",
    "  # Compute derivatives of the loss with respect to the network output\n",
    "  all_dl_df[K] = np.array(d_loss_d_output(all_f[K],y))\n",
    "\n",
    "  # Now work backwards through the network\n",
    "  for layer in range(K,-1,-1):\n",
    "    # TODO Calculate the derivatives of the loss with respect to the biases at layer from all_dl_df[layer]. (eq 7.21)\n",
    "    # NOTE!  To take a copy of matrix X, use Z=np.array(X)\n",
    "    all_dl_dbiases[layer] = np.array(all_dl_df[layer])\n",
    "    #print('dldbias:',all_dl_dbiases[layer].shape)\n",
    "\n",
    "    # TODO Calculate the derivatives of the loss with respect to the weights at layer from all_dl_df[layer] and all_h[layer] (eq 7.22)\n",
    "    # Don't forget to use np.matmul\n",
    "    #print('dldf', all_dl_df[layer].shape, ', h:', all_h[layer].shape)\n",
    "    all_dl_dweights[layer] = np.matmul(all_dl_df[layer], all_h[layer].T)\n",
    "\n",
    "    # TODO: calculate the derivatives of the loss with respect to the activations from weight and derivatives of next preactivations (second part of last line of eq 7.24)\n",
    "    #print('W:',all_weights[layer].shape) \n",
    "    all_dl_dh[layer] = np.matmul(all_weights[layer].T, all_dl_df[layer])\n",
    "\n",
    "    if layer > 0:\n",
    "      # TODO Calculate the derivatives of the loss with respect to the pre-activation f (use derivative of ReLu function, first part of last line of eq. 7.24)\n",
    "      all_dl_df[layer-1] = indicator_function(all_f[layer-1]) * all_dl_dh[layer]\n",
    "\n",
    "  return all_dl_dweights, all_dl_dbiases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "id": "9A9MHc4sQvbp"
   },
   "outputs": [],
   "source": [
    "all_dl_dweights, all_dl_dbiases = backward_pass(all_weights, all_biases, all_f, all_h, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "id": "PK-UtE3hreAK"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------------------------------------\n",
      "Bias 0, derivatives from backprop:\n",
      "[[ -4.486]\n",
      " [  4.947]\n",
      " [  6.812]\n",
      " [ -3.883]\n",
      " [-24.935]\n",
      " [  0.   ]]\n",
      "Bias 0, derivatives from finite differences\n",
      "[[ -4.486]\n",
      " [  4.947]\n",
      " [  6.812]\n",
      " [ -3.883]\n",
      " [-24.935]\n",
      " [  0.   ]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Bias 1, derivatives from backprop:\n",
      "[[ -0.   ]\n",
      " [-11.297]\n",
      " [  0.   ]\n",
      " [  0.   ]\n",
      " [-10.722]\n",
      " [  0.   ]]\n",
      "Bias 1, derivatives from finite differences\n",
      "[[  0.   ]\n",
      " [-11.297]\n",
      " [  0.   ]\n",
      " [  0.   ]\n",
      " [-10.722]\n",
      " [  0.   ]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Bias 2, derivatives from backprop:\n",
      "[[-0.   ]\n",
      " [-0.   ]\n",
      " [ 0.938]\n",
      " [ 0.   ]\n",
      " [-9.993]\n",
      " [ 0.508]]\n",
      "Bias 2, derivatives from finite differences\n",
      "[[ 0.   ]\n",
      " [ 0.   ]\n",
      " [ 0.938]\n",
      " [ 0.   ]\n",
      " [-9.993]\n",
      " [ 0.508]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Bias 3, derivatives from backprop:\n",
      "[[-0.   ]\n",
      " [-4.8  ]\n",
      " [-1.661]\n",
      " [-0.   ]\n",
      " [ 3.393]\n",
      " [ 5.391]]\n",
      "Bias 3, derivatives from finite differences\n",
      "[[ 0.   ]\n",
      " [-4.8  ]\n",
      " [-1.661]\n",
      " [ 0.   ]\n",
      " [ 3.393]\n",
      " [ 5.391]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Bias 4, derivatives from backprop:\n",
      "[[-0.   ]\n",
      " [ 0.   ]\n",
      " [ 0.   ]\n",
      " [-0.   ]\n",
      " [-5.212]\n",
      " [-0.   ]]\n",
      "Bias 4, derivatives from finite differences\n",
      "[[ 0.   ]\n",
      " [ 0.   ]\n",
      " [ 0.   ]\n",
      " [ 0.   ]\n",
      " [-5.212]\n",
      " [ 0.   ]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Weight 0, derivatives from backprop:\n",
      "[[ -5.383]\n",
      " [  5.937]\n",
      " [  8.174]\n",
      " [ -4.66 ]\n",
      " [-29.922]\n",
      " [  0.   ]]\n",
      "Weight 0, derivatives from finite differences\n",
      "[[ -5.383]\n",
      " [  5.937]\n",
      " [  8.174]\n",
      " [ -4.66 ]\n",
      " [-29.922]\n",
      " [  0.   ]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Weight 1, derivatives from backprop:\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [-32.511  -6.799 -18.282 -34.148 -42.196   0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [-30.856  -6.453 -17.352 -32.409 -40.047   0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]]\n",
      "Weight 1, derivatives from finite differences\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [-32.511  -6.799 -18.282 -34.148 -42.196   0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [-30.856  -6.453 -17.352 -32.409 -40.047   0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Weight 2, derivatives from backprop:\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      5.371   0.      0.      3.145   0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.    -57.233   0.      0.    -33.506   0.   ]\n",
      " [  0.      2.907   0.      0.      1.702   0.   ]]\n",
      "Weight 2, derivatives from finite differences\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      5.371   0.      0.      3.145   0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.    -57.233   0.      0.    -33.506   0.   ]\n",
      " [  0.      2.907   0.      0.      1.702   0.   ]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Weight 3, derivatives from backprop:\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.     -3.674   0.    -42.905 -10.998]\n",
      " [  0.      0.     -1.272   0.    -14.85   -3.807]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      2.597   0.     30.333   7.776]\n",
      " [  0.      0.      4.126   0.     48.188  12.353]]\n",
      "Weight 3, derivatives from finite differences\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.     -3.674   0.    -42.905 -10.998]\n",
      " [  0.      0.     -1.272   0.    -14.85   -3.807]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      2.597   0.     30.333   7.776]\n",
      " [  0.      0.      4.126   0.     48.188  12.353]]\n",
      "Success!  Derivatives match.\n",
      "-----------------------------------------------\n",
      "Weight 4, derivatives from backprop:\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.    -81.635 -49.136   0.    -22.007 -10.146]\n",
      " [  0.      0.      0.      0.      0.      0.   ]]\n",
      "Weight 4, derivatives from finite differences\n",
      "[[  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.      0.      0.      0.      0.      0.   ]\n",
      " [  0.    -81.635 -49.136   0.    -22.007 -10.146]\n",
      " [  0.      0.      0.      0.      0.      0.   ]]\n",
      "Success!  Derivatives match.\n"
     ]
    }
   ],
   "source": [
    "np.set_printoptions(precision=3)\n",
    "# Make space for derivatives computed by finite differences\n",
    "all_dl_dweights_fd = [None] * (K+1)\n",
    "all_dl_dbiases_fd = [None] * (K+1)\n",
    "\n",
    "# Let's test if we have the derivatives right using finite differences\n",
    "delta_fd = 0.000001\n",
    "\n",
    "# Test the dervatives of the bias vectors\n",
    "for layer in range(K):\n",
    "  dl_dbias  = np.zeros_like(all_dl_dbiases[layer])\n",
    "  # For every element in the bias\n",
    "  for row in range(all_biases[layer].shape[0]):\n",
    "    # Take copy of biases  We'll change one element each time\n",
    "    all_biases_copy = [np.array(x) for x in all_biases]\n",
    "    all_biases_copy[layer][row] += delta_fd\n",
    "    network_output_1, *_ = compute_network_output(net_input, all_weights, all_biases_copy)\n",
    "    network_output_2, *_ = compute_network_output(net_input, all_weights, all_biases)\n",
    "    dl_dbias[row] = (least_squares_loss(network_output_1, y) - least_squares_loss(network_output_2,y))/delta_fd\n",
    "  all_dl_dbiases_fd[layer] = np.array(dl_dbias)\n",
    "  print(\"-----------------------------------------------\")\n",
    "  print(\"Bias %d, derivatives from backprop:\"%(layer))\n",
    "  print(all_dl_dbiases[layer])\n",
    "  print(\"Bias %d, derivatives from finite differences\"%(layer))\n",
    "  print(all_dl_dbiases_fd[layer])\n",
    "  if np.allclose(all_dl_dbiases_fd[layer],all_dl_dbiases[layer],rtol=1e-05, atol=1e-08, equal_nan=False):\n",
    "    print(\"Success!  Derivatives match.\")\n",
    "  else:\n",
    "    print(\"Failure!  Derivatives different.\")\n",
    "\n",
    "\n",
    "\n",
    "# Test the derivatives of the weights matrices\n",
    "for layer in range(K):\n",
    "  dl_dweight  = np.zeros_like(all_dl_dweights[layer])\n",
    "  # For every element in the bias\n",
    "  for row in range(all_weights[layer].shape[0]):\n",
    "    for col in range(all_weights[layer].shape[1]):\n",
    "      # Take copy of biases  We'll change one element each time\n",
    "      all_weights_copy = [np.array(x) for x in all_weights]\n",
    "      all_weights_copy[layer][row][col] += delta_fd\n",
    "      network_output_1, *_ = compute_network_output(net_input, all_weights_copy, all_biases)\n",
    "      network_output_2, *_ = compute_network_output(net_input, all_weights, all_biases)\n",
    "      dl_dweight[row][col] = (least_squares_loss(network_output_1, y) - least_squares_loss(network_output_2,y))/delta_fd\n",
    "  all_dl_dweights_fd[layer] = np.array(dl_dweight)\n",
    "  print(\"-----------------------------------------------\")\n",
    "  print(\"Weight %d, derivatives from backprop:\"%(layer))\n",
    "  print(all_dl_dweights[layer])\n",
    "  print(\"Weight %d, derivatives from finite differences\"%(layer))\n",
    "  print(all_dl_dweights_fd[layer])\n",
    "  if np.allclose(all_dl_dweights_fd[layer],all_dl_dweights[layer],rtol=1e-05, atol=1e-08, equal_nan=False):\n",
    "    print(\"Success!  Derivatives match.\")\n",
    "  else:\n",
    "    print(\"Failure!  Derivatives different.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyM2kkHLr00J4Jeypw41sTkQ",
   "include_colab_link": true,
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}