part-two-backpropagation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![tinhatben](tinhatben_svg.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Neural Networks & Backpropagation: Part Two\n",
    "\n",
    "This Jupyter notebook has been written to partner with the\n",
    "[tinhatben.com](https://tinhatben.com) article on : [Neural Networks & Backpropagation: Part Two](https://tinhatben.com/2016/09/28/neural-networks-and-backpropagation-part-two/)\n",
    "\n",
    "For more information on data science and machine learning go to\n",
    "[tinhatben.com](https://www.tinhatben.com)\n",
    "\n",
    "This jupyter notebook is licensed under the Mozilla Public License 2.0 if a copy of the license was not provided with this notebook it can be downloaded [here](https://www.mozilla.org/en-US/MPL/2.0/)\n",
    "\n",
    "THIS NOTEBOOK IS PROVIDED UNDER THIS LICENSE ON AN “AS IS” BASIS, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED SOFTWARE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE OR NON-INFRINGING"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Imports\n",
    "from tinhatbenbranding import TINHATBEN_GRAY, TINHATBEN_YELLOW, add_tinhatbendotcom\n",
    "from matplotlib import pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "%matplotlib inline\n",
    "plt.rcParams['figure.figsize'] = 10, 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prettyprintarray(array, format=\"%d\"):\n",
    "    rows, cols = array.shape\n",
    "    msg = \"Shape: %i x %i\\n\" % (rows, cols)\n",
    "    for row in range(rows):\n",
    "        for col in range(cols):\n",
    "            msg += format % (array[row, col])\n",
    "            msg += \"\\t\"\n",
    "        msg += \"\\n\"\n",
    "    \n",
    "    print(msg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Review of Part One: Forward Propagation\n",
    "\n",
    "From the Part One: we have established the following:\n",
    "\n",
    "Given the following inputs, we expect the outputs of our neural network to be:\n",
    "\n",
    "| Input 1 | Input 2 | Output | \n",
    "|---------|:--------|:-------|\n",
    "| 0 | 0 | 0 |\n",
    "| 1 | 0 | 1 |\n",
    "| 0 | 1 | 1 |\n",
    "| 1 | 1 | 1 |\n",
    "\n",
    "We will be constructing a neural network with the following topology and intial weights values.\n",
    "\n",
    "<img src=\"net_all.png\">\n",
    "\n",
    "## Training Data\n",
    "Dividing the training data into inputs and targets where x_train represents the inputs and y_train represents the target outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Training data\n",
    "x_train = np.array([\n",
    "        [0, 0],\n",
    "        [1, 0],   \n",
    "        [0, 1],\n",
    "        [1, 1],\n",
    "    ])\n",
    "\n",
    "y_train = np.array([\n",
    "        [0],\n",
    "        [1],\n",
    "        [1],\n",
    "        [0],\n",
    "    ])\n",
    "\n",
    "# Adding bias to the inputs\n",
    "I = np.hstack((np.ones((x_train.shape[0], 1)),\n",
    "              x_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cost Function\n",
    "We need a cost function to determine the error in the network.  In the article we use the squared error function so:\n",
    "\n",
    "$$ E = \\frac{1}{2}(y_{train} - a_o)^2$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cost_function(outputs, targets):\n",
    "    return 0.5 * ((targets - outputs) ** 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will also need the derivative of the cost function:\n",
    "\n",
    "$$ \\frac{\\partial{E}}{\\partial{a_o}} = a_o - y_{train}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cost_function_prime(outputs, targets):\n",
    "    return outputs - targets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sigmoid Function\n",
    "This is the linearity function to be used for the hidden and output layers in the network\n",
    "\n",
    "$$g(z) = \\frac{1}{1 + e^{-z}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sigmoid(z):\n",
    "    return 1.0 / (1 + np.exp(-z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will also need the derivative of the sigmoid function for later use in backpropagation, so:\n",
    "\n",
    "$$\\frac{\\partial{g}}{\\partial{z}} = \\sigma'(z) = g(z)(1 - g(z))$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sigmoid_prime(z):\n",
    "    return sigmoid(z) * (1 - sigmoid(z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## Initialised Weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Layer 1 weights\n",
    "w1 = 0.1\n",
    "w2 = 0.2\n",
    "w3 = 0.3\n",
    "w4 = 0.4\n",
    "b1 = 0.5\n",
    "b2 = 0.5\n",
    "\n",
    "# Layer 2 weights\n",
    "w5 = 0.01\n",
    "w6 = 0.02\n",
    "b3 = 0.03\n",
    "\n",
    "# Representing the weights as a matrix\n",
    "Weights_hidden = np.array([\n",
    "        [b1, b2],        \n",
    "        [w1, w2],\n",
    "        [w3, w4],\n",
    "    ])\n",
    "\n",
    "Weights_output = np.array([\n",
    "        [b3],\n",
    "        [w5],\n",
    "        [w6],\n",
    "    ])\n",
    "\n",
    "# Store the weights in a list for later use\n",
    "Weights = [Weights_hidden, Weights_output]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Forward Propagation\n",
    "Given the weights and inputs we can now compute the activations for each of the nodes in the network.  Computing all training examples at once using linear algebra:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hidden layer activations\n",
      "a_hidden\n",
      "Shape: 4 x 2\n",
      "0.622\t0.622\t\n",
      "0.646\t0.668\t\n",
      "0.690\t0.711\t\n",
      "0.711\t0.750\t\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Hidden Layer activations\n",
    "h_hidden = np.dot(I, Weights_hidden)\n",
    "a_hidden = sigmoid(h_hidden)\n",
    "print(\"Hidden layer activations\")\n",
    "print(\"a_hidden\")\n",
    "prettyprintarray(a_hidden, format=\"%0.3f\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a_hidden_bias\n",
      "Shape: 4 x 3\n",
      "1.000\t0.622\t0.622\t\n",
      "1.000\t0.646\t0.668\t\n",
      "1.000\t0.690\t0.711\t\n",
      "1.000\t0.711\t0.750\t\n",
      "\n",
      "h_output\n",
      "Shape: 4 x 1\n",
      "0.049\t\n",
      "0.050\t\n",
      "0.051\t\n",
      "0.052\t\n",
      "\n",
      "Network output\n",
      "a_output\n",
      "Shape: 4 x 1\n",
      "0.5122\t\n",
      "0.5125\t\n",
      "0.5128\t\n",
      "0.5130\t\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Output layer activations\n",
    "# Insert the bias term\n",
    "a_hidden_bias = np.hstack((np.ones((a_hidden.shape[0], 1)),\n",
    "                a_hidden))\n",
    "# hidden layer activations with bias\n",
    "print(\"a_hidden_bias\")\n",
    "prettyprintarray(a_hidden_bias, format=\"%0.3f\")\n",
    "h_output = np.dot(a_hidden_bias, Weights_output)\n",
    "\n",
    "print(\"h_output\")\n",
    "prettyprintarray(h_output, format=\"%0.3f\")\n",
    "a_output = sigmoid(h_output)\n",
    "print(\"Network output\")\n",
    "print(\"a_output\")\n",
    "prettyprintarray(a_output, format=\"%0.4f\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computing backpropagation\n",
    "Starting at the output layer for the network and working back, remembering that the intent of backpropagation is to determine how much each weight in the network contributes to the error; providing a means of changing the weights to reduce the error.  \n",
    "\n",
    "So at the output layer:\n",
    "\n",
    "$$\\begin{eqnarray}\n",
    "\\frac{\\partial{E}}{\\partial{h_o}} = \\delta_o & = & (a_o - y_{train})\\sigma'(h_o) \\\\ \\delta_o & = & (a_o - y_{train})g(h_o)(1 - g(h_o))\\\\ \\end{eqnarray}$$\n",
    "\n",
    "So the change in weights in the hidden layer:\n",
    "\n",
    "$$\\frac{\\partial{E}}{\\partial{w_{output}}} = \\delta_oa_{hidden}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "delta_o\n",
      "Shape: 4 x 1\n",
      "0.128\t\n",
      "-0.122\t\n",
      "-0.122\t\n",
      "0.128\t\n",
      "\n",
      "dE/dw_output\n",
      "Shape: 3 x 1\n",
      "0.013\t\n",
      "0.008\t\n",
      "0.008\t\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Output layer\n",
    "# delta_o\n",
    "delta_o = cost_function_prime(a_output, y_train) * sigmoid_prime(h_output)\n",
    "print(\"delta_o\")\n",
    "prettyprintarray(delta_o, format=\"%0.3f\")\n",
    "\n",
    "# Change in error due to weights\n",
    "# dE/dw_output\n",
    "dE_dw_output = np.dot(delta_o.T, a_hidden_bias).T\n",
    "print(\"dE/dw_output\")\n",
    "prettyprintarray(dE_dw_output, format=\"%0.3f\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can determine the change in weights for the hidden layer:\n",
    "\n",
    "$$\\begin{eqnarray}\\frac{\\partial{E}}{\\partial{h_{hidden}}} & = & \\delta_h = \\delta_ow_{output}\\sigma'({h_{hidden}})\\\\\\frac{\\partial{E}}{\\partial{w_{hidden}}} & = & \\delta_hI\\end{eqnarray}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "delta_h\n",
      "Shape: 2 x 4\n",
      "0.000\t-0.000\t-0.000\t0.000\t\n",
      "0.001\t-0.001\t-0.001\t0.000\t\n",
      "\n",
      "dE/dw_hidden\n",
      "Shape: 3 x 2\n",
      "0.000025\t0.000041\t\n",
      "-0.000015\t-0.000060\t\n",
      "0.000003\t-0.000020\t\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# delta_h\n",
    "# Need to strip out the biases in order to calculate the contribution to error at the activation units\n",
    "delta_h = np.dot(Weights[1][1:], delta_o.T) * sigmoid_prime(h_hidden).T\n",
    "print(\"delta_h\")\n",
    "prettyprintarray(delta_h, format=\"%0.3f\")\n",
    "\n",
    "# Change in error due to weights\n",
    "# dE/dw hidden\n",
    "dE_dw_hidden = np.dot(delta_h, I).T\n",
    "print(\"dE/dw_hidden\")\n",
    "prettyprintarray(dE_dw_hidden, format=\"%0.6f\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now we have two matrices of $\\frac{\\partial{E}}{\\partial{W}}$ with the correct size:\n",
    "\n",
    "* we have 3 weights in the output layer (3 x 1 matrix); and\n",
    "* 6 weights in the hidden layer (3 x 2 matrix)\n",
    "\n",
    "### General backprop rule\n",
    "No matter how many hidden layers, we can observe a general pattern with backpropagation.  Where $l$ is the current layer amd $l+1$ is the next layer in the network (and the layer previously calculated during backprop).\n",
    "\n",
    "$$\\begin{eqnarray}\\frac{\\partial{E}}{\\partial{h_l}} & = & \\delta_l = \\delta_{l+1}w_{l+1}\\sigma'(h_l)\\\\ \\frac{\\partial{E}}{\\partial{w_l}} & = & \\delta_la_{l-1}\\end{eqnarray}$$\n",
    "\n",
    "Where:\n",
    "$a_{l-1}$ is the activations of the previous layer, or in the case of the first hidden layer the inputs to the network.\n",
    "\n",
    "## Update The Weights\n",
    "Now that we have determined how much each of the weights contribute to the error we can update the weights, hopefully to improve the predictions made by the network.\n",
    "\n",
    "$$W \\leftarrow W - \\eta\\frac{\\partial{E}}{\\partial{W}}$$\n",
    "\n",
    "We also have a new term $\\eta$, this is the **learning rate**, which defines the size of the step taken down the $\\frac{\\partial{E}}{\\partial{W}}$ gradient; or in other terms how much of the change to apply to the weights.  In neural networks this is a critical parameter.  If the learning rate is too small, the network will take a long time to train; conversely if too large the network may never converge due to instability in the weights.  If you are having issues with your network and are unsure about $\\eta$, a rule of thumb:\n",
    "\n",
    "> Reduce the learning rate\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "New hidden weights\n",
      "Shape: 3 x 2\n",
      "0.500000\t0.500000\t\n",
      "0.100000\t0.200001\t\n",
      "0.300000\t0.400000\t\n",
      "\n",
      "New output weights\n",
      "Shape: 3 x 1\n",
      "0.029874\t\n",
      "0.009919\t\n",
      "0.019921\t\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Define the learning rate\n",
    "eta = 0.01\n",
    "\n",
    "# update the output weights\n",
    "Weights_hidden -= (eta * dE_dw_hidden)\n",
    "Weights_output -= (eta * dE_dw_output)\n",
    "\n",
    "# The new weights\n",
    "print(\"New hidden weights\")\n",
    "prettyprintarray(Weights_hidden, format=\"%0.6f\")\n",
    "\n",
    "print(\"New output weights\")\n",
    "prettyprintarray(Weights_output, format=\"%0.6f\")"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}