24th February 2009, 12:05 am
I have another paper draft for submission to ICFP 2009.
This one is called Beautiful differentiation,
The paper is a culmination of the several posts I’ve written on derivatives and automatic differentiation (AD).
I’m happy with how the derivation keeps getting simpler.
Now I’ve boiled extremely general higher-order AD down to a Functor and Applicative morphism.
I’d love to get some readings and feedback.
I’m a bit over the page the limit, so I’ll have to do some trimming before submitting.
The abstract:
Automatic differentiation (AD) is a precise, efficient, and convenient
method for computing derivatives of functions. Its implementation can be
quite simple even when extended to compute all of the higher-order
derivatives as well. The higher-dimensional case has also been tackled,
though with extra complexity. This paper develops an implementation of
higher-dimensional, higher-order differentiation in the extremely
general and elegant setting of calculus on manifolds and derives that
implementation from a simple and precise specification.
In order to motivate and discover the implementation, the paper poses
the question “What does AD mean, independently of implementation?” An
answer arises in the form of naturality of sampling a function and its
derivative. Automatic differentiation flows out of this naturality
condition, together with the chain rule. Graduating from first-order to
higher-order AD corresponds to sampling all derivatives instead of just
one. Next, the notion of a derivative is generalized via the notions of
vector space and linear maps. The specification of AD adapts to this
elegant and very general setting, which even simplifies the
development.
You can get the paper and see current errata here.
The submission deadline is March 2, so comments before then are most helpful to me.
Enjoy, and thanks!
I have another paper draft for submission to ICFP 2009. This one is called Beautiful differentiation, The paper is a culmination of the several posts I’ve written on derivatives and...
20th May 2008, 09:29 pm
The post Beautiful differentiation showed some lovely code that makes it easy to compute not just the values of user-written functions, but also all of its derivatives (infinitely many).
This elegant technique is limited, however, to functions over a scalar (one-dimensional) domain.
Next, we explored what it means to transcend that limitation, asking and answering the question What is a derivative, really?
The answer to that question is that derivative values are linear maps saying how small input changes result in output changes.
This answer allows us to unify several different notions of derivatives and their corresponding chain rules into a single simple and powerful form.
This third post combines the ideas from the two previous posts, to easily compute infinitely many derivatives of functions over arbitrary-dimensional domains.
The code shown here is part of a new Haskell library, which you can download and play with or peruse on the web.
Continue reading ‘Higher-dimensional, higher-order derivatives, functionally’ »
The post Beautiful differentiation showed some lovely code that makes it easy to compute not just the values of user-written functions, but also all of its derivatives (infinitely many). This...
7th May 2008, 02:26 pm
Lately I’ve been playing again with parametric surfaces in Haskell.
Surface rendering requires normals, which can be constructed from partial derivatives, which brings up automatic differentiation (AD).
Playing with some refactoring, I’ve stumbled across a terser, lovelier formulation for the derivative rules than I’ve seen before.
Edits:
- 2008-05-08: Added source files: NumInstances.hs and Dif.hs.
- 2008-05-20: Changed some variable names for clarity and consistency. For instance,
x@(D x0 x') instead of p@(D x x').
- 2008-05-20: Removed extraneous
Fractional constraint in the Floating instance of Dif.
Continue reading ‘Beautiful differentiation’ »
Lately I’ve been playing again with parametric surfaces in Haskell. Surface rendering requires normals, which can be constructed from partial derivatives, which brings up automatic differentiation (AD). Playing with some...