Automatic Differentiation in 38 lines of Haskell(gist.github.com) |
Automatic Differentiation in 38 lines of Haskell(gist.github.com) |
{-# LANGUAGE ImportQualifiedPost #-}
module Module_1663406024_9206 where
import Numeric.AD qualified as Ad
import Data.Number.Symbolic qualified as Sym
-- >>> f x = x^2 + 3 * x
-- >>> Ad.diff f 1
-- >>> Ad.diff f (Sym.var "a")
-- 5
-- 3+a+a
-- >>> Ad.diff sin pi
-- >>> Ad.diff sin (Sym.var "a")
-- -1.0
-- cos a
Saw it first here: https://twitter.com/GabriellaG439/status/647601518871359489 and https://www.reddit.com/r/haskell/comments/3r75hq/comment/cwm...
It works because `f` is polymorphic. The type of its `x` argument is not constrained in `f`'s definition, so you can plug in any `x` of any type you want provided that `x`'s type implements the methods used in `f`'s definition. With the `Dual` scheme you get to use as `x` a "dual" of `y` (`f x`, for some `f`) and `y'`, and then you get an `f` applied to that `x` where the actual `f` is parameterized by the actual `x`'s type, and so the methods called by `f` are those that apply to `x`'s type. So instead of the traditional numeric addition and multiplication, you'd get the "dual" addition and multiplication, and then everything "chains" through and you end up with `diff f x` being the `y'` in the dual of `y` and `y'` (you don't care about the `y`, just the `y'` because you want the `diff` -- the differential or derivative).
It's brilliant.
It's a neat design pattern. I bet it'd work in Julia too.
I'm only a beginner in Julia and not and AD expert, but I went through the exercise of porting this to python and found it very enlightening
I'm not sure I understand what this means. What is a symbolic language that excludes languages like Haskell, F#, OCaml, etc.?
I'm neither a math expert nor a haskell expert, but I happen to enjoy both. It's been a while since I've watched a SPJ lecture, and I'd forgotten how much I want him to explain everything.
If I may ...
1. First attempt - https://sriku.org/blog/2019/03/08/automatic-differentiation/
2. Dual numbers and Taylor numbers - http://sriku.org/blog/2019/03/12/automatic-differentiation-d...
3. Higher ranked beings - http://sriku.org/blog/2019/03/13/automatic-differentiation-h...
can't speak to the OPs process though, maybe they shat it out on a whim :)
Although, I'm rarely interested in <such and such> in <n> lines of <language>. The more interesting things are overall conciseness with regards to the problem, the expressiveness, and the clarity that the code produces.
log (D u u') = D (log u) (scale (log u) u')
If you did (f 'x) for instance, you'd end up with things like (* 2 'x) which would blow up, since Lisp would try to compute the answer instead giving you '(* 2 x) back.
https://github.com/naasking/AutoDiffSharp/blob/master/AutoDi...
However, I think the Float' and `diff` etc. is at least a little helpful in understanding it. I got it from SPJ's talk, which I linked to in the file. Also, it makes it easier (e.g. in the case of `diff`) to later add onto the Autodiff, for example by implementing reverse mode, Jacobians, etc.
EDIT: As for the differentiation, it works for ^ since it is just multiplication (https://hackage.haskell.org/package/base-4.17.0.0/docs/src/G...) for which the derivative was defined using the product rule.
[1]: https://hackage.haskell.org/package/base-4.17.0.0/docs/Prelu... [2]: https://hackage.haskell.org/package/base-4.17.0.0/docs/Prelu...
The neat thing with this approach is that ^ works for any numeric type, including user-defined types like Dual in this example. Since the Dual type can handle calculating derivatives for *, it gets derivatives for ^ for free.
[1]: https://hackage.haskell.org/package/base-4.17.0.0/docs/src/G...
`Num`, then, is a Haskell class (Java interface).
The `Num` class will have a bunch of what Java would call "default methods".
Now, the "instance" of `Num` defined here has only a few methods defined, but the other default methods of `Num` will use those. So if `Num` has a `^` defined in terms of ``, and you define an instance of `Num` that defines ``, then you get `^` for free if you don't implement it.
(^) :: (Num a, Integral b) => a -> b -> a
(^^) :: (Fractional a, Integral b) => a -> b -> a
(**) :: Floating a => a -> a -> a
The second one allows any value with multiplication and multiplicative inverses (Fractional) to be raised to an integral power.
The third one allows any value which supports exponents, trig functions, and logarithms to be raised to a power with the same type. `*` is in fact one of the functions one must implement to implement the Floating typeclass.
It's like Lisp, if everything in Lisp were quoted, and eval consisted of pattern matching and applying substitution rules.
As an example, say in Haskell I have foo x y = x + 2/y. Can you write a function that takes any function in, and replaces all + with *? in Mathematica you can: foo[x_,y_] := x + 2/y; foo[x,y] /. l_ + r_ -> l*r.
I'm sure you can do this stuff in other languages if you try hard enough. Some kind of reflection in Haskell or F#. In Lisp, grab and quote the definition of foo and apply macro machinery to it. But that's not the tao of those languages, while it is the essence of Mathematica.
In Haskell you can only do that kind of manipulation at compile time. At run time, the source code is long gone. And even at compile time, expressions are a very different type than code that can be run. Haskell just isn't anything like a symbolic language.
As pointed out way upthread, it provides lots of hooks for programmers to have nice syntax for entry points to symbolic systems - if someone writes one.
The "coordination" is that they both use the "symbol" sin to refer to the idea of sine function.
Earlier in this thread though "symbol" was used in a less formal, handwavy way as "a named handle to some concept in the language". In that sense, indeed, the way that Julia adds multiple methods to a single named function and supports multiple dispatch permits amazing interoperability (and has little to do with Julia/Lisp/Ruby symbol datastructures).
instance VectorSpace d => Floating (Dual d) where
pi = D pi zero
exp (D u u') = D (exp u) (scale (exp u) u')
log (D u u') = D (log u) (scale (log u) u')
--->sin (D u u') = D (sin u) (scale (cos u) u')
cos (D u u') = D (cos u) (scale (-sin u) u')
sinh (D u u') = D (sinh u) (scale (cosh u) u')
cosh (D u u') = D (cosh u) (scale (sinh u) u')
cos(a+b) == cos(a)cos(b) - sin(a)sin(b)
then it works.
Something must be known in advance about the relationship between sin and cos for addition, otherwise you cannot go from one to the other (and the basic
cos(a)^2+sin(a)^2=1
is not enough for that.