EFFICIENT SYMBOLIC DIFFERENTIATION USING DERIVATIVE GRAPH FACTORIZATION

• US 20080189345A1
• Filed: 02/07/2007
• Published: 08/07/2008
• Est. Priority Date: 02/07/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Guenter, Brian K.
• Granted Patent: US 8,149,240 B2
• Time in Patent Office: Days
• US Class Current: 708/443
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

An efficient symbolic differentiation method and system that automatically computes one or more derivatives of a function using a computing device. A derivative graph is used to graphically represent the derivative of a function. Repeated factorization of the derivative graph yields a factored derivative graph. The derivative is computed by summing the products along all product paths in the factored derivative graph. The efficient symbolic differentiation method and system operates on both single input/single output and multiple input/multiple output functions. For a single input/single output function, the order of the factoring does not matter. However, for a multiple input/multiple output function, the factoring order is such that the factor subgraph appearing most frequently in the derivative graph is factored first. The method and system also use a product pairs priority queue to avoid the re-computing of sub-strings that are common between product paths.

Claims

1. A method for performing symbolic differentiation of a function using a computing device, comprising:

representing the function as an expression graph;

constructing a derivative graph from the expression graph to graphically represent a derivative of the function;

factoring out factor subgraphs from the derivative graph to generate a factored derivative graph; and

computing the derivative as a sum of products along all product paths in the factored derivative graph.

2. The method of claim 1, further comprising:

determining that at least one node on the derivative graph satisfies the postdominator test or the dominator test; and

factoring the derivative graph until no additional factoring can be performed.

3. The method of claim 1, wherein factoring further comprises replacing a factor subgraph with an edge subgraph containing a single edge.

4. The method of claim 3, further comprising replacing each of the factor subgraphs with corresponding edge subgraphs until the factored derivative graph collapses into a single edge.

5. The method of claim 1, wherein the function is a multiple input and multiple output function having n inputs and m outputs, and further comprising:

generating nm derivative graphs by taking derivates with respect to each of a plurality of range elements; and

finding factor subgraphs where each of the derivative graphs intersect.

6. The method of claim 5, further comprising:

counting a frequency in which the factor subgraphs appear in the derivative graphs;

ranking each of the factor subgraphs using a priority queue in an order based on the frequency such that a factor subgraph having a highest frequency has a highest ranking; and

factoring first a factor subgraph having a highest ranking in the priority queue.

7. The method of claim 6, further comprising updating the ranking of each factor subgraph such that the ranking is changes each time a factor subgraph in the derivative graph due to factorization.

8. The method of claim 1, further comprising:

generating intermediate results for each product path in the factored derivative graph;

determining sub-products that are common between intermediate results;

determining a number of product paths that pass through each of the sub-products; and

forming an optimal sub-product having a highest number of product paths that pass through each of the sub-products.

9. The method of claim 8, further comprising:

computing a path counts of pairs of edges that occur in sequence along a product path; and

determining a highest path count;

merging the highest pair count into an edge pair; and

inserting the edge pair into product paths of derivative graph containing the edge pair.

10. A computer-readable medium having computer-executable instructions running on a computing device for computing a derivative of a function having a single input and a single output, comprising:

constructing a derivative graph that graphically represents the derivative of the function, the derivative graph having nodes and edges that connect the nodes such that each edge represent a term;

determining that at least one node of the derivative graph satisfies the postdominator test or the dominator test;

generating a factored derivative graph by factoring the derivative graph until no additional factoring can occur; and

computing the derivative as the sum of products along all possible product paths in the factored derivative graph.

11. The computer-readable medium of claim 10, further comprising defining a product path as a path along the factored derivative graph from the single input to the single output or vice versa.

12. The computer-readable medium of claim 10, further comprising identifying a potential factorization of the derivative graph when two or more products paths pass through a same node en route to a root or a leaf of the derivative graph.

13. The computer-readable medium of claim 10, wherein the postdominator test further comprises:

identifying a first node and a second node on the derivative graph;

recognizing that the first node is on every product path from the second node to a leaf on the derivative graph; and

concluding that the first node satisfies the postdominator test.

14. A computer-implemented process for computing a derivative of a function having multiple inputs and multiple outputs, comprising:

expressing the function as an expression graph;

generating a derivative graph from the expression graph, wherein the derivative graph contains a plurality of nodes and edges that connect the nodes to each other, wherein each of the edges has an associated mathematical term;

determining that at least one node of the derivative graph satisfies the postdominator test or the dominator test;

factoring out factor subgraphs from the derivative graph such that a factor subgraph appearing most frequently in the derivative graph is factored first to generate a factored derivative graph; and

computing the derivative by summing the each product of all product paths along the factored derivative graph.

15. The computer-implemented process of claim 14, further comprising:

keeping a count of the number of times each of the factor subgraphs appears in the derivative graph; and

decrementing the count for a certain factor subgraph whenever during factorization the factor subgraph disappears.

16. The computer-implemented process of claim 15, further comprising updating the count by observing whether a node of a deleted edge is either a factor or a factor base node.

17. The computer-implemented process of claim 14, further comprising:

computing a number of product paths that pass through each of a plurality of sub-products; and

forming a sub-product having a highest path count.

18. The computer-implemented process of claim 17, further comprising computing path counts of pairs of edges that occur in sequence along the product paths.

19. The computer-implemented process of claim 18, further comprising merging a highest pair count into an edge pair.

20. The computer-implemented process of claim 19, further comprising:

inserting the edge pair into all paths of all derivative graphs that contain the edge pair; and

continuing the above process until all path in all derivative graphs are one edge long.