Symbolic forward and reverse differentiation
AssigneeMicrosoft Corporation
InventorBrian Kevin Guenter
Life of this patent
Estimating the term…
Abstract
The symbolic differentiation technique described herein uses operator overloading and two simple recursive procedures, both the forward and reverse forms of differentiation, to create purely symbolic derivatives. The symbolic derivative expressions can be translated into a program in an arbitrary source language, such as C# or C++, and this program can then be compiled to generate an efficient executable which eliminates much of the interpretive overhead normally encountered in automatic differentiation.
Claims20
A computer-implemented process for computing the symbolic derivative of an expression to be used in an application, comprising:
- inputting an expression to be differentiated;
- converting the expression to a directed acyclic graph of node objects and edges where each node represents one operation or sub-expression of the expression;
- converting the directed acyclic graph to a derivative graph where each edge of the derivative graph corresponds to a partial derivative of the parent node which is a sub-expression of the original expression;
- for each child for each parent node, computing the partial derivative of the sub-expression;
- computing the total derivative of the input expression by summing the partial derivatives of each child edge;
- and
- using the computed total derivative of the expression is in an application that requires computation of the derivative for the expression.
A computer-implemented process for computing the derivative of an expression to be used in an application, comprising:
- inputting an expression to be differentiated;
- converting the expression to a directed acyclic graph of node objects and edges where each node represents one operation or sub-expression of the expression;
- converting the directed acyclic graph to a derivative graph where each edge of the derivative graph corresponds to a partial derivative of the parent node (406);
- for each sub-expression, making a check to see if the derivative of the sub-expression is in a hash table;
- if the derivative of the sub-expression is not in the hash table, computing the derivative of the sub-expression and putting the derivative of the sub-expression into the hash table;
- if the derivative of the sub-expression is in the hash table, using the value in the hash table as the value for the sub-expression;
- computing the total derivative of the input expression by summing the derivatives of each child edge;
- and
- using the computed total derivative of the expression is in an application that requires computation of the derivative for the expression.
A system for computing the derivative of an expression, comprising:
- a general purpose computing device;
- a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,
- input an expression for which a derivative is sought;
- convert the expression to a directed acyclic graph where the nodes of the graph represent sub-expressions of the expression;
- convert the directed acyclic graph into a derivative graph;
- compute a set of partial derivatives for each of the sub-expressions of the derivative graph;
- sum the set of partial derivatives for the sub-expressions to obtain a total derivative of the original input expression;
- and
- employ the total derivative of the original input expression in an application that requires computation of the derivative of the expression.
Dependencies are inferred from the claim text.