Let's say we have expression $z = x_1x_2 + \sin(x_1)$ and want to find derivatives $\frac{dz}{dx_1}$ and $\frac{dz}{dx_2}$. Reverse-mode AD splits this task into 2 parts, namely, forward and reverse passes.
Forward pass
First, we decompose our complex expression into a set of primitive ones, i.e. expressions consisting of at most single function call. Note that I also rename input and output variables for consistency, though it's not necessary:
$$w_1 = x_1$$
$$w_2 = x_2$$
$$w_3 = w_1w_2$$
$$w_4 = \sin(w_1)$$
$$w_5 = w_3 + w_4$$
$$z = w_5$$
The advantage of this representation is that differentiation rules for each separate expression are already known. For example, we know that derivative of $\sin$ is $\cos$, and so $\frac{dw_4}{dw_1} = \cos(w_1)$. We will use this fact in reverse pass below.
Essentially, forward pass consists of evaluating each of these expressions and saving the results. Say, our inputs are: $x_1 = 2$ and $x_2 = 3$. Then we have:
$$w_1 = x_1 = 2$$
$$w_2 = x_2 = 3$$
$$w_3 = w_1w_2 = 6$$
$$w_4 = \sin(w_1) ~= 0.9$$
$$w_5 = w_3 + w_4 = 6.9$$
$$z = w_5 = 6.9$$
Reverse pass
This is were the magic starts, and it starts with the chain rule. In its basic form, chain rule states that if you have variable $t(u(v))$ which depends on $u$ which, in its turn, depends on $v$, then:
$$\frac{dt}{dv} = \frac{dt}{du}\frac{du}{dv}$$
or, if $t$ depends on $v$ via several paths / variables $u_i$, e.g.:
$$u_1 = f(v)$$
$$u_2 = g(v)$$
$$t = h(u_1, u_2)$$
then (see proof here):
$$\frac{dt}{dv} = \sum_i \frac{dt}{du_i}\frac{du_i}{dv}$$
In terms of expression graph, if we have a final node $z$ and input nodes $w_i$, and path from $z$ to $w_i$ goes through intermediate nodes $w_p$ (i.e. $z = g(w_p)$ where $w_p = f(w_i)$), we can find derivative $\frac{dz}{dw_i}$ as
$$\frac{dz}{dw_i} = \sum_{p \in parents(i)} \frac{dz}{dw_p} \frac{dw_p}{dw_i}$$
In other words, to calculate the derivative of output variable $z$ w.r.t. any intermediate or input variable $w_i$, we only need to know the derivatives of its parents and the formula to calculate derivative of primitive expression $w_p = f(w_i)$.
Reverse pass starts at the end (i.e. $\frac{dz}{dz}$) and propagates backward to all dependencies. Here we have (expression for "seed"):
$$\frac{dz}{dz} = 1$$
That may be read as "change in $z$ results in exactly the same change in $z$", which is quite obvious.
Then we know that $z = w_5$ and so:
$$\frac{dz}{dw_5} = 1$$
$w_5$ linearly depends on $w_3$ and $w_4$, so $\frac{dw_5}{dw_3} = 1$ and $\frac{dw_5}{dw_4} = 1$. Using the chain rule we find:
$$\frac{dz}{dw_3} = \frac{dz}{dw_5} \frac{dw_5}{dw_3} = 1 \times 1 = 1$$
$$\frac{dz}{dw_4} = \frac{dz}{dw_5} \frac{dw_5}{dw_4} = 1 \times 1 = 1$$
From definition $w_3 = w_1w_2$ and rules of partial derivatives, we find that $\frac{dw_3}{dw_2} = w_1$. Thus:
$$\frac{dz}{dw_2} = \frac{dz}{dw_3} \frac{dw_3}{dw_2} = 1 \times w_1 = w_1$$
Which, as we already know from forward pass, is:
$$\frac{dz}{dw_2} = w_1 = 2$$
Finally, $w_1$ contributes to $z$ via $w_3$ and $w_4$. Once again, from the rules of partial derivatives we know that $\frac{dw_3}{dw_1} = w_2$ and $\frac{dw_4}{dw_1} = \cos(w_1)$. Thus:
$$\frac{dz}{dw_1} = \frac{dz}{dw_3} \frac{dw_3}{dw_1} + \frac{dz}{dw_4} \frac{dw_4}{dw_1} = w_2 + \cos(w_1)$$
And again, given known inputs, we can calculate it:
$$\frac{dz}{dw_1} = w_2 + \cos(w_1) = 3 + \cos(2) ~= 2.58$$
Since $w_1$ and $w_2$ are just aliases for $x_1$ and $x_2$, we get our answer:
$$\frac{dz}{dx_1} = 2.58$$
$$\frac{dz}{dx_2} = 2$$
And that's it!
This description concerns only scalar inputs, i.e. numbers, but in fact it can also be applied to multidimensional arrays such as vectors and matrices. Two things that one should keep in mind when differentiating expressions with such objects:
- Derivatives may have much higher dimensionality than inputs or output, e.g. derivative of vector w.r.t. vector is a matrix and derivative of matrix w.r.t. matrix is a 4-dimensional array (sometimes referred to as a tensor). In many cases such derivatives are very sparse.
- Each component in output array is an independent function of 1 or more components of input array(s). E.g. if $y = f(x)$ and both $x$ and $y$ are vectors, $y_i$ never depends on $y_j$, but only on subset of $x_k$. In particular, this means that finding derivative $\frac{dy_i}{dx_j}$ boils down to tracking how $y_i$ depends on $x_j$.
The power of automatic differentiation is that it can deal with complicated structures from programming languages like conditions and loops. However, if all you need is algebraic expressions and you have good enough framework to work with symbolic representations, it's possible to construct fully symbolic expressions. In fact, in this example we could produce expression $\frac{dz}{dw_1} = w_2 + \cos(w_1) = x_2 + \cos(x_1)$ and calculate this derivative for whatever inputs we want.
