backprop_workbook_02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backprop Workbook 02: Backprop to Hidden Layer\n",
    "\n",
    "**For these questions, assume that an $x$ input has 1024 dimensions, that the first hidden layer should have $512$ units, a second layer has $256$ units, and that there are $10$ classes to choose from at the end.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Cell to run for Latex commands**\n",
    "\n",
    "\\\\[\n",
    "\\newcommand{\\fpartial}[2]{\\frac{\\partial #1}{\\partial #2}}\n",
    "\\newcommand{\\grad}[1]{\\nabla #1}\n",
    "\\newcommand{\\softmax}[0]{\\text{SOFTMAX}}\n",
    "\\newcommand{\\trans}[1]{{#1}^{\\intercal}}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backprop Further Through Gradient Chains"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've now calculated gradients for the final layer's weights and biases. We now want to calculate the corresponding gradients for $\\grad_{W^{(2)}} CE(h^{(3)}, y)$ and $\\grad_{b^{(2)}} CE(h^{(3)}, y)$.\n",
    "\n",
    "How do changes to these weights and biases affect the loss?\n",
    "\n",
    "1. Changes to $W^{(2)}$ and $b^{(2)}$ change the $z^{(2)}$ values.\n",
    "2. Changes to the $z^{(2)}$ values change the $h^{(2)}$ values.\n",
    "3. Changes to the $h^{(2)}$ values change the $z^{(3)}$ values.\n",
    "4. And we already know how changes to $z^{(3)}$ values change the loss.\n",
    "\n",
    "In this section we will work our way backward: 3, 2, 1. Blast off!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. Write $\\grad_{b^{(2)}} CE(h^{(3)}, y)$ as a chain of four gradients. Take inspiration from the above plan.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{b^{(2)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\left(\n",
    "    \\grad_{b^{(2)}} z^{(2)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{z^{(2)}} h^{(2)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{h^{(2)}} z^{(3)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{z^{(3)}} CE(h^{(3)}, y)\n",
    "\\right)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Write $\\grad_{W^{(2)}} CE(h^{(3)}, y)$ as a chain of four gradients. Take inspiration from the above plan.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{W^{(2)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\left(\n",
    "    \\grad_{W^{(2)}} z^{(2)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{z^{(2)}} h^{(2)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{h^{(2)}} z^{(3)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{z^{(3)}} CE(h^{(3)}, y)\n",
    "\\right)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chain Rule For Gradients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. Gradients like $\\grad_{z^{(3)}} CE(h^{(3)}, y)$ are familiar because there are many inputs, but only one output. What is the shape of this vector? Why?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is a row vector of length ten because there are ten $z^{(3)}$ values and thus ten partial derivatives. The gradient matches the shape of $z^{(3)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. When we write $\\Delta z^{(3)} \\cdot \\grad_{z^{(3)}} CE(h^{(3)}, y) = \\Delta CE(h^{(3)}, y)$, what are the shapes of the vectors involved?**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first two are vectors of shape $(10,)$. The last is a scalar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. The next step is to try to calculate $\\grad_{h^{(2)}} z^{(3)}$. I want to write $\\Delta h^{(2)} \\cdot \\grad_{h^{(2)}} z^{(3)} = \\Delta z^{(3)}$. What are the shapes involved?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First a vector of length $(256,)$. Then a *matrix* of dimension $(256, 10)$. Finally a vector of length $(10,)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. Soon I will want to calculate $\\grad_{W^{(2)}} z^{(2)}$. Whoa. Let's start with a simpler question: $\\grad_{W^{(2)}} z^{(2)}_k$. What is the shape of my $\\Delta W^{(2)}$?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The shape is $(512, 256)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5. What is the shape of $\\grad_{W^{(2)}} z^{(2)}_k$? How is this different from $\\grad_{h^{(2)}} z^{(3)}$?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is $(512, 256)$. The difference is that *both* dimensions are \"input dimensions.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6. How do you calculate $\\Delta z^{(2)}_k$?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You multiply corresponding entries of $\\Delta W^{(2)}$ and $\\grad_{W^{(2)}} z^{(2)}_k$ and sum out."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** this kind of operation is called a \"double dot product.\" We denote it as:\n",
    "\n",
    "\\\\[\n",
    "\\Delta W^{(2)} : \\grad_{W^{(2)}} z^{(2)}_k = \\Delta z^{(2)}_k\n",
    "\\\\]\n",
    "\n",
    "It says: take the *last* two (i.e., all) the dimensions of $W^{(2)}$ and multiply them coordinatewise with the *first* two dimensions of $\\grad_{W^{(2)}} z^{(2)}_k$ (i.e., all), and then sum out.\n",
    "\n",
    "It's just like the dot-product, but with two dimensions!\n",
    "\n",
    "In numpy we write: `np.tensordot(A, B, axes = 2)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7. Write the formula for $\\Delta z^{(2)}$ now.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\Delta W^{(2)} : \\grad_{W^{(2)}} z^{(2)} = \\Delta z^{(2)}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating $\\grad_{h^{(2)}} z^{(3)}$ and $\\grad_{h^{(2)}} CE(h^{(3)}, y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. In our plan we know the last gradient $\\grad_{z^{(3)}} CE(h^{(3)}, y)$, so let's work backward and start with $\\grad_{h^{(2)}} z^{(3)}$. Let's focus on just a single partial: $\\fpartial{}{h^{(2)}_i} z^{(3)}_j$. Use the formula for $z^{(3)}_j$ to calculate this.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\fpartial{}{h^{(2)}_i} z^{(3)}_j\n",
    "=\n",
    "\\fpartial{}{h^{(2)}_i} \\left(\n",
    "    \\sum_{k = 0}^{512} h^{(2)}_k W^{(3)}_{k, j}\n",
    "\\right) + b^{(3)}_j\n",
    "=\n",
    "W^{(3)}_{i, j}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Why does does $W^{(3)}_{i, j}$ feel like the right anwer?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because it is the weight that connects $h^{(2)}_i$ to $z^{(3)}_j$. Any change in $h^{(2)}_i$ will be \"magnified\" by $W^{(3)}_{i, j}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. Using this result, and our definition above for $\\left(\\grad_{h^{(2)}} z^{(3)}\\right)_{i, j}$, give an equation for $\\grad_{h^{(2)}} z^{(3)}$.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{h^{(2)}} z^{(3)}\n",
    "=\n",
    "W^{(3)}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. Great. Let's break this down to understand better. Give a formula for $\\grad_{h^{(2)}} z^{(3)}_j$ in terms of $W^{(3)}$. What is the shape of this? Why does this formula make sense?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{h^{(2)}} z^{(3)}_j = W^{(3)}_{:, j}\n",
    "\\\\]\n",
    "\n",
    "This is a vector with length $256$. It makes sense because all 256 units of $h^{(2)}$ are connected to the $z^{(3)}_j$ value. This column consists of exactly the weights used to calculate $z^{(3)}_j$ and scale the values in $h^{(2)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5. Using the above formula, consider a change $\\Delta h^{(2)}$ to the 256 dimensions of $h^{(2)}$. Use the gradient for $z^{(3)}_j$ to calculate the change in $z^{(3)}_j$. Break it down to the summation level even. Do this both in terms of partials $\\fpartial{z^{(3)}_j}{h^{(2)}_i}$ and $W^{(3)}$. Give an explanation for the formulae.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\begin{align}\n",
    "    \\Delta z^{(3)}_j\n",
    "    &=\n",
    "    \\left(\n",
    "        \\Delta h^{(2)}\n",
    "    \\right)\n",
    "    \\cdot\n",
    "    \\left(\n",
    "        \\grad_{h^{(2)}} z^{(3)}_j\n",
    "    \\right)\n",
    "    =\n",
    "    \\sum_{i = 0}^{256}\n",
    "    \\Delta h^{(2)}_i \\fpartial{z^{(3)}_j}{h^{(2)}_i}\n",
    "\\\\\n",
    "    &=\n",
    "    \\left(\n",
    "        \\Delta h^{(2)}\n",
    "    \\right)\n",
    "    \\cdot\n",
    "    \\left(\n",
    "        W^{(2)}_{:, j}\n",
    "    \\right)\n",
    "    =\n",
    "    \\sum_{i = 0}^{256}\n",
    "    \\Delta h^{(2)}_i W^{(3)}_{i, j}\n",
    "\\end{align}\n",
    "\\\\]\n",
    "\n",
    "Basically each change to $h^{(2)}$ has its own impact on the $z^{(3)}_j$ value. We need to evaluate those impacts and sum them up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6. Give a formula for $\\grad_{h^{(2)}_i} z^{(3)}$ in terms of $W^{(3)}$. What is the shape of this? Column or row vector? Why? Why does this formula make sense?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{h^{(2)}_i} z^{(3)} = W^{(3)}_{i, :}\n",
    "\\\\]\n",
    "\n",
    "This is a vector of length $10$. This way when multiplied by a scalar change $\\Delta h^{(2)}_i$ you get $\\Delta z^{(3)}$.\n",
    "\n",
    "It makes sense because the unit $h^{(2)}_i$ is connected to all $10$ units of $z^{(3)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7. Using the above formula, consider a scalar change $\\Delta h^{(2)}_i$. Calculate the change in $z^{(3)}$. Do this both in terms of partials $\\fpartial{z^{(3)}_j}{h^{(2)}_i}$ and $W^{(3)}$. Give an explanation for the formulas.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\begin{align}\n",
    "    \\Delta z^{(3)}\n",
    "    &=\n",
    "    \\Delta h^{(2)}_i \\grad_{h^{(2)}_i} z^{(3)}\n",
    "    =\n",
    "    \\left(\n",
    "        \\Delta h^{(2)}_i\n",
    "        \\fpartial{z^{(3)}_0}{h^{(2)}_i}\n",
    "        ,\n",
    "        \\Delta h^{(2)}_i\n",
    "        \\fpartial{z^{(3)}_1}{h^{(2)}_i}\n",
    "        ,\n",
    "        \\ldots\n",
    "        ,\n",
    "        \\Delta h^{(2)}_i\n",
    "        \\fpartial{z^{(3)}_255}{h^{(2)}_i}\n",
    "    \\right)\n",
    "\\\\\n",
    "    &=\n",
    "    \\Delta h^{(2)}_i W^{(3)}_{i, :}\n",
    "    =\n",
    "    \\left(\n",
    "        \\Delta h^{(2)}_i\n",
    "        W^{(3)}_{i, 0}\n",
    "        ,\n",
    "        \\Delta h^{(2)}_i\n",
    "        W^{(3)}_{i, 1}\n",
    "        ,\n",
    "        \\ldots\n",
    "        ,\n",
    "        \\Delta h^{(2)}_i\n",
    "        W^{(3)}_{i, 255}\n",
    "    \\right)\n",
    "\\end{align}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8. The chain rule says:**\n",
    "\n",
    "\\\\[\n",
    "\\grad_{h^{(2)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\left(\n",
    "    \\grad_{h^{(2)}} z^{(3)}\n",
    "\\right)\n",
    "\\cdot\n",
    "\\left(\n",
    "    \\grad_{z^{(3)}} CE(h^{(3)}, y)\n",
    "\\right)\n",
    "\\\\]\n",
    "\n",
    "**Tell me the shapes of the terms in the product. Tell me about the final shape.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The shapes are $(256, 10)$ and $(10,1)$. The product is a vector $(256, 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**9. Why does it make sense that the final shape of the gradient is $(256, 1)$?**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are $256$ units in layer two, but we're assessing their impact on a single scalar value: the loss."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**10. To calculate the product, we take the dot product of rows of $\\grad_{h^{(2)}} z^{(3)}$ with $\\grad_{z^{(3)}} CE(h^{(3)}, y)$. This dot product is $\\left(\\grad_{h^{(2)}} CE(h^{(3)}, y)\\right)_i$.**\n",
    "\n",
    "**Write a formula with a summation for this for row $i$ of $\\grad_{h^{(2)}} z^{(3)}$. Do this both in terms of partials and in terms of $W^{(3)}$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\begin{align}\n",
    "    \\left(\n",
    "        \\grad_{h^{(2)}} CE(h^{(3)}, y)_i\n",
    "    \\right)_i\n",
    "    &=\n",
    "    \\left(\n",
    "        \\grad_{h^{(2)}} z^{(3)}\n",
    "    \\right)_{i, :}\n",
    "    \\cdot\n",
    "    \\left(\n",
    "        \\grad_{z^{(3)}} CE(h^{(3)}, y)\n",
    "    \\right)\n",
    "    =\n",
    "    \\sum_{j = 0}^{10}\n",
    "    \\left(\n",
    "        \\fpartial{z^{(3)}_j}{h^{(2)}_i}\n",
    "    \\right)\n",
    "    \\left(\n",
    "        \\fpartial{CE(h^{(3)}, y)}{z^{(3)}_j}\n",
    "    \\right)\n",
    "\\\\\n",
    "    &=\n",
    "    W^{(3)}_{i, :}\n",
    "    \\cdot\n",
    "    \\left(\n",
    "        \\grad_{z^{(3)}} CE(h^{(3)}, y)\n",
    "    \\right)\n",
    "    =\n",
    "    \\sum_{j = 0}^{10}\n",
    "    W^{(3)}_{i, j}\n",
    "    \\left(\n",
    "        \\fpartial{CE(h^{(3)}, y)}{z^{(3)}_j}\n",
    "    \\right)\n",
    "\\end{align}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**11. Give me a story in words for this formula.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A change in $h^{(2)}_i$ affects all of $z^{(3)}_j$ values via the weights in row $W_{i, :}$. And a change in a $z^{(3)}_j$ value causes a change in $CE(h^{(3)}, y)$.\n",
    "\n",
    "The amount of change for $CE(h^{(3)}, y)$ \"via\" the value $z^{(3)}_j$ is equal to the product of the two partial derivatives.\n",
    "\n",
    "The total change in cross-entropy comes from summing up over all the \"routes\" via which $h^{(2)}_i$ can impact the cross-entropy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**12. Calculate $\\grad_{h^{(2)}} CE(h^{(3)}, y)$ by using the formulae we've found for $\\grad_{h^{(2)}} z^{(3)}$ and $\\grad_{z^{(3)}} CE(h^{(3)}, y)$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\begin{align}\n",
    "    \\grad_{h^{(2)}} CE(h^{(3)}, y)\n",
    "    &=\n",
    "    \\left(\n",
    "        \\grad_{h^{(2)}} z^{(3)}\n",
    "    \\right)\n",
    "    \\cdot\n",
    "    \\left(\n",
    "        \\grad_{z^{(3)}} CE(h^{(3)}, y)\n",
    "    \\right)\n",
    "\\\\\n",
    "    &=\n",
    "    W^{(3)}\n",
    "    \\cdot\n",
    "    (h^{(3)} - y)\n",
    "\\end{align}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating $\\grad_{z^{(2)}} h^{(2)}$ and $\\grad_{z^{(2)}} CE(h^{(3)}, y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we know \n",
    "\n",
    "\\\\[\n",
    "\\grad_{z^{(2)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\left(\\grad_{z^{(2)}} h^{(2)}\\right)\n",
    "\\cdot\n",
    "\\left(\\grad_{h^{(2)}} CE(h^{(3)}, y)\\right)\n",
    "\\\\]\n",
    "\n",
    "We know that what we really need to backprop the loss to $z^{(2)}$ is to calculate $\\grad_{z^{(2)}} h^{(2)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. What are the shapes of $\\grad_{z^{(2)}} h^{(2)}$, $\\grad_{h^{(2)}} CE(h^{(3)}, y)$ and $\\grad_{z^{(2)}} CE(h^{(3)} y)$.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "They are $(256, 256)$ $(256, 1)$, and $(256, 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. $\\grad_{z^{(2)}} h^{(2)}$ is a matrix which records how a change to any $z^{(2)}_i$ can change any $h^{(2)}_j$. Why does this seem excessive? How many and which $h^{(2)}_j$ values respond to a change in $z^{(2)}_i$? Why? Consider the formula for $h^{(2)}_j$ in terms of the $z^{(2)}$ values...**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We know:\n",
    "\n",
    "\\\\[\n",
    "h^{(2)}_j = \\sigma\\left(z^{(2}_j\\right)\n",
    "\\\\]\n",
    "\n",
    "Therefore, the only $z^{(2)}$ value that can effect $h^{(2)}_j$ is $z^{(2)}_j$. The other $z^{(2)}$ values have no impact at all on $h^{(2)}_j$.\n",
    "\n",
    "Our gradient matrix $\\grad_{z^{(2)}} h^{(2)}$ will hold almost all zeros!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. What entries of the gradient matrix $\\grad_{z^{(2)}} h^{(2)}$ will be zero, and which can be non-zero? What do we call this kind of matrix? What are the values of these entries in terms of partials?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only at positions $(i, j)$ where $i = j$ can the matrix be non-zero. All other entries must be zero.\n",
    "\n",
    "We have:\n",
    "\n",
    "\\\\[\n",
    "\\left(\n",
    "     \\grad_{z^{(2)}} h^{(2)}\n",
    "\\right)_{i, i}\n",
    "=\n",
    "\\fpartial{h^{(2)}_i}{z^{(2)}_i}\n",
    "\\\\]\n",
    "\n",
    "This is called a *diagonal* matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. What does a diagonal matrix do to a vector? What kind of operation is it? Think about what a $3$-by-$3$ diagonal matrix does to $(1, 0, 0)$, $(0, 1, 0)$, and $(0, 0, 1)$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The digonal matrix stretches unit vectors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5. What does a diagonal matrix $D$ do to a matrix $M$? Think about composition of operations when considering $DM$: think about $(xD)M$. Why?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The matrix $D$ stretches each row of $M$. That's because any input $xD$ to $M$ will have been \"pre-stretched.\" So we can just fold the stretching into $M$ by multiplying appropriate rows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6. We must now learn how to calculate the partial $\\fpartial{\\sigma(z)}{z}$. The first step is to learn a formula for $1 - \\sigma(z)$. Calculate this by expanding the definition of $\\sigma$ and simplifying. Hint: remember both formulas for $\\sigma(z)$...**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "1 - \\sigma(z)\n",
    "=\n",
    "1 - \\frac{e^z}{1 + e^z}\n",
    "=\n",
    "\\frac{1 + e^z}{1 + e^z} - \\frac{e^z}{1+e^z}\n",
    "=\n",
    "\\frac{1}{1 + e^z}\n",
    "\\\\]\n",
    "\n",
    "That's almost the same as the \"other\" formula for $\\sigma(z)$. Except the other formula has a $-z$ in the denominator. So this is actually the formula for $\\sigma(-z)$.\n",
    "\n",
    "Thus we have \n",
    "\n",
    "\\\\[\n",
    "1 - \\sigma(z)\n",
    "=\n",
    "\\sigma(-z)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7. Why does this formula make sense? Think about the relation of an odds $A:B$ vs odds of $B:A$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $A:B$ is three-to-one odds, then $B:A$ is one-to-three odds. That is, the relationship is $odds_{B:A} = \\left(odds_{A:B}\\right)^{-1}$. In the log scale, that turns out to $\\log odds_{B:A} = -\\log odds_{A:B}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8. Next, let's take the derivative of $\\sigma(z)$ wrt $z$. Remember that we can write $\\sigma(z) = \\left(1 + e^{-z}\\right)^{-1}$. This lets us use the \"polynomial rule\" and chain rule together.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\begin{align}\n",
    "\\fpartial{\\sigma(z)}{z}\n",
    "&=\n",
    "\\fpartial{}{z}\n",
    "\\left(1 + e^{-z}\\right)^{-1}\n",
    "\\\\\n",
    "&=\n",
    "-1\n",
    "\\left(1 + e^{-z}\\right)^{-2}\n",
    "\\fpartial{}{z}\n",
    "e^{-z}\n",
    "\\\\\n",
    "&=\n",
    "-1\n",
    "\\left(1 + e^{-z}\\right)^{-2}\n",
    "\\left(\n",
    "    -e^{-z}\n",
    "\\right)\n",
    "\\\\\n",
    "&=\n",
    "\\frac{e^{-z}}{\\left(1 + e^{-z}\\right)^2}\n",
    "\\\\\n",
    "&=\n",
    "\\frac{1}{\\left(1 + e^{-z}\\right)}\n",
    "\\frac{e^{-z}}{\\left(1 + e^{-z}\\right)}\n",
    "\\\\\n",
    "&=\n",
    "\\sigma(z)\n",
    "\\frac{1}{\\left(1 + e^{z}\\right)}\n",
    "\\\\\n",
    "&=\n",
    "\\sigma(z)\n",
    "\\sigma(-z)\n",
    "\\\\\n",
    "&=\n",
    "\\sigma(z)\n",
    "\\left(1 - \\sigma(z)\\right)\n",
    "\\end{align}\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**9. Consider our diagonal matrix $\\grad_{z^{(2)}} h^{(2)}$ with $\\sigma(z^{(2)}_i)(1 - \\sigma(z^{(2)}_i))$ along the diagonal. We know that:**\n",
    "\n",
    "\\\\[\n",
    "\\grad_{z^{(2)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\left(\\grad_{z^{(2)}} h^{(2)}\\right)\n",
    "\\cdot\n",
    "\\left(\\grad_{h^{(2)}} CE(h^{(3)}, y)\\right)\n",
    "\\\\]\n",
    "\n",
    "**When we take this product, what happens to each element of $\\grad_{h^{(2)}} CE(h^{(3)}, y)$? Explain.**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each element $\\left(\\grad_{h^{(2)}} CE(h^{(3)}, y)\\right)_i$ is scaled by $\\sigma(z^{(2)}_i)(1 - \\sigma(z^{(2)}_i))$.\n",
    "\n",
    "The reason is that the impact of $z^{(2)}_i$ on $h^{(2)}_i$ is $\\sigma(z^{(2)}_i)(1 - \\sigma(z^{(2)}_i))$. And then the impact of $h^{(2)}_i$ on the loss is $\\left(\\grad_{h^{(2)}} CE(h^{(3)}, y)\\right)_i$.\n",
    "\n",
    "So they multiply together."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**10. This sounds like a job for the Hadamard AKA coordinatewise product $\\odot$. Write a formula for $\\grad_{z^{(2)}} CE(h^{(3)}, y)$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{z^{(2)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\sigma(z^{(2)}) \\odot (1 - \\sigma(z^{(2)}))\n",
    "\\odot\n",
    "\\grad_{h^{(2)}} CE(h^{(3)}, y)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Backprop to $\\grad_{b^{(2)}} CE(h^{(3)}, y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. What is the shape of $\\grad_{b^{(2)}} z^{(2)}$?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$(256, 256)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. What is $\\fpartial{z^{(2)}_j}{b^{(2)}_j}$? Why?**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $z^{(2)}_j = b^{(2)}_j + \\sum_{i=0}^{512} h^{(1)}_i W^{(2)}_{i, j}$, the partial is $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. Why does $\\grad_{b^{(2)}} z^{(2)}$ equal the identity matrix (ones along the diagonal, zeros everywhere else?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By the above equation all the diagonal entries equal one. Also the non-diagonal entries must all be zero because no $b^{(2)}_j$ affects any other $z^{(2)}_k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. For an identity matrix $I$, what is $IM$? Why?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is $M$, by the above reasoning about the action of diagonal matrices as unit-vector stretchers. The identity matrix doesn't do anything to $xI$. So $xIM = xM$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5. Therefore, what is $\\grad_{b^{(2)}} CE(h^{(3)}, y)$?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is $\\grad_{z^{(2)}} CE(h^{(3)}, y)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backprop to $\\grad_{W^{(2)}} CE(h^{(3)}, y)$ using $\\grad_{z^{(2)}} CE(h^{(3)}, y)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. Consider $\\grad_{W^{(2)}} CE(h^{(3)}, y)$. What is its shape?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is $(512, 256)$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Consider a single entry $W^{(2)}_{i, j}$. We want to calculate $\\fpartial{}{W^{(2)}_{i, j}} CE(h^{(3)}, y)$. Let's first calculate $\\fpartial{}{W^{(2)}_{i, j}} z^{(2)}_j$. Explain the formula.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since\n",
    "\n",
    "\\\\[\n",
    "z^{(2)}_j = b^{(2)}_j + \\sum_{i = 0}^{512} h^{(1)}_i W^{(2)}_{i, j}\n",
    "\\\\]\n",
    "\n",
    "we have that the partial is $h^{(1)}_i$. That's because this weight connects $h^{(1)}_i$ to $z^{(2)}_j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. Consider $\\fpartial{}{W^{(2)}_{i, j}} z^{(2)}_k$ for any $k\\ne j$. What is this? Why?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is zero because this weight does not contribute to $z^{(2)}_k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. What is $\\grad_{W^{(2)}_{i, j}} z^{(2)}$ then? (Carefull: this is a gradient with respect to a single variable).**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is all zeros, except for $h^{(1)}_i$ at position $j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5. Using the chain rule for $\\grad_{W^{(2)}_{i, j}} CE(h^{(3)}, y) = \\grad_{W^{(2)}_{i, j}} z^{(2)} \\cdot \\grad_{z^{(2)}} CE(h^{(3)}, y)$, what do you compute?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We get $h^{(1)}_i \\left(\\grad_{z^{(2)}} CE(h^{(3)}, y))\\right)_j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6. So every entry $(i, j)$ of $\\grad_{W^{(2)}} CE(h^{(3)}, y)$ consists of two factors. Which factor is constant across *rows*? Explain.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$h^{(1)}_i$. The reason is that all the weights in row $i$ connect the hidden unit $h^{(1)}_i$ to various units of $z^{(2)}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7. What factor is constant across *columns*? Explain.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\left(\\grad_{z^{(2)}} CE(h^{(3)}, y))\\right)_j$. The reason is that every weight in column $j$ connects to $z^{(2)}_j$, and the change in this unit is captured by this gradient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8. Therefore write $\\grad_{W^{(2)}} CE(h^{(3)}, y)$ as an outer product.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$h^{(1)} \\otimes \\grad_{z^{(2)}} CE(h^{(3)}, y))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Further Backprop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. At this point, you just repeat the process. You can calculate $\\grad_{h^{(1)}} CE(h^{(3)}, y)$ as before. What dot product do you use?**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{h^{(1)}} CE(h^{(3)}, y)\n",
    "=\n",
    "W^{(2)}\n",
    "\\cdot\n",
    "\\grad_{z^{(2)}} CE(h^{(3)}, y)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Likewise $\\grad_{z^{(1)}} CE(z^{(3)}, y)$. What Hadamard product do you do?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{z^{(1)}} CE(h^{(3)}, y)\n",
    "=\n",
    "\\left(\n",
    "    \\sigma(z^{(1)})\n",
    "    \\odot\n",
    "    (1 - \\sigma(z^{(2)}))\n",
    "\\right)\n",
    "\\odot\n",
    "\\grad_{h^{(1)}} CE(h^{(3)}, y)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. We know that the prior gradient is equal to $\\grad_{b^{(1)}} CE(z^{(3)}, y)$. What outer product do you need for $\\grad_{W^{(1)}} CE(z^{(3)}, y)$?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\\\[\n",
    "\\grad_{W^{(1)}} CE(z^{(3)}, y)\n",
    "=\n",
    "x\n",
    "\\otimes\n",
    "\\grad_{z^{(1)}} CE(h^{(3)}, y)\n",
    "\\\\]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python (default)",
   "language": "python",
   "name": "conda-default"
  },
  "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}