Differentiation for Hackers

https://github.com/MikeInnes/diff-zoo

by adamnemecek • 7 years ago

176 51 7 years ago

github.com

mlevental• 7 years ago

here's a very readable survey paper

http://jmlr.org/papers/volume18/17-468/17-468.pdf

Bostonian• 7 years ago

What do automatic differentiation tools do for functions with integer arguments?

osipov• 7 years ago

Great question. Both TensorFlow and PyTorch pretty much do nothing https://github.com/tensorflow/tensorflow/issues/20524

mcabbott• 7 years ago

That seems strange, if I'm reading it correctly.

In the author's packages, integers which label dimensions etc. have gradient `nothing`, but arrays which happen to contain integers do not signal anything:

    julia> Zygote.gradient((x,d)->abs(sum(sin,fft(x,d))), [2 2; 0 0], 2)
    (Complex{Float64}[-0.346356+0.0im 1.65364+0.0im; -2.0+0.0im 0.0+0.0im], nothing)

bmc7505• 7 years ago

It is possible to do backprop with integers: https://arxiv.org/abs/1802.04680

adamnemecek15• 7 years ago

Autodiff is insane. Kids waste how much time in school doing analytical calculus like troglodytes.

taneq• 7 years ago

You... do realise why doing these things analytically is worth while, right?

adamnemecek15• 7 years ago

I dont, no.

noelwelsh• 7 years ago

I don't really understand this comment. The rules of forward mode automatic differentiation are exactly the rules of symbolic differentiation one would learn in high school, except AD is evaluated at a particular point (thus avoiding the need to build an expression tree and thus avoiding exponential blow-up in the size of said tree).

AD is also on fairly shaky ground once you step outside what can be expressed in standard analytical calculus. For example it is fairly easy to express the same function in different ways and get derivatives that differ. A lot of work on semantics is needed.

adamnemecek15• 7 years ago

For example it is fairly easy to express the same function in different ways and get derivatives that differ.

Example?

brighter2morrow• 7 years ago

Learning to do calculus allows you to do it on paper and in your head. Lines of code are liabilities that need to be maintained, understood concepts are assets that let you build, maintain, and simplify.

adamnemecek15• 7 years ago

AD can be done on paper. Analytical calculus derivatives get exponentially longer with the length of the derived expression.

https://blog.demofox.org/2014/12/30/dual-numbers-automatic-d...

gugagore6• 7 years ago

It's good to question what we teach. Like I never learned any methods for computing a square root, to arbitrary precision, whereas my parents did.

But autodiff doesn't replace symbolic differentiation. Consider the derivative of cuberoot(x^3). Autodiff struggles at x=0 because x^3 is flat (slope 0) and cuberoot is vertical (slope inf). And together, with autodiff, you get slope NaN.

If you wanted to try to fix that problem with autodiff, well first off it's likely not worth it because similar problems are inherent to autodiff, but you'll need an analytic understanding of what's going on.

adamnemecek15• 7 years ago

I'm out right now but this doesn't sound right. How does autodiff struggle with it?

one-more-minute• 7 years ago

It's true that most autodiff systems would behave this way, but a human given only the rules of calculus (the same rules as AD) would have trouble at the same point. Of course, most mathemeticians would apply additional insights while differentiating here (such as cancellation of terms or L'Hôpital's rule). But equally, you could add these things to an AD too; they are orthogonal to the basic derivative transformation, so it's really a difference of degree at best.

eli_gottlieb2• 7 years ago

Autodiff only works because analytical calculus can prove that differentiation is a functor over functions.

jjtheblunt• 7 years ago

over continuous functions?

nthompson• 7 years ago

Automatic differentiation only works on functions which are locally complex analytic. It fails on things that fall outside that model, but are still differentiable. Daubechies wavelets are a good example of this.

ChrisRackauckas• 7 years ago

Julia's systems can make use of ChainRules.jl which doesn't assume locally complex analytic, and instead uses its Wirtinger derivatives (df/dz and df/dzbar), and if complex analytic just uses the well-known simplification df/dzbar=0. This allows for non-analytic functions to be used, and you just need to supply all primitives in Wirtinger form. Julia has enough non-ML people using this stuff that complex numbers actually get used here :).

petschge4• 7 years ago

Kids in school say "why do I to learn X, I am never going to need it in real live".

And then you end up with adults who don't believe that the earth is round, that vaccines are low-risk and extremely beneficial and think that the existence of snow means that there is no climate change and that homeopathy and essential oils are a valid alternative to modern medicine, etc.

tobmlt3• 7 years ago

This is really a nice thing to put out there. I want to add that AD (automatic differentiation) can be a great jumping off point to other things. (It sure was for me in my studies anyway) Here is the path I followed (though I am sure there are many paths; I am too dumb and tired to dream up another right now. Perhaps that is why I am so eager to put this all out here in a "gushy" way -- my apologies):

First I implemented simple forward mode AD in Python (with NumPy, handling gradients and Hessians so you could apply AD to find extrema of constrained variational problems, (to design constrained B-spline geometry for example... or construct equations of motion), then extended to handle interval analysis, which introduces a tiny bit of topology (fixed point theorems and such - provably find all solutions to nonlinear systems over some domain).

Then pick up declarative programming (unification) and revisit overloading to build up a mathematical expression tree for anything you have implemented. (In detail, overload math such that, for some object which is a mathematical combination of two other objects, store in the new object's memory some representation of the two original objects, and also the operation used to combine them. Remember to track your automatically generated-connectives! (all expressions are ternary - n-ary stuff get broken out into ternary stuff) )

Then starting at the final "node" of this mathematical tree, walk back down the tree to build whatever you want. (Reverse mode ad can be done this way, and is a good thing to try) I used it to automatically compile math down into logical rules for constraint programming. Much fun!

Now re-do it all in C++ but use overloading to build a math lib to support everything, or, use eigen, or some other expression template lib. (I'm not done with this.)

Ah, expression template libraries are another instance of "reverse mode style" expression tree computation. AKA the "interpreter pattern". Good fun here, but more involved I think.

Differentiation for Hackers

Related Stories