Differentiable Programming Mega-Proposal
forums.swift.org
forums.swift.org
It just seems so narrow and not at the same level of abstraction that languages typically sit at. I could see the language supporting higher level functionality so a library could do this without a bunch of extra work (such as by some reflection).
I think the applications for automatic differentiation and gradient optimization well exceed what we think of as ML and data science today.
The mega-proposal links out to a separate doc on embedded DSLs, with broad statements about what's "typical" or "often" true of existing DSLs -- but which of those issues are insurmountable? That section mentions Swift's limited metaprogramming facilities. Why choose to carve out this added support for a single family of algorithms rather than add in some more general metaprogramming abilities that enable better EDSLs?
Take
if x == 59:
return 1000
else if x > 59:
return -x
else:
return x
It's true that you can get a derivative, but the derivative is essentially meaningless.
What I'm arguing is that this gradient will not allow you to optimize anything of interest for the vast majority of programs.
But the function's derivative can't be derived by an application of the chain rule and the know derivatives of primitive functions, which is what Algorithmic/automatic differentiation ultimately does (though it does this at run time, not compile time, since ordinary, symbolic differentiation explodes in memory for a complicated functions).
Also:
The continuous function
int f(int x) {
if(x > 2)
return x + x;
else
return x*2;
}
https://github.com/FluxML/Zygote.jl
julia> fs = Dict("sin" => sin, "cos" => cos, "tan" => tan);
julia> gradient(x -> fs[readline()](x), 1)
sin
0.5403023058681398 if x <= 0:
return 0
else:
return x
AD is not usable on loops, conditionals or recursive calls.
So basically, whatever way you specify your functions, you are effectively going to have DSL (within a general purpose language or otherwise) since not all the functions you form are going to be differentiable by AD (and there's some confusion between differentiable in the abstract and differentiable by the methods of AD).
Edit: actually, it's pretty easy to extend AD to functions defined piecewise on intervals to be in the class of function amenable of AD. What's hard/impossible is extending functions defined by loops or recursion.
This “trick” does not extend to statements, however. You can’t override if or semicolon in most languages. You can encode statements as expressions, but then you have to worry about things like variable bindings on your own.
#include <math.h>
#include <stdio.h>
struct autodiff { double value, deriv; };
autodiff just(double x) { return { x, 1 }; }
autodiff operator +(autodiff a, autodiff b) {
return { a.value + b.value, a.deriv + b.deriv };
}
autodiff operator *(autodiff a, autodiff b) {
return { a.value * b.value, a.deriv*b.value + a.value*b.deriv };
}
autodiff sin(autodiff a) {
return { sin(a.value), cos(a.value)*a.deriv };
}
int main() {
autodiff x = just(.1);
for (int ii = 0; ii<4; ii++) {
x = x*x + sin(x);
}
printf("value: %lf, deriv: %lf\n", x.value, x.deriv);
return 0;
}
This generalizes to partial derivatives for multivariate functions too:
template<int dims>
struct autograd { double value, grad[dims}; };But this goes to question at hand, whether AD should be a library/DSL or whether it should be a primitive of a general purpose language. The thing is a general purpose language lets you present sorts of things as functions that can't be even dual numbers won't take the derivative of correctly - a dual scheme can't distinguish variable order loops from constant order loops.
An alternative would be creating a general purpose language just for this feature - an interesting though rather specialized project.
> While the differentiation APIs are flexible and fully dynamic, differentiation is based on a program transformation that happens at compile-time. This enables many static analyses that not only help produce more efficient programs, but also detect common numerical programming mistakes such as non-differentiable functions and zero derivatives.
> With a first-class differentiable programming language, some of the most common runtime errors in machine learning become directly debuggable without library boundaries. Simply step through backpropagation using LLDB to debug derivatives.
You can do this with a library by implementing "number" types that, as a side effect of arithmetic operations, record those operations onto a "tape", so that corresponding (different) operations can be played back later in reverse order.
Unfortunately, those side effects have a cost during the forward pass. And during the backwards pass you are essentially running a little interpreter to execute your instructions.
Putting this stuff into the compiler lets the forward pass just be normal, native code on doubles/floats, and the same for the reverse-pass code. Moreover, all of this can now be worked on by the optimizing compiler.
This is especially important for embedded applications where you can't afford all this interpretation.
I guess the original TensorFlow "computation graph" approach is a little different to the "tape" I described because the graph is built explicitly rather than through side effects, but that just makes even more clear that you're really assembling an AST for some /other/ language and (when not using XLA) running an interpreter.
In principle some suitably powerful macro language with full access to the AST might be able to do good compile-time reverse-mode AD, but I am not aware of any language with powerful enough macros. Again, this is because the transformation is not just a local pattern replacement; it involves flipping the code upside down.
What's funny is that physicists have been able to do this kind of program transformation in a slightly clunky(?) way -- FORTRAN in, FORTRAN out -- since the 70s, supposedly.
It all makes me think that our ideas about what a "language" is, what a "compiler" is, what a "library" is, are all stuck in convention and prematurely ossified. The first compilers, which we celebrate, looked to their users like codegen (which we detest, I think)! I would love for the boundary between "language" and "compiler" to be broken down more so that AD could be more easily done "within the language"; maybe one day that will happen in Julia, or Nim, or Jai, or Terra.
But for now I think I agree with the designers that the best hope for good results, and really the most straightforward way, is to just do it in the compiler.
Works with typed IR equivalent to a core compiler pass but from a third party package with regular Julia staged programming.
[1] http://blog.rogerluo.me/2019/07/27/yassad/
[2] https://docs.julialang.org/en/v1/manual/metaprogramming/inde...
[3] https://mikeinnes.github.io/IRTools.jl/latest/#Evaluating-IR...
1. The debugging experience is probably better. Computing a derivative can be complex— you might be seeing a high value where you were expecting a low one, and you want to "step through the equation and how it changes. Having to do that when "the equation" is a bunch of obscure data structures, through the internal representation of functions in 3-rd party library could get very complex very quickly.
2. You might not catch non-differentiable functions and zero derivatives. Moreover, given just the nature of math, you could see millions of inputs that wouldn't trigger an exception, ship your model, and then one day the one that yields a 0 shows up, your model crashes, and you don't know why. Having the compiler essentially act as proof that something will _never_ be zero is awesome for correctness and reliability.
If you think about it, derivatives aren't really an operation "through" the equation, but "on" the equation. You're writing some function, but instead of passing a value through it, you're changing the function itself.
So the functions are the values, and need to be changed, morphed, combined, split, etc. If a library wanted to do this, my guess is either:
a) devx would suffer since wouldn't be writing functions normally, but rather defining them as objects with verbose constructors, etc.
b) for the sake of devx, the library would have to do some hacky introspection and jump hoops to get to work on the functions themselves, not with them, at the cost of performance or debuggability.
There's already software we use all the time that takes these functions, breaks them apart, understands them and does things with them though— the compiler. It transforms functions to machine code. Let's have it add a step in the middle there, and if a function is marked as being derived, let's have the compiler take it, transform it to its derivative, and then to machine code ¯\_(ツ)_/¯.
> of algorithms rather than add in some more general
> metaprogramming abilities that enable better EDSLs?
It is The Swift Way™
The answer is always to add something to the language and the compiler, the question seems to be largely irrelevant.
Of course, that's a consequence of not heeding Alan Kay's advice from 1998, that when you design a new language, you need to focus on the metasystem first, the rest will follow.
http://wiki.c2.com/?AlanKayOnMessaging
When you don't do that, every new requirement comes as a surprise that you need to hack into the compiler somehow. Objective-C compatibility: hack the language; Python integration: hack the language; SwiftUI: hack the language; Differentiable Programming: hack the language.
And of course, each additional hack makes the already not-to-elegant base language even more difficult for implementing stuff without hacking the language.
What kind of a metasystem would we need in order to not have to hack the language for all of these features? That, detective, is the right question!
You can find out more on the mailing list https://groups.google.com/a/tensorflow.org/forum/m/#!forum/s...
Is this... a separate, parallel, more encompassing proposal?
Is there any coordination between these two groups?
--
Moreover, a statically typed language like Swift is a much better starting point for this kind of effort than Python. Array shapes and dimensions are already a type system - you might as well go the whole distance and get all the other safety, readability, and efficiency benefits!
PS shout out for named array axes as the future of array-based (and hence differentiable) programming... see http://nlp.seas.harvard.edu/NamedTensor for a good rationale
The fact that you can jit compile and gain the benefits of "doing this within the compiler" is one of its main selling points.
should this be done as a special case in the compiler
or
shouldn’t this be a more general meta programming based feature
with those in favor of meta-programming also bringing up the potential complexity/speed loss added to the compiler for this feature
the problem for swift is, there hasn’t been a coherent meta-programming story (something like a meta-programming mega proposal) so it seems hard to push for that instead right now....
In his excellent interview with Lex Fridman, Yann LeCun was critical of any approach to AI that was not differentiable, even constraint satisfaction, and other solid optimization techniques. In the context of scaling to very large problems or models with many billions of parameters, he is probably correct.
I have had problems with the Swift and TensorFlow code drops. Sometimes they work for me and sometime they don’t. So, very good technology but perhaps wait for it to mature. I read that some students for the fast.ai course using Swift have also had some setup difficulties.
EDIT: you might also want to look at Julia for differentiable programming and Julia with deep learning libraries like Flux is also a ‘turtles all the way down’ system, where unlike TensorFlow where the guts are implemented in C++, for Swift and Julia the entire stack can be implemented in a single language.
This may let them capture a large chunk of the ML market from Python - and hopefully greatly improve ML apis while they're at it.
I'll get excited if Apple actually merges this into Swift. It's a niche feature that their compiler team will need to maintain forever. I actually have been working on algorithmic differentiation in C++, so it's not even that I wouldn't want to try Swift out if it actually made it in. However, because this sort of thing is of such narrow interest I believe the future will stay with embedded DSLs / libraries / ugly macro/template hackery.
Probably Conal Elliott’s work, eg in Vertigo (http://conal.net/Vertigo/, circa 2005)? There he was using it for normal computations used in pixel shading, pretty cool stuff. He is still active in this field, and has a lot of new papers that are more ML focused. I do wonder if “general” AD support will be useful for computer graphics as well as ML?
Non-smooth functions like abs(), max(), min() have points where derivatives do not exist. ReLU functions are non-differentiable at their hinge points.
Disjoint IF-THEN-ELSE conditions are discontinuities in the function space, and are traditionally handled in optimization with mixed-integer formulations (i.e. split up the space and do something clever like branch-and-bound to find the optimum).
But "networks" here, you're thinking of ANNs, yes?
But in the context of proposing differential programming as an addition to a general purpose language (and where the proposal explicitly brings up a bunch of cases outside of deep learning), is it fair to justify behavior based on what makes sense in a popular but narrow application?
For sensitivity analysis it might be disastrous to conclude that an output is sensitive to an input when it is actually not, merely because an intermediary ReLU hit 0, for example.
A conservative approach could be to define versions of the relevant functions that threw exceptions at such points, or that also calculated the trusted margin of the resulting gradients; non-differentiability would then produce a zero trust margin.
It's true that once you have control flow, the gradient quickly becomes meaningless. I posted an example here: https://news.ycombinator.com/item?id=20892287
That's also the biggest reason I tend to find much of this "differentiable programming" stuff to be overhyped. It's hard to reformulate programs in a way s.t. the derivative can mean something meaningful. And I'm not convinced traditional languages will benefit.
That's not to say that there isn't cases where your program can be formulated to have a meaningful derivative.
See this differentiable ray tracer: https://people.csail.mit.edu/tzumao/diffrt/
Really? The gradients computed by AD are the exact answer to the following question: if I were to change this input or parameter an infinitesimal amount, how much would it change the output of my function? That is always meaningful (when it is defined), and means what I just said. You can easily make functions where it is not defined, of course, just like you can make a sphere into two spheres with the Banach-Tarski theorem!
But there are vast, vast forests of numerical computation employed in industry, science, finance, engineering, where it is almost always defined.
And even for more “chunky” computations where the non-differentiability is more severe, there are algorithms like REINFORCE that you can use to estimate gradients through these parts.
For example, take this code.
x,y
for (int i=0; i<x; i++)
y += 1
return y
I believe REINFORCE is not of much help either - it's not magic. I'm not aware of any stochastic gradient estimators that are helpful in this case (although if there is a method I'd like to hear about it).
While these functions are not differentiable they are sub-differentiable. Which is an extension of differentiability.
Subderivatives are set, if the set only contain one point the function is differentiable. Otherwise it doesn't matter for gradient descent you can just use any element of the set.
> Disjoint IF-THEN-ELSE conditions are discontinuities in the function space
Same, it doesn't matter, they mathematically are equivalent to indicator functions and are subdifferentiable.
Also, from the GP’s thought about applications beyond DL, my favorite examples so far are for model-based RL [1] and Neural ODEs [2]