Backpropagation and Automatic Differentiation, machine learning lesson

A forward pass turns parameters into a loss, but gradient descent needs more, namely the rate at which the loss changes with every single parameter. Nudging each parameter in turn and recomputing the loss would cost two forward passes per parameter, which is hopeless for a network with millions of them. Backpropagation obtains all of these derivatives from one forward pass and one backward pass. This lesson draws a tiny network as a computational graph, applies the multivariable chain rule along its paths, shows how reverse-mode automatic differentiation does the bookkeeping in code, and tests the result with finite differences. All numbers are constructed and dimensionless.

Key terms

Computational graph

Definition The computational graph of a calculation is a directed acyclic graph with one node for each input, parameter and intermediate result, and an edge from each argument of an operation to the node that holds its result. Every node that is not an input applies an elementary operation, such as addition, multiplication, ReLU or squaring, whose partial derivatives with respect to its arguments are known formulas. These are the local derivatives of the graph. Evaluating the nodes in a topological order, in which every node comes after all of its arguments, is the forward pass. When a training loss is differentiated with respect to the parameters, the data nodes, such as the input and the target, are held fixed.

In plain words The graph is the calculation drawn as a diagram of small steps. Each edge carries a simple local rate of change, and every derivative of the loss will be assembled from these rates and the values stored during the forward pass.

Example A tiny network has one input $x$ , one hidden ReLU unit, one output and a half squared error loss,

\begin{gathered} z = wx + b, \quad h = \operatorname{ReLU}(z), \\[0.4em] s = vh + c, \quad L = \tfrac12 (s - y)^2 , \end{gathered}

with parameters $w$ , $b$ , $v$ and $c$ . Take $x = 2$ , $y = 1$ , $w = 0.5$ , $b = 0$ , $v = 3$ and $c = -1$ . The forward pass gives $z = 1$ , $h = 1$ , $s = 2$ , the error $e = s - y = 1$ and the loss $L = 0.5$ . At these values the local derivatives are $\partial z / \partial w = x = 2$ , $\partial z / \partial b = 1$ , $\partial h / \partial z = 1$ because $z > 0$ , $\partial s / \partial h = v = 3$ , $\partial s / \partial v = h = 1$ , $\partial s / \partial c = 1$ and $\partial L / \partial s = e = 1$ . The factor $\tfrac12$ only makes the last local derivative equal to the error.

Multivariable chain rule

Definition Let $g$ be a function from $\mathbb{R}^n$ to $\mathbb{R}^m$ that is differentiable at $\boldsymbol{\theta}$ , with values $\mathbf{u} = g(\boldsymbol{\theta})$ , and let $F$ be a function from $\mathbb{R}^m$ to $\mathbb{R}$ that is differentiable at $\mathbf{u}$ . Then $L(\boldsymbol{\theta}) = F(g(\boldsymbol{\theta}))$ is differentiable at $\boldsymbol{\theta}$ , and for each $j$

\frac{\partial L}{\partial \theta_j} = \sum_{k=1}^{m} \frac{\partial F}{\partial u_k}\, \frac{\partial u_k}{\partial \theta_j} ,

or in matrix form $\nabla L(\boldsymbol{\theta}) = J_g(\boldsymbol{\theta})^{\top}\nabla F(\mathbf{u})$ , where $J_g$ is the $m \times n$ Jacobian matrix of $g$ . Applied node by node in a computational graph whose operations are all differentiable at the current values, it gives the path rule. The derivative of the output with respect to any node equals the sum, over all directed paths from that node to the output, of the product of the local derivatives along the path. The hypothesis is differentiability, which is more than the existence of partial derivatives, and an operation evaluated where it has no derivative, such as ReLU at $0$ , breaks it.

In plain words Rates multiply along a chain of dependencies. When a quantity affects the output through several routes, the contributions of the routes add. Leaving out one route gives a wrong derivative even when every factor on the other routes is right.

Example Let $q = u^2 + u$ at $u = 2$ . The variable $u$ reaches $q$ through the squaring branch, with local derivatives $2u = 4$ and then $1$ , and directly through the addition, with local derivative $1$ . The two paths contribute $4$ and $1$ , so $dq/du = 5$ , in agreement with the derivative $2u + 1$ of the formula. Keeping only the squaring branch would give $4$ . Writing the square as the product $u \cdot u$ gives two edges from $u$ into the multiplication, each with local derivative $u = 2$ , and adding them is the product rule. In the tiny network a single path leads from $w$ to $L$ , through $z$ , $h$ and $s$ , so

\begin{aligned} \frac{\partial L}{\partial w} &= \frac{\partial L}{\partial s}\,\frac{\partial s}{\partial h}\,\frac{\partial h}{\partial z}\,\frac{\partial z}{\partial w} \\[0.4em] &= 1 \cdot 3 \cdot 1 \cdot 2 = 6 . \end{aligned}

Backpropagation

Definition Backpropagation computes the gradient of a scalar loss with respect to all parameters of a network by one forward pass followed by one backward pass. The forward pass stores every intermediate value. The backward pass visits the nodes in reverse topological order and computes, for each node $u$ , its adjoint $\bar{u} = \partial L / \partial u$ , the derivative of the final loss with respect to that node’s value. It starts from $\bar{L} = 1$ , and the adjoint of each node is the sum, over the nodes that use it directly, of their adjoint times the local derivative. For a fully connected layer with $\mathbf{z}^{(l)} = W^{(l)}\mathbf{h}^{(l-1)} + \mathbf{b}^{(l)}$ and $\mathbf{h}^{(l)} = \phi(\mathbf{z}^{(l)})$ this gives, for one example,

\begin{aligned} \bar{\mathbf{z}}^{(l)} &= \bar{\mathbf{h}}^{(l)} \odot \phi'\bigl(\mathbf{z}^{(l)}\bigr), \\[0.4em] \bar{W}^{(l)} &= \bar{\mathbf{z}}^{(l)}\, \mathbf{h}^{(l-1)\top}, \\[0.4em] \bar{\mathbf{b}}^{(l)} &= \bar{\mathbf{z}}^{(l)}, \\[0.4em] \bar{\mathbf{h}}^{(l-1)} &= W^{(l)\top}\, \bar{\mathbf{z}}^{(l)}, \end{aligned}

where $\odot$ multiplies entry by entry and each adjoint has the shape of its variable. For a loss averaged over a batch, each parameter adjoint is the average of the per-example adjoints. The first formula needs $\phi$ to be differentiable at every entry of $\mathbf{z}^{(l)}$ . Where a ReLU preactivation is exactly $0$ , implementations insert a chosen value, usually $0$ , which is a convention and not a derivative.

In plain words Work backward from the loss. Each node receives the sensitivity of the loss to its own value, multiplies it by its local rates and passes the products on to its arguments. One backward sweep, at a cost comparable to the forward pass, yields the derivative for every parameter at once, and that is what makes gradient training of large networks practical.

Example For the tiny network at the values above, start with $\bar{s} = \partial L / \partial s = e = 1$ . Then $\bar{c} = \bar{s} = 1$ and $\bar{v} = \bar{s}\,h = 1$ , and the hidden value receives $\bar{h} = \bar{s}\,v = 3$ . The unit is active because $z = 1 > 0$ , so $\bar{z} = \bar{h} \cdot 1 = 3$ , and finally $\bar{b} = \bar{z} = 3$ and $\bar{w} = \bar{z}\,x = 6$ . In the order $(w, b, v, c)$ the gradient is $(6, 3, 1, 1)$ . A gradient descent step with learning rate $0.01$ gives $w = 0.44$ , $b = -0.03$ , $v = 2.99$ and $c = -1.01$ . A new forward pass gives $z = 0.85$ , $h = 0.85$ , $s = 1.5315$ and

L = \tfrac12 (0.5315)^2 = 0.141246125 ,

down from $0.5$ . That checks this one step. It does not show that every step size lowers the loss, and the loss of a network is in general not convex in its parameters.

Reverse-mode automatic differentiation

Definition Automatic differentiation computes derivatives of a function given as a program by applying the chain rule to the elementary operations the program executes, at the values it computes. Reverse mode records each operation, its arguments and its result during the forward evaluation, sets the adjoint of the scalar output to $1$ , and then processes the record in reverse order, adding each operation’s contribution to the adjoints of its arguments. At points where every executed operation is differentiable, the results are the exact derivatives of the executed composition, up to floating-point rounding. For a scalar output the whole gradient costs a small constant multiple of one evaluation, whatever the number of inputs, at the price of storing the intermediate values. Forward mode instead carries a derivative along with each value and yields one directional derivative per pass, so a gradient with respect to $n$ parameters takes $n$ passes. Automatic differentiation is neither a finite-difference estimate nor a symbolic simplification of a formula. Backpropagation is reverse mode applied to the loss of a neural network.

In plain words The software watches the forward calculation, keeps a list of what it did, and then walks the list backward applying the local rules. A value used in several places collects its adjoint by addition, one contribution per use, which is the path rule in code. The same addition explains a common bug. Frameworks that keep gradients in buffers attached to the parameters add every new backward pass into those buffers, so the buffers must be cleared before the next independent update, unless accumulation over several batches is intended and the loss is scaled for it.

Example The Python sketch below implements reverse mode for addition, multiplication and ReLU. Each node stores its value and, for each argument, the local derivative at the current values.

class Node:
    def __init__(self, value, parents=()):
        self.value = value      # forward value
        self.parents = parents  # (argument, local derivative)
        self.adjoint = 0.0

def add(a, b):
    return Node(a.value + b.value, ((a, 1.0), (b, 1.0)))

def mul(a, b):
    return Node(a.value * b.value,
                ((a, b.value), (b, a.value)))

def relu(a):
    slope = 1.0 if a.value > 0 else 0.0  # 0 at the kink
    return Node(max(0.0, a.value), ((a, slope),))

def backward(out):
    order, seen = [], set()
    def visit(n):  # arguments before results
        if id(n) not in seen:
            seen.add(id(n))
            for p, _ in n.parents:
                visit(p)
            order.append(n)
    visit(out)
    for n in order:
        n.adjoint = 0.0
    out.adjoint = 1.0
    for n in reversed(order):
        for p, d in n.parents:
            # paths that meet add their contributions
            p.adjoint += d * n.adjoint

u = Node(2.0)
q = add(mul(u, u), u)
backward(q)
print(u.adjoint)  # 5.0

Building the tiny network from the same operations, with the error written as $s + (-1)\,y$ and the loss as $0.5 \cdot e \cdot e$ , gives the adjoints $(6, 3, 1, 1)$ for $(w, b, v, c)$ . If the line with += used = instead, each adjoint would keep only the last contribution it received, and the sketch would report $2$ instead of $5$ for $q$ .

Gradient check

Definition A gradient check compares a computed gradient $\mathbf{g}$ with finite-difference estimates. For parameter $i$ and a step $\varepsilon > 0$ the central difference is

\hat{g}_i = \frac{L_i^{+} - L_i^{-}}{2\varepsilon},

where $L_i^{\pm} = L(\boldsymbol{\theta} \pm \varepsilon \mathbf{e}_i)$ are the losses after moving parameter $i$ alone up or down by $\varepsilon$ , and $\mathbf{e}_i$ is the $i$ th coordinate vector. If $L$ has a continuous third derivative in $\theta_i$ on the interval from $\theta_i - \varepsilon$ to $\theta_i + \varepsilon$ , the difference between $\hat{g}_i$ and the true partial derivative $\partial L / \partial \theta_i$ equals $\tfrac16 \varepsilon^2$ times that third derivative at some point of the interval. The comparison uses a relative difference such as $\lvert g_i - \hat{g}_i \rvert / \max(\lvert g_i \rvert, \lvert \hat{g}_i \rvert)$ when the two are not both $0$ . Each parameter costs two loss evaluations, so the check is a test on small models or a few coordinates, not a way to train. Too large a step picks up curvature, too small a step loses digits to rounding, and near a kink such as ReLU at $0$ the difference need not agree with any derivative convention. A passing check is evidence that the gradient code is right at the tested points, not a proof that it is right everywhere.

In plain words Nudge one parameter up and down, see how much the loss moves, and compare with the gradient the code reports. Agreement on several parameters and points builds confidence. Disagreement usually points to a missing path, a missing factor, a different averaging convention, or a test point at a kink.

Example At the working point of the tiny network with $\varepsilon = 10^{-6}$ , the four central differences agree with $(6, 3, 1, 1)$ with relative differences below $10^{-9}$ . Near this point $z > 0$ , so the loss is a polynomial of degree two in each single parameter, the central difference has no truncation error, and only rounding remains. Now suppose a backward pass forgets the factor $v$ on the edge from $h$ to $s$ and sets $\bar{h} = \bar{s}$ . It reports $\partial L / \partial w = 2$ and $\partial L / \partial b = 1$ , while the check gives $6$ and $3$ , and $\partial L / \partial v$ and $\partial L / \partial c$ still agree. The mismatch is confined to the parameters whose paths pass through the edge from $h$ to $s$ , which locates the error.

Check yourself

In the tiny network keep $x = 2$ , $y = 1$ , $b = 0$ , $v = 3$ and $c = -1$ , but set $w = -1$ . Compute the loss and all four parameter derivatives. Does the zero derivative for $w$ mean that $w$ is at its best value?

Show the answer

The forward pass gives $z = -2$ , $h = \operatorname{ReLU}(-2) = 0$ , $s = 3 \cdot 0 - 1 = -1$ , the error $e = -2$ and the loss $L = \tfrac12 \cdot 4 = 2$ . Backward, $\bar{s} = e = -2$ , so $\bar{c} = -2$ and $\bar{v} = \bar{s}\,h = 0$ . The hidden value receives $\bar{h} = \bar{s}\,v = -6$ , but the unit is inactive because $z < 0$ , so $\bar{z} = 0$ and therefore $\bar{b} = 0$ and $\bar{w} = 0$ . The gradient in the order $(w, b, v, c)$ is $(0, 0, 0, -2)$ .

The zero for $w$ only says that small changes of $w$ keep $z$ negative and leave the loss unchanged. The loss of $2$ is far from its smallest value, and $c$ can still lower it, so a step with learning rate $0.01$ moves $c$ from $-1$ to $-0.98$ and nothing else. A ReLU unit that is inactive on every training example passes no gradient to its incoming weights in this way.

A hand-written backward pass for $r = u^2 + 3u$ at $u = -1$ returns $dr/du = -2$ , while a central difference with $\varepsilon = 0.001$ gives $1$ . Which value is right, which path was left out, and what would gradient descent do with the wrong value?

Show the answer

The variable $u$ reaches $r$ through the squaring branch, which contributes $2u = -2$ , and through the term $3u$ , which contributes $3$ . The derivative is the sum, $-2 + 3 = 1$ , so the backward pass left out the linear path. The central difference agrees, since $r(-0.999) = -1.998999$ and $r(-1.001) = -2.000999$ differ by $0.002$ , and dividing by $2\varepsilon = 0.002$ gives $1$ , exact up to rounding because $r$ is quadratic.

With the wrong value $-2$ , a gradient descent step $u \leftarrow u - \alpha(-2)$ increases $u$ . The true derivative $1$ says that increasing $u$ increases $r$ , so the faulty gradient moves uphill.

In the tiny network set $w = 0$ and keep $x = 2$ , $y = 1$ , $b = 0$ , $v = 3$ and $c = -1$ . Automatic differentiation with the convention that ReLU has slope $0$ at $0$ returns $\partial L / \partial w = 0$ , while a central difference with $\varepsilon = 10^{-4}$ gives about $-5.9991$ . Is the gradient code broken?

Show the answer

No. Here $z = 0$ , exactly at the kink, and the loss has no derivative in $w$ at this point. For small $w < 0$ the unit is inactive, $s = -1$ and $L = 2$ , so the slope from the left is $0$ . For $w > 0$ the loss is $\tfrac12 (6w - 2)^2$ , whose slope at $w = 0$ from the right is $-12$ . The central difference is

\frac{L(\varepsilon) - L(-\varepsilon)}{2\varepsilon} = 9\varepsilon - 6 ,

which is $-5.9991$ for $\varepsilon = 10^{-4}$ and tends to $-6$ , the average of the two one-sided slopes. The value $0$ from automatic differentiation is the chosen convention, which here equals the slope from the left. Neither number is a derivative, so the mismatch says nothing about the code. Gradient checks belong at points away from kinks. With this convention a gradient step also leaves $w$ at $0$ , even though increasing $w$ would lower the loss.

Backpropagation and Automatic Differentiation

Key terms

Computational graph

Multivariable chain rule

Backpropagation

Reverse-mode automatic differentiation

Gradient check

Check yourself

How this lesson connects

Builds on

Used later in