Automatic differentiation
Automatic differentiation computes exact derivatives of a program by applying the chain rule to each elementary operation. It is neither numerical finite differences nor symbolic algebra.
Throughout this note, take f(x, y) = x * y + sin(x) at x = 2 and y = 3. By hand, df/dx = y + cos(x) ≈ 2.5839 and df/dy = x = 2.
Forward mode
Forward mode carries a derivative alongside each value, in the same order the program runs. A small dual number class is enough to show it:
import math
class Dual:
def __init__(self, v, d=0.0):
self.v, self.d = v, d
def __add__(self, o):
return Dual(self.v + o.v, self.d + o.d)
def __mul__(self, o):
return Dual(self.v * o.v, self.v * o.d + self.d * o.v)
def sin(x):
return Dual(math.sin(x.v), math.cos(x.v) * x.d)
x = Dual(2.0, 1.0) # seed: differentiate with respect to x
y = Dual(3.0, 0.0)
out = x * y + sin(x)
print(out.v, out.d) # 6.9093 2.5839
Each pass gives the derivative with respect to one seeded input, so a function with n inputs needs n passes.
Reverse mode
Reverse mode runs the program once to record intermediate values, then walks backwards, propagating how much the output depends on each one. Call that sensitivity the adjoint.
| Forward pass | Value |
|---|---|
v1 = x * y | 6 |
v2 = sin(x) | 0.9093 |
v3 = v1 + v2 | 6.9093 |
Start with the adjoint of v3 equal to 1. Because v3 is a sum, the adjoints of v1 and v2 are both 1. Then v1 sends y to x and x to y, and v2 sends cos(x) to x. Adding the contributions gives 3 + cos(2) ≈ 2.5839 for x and 2 for y, which matches the hand calculation. One backward pass produced both derivatives.
Which to use
| Mode | Cost scales with | Good fit |
|---|---|---|
| Forward | Number of inputs | Few inputs, many outputs |
| Reverse | Number of outputs | Many inputs, one output |
Training a neural network has millions of inputs and a single scalar loss, which is why it relies on reverse mode, known there as backpropagation. The price is memory, because every intermediate value must be kept until the backward pass reaches it.