In mathematics and computer algebra, automatic differentiation (auto-differentiation, autodiff, or AD), also called algorithmic differentiation, computational differentiation, and differentiation arithmetic is a set of techniques to evaluate the partial derivative of a function specified by a computer program. Automatic differentiation enables the simultaneous computation of the numerical values of arbitrarily complex functions and their derivatives using only the function itself; no symbolic derivative is required. Auto-differentiation is thus neither numeric nor symbolic, nor is it a combination of both. In contrast to the more traditional numerical methods based on finite differences, auto-differentiation is 'in theory' exact, and in comparison to symbolic algorithms, it is computationally inexpensive. Automatic differentiation exploits the fact that every computer calculation, no matter how complicated, executes a sequence of elementary arithmetic operations (addition, subtraction, multiplication, division, etc.) and elementary functions (exp, log, sin, cos, etc.). By applying the chain rule repeatedly to these operations, partial derivatives of arbitrary order can be computed automatically, accurately to working precision, and using at most a small constant factor of more arithmetic operations than the original program.
Difference from other differentiation methods
Automatic differentiation is distinct from symbolic differentiation and numerical differentiation. Symbolic differentiation faces the difficulty of converting a computer program into a single mathematical expression and can lead to inefficient code. Numerical differentiation (the method of finite differences) can introduce round-off errors in the discretization process and cancellation. These classical methods may have problems with calculating higher derivatives, where complexity and errors increase. Finally, both of these classical methods may be slow at computing partial derivatives of a function with respect to many inputs, as is needed for gradient-based optimization algorithms. Automatic differentiation solves all of these problems.
Applications Because of its efficiency and accuracy in computing first and higher order derivatives, auto-differentiation finds diverse applications in scientific computing and mathematics, and there are numerous computational implementations of auto-differentiation. Among these, one mentions INTLAB, Sollya, and InCLosure. In practice, there are two types (modes) of algorithmic differentiation: a forward-type and a reversed-type. Presently, the two types are highly correlated and complementary and both have a wide variety of applications in, e.g., non-linear optimization, sensitivity analysis, robotics, machine learning, computer graphics, and computer vision. Automatic differentiation is particularly important in the field of machine learning. For example, it allows one to implement backpropagation in a neural network without a manually-computed derivative.
Forward and reverse accumulation
Chain rule of partial derivatives of composite functions Fundamental to automatic differentiation is the decomposition of differentials provided by the chain rule of partial derivatives of composite functions. For the simple composition
y = f ( g ( h ( x ) ) ) = f ( g ( h ( w 0 ) ) ) = f ( g ( w 1 ) ) = f ( w 2 ) = w 3 w 0 = x w 1 = h ( w 0 ) w 2 = g ( w 1 ) w 3 = f ( w 2 ) = y {\displaystyle {\begin{aligned}y&=f(g(h(x)))=f(g(h(w_{0})))=f(g(w_{1}))=f(w_{2})=w_{3}\\w_{0}&=x\\w_{1}&=h(w_{0})\\w_{2}&=g(w_{1})\\w_{3}&=f(w_{2})=y\end{aligned}}}
the chain rule gives
∂ y ∂ x = ∂ y ∂ w 2 ∂ w 2 ∂ w 1 ∂ w 1 ∂ x = ∂ f ( w 2 ) ∂ w 2 ∂ g ( w 1 ) ∂ w 1 ∂ h ( w 0 ) ∂ x {\displaystyle {\frac {\partial y}{\partial x}}={\frac {\partial y}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x}}={\frac {\partial f(w_{2})}{\partial w_{2}}}{\frac {\partial g(w_{1})}{\partial w_{1}}}{\frac {\partial h(w_{0})}{\partial x}}}
Two types of automatic differentiation Usually, two distinct modes of automatic differentiation are presented.
forward accumulation (also called bottom-up, forward mode, or tangent mode) reverse accumulation (also called top-down, reverse mode, or adjoint mode) Forward accumulation specifies that one traverses the chain rule from inside to outside (that is, first compute ∂ w 1 ∂ x {\textstyle {\frac {\partial w_{1}}{\partial x}}} and then ∂ w 2 ∂ w 1 {\textstyle {\frac {\partial w_{2}}{\partial w_{1}}}} and lastly ∂ y ∂ w 2 {\textstyle {\frac {\partial y}{\partial w_{2}}}} ), while reverse accumulation traverses from outside to inside (first compute ∂ y ∂ w 2 {\textstyle {\frac {\partial y}{\partial w_{2}}}} and then ∂ w 2 ∂ w 1 {\textstyle {\frac {\partial w_{2}}{\partial w_{1}}}} and lastly ∂ w 1 ∂ x {\textstyle {\frac {\partial w_{1}}{\partial x}}} ). More succinctly,
Forward accumulation computes the recursive relation: ∂ w i ∂ x = ∂ w i ∂ w i − 1 ∂ w i − 1 ∂ x with w 3 = y , {\displaystyle {\frac {\partial w_{i}}{\partial x}}={\frac {\partial w_{i}}{\partial w_{i-1}}}{\frac {\partial w_{i-1}}{\partial x}}\quad {\text{with }}w_{3}=y,}
Reverse accumulation computes the recursive relation: ∂ y ∂ w i = ∂ y ∂ w i + 1 ∂ w i + 1 ∂ w i with w 0 = x . {\displaystyle {\frac {\partial y}{\partial w_{i}}}={\frac {\partial y}{\partial w_{i+1}}}{\frac {\partial w_{i+1}}{\partial w_{i}}}\quad {\text{with }}w_{0}=x.}
The value of the partial derivative, called the seed, is propagated forward or backward and is initially ∂ x ∂ x = 1 {\textstyle {\frac {\partial x}{\partial x}}=1} or ∂ y ∂ y = 1 {\textstyle {\frac {\partial y}{\partial y}}=1} . Forward accumulation evaluates the function and calculates the derivative with respect to one independent variable in one pass. For each independent variable x 1 , x 2 , … , x n {\textstyle x_{1},x_{2},\dots ,x_{n}} a separate pass is therefore necessary in which the derivative with respect to that independent variable is set to one ( ∂ x 1 ∂ x 1 = 1 {\textstyle {\frac {\partial x_{1}}{\partial x_{1}}}=1} ) and of all others to zero ( ∂ x 2 ∂ x 1 = ⋯ = ∂ x n ∂ x 1 = 0 {\textstyle {\frac {\partial x_{2}}{\partial x_{1}}}=\dots ={\frac {\partial x_{n}}{\partial x_{1}}}=0} ). In contrast, reverse accumulation requires the evaluated partial functions for the partial derivatives. Reverse accumulation therefore evaluates the function first and calculates the derivatives with respect to all independent variables in an additional pass. Which of these two types should be used depends on the sweep count. The computational complexity of one sweep is proportional to the complexity of the original code.
Forward accumulation is more efficient than reverse accumulation for functions f : R n → R m {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}} with n ≪ m {\displaystyle n\ll m} as only n {\displaystyle n} sweeps are necessary, compared to m {\displaystyle m} sweeps for reverse accumulation. Reverse accumulation is more efficient than forward accumulation for functions f : R n → R m {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}} with n ≫ m {\displaystyle n\gg m} as only m {\displaystyle m} sweeps are necessary, compared to n {\displaystyle n} sweeps for forward accumulation. Backpropagation of errors in multilayer perceptrons, a technique used in machine learning, is a special case of reverse accumulation. Forward accumulation was introduced by R. E. Wengert in 1964. According to Andreas Griewank, reverse accumulation has been suggested since the late 1960s, but the inventor is unknown. Seppo Linnainmaa published reverse accumulation in 1976.
Forward accumulation
In forward accumulation AD, one first fixes the independent variable with respect to which differentiation is performed and computes the derivative of each sub-expression recursively. In a pen-and-paper calculation, this involves repeatedly substituting the derivative of the inner functions in the chain rule:
∂ y ∂ x = ∂ y ∂ w n − 1 ∂ w n − 1 ∂ x = ∂ y ∂ w n − 1 ( ∂ w n − 1 ∂ w n − 2 ∂ w n − 2 ∂ x ) = ∂ y ∂ w n − 1 ( ∂ w n − 1 ∂ w n − 2 ( ∂ w n − 2 ∂ w n − 3 ∂ w n − 3 ∂ x ) ) = ⋯ {\displaystyle {\begin{aligned}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{n-1}}}{\frac {\partial w_{n-1}}{\partial x}}\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}{\frac {\partial w_{n-2}}{\partial x}}\right)\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}\left({\frac {\partial w_{n-2}}{\partial w_{n-3}}}{\frac {\partial w_{n-3}}{\partial x}}\right)\right)\\[6pt]&=\cdots \end{aligned}}}
This can be generalized to multiple variables as a matrix product of Jacobians. Compared to reverse accumulation, forward accumulation is natural and easy to implement as the flow of derivative information coincides with the order of evaluation. Each variable w i {\displaystyle w_{i}} is augmented with its derivative w ˙ i {\displaystyle {\dot {w}}_{i}} (stored as a numerical value, not a symbolic expression),
w ˙ i = ∂ w i ∂ x {\displaystyle {\dot {w}}_{i}={\frac {\partial w_{i}}{\partial x}}}
as denoted by the dot. The derivatives are then computed in sync with the evaluation steps and combined with other derivatives via the chain rule. Using the chain rule, if w i {\displaystyle w_{i}} has predecessors in the computational graph:
w ˙ i = ∑ j ∈ { predecessors of i } ∂ w i ∂ w j w ˙ j {\displaystyle {\dot {w}}_{i}=\sum _{j\in \{{\text{predecessors of }}i\}}{\frac {\partial w_{i}}{\partial w_{j}}}{\dot {w}}_{j}}
As an example, consider the function:
y = f ( x 1 , x 2 ) = x 1 x 2 + sin x 1 = w 1 w 2 + sin w 1 = w 3 + w 4 = w 5 {\displaystyle {\begin{aligned}y&=f(x_{1},x_{2})\\&=x_{1}x_{2}+\sin x_{1}\\&=w_{1}w_{2}+\sin w_{1}\\&=w_{3}+w_{4}\\&=w_{5}\end{aligned}}}
For clarity, the individual sub-expressions have been labeled with the variables w i {\displaystyle w_{i}} . The choice of the independent variable to which differentiation is performed affects the seed values ẇ1 and ẇ2. Given interest in the derivative of this function with respect to x1, the seed values should be set to:
w ˙ 1 = ∂ w 1 ∂ x 1 = ∂ x 1 ∂ x 1 = 1 w ˙ 2 = ∂ w 2 ∂ x 1 = ∂ x 2 ∂ x 1 = 0 {\displaystyle {\begin{aligned}{\dot {w}}_{1}={\frac {\partial w_{1}}{\partial x_{1}}}={\frac {\partial x_{1}}{\partial x_{1}}}=1\\{\dot {w}}_{2}={\frac {\partial w_{2}}{\partial x_{1}}}={\frac {\partial x_{2}}{\partial x_{1}}}=0\end{aligned}}}
With the seed values set, the values propagate using the chain rule as shown. Figure 2 shows a pictorial depiction of this process as a computational graph.
To compute the gradient of this example function, which requires not only ∂ y ∂ x 1 {\textstyle {\frac {\partial y}{\partial x_{1}}}} but also ∂ y ∂ x 2 {\textstyle {\frac {\partial y}{\partial x_{2}}}} , an additional sweep is performed over the computational graph using the seed values w ˙ 1 = 0 {\textstyle {\dot {w}}_{1}=0} ; w ˙ 2 = 1 {\textstyle {\dot {w}}_{2}=1} .
Implementation
Pseudocode Forward accumulation calculates the function and the derivative (but only for one independent variable each) in one pass. The associated method call expects the expression Z to be derived with regard to a variable V. The method returns a pair of the evaluated function and its derivative. The method traverses the expression tree recursively until a variable is reached. If the derivative with respect to this variable is requested, its derivative is 1, 0 otherwise. Then the partial function as well as the partial derivative are evaluated.
C++
Reverse accumulation
In reverse accumulation AD, the dependent variable to be differentiated is fixed and the derivative is computed with respect to each sub-expression recursively. In a pen-and-paper calculation, the derivative of the outer functions is repeatedly substituted in the chain rule:
∂ y ∂ x = ∂ y ∂ w 1 ∂ w 1 ∂ x = ( ∂ y ∂ w 2 ∂ w 2 ∂ w 1 ) ∂ w 1 ∂ x = ( ( ∂ y ∂ w 3