AUTOMATIC DERIVATIVE METHOD FOR A COMPUTER PROGRAMMING LANGUAGE

• US 20090077543A1
• Filed: 10/19/2007
• Published: 03/19/2009
• Est. Priority Date: 10/19/2006
• Status: Active Grant

• Current Assignee: National University of Ireland, Maynooth, Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Pearlmutter, Barak Avrum, Siskind, Jeffrey Mark
• Granted Patent: US 8,739,137 B2
• Time in Patent Office: Days
• US Class Current: 717/136
• 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
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

The disclosed system provides a transformation-based implementation of forward-mode and reverse-mode automatic differentiation as a built-in, first-class function in a functional programming language. Each of these constructs imposes only a small constant factor of the computational burden (time) of the function itself, and the forward construct has the same properties in terms of space. The functions can be applied to any function, including those involving derivatives and nested closures.

Claims

1. A computing system, comprising a processor;

and a first memory in communication with the processor, the first memory storing programming instructions executable by the processor to;

accept a function expressed as a program in a formal language of a formal system;

automatically process the program to yield an output; and

store the output of the processing in a second memory;

wherein the formal language includes at least one automatic differentiation (AD) construct that

takes as its input a first object expressed in the formal language,

provides as its output a second object expressed in the formal language, where the second object calculates the derivative of the first object, and

wherein the second object is produced by transforming the first object within the formal system.

2. The computing system of claim 1, wherein the formal system includes closures.

3. The computing system of claim 2, wherein the formal system includes the lambda calculus.

4. The computing system of claim 2, wherein the AD construct is implemented by run-time reflection.

5. The computing system of claim 4, in which the reflection performs a recursive traversal of program data structures in order to transform all accessible nested code and data.

7. The computing system of claim 4, wherein the reflection is accomplished by providing a program language construct

that takes a function and an input closure as input arguments, where the input closure has a body and an environment, and

produces an output result closure

having a body that is the same as the body of the input closure, and

having an environment that is derived from the environment of the input closure by processing values in the environment of the input closure by the input function.

9. The computing system of claim 4, wherein the run-time reflection is migrated to compile time by the use of abstract interpretation.

11. The computing system of claim 4, wherein the reflection is implemented by run-time compilation.

13. The computing system of claim 3 wherein the formal system includes a forward AD basis comprising:

a forward zero function that retains the shape of its input, converting any real-number component of that input to the real number zero, where the set of valid inputs includes opaque objects;

a primal function that (a) returns the primal portion of a given primal-tangent pair, (b) returns the corresponding primal basis function when given a forward transformed basis function as input, and (c) applies the inverse of the forward transform to its argument when given a closure as input;

a tangent function that returns the tangent portion of a given primal-tangent pair;

a bundle function that (a) returns a pair of a given primal and tangent;

(b) returns the corresponding forward transformed basis function when given a primal basis function as input, and (c) applies the forward transform to its argument when given a closure as input; and

a j* function that bundles its argument with the result of forward zero applied to that argument.

14. The computing system of claim 3 wherein the formal system includes a reverse AD basis comprising:

a reverse zero function that retains the shape of its input, converting any real-number component of that input to the real number zero;

a plus function that takes two input arguments of the same shape and produces an output result of the same shape as the input arguments where real number components of the output are derived by summing the corresponding real number components of the input arguments, where the set of valid inputs includes opaque objects;

a *j function that (a) returns the corresponding reverse transformed basis function when given a primal basis function as input and (b) applies the reverse transform to its argument when given a closure as input; and

a *j-inverse function that (a) returns the corresponding primal basis function when given a reverse transformed basis function as input and (b) applies the inverse of the reverse transform to its argument when given a closure as input.

15. The computing system of claim 1, wherein the first memory and the second memory are the same physical device.

17. The computing system of claim 1, wherein at least one of the one or more AD constructs comprises a reverse-mode transformation that, when given a first “

primal”

function value as input, returns a function value that, when invoked, returns both

the value returned when said primal function is invoked, and

a “

backpropagator”

function value, closed over intermediate values calculated during invocation of the primal function,

wherein the backpropagator function value, when invoked with a sensitivity of the output of the primal function, returns both a sensitivity of the input to the primal function and a representation of the sensitivities of any involved relevant free variables over which the primal function was closed; and

wherein the backpropagator function value is constructed by augmenting the primal function by associating a partial backpropagator with each value computed during the primal computation, and these partial backpropagators are combined to form the final backpropagator.

18. The computing system of claim 1, wherein the AD construct is generalized to operate on any program that is valid under the formal language.

19. The computing system of claim 18, wherein the formal language includes at least one of

a function that accepts as an argument at least one of

an arbitrary aggregate data structure and

a higher-order function, and

a function that returns at least one of

an aggregate data structure and

a higher-order function.

21. The computing system of claim 1, wherein abstract interpretation is used to eliminate at least one of

non-numeric computations associated with performing numeric computation in the formal language, where the formal language incorporates aggregate data structures,

non-numeric computations associated with performing numeric computation in a higher-order functional or dynamic language, and

non-numeric computations associated with AD.

24. The computing system of claim 1, wherein the AD construct is optimized by applying general-purpose optimizing compiler techniques.

25. The computing system of claim 1, wherein the formal system uses the monad construct to include mutable variables and update-in-place components of aggregate data objects.

6. (canceled)

8. (canceled)

10. (canceled)

12. (canceled)

16. (canceled)

20. A computing system, comprising a processor and a first memory in communication with the processor, the first memory storing programming instructions executable by the processor to:

accept a function expressed as a program in a formal language of a formal system;

automatically process the program to yield an output; and

store the output of the processing in a second memory;

wherein the formal language includes at least one forward-mode automatic differentiation (AD) construct that operates in the presence of multivariate derivatives and to maintain a stream of higher-order derivatives, the stream being at least one of;

lazy and

truncated at some finite order greater than one.

22. (canceled)

23. (canceled)

26. A computing system, comprising a processor;

and a first memory in communication with the processor, the first memory storing programming instructions executable by the processor to;

accept a function expressed as a program in a formal language of a formal system;

automatically process the program, where the processing is selected from the group consisting of

interpreting the program to produce the program'"'"'s output, and

compiling the program to produce as output an executable form of the program; and

store the output in a second memory;

wherein the formal language includes an intrinsic operation by which an additional operation is defined with its forward- and backward-mode AD transforms; and

wherein the automatic processing correctly applies the new operation in programs wherein AD constructs are used in a nested fashion, and in programs wherein higher-order derivatives are taken of functions defined using the additional construct.

28. The computing system of claim 26, wherein the additional operation is a numeric fixed point construct.

27. (canceled)

29. A computing system, comprising a processor and a first memory in communication with the processor, the first memory storing programming instructions executable by the processor to:

accept a function expressed as a program;

automatically process the program to produce an output; and

store the output in a second memory;

wherein the automatic processing interprets an automatic differentiation (AD) construct that

takes a first function as its input,

provides a second function as its output, where the second function calculates the derivative of the first function, and

wherein the first function includes a nested AD operation such that at least one of the following hold;

the first function provides cascaded use of the AD construct, with or without intermediate operations on the resulting value;

or

the code for the first function invokes the AD construct.

32. The computing system of claim 29, wherein the formal system includes a forward AD basis comprising:

a forward zero function that retains the shape of its input, converting any real-number component of that input to the real number zero, where the set of valid inputs contains opaque objects;

a primal function that (a) returns the primal portion of a given primal-tangent pair, (b) returns the corresponding primal basis function when given a forward transformed basis function as input, and (c) applies the inverse of the forward transform to its argument when given a closure as input;

a tangent function that returns the tangent portion of a given primal-tangent pair;

a bundle function that (a) returns a pair of a given primal and tangent;

(b) returns the corresponding forward transformed basis function when given a primal basis function as input, and (c) applies the forward transform to its argument when given a closure as input; and

a j* function that bundles its argument with the result of forward zero applied to that argument.

33. The computing system of claim 29, wherein the formal system includes a reverse AD basis comprising:

a reverse zero function that retains the shape of its input, converting any real-number component of that input to the real number zero;

a plus function that takes two input argument of the same shape and produces and output result of the same shape as the input where real number components of the output are derived by summing the corresponding real number components of the input, where said input may contain opaque objects;

a *j function that (a) returns the corresponding reverse transformed basis function when given a primal basis function as input and (b) applies the reverse transform to its argument when given a closure as input; and

a *j-inverse function that (a) returns the corresponding primal basis function when given a reverse transformed basis function as input and (b) applies the inverse of the reverse transform to its argument when given a closure as input.

36. The computing system of claim 29, wherein at least one of-the AD operators is optimized by applying general-purpose optimizing compiler techniques.

37. The computing system of claim 29, wherein the formal system uses the monad construct to include mutable variables and update-in-place components of aggregate data objects.

30. (canceled)

31. (canceled)

34. (canceled)

35. (canceled)