In mathematics and computer algebra, automatic differentiation (auto-differentiation, autodiff, or AD), also called algorithmic differentiation, computational differentiation, and differentiation arithmeticHend Dawood and Nefertiti Megahed (2023). Automatic differentiation of uncertainties: an interval computational differentiation for first and higher derivatives with implementation. PeerJ Computer Science 9:e1301 https://doi.org/10.7717/peerj-cs.1301.Hend Dawood and Nefertiti Megahed (2019). A Consistent and Categorical Axiomatization of Differentiation Arithmetic Applicable to First and Higher Order Derivatives. Punjab University Journal of Mathematics. 51(11). pp. 77-100. doi: 10.5281/zenodo.3479546. http://doi.org/10.5281/zenodo.3479546. 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.Hend Dawood and Yasser Dawood (2022). Interval Root Finding and Interval Polynomials: Methods and Applications in Science and Engineering. In S. Chakraverty, editor, Polynomial Paradigms: Trends and Applications in Science and Engineering, chapter 15. IOP Publishing. ISBN 978-0-7503-5065-5. doi: 10.1088/978-0-7503-5067-9ch15. URL https://doi.org/10.1088/978-0-7503-5067-9ch15.
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.Siegfried M. Rump (1999). INTLAB–INTerval LABoratory. In T. Csendes, editor, Developments in Reliable Computing, pages 77–104. Kluwer Academic Publishers, Dordrecht.S. Chevillard, M. Joldes, and C. Lauter. Sollya (2010). An Environment for the Development of Numerical Codes. In K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, editors, Mathematical Software - ICMS 2010, volume 6327 of Lecture Notes in Computer Science, pages 28–31, Heidelberg, Germany. Springer.Hend Dawood (2022). InCLosure (Interval enCLosure)–A Language and Environment for Reliable Scientific Computing. Computer Software, Version 4.0. Department of Mathematics. Faculty of Science, Cairo University, Giza, Egypt, September 2022. url: https://doi.org/10.5281/zenodo.2702404. 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.Christian P. Fries (2019). Stochastic Automatic Differentiation: Automatic Differentiation for Monte-Carlo Simulations. Quantitative Finance, 19(6):1043–1059. doi: 10.1080/14697688.2018.1556398. url: https://doi.org/10.1080/14697688.2018.1556398.Hend Dawood and Yasser Dawood (2020). Universal Intervals: Towards a Dependency-Aware Interval Algebra. In S. Chakraverty, editor, Mathematical Methods in Interdisciplinary Sciences. chapter 10, pages 167–214. John Wiley & Sons, Hoboken, New Jersey. ISBN 978-1-119-58550-3. doi: 10.1002/9781119585640.ch10. url: https://doi.org/10.1002/9781119585640.ch10.Hend Dawood (2014). Interval Mathematics as a Potential Weapon against Uncertainty. In S. Chakraverty, editor, Mathematics of Uncertainty Modeling in the Analysis of Engineering and Science Problems. chapter 1, pages 1–38. IGI Global, Hershey, PA. ISBN 978-1-4666-4991-0. 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
the chain rule gives
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 and then and lastly ), while reverse accumulation traverses from outside to inside (first compute and then and lastly ). More succinctly, Forward accumulation computes the recursive relation: Reverse accumulation computes the recursive relation:
The value of the partial derivative, called the seed, is propagated forward or backward and is initially or . Forward accumulation evaluates the function and calculates the derivative with respect to one independent variable in one pass. For each independent variable a separate pass is therefore necessary in which the derivative with respect to that independent variable is set to one () and of all others to zero (). 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 with as only sweeps are necessary, compared to sweeps for reverse accumulation. Reverse accumulation is more efficient than forward accumulation for functions with as only sweeps are necessary, compared to 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:
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 is augmented with its derivative (stored as a numerical value, not a symbolic expression),
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 has predecessors in the computational graph:
As an example, consider the function:
For clarity, the individual sub-expressions have been labeled with the variables .
The choice of the independent variable to which differentiation is performed affects the seed values and . Given interest in the derivative of this function with respect to , the seed values should be set to:
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. {| class="wikitable" !Operations to compute value !!Operations to compute derivative |- | || (seed) |- | || (seed)
To compute the gradient of this example function, which requires not only but also , an additional sweep is performed over the computational graph using the seed values ; .
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 to be derived with regard to a variable . 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. tuple<float,float> evaluateAndDerive(Expression Z, Variable V) { if isVariable(Z) if (Z = V) return {valueOf(Z), 1}; else return {valueOf(Z), 0}; else if (Z = A + B) {a, a'} = evaluateAndDerive(A, V); {b, b'} = evaluateAndDerive(B, V); return {a + b, a' + b'}; else if (Z = A - B) {a, a'} = evaluateAndDerive(A, V); {b, b'} = evaluateAndDerive(B, V); return {a - b, a' - b'}; else if (Z = A * B) {a, a'} = evaluateAndDerive(A, V); {b, b'} = evaluateAndDerive(B, V); return {a * b, b * a' + a * b'}; }
C++ #include <iostream> struct ValueAndPartial { float value, partial; }; struct Variable; struct Expression { virtual ValueAndPartial evaluateAndDerive(Variable &variable) = 0; }; struct Variable: public Expression { float value; Variable(float value): value(value) {} ValueAndPartial evaluateAndDerive(Variable &variable) { float partial = (this == &variable) ? 1.0f : 0.0f; return {value, partial};
struct Plus: public Expression { Expression &a, &b; Plus(Expression &a, Expression &b): a(a), b(b) {} ValueAndPartial evaluateAndDerive(Variable &variable) { auto [valueA, partialA] = a.evaluateAndDerive(variable); auto [valueB, partialB] = b.evaluateAndDerive(variable); return {valueA + valueB, partialA + partialB};
struct Multiply: public Expression { Expression &a, &b; Multiply(Expression &a, Expression &b): a(a), b(b) {} ValueAndPartial evaluateAndDerive(Variable &variable) { auto [valueA, partialA] = a.evaluateAndDerive(variable); auto [valueB, partialB] = b.evaluateAndDerive(variable); return {valueA * valueB, valueB * partialA + valueA * partialB};
int main () {