Ch04_The_Preliminaries_A_Crashcourse/Automatic_Differentiation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Automatic Differentiation\n",
    "\n",
    "In machine learning, we *train* models, updating them successively so that they get better and better as they see more and more data. Usually, *getting better* means minimizing a *loss function*, a score that answers the question \"how *bad* is our model?\" With neural networks, we typically choose loss functions that are differentiable with respect to our parameters.\n",
    "Put simply, this means that for each of the model's parameters, we can determine how much *increasing* or *decreasing* it might affect the loss. While the calculations for taking these derivatives are straightforward, requiring only some basic calculus, for complex models, working out the updates by hand can be a pain (and often error-prone)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The autograd package expedites this work by automatically calculating derivatives. And while many other libraries require that we compile a symbolic graph to take automatic derivatives, `autograd` allows us to take derivatives while writing  ordinary imperative code. Every time we pass data through our model, `autograd` builds a graph on the fly, tracking which data combined through which operations to produce the output. This graph enables `autograd` to subsequently backpropagate gradients on command. Here *backpropagate* simply means to trace through the compute graph, filling in the partial derivatives with respect to each parameter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch.autograd import Variable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Simple Example\n",
    "\n",
    "As a toy example, say that we are interested in differentiating the mapping $y = 2\\mathbf{x}^{\\top}\\mathbf{x}$ with respect to the column vector $\\mathbf{x}$. To start, let's create the variable `x` and assign it an initial value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[0.],\n",
      "        [1.],\n",
      "        [2.],\n",
      "        [3.]], requires_grad=True)\n"
     ]
    }
   ],
   "source": [
    "x = Variable(torch.arange(4, dtype=torch.float32).reshape((4, 1)), requires_grad=True)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we compute the gradient of ``y`` with respect to ``x``, we will need a place to store it. We can tell a tensor that we plan to store a gradient by the ``requires_grad=True`` keyword."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are going to compute ``y`` and PyTorch will generate a computation graph on the fly. Autograd is reverse automatic differentiation system. Conceptually, autograd records a graph recording all of the operations that created the data as you execute operations, giving you a directed acyclic graph whose leaves are the input tensors and roots are the output tensors. By tracing this graph from roots to leaves, you can automatically compute the gradients using the chain rule.\n",
    "\n",
    "Note that building the computation graph requires a nontrivial amount of computation. So PyTorch will *only* build the graph when explicitly told to do so. For a tensor to be “recordable”, it must be wrapped with torch.autograd.Variable. The Variable class provides almost the same API as Tensor, but augments it with the ability to interplay with torch.autograd.Function in order to be differentiated automatically. More precisely, a Variable records the history of operations on a Tensor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[28.]], grad_fn=<MulBackward0>)\n"
     ]
    }
   ],
   "source": [
    "y = 2*torch.mm(x.t(),x)\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since the shape of `x` is (4, 1), `y` is a scalar. Next, we can automatically find the gradient by calling the `backward` function. It should be noted that if `y` is not a scalar, PyTorch will first sum the elements in `y` to get the new variable by default, and then find the gradient of the variable with respect to `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "y.backward()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since every Variable except for inputs is the result of an operation, each Variable has an associated grad_fn, which is the torch.autograd.Function that is used to compute the backward step. For inputs it is None:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x.grad: tensor([[ 0.],\n",
      "        [ 4.],\n",
      "        [ 8.],\n",
      "        [12.]])\n",
      "x.grad_fn: None\n",
      "y.grad_fn: <MulBackward0 object at 0x105e8db00>\n"
     ]
    }
   ],
   "source": [
    "print(\"x.grad:\", x.grad)\n",
    "print(\"x.grad_fn:\", x.grad_fn)\n",
    "print(\"y.grad_fn:\", y.grad_fn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The gradient of the function $y = 2\\mathbf{x}^{\\top}\\mathbf{x}$ with respect to $\\mathbf{x}$ should be $4\\mathbf{x}$. Now let's verify that the gradient produced is correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "tensor([[ 0.],\n",
      "        [ 4.],\n",
      "        [ 8.],\n",
      "        [12.]])\n"
     ]
    }
   ],
   "source": [
    "print((x.grad - 4*x).norm().item() == 0)\n",
    "print(x.grad)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Training Mode and Evaluation Mode\n",
    "\n",
    "`Model` will change the running mode to the evaluation mode on calling `model.eval()` or to the training mode on calling `model.train()`.\n",
    "\n",
    "In some cases, the same model behaves differently in the training and prediction modes (e.g. when using neural techniques such as dropout and batch normalization). In other cases, some models may store more auxiliary variables to make computing gradients easier. We will cover these differences in detail in later chapters. For now, you do not need to worry about them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computing the Gradient of Python Control Flow\n",
    "\n",
    "One benefit of using automatic differentiation is that even if the computational graph of the function contains Python's control flow (such as conditional and loop control), we may still be able to find the gradient of a variable. Consider the following program:  It should be emphasized that the number of iterations of the loop (while loop) and the execution of the conditional judgment (if statement) depend on the value of the input `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(a):\n",
    "    b = a * 2\n",
    "    while b.norm().item() < 1000:\n",
    "        b = b * 2\n",
    "    if b.sum().item() > 0:\n",
    "        c = b\n",
    "    else:\n",
    "        c = 100 * b\n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the number of iterations of the while loop and the execution of the conditional statement (if then else) depend on the value of `a`. To compute gradients, we need to `record` the calculation, and then call the `backward` function to calculate the gradient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = torch.randn(size=(1,))\n",
    "a.requires_grad=True\n",
    "d = f(a)\n",
    "d.backward()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's analyze the `f` function defined above. As you can see, it is piecewise linear in its input `a`. In other words, for any `a` there exists some constant such that for a given range `f(a) = g * a`. Consequently `d / a` allows us to verify that the gradient is correct:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([1], dtype=torch.uint8)\n"
     ]
    }
   ],
   "source": [
    "print(a.grad == (d / a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Head gradients and the chain rule\n",
    "\n",
    "*Caution: This part is tricky and not necessary to understanding subsequent sections. That said, it is needed if you want to build new layers from scratch. You can skip this on a first read.*\n",
    "\n",
    "Sometimes when we call the backward method, e.g. `y.backward()`, where\n",
    "`y` is a function of `x` we are just interested in the derivative of\n",
    "`y` with respect to `x`. Mathematicians write this as\n",
    "$\\frac{dy(x)}{dx}$. At other times, we may be interested in the\n",
    "gradient of `z` with respect to `x`, where `z` is a function of `y`,\n",
    "which in turn, is a function of `x`. That is, we are interested in\n",
    "$\\frac{d}{dx} z(y(x))$. Recall that by the chain rule\n",
    "\n",
    "$$\\frac{d}{dx} z(y(x)) = \\frac{dz(y)}{dy} \\frac{dy(x)}{dx}.$$\n",
    "\n",
    "So, when ``y`` is part of a larger function ``z`` and we want ``x.grad`` to store $\\frac{dz}{dx}$, we can pass in the *head gradient* $\\frac{dz}{dy}$ as an input to ``backward()``. The default argument is ``torch.ones_like(y)``. See [Wikipedia](https://en.wikipedia.org/wiki/Chain_rule) for more details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[0.0000],\n",
      "        [4.0000],\n",
      "        [0.8000],\n",
      "        [0.1200]])\n"
     ]
    }
   ],
   "source": [
    "x = Variable(torch.tensor([[0.],[1.],[2.],[3.]]), requires_grad=True)\n",
    "y = x * 2\n",
    "z = y * x\n",
    "\n",
    "head_gradient = torch.tensor([[10], [1.], [.1], [.01]])\n",
    "z.backward(head_gradient)\n",
    "print(x.grad)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "* PyTorch provides an `autograd` package to automate the derivation process.\n",
    "* PyTorch's `autograd` package can be used to derive general imperative programs.\n",
    "* The running modes of PyTorch include the training mode and the evaluation mode."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "\n",
    "1. In the control flow example where we calculate the derivative of `d` with respect to `a`, what would happen if we changed the variable `a` to a random vector or matrix. At this point, the result of the calculation `f(a)` is no longer a scalar. What happens to the result? How do we analyze this?\n",
    "1. Redesign an example of finding the gradient of the control flow. Run and analyze the result.\n",
    "1. In a second-price auction (such as in eBay or in computational advertising), the winning bidder pays the second-highest price. Compute the gradient of the final price with respect to the winning bidder's bid using `autograd`. What does the result tell you about the mechanism? If you are curious to learn more about second-price auctions, check out this paper by [Edelman, Ostrovski and Schwartz, 2005](https://www.benedelman.org/publications/gsp-060801.pdf).\n",
    "1. Why is the second derivative much more expensive to compute than the first derivative?\n",
    "1. Derive the head gradient relationship for the chain rule. If you get stuck, use the [\"Chain rule\" article on Wikipedia](https://en.wikipedia.org/wiki/Chain_rule).\n",
    "1. Assume $f(x) = \\sin(x)$. Plot $f(x)$ and $\\frac{df(x)}{dx}$ on a graph, where you computed the latter without any symbolic calculations, i.e. without exploiting that $f'(x) = \\cos(x)$.\n",
    "\n"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}