Part 5 Numerical Gradient Checking.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:428444e60ba9811b635469e442acb5a0ee8960c62813907a8cb60f860ccd7747"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h1 align = 'center'> Neural Networks Demystified </h1>\n",
      "<h2 align = 'center'> Part 5: Numerical Gradient Checking </h2>\n",
      "\n",
      "\n",
      "<h4 align = 'center' > @stephencwelch </h4>"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from IPython.display import YouTubeVideo\n",
      "YouTubeVideo('pHMzNW8Agq4')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "\n",
        "        <iframe\n",
        "            width=\"400\"\n",
        "            height=300\"\n",
        "            src=\"https://www.youtube.com/embed/pHMzNW8Agq4\"\n",
        "            frameborder=\"0\"\n",
        "            allowfullscreen\n",
        "        ></iframe>\n",
        "        "
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "<IPython.lib.display.YouTubeVideo at 0x10942a450>"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Last time, we did a bunch of calculus to find the rate of change of our cost, J, with respect to our parameters, W. Although each calculus step was pretty straight forward, it\u2019s still easy to make mistakes. What\u2019s worse, is that our network doesn\u2019t have a good way to tell us that it\u2019s broken \u2013 code with incorrectly implemented gradients may appear to be functioning just fine."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is the most nefarious kind of error when building complex systems. Big, in-your-face errors suck initially, but it\u2019s clear that you must fix this error for your work to succeed. More subtle errors can be more troublesome because they hide in your code and steal hours of your time, slowly degrading performance, while you wonder what the problem is. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A good solution here is to test the gradient computation part of our code, just as developer would unit test new portions of their code. We\u2019ll combine a simple understanding of the derivative with some mild cleverness to perform numerical gradient checking. If our code passes this test, we can be quite confident that we have computed and coded up our gradients correctly. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To get started, let\u2019s quickly review derivatives. Derivates tell us the slope, or how steep a function is. Once you\u2019re familiar with calculus, it\u2019s easy to take for granted the inner workings of the derivative - we just accept that the derivative of x^2 is 2x by the power rule. However, depending on how mean your calculus teacher was, you may have spent months not being taught the power rule, and instead required to compute derivatives using the definition. Taking derivatives this way is a bit tedious, but still important - it provides us a deeper understanding of what a derivative is, and it\u2019s going to help us solve our current problem. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The definition of the derivative is really a glorified slope formula. The numerator gives us the change in y values, while the denominator is convenient way to express the change in x values. By including the limit, we are applying the slope formula across an infinitely small region \u2013 it\u2019s like zooming in on our function, until it becomes linear. \n",
      "\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The definition tells us to zoom in until our x distance is infinitely small, but computers can\u2019t really handle infinitely small numbers, especially when they\u2019re in the bottom parts of fractions - if we try to plug in something too small, we will quickly lose precision. The good news here is that if we plug in something reasonable small, we can still get surprisingly good numerical estimates of the derivative. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We\u2019ll modify our approach slightly by picking a point in the middle of the interval we would like to test, and call the distance we move in each direction epsilon. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let\u2019s test our method with a simple function, x squared. We\u2019ll choose a reasonable small value for epsilon, and compute the slope of x^2 at a given point by finding the function value just above and just below our test point. We can then compare our result to our symbolic derivative 2x, at the test point. If the numbers match, we\u2019re in business!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Import Code from previous videos:\n",
      "from partFour import *"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def f(x):\n",
      "    return x**2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "epsilon = 1e-4\n",
      "x = 1.5"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "numericalGradient = (f(x+epsilon)- f(x-epsilon))/(2*epsilon)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "numericalGradient, 2*x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "(2.9999999999996696, 3.0)"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Add helper functions to our neural network class: "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "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\n",
      "    \n",
      "    #Helper Functions for interacting with other classes:\n",
      "    def getParams(self):\n",
      "        #Get W1 and W2 unrolled into vector:\n",
      "        params = np.concatenate((self.W1.ravel(), self.W2.ravel()))\n",
      "        return params\n",
      "    \n",
      "    def setParams(self, params):\n",
      "        #Set W1 and W2 using single paramater vector.\n",
      "        W1_start = 0\n",
      "        W1_end = self.hiddenLayerSize * self.inputLayerSize\n",
      "        self.W1 = np.reshape(params[W1_start:W1_end], (self.inputLayerSize , self.hiddenLayerSize))\n",
      "        W2_end = W1_end + self.hiddenLayerSize*self.outputLayerSize\n",
      "        self.W2 = np.reshape(params[W1_end:W2_end], (self.hiddenLayerSize, self.outputLayerSize))\n",
      "        \n",
      "    def computeGradients(self, X, y):\n",
      "        dJdW1, dJdW2 = self.costFunctionPrime(X, y)\n",
      "        return np.concatenate((dJdW1.ravel(), dJdW2.ravel()))\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can use the same approach to numerically evaluate the gradient of our neural network. It\u2019s a little more complicated this time, since we have 9 gradient values, and we\u2019re interested in the gradient of our cost function. We\u2019ll make things simpler by testing one gradient at a time. We\u2019ll \u201cperturb\u201d each weight - adding epsilon to the current value and  computing the cost function, subtracting epsilon from the current value and computing the cost function, and then computing the slope between these two values. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def computeNumericalGradient(N, X, y):\n",
      "        paramsInitial = N.getParams()\n",
      "        numgrad = np.zeros(paramsInitial.shape)\n",
      "        perturb = np.zeros(paramsInitial.shape)\n",
      "        e = 1e-4\n",
      "\n",
      "        for p in range(len(paramsInitial)):\n",
      "            #Set perturbation vector\n",
      "            perturb[p] = e\n",
      "            N.setParams(paramsInitial + perturb)\n",
      "            loss2 = N.costFunction(X, y)\n",
      "            \n",
      "            N.setParams(paramsInitial - perturb)\n",
      "            loss1 = N.costFunction(X, y)\n",
      "\n",
      "            #Compute Numerical Gradient\n",
      "            numgrad[p] = (loss2 - loss1) / (2*e)\n",
      "\n",
      "            #Return the value we changed to zero:\n",
      "            perturb[p] = 0\n",
      "            \n",
      "        #Return Params to original value:\n",
      "        N.setParams(paramsInitial)\n",
      "\n",
      "        return numgrad "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We\u2019ll repeat this process across all our weights, and when we\u2019re done we\u2019ll have a numerical gradient vector, with the same number of values as we have weights. It\u2019s this vector we would like to compare to our official gradient calculation. We see that our vectors appear very similar, which is a good sign, but we need to quantify just how similar they are. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "NN = Neural_Network()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "numgrad = computeNumericalGradient(NN, X, y)\n",
      "numgrad"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "array([ 0.00108266,  0.00282183,  0.0023393 ,  0.00172423,  0.00484326,\n",
        "        0.00358675,  0.00780005,  0.01335848,  0.01554413])"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "grad = NN.computeGradients(X,y)\n",
      "grad"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "array([ 0.00108266,  0.00282183,  0.0023393 ,  0.00172423,  0.00484326,\n",
        "        0.00358675,  0.00780005,  0.01335848,  0.01554413])"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A nice way to do this is to divide the norm of the difference by the norm of the sum of the vectors we would like to compare. Typical results should be on the order of 10^-8 or less if you\u2019ve computed your gradient correctly. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "norm(grad-numgrad)/norm(grad+numgrad)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "4.3787229004079797e-10"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "And that\u2019s it, we can now check our computations and eliminate gradient errors before they become a problem. Next time we\u2019ll train our Neural Network. "
     ]
    }
   ],
   "metadata": {}
  }
 ]
}