11 ms·

Differentiable Programming Manifesto

180 points by kristianp 7y ago

kragen 7y ago
This looks like it's going to be a really big deal unless they totally fuck it up. Autodiff greatly simplifies all kinds of continuous mathematical optimization algorithms, and using mathematical optimization means you only have to write code that can recognize things that look similar to a solution instead of code that can find the solution — in a sense, mathematical optimization derives your code from tests. Autodiff is useful for other kinds of things too, not just mathematical optimization, as they mention in the manifesto. This weekend I wrote a real-time SDF raymarcher in a page of Lua (https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.png https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.png https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.lua https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.lua), but the surface shading is pretty lame because without sampling the SDF multiple times it doesn't yet have any way to calculate surface normals. Guess what a surface normal is? It's the gradient of the SDF, and reverse-mode autodiff can sample the SDF and its gradient in only double the time of just sampling the SDF. Pretty much anything you do in continuous domains can get simpler and/or better-performing with autodiff. This is why I've written so much about it in Dercuano. It's worth pointing out that you don't need to redesign your language to get first-class differentiable programming. Source-to-source transformation has been used to do autodiff in FORTRAN for at least ten years, including on pretty massive applications. (This is mentioned in the manifesto.)
- seanmcdirmid 7y ago
  Conal Elliott (the guy who co-invented FRP) did a nice project on shading computational surfaces by extracting derivatives from code more than a decade ago: http://conal.net/Vertigo/ http://conal.net/Vertigo/ He is now very active in the differentiable programming community, but he got started on the problem in the graphics field.
  - noblethrasher 7y ago
    He also gave nice presentation on AD: https://www.youtube.com/watch?v=ne99laPUxN4 https://www.youtube.com/watch?v=ne99laPUxN4 (surprised that you didn't already mention it, considering the venue ;-))
  - kragen 7y ago
    The manifesto links one of his papers, "The simple essence", which I've started but haven't finished.
    - seanmcdirmid 7y ago
      He has been working on that for a long time. Though much of his earlier work is symbolic differentiation, I’m not very familiar with the more recent AD stuff.
    - thechao 7y ago
      Let me mostly summarize Conal’s “simple” reverse AD: he drops the tape into the stack. This has two impacts: the stack is “about twice as long”; and, you “may (will?) lose tail recursion”. It is still a really good paper—and no doubt a lot of the subtlety was list to me.
- sitkack 7y ago
  AD also has a nice synergy with DNN, the whole formalization allows for moving the runtime into a DNN and thus onto a GPU. I have been looking for a technique for representing algorithms that are amenable to conversion to anytime [1] I believe AD could be that technique. [1] https://en.wikipedia.org/wiki/Anytime_algorithm https://en.wikipedia.org/wiki/Anytime_algorithm
  - kragen 7y ago
    Well, successive-approximation mathematical optimization algorithms are sort of inherently anytime, in a way: you can stop after any integer number of iterations and use the approximate solution. Some of them fail to be anytime in practice, like SOR (“successive over-relaxation”) where you usually quit after like six iterations but each iteration takes a long time. And autodiff makes it a lot easier to apply mathematical optimization, in particular variants of gradient descent, one popular use of which is training deep ANNs. Is that what you meant, or are you talking about something else?
    - sitkack 7y ago
      This is it. I think AD can be used to train a DNN, the DNN in turn can be used to power an anytime algorithm such that you can have systems that can not only respond on different time scales, they are also robust in the face of sensor noise, adversarial sensors or broken actuators.
dual_basis 7y ago
I like differentiable programming a lot, but can anyone explain the motivation for Swift as their language of choice for this? I assume it was simply because they wanted to get Chris Lattner, and Swift was his baby. Julia seems like a much better target for this, I wish they had just dedicated some money or resources to that. I don't have a problem with Swift's language design per-se (although Julia's dynamic nature really lends itself more naturally to the sort of problems you might be trying to solve using differential programming, in my opinion) but its cross-platform support is terrible. Why would you choose Mac's boutique language as the foundation of your new paradigm?
- nnq 7y ago
  > Julia seems like a much better target for this Exactly, at least from an outside perspective, why tf?! It seems like people love so much bolting stuff to "classic, conservative" languages that they do it even if it's 10x more work than doing it in a language already having full fledged mature real macros. And this is not Common Lisp we're talking about... Julia is a pretty "normal" language that wouldn't scare anyone off! (EDIT+: though, as a software engineer primarily, I do have a slight personal preference for more classic single-dispatchy languages like Swift... I imagine that in general it's some king of Stockholm-syndrome we developers experience :P)
  - deleted 7y ago
    [deleted]
  - MiroF 7y ago
    > "classic, conservative" Very odd to see these words used in conjunction with a modern language like Swift.
  - dnautics 7y ago
    > classic single-dispatchy languages like Swift Is C++ not classic enough these days?
    - madhadron 7y ago
targonca 7y ago
So now everyone's pet project gets a language extension in Swift? Apple extended the language with @_functionBuilder for SwiftUI. Now Google wants to extend it with this differentiable stuff for TensorFlow. Why won't they implement proper metaprogramming support instead of proliferating the core language?
- classified 7y ago
  > Why won't they implement proper metaprogramming support instead of proliferating the core language? Proper metaprogramming support is hard. Polluting the language with special case hocus pocus is relatively easy.
  - marmaduke 7y ago
    > Polluting the language with special case hocus pocus is relatively easy or if it's well done is it still hocus pocus pollution?
    - classified 7y ago
      Then it's pollution with compiler magic. But only if it's really well done.
fuklief 7y ago
Meanwhile, Google researchers (Plotkin and Abadi) are going to present "A Simple Differentiable Programming Language" at POPL20[1] in January. I can't find a preprint though :'( [1]: https://popl20.sigplan.org/track/POPL-2020-Research-Papers#event-overview https://popl20.sigplan.org/track/POPL-2020-Research-Papers#e...
- ml_thoughts 7y ago
  Went up this morning on arXiv: https://arxiv.org/abs/1911.04523 https://arxiv.org/abs/1911.04523
jpz 7y ago
Does anyone else dislike the usage of the word "manifesto" in computing? It always seems to me to indicate a faith-based rather than evidence-based commitment to some train of thought. Seems strange to see manifestos discussed in the ML space, which is nominally a measure-oriented world. Mind you, when has statistics not been polemical.
- new2628 7y ago
  My experience is that evidence-based commitments are overrated and are usually a post-hoc rationalization for faith- (or gut-feeling)-based ones.
nuclx 7y ago
Striving for concise syntax for mathematical operations is a noble intention, but it's hardly a good idea achieve that by shoehorning changes into an existing language. A language framework designed for extensibility has to be the basis allowing for the implementation of concepts such as differential or probabilistic programming, and it's not Haskell, i.e. we're not there yet.
- byt143 7y ago
  Julia,'s source to source autodiff is implemented as a custom compiler pass in a third party package. Similar approached are bring taken by prob programming packages.
mratsim 7y ago
So the software is improving by leaps and bounds but where is the hardware? OpenCL --> deprecated Cuda --> No Nvidia GPU ROCm/HIP: does it work on Mac or are you strong-armed into using Apple Metal? Metal --> I couldn't find an AXPY example
keithalewis 7y ago
There is a simpler way to do this; https://github.com/keithalewis/epsilon/blob/master/README.md https://github.com/keithalewis/epsilon/blob/master/README.md.
bcheung 7y ago
Pardon my ignorance but I have a few questions... 1) This seems like it would only work for varying the values passed to variables in a function. Can you differential a function other than just changing some values -- like using a genetic algorithm. Seems like this is just finding the right values to pass to a function not finding a different function itself. 2) Is this limited to only continuous / ordered values? How can you differentiate logic, branching, and what other functions to call? Seems like to do so would require mapping a function to some kind of n-dimensional euclidian space / manifold. 3) Why does this need to be an extension to a language? Can't ordinary interfaces in the OOP sense or monads in the FP sense be used to wrap functions and give them this functionality for free?
- ddragon 7y ago
  1) It's not restricted to the variables being passed, for example Zygote [1] has an example in the README with IO gradient(x -> fs[readline()](x), 1), and it's not using numerical differentiation (varying inputs to check the output), but finding a formula (approximate, not a closed form like a symbolic differentiation) of how changing the output affects the input. Genetic algorithms is a black box metaheuristic, so people would favor using gradient descent given that the code is differentiable, but how the model is optimized is technically open to any method. 2) Yes, it can differentiate all control flow. What happens is that each forward/backward pass will have a different graph based on what branches it would follow (effectively a subderivative). Each one of these graphs is independently differentiable and do not contain the control flow by themselves. 3) It doesn't need a language extension (Julia doesn't, but that's because you can access Julia IR using the language itself, not many language support this level of metaprogramming). The OOP strategy (like Pytorch) overload methods so every time you call the overloaded method it builds the graph. It depends on customized types and methods and does not support code that isn't using those custom types that can hold the graph (native/custom types), native control flow (only implicitly by changing what graph is being created), reduces the possible optimizations (you only have one subderivative, not the complete graph to optimize) and end up creating a DSL with it's own error messages and quirks that is less natural than just using the host language. I can't say how it would look using monads though. [1] https://github.com/FluxML/Zygote.jl https://github.com/FluxML/Zygote.jl
Nelkins 7y ago
I was recently looking at a library in F# that does something similar: https://diffsharp.github.io/DiffSharp/ https://diffsharp.github.io/DiffSharp/ Also related: https://github.com/fsprojects/fsharp-ai-tools https://github.com/fsprojects/fsharp-ai-tools

180 points by kristianp 7y ago

This looks like it's going to be a really big deal unless they totally fuck it up. Autodiff greatly simplifies all kinds of continuous mathematical optimization algorithms, and using mathematical optimization means you only have to write code that can recognize things that look similar to a solution instead of code that can find the solution — in a sense, mathematical optimization derives your code from tests. Autodiff is useful for other kinds of things too, not just mathematical optimization, as they mention in the manifesto. This weekend I wrote a real-time SDF raymarcher in a page of Lua (https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.png https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.png https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.lua https://gitlab.com/kragen/bubbleos/blob/master/yeso/sdf.lua), but the surface shading is pretty lame because without sampling the SDF multiple times it doesn't yet have any way to calculate surface normals. Guess what a surface normal is? It's the gradient of the SDF, and reverse-mode autodiff can sample the SDF and its gradient in only double the time of just sampling the SDF. Pretty much anything you do in continuous domains can get simpler and/or better-performing with autodiff. This is why I've written so much about it in Dercuano. It's worth pointing out that you don't need to redesign your language to get first-class differentiable programming. Source-to-source transformation has been used to do autodiff in FORTRAN for at least ten years, including on pretty massive applications. (This is mentioned in the manifesto.)

seanmcdirmid 7y ago
Conal Elliott (the guy who co-invented FRP) did a nice project on shading computational surfaces by extracting derivatives from code more than a decade ago: http://conal.net/Vertigo/ http://conal.net/Vertigo/ He is now very active in the differentiable programming community, but he got started on the problem in the graphics field.
- noblethrasher 7y ago
  He also gave nice presentation on AD: https://www.youtube.com/watch?v=ne99laPUxN4 https://www.youtube.com/watch?v=ne99laPUxN4 (surprised that you didn't already mention it, considering the venue ;-))
- kragen 7y ago
  The manifesto links one of his papers, "The simple essence", which I've started but haven't finished.
  - seanmcdirmid 7y ago
    He has been working on that for a long time. Though much of his earlier work is symbolic differentiation, I’m not very familiar with the more recent AD stuff.
  - thechao 7y ago
    Let me mostly summarize Conal’s “simple” reverse AD: he drops the tape into the stack. This has two impacts: the stack is “about twice as long”; and, you “may (will?) lose tail recursion”. It is still a really good paper—and no doubt a lot of the subtlety was list to me.
sitkack 7y ago
AD also has a nice synergy with DNN, the whole formalization allows for moving the runtime into a DNN and thus onto a GPU. I have been looking for a technique for representing algorithms that are amenable to conversion to anytime [1] I believe AD could be that technique. [1] https://en.wikipedia.org/wiki/Anytime_algorithm https://en.wikipedia.org/wiki/Anytime_algorithm
- kragen 7y ago
  Well, successive-approximation mathematical optimization algorithms are sort of inherently anytime, in a way: you can stop after any integer number of iterations and use the approximate solution. Some of them fail to be anytime in practice, like SOR (“successive over-relaxation”) where you usually quit after like six iterations but each iteration takes a long time. And autodiff makes it a lot easier to apply mathematical optimization, in particular variants of gradient descent, one popular use of which is training deep ANNs. Is that what you meant, or are you talking about something else?
  - sitkack 7y ago
    This is it. I think AD can be used to train a DNN, the DNN in turn can be used to power an anytime algorithm such that you can have systems that can not only respond on different time scales, they are also robust in the face of sensor noise, adversarial sensors or broken actuators.

dual_basis 7y ago

I like differentiable programming a lot, but can anyone explain the motivation for Swift as their language of choice for this? I assume it was simply because they wanted to get Chris Lattner, and Swift was his baby. Julia seems like a much better target for this, I wish they had just dedicated some money or resources to that. I don't have a problem with Swift's language design per-se (although Julia's dynamic nature really lends itself more naturally to the sort of problems you might be trying to solve using differential programming, in my opinion) but its cross-platform support is terrible. Why would you choose Mac's boutique language as the foundation of your new paradigm?

nnq 7y ago
> Julia seems like a much better target for this Exactly, at least from an outside perspective, why tf?! It seems like people love so much bolting stuff to "classic, conservative" languages that they do it even if it's 10x more work than doing it in a language already having full fledged mature real macros. And this is not Common Lisp we're talking about... Julia is a pretty "normal" language that wouldn't scare anyone off! (EDIT+: though, as a software engineer primarily, I do have a slight personal preference for more classic single-dispatchy languages like Swift... I imagine that in general it's some king of Stockholm-syndrome we developers experience :P)
- deleted 7y ago
  [deleted]
- MiroF 7y ago
  > "classic, conservative" Very odd to see these words used in conjunction with a modern language like Swift.
- dnautics 7y ago
  > classic single-dispatchy languages like Swift Is C++ not classic enough these days?
  - madhadron 7y ago

targonca 7y ago

So now everyone's pet project gets a language extension in Swift? Apple extended the language with @_functionBuilder for SwiftUI. Now Google wants to extend it with this differentiable stuff for TensorFlow. Why won't they implement proper metaprogramming support instead of proliferating the core language?

classified 7y ago
> Why won't they implement proper metaprogramming support instead of proliferating the core language? Proper metaprogramming support is hard. Polluting the language with special case hocus pocus is relatively easy.
- marmaduke 7y ago
  > Polluting the language with special case hocus pocus is relatively easy or if it's well done is it still hocus pocus pollution?
  - classified 7y ago
    Then it's pollution with compiler magic. But only if it's really well done.

fuklief 7y ago

Meanwhile, Google researchers (Plotkin and Abadi) are going to present "A Simple Differentiable Programming Language" at POPL20[1] in January. I can't find a preprint though :'( [1]: https://popl20.sigplan.org/track/POPL-2020-Research-Papers#event-overview https://popl20.sigplan.org/track/POPL-2020-Research-Papers#e...

ml_thoughts 7y ago
Went up this morning on arXiv: https://arxiv.org/abs/1911.04523 https://arxiv.org/abs/1911.04523

jpz 7y ago

Does anyone else dislike the usage of the word "manifesto" in computing? It always seems to me to indicate a faith-based rather than evidence-based commitment to some train of thought. Seems strange to see manifestos discussed in the ML space, which is nominally a measure-oriented world. Mind you, when has statistics not been polemical.

new2628 7y ago
My experience is that evidence-based commitments are overrated and are usually a post-hoc rationalization for faith- (or gut-feeling)-based ones.

nuclx 7y ago

Striving for concise syntax for mathematical operations is a noble intention, but it's hardly a good idea achieve that by shoehorning changes into an existing language. A language framework designed for extensibility has to be the basis allowing for the implementation of concepts such as differential or probabilistic programming, and it's not Haskell, i.e. we're not there yet.

byt143 7y ago
Julia,'s source to source autodiff is implemented as a custom compiler pass in a third party package. Similar approached are bring taken by prob programming packages.

mratsim 7y ago

So the software is improving by leaps and bounds but where is the hardware? OpenCL --> deprecated Cuda --> No Nvidia GPU ROCm/HIP: does it work on Mac or are you strong-armed into using Apple Metal? Metal --> I couldn't find an AXPY example

keithalewis 7y ago

There is a simpler way to do this; https://github.com/keithalewis/epsilon/blob/master/README.md https://github.com/keithalewis/epsilon/blob/master/README.md.

bcheung 7y ago

Pardon my ignorance but I have a few questions... 1) This seems like it would only work for varying the values passed to variables in a function. Can you differential a function other than just changing some values -- like using a genetic algorithm. Seems like this is just finding the right values to pass to a function not finding a different function itself. 2) Is this limited to only continuous / ordered values? How can you differentiate logic, branching, and what other functions to call? Seems like to do so would require mapping a function to some kind of n-dimensional euclidian space / manifold. 3) Why does this need to be an extension to a language? Can't ordinary interfaces in the OOP sense or monads in the FP sense be used to wrap functions and give them this functionality for free?

ddragon 7y ago
1) It's not restricted to the variables being passed, for example Zygote [1] has an example in the README with IO gradient(x -> fs[readline()](x), 1), and it's not using numerical differentiation (varying inputs to check the output), but finding a formula (approximate, not a closed form like a symbolic differentiation) of how changing the output affects the input. Genetic algorithms is a black box metaheuristic, so people would favor using gradient descent given that the code is differentiable, but how the model is optimized is technically open to any method. 2) Yes, it can differentiate all control flow. What happens is that each forward/backward pass will have a different graph based on what branches it would follow (effectively a subderivative). Each one of these graphs is independently differentiable and do not contain the control flow by themselves. 3) It doesn't need a language extension (Julia doesn't, but that's because you can access Julia IR using the language itself, not many language support this level of metaprogramming). The OOP strategy (like Pytorch) overload methods so every time you call the overloaded method it builds the graph. It depends on customized types and methods and does not support code that isn't using those custom types that can hold the graph (native/custom types), native control flow (only implicitly by changing what graph is being created), reduces the possible optimizations (you only have one subderivative, not the complete graph to optimize) and end up creating a DSL with it's own error messages and quirks that is less natural than just using the host language. I can't say how it would look using monads though. [1] https://github.com/FluxML/Zygote.jl https://github.com/FluxML/Zygote.jl

Nelkins 7y ago

I was recently looking at a library in F# that does something similar: https://diffsharp.github.io/DiffSharp/ https://diffsharp.github.io/DiffSharp/ Also related: https://github.com/fsprojects/fsharp-ai-tools https://github.com/fsprojects/fsharp-ai-tools