{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=backprop-md-1 fw=all -->\n",
    "\n",
    "# Forward Propagation, Backward Propagation, and Computational Graphs\n",
    "\n",
    "So far, we have trained our models\n",
    "with minibatch stochastic gradient descent.\n",
    "However, when we implemented the algorithm,\n",
    "we only worried about the calculations involved\n",
    "in *forward propagation* through the model.\n",
    "When it came time to calculate the gradients,\n",
    "we just invoked the backpropagation function provided by the deep learning framework.\n",
    "\n",
    "The automatic calculation of gradients\n",
    "simplifies\n",
    "the implementation of deep learning algorithms.\n",
    "Before automatic differentiation,\n",
    "even small changes to complicated models required\n",
    "recalculating complicated derivatives by hand.\n",
    "Surprisingly often, academic papers had to allocate\n",
    "numerous pages to deriving update rules.\n",
    "While we must continue to rely on automatic differentiation\n",
    "so we can focus on the interesting parts,\n",
    "you ought to know how these gradients\n",
    "are calculated under the hood\n",
    "if you want to go beyond a shallow\n",
    "understanding of deep learning.\n",
    "\n",
    "In this section, we take a deep dive\n",
    "into the details of *backward propagation*\n",
    "(more commonly called *backpropagation*).\n",
    "To convey some insight for both the\n",
    "techniques and their implementations,\n",
    "we rely on some basic mathematics and computational graphs.\n",
    "To start, we focus our exposition on\n",
    "a one-hidden-layer MLP\n",
    "with weight decay ($\\ell_2$ regularization, introduced in that section)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=backprop-md-2 fw=all -->\n",
    "\n",
    "## Forward Propagation\n",
    "\n",
    "*Forward propagation* (or *forward pass*) refers to the calculation and storage\n",
    "of intermediate variables (including outputs)\n",
    "for a neural network in order\n",
    "from the input layer to the output layer.\n",
    "We now work step-by-step through the mechanics\n",
    "of a neural network with one hidden layer.\n",
    "This may seem tedious but in the eternal words\n",
    "of funk virtuoso James Brown,\n",
    "you must \"pay the cost to be the boss\".\n",
    "\n",
    "\n",
    "For the sake of simplicity, let's assume\n",
    "that the input example is $\\mathbf{x}\\in \\mathbb{R}^d$\n",
    "and that our hidden layer does not include a bias term.\n",
    "Note a switch of convention: that section processed a minibatch of *rows*\n",
    "via $\\mathbf{X}\\mathbf{W}$, whereas here we track a single example as a *column*\n",
    "vector acted on from the left, $\\mathbf{W}\\mathbf{x}$, so every weight matrix in\n",
    "this section is transposed relative to its counterpart there.\n",
    "Here the intermediate variable is:\n",
    "\n",
    "$$\\mathbf{z}= \\mathbf{W}^{(1)} \\mathbf{x},$$\n",
    "\n",
    "where $\\mathbf{W}^{(1)} \\in \\mathbb{R}^{h \\times d}$\n",
    "is the weight parameter of the hidden layer.\n",
    "After running the intermediate variable\n",
    "$\\mathbf{z}\\in \\mathbb{R}^h$ through the\n",
    "activation function $\\phi$\n",
    "we obtain our hidden activation vector of length $h$:\n",
    "\n",
    "$$\\mathbf{h}= \\phi (\\mathbf{z}).$$\n",
    "\n",
    "The hidden layer output $\\mathbf{h}$\n",
    "is also an intermediate variable.\n",
    "Assuming that the parameters of the output layer\n",
    "possess only a weight of\n",
    "$\\mathbf{W}^{(2)} \\in \\mathbb{R}^{q \\times h}$,\n",
    "we can obtain an output layer variable\n",
    "with a vector of length $q$:\n",
    "\n",
    "$$\\mathbf{o}= \\mathbf{W}^{(2)} \\mathbf{h}.$$\n",
    "\n",
    "Assuming that the loss function is $l$\n",
    "and the example label is $y$,\n",
    "we can then calculate the loss term\n",
    "for a single data example,\n",
    "\n",
    "$$L = l(\\mathbf{o}, y).$$\n",
    "\n",
    "Recall the $\\ell_2$ regularization term (that section): given\n",
    "the hyperparameter $\\lambda$,\n",
    "the regularization term is\n",
    "\n",
    "$$s = \\frac{\\lambda}{2} \\left(\\|\\mathbf{W}^{(1)}\\|_\\textrm{F}^2 + \\|\\mathbf{W}^{(2)}\\|_\\textrm{F}^2\\right),$$\n",
    "\n",
    "where the Frobenius norm of the matrix\n",
    "is simply the $\\ell_2$ norm applied\n",
    "after flattening the matrix into a vector.\n",
    "Finally, the model's regularized loss\n",
    "on a given data example is:\n",
    "\n",
    "$$J = L + s.$$\n",
    "\n",
    "We refer to $J$ as the *objective function*\n",
    "in the following discussion.\n",
    "\n",
    "\n",
    "## Computational Graph of Forward Propagation\n",
    "\n",
    "Plotting *computational graphs* helps us visualize\n",
    "the dependencies of operators\n",
    "and variables within the calculation.\n",
    "the figure contains the graph associated\n",
    "with the simple network described above,\n",
    "where squares denote variables and circles denote operators.\n",
    "The lower-left corner signifies the input\n",
    "and the upper-right corner is the output.\n",
    "Notice that the directions of the arrows\n",
    "(which illustrate data flow)\n",
    "are primarily rightward and upward.\n",
    "\n",
    "![Computational graph of forward propagation.](../img/mdl-mlp-forward-graph.svg)\n",
    "\n",
    "## Backpropagation\n",
    "\n",
    "*Backpropagation* refers to the method of calculating\n",
    "the gradient of neural network parameters.\n",
    "In short, the method traverses the network in reverse order,\n",
    "from the output to the input layer,\n",
    "according to the *chain rule* from calculus (that section).\n",
    "The algorithm stores any intermediate variables\n",
    "(partial derivatives)\n",
    "required while calculating the gradient\n",
    "with respect to some parameters.\n",
    "Assume that we have functions\n",
    "$\\mathsf{Y}=f(\\mathsf{X})$\n",
    "and $\\mathsf{Z}=g(\\mathsf{Y})$,\n",
    "in which the input and the output\n",
    "$\\mathsf{X}, \\mathsf{Y}, \\mathsf{Z}$\n",
    "are tensors of arbitrary shapes.\n",
    "By using the chain rule,\n",
    "we can compute the derivative\n",
    "of $\\mathsf{Z}$ with respect to $\\mathsf{X}$ via\n",
    "\n",
    "$$\\frac{\\partial \\mathsf{Z}}{\\partial \\mathsf{X}} = \\textrm{prod}\\left(\\frac{\\partial \\mathsf{Z}}{\\partial \\mathsf{Y}}, \\frac{\\partial \\mathsf{Y}}{\\partial \\mathsf{X}}\\right).$$\n",
    "\n",
    "Here we use the $\\textrm{prod}$ operator\n",
    "to multiply its arguments\n",
    "after the necessary operations,\n",
    "such as transposition and swapping input positions,\n",
    "have been carried out.\n",
    "For vectors, this is straightforward:\n",
    "it is simply matrix--matrix multiplication.\n",
    "For higher dimensional tensors,\n",
    "we use the appropriate counterpart.\n",
    "The operator $\\textrm{prod}$ hides all the notational overhead;\n",
    "what it computes is made precise as *vector--Jacobian products*\n",
    "in that section.\n",
    "\n",
    "Recall that\n",
    "the parameters of the simple network with one hidden layer,\n",
    "whose computational graph is in the figure,\n",
    "are $\\mathbf{W}^{(1)}$ and $\\mathbf{W}^{(2)}$.\n",
    "The objective of backpropagation is to\n",
    "calculate the gradients $\\partial J/\\partial \\mathbf{W}^{(1)}$\n",
    "and $\\partial J/\\partial \\mathbf{W}^{(2)}$.\n",
    "To accomplish this, we apply the chain rule\n",
    "and calculate, in turn, the gradient of\n",
    "each intermediate variable and parameter.\n",
    "The order of calculations is reversed\n",
    "relative to those performed in forward propagation,\n",
    "since we need to start with the outcome of the computational graph\n",
    "and work our way towards the parameters.\n",
    "The first step is to calculate the gradients\n",
    "of the objective function $J=L+s$\n",
    "with respect to the loss term $L$\n",
    "and the regularization term $s$:\n",
    "\n",
    "$$\\frac{\\partial J}{\\partial L} = 1 \\; \\textrm{and} \\; \\frac{\\partial J}{\\partial s} = 1.$$\n",
    "\n",
    "Next, we compute the gradient of the objective function\n",
    "with respect to the output-layer variable $\\mathbf{o}$\n",
    "according to the chain rule:\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{o}}\n",
    "= \\textrm{prod}\\left(\\frac{\\partial J}{\\partial L}, \\frac{\\partial L}{\\partial \\mathbf{o}}\\right)\n",
    "= \\frac{\\partial L}{\\partial \\mathbf{o}}\n",
    "\\in \\mathbb{R}^q.\n",
    "$$\n",
    "\n",
    "Next, we calculate the gradients\n",
    "of the regularization term\n",
    "with respect to both parameters:\n",
    "\n",
    "$$\\frac{\\partial s}{\\partial \\mathbf{W}^{(1)}} = \\lambda \\mathbf{W}^{(1)}\n",
    "\\; \\textrm{and} \\;\n",
    "\\frac{\\partial s}{\\partial \\mathbf{W}^{(2)}} = \\lambda \\mathbf{W}^{(2)}.$$\n",
    "\n",
    "Now we are able to calculate the gradient\n",
    "$\\partial J/\\partial \\mathbf{W}^{(2)} \\in \\mathbb{R}^{q \\times h}$\n",
    "of the model parameters closest to the output layer.\n",
    "Using the chain rule yields:\n",
    "\n",
    "$$\\frac{\\partial J}{\\partial \\mathbf{W}^{(2)}}= \\textrm{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{o}}, \\frac{\\partial \\mathbf{o}}{\\partial \\mathbf{W}^{(2)}}\\right) + \\textrm{prod}\\left(\\frac{\\partial J}{\\partial s}, \\frac{\\partial s}{\\partial \\mathbf{W}^{(2)}}\\right)= \\frac{\\partial J}{\\partial \\mathbf{o}} \\mathbf{h}^\\top + \\lambda \\mathbf{W}^{(2)}.$$\n",
    "\n",
    "The \"+\" in the equation encodes a general rule:\n",
    "when a variable reaches the output along several paths, its gradient is the\n",
    "**sum** of the gradients arriving along each path.\n",
    "Here $\\mathbf{W}^{(2)}$ affects $J$ twice, through the prediction path\n",
    "$J \\leftarrow L \\leftarrow \\mathbf{o} \\leftarrow \\mathbf{W}^{(2)}$ and through\n",
    "the regularizer path $J \\leftarrow s \\leftarrow \\mathbf{W}^{(2)}$, and the two\n",
    "contributions add. Forgetting to *accumulate* at such forks (overwriting\n",
    "instead of adding) is among the most common bugs in hand-written backward\n",
    "passes.\n",
    "\n",
    "To obtain the gradient with respect to $\\mathbf{W}^{(1)}$\n",
    "we need to continue backpropagation\n",
    "along the output layer to the hidden layer.\n",
    "The gradient with respect to the hidden layer output\n",
    "$\\partial J/\\partial \\mathbf{h} \\in \\mathbb{R}^h$ is given by\n",
    "\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{h}}\n",
    "= \\textrm{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{o}}, \\frac{\\partial \\mathbf{o}}{\\partial \\mathbf{h}}\\right)\n",
    "= {\\mathbf{W}^{(2)}}^\\top \\frac{\\partial J}{\\partial \\mathbf{o}}.\n",
    "$$\n",
    "\n",
    "Since the activation function $\\phi$ applies elementwise,\n",
    "calculating the gradient $\\partial J/\\partial \\mathbf{z} \\in \\mathbb{R}^h$\n",
    "of the intermediate variable $\\mathbf{z}$\n",
    "requires that we use the elementwise multiplication operator,\n",
    "which we denote by $\\odot$:\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{z}}\n",
    "= \\textrm{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{h}}, \\frac{\\partial \\mathbf{h}}{\\partial \\mathbf{z}}\\right)\n",
    "= \\frac{\\partial J}{\\partial \\mathbf{h}} \\odot \\phi'\\left(\\mathbf{z}\\right).\n",
    "$$\n",
    "\n",
    "Finally, we can obtain the gradient\n",
    "$\\partial J/\\partial \\mathbf{W}^{(1)} \\in \\mathbb{R}^{h \\times d}$\n",
    "of the model parameters closest to the input layer.\n",
    "According to the chain rule, we get\n",
    "\n",
    "$$\n",
    "\\frac{\\partial J}{\\partial \\mathbf{W}^{(1)}}\n",
    "= \\textrm{prod}\\left(\\frac{\\partial J}{\\partial \\mathbf{z}}, \\frac{\\partial \\mathbf{z}}{\\partial \\mathbf{W}^{(1)}}\\right) + \\textrm{prod}\\left(\\frac{\\partial J}{\\partial s}, \\frac{\\partial s}{\\partial \\mathbf{W}^{(1)}}\\right)\n",
    "= \\frac{\\partial J}{\\partial \\mathbf{z}} \\mathbf{x}^\\top + \\lambda \\mathbf{W}^{(1)}.\n",
    "$$\n",
    "\n",
    "### A Worked Example\n",
    "\n",
    "Symbols can hide what backpropagation actually *does*, so let us push real\n",
    "numbers through a graph. We follow the one rule that produced every equation\n",
    "above: at each node, multiply the gradient arriving from downstream by the\n",
    "node's *local* derivative.\n",
    "\n",
    "Start with the simplest non-trivial graph, $e = (a + b)\\,c$, evaluated at\n",
    "$a = 2$, $b = 1$, $c = -3$. The *forward pass* computes the intermediate\n",
    "$d = a + b = 3$ and then $e = d\\,c = -9$. For the *backward pass* we seed\n",
    "$\\partial e/\\partial e = 1$ and walk back. The multiply node $e = d\\,c$ has\n",
    "local derivatives $\\partial e/\\partial d = c = -3$ and\n",
    "$\\partial e/\\partial c = d = 3$. The add node $d = a + b$ has\n",
    "$\\partial d/\\partial a = \\partial d/\\partial b = 1$, so it simply *passes its\n",
    "incoming gradient through* to both inputs. Chaining,\n",
    "\n",
    "$$\\frac{\\partial e}{\\partial a} = \\frac{\\partial e}{\\partial d}\\frac{\\partial d}{\\partial a} = -3,\\quad\n",
    "  \\frac{\\partial e}{\\partial b} = -3,\\quad\n",
    "  \\frac{\\partial e}{\\partial c} = 3.$$\n",
    "\n",
    "This is the whole algorithm in miniature: *add* nodes broadcast the upstream\n",
    "gradient unchanged, *multiply* nodes scale it by the other input. Every backward\n",
    "equation in this section is an instance of this one move.\n",
    "\n",
    "Now run the same machinery on a network of the form above, shrunk to\n",
    "$d = h = 2$ inputs and hidden units, $q = 1$ output, with ReLU activation\n",
    "$\\phi(z) = \\max(0, z)$ and (for clarity) no regularization, $\\lambda = 0$. Take\n",
    "\n",
    "$$\\mathbf{x} = \\begin{bmatrix} 1 \\\\ 2 \\end{bmatrix},\\quad\n",
    "  \\mathbf{W}^{(1)} = \\begin{bmatrix} 1 & -1 \\\\ 0 & \\phantom{-}1 \\end{bmatrix},\\quad\n",
    "  \\mathbf{W}^{(2)} = \\begin{bmatrix} 2 & -1 \\end{bmatrix},\\quad y = 0,$$\n",
    "\n",
    "and squared-error loss $L = \\tfrac12 (o - y)^2$. The *forward pass* gives\n",
    "$\\mathbf{z} = \\mathbf{W}^{(1)}\\mathbf{x} = [-1,\\ 2]^\\top$, so\n",
    "$\\mathbf{h} = \\phi(\\mathbf{z}) = [0,\\ 2]^\\top$ (the first unit is dead),\n",
    "$o = \\mathbf{W}^{(2)}\\mathbf{h} = -2$, and $L = \\tfrac12(-2)^2 = 2$. For the\n",
    "*backward pass*, $\\partial L/\\partial o = o - y = -2$, and then, reading the\n",
    "section's equations top to bottom,\n",
    "\n",
    "$$\\frac{\\partial L}{\\partial \\mathbf{W}^{(2)}} = \\frac{\\partial L}{\\partial o}\\,\\mathbf{h}^\\top = -2\\,[0,\\ 2] = [0,\\ -4],$$\n",
    "\n",
    "$$\\frac{\\partial L}{\\partial \\mathbf{h}} = {\\mathbf{W}^{(2)}}^\\top \\frac{\\partial L}{\\partial o} = [-4,\\ 2]^\\top,\\qquad\n",
    "  \\frac{\\partial L}{\\partial \\mathbf{z}} = \\frac{\\partial L}{\\partial \\mathbf{h}} \\odot \\phi'(\\mathbf{z}) = [-4,\\ 2]^\\top \\odot [0,\\ 1]^\\top = [0,\\ 2]^\\top,$$\n",
    "\n",
    "using $\\phi'(z) = \\mathbf{1}[z > 0]$, which is exactly where the *dead* first\n",
    "unit blocks the gradient. Finally,\n",
    "\n",
    "$$\\frac{\\partial L}{\\partial \\mathbf{W}^{(1)}} = \\frac{\\partial L}{\\partial \\mathbf{z}}\\,\\mathbf{x}^\\top\n",
    "  = \\begin{bmatrix} 0 \\\\ 2 \\end{bmatrix}[1,\\ 2]\n",
    "  = \\begin{bmatrix} 0 & 0 \\\\ 2 & 4 \\end{bmatrix}.$$\n",
    "\n",
    "the figure traces these numbers through the graph,\n",
    "forward in black and backward in blue. Notice that the row of\n",
    "$\\partial L/\\partial \\mathbf{W}^{(1)}$ feeding the dead unit is entirely zero:\n",
    "no gradient means no learning signal, the concrete face of the \"dying ReLU\" we\n",
    "met in that section. You can confirm every number here in a few lines of\n",
    "automatic differentiation (that section): rebuild the same tensors\n",
    "with gradient tracking, run the forward pass, sweep back through the graph, and\n",
    "compare against the gradients we just derived by hand. The PyTorch cell below\n",
    "does exactly this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=backprop-md-3 fw=all -->\n",
    "\n",
    "Every printed gradient matches the hand computation, down to the zeroed-out\n",
    "row for the dead unit. (The $-0$ in $\\partial L/\\partial \\mathbf{W}^{(2)}$ is\n",
    "floating point's *signed zero*, an artifact of multiplying $h_1 = 0$ by the\n",
    "negative upstream gradient; it compares equal to $0$.)\n",
    "\n",
    "![The worked example as a computational graph, with $\\lambda=0$. The forward pass (black) carries values from the input $\\mathbf{x}$ to the loss $L$; backpropagation (blue) walks the same graph in reverse, multiplying each node's local derivative to accumulate the gradients $\\partial L/\\partial\\mathbf{W}^{(2)}$ and $\\partial L/\\partial\\mathbf{W}^{(1)}$. The dead first ReLU unit ($z_1=-1$) zeros the gradient flowing into the top row of $\\mathbf{W}^{(1)}$.](../img/mdl-mlp-backprop-graph.svg)\n",
    "\n",
    "### From the Chain Rule to Autograd\n",
    "\n",
    "What we have just done by hand is precisely what a deep learning framework does\n",
    "when you ask it for gradients: it records the computational graph during the forward\n",
    "pass, seeds a gradient of $1$ at the scalar objective, and sweeps the graph in\n",
    "reverse, multiplying the local derivative at each node (our $\\textrm{prod}$) to\n",
    "accumulate the gradient with respect to every parameter in a *single* pass. This\n",
    "output-to-input sweep is *reverse-mode* automatic differentiation, and it is cheap\n",
    "exactly when there are many parameters and one scalar loss, the deep learning\n",
    "regime. We use it throughout the book and developed its mechanics, including when\n",
    "the opposite *forward mode* is preferable, in that section; the full\n",
    "theory, with both modes expressed as Jacobian products and the memory\n",
    "trade-offs they imply, is developed in\n",
    "that section.\n",
    "\n",
    "## Training Neural Networks\n",
    "\n",
    "When training neural networks,\n",
    "forward and backward propagation depend on each other.\n",
    "In particular, for forward propagation,\n",
    "we traverse the computational graph in the direction of dependencies\n",
    "and compute all the variables on its path.\n",
    "These are then used for backpropagation\n",
    "where the compute order on the graph is reversed.\n",
    "\n",
    "Take the aforementioned simple network as an illustrative example.\n",
    "On the one hand,\n",
    "computing the regularization term the equation\n",
    "during forward propagation\n",
    "depends on the current values of model parameters $\\mathbf{W}^{(1)}$ and $\\mathbf{W}^{(2)}$.\n",
    "They are given by the optimization algorithm according to backpropagation in the most recent iteration.\n",
    "On the other hand,\n",
    "the gradient calculation for the parameter\n",
    "the equation during backpropagation\n",
    "depends on the current value of the hidden layer output $\\mathbf{h}$,\n",
    "which is given by forward propagation.\n",
    "\n",
    "\n",
    "Therefore when training neural networks, once model parameters are initialized,\n",
    "we alternate forward propagation with backpropagation,\n",
    "updating model parameters using gradients given by backpropagation.\n",
    "Note that backpropagation reuses the stored intermediate values from forward propagation to avoid duplicate calculations.\n",
    "One of the consequences is that we need to retain\n",
    "the intermediate values until backpropagation is complete.\n",
    "This is also one of the reasons why training\n",
    "requires significantly more memory than plain prediction.\n",
    "Besides, the size of such intermediate values is roughly\n",
    "proportional to the number of network layers and the batch size.\n",
    "Thus,\n",
    "training deeper networks using larger batch sizes\n",
    "more easily leads to *out-of-memory* errors.\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "Forward propagation sequentially calculates and stores intermediate variables within the computational graph defined by the neural network. It proceeds from the input to the output layer.\n",
    "Backpropagation sequentially calculates and stores the gradients of intermediate variables and parameters within the neural network in the reversed order.\n",
    "When training deep learning models, forward propagation and backpropagation are interdependent,\n",
    "and training requires significantly more memory than prediction.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Assume that the inputs $\\mathbf{X}$ to some scalar function $f$ are $n \\times m$ matrices. What is the dimensionality of the gradient of $f$ with respect to $\\mathbf{X}$?\n",
    "1. Add a bias to the hidden layer of the model described in this section (you do not need to include bias in the regularization term).\n",
    "    1. Draw the corresponding computational graph.\n",
    "    1. Derive the forward and backward propagation equations.\n",
    "1. Compute the memory footprint for training and prediction in the model described in this section.\n",
    "1. Assume that you want to compute second derivatives. What happens to the computational graph? How long do you expect the calculation to take?\n",
    "1. Assume that the computational graph is too large for your GPU.\n",
    "    1. Can you partition it over more than one GPU?\n",
    "    1. What are the advantages and disadvantages over training on a smaller minibatch?\n",
    "1. Build a miniature autograd engine and use it to re-derive this section's worked example.\n",
    "    1. Write a scalar `Value` class that records, for each result, its inputs and the operation that produced it (the computational graph), supporting `+`, `*`, and `relu`. (*Hint:* implement `__add__` and `__mul__` so that each returns a new `Value` holding references to its parents and a small function that propagates the gradient one step.)\n",
    "    1. Implement `backward()`: topologically sort the graph, seed the output's gradient with $1$, and sweep the nodes in reverse order, letting each node pass its gradient to its parents. Make sure gradients *accumulate* (`+=`, not `=`) when a value is used more than once (the fork rule from the equation).\n",
    "    1. Reproduce the worked example with your engine (unroll the matrix products into scalars) and check all four gradients.\n",
    "    1. For a chain of three inputs feeding three outputs feeding one loss, the sum-over-paths view of the chain rule enumerates $3 \\times 3 = 9$ paths, yet your engine touches each edge only once. Show that reverse mode computes $(\\alpha+\\beta+\\gamma)(\\delta+\\epsilon+\\zeta)$ instead of expanding all nine products, and explain why this factoring is exactly what makes backpropagation affordable.\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/102)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-mxnet",
   "display_name": "d2l (MXNet)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
