Part 4 Backpropagation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align = 'center'> Neural Networks Demystified </h1>\n",
    "<h2 align = 'center'> Part 4: Backpropagation </h2>\n",
    "\n",
    "\n",
    "<h4 align = 'center' > @stephencwelch </h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"400\"\n",
       "            height=\"300\"\n",
       "            src=\"https://www.youtube.com/embed/GlcnxUlrtek\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.YouTubeVideo at 0x103572bd0>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import YouTubeVideo\n",
    "YouTubeVideo('GlcnxUlrtek')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3 align = 'center'> Variables </h3>\n",
    "\n",
    "|Code Symbol | Math Symbol | Definition | Dimensions\n",
    "| :-: | :-: | :-: | :-: |\n",
    "|X|$$X$$|Input Data, each row in an example| (numExamples, inputLayerSize)|\n",
    "|y |$$y$$|target data|(numExamples, outputLayerSize)|\n",
    "|W1 | $$W^{(1)}$$ | Layer 1 weights | (inputLayerSize, hiddenLayerSize) |\n",
    "|W2 | $$W^{(2)}$$ | Layer 2 weights | (hiddenLayerSize, outputLayerSize) |\n",
    "|z2 | $$z^{(2)}$$ | Layer 2 activation | (numExamples, hiddenLayerSize) |\n",
    "|a2 | $$a^{(2)}$$ | Layer 2 activity | (numExamples, hiddenLayerSize) |\n",
    "|z3 | $$z^{(3)}$$ | Layer 3 activation | (numExamples, outputLayerSize) |\n",
    "|J | $$J$$ | Cost | (1, outputLayerSize) |\n",
    "|dJdz3 | $$\\frac{\\partial J}{\\partial z^{(3)} } = \\delta^{(3)}$$ | Partial derivative of cost with respect to $z^{(3)}$ | (numExamples,outputLayerSize)|\n",
    "|dJdW2|$$\\frac{\\partial J}{\\partial W^{(2)}}$$|Partial derivative of cost with respect to $W^{(2)}$|(hiddenLayerSize, outputLayerSize)|\n",
    "|dz3dz2|$$\\frac{\\partial z^{(3)}}{\\partial z^{(2)}}$$|Partial derivative of $z^{(3)}$ with respect to $z^{(2)}$|(numExamples, hiddenLayerSize)|\n",
    "|dJdW1|$$\\frac{\\partial J}{\\partial W^{(1)}}$$|Partial derivative of cost with respect to $W^{(1)}$|(inputLayerSize, hiddenLayerSize)|\n",
    "|delta2|$$\\delta^{(2)}$$|Backpropagating Error 2|(numExamples,hiddenLayerSize)|\n",
    "|delta3|$$\\delta^{(3)}$$|Backpropagating Error 1|(numExamples,outputLayerSize)|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Last time, we decided to use gradient descent to train our Neural Network, so it could make better predictions of your score on a test based on how many hours you slept, and how many hours you studied the night before. To perform gradient descent, we need an equation and some code for our gradient, dJ/dW.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our weights, W, are spread across two matrices, W1 and W2. We’ll separate our dJ/dW computation in the same way, by computing dJdW1 and dJdW2 independently. We should have just as many gradient values as weight values, so when we’re done, our matrices dJdW1 and dJdW2 will be the same size as W1 and W2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(2)}} = \\frac{\\partial \\sum \\frac{1}{2}(y-\\hat{y})^2}{\\partial W^{(2)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s work on dJdW2 first. The sum in our cost function adds the error from each example to create our overall cost. We’ll take advantage of the sum rule in differentiation, which says that the derivative of the sums equals the sum of the derivatives. We can move our sigma outside and just worry about the derivative of the inside expression first. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(2)}} = \\sum \\frac{\\partial \\frac{1}{2}(y-\\hat{y})^2}{\\partial W^{(2)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To keep things simple, we’ll temporarily forget about our summation. Once we’ve computed dJdW for a single example, we’ll add all our individual derivative terms together. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now evaluate our derivative. The power rule tells us to bring down our exponent, 2, and multiply. To finish our derivative, we’ll need to apply the chain rule. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The chain rule tells us how to take the derivative of a function inside of a function, and generally says we take the derivative of the outside function and then multiply it by the derivative of the inside function. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One way to express the chain rule is as the product of derivatives, this will come in very handy as we progress through backpropagation. In fact, a better name for backpropagation might be: don’t stop doing the chain rule. ever. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We’ve taken the derivative of the outside of our cost function - now we need to multiply it by the derivative of the inside."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Y is just our test scores, which won’t change, so the derivative of y, a constant, with respect to W two is 0! yHat, on the other hand, does change with respect to W two, so we’ll apply the chain rule and multiply our results by minus dYhat/dW2. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(2)}} = -(y-\\hat{y}) \\frac{\\partial \\hat{y}}{\\partial W^{(2)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now need to think about the derivative of yHat with respect to W2. Equation 4 tells us that yHat is our activation function of z3, so we it will be helpful to apply the chain rule again to break dyHat/dW2 into dyHat/dz3 times dz3/dW2. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(2)}} = \n",
    "-(y-\\hat{y})\n",
    "\\frac{\\partial \\hat{y}}{\\partial z^{(3)}}  \n",
    "\\frac{\\partial z^{(3)}}{\\partial W^{(2)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To find the rate of change of yHat with respect to z3, we need to differentiate our sigmoid activation function with respect to z. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "f(z) = \\frac{1}{1+e^{-z}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "f^\\prime(z) = \\frac{e^{-z}}{(1+e^{-z})^2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now is a good time to add a new python method for the derivative of our sigmoid function, sigmoid Prime. Our derivative should be the largest where our sigmoid function is the steepest, at the value z equals zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline\n",
    "#Import code from last time\n",
    "from partTwo import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sigmoid(z):\n",
    "     #Apply sigmoid activation function to scalar, vector, or matrix\n",
    "    return 1/(1+np.exp(-z))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sigmoidPrime(z):\n",
    "    #Derivative of sigmoid function\n",
    "    return np.exp(-z)/((1+np.exp(-z))**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x1053eb950>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAEACAYAAACuzv3DAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8Dff6wPHPVzaxBrElEVFB7bFWXe21095bWrTo9ktv\nKaqtbmq7KkWLtrdV1QWluihFucVtlZaUovbatyASEmsFEVkk398fk0ZEliM558w5k+f9ep2XMzlf\nM89j5MnkmZnvKK01Qggh3FcJswMQQghRNFLIhRDCzUkhF0IINyeFXAgh3JwUciGEcHNSyIUQws0V\nWMiVUnOUUmeUUnvyGTNNKXVEKbVLKdXMviEKIYTIjy1H5J8D3fP6UCl1PxCqta4DPAN8YqfYhBBC\n2KDAQq61Xg9czGdID+CLzLGbAT+lVFX7hCeEEKIg9uiRBwKx2ZZPAkF2WK8QQggb2Otkp8qxLPf9\nCyGEk3jaYR2ngBrZloMyv3YTpZQUdyGEKAStdc6D5ZvY44h8GfAkgFKqDZCgtT6TRzCWfY0bN870\nGCQ/yU3y06Sna+LjNdu2af77X81HH2lGjdI8+aSmUydN48aaatU0np4ao3lwe69Bg5ybny0KPCJX\nSs0H/g74K6VigXGAV2ZhnqG1/kEpdb9SKgq4Cjxl05YtJjo62uwQHMrK+Vk5N7BmflevwrFjcPQo\nrFgRzdmzEBVlLMfGQlqabespWxb8/aFy5RuvSpWgQgUoXx78/IxX9vcVKzo2t8IosJBrrfvbMOY5\n+4QjhBA3JCfDwYOwbx/s3XvjlfNn0/btNy9XqgSBgRAUdPOfgYFQtapRsP39oWRJp6XiUPbokQsg\nPDzc7BAcysr5WTk3cJ/80tKMIr1lC2zdavy5fz+kp9861ssLatWC2rXBxyecv//deF+7NoSEQKlS\nTg/fVMrWHkyRN6SUdta2hBCu7+pV2LgR1q6FX3+FHTuMI/DsSpSAOnWgUaObX6Gh4FlMDkOVUugC\nTnZKIbeTyMhI2rdvb3YYDmPl/Fw1N6Xy/d4VFpRbjbSlkBeTn2lCuCcrH/yImxXlB7cckQvhojKP\nxMwOQzhJXvvbliNymcZWCCHcnBRyO4mMjDQ7BIeycn5Wzk0UD1LIhRB2M2nSJAYOHOhy2w0JCeGX\nX35xYkTOJT1yIVyU9Mjtp1atWsyePZuOHTuaHUqepEcuhBDFmBRyO7F6n9XK+Vk5N0eaMmUKQUFB\nlCtXjjvvvJM1a9YQERHBE088kTXmyy+/pGbNmvj7+zNx4kRCQkJYs2YNABERETz88MM88cQTlCtX\njiZNmnDkyBEmTZpE1apVCQ4OZvXq1VnriouLo0ePHlSqVIk6derw2WefZX2Wc7tfffVV1nbfeust\nJ/xrmEsKuRBuSin7vArj0KFDfPTRR2zbto3Lly+zatUqQkJCbroWev/+/QwdOpT58+cTHx/PpUuX\niIuLu2k9K1as4Mknn+TixYs0a9aMbt26AUbRfv311xk0aFDW2H79+hEcHEx8fDyLFy9m9OjRrF27\nNvPf4ubtPvvss8ybN4+4uDguXLjAyZMnC5eom5BCbieueGegPVk5Pyvn5igeHh6kpKSwb98+0tLS\nCA4O5o477ripx7t48WJ69OhB27Zt8fLyYvz48bfc9HLvvffSpUsXPDw86NOnD+fOnWPkyJF4eHjQ\nt29foqOjuXz5MrGxsWzcuJEpU6bg7e1N06ZNGTBgAF9++SXALdt94IEHaNeuHd7e3kyYMIESJaxd\n6qydnRAWprV9XoURGhrK1KlTiYiIoGrVqvTv35/4+PibxsTFxREUdOOpj76+vlSqVOmmMVWqVLnp\nc39//6xi7+vrC0BiYiJxcXFUrFiR0qVLZ40PDg7m1KlbnmFzy3ZLlSp1y3atRgq5nVi9z2rl/Kyc\nmyP179+f9evXc+LECZRSjBgx4qYj7oCAgJtaGteuXePChQuF2lZAQAB//vkniYmJWV+LiYm5qWBn\nHxsbe+MxwklJSYXerruQQi6EuG2HDx9mzZo1pKSk4OPjQ8mSJfHw8LhpTO/evVm+fDmbNm0iNTWV\niIiIQl9OWaNGDdq2bcuoUaNISUlh9+7dzJkzh8cff/yWsb1792bFihVs2LCB1NRUXn/9dTIyMgq1\nXXchhdxOrN5ntXJ+Vs7NUVJSUhg1ahSVK1emevXqnD9/nkmTJgE3Tjw2bNiQDz/8kH79+hEQEEDZ\nsmWpUqUKPj4+WeNy9szzW54/fz7R0dEEBATQq1cvxo8fn3VdePZ1NWzYkI8++ohHH32UgIAAKlas\nSI0aNbAyuSFICBdltRuCEhMTqVChAlFRUdSsWdPscFyO3BDkAqzeZ7VyflbOzWzLly8nKSmJq1ev\n8uqrr9KkSRMp4g4ghVwI4TDLli0jMDCQwMBAjh49yoIFC8wOyZKktSKEi7Jaa0XkT1orQghRjEkh\ntxOr91mtnJ+VcxPFgxRyIYRwc9IjF8JFSY+8eJEeuRBCFGNSyO3E6n1WK+dn5dyczYqPehsyZAgT\nJ04sbGhO4Wl2AEII6xg1apRLbjf7LfwRERG8+eablCxZEk9PTxo0aMB//vMf2rRpk+vf/eSTT+we\nr73JEbmdWH2+DivnZ+XcxK2UUvTv358rV65w7tw52rVrR69evXId6y6TbUkhF0IUirs+6k1rnXVS\n0dPTkyeffJLTp09z4cIFwsPDGTJkCPfffz9lypRh7dq1hIeHM3bsWMBowwUFBfHOO+9QtWpVAgIC\n+P777/nhhx+oV68elSpVypo87K9tTZ48mdDQUPz9/enbty8XL160414wSCG3E6v3Wa2cn7vmpt5Q\ndnkVhlUe9ZaSksLcuXMJDg7OevjE/PnzGTt2LImJibRr1+6WWRrPnDlDSkoKcXFxjB8/ngEDBvDN\nN9+wY8cO1q9fz4QJEzhx4gQA06ZNY9myZaxbt474+HgqVKjA0KFDC/Vvnh8p5EKI2+buj3pbuHAh\nFSpUIDg4mJ07d7J06dKszx588EHuvvtugKwpd7Ov38vLizFjxmTFeOHCBYYNG0bp0qVp0KABDRo0\nYNeuXQB8+umnTJw4kYCAALy8vBg3bhyLFy+2e8tGTnbaidX7rFbOz11z0+PMu8Y8+6Pe9u3bR7du\n3XjvvfduGuOMR71t27btlthsedRb3759s34IZKeUyvWpQ9lVqlTplhirVq16Ux5/PcnoxIkTPPTQ\nQzf9IPH09OTMmTNUr1493+3cDjkiF0IUijs/6u12b7TK+ZuErYKDg1m5ciUXL17MeiUlJdm1iIMU\ncrtx1z6rraycn5VzcxSrPuott/iynxy9XYMHD2b06NHExMQAcO7cOZYtW1aodeVHCrkQ4ra586Pe\ncttufp/l/FpBMWc3bNgwevToQdeuXSlXrhx33303W7ZsyXN8YRU414pSqjswFfAAPtNaT8nxeXng\na6AGRs/9Xa313FzWI3OtCHEbrDbXijzqLX8Om2tFKeUBTAe6Aw2A/kqp+jmGDQX2aq3DgPbAf5RS\nchJVCCGPenOSglorrYEorXW01joNWAD0zDEmAyiX+b4ccEFrfd2+Ybo+q/dZrZyflXMzmzzqzTkK\nOnIOBGKzLZ8E7soxZjqwXCkVB5QFHrFfeEIUT1bpqMyaNYtZs2aZHYblFVTIbfnv1B3YobXuoJSq\nDaxWSjXVWl/JOTA8PJyQkBAA/Pz8CAsLy7qG96+jIndd/utrrhKP5Gf7cvv27V0qHoAXXjCWRfET\nGRnJ3LlzAbLqZUHyPdmplGoDRGitu2cujwIysp/wVEqtACZprTdkLv8CjNBab8uxLjnZKYQNNm+G\ndu3g+nVrnewU+XPkgyW2AXWUUiFKKW+gL5DzIsgYoHPmBqsC9YBjNsZuGVbvs1o5P1fKLSEB+vWD\n68XuLJMoinxbK1rr60qp54CfMC4/nK21PqCUGpT5+QxgAjBXKbUbUMBrWus/HRy3EJajNTzzDERH\nQ4sWsH174e8oFMWLPLNTCBcxYwYMHgxly8KOHRAaanZEwhXY0lqRQi6EC9izB1q3huRk+OYb6N/f\n7IiEq5CHLzuRK/VZHcHK+ZmdW0oKPPaYUcSfftr+Rdzs/BzN6vnZQgq5ECaLiDCOyEND4YMPzI5G\nuCNprQhhoo0b4Z57jPfr10PbtubGI1yPtFaEcGFXr8L//R9kZMDw4VLEReFJIbcTq/fprJyfWbm9\n9hpERUHjxvDGG47bjpX3HVg/P1tIIRfCBD//DB9/DF5e8NVXkDlFtxCFIj1yIZzs6lXjKPz4cZg4\nEcaMMTsi4cqkRy6ECxo3zijiTZsa7RUhikoKuZ1YvU9n5fycmdv27fD++1CiBHz2mdFacTQr7zuw\nfn62kEIuhJOkpcGAAcZVKsOGQcuWZkckrEJ65EI4ydtvw4gREBICe/dC6dJmRyTcgcy1IoSLOHoU\nGjUybsNfuRK6dTM7IuEu5GSnE1m9T2fl/Bydm9bw7LNGEX/sMecXcSvvO7B+fraQQi6Egy1dCqtW\ngZ8fvPee2dEIK5LWihAOlJQE9etDTAxMnw5Dh5odkXA30loRwmSTJxtFPCzMeGiEEI4ghdxOrN6n\ns3J+jsrt6FHjShUwjsY9PByymQJZed+B9fOzhRRyIRzkxReNh0Y8+ST87W9mRyOsTHrkQjjAihXw\nwANQrhwcOgTVqpkdkXBX0iMXwgTJycadm2BMTytFXDiaFHI7sXqfzsr52Tu3adPg2DFo2NA1rlKx\n8r4D6+dnCynkQtjR2bPw5pvG+/ffd86kWEJIj1wIO3r2WfjkE7jvPvjhB7OjEVYgc60I4UT790OT\nJsb73buhQQNz4xHWICc7ncjqfTor52ev3IYPh/R0eOYZ1yriVt53YP38bCGFXAg7WLXKaKWULQsR\nEWZHI4obaa0IUUTp6dCsGezZY9ySP2KE2REJK5HWihBO8PnnRhGvWfPG9eNCOJMUcjuxep/OyvkV\nJberV2HsWOP95MlQsqR9YrInK+87sH5+tpBCLkQRfPABnD4NrVpB375mRyOKK+mRC1FIFy7AHXfA\n5cvwyy/QsaPZEQkrkh65EA40ebJRxLt0kSIuzCWF3E6s3qezcn6Fye3kSfjwQ+P9pEn2jcferLzv\nwPr52UIKuRCF8MYbxlzjjzwCLVqYHY0o7grskSulugNTAQ/gM631lFzGtAfeB7yA81rr9rmMkR65\nsISDB42ZDZUybsuvW9fsiISV2dIj9yxgBR7AdKAzcArYqpRaprU+kG2MH/AR0E1rfVIp5V/00IVw\nXf/+N2RkGLfiSxEXrqCg1kprIEprHa21TgMWAD1zjHkU+E5rfRJAa33e/mG6Pqv36ayc3+3ktnUr\nfPedcb346687LiZ7svK+A+vnZ4uCCnkgEJtt+WTm17KrA1RUSq1VSm1TSj1hzwCFcBVaw8iRxvth\nwyAw53eCECbJt0eulOoNdNdaD8xcfhy4S2v9fLYx04HmQCegFLAJ+IfW+kiOdUmPXLi11auha1fw\n8zOeAFShgtkRieKgyD1yjL54jWzLNTCOyrOLxTjBeQ24ppRaBzQFjuQYR3h4OCEhIQD4+fkRFhZG\n+/btgRu/HsmyLLvi8tq1kZnzqLTntddg1y7Xik+WrbMcGRnJ3LlzAbLqZYG01nm+MAr9USAE8Ab+\nAOrnGHMn8DPGVS2lgD1Ag1zWpa1s7dq1ZofgUFbOz5bcfvhBa9Da31/rK1ccH5M9WXnfaW39/DJr\nZ761Ot8jcq31daXUc8BPmYV6ttb6gFJqUObnM7TWB5VSK4HdQAYwS2u937YfI0K4Pq1vnNgcMQLK\nlDE3HiFykrlWhCjAihXwwANQpYrRGy9d2uyIRHEic60IUURaw7hxxvuRI6WIC9ckhdxO/jpZYVVW\nzi+/3JYtgx07oFo1GDzYeTHZk5X3HVg/P1tIIRciD1rfeP7myJHg62tqOELkSXrkQuRh6VLo1QsC\nAiAqSgq5MIf0yIUopIyMG73xUaOkiAvXJoXcTqzep7NyfrnltmSJ8UDlwEAYMMD5MdmTlfcdWD8/\nW0ghFyKHjIwbvfExY1zzgcpCZCc9ciFy+PZb6NcPatSAI0fAx8fsiERxJj1yIW5Terrx9B8w5h2X\nIi7cgRRyO7F6n87K+WXP7dtv4cABqFkTwsNNC8murLzvwPr52UIKuRCZ0tNh/Hjj/b//Dd7e5sYj\nhK2kRy5Epq+/hieegFq14NAh8PIyOyIhpEcuhM2uX7/RGx87Voq4cC9SyO3E6n06K+cXGRnJvHnG\n3Zu1axtH5VZi5X0H1s/PFlLIRbF3/TpMmGC8f/118CzouVlCuBjpkYtib84cePppqFMH9u+XQi5c\ni/TIhShAWhpMnGi8HzdOirhwT1LI7cTqfTqr5vfFF3D8eCR33mnczWlFVt13f7F6fraQQi6KrdTU\nm3vjHh7mxiNEYUmPXBRbM2YYT/1p0AB275ZCLlyTLT1yKeSiWEpJMU5uxsYat+U/8ojZEQmROznZ\n6URW79NZLb/Zs40i3qgR+PtHmh2OQ1lt3+Vk9fxsIYVcFDvJyfDWW8b7iAgoId8Fws1Ja0UUOx9+\nCC+8AE2awM6dUsiFa5MeuRA5XLtm3IYfH288zu2hh8yOSIj8SY/ciazep7NKfjNmGEW8WTN48EHj\na1bJLS+Sn/VJIRfFxtWrMGmS8X78eFD5HuMI4T6ktSKKjXffheHDoVUr2LxZCrlwD9IjFyJTYqLx\nwIjz5+HHH6F7d7MjEsI20iN3Iqv36dw9v+nTjSLepg1063bzZ+6eW0EkP+uTQi4s7/JleOcd4730\nxoUVSWtFWN7Eicbj29q1g3XrpJAL9yI9clHsXboEISGQkABr1kCHDmZHJMTtkR65E1m9T+eu+U2d\nahTx9u3zLuLumputJD/rk0IuLOviRXjvPeP9G2+YG4sQjiStFWFZY8ca/fHOnWH1arOjEaJw7NJa\nUUp1V0odVEodUUqNyGdcK6XUdaVUr8IEK4Q9XbhgtFVAjsaF9eVbyJVSHsB0oDvQAOivlKqfx7gp\nwEqgWF4TYPU+nbvl9847xk1A3bpB27b5j3W33G6X5Gd9BR2RtwaitNbRWus0YAHQM5dxzwOLgXN2\njk+I23b6NEybZrwfP97cWIRwhnx75EqpPkA3rfXAzOXHgbu01s9nGxMIfA10BOYAy7XWS3JZl/TI\nhVM89xx89JExu+HSpWZHI0TR2KNHbkvlnQqMzKzSimLaWhGu4fhxmDnTuOlnwgSzoxHCOTwL+PwU\nUCPbcg3gZI4xLYAFyrhdzh+4TymVprVelnNl4eHhhISEAODn50dYWBjt27cHbvS53HV56tSplsrH\nXfObM6c9aWnQpUsk588DFPz3s/dYzY7fEcuSn3stR0ZGMnfuXICselmQglornsAhoBMQB2wB+mut\nD+Qx/nOKaWslMjIya6dYkTvkt3ev8fg2T084dMiY7dAW7pBbUUh+7s0ut+grpe7DaJ94ALO11pOU\nUoMAtNYzcowttoVcmO/BB+H772HoUGO2QyGsQOZaEcXG5s3GFLW+vnDsGFSrZnZEQtiHzLXiRNn7\ndFbk6vmNHm38OWzY7RdxV8+tqCQ/65NCLtzezz8bMxv6+cFrr5kdjRDOJ60V4da0hrvugq1b4a23\nYNQosyMSwr6kRy4s79tvoV8/o50SFQWlS5sdkRD2JT1yJ7J6n84V80tJgZEjjffjxxe+iLtibvYk\n+VmfFHLhtj76CKKjoUEDeOops6MRwjzSWhFu6c8/ITTUeHjEihXwj3+YHZEQjiGtFWFZb75pFPGO\nHeH++82ORghzSSG3E6v36Vwpv2PHbty5+c47xgRZReFKuTmC5Gd9UsiF2xk9GlJT4YknoHlzs6MR\nwnzSIxdu5a9b8X184PBhCA42OyIhHEt65MJStIZXXjHev/SSFHEh/iKF3E6s3qdzhfzmz4cNG6BK\nlRvXj9uDK+TmSJKf9UkhF24hMRGGDzfeT5oE5cubG48QrkR65MItjBljzKXSsqXRJy8hhyCimJC5\nVoQlHD1q3L2ZmgobN8Ldd5sdkRDOIyc7ncjqfToz83vllRuXGzqiiMu+c29Wz88WUsiFS1u92nh8\nW+nSMHmy2dEI4ZqktSJcVmoqhIXBgQNGER8xwuyIhHA+aa0It/buu0YRr1MHXnzR7GiEcF1SyO3E\n6n06Z+d37BhMmGC8//hj405OR5F9596snp8tpJALl6M1DB0Kycnw2GPQubPZEQnh2qRHLlzOokXw\nyCPGw5QPHoSqVc2OSAjzSI9cuJ3Ll2HYMOP95MlSxIWwhRRyO7F6n85Z+f373xAfb8xwOHCgUzYp\n+87NWT0/W0ghFy5jwwbjgREeHvDpp3IbvhC2kh65cAnXrhnXjB8+bMyrMnGi2REJ4RqkRy7cxuuv\nG0W8YUMYO9bsaIRwL3JEbieRkZG0b9/e7DAcxpH5bd4Mbdsa73//HVq1su/60zPS2Xt2L9vitrE9\nfjtHLx4l5lIMpxNPk3I9hZSoFHxCffAr6UelUpUIrRjKnZXuJKxaGPfUvIeAsgH2DcjJ5P+me7Pl\niNzTWcEIkZvkZHjqKcjIgNdes18Rv5p6lRWHV7DiyApWRq3kfNL5vAdruHb9GtcSrxGfGM/es3tv\n+ji0Yig96vagd4PetAlqQwklv8gK1yJH5MJUo0YZlxnWqwd//AElSxZ+XVprfj/5O7N3zmbhvoVc\nSb2S9VnN8jVpE9SGlgEtqe9fn+DywQSUDcDXyxevEl6kpKeQkJzAmcQzHL5wmIPnD7L51GY2xG4g\nMTUxaz1B5YIY2HwgA5sPpHrZ6kVJXQibyHzkwqWtWwft24NSsH79jfbK7crQGSw/tJwpG6aw6eSm\nrK+3CWpDn/p9uL/O/dzpfydK5fu9kKvrGdfZfHIz3x34jsX7FxN7ORYAzxKe9GnQh9HtRtO4auPC\nBS6EDWwp5GitnfIyNmVda9euNTsEh7J3fhcvah0crDVoPWZM4daRkZGhl+xfoutPr6+JQBOBrjC5\ngh6+arjef3a/zeuxNbeMjAz989Gfda9ve2mPNzyyttn729561+ldhUvCCeT/pnvLrJ351lfpkQtT\nDB0KMTFGT3zcuNv/+xtjNzJ89XA2xm4EoEa5Grx898sMaD6AMt5l7BytQSlFpzs60emOTsReiuWd\nje8wc/tMvjvwHUsOLOGpsKd4s9ObVCtTzSHbFyIv0loRTjdvHjz+uPGwiJ07jWlqbXU68TQv//Qy\n8/fOB6ByqcqM+/s4BrYYiLeHt4Mizlv8lXimbJjCx1s/Ji0jjTLeZRhzzxheavMSPp4OnLJRFBvS\nIxcuJzoamjY15lSZNQsGDLDt72XoDGZtn8XIX0aSkJyAr6cvr7Z9lVfbvko5n3IOjdkWRy4c4dXV\nr7Ls0DIA6vvX57Men9G2RiEb/0JkstsNQUqp7kqpg0qpI0qpW57TopR6TCm1Sym1Wym1QSnVpLBB\nuyurz/dgj/xSUuDhh40i/tBD8PTTtv29A+cO0G5OOwb/bzAJyQncF3of+57dx/gO4+1SxO2RW51K\ndfi+3/esenwVdSvV5cB5I+bnf3ieKylXCl6BA8n/TesrsJArpTyA6UB3oAHQXylVP8ewY8C9Wusm\nwARgpr0DFe7v5Zdh2zYICYHZs42rVfKToTOYtnkazWc2Z9PJTVQrU42FfRbyv0f/R60KtZwS8+3q\nUrsLuwbvYnS70XiU8GD61uk0+qQRv0b/anZowsIKbK0ope4Gxmmtu2cujwTQWuf6KFylVAVgj9Y6\nKMfXpbVSjC1YAP37g7e3MTlWy5b5jz95+STh/w3nl+O/ABAeFs773d7Hr6SfE6K1j12nd/H0sqfZ\nHr8dheK1v73G+A7jTenlC/dlr9ZKIBCbbflk5tfy8jTwgw3rFcXEgQM3euFTpxZcxOfvmU/jTxrz\ny/Ff8C/lz5JHlvB5z8/dqogDNK3WlE1Pb2LsvWNRSjFlwxTafNaGA+cOmB2asBhbLj+0+TBaKdUB\n+Bfwt9w+Dw8PJyQkBAA/Pz/CwsKy5kj4q8/lrstTp061VD72yq958/b06QNXr0bSsSMMHpz3+OTr\nySy8upDP//gcjkObGm1YOmQp1cpUc2h+2Xusjlj/+A7jqXKuCm+ue5Od7KT5zOYM8R/CA3UfoEOH\nDnbfnrPzM3vZavlFRkYyd+5cgKx6WaCCLjQH2gArsy2PAkbkMq4JEAWE5rEeh1ws7yqsflNCYfK7\nfl3rBx4wbvqpX1/rK1fyHnvg3AHd6ONGmgh0yYkl9YxtM3RGRkbhA74Nztp3l5Iv6fD/hmfdSNR/\ncX99Ofmyw7cr/zfdGzbcEGRLj9wTOAR0AuKALUB/rfWBbGOCgTXA41rr3/NYjy5oW8Ja/ppHpUIF\n2LIFQkNzHzdv9zwGrRjE1bSr1KtUj0UPL7L0be/Z861bqS6LHl5Ek6rF7kIvYSO7XUeulLoPmAp4\nALO11pOUUoMAtNYzlFKfAQ8BMZl/JU1r3TrHOqSQFyN/3fTj4QGrVkHHjreOuZZ2jWErhzFrxywA\nHm38KJ/+41PK+pR1crTOd+j8IR5e9DB7zu6hpGdJpnWfxoDmAwo1H4ywNplrxYms/uvd7eS3ebPW\nPj5GS2X69NzHHDp/SDf9pKkmAu0zwceprZSczNp3SalJeuCygVmtlse+e0xfScmn/1RI8n/TvWFD\na0UmVhZ2deQI/POfxs0/gwbBs8/eOubbvd/SYmYLdp3ZRWjFUH4f8DvPtHim2B2N+nr5MvOBmXz9\n0NeU9irNvD3zaDmzJXvO7DE7NOFm5BZ9YTdnzsDdd8Px49CtGyxfDl5eNz5PuZ7Cyz+9zMfbPgbg\nkYaPMOuBWS5xi73ZDp4/yMOLHmbv2b34evry8T8+Jjws3OywhAuQuVaE01y5YswtvmOHcZ342rVQ\nJtskhMcvHufhRQ+zPX473h7evN/tfYa0HFLsjsLzk5SWxHM/PGdcfolxE9RH939EKa9SJkcmzCQP\nX3ai7NeyWlF++aWkQO/eRhGvXRv+97+bi/iyQ8toPrM52+O3E+IXwoZ/beDZVs+6TBF3lX1XyqsU\nc3rO4fMxdHnQAAAROUlEQVSen+Pr6cvcP+Zy12d3cfD8wSKt11XycxSr52cLKeSiSNLSoG9fWL0a\nqlSBn34y/gRIS0/jtdWv0XNBTxKSE+hRrwc7ntlBy4ACbu0s5sLDwtkycAv1KtVj79m9tJzZkm/2\nfGN2WMKFSWtFFFpamjF/ynffgZ8frFkDzZoZn526fIp+3/Xjt5jf8FAeTOo0iVfbvuoyR+HuIDE1\nkUErBmUV8UEtBjG1+1RKehbhwabC7UiPXDjM9evGdeLffgvly8PPP9+YQ+XnYz/z6HePci7pHAFl\nA1jQewH31LzH3IDdlNaamdtnMmzlMFLSUwirFsaihxcRWjGPu6uE5UiP3Ims3qfLnl9aGvzf/xlF\nvGxZo53SsiWkZ6Qz/tfxdP2qK+eSztGpVid2Dtrp8kXclfedUopBLQex6elN1K5Qmz9O/0GLmS34\nbv93Nq/DlfOzB6vnZwsp5OK2XLsGvXrBN98YJzRXroS77oLYS7F0+rIT4yKNB3CO+/s4fnr8J6qU\nrmJyxNbQrHoztj+znd71e3M55TJ9FvVh2I/DSE1PNTs04QKktSJsdukS9OgB69ZBxYrw44/QujUs\nPbCUp5c9zcXki1QrU40vH/ySLrW7mB2uJWmtmb5lOq+seoW0jDRaBbRiQZ8F3FHhDrNDEw4iPXJh\nN2fPwn33GZcYBgQYV6mE1Eni5Z9eZsb2GQD8o84/+Lzn51QuXdnkaK1vy6ktPLLoEU5cOkEZ7zJM\n6z6N8LBwOZlsQdIjdyIr9+n27oUmTSKzrhPfsAHSKu6i1axWzNg+A28Pbz7o/gHL+y93yyLujvuu\ndWBrdgzaQZ8GfUhMTeRfy/5F74W9OZ90/pax7pjf7bB6fraQQi7ytXIltG1r3H7fujWs/TWNr05M\noOWsluw/t587/e9ky4AtvHDXC3I06GQVfSuysM9CvnjwC8p6l2XpwaU0/qQxPx750ezQhJNJa0Xk\nSmv48EN46SXIyIBHHoHX3t3HoB//j+3x2wEY2mooUzpPobR3aZOjFdEJ0Ty59EnWx6wHYEjLIUzp\nPKVYTAlsddIjF4WSmGjMXPhN5s2E/349nTJd/sPrkWNJTU+lZvmazOk5h461cplkXJgmPSOddze+\ny9i1Y0nLSCO4fDAz/jmD7qHdzQ5NFIH0yJ3IKn26/fuNFso330Dp0vDW5ztYGdSGkZ+NIDU9lYHN\nB7J7yG5LFXGr7DuPEh6MaDeCrQO30qJ6C2IuxXDfvPvoOqErF5IumB2ew1hl/xWFFHIBGK2UL76A\nVq2Mp97Xa3KF3jNf4t8xrdgWtw3/0v78+NiPzHxgpkw76+KaVmvK7wN+5+3Ob1PSsySrj66m/kf1\nmb9nPvJbsTVJa0Vw7pzRSlm6FEBz76D/crTuC5y6cpISqgQv3vUib3R4gzLeZQpalXAxUX9GMXD5\nQCKjIwHoENKBafdNo1GVRuYGJmwmPXJRoO+/h2eeMa4TLxWyl1qDX2Zf8moAWgW0YsY/Z9CsejOT\noxRFkaEzmLNzDiN/HsmFaxfwUB4MbTWUNzq8gV9JP7PDEwWQHrkTuVufLi7OmH72wQfh7NWzBDwz\nmOSnmrIveTV+Jf348L4P2fT0pqwi7m753Q4r5waw7td1DGg+gMPPH2Zoq6FoNNO2TKPuh3WZuX0m\n1zOumx1ikVh9/9lCCnkxk54O06dD/fqwcGkSXu2nUHJ4HeICZqBQPNfqOaKej+K51s/hUcLD7HCF\nHVX0rcj0+6ez45kd3BN8D+eSzjFoxSAaftyQxfsXS//cjUlrpRiJjIRXXoEdu5OhxQx8Ok8ixesM\nAPfXuZ93u7xL/cr1zQ1SOIXWmkX7FzFmzRii/owCoGVASyZ3mkynOzqZHJ3ITnrkAjAuKRwxAlb8\nmALNPsejw0TSS58CjG/eNzu+SdfaXU2OUpghLT2N2Ttn88avb3A68TQA99a8l9HtRtO1dle5W9cF\nSI/ciVyxT3fsGAwYAI1aJrDi4hTUS7Xgn0NIL32KJlWb8H2/79kyYItNRdwV87MXK+cG+efn5eHF\n4JaDiXo+irc6voVfST/WnVhH93ndaTWrFUsOLCFDZzgv2EKw+v6zhRRyCzp8GMLDoU7LWGbHvoJ+\nsQZ0GYkuE0/jKo1Z2GchOwftpEe9HnLEJQAo7V2aUfeM4sSLJ5jcaTJVSldhe/x2ei/sTcOPG/LJ\n1k9ITE00O0yRB2mtWITWsHEjTP0gg+92/oJu/inc+T2USAegY62ODG87nG61u0nxFgW6lnaNOTvn\n8PbGt4m5FANAOZ9yPBX2FENbDaVOpTomR1h8SI+8GEhONh659p9Pz7HH43NoMQMqHgPAQ3nwcMOH\nGd52OM2rNzc5UuGO0tLTWHJgCR9u+ZANsRuyvt61dleeCnuKnvV64uvla2KE1ieF3IkiIyNp3769\nU7alNezcCbPmXuXrbd+TWGse1F4FHsb1wIFlghnS6hn+1exfVC9b3S7bdGZ+zmbl3MB++e2M38n0\nLdP5Zu83JF9PBqC8T3n6NuxLeFg4bYLamPLbntX3ny2F3NNZwYiii42Fed9e49PVP3Oi9EKovxS6\nXQWgBB50r/1Pnm09mO6h3eUacGF3zao3Y3bP2bzd5W0W7F3A3F1z2Ra3jZk7ZjJzx0xq+dWiV/1e\n9GnQh9aBrSmh5BScs8gRuYuLioIvF1/g6y0rOO79PdT+CbyTsj5vXKENz7R5jEcaPiIPOhZOt+/s\nPr7Y9QVf7/6a+MT4rK8Hlg2kV/1e9KzXk3bB7fDx9DExSvcmrRU3dO0arF2XyldrNvNL9M+cK/Mz\nBP0OJW5cAlbbtwVPtHqQx5v2p3bF2iZGK4QhPSOdTSc3sXj/YpYcWELs5disz0p5laJ9SHu61+5O\nt9Bu1KlYR0643wYp5E5U2D5daips2prMot92sPrgRqKuryUj+Ffwvpo1poT2oknZDvxfm570adyD\noHJBdozcNlbuQ1o5N3B+flprtsZtZcmBJfwY9SO7z+y+6fPg8sHcE3wP9wTfQ7vgdtSvXL9IbRir\n7z/pkbugs2c1//sthmU7trAlfiPxHpvQ1XaARxqE3Bjnn9GQe4M689jdnehc5+8yB7hwG0opWge2\npnVgayZ3nkz8lXhWHV3FyqMrWX10NTGXYpi3Zx7z9swDjDlg/lbjb9wVeBfNqzenRUALaRPeJjki\nd5CMDNh/+Bortuxj/ZFd7Du/i/iMXaRW2A2+CTcP1ooKaQ0J829L75b30Cusk92uNhHClaRnpLP3\n7F5+i/mN9THrWR+znrgrcbeMCywbSIuAFjSv1pxGVRrRoHIDQiuG4uXhZULU5pLWihP8eTGddbti\n2HDoMHtOHSYq4RBnrh/masnD6HIxoG7N2Su1CkEezbk76G56tbqbzvVbU75keROiF8JcWmuiE6L5\nLeY3tsdvZ0f8Dnae3pnrXaSeJTypU7EO9SvXp4F/A+pWqkutCrWo5VeL6mWrW/YqGbsUcqVUd2Aq\n4AF8prWeksuYacB9QBIQrrXemcsYtyvkySkZHDmZwO5jceyJieHwmRhiLsVwOjmGhIwYrnnFklHm\npHH99nGgVo4VpHtSJrUOwd5hNKvelI4Nm9I9LIyActXMSKdIrNyHtHJu4H75ZegMjlw4klXU95/b\nz/5z+4lOiEaTSw05Dj6hPtT0q8kdFe6gll8tgssHE1A24KZXeZ/ybnmStcg9cqWUBzAd6AycArYq\npZZprQ9kG3M/EKq1rqOUugv4BGhT5OjtLD1dc+ZiEjFnEjh54SJxfyZw5lIC8QkXiLt8lrNXz/Bn\nylkuZ5whSZ0l1esM2vdc1k02WUplvrLxvBaAzwlf6tXszJ2V69IipC73NqxL0+BalvlV8I8//nCr\nYnA7rJwbuF9+JVQJ6vnXo55/Pfo37p/19aS0JA6dP8T+c/s5cP4AUX9GceziMfZt30dSehKHLxzm\n8IXDea7X19M3q6hXKV2FSr6V8C/lT6VSmX/mWC7nU85tjvILOtnZGojSWkcDKKUWAD2BA9nG9AC+\nANBab1ZK+Smlqmqtzzgg3gL9tvcE/WYPJykjgRSVQKrHRdI9E9A+CbcW5ex8M185qJTy+KRWpxzB\nVPEOpka5YGpXDqZhYDDNategSUgQvl4liYiIICIiwlFpmS4hIaHgQW7KyrmBdfIr5VWKZtWb3fLo\nwYhTEbwy8hWiE6I5nnCc4xePc/LySeIS44i7YrxOXT7F1bSrHL14lKMXj9q0PYWirE9ZyvuUp3zJ\n8ll/9qjbg0EtBzkixUIrqJAHArHZlk8Cd9kwJggwpZAnp6Zyym9R7h+m+eKRWgHPdD98tB+++FHa\nowKVSlalapmqBJavQk3/qtxRtQp3BlWlbmBlfL3lRgYhXF1Zn7I0rtqYxlUb5znmSsqVrMJ+Puk8\n55POc+HahZv/TLqxfDnlctYr+3XxdSq63oRhBRVyW5vaOfs3pjXDm4UG8mLQAqqU8yOggh+BlSpQ\no7IfQf7lKV3ScUU5OjraYet2BVbOz8q5geT3l7I+ZannY7RsbJGekc6V1CtcSr7EpZRLXEq+REJy\nAjX9ahYhWsfI92SnUqoNEKG17p65PArIyH7CUyn1KRCptV6QuXwQ+HvO1opSuVy+IYQQokBFvSFo\nG1BHKRUCxAF9gf45xiwDngMWZBb+hNz64wUFIoQQonDyLeRa6+tKqeeAnzAuP5yttT6glBqU+fkM\nrfUPSqn7lVJRwFXgKYdHLYQQIovTbggSQgjhGE69SFIp9bxS6oBSaq9S6pYbi6xAKfWKUipDKVXR\n7FjsSSn1Tua+26WUWqKUssStqEqp7kqpg0qpI0qpEWbHY09KqRpKqbVKqX2Z33MvmB2TvSmlPJRS\nO5VSy82Oxd4yL+VenPl9tz+zdZ0rpxVypVQHjGvOm2itGwHvOmvbzqKUqgF0AU6YHYsDrAIaaq2b\nAoeBUSbHU2TZbnjrDjQA+iul6psblV2lAS9prRti3KQ31GL5AQwD9mPilXIO9AHwg9a6PtCEm+/f\nuYkzj8iHAJO01mkAWutzTty2s7wHvGZ2EI6gtV6ttf5rUvTNGPcKuLusG94y/1/+dcObJWitT2ut\n/8h8n4hRCALMjcp+lFJBwP3AZ9x6CbRby/yN9x6t9RwwzldqrS/lNd6ZhbwOcK9S6nelVKRSqqUT\nt+1wSqmewEmt9e4CB7u/fwE/mB2EHeR2M1ugSbE4VOaVZ80wfghbxfvAcCCjoIFuqBZwTin1uVJq\nh1JqllKqVF6D7TofuVJqNZDbjFBjMrdVQWvdRinVClgI3GHP7TtaAfmNArpmH+6UoOwon/xGa62X\nZ44ZA6Rqrb9xanCOYcVfx2+hlCoDLAaGZR6Zuz2l1D+Bs1rrnUqp9mbH4wCeQHPgOa31VqXUVGAk\n8Hpeg+1Ga90lr8+UUkOAJZnjtmaeEKyktb5gzxgcKa/8lFKNMH6C7sqcXS0I2K6Uaq21PuvEEIsk\nv/0HoJQKx/hVtpNTAnK8U0CNbMs1MI7KLUMp5QV8B3yttf6v2fHYUVugR+akfSWBckqpL7XWT5oc\nl72cxPgNf2vm8mKMQp4rZ7ZW/gt0BFBK1QW83amI50drvVdrXVVrXUtrXQtjJzR3pyJekMzpjIcD\nPbXWyWbHYydZN7wppbwxbnhbZnJMdqOMo4rZwH6t9VSz47EnrfVorXWNzO+3fsAaCxVxtNangdjM\nWgnGDLT78hrvzEe9zQHmKKX2AKmAZf7Rc2HFX9k/BLyB1Zm/dWzSWj9rbkhFk9cNbyaHZU9/Ax4H\ndiul/npGwCit9UoTY3IUK37PPQ/MyzzIOEo+N1vKDUFCCOHm3GPWdCGEEHmSQi6EEG5OCrkQQrg5\nKeRCCOHmpJALIYSbk0IuhBBuTgq5EEK4OSnkQgjh5v4fkCR/CNy3Sa4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x105344290>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "testValues = np.arange(-5,5,0.01)\n",
    "plot(testValues, sigmoid(testValues), linewidth=2)\n",
    "plot(testValues, sigmoidPrime(testValues), linewidth=2)\n",
    "grid(1)\n",
    "legend(['sigmoid', 'sigmoidPrime'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now replace dyHat/dz3 with f prime of z 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(2)}}= \n",
    "-(y-\\hat{y}) f^\\prime(z^{(3)}) \\frac{\\partial z^{(3)}}{\\partial W^{(2)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our final piece of the puzzle is dz3dW2, this term represents the change of z, our third layer activity, with respect to the weights in the second layer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Z three is the matrix product of our activities, a two, and our weights, w two. The activities from layer two are multiplied by their correspond weights and added together to yield z3. If we focus on a single synapse for a moment, we see a simple linear relationship between W and z, where a is the slope. So for each synapse, dz/dW(2) is just the activation, a on that synapse!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "z^{(3)} = a^{(2)}W^{(2)} \\tag{3}\\\\\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way to think about what the calculus is doing here is that it is “backpropagating” the error to each weight, by multiplying by the activity on each synapses, the weights that contribute more to the error will have larger activations, and yield larger dJ/dW2 values, and those weights will be changed more when we perform gradient descent. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to be careful with our dimensionality here, and if we’re clever, we can take care of that summation we got rid of earlier. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first part of our equation, y minus yHat is of the same dimension as our output data, 3 by 1. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "F prime of z three is of the same size, 3 by 1, and our first operation is scalar multiplication. Our resulting 3 by 1 matrix is referred to as the backpropagating error, delta 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We determined that dz3/dW2 is equal to the activity of each synapse. Each value in delta 3 needs to be multiplied by each activity. We can achieve this by transposing a2 and matrix multiplying by delta3. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(2)}} = \n",
    "(a^{(2)})^T\\delta^{(3)}\\tag{6}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\delta^{(3)} = -(y-\\hat{y}) f^\\prime(z^{(3)}) \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What’s cool here is that the matrix multiplication also takes care of our earlier omission – it adds up the dJ/dW terms across all our examples. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way to think about what’s happening here is that is that each example our algorithm sees has a certain cost and a certain gradient. The gradient with respect to each example pulls our gradient descent algorithm in a certain direction. It's like every example gets a vote on which way is downhill, and when we perform batch gradient descent we just add together everyone’s vote, call it downhill, and move in that direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We’ll code up our gradients in python in a new method, cost function prime. Numpy’s multiply method performs element-wise multiplication, and the dot method performs matrix multiplication."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Part of NN Class (won't work alone, needs to be included in class as \n",
    "# shown in below and in partFour.py):\n",
    "\n",
    "def costFunctionPrime(self, X, y):\n",
    "    #Compute derivative with respect to W and W2 for a given X and y:\n",
    "    self.yHat = self.forward(X)\n",
    "\n",
    "    delta3 = np.multiply(-(y-self.yHat), self.sigmoidPrime(self.z3))\n",
    "    dJdW2 = np.dot(self.a2.T, delta3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have one final term to compute: dJ/dW1. The derivation begins the same way, computing the derivative through our final layer: first dJ/dyHat, then dyHat/dz3, and we called these two taken together form our backpropagating error, delta3. We now take the derivative “across” our synapses, this is a little different from out job last time, computing the derivative with respect to the weights on our synapses. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = (y-\\hat{y})\n",
    "\\frac{\\partial \\hat{y}}{\\partial W^{(1)}}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = (y-\\hat{y})\n",
    "\\frac{\\partial \\hat{y}}{\\partial z^{(3)}}\n",
    "\\frac{\\partial z^{(3)}}{\\partial W^{(1)}}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = -(y-\\hat{y}) f^\\prime(z^{(3)}) \\frac{\\partial z^{(3)}}{\\partial W^{(1)}}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{\\partial z^{(3)}}{\\partial W^{(1)}} = \\frac{\\partial z^{(3)}}{\\partial a^{(2)}}\\frac{\\partial a^{(2)}}{\\partial W^{(1)}}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There’s still a nice linear relationship along each synapse, but now we’re interested in the rate of change of z(3) with respect to a(2). Now the slope is just equal to the weight value for that synapse. We can achieve this mathematically by multiplying by W(2) transpose. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = \\delta^{(3)} \n",
    "(W^{(2)})^{T}\n",
    "\\frac{\\partial a^{(2)}}{\\partial W^{(1)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = \\delta^{(3)} \n",
    "(W^{(2)})^{T}\n",
    "\\frac{\\partial a^{(2)}}{\\partial z^{(2)}}\n",
    "\\frac{\\partial z^{(2)}}{\\partial W^{(1)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our next term to work on is da(2)/dz(2) – this step is just like the derivative across our layer 3 neurons, so we can just multiply by f prime(z2). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = \\delta^{(3)} \n",
    "(W^{(2)})^{T}\n",
    "f^\\prime(z^{(2)})\n",
    "\\frac{\\partial z^{(2)}}{\\partial W^{(1)}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our final computation here is dz2/dW1. This is very similar to our dz3/dW2 computation, there is a simple linear relationship on the synapses between z2 and w1, in this case though, the slope is the input value, X. We can use the same technique as last time by multiplying by X transpose, effectively applying the derivative and adding our dJ/dW1’s together across all our examples. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = \n",
    "X^{T}\n",
    "\\delta^{(3)} \n",
    "(W^{(2)})^{T}\n",
    "f^\\prime(z^{(2)})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{\\partial J}{\\partial W^{(1)}} = \n",
    "X^{T}\\delta^{(2)} \\tag{7}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\delta^{(2)} = \\delta^{(3)} \n",
    "(W^{(2)})^{T}\n",
    "f^\\prime(z^{(2)})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All that’s left is to code this equation up in python. What’s cool here is that if we want to make a deeper neural network, we could just stack a bunch of these operations together. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Whole Class with additions:\n",
    "class Neural_Network(object):\n",
    "    def __init__(self):        \n",
    "        #Define Hyperparameters\n",
    "        self.inputLayerSize = 2\n",
    "        self.outputLayerSize = 1\n",
    "        self.hiddenLayerSize = 3\n",
    "        \n",
    "        #Weights (parameters)\n",
    "        self.W1 = np.random.randn(self.inputLayerSize,self.hiddenLayerSize)\n",
    "        self.W2 = np.random.randn(self.hiddenLayerSize,self.outputLayerSize)\n",
    "        \n",
    "    def forward(self, X):\n",
    "        #Propogate inputs though network\n",
    "        self.z2 = np.dot(X, self.W1)\n",
    "        self.a2 = self.sigmoid(self.z2)\n",
    "        self.z3 = np.dot(self.a2, self.W2)\n",
    "        yHat = self.sigmoid(self.z3) \n",
    "        return yHat\n",
    "        \n",
    "    def sigmoid(self, z):\n",
    "        #Apply sigmoid activation function to scalar, vector, or matrix\n",
    "        return 1/(1+np.exp(-z))\n",
    "    \n",
    "    def sigmoidPrime(self,z):\n",
    "        #Gradient of sigmoid\n",
    "        return np.exp(-z)/((1+np.exp(-z))**2)\n",
    "    \n",
    "    def costFunction(self, X, y):\n",
    "        #Compute cost for given X,y, use weights already stored in class.\n",
    "        self.yHat = self.forward(X)\n",
    "        J = 0.5*sum((y-self.yHat)**2)\n",
    "        return J\n",
    "        \n",
    "    def costFunctionPrime(self, X, y):\n",
    "        #Compute derivative with respect to W and W2 for a given X and y:\n",
    "        self.yHat = self.forward(X)\n",
    "        \n",
    "        delta3 = np.multiply(-(y-self.yHat), self.sigmoidPrime(self.z3))\n",
    "        dJdW2 = np.dot(self.a2.T, delta3)\n",
    "        \n",
    "        delta2 = np.dot(delta3, self.W2.T)*self.sigmoidPrime(self.z2)\n",
    "        dJdW1 = np.dot(X.T, delta2)  \n",
    "        \n",
    "        return dJdW1, dJdW2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So how should we change our W’s to decrease our cost? We can now compute dJ/dW, which tells us which way is uphill in our 9 dimensional optimization space. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "NN = Neural_Network()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "cost1 = NN.costFunction(X,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dJdW1, dJdW2 = NN.costFunctionPrime(X,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.00292997,  0.01709262,  0.05603318],\n",
       "       [ 0.00183221,  0.01376613,  0.04525805]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dJdW1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[-0.05659312],\n",
       "       [-0.13972542],\n",
       "       [-0.19348711]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dJdW2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we move this way by adding a scalar times our derivative to our weights, our cost will increase, and if we do the opposite, subtract our gradient from our weights, we will move downhill and reduce our cost. This simple step downhill is the core of gradient descent and a key part of how even very sophisticated learning algorithms are trained. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "scalar = 3\n",
    "NN.W1 = NN.W1 + scalar*dJdW1\n",
    "NN.W2 = NN.W2 + scalar*dJdW2\n",
    "cost2 = NN.costFunction(X,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.42407153522 0.623202502031\n"
     ]
    }
   ],
   "source": [
    "print cost1, cost2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "dJdW1, dJdW2 = NN.costFunctionPrime(X,y)\n",
    "NN.W1 = NN.W1 - scalar*dJdW1\n",
    "NN.W2 = NN.W2 - scalar*dJdW2\n",
    "cost3 = NN.costFunction(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.623202502031 0.429162161135\n"
     ]
    }
   ],
   "source": [
    "print cost2, cost3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next time we’ll perform numerical gradient checking check to make sure our math is correct. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}