Automatic Differentiation Revisited
Previous: Why does trig-sub even exist?
Next: Scala Try is Broken
Branium and the Santa Monica Haskell Users Group were kind enough to give me a chance to present about automatic differentiation for an evening, a topic we’ve visited before. This gave me a chance to improve my existing implementation and even add symbolic differentiation capabilities.
You can find the source code on GitHub, but I’ll inline the interesting bits.
Dual
is now a type constructor, rather than a concrete type.
This lets us accomplish a neat trick, which I will point out below.
Implementation of (**)
is split into three cases in order to fix the bug mentioned in my earlier post.
The three cases correspond to the power rule (variable raised to a constant), the exponential function rule (constant raised to a variable), and a third unnamed rule for finding the derivative of a variable raised to a variable.
We can derive this rule using logarithmic differentiation:
We also found it necessary to add an Ord (Dual a)
instance (when Ord a
exists, of course) for some bookkeeping later on (I forget exactly where).
Now for the neat trick.
Normally, if we have a function \(f\) in hand, then you can think of differentiation as two different processes.
In the first process, you can choose a specific input \(c\) and ask for \(f’(c)\), presumably some kind of concrete type.
We carry out this process when we ask Haskell to evaluate f $ Dual 5 1
, for example.
A more general process would be to pretend we chose a specific number (using, say, \(x\) as a placeholder) and use the formalism to arrive at a formula for \(f’\) (in terms of \(x\)).
In Haskell, we pretend that we chose a number like this: \x -> f $ Dual x 1
.
This lambda is the derivative \(f’\) of the original function \(f\).
Let’s write down this lambda expression so that we don’t forget it.
So now, if f
is a Haskell function with type Num a -> Num c
(res. Fractional
/Floating
), then d f
is the derivative of f
, also of type Num a -> Num c
(res. Fractional
/Floating
).
And now we see why Dual
was made a type constructor this time around: f
and d f
would both be stuck being boring Double -> Double
s if Dual
were simply defined as data Dual = Dual Double Double
.
There are some illustrative examples in the repo that you might want to check out, but those aside, it’s time for symbolic differentiation.
For symbolic differentiation, I literally copied portions of code from Benjamin Kovach’s “Abstract Nonsense” blog post, Symbolic Calculus in Haskell.
Kovach defines a type Expr a
for algebraic expressions that accept and produce values of type a
(“accept” and “produce” in paper-pencil-land, not in Haskell).
(In practice, you’d want more than just :+:
and :*:
, but we’re only going to implement Num (Expr a)
today.)
Where Kovach implements a function derivative :: (Num a) => Expr a -> Expr a
which returns an Expr a
for the derivative of the passed Expr a
, we take a different approach: we will write a Num (Expr a)
instance, which will allow us to leverage our existing automatic differentiation machinery.
Automatic differentiation doesn’t do anything to Expr a
s.
It requires a Haskell function–something like Num a => a -> a
.
So, the last ingredient we need is a way to think of an Expr a
as a Haskell function.
We get this by writing a function that evaluates an Expr a
at a given a
.
Kovach implements a nice one.
I’m going to just take one on credit for now:
And that’s it, we now have symbolic differentiation!
For example, consider the following Expr a
s.
Find their derivatives by:
Or, for lack of an implementation of applyExpr
, inline the lambdas:
You’ll find that you get the expected results.
Previous: Why does trig-sub even exist?
Next: Scala Try is Broken