cs231n-two-layer-backprop-math.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# cs231n Two-Layer Backprop Mathematics Example\n",
    "In this notebook I attempt to connect the mathematics of backprop to the variables and network from the Two-Layer Neural Network assigment supplied here: http://cs231n.stanford.edu/assignments/2017/spring1617_assignment1.zip. Each significant variable has a section explaining the math used to calculate the variable's content in the case where the network has the following starting conditions:\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\mathit{x} &= \\begin{bmatrix}16 & -6\\end{bmatrix} &\n",
    "\\mathit{y} &= 2 \\\\\n",
    "\\mathit{W1} &= \\begin{bmatrix}0.18 & 0.04 \\\\ 0.1 & 0.22\\end{bmatrix} &\n",
    "\\mathit{b1} &= \\begin{bmatrix}0 & 0\\end{bmatrix} \\\\\n",
    "\\mathit{W2} &= \\begin{bmatrix}0.19 & -0.1 & 0.1 \\\\ -0.02 & -0.01 & 0.04\\end{bmatrix} &\n",
    "\\mathit{b2} &= \\begin{bmatrix}0 & 0 & 0\\end{bmatrix}\n",
    "\\end{align*}$$\n",
    "\n",
    "I'll also check the calculations when possible with a completed `cs231n/classifiers/neural_net.py` that has the starting conditions hardcoded. \n",
    "\n",
    "A description of the network can be found here https://cs231n.github.io/neural-networks-case-study/#net although the variable names don't exactly match the assignment (I'm pretty sure you can figure out what's what). This diagram of the network may also help with intuitive understanding (gradients are in dark red):\n",
    "![two-layer-net.png](cs231n/two-layer-net.png)\n",
    "\n",
    "**Sections**\n",
    "- [Forward Pass](#fp)\n",
    "    - [h1](#h1)\n",
    "    - [scores](#scores)\n",
    "    - [loss](#loss)\n",
    "- [Backward Pass](#bp)\n",
    "    - [dscores](#dscores)\n",
    "    - [grads\\['W2'\\]](#dW2)\n",
    "    - [grads\\['b2'\\]](#db2)\n",
    "    - [dh1](#dh1)\n",
    "    - [dh1\\[h1 <= 0\\] = 0](#dh1_1)\n",
    "    - [grads\\['W1'\\]](#dW1)\n",
    "    - [grads\\['b1'\\]](#db1)\n",
    "\n",
    "**Notes**\n",
    "- indexing subscripts start at $0$ for matrices and vectors to make relating back to code easier\n",
    "- for now, I don't include regularization\n",
    "- gradients use [denominator-layout notation](https://en.wikipedia.org/wiki/Matrix_calculus#Layout_conventions) -- I assume this is so weights can be easily updated with addition\n",
    "- There are multiple sections where the multivariable chain rule is used but most of the partial derivatives are $0$, so I don't explicitly write it out. For example, in the section [grads\\['W2'\\]](#dW2), $loss$ is a function of the three variables $scores_0, scores_1, scores_2$, so by the multivariable chain rule we can get:\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{00}}}}\n",
    "&= \n",
    "\\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{scores_0}}{\\partial{\\mathit{W2_{00}}}} +\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} \\frac{\\partial{scores_1}}{\\partial{\\mathit{W2_{00}}}} +\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}} \\frac{\\partial{scores_2}}{\\partial{\\mathit{W2_{00}}}} \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{}}{\\partial{\\mathit{W2_{00}}}}(\\mathit{h1_0} \\mathit{W2_{00}} + \\mathit{h1_1} \\mathit{W2_{10}} + \\mathit{b2_0}) \\\\\n",
    "&+ \\frac{\\partial{loss}}{\\partial{scores_1}} \\frac{\\partial{}}{\\partial{\\mathit{W2_{00}}}}(\\mathit{h1_0} \\mathit{W2_{01}} + \\mathit{h1_1} \\mathit{W2_{11}} + \\mathit{b2_1}) \\\\\n",
    "&+ \\frac{\\partial{loss}}{\\partial{scores_2}} \\frac{\\partial{}}{\\partial{\\mathit{W2_{00}}}}(\\mathit{h1_0} \\mathit{W2_{02}} + \\mathit{h1_1} \\mathit{W2_{12}} + \\mathit{b2_2}) \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{scores_0}}{\\partial{\\mathit{W2_{00}}}} + 0 + 0\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X:\n",
      " [[16. -6.]] \n",
      "y:\n",
      " [2]\n",
      "W1:\n",
      "[[0.18 0.04]\n",
      " [0.1  0.22]]\n",
      "b1:\n",
      "[0. 0.]\n",
      "W2:\n",
      "[[ 0.19 -0.1   0.1 ]\n",
      " [-0.02 -0.01  0.04]]\n",
      "b2:\n",
      "[0. 0. 0.]\n"
     ]
    }
   ],
   "source": [
    "# A bit of setup\n",
    "import numpy as np\n",
    "# I hard coded the starting conditions in a completed neural_net.py and renamed it backprop_math_neural_net.py\n",
    "from cs231n.classifiers.backprop_math_neural_net import TwoLayerNet\n",
    "from __future__ import print_function\n",
    "\n",
    "# for auto-reloading external modules\n",
    "# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython\n",
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "\n",
    "def rel_error(x, y):\n",
    "    \"\"\" returns relative error \"\"\"\n",
    "    return np.max(np.abs(x - y) / (np.maximum(1e-8, np.abs(x) + np.abs(y))))\n",
    "\n",
    "# if we were doing a random initialization for this example,\n",
    "# these would be the arguments\n",
    "input_size = 2\n",
    "hidden_size = 2\n",
    "num_classes = 3\n",
    "\n",
    "# however, since the starting conditions are hard coded the arguments don't matter much\n",
    "net = TwoLayerNet(input_size, hidden_size, num_classes, std=1e-1)\n",
    "X = np.array([[16., -6.]])\n",
    "y = np.array([2])\n",
    "\n",
    "# these values should match the starting conditions\n",
    "print(\"X:\\n\", X, \"\\ny:\\n\", y)\n",
    "for k in net.params:\n",
    "    print(k, \":\\n\", net.params[k], sep='')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='fp'></a>\n",
    "## Forward Pass \n",
    "<a id='h1'></a>\n",
    "*** \n",
    "`h1` \n",
    "\n",
    "$\\mathit{h1} = \n",
    "\\max(0, \\mathit{x} \\mathit{W1} + \\mathit{b1}) = \n",
    "\\max (0, \\begin{bmatrix}16 & -6\\end{bmatrix} \\begin{bmatrix}0.18 & 0.04 \\\\ 0.1 & 0.22\\end{bmatrix} + \\begin{bmatrix}0 & 0\\end{bmatrix}) = \n",
    "\\max (0, \\begin{bmatrix}2.28 & -0.68\\end{bmatrix}) = \n",
    "\\begin{bmatrix}2.28 & 0\\end{bmatrix}$\n",
    "\n",
    "<a id='scores'></a>\n",
    "***\n",
    "`scores` \n",
    "\n",
    "$\\mathit{scores} = \n",
    "\\mathit{h1} \\mathit{W2} + \\mathit{b2} = \n",
    "\\begin{bmatrix}2.28 & 0\\end{bmatrix} \\begin{bmatrix}0.19 & -0.1 & 0.1 \\\\ -0.02 & -0.01 & 0.04\\end{bmatrix} + \\begin{bmatrix}0. & 0. & 0.\\end{bmatrix} = \n",
    "\\begin{bmatrix}0.4332 & -0.228 & 0.228\\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Network scores:\n",
      "[[ 0.4332 -0.228   0.228 ]]\n",
      "\n",
      "Math scores:\n",
      "[[ 0.4332 -0.228   0.228 ]]\n",
      "\n",
      "Difference between network scores and math scores:\n",
      "5.551115123125783e-17\n"
     ]
    }
   ],
   "source": [
    "# Check that the math matches the network\n",
    "math_scores = np.asarray([[0.4332, -0.228, 0.228]])\n",
    "scores = net.loss(X)\n",
    "print('Network scores:')\n",
    "print(scores)\n",
    "print()\n",
    "\n",
    "print('Math scores:')\n",
    "print(math_scores)\n",
    "print()\n",
    "\n",
    "print('Difference between network scores and math scores:')\n",
    "print(np.sum(np.abs(scores - math_scores)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='loss'></a>\n",
    " ***\n",
    "`loss`\n",
    "\n",
    "Note that $loss$ is a function of multiple variables, which is what allows us to use the multivariable chain rule later.\n",
    "\n",
    "$$\\begin{align*}\n",
    "loss(scores) &= loss(scores_0, scores_1, scores_2) \\\\\n",
    "&= -(trueprob_0)\\log{(\\frac{e^{scores_0}}{e^{scores_0} + e^{scores_1} + e^{scores_2}})} \\\\\n",
    "&+ -(trueprob_1)\\log{(\\frac{e^{scores_1}}{e^{scores_0} + e^{scores_1} + e^{scores_2}})} \\\\ \n",
    "&+ -(trueprob_2)\\log{(\\frac{e^{scores_2}}{e^{scores_0} + e^{scores_1} + e^{scores_2}})} \\\\\n",
    "\\end{align*}$$\n",
    "\n",
    "Next we evaluate $loss(scores)$ at $\\mathit{scores} = \\begin{bmatrix}0.4332 & -0.228 & 0.228\\end{bmatrix}$. In this case $y = 2$, which gives us $trueprob = \\begin{bmatrix}0 & 0 & 1\\end{bmatrix}$. So\n",
    "\n",
    "$$\\begin{align*}\n",
    "loss(scores) &= -(0)\\log{(\\frac{e^{0.4332}}{e^{0.4332} + e^{-0.228} + e^{0.228}})} \\\\\n",
    "&+ -(0)\\log{(\\frac{e^{-0.228}}{e^{0.4332} + e^{-0.228} + e^{0.228}})} \\\\\n",
    "&+ -(1)\\log{(\\frac{e^{0.228}}{e^{0.4332} + e^{-0.228} + e^{0.228}})} \\\\\n",
    "&= 1.051375468504\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Network loss:\n",
      "1.0513754685043635\n",
      "\n",
      "Math loss:\n",
      "1.051375468504\n",
      "\n",
      "Difference between network loss and math loss:\n",
      "3.6348701826227625e-13\n"
     ]
    }
   ],
   "source": [
    "# Check that the math matches the network\n",
    "math_loss = 1.051375468504\n",
    "loss, grad = net.loss(X, y)\n",
    "print('Network loss:')\n",
    "print(loss)\n",
    "print()\n",
    "\n",
    "print('Math loss:')\n",
    "print(math_loss)\n",
    "print()\n",
    "\n",
    "print('Difference between network loss and math loss:')\n",
    "print(np.sum(np.abs(loss - math_loss)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='bp'></a>\n",
    "## Backward Pass \n",
    "<a id='dscores'></a>\n",
    "***\n",
    "`dscores` \n",
    "\n",
    "To start, we want to find $\\nabla loss = \\begin{bmatrix}\\frac{\\partial{loss}}{\\partial{scores_0}} & \\frac{\\partial{loss}}{\\partial{scores_1}}  & \\frac{\\partial{loss}}{\\partial{scores_2}}\\end{bmatrix}$ where $loss$ is a function of $scores$.\n",
    "Note that $-scores_y + \\log \\sum_{j} e^{scores_j}$ is an alternate form of the loss function that is easier to differentiate with respect to $scores_j$. Remembering that in this case $y = 2$, we get\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{scores_0}} \n",
    "&= \\frac{\\partial}{\\partial{scores_0}}(-scores_2 + \\log{(e^{scores_0} + e^{scores_1} + e^{scores_2})}) \\\\\n",
    "&= 0 + \\frac{e^{scores_0}}{(e^{scores_0} + e^{scores_1} + e^{scores_2})} \\\\\n",
    "&= \\text{softmax}(scores_0), \\\\\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} \n",
    "&= \\frac{\\partial}{\\partial{scores_1}}(-scores_2 + \\log{(e^{scores_0} + e^{scores_1} + e^{scores_2})}) \\\\\n",
    "&= 0 + \\frac{e^{scores_1}}{(e^{scores_0} + e^{scores_1} + e^{scores_2})} \\\\\n",
    "&= \\text{softmax}(scores_1), \\\\\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}} \n",
    "&= \\frac{\\partial}{\\partial{scores_2}}(-scores_2 + \\log{(e^{scores_0} + e^{scores_1} + e^{scores_2})}) \\\\\n",
    "&= -1 + \\frac{e^{scores_2}}{(e^{scores_0} + e^{scores_1} + e^{scores_2})} \\\\\n",
    "&= -1 + \\text{softmax}(scores_2). \\\\\n",
    "\\end{align*}$$\n",
    "\n",
    "Next, we evaluate $\\nabla loss(scores)$ at the scores from our forward pass. Recall that $\\mathit{scores} = \\begin{bmatrix}0.4332 & -0.228 & 0.228\\end{bmatrix}$, so\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\nabla loss(scores) &= \\begin{bmatrix}\\text{softmax}(scores_0) & \\text{softmax}(scores_1) & -1 + \\text{softmax}(scores_2)\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}\\text{softmax}(0.4332) & \\text{softmax}(-0.228) & -1 + \\text{softmax}(0.228)\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}0.429052723714 & 0.221490524653 & -0.650543248367\\end{bmatrix}.\n",
    "\\end{align*}$$ \n",
    "\n",
    "This is the array stored in the variable `dscores`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='dW2'></a>\n",
    "***\n",
    "`grad['W2']` \n",
    "\n",
    "We want to find\n",
    "$\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{00}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{01}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{02}}}} \\\\\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{10}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{11}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{12}}}}\n",
    "\\end{bmatrix}.\n",
    "$\n",
    "By the multivariable chain rule\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2_{00}}}}\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{scores_0}}{\\partial{\\mathit{W2_{00}}}} + 0 + 0\\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{}}{\\partial{\\mathit{W2_{00}}}}(\\mathit{h1_0} \\mathit{W2_{00}} + \\mathit{h1_1} \\mathit{W2_{10}} + \\mathit{b2_0}) \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}}(\\mathit{h1_0}).\n",
    "\\end{align*}$$\n",
    "\n",
    "If we apply similar logic to every element of $\\frac{\\partial{loss}}{\\partial{\\mathit{W2}}}$ we get\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W2}}} \n",
    "&= \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{scores_0}}(\\mathit{h1_0}) &\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}}(\\mathit{h1_0}) &\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}}(\\mathit{h1_0}) \\\\\n",
    "\\frac{\\partial{loss}}{\\partial{scores_0}}(\\mathit{h1_1}) &\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}}(\\mathit{h1_1}) &\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}}(\\mathit{h1_1})\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix} \\mathit{h1_0} \\\\ \\mathit{h1_2} \\end{bmatrix} \n",
    "\\begin{bmatrix} \\frac{\\partial{loss}}{\\partial{scores_0}} & \\frac{\\partial{loss}}{\\partial{scores_1}} & \\frac{\\partial{loss}}{\\partial{scores_2}} \\end{bmatrix} \\\\\n",
    "&= \\mathit{h1}^\\mathsf{T} \\nabla loss.\n",
    "\\end{align*}$$\n",
    "\n",
    "So the array stored in `grad['W2']` is\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\mathit{h1}^\\mathsf{T} \\nabla loss(scores)\n",
    "&= \\begin{bmatrix}2.28 \\\\ 0\\end{bmatrix} \\begin{bmatrix}0.429052723714 & 0.221490524653 & -0.650543248367\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}\n",
    "0.978240210068 & 0.504998396209 & -1.483238606277 \\\\\n",
    "0 & 0 & 0\n",
    "\\end{bmatrix}.\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Network dW2:\n",
      "[[ 0.97824021  0.5049984  -1.48323861]\n",
      " [ 0.          0.          0.        ]]\n",
      "\n",
      "Math dW2:\n",
      "[[ 0.97824021  0.5049984  -1.48323861]\n",
      " [ 0.          0.          0.        ]]\n",
      "\n",
      "Difference between network loss and math loss:\n",
      "2.4562574196806963e-12\n"
     ]
    }
   ],
   "source": [
    "# Check that the math matches the network\n",
    "math_dW2 = np.asarray([[0.978240210068 , 0.504998396209 , -1.483238606277], [0, 0, 0]])\n",
    "print('Network dW2:')\n",
    "print(grad['W2'])\n",
    "print()\n",
    "\n",
    "print('Math dW2:')\n",
    "print(math_dW2)\n",
    "print()\n",
    "\n",
    "print('Difference between network loss and math loss:')\n",
    "print(np.sum(np.abs(grad['W2'] - math_dW2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='db2'></a>\n",
    "***\n",
    "`grad['b2']` \n",
    "\n",
    "We want to find\n",
    "$\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b2}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b2_{0}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b2_{1}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b2_{2}}}} \n",
    "\\end{bmatrix}.\n",
    "$\n",
    "By the multivariable chain rule\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b2_{0}}}}\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{scores_0}}{\\partial{\\mathit{b2_{0}}}} + 0 + 0\\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{}}{\\partial{\\mathit{b2_{0}}}}(\\mathit{h1_0} \\mathit{W2_{00}} + \\mathit{h1_1} \\mathit{W2_{10}} + \\mathit{b2_0}) \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}}(1).\n",
    "\\end{align*}$$\n",
    "\n",
    "If we apply similar logic to every element of $\\frac{\\partial{loss}}{\\partial{\\mathit{b2}}}$ we get\n",
    "$\\frac{\\partial{loss}}{\\partial{\\mathit{b2}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{scores_0}} &\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} &\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}}\n",
    "\\end{bmatrix}\n",
    "= \\nabla loss(scores).$\n",
    "\n",
    "So the array stored in `grad['b2']` is\n",
    "$\\nabla loss(scores) = \\begin{bmatrix}0.429052723714 & 0.221490524653 & -0.650543248367\\end{bmatrix}.$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Network db2:\n",
      "[ 0.42905272  0.22149052 -0.65054325]\n",
      "\n",
      "Math db2:\n",
      "[ 0.42905272  0.22149052 -0.65054325]\n",
      "\n",
      "Difference between network loss and math loss:\n",
      "9.368616993299383e-13\n"
     ]
    }
   ],
   "source": [
    "math_db2 = np.asarray([0.429052723714 , 0.221490524653 , -0.650543248367])\n",
    "print('Network db2:')\n",
    "print(grad['b2'])\n",
    "print()\n",
    "\n",
    "print('Math db2:')\n",
    "print(math_db2)\n",
    "print()\n",
    "\n",
    "print('Difference between network loss and math loss:')\n",
    "print(np.sum(np.abs(grad['b2'] - math_db2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='dh1'></a>\n",
    "***\n",
    "`dh1`  \n",
    "\n",
    "We want to find\n",
    "$\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1_{0}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1_{1}}}}\n",
    "\\end{bmatrix}.\n",
    "$\n",
    "By the multivariable chain rule\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1_0}}} \n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{scores_0}}{\\partial{\\mathit{h1_0}}} +\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} \\frac{\\partial{scores_1}}{\\partial{\\mathit{h1_0}}} +\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}} \\frac{\\partial{scores_2}}{\\partial{\\mathit{h1_0}}} \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} \\frac{\\partial{}}{\\partial{\\mathit{h1_0}}}(\\mathit{h1_0} \\mathit{W2_{00}} + \\mathit{h1_1} \\mathit{W2_{10}} + \\mathit{b2_0}) \\\\\n",
    "&+\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} \\frac{\\partial{}}{\\partial{\\mathit{h1_0}}}(\\mathit{h1_0} \\mathit{W2_{01}} + \\mathit{h1_1} \\mathit{W2_{11}} + \\mathit{b2_1}) \\\\\n",
    "&+\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}} \\frac{\\partial{}}{\\partial{\\mathit{h1_0}}}(\\mathit{h1_0} \\mathit{W2_{02}} + \\mathit{h1_1} \\mathit{W2_{12}} + \\mathit{b2_2}) \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{scores_0}} (\\mathit{W2}_{00}) +\n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} (\\mathit{W2}_{01}) +\n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}} (\\mathit{W2}_{02}) \\\\\n",
    "&= \\begin{bmatrix} \\frac{\\partial{loss}}{\\partial{scores_0}} & \\frac{\\partial{loss}}{\\partial{scores_1}} & \\frac{\\partial{loss}}{\\partial{scores_2}} \\end{bmatrix} \n",
    "\\begin{bmatrix} \\mathit{W2}_{00} \\\\ \\mathit{W2}_{01} \\\\ \\mathit{W2}_{02} \\end{bmatrix}.\n",
    "\\end{align*}$$\n",
    "\n",
    "If we apply similar logic to every element of $\\frac{\\partial{loss}}{\\partial{\\mathit{h1}}}$ we get\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}}} \n",
    "&= \n",
    "\\begin{bmatrix} \n",
    "\\begin{bmatrix} \\frac{\\partial{loss}}{\\partial{scores_0}} & \\frac{\\partial{loss}}{\\partial{scores_1}} & \\frac{\\partial{loss}}{\\partial{scores_2}} \\end{bmatrix} \n",
    "\\begin{bmatrix} \\mathit{W2}_{00} \\\\ \\mathit{W2}_{01} \\\\ \\mathit{W2}_{02} \\end{bmatrix} &\n",
    "\\begin{bmatrix} \\frac{\\partial{loss}}{\\partial{scores_0}} & \\frac{\\partial{loss}}{\\partial{scores_1}} & \\frac{\\partial{loss}}{\\partial{scores_2}} \\end{bmatrix} \n",
    "\\begin{bmatrix} \\mathit{W2}_{10} \\\\ \\mathit{W2}_{11} \\\\ \\mathit{W2}_{12} \\end{bmatrix}\n",
    "\\end{bmatrix} \\\\\n",
    "&= \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{scores_0}} & \n",
    "\\frac{\\partial{loss}}{\\partial{scores_1}} & \n",
    "\\frac{\\partial{loss}}{\\partial{scores_2}} \n",
    "\\end{bmatrix} \n",
    "\\begin{bmatrix} \n",
    "\\mathit{W2}_{00} & \\mathit{W2}_{10} \\\\\n",
    "\\mathit{W2}_{01} & \\mathit{W2}_{11} \\\\\n",
    "\\mathit{W2}_{02} & \\mathit{W2}_{12} \n",
    "\\end{bmatrix} \\\\\n",
    "&= \\nabla loss(scores) \\mathit{W2}^\\mathsf{T}.\n",
    "\\end{align*}$$\n",
    "\n",
    "So the array stored in `dh1` is \n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}}} \n",
    "&= \\nabla loss(scores) \\mathit{W2}^\\mathsf{T} \\\\\n",
    "&= \\begin{bmatrix}0.429052723714 & 0.221490524653 & -0.650543248367\\end{bmatrix}\n",
    "\\begin{bmatrix}0.19 & -0.02 \\\\ -0.1 & -0.01 \\\\ 0.1 & 0.04\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix} -0.005683359796 & -0.036817689655 \\end{bmatrix}.\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='dh1_1'></a>\n",
    "***\n",
    "`dh1[h1 <= 0] = 0` \n",
    "\n",
    "This is the part where we backprop through the ReLU. Let $M = X\\mathit{W1} + \\mathit{b1}$, which in this case is a $1 \\times 2$ array. What we are trying to find is\n",
    "\n",
    "$$\n",
    "\\frac{\\partial{loss}}{\\partial{M}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{M_0}} &\n",
    "\\frac{\\partial{loss}}{\\partial{M_1}}\n",
    "\\end{bmatrix}.\n",
    "$$\n",
    "By the multivariable chain rule\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{M_n}} \n",
    "&= \\frac{\\partial{loss}}{\\partial{\\mathit{h1}_n}}\n",
    "\\frac{\\partial{\\mathit{h1}_n}}{\\partial{M_n}} + 0 \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{\\mathit{h1}_n}} \n",
    "\\frac{\\partial{}}{\\partial{M_n}} (\\max(0, M_n)) \\\\\n",
    "&= \\begin{cases}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}_n}}(1) = \\frac{\\partial{loss}}{\\partial{\\mathit{h1}_n}} , & \\text{if } M_n > 0\\\\\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}_n}}(0) = 0 , & \\text{if } M_n \\leq 0.\n",
    "\\end{cases}\n",
    "\\end{align*}$$\n",
    "\n",
    "So \n",
    "$\n",
    "\\frac{\\partial{loss}}{\\partial{M}} =\n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}_0}}\n",
    "\\frac{\\partial{\\mathit{h1}_0}}{\\partial{M_0}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}_1}}\n",
    "\\frac{\\partial{\\mathit{h1}_1}}{\\partial{M_1}}\n",
    "\\end{bmatrix}.\n",
    "$\n",
    "From the forward pass we know that $M = \\begin{bmatrix}2.28 & -0.68\\end{bmatrix}$ and recall that $\\frac{\\partial{loss}}{\\partial{\\mathit{h1}}} = \\begin{bmatrix} -0.005683359796 & -0.036817689655 \\end{bmatrix}.$ Thus we change the array stored in `dh1` to be \n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{M}} \n",
    "&=\n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}_0}}\n",
    "\\frac{\\partial{\\mathit{h1}_0}}{\\partial{M_0}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{h1}_1}}\n",
    "\\frac{\\partial{\\mathit{h1}_1}}{\\partial{M_1}}\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix} -0.005683359796(1) & -0.036817689655(0) \\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix} -0.005683359796 & 0 \\end{bmatrix}.\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='dW1'></a>\n",
    "***\n",
    "`grad['W1']` \n",
    "\n",
    "We want to find\n",
    "$\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1_{00}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1_{01}}}} \\\\\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1_{10}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1_{11}}}}\n",
    "\\end{bmatrix}.\n",
    "$\n",
    "Let $M = x\\mathit{W1} + \\mathit{b1}$, which in this case is a $1 \\times 2$ array. By the multivariable chain rule\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1_{00}}}}\n",
    "&= \\frac{\\partial{loss}}{\\partial{M_0}} \\frac{\\partial{M_0}}{\\partial{\\mathit{W1_{00}}}} + 0\\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{M_0}} \\frac{\\partial{}}{\\partial{\\mathit{W1_{00}}}}(\\mathit{x_0} \\mathit{W1_{00}} + \\mathit{x_1} \\mathit{W1_{10}} + \\mathit{b1_0}) \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{M_0}}(\\mathit{x_0}).\n",
    "\\end{align*}$$\n",
    "\n",
    "If we apply similar logic to every element of $\\frac{\\partial{loss}}{\\partial{\\mathit{W1}}}$ we get\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{W1}}} \n",
    "&= \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{M_0}}(\\mathit{x_0}) &\n",
    "\\frac{\\partial{loss}}{\\partial{M_1}}(\\mathit{x_0}) \\\\\n",
    "\\frac{\\partial{loss}}{\\partial{M_0}}(\\mathit{x_1}) &\n",
    "\\frac{\\partial{loss}}{\\partial{M_1}}(\\mathit{x_1})\n",
    "\\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix} \\mathit{x_0} \\\\ \\mathit{x_1} \\end{bmatrix} \n",
    "\\begin{bmatrix} \\frac{\\partial{loss}}{\\partial{M_0}} & \\frac{\\partial{loss}}{\\partial{M_1}}\\end{bmatrix} \\\\\n",
    "&= \\mathit{x}^\\mathsf{T} \\frac{\\partial{loss}}{\\partial{M}}.\n",
    "\\end{align*}$$\n",
    "\n",
    "Recall that $\\frac{\\partial{loss}}{\\partial{M}} = \\begin{bmatrix} -0.005683359796 & 0 \\end{bmatrix}$ from the section for `dh1[h1 <= 0] = 0`. So the array stored in `grad['W1']` is\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\mathit{x}^\\mathsf{T} \\frac{\\partial{loss}}{\\partial{M}}\n",
    "&= \\begin{bmatrix}16 \\\\ -6\\end{bmatrix} \\begin{bmatrix} -0.005683359796 & 0 \\end{bmatrix} \\\\\n",
    "&= \\begin{bmatrix}\n",
    "-0.090933756736 & 0 \\\\\n",
    "0.034100158776 & 0\n",
    "\\end{bmatrix}.\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Network dW1:\n",
      "[[-0.09093376  0.        ]\n",
      " [ 0.03410016  0.        ]]\n",
      "\n",
      "Math dW1:\n",
      "[[-0.09093376  0.        ]\n",
      " [ 0.03410016  0.        ]]\n",
      "\n",
      "Difference between network loss and math loss:\n",
      "4.570302469808496e-12\n"
     ]
    }
   ],
   "source": [
    "math_dW1 = np.asarray([[-0.090933756736 , 0], [0.034100158776, 0]])\n",
    "print('Network dW1:')\n",
    "print(grad['W1'])\n",
    "print()\n",
    "\n",
    "print('Math dW1:')\n",
    "print(math_dW1)\n",
    "print()\n",
    "\n",
    "print('Difference between network loss and math loss:')\n",
    "print(np.sum(np.abs(grad['W1'] - math_dW1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='db1'></a>\n",
    "***\n",
    "`grad['b1']` \n",
    "\n",
    "We want to find\n",
    "$\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b1}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b1_{0}}}} &\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b1_{1}}}} \n",
    "\\end{bmatrix}.\n",
    "$\n",
    "Let $M = x\\mathit{W1} + \\mathit{b1}$, which in this case is a $1 \\times 2$ array. By the multivariable chain rule\n",
    "\n",
    "$$\\begin{align*}\n",
    "\\frac{\\partial{loss}}{\\partial{\\mathit{b1_{0}}}}\n",
    "&= \\frac{\\partial{loss}}{\\partial{M_0}} \\frac{\\partial{M_0}}{\\partial{\\mathit{b1_{0}}}} + 0 \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{M_0}} \\frac{\\partial{}}{\\partial{\\mathit{b1_{0}}}}(\\mathit{x_0} \\mathit{W1_{00}} + \\mathit{x_1} \\mathit{W1_{10}} + \\mathit{b1_0}) \\\\\n",
    "&= \\frac{\\partial{loss}}{\\partial{M_0}}(1).\n",
    "\\end{align*}$$\n",
    "\n",
    "If we apply similar logic to every element of $\\frac{\\partial{loss}}{\\partial{\\mathit{b1}}}$ we get\n",
    "$\\frac{\\partial{loss}}{\\partial{\\mathit{b1}}} = \n",
    "\\begin{bmatrix} \n",
    "\\frac{\\partial{loss}}{\\partial{M_0}} &\n",
    "\\frac{\\partial{loss}}{\\partial{M_1}}\n",
    "\\end{bmatrix} =\n",
    "\\frac{\\partial{loss}}{\\partial{M}}.$\n",
    "\n",
    "Recall that $\\frac{\\partial{loss}}{\\partial{M}} = \\begin{bmatrix} -0.005683359796 & 0 \\end{bmatrix}$ from the section for `dh1[h1 <= 0] = 0`. So the array stored in `grad['b1']` is $\\frac{\\partial{loss}}{\\partial{M}} = \\begin{bmatrix} -0.005683359796 & 0 \\end{bmatrix}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Network db1:\n",
      "[-0.00568336  0.        ]\n",
      "\n",
      "Math db1:\n",
      "[-0.00568336  0.        ]\n",
      "\n",
      "Difference between network loss and math loss:\n",
      "2.0774094250386455e-13\n"
     ]
    }
   ],
   "source": [
    "math_db1 = np.array([-0.005683359796, 0])\n",
    "print('Network db1:')\n",
    "print(grad['b1'])\n",
    "print()\n",
    "\n",
    "print('Math db1:')\n",
    "print(math_db1)\n",
    "print()\n",
    "\n",
    "print('Difference between network loss and math loss:')\n",
    "print(np.sum(np.abs(grad['b1'] - math_db1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gradient Check\n",
    "Just to confirm `cs231n/classifiers/backprop_math_neural_net.py` is implemented correctly!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "W2 max relative error: 3.038736e-09\n",
      "b2 max relative error: 5.774141e-12\n",
      "W1 max relative error: 5.724374e-10\n",
      "b1 max relative error: 7.733046e-10\n"
     ]
    }
   ],
   "source": [
    "from cs231n.gradient_check import eval_numerical_gradient\n",
    "\n",
    "# Use numeric gradient checking to check your implementation of the backward pass.\n",
    "# If your implementation is correct, the difference between the numeric and\n",
    "# analytic gradients should be less than 1e-8 for each of W1, W2, b1, and b2.\n",
    "\n",
    "loss, grads = net.loss(X, y, reg=0.05)\n",
    "\n",
    "# these should all be less than 1e-8 or so\n",
    "for param_name in grads:\n",
    "    f = lambda W: net.loss(X, y, reg=0.05)[0]\n",
    "    param_grad_num = eval_numerical_gradient(f, net.params[param_name], verbose=False)\n",
    "    print('%s max relative error: %e' % (param_name, rel_error(param_grad_num, grads[param_name])))"
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}