notebooks/Backpropagation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Backpropagation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(C) 2018 by [Damir Cavar](http://damir.cavar.me/)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Version:** 1.0, January 2018"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**License:** [Creative Commons Attribution-ShareAlike 4.0 International License](https://creativecommons.org/licenses/by-sa/4.0/) ([CA BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a tutorial related to the L665 course on Machine Learning for NLP focusing on Deep Learning, Spring 2018 at Indiana University."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This material is based on Andrew Trask's tutorial [A Neural Network in 11 lines of Python (Part 1) A bare bones neural network implementation to describe the inner workings of backpropagation](https://iamtrask.github.io/2015/07/12/basic-python-network/). See for more details and explanations on his tutorial page. All copyrights are his, except on a few small comments that I added. I also simplified the code and introduced more intuitive variable names, as well as most likely some errors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another source of information, in fact a good one, is the [ML Cheat Sheet](http://ml-cheatsheet.readthedocs.io/en/latest/index.html). I would recommend to work through both:\n",
    "- [Forewardpropagation](http://ml-cheatsheet.readthedocs.io/en/latest/forwardpropagation.html)\n",
    "- [Backpropagation](http://ml-cheatsheet.readthedocs.io/en/latest/backpropagation.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another good article to read and understand is Andrej Karpathy's [Yes you should understand backprop](https://medium.com/@karpathy/yes-you-should-understand-backprop-e2f06eab496b)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we will use a very simple network to start with. The network will only have one input and one output layer. We want to make the following predictions from the input:\n",
    "\n",
    "| Input  | Output |\n",
    "| ------ |:------:|\n",
    "| 0 0 1  | 0      |\n",
    "| 1 1 1  | 1      |\n",
    "| 1 0 1  | 1      |\n",
    "| 0 1 1  | 0      |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use *Numpy* to compute the network parameters, weights, activation, and outputs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use the *[Sigmoid](http://ml-cheatsheet.readthedocs.io/en/latest/activation_functions.html#sigmoid)* activation function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sigmoid(z):\n",
    "    \"\"\"The sigmoid activation function.\"\"\"\n",
    "    return 1 / (1 + np.exp(-z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could use the [ReLU](http://ml-cheatsheet.readthedocs.io/en/latest/activation_functions.html#activation-relu) activation function instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def relu(z):\n",
    "    \"\"\"The ReLU activation function.\"\"\"\n",
    "    return max(0, z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Sigmoid](http://ml-cheatsheet.readthedocs.io/en/latest/activation_functions.html#sigmoid) activation function introduces non-linearity to the computation. It maps the input value to an output value between $0$ and $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"SigmoidFunction1.png\" style=\"max-width:100%; width: 30%; max-width: none\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The derivative of the sigmoid function is maximal at $x=0$ and minimal for lower or higher values of $x$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"sigmoid_prime.png\" style=\"max-width:100%; width: 25%; max-width: none\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *sigmoid_prime* function returns the derivative of the sigmoid for any given $z$. The derivative of the sigmoid is $z * (1 - z)$. This is basically the slope of the sigmoid function at any given point: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sigmoid_prime(z):\n",
    "    \"\"\"The derivative of sigmoid for z.\"\"\"\n",
    "    return z * (1 - z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define the inputs as rows in *X*. There are three input nodes (three columns per vector in $X$. Each row is one trainig example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 1]\n",
      " [0 1 1]\n",
      " [1 0 1]\n",
      " [1 1 1]]\n"
     ]
    }
   ],
   "source": [
    "X = np.array([ [ 0, 0, 1 ],\n",
    "               [ 0, 1, 1 ],\n",
    "               [ 1, 0, 1 ],\n",
    "               [ 1, 1, 1 ] ])\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The outputs are stored in *y*, where each row represents the output for the corresponding input vector (row) in *X*. The vector is initiated as a single row vector and with four columns and transposed (using the $.T$ method) into a column vector with four rows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0]\n",
      " [0]\n",
      " [1]\n",
      " [1]]\n"
     ]
    }
   ],
   "source": [
    "y = np.array([[0,0,1,1]]).T\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make the outputs deterministic, we seed the random number generator with a constant. This will guarantee that every time you run the code, you will get the same random distribution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create a weight matrix ($Wo$) with randomly initialized weights:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.24685351]\n",
      " [0.11982568]\n",
      " [0.07539415]]\n"
     ]
    }
   ],
   "source": [
    "n_inputs = 3\n",
    "n_outputs = 1\n",
    "#Wo = 2 * np.random.random( (n_inputs, n_outputs) ) - 1\n",
    "Wo = np.random.random( (n_inputs, n_outputs) ) * np.sqrt(2.0/n_inputs)\n",
    "print(Wo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reason for the output weight matrix ($Wo$) to have 3 rows and 1 column is that it represents the weights of the connections from the three input neurons to the single output neuron. The initialization of the weight matrix is random with a mean of $0$ and a variance of $1$. There is a good reason for chosing a mean of zero in the weight initialization. See for details the section on Weight Initialization in the [Stanford course CS231n on Convolutional Neural Networks for Visual Recognition](https://cs231n.github.io/neural-networks-2/#init)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The core representation of this network is basically the weight matrix *Wo*. The rest, input matrix, output vector and so on are components that we need to learning and evaluation. The leraning result is stored in the *Wo* weight matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We loop in the optimization and learning cycle 10,000 times. In the *forward propagation* line we process the entire input matrix for training. This is called **full batch** training. I do not use an alternative variable name to represent the input layer, instead I use the input matrix $X$ directly here. Think of this as the different inputs to the input neurons computed at once. In principle the input or training data could have many more training examples, the code would stay the same."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "l1:\n",
      " [[0.00966793]\n",
      " [0.00786376]\n",
      " [0.99359069]\n",
      " [0.99211756]]\n"
     ]
    }
   ],
   "source": [
    "for n in range(10000):\n",
    "    # forward propagation\n",
    "    l1 = sigmoid(np.dot(X, Wo))\n",
    "    \n",
    "    # compute the loss\n",
    "    l1_error = y - l1\n",
    "    #print(\"l1_error:\\n\", l1_error)\n",
    "    \n",
    "    # multiply the loss by the slope of the sigmoid at l1\n",
    "    l1_delta = l1_error * sigmoid_prime(l1)\n",
    "    #print(\"l1_delta:\\n\", l1_delta)\n",
    "    \n",
    "    #print(\"error:\", l1_error, \"\\nderivative:\", sigmoid(l1, True), \"\\ndelta:\", l1_delta, \"\\n\", \"-\"*10, \"\\n\")\n",
    "    # update weights\n",
    "    Wo += np.dot(X.T, l1_delta)\n",
    "\n",
    "print(\"l1:\\n\", l1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dots in $l1$ represent the lines in the graphic below. The lines represent the slope of the sigmoid in the particular position. The slope is highest with a value $x = 0$ (blue dot). It is rather shallow with $x = 2$ (green dot), and not so shallow and not as high with $x = -1$. All derivatives are between $0$ and $1$, of course, that is, no slope or a maximal slope of $1$. There is no negative slope in a sigmoid function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"sigmoid-deriv-2.png\" style=\"max-width:100%; width: 50%; max-width: none\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The matrix $l1\\_error$ is a 4 by 1 matrix (4 rows, 1 column). The derivative matrix $sigmoid\\_prime(l1)$ is also a 4 by one matrix. The returned matrix of the element-wise product $l1\\_delta$ is also the 4 by 1 matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The product of the error and the slopes **reduces the error of high confidence predictions**. When the sigmoid slope is very shallow, the network had a very high or a very low value, that is, it was rather confident. If the network guessed something close to $x=0, y=0.5$, it was not very confident. Such predictions without confidence are updated most significantly. The other peripheral scores are multiplied with a number closer to $0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the prediction line $l1 = sigmoid(np.dot(X, Wo))$ we compute the dot-product of the input vectors with the weights and compute the sigmoid on the sums.\n",
    "The result of the dot-product is the number of rows of the first matrix ($X$) and the number of columns of the second matrix ($Wo$).\n",
    "In the computation of the difference between the true (or gold) values in $y$ and the \"guessed\" values in $l1$ we have an estimate of the miss."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An example computation for the input $[ 1, 0, 1 ]$ and the weights $[ 9.5, 0.2, -0.1 ]$ and an output of $0.99$: If $y = 1$, the $l1\\_error = y - l2 = 0.01$, and $l1\\_delta = 0.01 * tiny\\_deriv$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"toy_network_deriv.png\" style=\"max-width:100%; width: 40%; max-width: none\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More Complex Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider now a more complicated example where no column has a correlation with the output:\n",
    "\n",
    "| Input  | Output |\n",
    "| ------ |:------:|\n",
    "| 0 0 1  | 0      |\n",
    "| 0 1 1  | 1      |\n",
    "| 1 0 1  | 1      |\n",
    "| 1 1 1  | 0      |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The pattern here is our XOR pattern or problem: If there is a $1$ in either column $1$ or $2$, but not in both, the output is $1$ (XOR over column $1$ and $2$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From our discussion of the XOR problem we remember that this is a *non-linear pattern*, a **one-to-one relationship between a combination of inputs**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To cope with this problem, we need a network with another layer, that is a layer that will combine and transform the input, and an additional layer will map it to the output. We will add a *hidden layer* with randomized weights and then train those to optimize the output probabilities of the table above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will define a new $X$ input matrix that reflects the above table:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 1]\n",
      " [0 1 1]\n",
      " [1 0 1]\n",
      " [1 1 1]]\n"
     ]
    }
   ],
   "source": [
    "X = np.array([[0, 0, 1],\n",
    "              [0, 1, 1],\n",
    "              [1, 0, 1],\n",
    "              [1, 1, 1]])\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also define a new output matrix $y$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0]\n",
      " [1]\n",
      " [1]\n",
      " [0]]\n"
     ]
    }
   ],
   "source": [
    "y = np.array([[ 0, 1, 1, 0]]).T\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We initialize the random number generator with a constant again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Assume that our 3 inputs are mapped to 4 hidden layer ($Wh$) neurons, we have to initialize the hidden layer weights in a 3 by 4 matrix. The outout layer ($Wo$) is a single neuron that is connected to the hidden layer, thus the output layer is a 4 by 1 matrix:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wh:\n",
      " [[3.40497041e-01 5.88142486e-01 9.33866473e-05 2.46853512e-01]\n",
      " [1.19825683e-01 7.53941469e-02 1.52080826e-01 2.82149152e-01]\n",
      " [3.23959286e-01 4.39942021e-01 3.42270888e-01 5.59479379e-01]]\n",
      "Wo:\n",
      " [[0.14456957]\n",
      " [0.62092279]\n",
      " [0.01936595]\n",
      " [0.47409212]]\n"
     ]
    }
   ],
   "source": [
    "n_inputs = 3\n",
    "n_hidden_neurons = 4\n",
    "n_output_neurons = 1\n",
    "Wh = np.random.random( (n_inputs, n_hidden_neurons) )  * np.sqrt(2.0/n_inputs)\n",
    "Wo = np.random.random( (n_hidden_neurons, n_output_neurons) )  * np.sqrt(2.0/n_hidden_neurons)\n",
    "print(\"Wh:\\n\", Wh)\n",
    "print(\"Wo:\\n\", Wo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will loop now 60,000 times to optimize the weights:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error: 0.49962354308293877\n",
      "Error: 0.010185068686370107\n",
      "Error: 0.006740755437297382\n",
      "Error: 0.005345052957883485\n",
      "Error: 0.004547502999833714\n",
      "Error: 0.004017450105072935\n",
      "Error: 0.0036334495140870116\n",
      "Error: 0.003339229754058862\n",
      "Error: 0.003104745370932275\n",
      "Error: 0.002912327550144693\n",
      "Wo:\n",
      " [[-7.07355497]\n",
      " [14.20975817]\n",
      " [-7.01708617]\n",
      " [-7.15528258]]\n",
      "Wh:\n",
      " [[ 6.66182717  6.80494448 -3.00320286  3.65642155]\n",
      " [-3.43419418  6.77518798  6.58168773  3.71366194]\n",
      " [ 0.59089835 -1.96151177  0.18071609 -5.62078292]]\n"
     ]
    }
   ],
   "source": [
    "for i in range(100000):\n",
    "    l1 = sigmoid(np.dot(X, Wh))\n",
    "    l2 = sigmoid(np.dot(l1, Wo))\n",
    "    \n",
    "    l2_error = y - l2\n",
    "    \n",
    "    if (i % 10000) == 0:\n",
    "        print(\"Error:\", np.mean(np.abs(l2_error)))\n",
    "    \n",
    "    # gradient, changing towards the target value\n",
    "    l2_delta = l2_error * sigmoid_prime(l2)\n",
    "    \n",
    "    # compute the l1 contribution by value to the l2 error, given the output weights\n",
    "    l1_error = l2_delta.dot(Wo.T)\n",
    "    \n",
    "    # direction of the l1 target:\n",
    "    # in what direction is the target l1?\n",
    "    l1_delta = l1_error * sigmoid_prime(l1)\n",
    "    \n",
    "    Wo += np.dot(l1.T, l2_delta)\n",
    "    Wh += np.dot(X.T, l1_delta)\n",
    "\n",
    "print(\"Wo:\\n\", Wo)\n",
    "print(\"Wh:\\n\", Wh)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The new computation in this new loop is $l1\\_error = l2\\_delta.dot(Wo.T)$, a **confidence weighted error** from $l2$ to compute an error for $l1$. The computation sends the error across the weights from $l2$ to $l1$. The result is a **contribution weighted error**, because we learn how much each node value in $l1$ **contributed** to the error in $l2$. This step is called **backpropagation**. We update $Wh$ using the same steps we did in the 2 layer implementation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow Andrew Trask's tutorial and some more of the links and examples that he provides on [his website](https://iamtrask.github.io/2015/07/12/basic-python-network/) and work through the [ML Cheat Sheet](http://ml-cheatsheet.readthedocs.io/en/latest/index.html)."
   ]
  }
 ],
 "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.3"
  },
  "latex_metadata": {
   "affiliation": "Indiana University, Bloomington, IN, USA",
   "author": "Damir Cavar",
   "title": "Backpropagation (Neural Networks)"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}