Gradient_Checking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Checking\n",
    "\n",
    "Welcome to the final assignment for this week! In this assignment you'll be implementing gradient checking.\n",
    "\n",
    "By the end of this notebook, you'll be able to:\n",
    "\n",
    "Implement gradient checking to verify the accuracy of your backprop implementation.\n",
    "\n",
    "## Important Note on Submission to the AutoGrader\n",
    "\n",
    "Before submitting your assignment to the AutoGrader, please make sure you are not doing the following:\n",
    "\n",
    "1. You have not added any _extra_ `print` statement(s) in the assignment.\n",
    "2. You have not added any _extra_ code cell(s) in the assignment.\n",
    "3. You have not changed any of the function parameters.\n",
    "4. You are not using any global variables inside your graded exercises. Unless specifically instructed to do so, please refrain from it and use the local variables instead.\n",
    "5. You are not changing the assignment code where it is not required, like creating _extra_ variables.\n",
    "\n",
    "If you do any of the following, you will get something like, `Grader Error: Grader feedback not found` (or similarly unexpected) error upon submitting your assignment. Before asking for help/debugging the errors in your assignment, check for these first. If this is the case, and you don't remember the changes you have made, you can get a fresh copy of the assignment by following these [instructions](https://www.coursera.org/learn/deep-neural-network/supplement/QWEnZ/h-ow-to-refresh-your-workspace)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Table of Contents\n",
    "- [1 - Packages](#1)\n",
    "- [2 - Problem Statement](#2)\n",
    "- [3 - How does Gradient Checking work?](#3)\n",
    "- [4 - 1-Dimensional Gradient Checking](#4)\n",
    "    - [Exercise 1 - forward_propagation](#ex-1)\n",
    "    - [Exercise 2 - backward_propagation](#ex-2)\n",
    "    - [Exercise 3 - gradient_check](#ex-3)\n",
    "- [5 - N-Dimensional Gradient Checking](#5)\n",
    "    - [Exercise 4 - gradient_check_n](#ex-4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='1'></a>\n",
    "## 1 - Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "### v1.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from testCases import *\n",
    "from public_tests import *\n",
    "from gc_utils import sigmoid, relu, dictionary_to_vector, vector_to_dictionary, gradients_to_vector\n",
    "\n",
    "%load_ext autoreload\n",
    "%autoreload 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='2'></a>\n",
    "## 2 - Problem Statement\n",
    "\n",
    "You are part of a team working to make mobile payments available globally, and are asked to build a deep learning model to detect fraud--whenever someone makes a payment, you want to see if the payment might be fraudulent, such as if the user's account has been taken over by a hacker.\n",
    "\n",
    "You already know that backpropagation is quite challenging to implement, and sometimes has bugs. Because this is a mission-critical application, your company's CEO wants to be really certain that your implementation of backpropagation is correct. Your CEO says, \"Give me proof that your backpropagation is actually working!\" To give this reassurance, you are going to use \"gradient checking.\"\n",
    "\n",
    "Let's do it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='3'></a>\n",
    "## 3 - How does Gradient Checking work?\n",
    "Backpropagation computes the gradients $\\frac{\\partial J}{\\partial \\theta}$, where $\\theta$ denotes the parameters of the model. $J$ is computed using forward propagation and your loss function.\n",
    "\n",
    "Because forward propagation is relatively easy to implement, you're confident you got that right, and so you're almost 100% sure that you're computing the cost $J$ correctly. Thus, you can use your code for computing $J$ to verify the code for computing $\\frac{\\partial J}{\\partial \\theta}$.\n",
    "\n",
    "Let's look back at the definition of a derivative (or gradient):$$ \\frac{\\partial J}{\\partial \\theta} = \\lim_{\\varepsilon \\to 0} \\frac{J(\\theta + \\varepsilon) - J(\\theta - \\varepsilon)}{2 \\varepsilon} \\tag{1}$$\n",
    "\n",
    "If you're not familiar with the \"$\\displaystyle \\lim_{\\varepsilon \\to 0}$\" notation, it's just a way of saying \"when $\\varepsilon$ is really, really small.\"\n",
    "\n",
    "You know the following:\n",
    "\n",
    "$\\frac{\\partial J}{\\partial \\theta}$ is what you want to make sure you're computing correctly.\n",
    "You can compute $J(\\theta + \\varepsilon)$ and $J(\\theta - \\varepsilon)$ (in the case that $\\theta$ is a real number), since you're confident your implementation for $J$ is correct.\n",
    "Let's use equation (1) and a small value for $\\varepsilon$ to convince your CEO that your code for computing $\\frac{\\partial J}{\\partial \\theta}$ is correct!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='4'></a>\n",
    "## 4 - 1-Dimensional Gradient Checking\n",
    "\n",
    "Consider a 1D linear function $J(\\theta) = \\theta x$. The model contains only a single real-valued parameter $\\theta$, and takes $x$ as input.\n",
    "\n",
    "You will implement code to compute $J(.)$ and its derivative $\\frac{\\partial J}{\\partial \\theta}$. You will then use gradient checking to make sure your derivative computation for $J$ is correct. \n",
    "\n",
    "<img src=\"images/1Dgrad_kiank.png\" style=\"width:600px;height:250px;\">\n",
    "<caption><center><font color='purple'><b>Figure 1</b>:1D linear model </font></center></caption>\n",
    "\n",
    "The diagram above shows the key computation steps: First start with $x$, then evaluate the function $J(x)$ (\"forward propagation\"). Then compute the derivative $\\frac{\\partial J}{\\partial \\theta}$ (\"backward propagation\"). \n",
    "\n",
    "<a name='ex-1'></a>\n",
    "### Exercise 1 - forward_propagation\n",
    "\n",
    "Implement `forward propagation`. For this simple function compute $J(.)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "0f934d7a5ec9e6a41fc9ece5ec6a07fa",
     "grade": false,
     "grade_id": "cell-a4be88c5c0419ab7",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: forward_propagation\n",
    "\n",
    "def forward_propagation(x, theta):\n",
    "    \"\"\"\n",
    "    Implement the linear forward propagation (compute J) presented in Figure 1 (J(theta) = theta * x)\n",
    "    \n",
    "    Arguments:\n",
    "    x -- a real-valued input\n",
    "    theta -- our parameter, a real number as well\n",
    "    \n",
    "    Returns:\n",
    "    J -- the value of function J, computed using the formula J(theta) = theta * x\n",
    "    \"\"\"\n",
    "    \n",
    "    # (approx. 1 line)\n",
    "    # J = \n",
    "    # YOUR CODE STARTS HERE\n",
    "    \n",
    "    J = theta * x\n",
    "    \n",
    "    # YOUR CODE ENDS HERE\n",
    "    \n",
    "    return J"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c775107f8d8491592913f1991d0fc3da",
     "grade": true,
     "grade_id": "cell-805a7fd19d554221",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "J = 8\n",
      "\u001b[92m All tests passed.\n"
     ]
    }
   ],
   "source": [
    "x, theta = 2, 4\n",
    "J = forward_propagation(x, theta)\n",
    "print (\"J = \" + str(J))\n",
    "forward_propagation_test(forward_propagation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-2'></a>\n",
    "### Exercise 2 - backward_propagation\n",
    "\n",
    "Now, implement the `backward propagation` step (derivative computation) of Figure 1. That is, compute the derivative of $J(\\theta) = \\theta x$ with respect to $\\theta$. To save you from doing the calculus, you should get $dtheta = \\frac { \\partial J }{ \\partial \\theta} = x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "7315e45824efc41770654b46c64c1c14",
     "grade": false,
     "grade_id": "cell-c06a1275399b210f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: backward_propagation\n",
    "\n",
    "def backward_propagation(x, theta):\n",
    "    \"\"\"\n",
    "    Computes the derivative of J with respect to theta (see Figure 1).\n",
    "    \n",
    "    Arguments:\n",
    "    x -- a real-valued input\n",
    "    theta -- our parameter, a real number as well\n",
    "    \n",
    "    Returns:\n",
    "    dtheta -- the gradient of the cost with respect to theta\n",
    "    \"\"\"\n",
    "    \n",
    "    # (approx. 1 line)\n",
    "    # dtheta = \n",
    "    # YOUR CODE STARTS HERE\n",
    "    \n",
    "    dtheta = x\n",
    "    \n",
    "    # YOUR CODE ENDS HERE\n",
    "    \n",
    "    return dtheta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a4b03438ce60ba7d060246c0aed1cab8",
     "grade": true,
     "grade_id": "cell-7b67ed84ac8bfd91",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dtheta = 3\n",
      "\u001b[92m All tests passed.\n"
     ]
    }
   ],
   "source": [
    "x, theta = 3, 4\n",
    "dtheta = backward_propagation(x, theta)\n",
    "print (\"dtheta = \" + str(dtheta))\n",
    "backward_propagation_test(backward_propagation)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Expected output:\n",
    "\n",
    "```\n",
    "dtheta = 3\n",
    " All tests passed.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='ex-3'></a>\n",
    "### Exercise 3 - gradient_check\n",
    "\n",
    "To show that the `backward_propagation()` function is correctly computing the gradient $\\frac{\\partial J}{\\partial \\theta}$, let's implement gradient checking.\n",
    "\n",
    "**Instructions**:\n",
    "- First compute \"gradapprox\" using the formula above (1) and a small value of $\\varepsilon$. Here are the Steps to follow:\n",
    "    1. $\\theta^{+} = \\theta + \\varepsilon$\n",
    "    2. $\\theta^{-} = \\theta - \\varepsilon$\n",
    "    3. $J^{+} = J(\\theta^{+})$\n",
    "    4. $J^{-} = J(\\theta^{-})$\n",
    "    5. $gradapprox = \\frac{J^{+} - J^{-}}{2  \\varepsilon}$\n",
    "- Then compute the gradient using backward propagation, and store the result in a variable \"grad\"\n",
    "- Finally, compute the relative difference between \"gradapprox\" and the \"grad\" using the following formula:\n",
    "$$ difference = \\frac {\\mid\\mid grad - gradapprox \\mid\\mid_2}{\\mid\\mid grad \\mid\\mid_2 + \\mid\\mid gradapprox \\mid\\mid_2} \\tag{2}$$\n",
    "You will need 3 Steps to compute this formula:\n",
    "   - 1'. compute the numerator using np.linalg.norm(...)\n",
    "   - 2'. compute the denominator. You will need to call np.linalg.norm(...) twice.\n",
    "   - 3'. divide them.\n",
    "- If this difference is small (say less than $10^{-7}$), you can be quite confident that you have computed your gradient correctly. Otherwise, there may be a mistake in the gradient computation. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "80dfb6e4c898e29e5b088c5a678eea60",
     "grade": false,
     "grade_id": "cell-ed57ede577f9d607",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: gradient_check\n",
    "\n",
    "def gradient_check(x, theta, epsilon=1e-7, print_msg=False):\n",
    "    \"\"\"\n",
    "    Implement the gradient checking presented in Figure 1.\n",
    "    \n",
    "    Arguments:\n",
    "    x -- a float input\n",
    "    theta -- our parameter, a float as well\n",
    "    epsilon -- tiny shift to the input to compute approximated gradient with formula(1)\n",
    "    \n",
    "    Returns:\n",
    "    difference -- difference (2) between the approximated gradient and the backward propagation gradient. Float output\n",
    "    \"\"\"\n",
    "    \n",
    "    # Compute gradapprox using right side of formula (1). epsilon is small enough, you don't need to worry about the limit.\n",
    "    # (approx. 5 lines)\n",
    "    # theta_plus =                                 # Step 1\n",
    "    # theta_minus =                                # Step 2\n",
    "    # J_plus =                                    # Step 3\n",
    "    # J_minus =                                   # Step 4\n",
    "    # gradapprox =                                # Step 5\n",
    "    # YOUR CODE STARTS HERE\n",
    "    \n",
    "    theta_plus = theta + epsilon                                # Step 1\n",
    "    theta_minus = theta - epsilon                               # Step 2\n",
    "    J_plus = forward_propagation(x, theta_plus)                                   # Step 3\n",
    "    J_minus = forward_propagation(x, theta_minus)                                  # Step 4\n",
    "    gradapprox = (J_plus - J_minus) / (2 * epsilon)                               # Step 5\n",
    "    \n",
    "    # YOUR CODE ENDS HERE\n",
    "    \n",
    "    # Check if gradapprox is close enough to the output of backward_propagation()\n",
    "    #(approx. 1 line) DO NOT USE \"grad = gradapprox\"\n",
    "    # grad =\n",
    "    # YOUR CODE STARTS HERE\n",
    "    \n",
    "    grad = backward_propagation(x, theta)\n",
    "    \n",
    "    # YOUR CODE ENDS HERE\n",
    "    \n",
    "    #(approx. 3 lines)\n",
    "    # numerator =                                 # Step 1'\n",
    "    # denominator =                               # Step 2'\n",
    "    # difference =                                # Step 3'\n",
    "    # YOUR CODE STARTS HERE\n",
    "    \n",
    "    numerator = np.linalg.norm(grad - gradapprox)                                    # Step 1'\n",
    "    denominator = np.linalg.norm(grad) + np.linalg.norm(gradapprox)               # Step 2'\n",
    "    difference =  numerator / denominator                                        # Step 3'\n",
    "    \n",
    "    # YOUR CODE ENDS HERE\n",
    "    if print_msg:\n",
    "        if difference > 2e-7:\n",
    "            print (\"\\033[93m\" + \"There is a mistake in the backward propagation! difference = \" + str(difference) + \"\\033[0m\")\n",
    "        else:\n",
    "            print (\"\\033[92m\" + \"Your backward propagation works perfectly fine! difference = \" + str(difference) + \"\\033[0m\")\n",
    "    \n",
    "    return difference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3b3d8738e60040109feab1c72a71d0c7",
     "grade": true,
     "grade_id": "cell-be0338be7d50dd11",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[92mYour backward propagation works perfectly fine! difference = 7.814075313343006e-11\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "x, theta = 3, 4\n",
    "difference = gradient_check(x, theta, print_msg=True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected output**:\n",
    "\n",
    "<table>\n",
    "    <tr>\n",
    "        <td>  <b> Your backward propagation works perfectly fine!</b>  </td>\n",
    "        <td> difference = 7.814075313343006e-11 </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congrats, the difference is smaller than the $2 * 10^{-7}$ threshold. So you can have high confidence that you've correctly computed the gradient in `backward_propagation()`. \n",
    "\n",
    "Now, in the more general case, your cost function $J$ has more than a single 1D input. When you are training a neural network, $\\theta$ actually consists of multiple matrices $W^{[l]}$ and biases $b^{[l]}$! It is important to know how to do a gradient check with higher-dimensional inputs. Let's do it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name='5'></a>\n",
    "## 5 - N-Dimensional Gradient Checking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "The following figure describes the forward and backward propagation of your fraud detection model.\n",
    "\n",
    "<img src=\"images/NDgrad_kiank.png\" style=\"width:600px;height:400px;\">\n",
    "<caption><center><font color='purple'><b>Figure 2</b>: Deep neural network. LINEAR -> RELU -> LINEAR -> RELU -> LINEAR -> SIGMOID</font></center></caption>\n",
    "\n",
    "Let's look at your implementations for `forward_propagation` and `backward_propagation`. \n",
    "\n",
    "Below is the code provided for `forward_propagation_n`. Note here that `n` in the name implies it is for n-dimensions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward_propagation_n(X, Y, parameters):\n",
    "    \"\"\"\n",
    "    Implements the forward propagation (and computes the cost) presented in Figure 3.\n",
    "    \n",
    "    Arguments:\n",
    "    X -- training set for m examples\n",
    "    Y -- labels for m examples \n",
    "    parameters -- python dictionary containing your parameters \"W1\", \"b1\", \"W2\", \"b2\", \"W3\", \"b3\":\n",
    "                    W1 -- weight matrix of shape (5, 4)\n",
    "                    b1 -- bias vector of shape (5, 1)\n",
    "                    W2 -- weight matrix of shape (3, 5)\n",
    "                    b2 -- bias vector of shape (3, 1)\n",
    "                    W3 -- weight matrix of shape (1, 3)\n",
    "                    b3 -- bias vector of shape (1, 1)\n",
    "    \n",
    "    Returns:\n",
    "    cost -- the cost function (logistic cost for m examples)\n",
    "    cache -- a tuple with the intermediate values (Z1, A1, W1, b1, Z2, A2, W2, b2, Z3, A3, W3, b3)\n",
    "\n",
    "    \"\"\"\n",
    "    \n",
    "    # retrieve parameters\n",
    "    m = X.shape[1]\n",
    "    W1 = parameters[\"W1\"]\n",
    "    b1 = parameters[\"b1\"]\n",
    "    W2 = parameters[\"W2\"]\n",
    "    b2 = parameters[\"b2\"]\n",
    "    W3 = parameters[\"W3\"]\n",
    "    b3 = parameters[\"b3\"]\n",
    "\n",
    "    # LINEAR -> RELU -> LINEAR -> RELU -> LINEAR -> SIGMOID\n",
    "    Z1 = np.dot(W1, X) + b1\n",
    "    A1 = relu(Z1)\n",
    "    Z2 = np.dot(W2, A1) + b2\n",
    "    A2 = relu(Z2)\n",
    "    Z3 = np.dot(W3, A2) + b3\n",
    "    A3 = sigmoid(Z3)\n",
    "\n",
    "    # Cost\n",
    "    log_probs = np.multiply(-np.log(A3),Y) + np.multiply(-np.log(1 - A3), 1 - Y)\n",
    "    cost = 1. / m * np.sum(log_probs)\n",
    "    \n",
    "    cache = (Z1, A1, W1, b1, Z2, A2, W2, b2, Z3, A3, W3, b3)\n",
    "    \n",
    "    return cost, cache"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's look at the code for backward propagation.\n",
    "\n",
    "Below is the code provided for `backward_propagation_n`. Note here that `n` in the name implies it is for n-dimensions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def backward_propagation_n(X, Y, cache):\n",
    "    \"\"\"\n",
    "    Implement the backward propagation presented in figure 2.\n",
    "    \n",
    "    Arguments:\n",
    "    X -- input datapoint, of shape (input size, 1)\n",
    "    Y -- true \"label\"\n",
    "    cache -- cache output from forward_propagation_n()\n",
    "    \n",
    "    Returns:\n",
    "    gradients -- A dictionary with the gradients of the cost with respect to each parameter, activation and pre-activation variables.\n",
    "    \"\"\"\n",
    "    \n",
    "    m = X.shape[1]\n",
    "    (Z1, A1, W1, b1, Z2, A2, W2, b2, Z3, A3, W3, b3) = cache\n",
    "    \n",
    "    dZ3 = A3 - Y\n",
    "    dW3 = 1. / m * np.dot(dZ3, A2.T)\n",
    "    db3 = 1. / m * np.sum(dZ3, axis=1, keepdims=True)\n",
    "    \n",
    "    dA2 = np.dot(W3.T, dZ3)\n",
    "    dZ2 = np.multiply(dA2, np.int64(A2 > 0))\n",
    "    dW2 = 1. / m * np.dot(dZ2, A1.T) * 2\n",
    "    db2 = 1. / m * np.sum(dZ2, axis=1, keepdims=True)\n",
    "    \n",
    "    dA1 = np.dot(W2.T, dZ2)\n",
    "    dZ1 = np.multiply(dA1, np.int64(A1 > 0))\n",
    "    dW1 = 1. / m * np.dot(dZ1, X.T)\n",
    "    db1 = 4. / m * np.sum(dZ1, axis=1, keepdims=True)\n",
    "    \n",
    "    gradients = {\"dZ3\": dZ3, \"dW3\": dW3, \"db3\": db3,\n",
    "                 \"dA2\": dA2, \"dZ2\": dZ2, \"dW2\": dW2, \"db2\": db2,\n",
    "                 \"dA1\": dA1, \"dZ1\": dZ1, \"dW1\": dW1, \"db1\": db1}\n",
    "    \n",
    "    return gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "If you had just implemented these functions, you might not have high confidence whether they work correctly. So let's implement gradient checking to help verify the performance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**How does gradient checking work?**.\n",
    "\n",
    "As in Section 3 and 4, you want to compare \"gradapprox\" to the gradient computed by backpropagation. The formula is still:\n",
    "\n",
    "$$ \\frac{\\partial J}{\\partial \\theta} = \\lim_{\\varepsilon \\to 0} \\frac{J(\\theta + \\varepsilon) - J(\\theta - \\varepsilon)}{2 \\varepsilon} \\tag{1}$$\n",
    "\n",
    "However, $\\theta$ is not a scalar anymore. It is a dictionary called \"parameters\". The  function \"`dictionary_to_vector()`\" has been implemented for you. It converts the \"parameters\" dictionary into a vector called \"values\", obtained by reshaping all parameters (W1, b1, W2, b2, W3, b3) into vectors and concatenating them.\n",
    "\n",
    "The inverse function is \"`vector_to_dictionary`\" which outputs back the \"parameters\" dictionary.\n",
    "\n",
    "<img src=\"images/dictionary_to_vector.png\" style=\"width:600px;height:400px;\">\n",
    "<caption><center><font color='purple'><b>Figure 2</b>: dictionary_to_vector() and vector_to_dictionary(). You will need these functions in gradient_check_n()</font></center></caption>\n",
    "\n",
    "The \"gradients\" dictionary has also been converted into a vector \"grad\" using gradients_to_vector(), so you don't need to worry about that.\n",
    "\n",
    "Now, for every single parameter in your vector, you will apply the same procedure as for the gradient_check exercise. You will store each gradient approximation in a vector `gradapprox`. If the check goes as expected, each value in this approximation must match the real gradient values stored in the `grad` vector. \n",
    "\n",
    "Note that `grad` is calculated using the function `gradients_to_vector`, which uses the gradients outputs of the `backward_propagation_n` function.\n",
    "\n",
    "<a name='ex-4'></a>\n",
    "### Exercise 4 - gradient_check_n\n",
    "\n",
    "Implement the function below.\n",
    "\n",
    "**Instructions**: Here is pseudo-code that will help you implement the gradient check.\n",
    "\n",
    "For each i in num_parameters:\n",
    "- To compute `J_plus[i]`:\n",
    "    1. Set $\\theta^{+}$ to `np.copy(parameters_values)`\n",
    "    2. Set $\\theta^{+}_i$ to $\\theta^{+}_i + \\varepsilon$\n",
    "    3. Calculate $J^{+}_i$ using to `forward_propagation_n(x, y, vector_to_dictionary(`$\\theta^{+}$ `))`.     \n",
    "- To compute `J_minus[i]`: do the same thing with $\\theta^{-}$\n",
    "- Compute $gradapprox[i] = \\frac{J^{+}_i - J^{-}_i}{2 \\varepsilon}$\n",
    "\n",
    "Thus, you get a vector gradapprox, where gradapprox[i] is an approximation of the gradient with respect to `parameter_values[i]`. You can now compare this gradapprox vector to the gradients vector from backpropagation. Just like for the 1D case (Steps 1', 2', 3'), compute: \n",
    "$$ difference = \\frac {\\| grad - gradapprox \\|_2}{\\| grad \\|_2 + \\| gradapprox \\|_2 } \\tag{3}$$\n",
    "\n",
    "**Note**: Use `np.linalg.norm` to get the norms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3e3b202b635b2e5dc4619c1daa0e1f0f",
     "grade": false,
     "grade_id": "cell-1e5a768bc4e28e66",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# GRADED FUNCTION: gradient_check_n\n",
    "\n",
    "def gradient_check_n(parameters, gradients, X, Y, epsilon=1e-7, print_msg=False):\n",
    "    \"\"\"\n",
    "    Checks if backward_propagation_n computes correctly the gradient of the cost output by forward_propagation_n\n",
    "    \n",
    "    Arguments:\n",
    "    parameters -- python dictionary containing your parameters \"W1\", \"b1\", \"W2\", \"b2\", \"W3\", \"b3\"\n",
    "    grad -- output of backward_propagation_n, contains gradients of the cost with respect to the parameters \n",
    "    X -- input datapoint, of shape (input size, number of examples)\n",
    "    Y -- true \"label\"\n",
    "    epsilon -- tiny shift to the input to compute approximated gradient with formula(1)\n",
    "    \n",
    "    Returns:\n",
    "    difference -- difference (2) between the approximated gradient and the backward propagation gradient\n",
    "    \"\"\"\n",
    "    \n",
    "    # Set-up variables\n",
    "    parameters_values, _ = dictionary_to_vector(parameters)\n",
    "    \n",
    "    grad = gradients_to_vector(gradients)\n",
    "    num_parameters = parameters_values.shape[0]\n",
    "    J_plus = np.zeros((num_parameters, 1))\n",
    "    J_minus = np.zeros((num_parameters, 1))\n",
    "    gradapprox = np.zeros((num_parameters, 1))\n",
    "    \n",
    "    # Compute gradapprox\n",
    "    for i in range(num_parameters):\n",
    "        \n",
    "        # Compute J_plus[i]. Inputs: \"parameters_values, epsilon\". Output = \"J_plus[i]\".\n",
    "        # \"_\" is used because the function you have outputs two parameters but we only care about the first one\n",
    "        #(approx. 3 lines)\n",
    "        # theta_plus =                                        # Step 1\n",
    "        # theta_plus[i] =                                     # Step 2\n",
    "        # J_plus[i], _ =                                     # Step 3\n",
    "        # YOUR CODE STARTS HERE\n",
    "        \n",
    "        theta_plus = np.copy(parameters_values)                              # Step 1\n",
    "        theta_plus[i] = theta_plus[i] + epsilon                                    # Step 2\n",
    "        J_plus[i], _ = forward_propagation_n(X, Y, vector_to_dictionary(theta_plus))                     # Step 3\n",
    "        \n",
    "        # YOUR CODE ENDS HERE\n",
    "        \n",
    "        # Compute J_minus[i]. Inputs: \"parameters_values, epsilon\". Output = \"J_minus[i]\".\n",
    "        #(approx. 3 lines)\n",
    "        # theta_minus =                                    # Step 1\n",
    "        # theta_minus[i] =                                 # Step 2        \n",
    "        # J_minus[i], _ =                                 # Step 3\n",
    "        # YOUR CODE STARTS HERE\n",
    "        \n",
    "        theta_minus = np.copy(parameters_values)                                    # Step 1\n",
    "        theta_minus[i] = theta_minus[i] - epsilon                                  # Step 2        \n",
    "        J_minus[i], _ = forward_propagation_n(X, Y, vector_to_dictionary(theta_minus))         # Step 3\n",
    "        \n",
    "        # YOUR CODE ENDS HERE\n",
    "        \n",
    "        # Compute gradapprox[i]\n",
    "        # (approx. 1 line)\n",
    "        # gradapprox[i] = \n",
    "        # YOUR CODE STARTS HERE\n",
    "        \n",
    "        gradapprox[i] = (J_plus[i] - J_minus[i]) / (2 * epsilon)\n",
    "        \n",
    "        # YOUR CODE ENDS HERE\n",
    "    \n",
    "    # Compare gradapprox to backward propagation gradients by computing difference.\n",
    "    # (approx. 3 line)\n",
    "    # numerator =                                             # Step 1'\n",
    "    # denominator =                                           # Step 2'\n",
    "    # difference =                                            # Step 3'\n",
    "    # YOUR CODE STARTS HERE\n",
    "    \n",
    "    numerator = np.linalg.norm(grad - gradapprox)                                            # Step 1'\n",
    "    denominator = np.linalg.norm(grad) + np.linalg.norm(gradapprox)                                          # Step 2'\n",
    "    difference = numerator / denominator                                           # Step 3'\n",
    "    \n",
    "    # YOUR CODE ENDS HERE\n",
    "    if print_msg:\n",
    "        if difference > 2e-7:\n",
    "            print (\"\\033[93m\" + \"There is a mistake in the backward propagation! difference = \" + str(difference) + \"\\033[0m\")\n",
    "        else:\n",
    "            print (\"\\033[92m\" + \"Your backward propagation works perfectly fine! difference = \" + str(difference) + \"\\033[0m\")\n",
    "\n",
    "    return difference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e119ddabcb075e6e3391464b48e11234",
     "grade": true,
     "grade_id": "cell-0d7896ce7c954fc9",
     "locked": true,
     "points": 20,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[93mThere is a mistake in the backward propagation! difference = 0.2850931567761623\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "X, Y, parameters = gradient_check_n_test_case()\n",
    "\n",
    "cost, cache = forward_propagation_n(X, Y, parameters)\n",
    "gradients = backward_propagation_n(X, Y, cache)\n",
    "difference = gradient_check_n(parameters, gradients, X, Y, 1e-7, True)\n",
    "expected_values = [0.2850931567761623, 1.1890913024229996e-07]\n",
    "assert not(type(difference) == np.ndarray), \"You are not using np.linalg.norm for numerator or denominator\"\n",
    "assert np.any(np.isclose(difference, expected_values)), \"Wrong value. It is not one of the expected values\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected output**:\n",
    "\n",
    "<table>\n",
    "    <tr>\n",
    "        <td>  <b> There is a mistake in the backward propagation!</b>  </td>\n",
    "        <td> difference = 0.2850931567761623 </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It seems that there were errors in the `backward_propagation_n` code! Good thing you've implemented the gradient check. Go back to `backward_propagation_n` and try to find/correct the errors *(Hint: check dW2 and db1)*. Rerun the gradient check when you think you've fixed it. Remember, you'll need to re-execute the cell defining `backward_propagation_n()` if you modify the code. \n",
    "\n",
    "Can you get gradient check to declare your derivative computation correct? Even though this part of the assignment isn't graded, you should try to find the bug and re-run gradient check until you're convinced backprop is now correctly implemented. \n",
    "\n",
    "**Notes** \n",
    "- Gradient Checking is slow! Approximating the gradient with $\\frac{\\partial J}{\\partial \\theta} \\approx  \\frac{J(\\theta + \\varepsilon) - J(\\theta - \\varepsilon)}{2 \\varepsilon}$ is computationally costly. For this reason, we don't run gradient checking at every iteration during training. Just a few times to check if the gradient is correct. \n",
    "- Gradient Checking, at least as we've presented it, doesn't work with dropout. You would usually run the gradient check algorithm without dropout to make sure your backprop is correct, then add dropout. \n",
    "\n",
    "Congrats! Now you can be confident that your deep learning model for fraud detection is working correctly! You can even use this to convince your CEO. :) \n",
    "<br>\n",
    "<font color='blue'>\n",
    "    \n",
    "**What you should remember from this notebook**:\n",
    "- Gradient checking verifies closeness between the gradients from backpropagation and the numerical approximation of the gradient (computed using forward propagation).\n",
    "- Gradient checking is slow, so you don't want to run it in every iteration of training. You would usually run it only to make sure your code is correct, then turn it off and use backprop for the actual learning process. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "coursera": {
   "course_slug": "deep-neural-network",
   "graded_item_id": "n6NBD",
   "launcher_item_id": "yfOsE"
  },
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}