7 ms·

Differentiation for Hackers

176 points by adamnemecek 7y ago

mlevental 7y ago
here's a very readable survey paper http://jmlr.org/papers/volume18/17-468/17-468.pdf http://jmlr.org/papers/volume18/17-468/17-468.pdf
Bostonian 7y ago
What do automatic differentiation tools do for functions with integer arguments?
- osipov 7y ago
  Great question. Both TensorFlow and PyTorch pretty much do nothing https://github.com/tensorflow/tensorflow/issues/20524 https://github.com/tensorflow/tensorflow/issues/20524
  - mcabbott 7y 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 7y ago
    It is possible to do backprop with integers: https://arxiv.org/abs/1802.04680 https://arxiv.org/abs/1802.04680
adamnemecek 7y ago
Autodiff is insane. Kids waste how much time in school doing analytical calculus like troglodytes.
- taneq 7y ago
  You... do realise why doing these things analytically is worth while, right?
  - adamnemecek 7y ago
    I dont, no.
    - wolfram74 7y ago
      Numerical methods can be efficient, but nothing beats an analytic method that can be simply evaluated after derived. Often times you can go from an approximate answer with numerous function evaluations to an exact answer in one simpler function evaluation. Pathological cases not withstanding.
      - adamnemecek 7y ago
        AD is NOT a numerical method, it's very precise. You can in fact do it on paper as well. https://blog.demofox.org/2014/12/30/dual-numbers-automatic-differentiation/ https://blog.demofox.org/2014/12/30/dual-numbers-automatic-d... Analytical derivatives grow exponentially longer with the length of the expression. AD doesn't have this problem.
        tntn 7y ago
        Just because automatic differentiation is a different technique than numerical differentiation doesn't mean it isn't a numerical method. (I probably should not say this, but I will anyway: your comments regarding math and science always give me the distinct impression that you know the name of a lot of things without knowing much about the thing. You are frequently breathless about analog quantum computing, Lie algebras, Chu spaces, some universal concept of duality, but then you fail to respond with substantial arguments to people that try to temper the breathlessness. If you want to convince people of things, you should work on this.)
tobmlt 7y 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.

176 points by adamnemecek 7y ago

here's a very readable survey paper http://jmlr.org/papers/volume18/17-468/17-468.pdf http://jmlr.org/papers/volume18/17-468/17-468.pdf

Bostonian 7y ago

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

osipov 7y ago
Great question. Both TensorFlow and PyTorch pretty much do nothing https://github.com/tensorflow/tensorflow/issues/20524 https://github.com/tensorflow/tensorflow/issues/20524
- mcabbott 7y 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 7y ago
  It is possible to do backprop with integers: https://arxiv.org/abs/1802.04680 https://arxiv.org/abs/1802.04680

adamnemecek 7y ago

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

taneq 7y ago
You... do realise why doing these things analytically is worth while, right?
- adamnemecek 7y ago
  I dont, no.
  - wolfram74 7y ago
    Numerical methods can be efficient, but nothing beats an analytic method that can be simply evaluated after derived. Often times you can go from an approximate answer with numerous function evaluations to an exact answer in one simpler function evaluation. Pathological cases not withstanding.
    - adamnemecek 7y ago
      AD is NOT a numerical method, it's very precise. You can in fact do it on paper as well. https://blog.demofox.org/2014/12/30/dual-numbers-automatic-differentiation/ https://blog.demofox.org/2014/12/30/dual-numbers-automatic-d... Analytical derivatives grow exponentially longer with the length of the expression. AD doesn't have this problem.
      - tntn 7y ago
        Just because automatic differentiation is a different technique than numerical differentiation doesn't mean it isn't a numerical method. (I probably should not say this, but I will anyway: your comments regarding math and science always give me the distinct impression that you know the name of a lot of things without knowing much about the thing. You are frequently breathless about analog quantum computing, Lie algebras, Chu spaces, some universal concept of duality, but then you fail to respond with substantial arguments to people that try to temper the breathlessness. If you want to convince people of things, you should work on this.)

tobmlt 7y 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.