26 ms·

Differentiable programming from scratch

196 points by TheNumbat 4y ago

bmitc 4y ago
You don't need induction for (x+x'e)^n+1. The binomial formula can be applied once the arithmetic on dual numbers is introduced. > We can use this result to prove the same property for any smooth function f. Examining the Taylor expansion of f at zero (also known as its Maclaurin series): That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x|<=1. However, polynomial series expansions exist for |x|>1, where similar arguments would apply. Also, Taylor series and Maclaurin series aren't the same thing. A Maclaurin series is a Taylor series centered at 0. Lastly, is "differential programming" a new term? It seems weird to me that the machine learning community continues to reinvent terminology for already existing things. What is wrong with automatic differentiation? (Not necessarily a question for the author.) It's not really a new paradigm in the sense of "logic programming", "object-oriented programming", "functional programming", etc., and is instead just a technique.
- adgjlsfhk1 4y ago
  The idea behind the term "differential programming" is that many traditional autodiff systems force you into a highly restricted subset of the language or DSL (e.g. no loops, no if statements etc). Differential programming is a term used to describe systems that let you take derivatives of your entire source code. This lets you do things like AD through a simulation or optimization algorithm which can be really powerful for applying ML techniques to domains that are less typically suited to ML approaches (circuits, physics, differential equations etc)
  - bmitc 4y ago
    But I would wager that those are poor implementations of automatic differentiation, as the property that automatic differentiation works with for loops, if statements, etc. is inherent to automatic differentiation. So differential programming seems like automatic differentiation just implemented properly. I've written some simple forward-mode automatic differentiation implementations in a few languages, and it's akin to just using a library. It doesn't seem like a paradigm to me. Reverse-mode automatic differentiation is basically backpropagation. So again, ML seems to just like to rename things. I studied mathematics and have recently been trying to learn some ML. It's pretty annoying that a lot of mathematical terms seem to have been renamed or coopted for something else.
    - oddity 4y ago
      Autodiff does not work with for loops or if statements. The current solutions effectively pick a few promising traces through the program and then assume that nothing else exists. To handle it more elegantly (for things like preserving equational reasoning or avoiding exponential blowup) you need to address it at the level of language semantics.
      - bmitc 4y ago
        > Autodiff does not work with for loops or if statements. Is that necessarily true? Here is an incomplete automatic differentiation implementation that handles if statements just fine in a function definition. Unless you mean something else. type Dual = {Real: float; Epsilon: float} with static member (~-) (x: Dual) = {Real = -x.Real; Epsilon = -x.Epsilon} static member (+) (x: Dual, y: Dual) = { Real = x.Real + y.Real Epsilon = x.Epsilon + y.Epsilon } static member (+) (x: Dual, c: float) = {x with Real = x.Real + c} static member (+) (c: float, y: Dual) = {y with Real = c + y.Real} static member (-) (x: Dual, y: Dual) = x + (-y) static member (-) (x: Dual, c: float) = x + (-c) static member (-) (c: float, y: Dual) = c + (-y) static member (*) (x: Dual, y: Dual) = { Real = x.Real * y.Real Epsilon = x.Real * y.Epsilon + x.Epsilon * y.Real } static member (*) (c: float, y: Dual) = {Real = c; Epsilon = 0} * y static member (*) (x: Dual, c: float) = x * {Real = c; Epsilon = 0} let dcos (x: Dual) = {Real = cos x.Real; Epsilon = -(sin x.Real) * x.Epsilon} let dsin (x: Dual) = {Real = sin x.Real; Epsilon = (cos x.Real) * x.Epsilon} let differentiate (f: Dual -> Dual) a = let x = f {Real = a; Epsilon = 1.0} x.Epsilon let testFunction (x: Dual) = if x.Real < 0.0 then dcos x else dsin (x*x - 3.0*x) Using that gives: > differentiate testFunction -1.0 0.8414709848078965 > differentiate testFunction 1.0 0.4161468365471424 > differentiate testFunction 0.0 -3.0 Now, of course, one needs to be careful interpreting the result at a = 0.0. That's because the testFunction is not differentiable at that point due to a jump discontinuity there, but we still get a value back. But as far as I know, this is simply an issue with automatic differentiation in that it only correctly tells you what the derivative is if it exists at the given point.
  - data_maan 4y ago
    Mathematician here. > Differential programming is a term used to describe systems that let you take derivatives of your entire source code. I think the way this is stated is incorrect. What would the derivative of a program that outputs the reverse the input string be? It would be meaningless. It seems rather to be the case that it describes systems that let you take derivatives of your entire source code where that source code describes a numerical function. Perhaps it is obvious to state this, but I keep seeing differentiable programming being described as "taking a derivative of the source code" and it seems annoyingly imprecise. > This lets you do things like AD through a simulation or optimization algorithm This is also, taken literally, not a correct statement. It's not the algorithm which you want to differentiate, but a hard-to-differentiate function within the algorithm (which is always a gradient-descent type algorithm, as it otherwise makes no sense to consider derivatives; there is the entire domain of derivative-free optimization BTW). So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously.
    - radarsat1 4y ago
      > So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously. The specific proposal of differential programming as a paradigm that goes beyond simple applications of gradient descent for optimising NNs is exactly to apply gradient descent to optimise learning (and other) algorithms themselves. This may be to select hyperparameters, or to select among a family of algorithms, or to include differentiable constraints in the solver, etc. I wonder, are you familiar with now classic paper, Learning to learn by gradient descent by gradient descent? [0] https://arxiv.org/abs/1606.04474 https://arxiv.org/abs/1606.04474
      - selestify 4y ago
        Wow, it’s interesting that a paper from 2016 is already classic. This field moves fast!
        deleted 4y ago
- oddity 4y ago
  Object oriented programming, for example, doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime, but object oriented + differentiable programming does. It's no less of a paradigm than logic, quantum, or probabilistic programming. If you want to, you can view differentiable programming as extending logic programming with a product and chain rule (+ some additional constraints) that allows (smooth, if you want it) interpolation between data and code. That said, most discussion of differentiable programming is at the level of syntax sugar for reverse mode differentiation, so I can't blame you for that conclusion.
  - bmitc 4y ago
    You don't need OOP plus another paradigm to do automatic differentiation though. I've implemented automatic differentiation, albeit "simple" versions and only forward-mode at this point, but there's really nothing special about the implementations. Logic programming, on the other hand and for example, needs something much more substantial to be implemented as a library in an existing language, such as backtracking, unification, or the full-on Warren Abstract Machine. If someone has a clear example of differential programming that is different than just using automatic differentiation as a technique or library, then that might help. > doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime I'm not sure what you mean here. Could you elaborate?
    - oddity 4y ago
      I don't need OOP to do a hash table lookup and then an indirect function call with the receiver as the first argument either but that ignores that there's more to a paradigm than the algorithm I use for facilitating it. You can embed unification of expression trees as a library in C++. People implement backtracking all the time in almost every language. Talking about differentiable programming as if it's just autodiff is missing the point of what a programming paradigm is. There's a mechanism, yes, but that's just a means to an end of efficiently enabling a different way of approaching programming. In the case of differentiable programming, that's continuous code and continuous data enabling program search that doesn't have to use purely discrete methods (like logic programming). If that sounds like autodiff and backprop, then yes, that's because that's a good way to implement it. Tensorflow and PyTorch are DSLs embedded in Python and C++ both useable and used for more than just implementing neural networks, but most people aren't happy calling a library a language until it has a parser and a file extension. > I'm not sure what you mean here. Could you elaborate? Most programming languages assume that a variable can only contain one value, or a composite value of values. Differentiable programming lets code be smoothly transformed from one to the other while being meaningful at all points between. In an object oriented case, this would be like having a variable contain an object that behaves like some known object A or object B selectively depending on which choice maximizes the success of the program at any given moment.
- deleted 4y ago
  [deleted]
- kragen 4y ago
  Agreed about the binomial formula, but don't you need induction to prove the binomial theorem? That is, if you have some sort of set that's like the naturals except that Peano's axiom of induction doesn't apply (such as the naturals plus Alberto and Cristina, who are one another's successors) is the binomial theorem necessarily true in it? Agreed about Maclaurin series. I didn't know there existed smooth functions with divergent Taylor series. I don't understand how that happens; if we're looking at term $n$ of the Taylor series around some point $a$, it's $f^{(n)}(a) \frac{(x - a)^n}{n!}$, where $f^{(n)}$ is the nth derivative, right? I guess you could have a function whose derivatives eventually start increasing so fast that even if (x - a) is 10^{-100}, the exploding derivative eventually wins? PARI/GP helpfully informs me that deriv(atan(x)) is 1 - x^2 + x^4 - x^6 + x^8 - x^10 + x^12 - x^14 + O(x^16), which sure sounds like the sort of thing that would diverge when |x| > 1. But presumably that's based on the Maclaurin series for arctan, and you'd get a different result if you were taking a Taylor series around 0.9 or something? In response to taylor(atan(x-9/10), x) PARI/GP says things I will not repeat here, so I guess blindly pounding on the keyboard isn't going to get me very far. Some guidance could be helpful. I think differentiable programming is a new paradigm in the sense of logic programming and functional programming, and I do think it goes beyond just autodiff (though the linked article only explains autodiff). To the extent that a programming system is differentiable, you can use gradient descent to search for programs that minimize a loss function, not just inputs that do. But even just searching for inputs that minimize a loss function is a pretty different way to program than the conventional approach, even though Ivan Sutherland proposed it as a general approach in SKETCHPAD. An example of a differentiable programming system is in https://arxiv.org/abs/1605.06640 https://arxiv.org/abs/1605.06640 "Programming with a Differentiable Forth Interpreter", 02016.
  - bmitc 4y ago
    > Agreed about the binomial formula, but don't you need induction to prove the binomial theorem? Yes, that's the point. :) In that, they're basically re-proving the binomial theorem (or more accurately, using the same method) rather than just using its results with the new dual number arithmetic. Michael Spivak's Calculus has some great chapters on Taylor polynomials, Taylor's remainder theorem, and Taylor series. I've been looking into this stuff lately, to try and justify mathematically why automatic differentiation works (I've never read anything that does so, including several published papers), and that's where I was reminded of the fact that not everything is gold with Taylor's polynomials on real numbers. Maybe (?) the introduction of dual numbers gives something akin to complex analysis' concept of analytic. Not sure and not there yet. > I think differentiable programming is a new paradigm in the sense of logic programming and functional programming, and I do think it goes beyond just autodiff (though the linked article only explains autodiff). After some of the responses, maybe that's where I'm balking at. In that, I've only ever seen differentiable programming mentioned in the context of automatic differentiation. One of the papers posted led me to be more comfortable with the concept of differentiable programming as a distinct thing, in a sort of Mathematica sense, but I'll definitely need to read some more.
- ithinkso 4y ago
  > That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x|<=1. This issue creeps in a lot but I think it comes from the complex analysis, where differentiable function is always smooth and analytic (holomorphic).
  - bmitc 4y ago
    But as far as I know, there is no corresponding dual analysis. The dual numbers do not form a field. The issue primarily revolves around elementary functions, compositions of them, and polynomials.
    - ithinkso 4y ago
      Yeah, I was only trying to explain where the issue (assuming smooth=analytic, that you rightfully pointed out) might have come from
      - bmitc 4y ago
        Ahh, gotcha. I'm trying to figure this out myself. I've always been intrigued by automatic differentiation but have never been satisfied by any article addressing its mathematical justification.
        data_maan 4y ago
        Neither have I ...
floehopper 4y ago
You may also enjoy https://tomstu.art/automatic-differentiation-in-ruby https://tomstu.art/automatic-differentiation-in-ruby and the accompanying video https://www.youtube.com/watch?v=TI7mtWB4WiA https://www.youtube.com/watch?v=TI7mtWB4WiA.
foxes 4y ago
I feel differentiable programming is not really there. I understand the specific case of numerical functions, it may make sense if you just want to tweak some parameters a bit like a nn, or for example in quantum diff programming people seem to tweak parameters in some Hamiltonian. What I actually want is something you will actually change the structure of the program somehow. If you pretend the entire program is a function f, parameters are just points on your program. Why is moving to different points differentiating. Differentiating is producing a new function f’. In the case of the NN it makes sense to select different points. But then we do also modify the structure with dropouts etc.
quickthrower2 4y ago
Nice, I hope Max Slater keeps writing about math, because this article seems more like it is written for a human than a lot of math texts. But it doesn't skimp on complexity or use silly gifs to do that.
ducktective 4y ago
Nice! I asked something about this a while ago: https://news.ycombinator.com/item?id=31044118 https://news.ycombinator.com/item?id=31044118
- sillysaurusx 4y ago
  Thanks for the link. Interesting conversations and anecdotes. Don’t worry about the fact that you don’t understand anything. Just keep trying to get results. If you focus on getting results, the understanding will come to you naturally. It’s how I learned ML. Watching presentations is nice, but tinkering with working code is so much nicer. It’s no surprise you came away feeling like you don’t actually know what you thought you knew — the only way to understand it is to go get some experience. Also don’t worry that it takes a long time to understand something. This stuff is inherently hard. (My answer to your post is “Yes, of course I feel that way too! I don’t understand a damn thing in most presentations till I go code it myself.” So don’t feel alone!)
  - ducktective 4y ago
    Thanks
muds 4y ago
I find differentiable programming languages really fascinating. Think about this: a differentiable programming language is still a programming language. If the language is designed to facilitate a smooth optimization landscape, it's actually possible to "learn" programs with gradient descent. This opens the door to a lot of cool possibilities: - programming languages which use neural networks as primitive functions (think `result = sum([mlp(input) for input in list])`. NN's are (understandably) notoriously bad at learning simple operators [1]. Differentiable programming over a language defined by aggregation functions (map/fold/sum/mean/etc.) allows us to bypass learning some simple functions. - Flipping this around, we can use neural networks that use differentiable programs to regularize the outputs. Assume we have a NN that learns the speed of a car from a video. We know that a car's speed cannot exceed (say) 200mph. Make a differentiable program to express this and use it to regularize the output of the network. - Reusing the image->NN->speed example again, use the differentiable program to identify speeds/conditions where using a neural network policy is unsafe and switch to a (less-performant) handmade policy instead. Some more thoughts about this: https://atharvas.prose.sh/differentiable_dsls https://atharvas.prose.sh/differentiable_dsls [1] https://dselsam.github.io/posts/2018-09-16-neural-networks-occams-razor.html https://dselsam.github.io/posts/2018-09-16-neural-networks-o...
- mjburgess 4y ago
  Two points, (1) everything which makes programs useful is impure device access and state change, discretely sequenced over time (2) grad. desc. et al. do not learn discrete constraints (hence why NNs are bad at learning operators: they cant. x+x is defined fa. x; not fa x. in the training set).
  - muds 4y ago
    > everything which makes programs useful is impure device access and state change, discretely sequenced over time I haven't heard about this before actually. I'd love to hear more about this! "Impure," here, is PL terminology for functions that affect global state/arguments when you run them. right? So, brainstorming a bit, what this means is that making a diff. programming language that treats a NN module as a pure function won't actually be beneficial? I'm not sure if I'm drawing the correct conclusion but this is a really interesting point. Don't have an answer for this (yet!). > grad. desc. et al. do not learn discrete constraints Great Point! To push back a little on this. You're right that any discrete constraint will always mess up the smoothness of the function (eg: less-than-g is not smooth at x=g). However, we can engineer our way around this by relaxing a discrete constraint to its closest smooth approximation! So, we can implement the less-than-g function as a sigmoid that is shifted by +/-g. This introduces a parameter to control the slope of the sigmoid. In practice, I haven't had much difficulty learning programs even with a really steep slope for the sigmoid.
infogulch 4y ago
Related post: Differentiable Programming – A Simple Introduction | 159 points, 3 months ago, 49 comments | https://news.ycombinator.com/item?id=31000709 https://news.ycombinator.com/item?id=31000709 There I mention "The simple essence of automatic differentiation" which posits that by keeping the a differentiated function paired together with its integrand then many functional transformations -- including integration, subexpression deduplication, and even automatic conversion from forward mode to reverse mode -- would be greatly simplified. Allegedly this claim is not backed up by a practical demonstration yet, but imo this is a very intriguing approach.
yarg 4y ago
One thing that I've thought about, when using calculus in programs, you're often dealing with a very small (but finite) Δx, rather than an infinitesimal 𝛿x. And I don't think that the common differential equation is the ideal form when dealing with that situation. (Take for example g(x) = -f(-x), the gradients at x and -x are not equivalent for Δx, but would be for 𝛿x.) Anyway, (limit(h -> 0)((f(x + h) - f(x))/h) Why do we even need h? It's just (the infinitesimal) 𝛿x multiplied by an arbitrary finite constant. (You're dealing with a linear equivalent infinitesimal subsection of the graph - so 𝛿x and 𝛿y scale linearly with each other.) So remove h: ((f(x + 𝛿x) - f(x))/𝛿x) Looks cleaner. (f(x + 𝛿x) - f(x))/𝛿x ≡ (f(x) - f(x - 𝛿x))/𝛿x ≡ (f(x + 𝛿x) - f(x - 𝛿x))/(2 * 𝛿x) You can take the gradient from x to (x + 𝛿x) or from (x - 𝛿x) to x, or from (x - 𝛿x) to (x + 𝛿x). (The cube-root of the other three forms is also a valid differential equation, if you want to be evil about it.) (f(x + 𝛿x) - f(x - 𝛿x))/(2 * 𝛿x) (That's a nicer form for programmatic use; resolving the earlier mentioned gradient issue when dealing with finite deltas.) Another thing I noticed: the standard (h -> 0) form eliminates all parts of the gradient containing 𝛿x values - which is fine for infinitesimal 𝛿x, but is less ideal for finite Δx.
- ngcc_hk 4y ago
  Is h use instead of 𝛿 or Δ, because it is applicable to both partial and normal differential. 𝛿 Is always a partial symbol to me. d in dx whilst is not the same as h, as it stands its own way now as “operator”.
  - hither_shores 4y ago
    No, the h here is a number, not an operator.
  - yarg 4y ago
    I just find that it buries the lede.
- joe__f 4y ago
  If you're interested in how to best calculate derivatives numerically using a finite difference rather than an infinitesimal, try having a look at the Wikipedia page on numerical differentiation. The punchline is that you can control the error in f'(x) much better if you use many displacements, ie. f'(x) = a1 f(x + b1 h) + a2 f(x + b2 h) + a3 f(x + b3 h)..., where the bi are chosen and the ai depend on the bi and h.
deleted 4y ago
[deleted]
foxbee 4y ago
This is the first time i've read about differentiable programming and it was incredibly interesting. Also, it's the first time I've came across this blog and it's wonderful. The minimal interactions really helped me visualise the content and it helped with comprehension. Great job.
- auggierose 4y ago
  Yes, very beautiful stuff. Only thing I don't like: The text in the SVG's is not texed, but that's difficult to achieve, I guess.
QuackingTheQ 4y ago
A pet peeve of mine is that differentiable programming is co-opted almost entirely by deep learning + neural networks. The idea of differentiable programming is much bigger than SGD, and in fact neural networks are typically a simple program to differentiate. Full differentiable programming requires solving much more involved problems around control flow than just implementing numerical forward/reverse mode for math operations with well defined and understood gradients.
josevalim 4y ago
Thank you for sharing, this was a great article! I had to implement autodiff from scratch for Nx (https://github.com/elixir-nx/nx https://github.com/elixir-nx/nx) about 18 months ago and this would have helped me so much! I spent roughly a month chasing a bug because I was not handling the case of duplicated incoming nodes and you outline it very clearly. I will be recommending the article from now on to anyone who needs to understand how autodiff works.

196 points by TheNumbat 4y ago

You don't need induction for (x+x'e)^n+1. The binomial formula can be applied once the arithmetic on dual numbers is introduced. > We can use this result to prove the same property for any smooth function f. Examining the Taylor expansion of f at zero (also known as its Maclaurin series): That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x|<=1. However, polynomial series expansions exist for |x|>1, where similar arguments would apply. Also, Taylor series and Maclaurin series aren't the same thing. A Maclaurin series is a Taylor series centered at 0. Lastly, is "differential programming" a new term? It seems weird to me that the machine learning community continues to reinvent terminology for already existing things. What is wrong with automatic differentiation? (Not necessarily a question for the author.) It's not really a new paradigm in the sense of "logic programming", "object-oriented programming", "functional programming", etc., and is instead just a technique.

adgjlsfhk1 4y ago
The idea behind the term "differential programming" is that many traditional autodiff systems force you into a highly restricted subset of the language or DSL (e.g. no loops, no if statements etc). Differential programming is a term used to describe systems that let you take derivatives of your entire source code. This lets you do things like AD through a simulation or optimization algorithm which can be really powerful for applying ML techniques to domains that are less typically suited to ML approaches (circuits, physics, differential equations etc)
- bmitc 4y ago
  But I would wager that those are poor implementations of automatic differentiation, as the property that automatic differentiation works with for loops, if statements, etc. is inherent to automatic differentiation. So differential programming seems like automatic differentiation just implemented properly. I've written some simple forward-mode automatic differentiation implementations in a few languages, and it's akin to just using a library. It doesn't seem like a paradigm to me. Reverse-mode automatic differentiation is basically backpropagation. So again, ML seems to just like to rename things. I studied mathematics and have recently been trying to learn some ML. It's pretty annoying that a lot of mathematical terms seem to have been renamed or coopted for something else.
  - oddity 4y ago
    Autodiff does not work with for loops or if statements. The current solutions effectively pick a few promising traces through the program and then assume that nothing else exists. To handle it more elegantly (for things like preserving equational reasoning or avoiding exponential blowup) you need to address it at the level of language semantics.
    - bmitc 4y ago
      > Autodiff does not work with for loops or if statements. Is that necessarily true? Here is an incomplete automatic differentiation implementation that handles if statements just fine in a function definition. Unless you mean something else. type Dual = {Real: float; Epsilon: float} with static member (~-) (x: Dual) = {Real = -x.Real; Epsilon = -x.Epsilon} static member (+) (x: Dual, y: Dual) = { Real = x.Real + y.Real Epsilon = x.Epsilon + y.Epsilon } static member (+) (x: Dual, c: float) = {x with Real = x.Real + c} static member (+) (c: float, y: Dual) = {y with Real = c + y.Real} static member (-) (x: Dual, y: Dual) = x + (-y) static member (-) (x: Dual, c: float) = x + (-c) static member (-) (c: float, y: Dual) = c + (-y) static member (*) (x: Dual, y: Dual) = { Real = x.Real * y.Real Epsilon = x.Real * y.Epsilon + x.Epsilon * y.Real } static member (*) (c: float, y: Dual) = {Real = c; Epsilon = 0} * y static member (*) (x: Dual, c: float) = x * {Real = c; Epsilon = 0} let dcos (x: Dual) = {Real = cos x.Real; Epsilon = -(sin x.Real) * x.Epsilon} let dsin (x: Dual) = {Real = sin x.Real; Epsilon = (cos x.Real) * x.Epsilon} let differentiate (f: Dual -> Dual) a = let x = f {Real = a; Epsilon = 1.0} x.Epsilon let testFunction (x: Dual) = if x.Real < 0.0 then dcos x else dsin (x*x - 3.0*x) Using that gives: > differentiate testFunction -1.0 0.8414709848078965 > differentiate testFunction 1.0 0.4161468365471424 > differentiate testFunction 0.0 -3.0 Now, of course, one needs to be careful interpreting the result at a = 0.0. That's because the testFunction is not differentiable at that point due to a jump discontinuity there, but we still get a value back. But as far as I know, this is simply an issue with automatic differentiation in that it only correctly tells you what the derivative is if it exists at the given point.
- data_maan 4y ago
  Mathematician here. > Differential programming is a term used to describe systems that let you take derivatives of your entire source code. I think the way this is stated is incorrect. What would the derivative of a program that outputs the reverse the input string be? It would be meaningless. It seems rather to be the case that it describes systems that let you take derivatives of your entire source code where that source code describes a numerical function. Perhaps it is obvious to state this, but I keep seeing differentiable programming being described as "taking a derivative of the source code" and it seems annoyingly imprecise. > This lets you do things like AD through a simulation or optimization algorithm This is also, taken literally, not a correct statement. It's not the algorithm which you want to differentiate, but a hard-to-differentiate function within the algorithm (which is always a gradient-descent type algorithm, as it otherwise makes no sense to consider derivatives; there is the entire domain of derivative-free optimization BTW). So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously.
  - radarsat1 4y ago
    > So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously. The specific proposal of differential programming as a paradigm that goes beyond simple applications of gradient descent for optimising NNs is exactly to apply gradient descent to optimise learning (and other) algorithms themselves. This may be to select hyperparameters, or to select among a family of algorithms, or to include differentiable constraints in the solver, etc. I wonder, are you familiar with now classic paper, Learning to learn by gradient descent by gradient descent? [0] https://arxiv.org/abs/1606.04474 https://arxiv.org/abs/1606.04474
    - selestify 4y ago
      Wow, it’s interesting that a paper from 2016 is already classic. This field moves fast!
      - deleted 4y ago
oddity 4y ago
Object oriented programming, for example, doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime, but object oriented + differentiable programming does. It's no less of a paradigm than logic, quantum, or probabilistic programming. If you want to, you can view differentiable programming as extending logic programming with a product and chain rule (+ some additional constraints) that allows (smooth, if you want it) interpolation between data and code. That said, most discussion of differentiable programming is at the level of syntax sugar for reverse mode differentiation, so I can't blame you for that conclusion.
- bmitc 4y ago
  You don't need OOP plus another paradigm to do automatic differentiation though. I've implemented automatic differentiation, albeit "simple" versions and only forward-mode at this point, but there's really nothing special about the implementations. Logic programming, on the other hand and for example, needs something much more substantial to be implemented as a library in an existing language, such as backtracking, unification, or the full-on Warren Abstract Machine. If someone has a clear example of differential programming that is different than just using automatic differentiation as a technique or library, then that might help. > doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime I'm not sure what you mean here. Could you elaborate?
  - oddity 4y ago
    I don't need OOP to do a hash table lookup and then an indirect function call with the receiver as the first argument either but that ignores that there's more to a paradigm than the algorithm I use for facilitating it. You can embed unification of expression trees as a library in C++. People implement backtracking all the time in almost every language. Talking about differentiable programming as if it's just autodiff is missing the point of what a programming paradigm is. There's a mechanism, yes, but that's just a means to an end of efficiently enabling a different way of approaching programming. In the case of differentiable programming, that's continuous code and continuous data enabling program search that doesn't have to use purely discrete methods (like logic programming). If that sounds like autodiff and backprop, then yes, that's because that's a good way to implement it. Tensorflow and PyTorch are DSLs embedded in Python and C++ both useable and used for more than just implementing neural networks, but most people aren't happy calling a library a language until it has a parser and a file extension. > I'm not sure what you mean here. Could you elaborate? Most programming languages assume that a variable can only contain one value, or a composite value of values. Differentiable programming lets code be smoothly transformed from one to the other while being meaningful at all points between. In an object oriented case, this would be like having a variable contain an object that behaves like some known object A or object B selectively depending on which choice maximizes the success of the program at any given moment.
deleted 4y ago
[deleted]
kragen 4y ago
Agreed about the binomial formula, but don't you need induction to prove the binomial theorem? That is, if you have some sort of set that's like the naturals except that Peano's axiom of induction doesn't apply (such as the naturals plus Alberto and Cristina, who are one another's successors) is the binomial theorem necessarily true in it? Agreed about Maclaurin series. I didn't know there existed smooth functions with divergent Taylor series. I don't understand how that happens; if we're looking at term $n$ of the Taylor series around some point $a$, it's $f^{(n)}(a) \frac{(x - a)^n}{n!}$, where $f^{(n)}$ is the nth derivative, right? I guess you could have a function whose derivatives eventually start increasing so fast that even if (x - a) is 10^{-100}, the exploding derivative eventually wins? PARI/GP helpfully informs me that deriv(atan(x)) is 1 - x^2 + x^4 - x^6 + x^8 - x^10 + x^12 - x^14 + O(x^16), which sure sounds like the sort of thing that would diverge when |x| > 1. But presumably that's based on the Maclaurin series for arctan, and you'd get a different result if you were taking a Taylor series around 0.9 or something? In response to taylor(atan(x-9/10), x) PARI/GP says things I will not repeat here, so I guess blindly pounding on the keyboard isn't going to get me very far. Some guidance could be helpful. I think differentiable programming is a new paradigm in the sense of logic programming and functional programming, and I do think it goes beyond just autodiff (though the linked article only explains autodiff). To the extent that a programming system is differentiable, you can use gradient descent to search for programs that minimize a loss function, not just inputs that do. But even just searching for inputs that minimize a loss function is a pretty different way to program than the conventional approach, even though Ivan Sutherland proposed it as a general approach in SKETCHPAD. An example of a differentiable programming system is in https://arxiv.org/abs/1605.06640 https://arxiv.org/abs/1605.06640 "Programming with a Differentiable Forth Interpreter", 02016.
- bmitc 4y ago
  > Agreed about the binomial formula, but don't you need induction to prove the binomial theorem? Yes, that's the point. :) In that, they're basically re-proving the binomial theorem (or more accurately, using the same method) rather than just using its results with the new dual number arithmetic. Michael Spivak's Calculus has some great chapters on Taylor polynomials, Taylor's remainder theorem, and Taylor series. I've been looking into this stuff lately, to try and justify mathematically why automatic differentiation works (I've never read anything that does so, including several published papers), and that's where I was reminded of the fact that not everything is gold with Taylor's polynomials on real numbers. Maybe (?) the introduction of dual numbers gives something akin to complex analysis' concept of analytic. Not sure and not there yet. > I think differentiable programming is a new paradigm in the sense of logic programming and functional programming, and I do think it goes beyond just autodiff (though the linked article only explains autodiff). After some of the responses, maybe that's where I'm balking at. In that, I've only ever seen differentiable programming mentioned in the context of automatic differentiation. One of the papers posted led me to be more comfortable with the concept of differentiable programming as a distinct thing, in a sort of Mathematica sense, but I'll definitely need to read some more.
ithinkso 4y ago
> That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x|<=1. This issue creeps in a lot but I think it comes from the complex analysis, where differentiable function is always smooth and analytic (holomorphic).
- bmitc 4y ago
  But as far as I know, there is no corresponding dual analysis. The dual numbers do not form a field. The issue primarily revolves around elementary functions, compositions of them, and polynomials.
  - ithinkso 4y ago
    Yeah, I was only trying to explain where the issue (assuming smooth=analytic, that you rightfully pointed out) might have come from
    - bmitc 4y ago
      Ahh, gotcha. I'm trying to figure this out myself. I've always been intrigued by automatic differentiation but have never been satisfied by any article addressing its mathematical justification.
      - data_maan 4y ago
        Neither have I ...

floehopper 4y ago

You may also enjoy https://tomstu.art/automatic-differentiation-in-ruby https://tomstu.art/automatic-differentiation-in-ruby and the accompanying video https://www.youtube.com/watch?v=TI7mtWB4WiA https://www.youtube.com/watch?v=TI7mtWB4WiA.

foxes 4y ago

I feel differentiable programming is not really there. I understand the specific case of numerical functions, it may make sense if you just want to tweak some parameters a bit like a nn, or for example in quantum diff programming people seem to tweak parameters in some Hamiltonian. What I actually want is something you will actually change the structure of the program somehow. If you pretend the entire program is a function f, parameters are just points on your program. Why is moving to different points differentiating. Differentiating is producing a new function f’. In the case of the NN it makes sense to select different points. But then we do also modify the structure with dropouts etc.

quickthrower2 4y ago

Nice, I hope Max Slater keeps writing about math, because this article seems more like it is written for a human than a lot of math texts. But it doesn't skimp on complexity or use silly gifs to do that.

ducktective 4y ago

Nice! I asked something about this a while ago: https://news.ycombinator.com/item?id=31044118 https://news.ycombinator.com/item?id=31044118

sillysaurusx 4y ago
Thanks for the link. Interesting conversations and anecdotes. Don’t worry about the fact that you don’t understand anything. Just keep trying to get results. If you focus on getting results, the understanding will come to you naturally. It’s how I learned ML. Watching presentations is nice, but tinkering with working code is so much nicer. It’s no surprise you came away feeling like you don’t actually know what you thought you knew — the only way to understand it is to go get some experience. Also don’t worry that it takes a long time to understand something. This stuff is inherently hard. (My answer to your post is “Yes, of course I feel that way too! I don’t understand a damn thing in most presentations till I go code it myself.” So don’t feel alone!)
- ducktective 4y ago
  Thanks

muds 4y ago

I find differentiable programming languages really fascinating. Think about this: a differentiable programming language is still a programming language. If the language is designed to facilitate a smooth optimization landscape, it's actually possible to "learn" programs with gradient descent. This opens the door to a lot of cool possibilities: - programming languages which use neural networks as primitive functions (think `result = sum([mlp(input) for input in list])`. NN's are (understandably) notoriously bad at learning simple operators [1]. Differentiable programming over a language defined by aggregation functions (map/fold/sum/mean/etc.) allows us to bypass learning some simple functions. - Flipping this around, we can use neural networks that use differentiable programs to regularize the outputs. Assume we have a NN that learns the speed of a car from a video. We know that a car's speed cannot exceed (say) 200mph. Make a differentiable program to express this and use it to regularize the output of the network. - Reusing the image->NN->speed example again, use the differentiable program to identify speeds/conditions where using a neural network policy is unsafe and switch to a (less-performant) handmade policy instead. Some more thoughts about this: https://atharvas.prose.sh/differentiable_dsls https://atharvas.prose.sh/differentiable_dsls [1] https://dselsam.github.io/posts/2018-09-16-neural-networks-occams-razor.html https://dselsam.github.io/posts/2018-09-16-neural-networks-o...

mjburgess 4y ago
Two points, (1) everything which makes programs useful is impure device access and state change, discretely sequenced over time (2) grad. desc. et al. do not learn discrete constraints (hence why NNs are bad at learning operators: they cant. x+x is defined fa. x; not fa x. in the training set).
- muds 4y ago
  > everything which makes programs useful is impure device access and state change, discretely sequenced over time I haven't heard about this before actually. I'd love to hear more about this! "Impure," here, is PL terminology for functions that affect global state/arguments when you run them. right? So, brainstorming a bit, what this means is that making a diff. programming language that treats a NN module as a pure function won't actually be beneficial? I'm not sure if I'm drawing the correct conclusion but this is a really interesting point. Don't have an answer for this (yet!). > grad. desc. et al. do not learn discrete constraints Great Point! To push back a little on this. You're right that any discrete constraint will always mess up the smoothness of the function (eg: less-than-g is not smooth at x=g). However, we can engineer our way around this by relaxing a discrete constraint to its closest smooth approximation! So, we can implement the less-than-g function as a sigmoid that is shifted by +/-g. This introduces a parameter to control the slope of the sigmoid. In practice, I haven't had much difficulty learning programs even with a really steep slope for the sigmoid.

infogulch 4y ago

Related post: Differentiable Programming – A Simple Introduction | 159 points, 3 months ago, 49 comments | https://news.ycombinator.com/item?id=31000709 https://news.ycombinator.com/item?id=31000709 There I mention "The simple essence of automatic differentiation" which posits that by keeping the a differentiated function paired together with its integrand then many functional transformations -- including integration, subexpression deduplication, and even automatic conversion from forward mode to reverse mode -- would be greatly simplified. Allegedly this claim is not backed up by a practical demonstration yet, but imo this is a very intriguing approach.

yarg 4y ago

One thing that I've thought about, when using calculus in programs, you're often dealing with a very small (but finite) Δx, rather than an infinitesimal 𝛿x. And I don't think that the common differential equation is the ideal form when dealing with that situation. (Take for example g(x) = -f(-x), the gradients at x and -x are not equivalent for Δx, but would be for 𝛿x.) Anyway, (limit(h -> 0)((f(x + h) - f(x))/h) Why do we even need h? It's just (the infinitesimal) 𝛿x multiplied by an arbitrary finite constant. (You're dealing with a linear equivalent infinitesimal subsection of the graph - so 𝛿x and 𝛿y scale linearly with each other.) So remove h: ((f(x + 𝛿x) - f(x))/𝛿x) Looks cleaner. (f(x + 𝛿x) - f(x))/𝛿x ≡ (f(x) - f(x - 𝛿x))/𝛿x ≡ (f(x + 𝛿x) - f(x - 𝛿x))/(2 * 𝛿x) You can take the gradient from x to (x + 𝛿x) or from (x - 𝛿x) to x, or from (x - 𝛿x) to (x + 𝛿x). (The cube-root of the other three forms is also a valid differential equation, if you want to be evil about it.) (f(x + 𝛿x) - f(x - 𝛿x))/(2 * 𝛿x) (That's a nicer form for programmatic use; resolving the earlier mentioned gradient issue when dealing with finite deltas.) Another thing I noticed: the standard (h -> 0) form eliminates all parts of the gradient containing 𝛿x values - which is fine for infinitesimal 𝛿x, but is less ideal for finite Δx.

ngcc_hk 4y ago
Is h use instead of 𝛿 or Δ, because it is applicable to both partial and normal differential. 𝛿 Is always a partial symbol to me. d in dx whilst is not the same as h, as it stands its own way now as “operator”.
- hither_shores 4y ago
  No, the h here is a number, not an operator.
- yarg 4y ago
  I just find that it buries the lede.
joe__f 4y ago
If you're interested in how to best calculate derivatives numerically using a finite difference rather than an infinitesimal, try having a look at the Wikipedia page on numerical differentiation. The punchline is that you can control the error in f'(x) much better if you use many displacements, ie. f'(x) = a1 f(x + b1 h) + a2 f(x + b2 h) + a3 f(x + b3 h)..., where the bi are chosen and the ai depend on the bi and h.

deleted 4y ago

[deleted]

foxbee 4y ago

This is the first time i've read about differentiable programming and it was incredibly interesting. Also, it's the first time I've came across this blog and it's wonderful. The minimal interactions really helped me visualise the content and it helped with comprehension. Great job.

auggierose 4y ago
Yes, very beautiful stuff. Only thing I don't like: The text in the SVG's is not texed, but that's difficult to achieve, I guess.

QuackingTheQ 4y ago

A pet peeve of mine is that differentiable programming is co-opted almost entirely by deep learning + neural networks. The idea of differentiable programming is much bigger than SGD, and in fact neural networks are typically a simple program to differentiate. Full differentiable programming requires solving much more involved problems around control flow than just implementing numerical forward/reverse mode for math operations with well defined and understood gradients.

josevalim 4y ago

Thank you for sharing, this was a great article! I had to implement autodiff from scratch for Nx (https://github.com/elixir-nx/nx https://github.com/elixir-nx/nx) about 18 months ago and this would have helped me so much! I spent roughly a month chasing a bug because I was not handling the case of duplicated incoming nodes and you outline it very clearly. I will be recommending the article from now on to anyone who needs to understand how autodiff works.