Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Differentiable Programming Mega-Proposal

forums.swift.org

Post reply on HN
Print view View original

71–78 of 78 posts

Re: Differentiable Programming Mega-Proposal

#71

Post by aylmao »

abeppu wrote: post #44
aylmao wrote: post #34

Earlier quoted context omitted.

From the proposal: > 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 langua…

I still don't get it. Why can't I use a debugger to step through derivatives when autodiff is implemented as a library?

I think it's mostly due to a couple of reasons:

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 ¯\_(ツ)_/¯.

Re: Differentiable Programming Mega-Proposal

#72

Post by neilparikh »

joe_the_user wrote: post #55
chillee wrote: post #31

Earlier quoted context omitted.

If statements aren't really meaningfully differentiable, regardless of how you do it. Take if x == 59: return 1000 else if x > 59: return -x else: return x How do you optimize this to maximize x, regardless of what language you're in? It's true that you can get a derivative, but the derivative is essentially meaningless.

Yeah, Automatic differentiation is essentially only usable on functions specified the way mathematicians specify functions; the compositions of a series of primitives (plus operators like the integral and the differential itself, as well inverse relations). 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…

AD on loops/recursion works fine when you implement it using dual numbers (see for https://news.ycombinator.com/item?id=20893414 an example). If you used this to implement x^n using a for loop, you would get the correct derivative (n * x ^ (n - 1)).

Re: Differentiable Programming Mega-Proposal

#73

Post by JustFinishedBSG »

wenc wrote: post #13

I'm curious (for folks in the know): how does differentiable programming handle non-differentiable points? Can it detect non-differentiable/non-smooth functions? 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 i…

> on-smooth functions like abs(), max(), min() where derivatives do not exist

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.

https://en.wikipedia.org/wiki/Subderivative

Re: Differentiable Programming Mega-Proposal

#74

Post by joe_the_user »

excessive wrote: post #51
seanmcdirmid wrote: post #45

Earlier quoted context omitted.

You can easily use expressions to create trees rather than values in a library. Eg a + b need not compute a value, through a bit of operating overloading it can compute the tree plus(tree-a, tree-b). 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…

Building expression trees is not the only way to do automatic differentiation. A simpler way is to just carry the value and it's derivative as a pair: #include #include 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.…

This only works if you don't have x as a value determining the length of the for loop. If you try to take the derivative of x^x using a loop multiplying x times, you'll get a wrong answer (admittedly, expecting a right answer would be foolish).

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.

Re: Differentiable Programming Mega-Proposal

#75

Post by excessive »

joe_the_user wrote: post #74
excessive wrote: post #51

Earlier quoted context omitted.

Building expression trees is not the only way to do automatic differentiation. A simpler way is to just carry the value and it's derivative as a pair: #include #include 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.…

This only works if you don't have x as a value determining the length of the for loop. If you try to take the derivative of x^x using a loop multiplying x times, you'll get a wrong answer (admittedly, expecting a right answer would be foolish). 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 languag…

That's a fair point (and worth documenting as part of the library), but I'd be much more likely to implement pow(x, x) carefully than switch to a different language or compiler.

Re: Differentiable Programming Mega-Proposal

#76

Post by joe_the_user »

excessive wrote: post #75
joe_the_user wrote: post #74

Earlier quoted context omitted.

This only works if you don't have x as a value determining the length of the for loop. If you try to take the derivative of x^x using a loop multiplying x times, you'll get a wrong answer (admittedly, expecting a right answer would be foolish). 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 languag…

That's a fair point (and worth documenting as part of the library), but I'd be much more likely to implement pow(x, x) carefully than switch to a different language or compiler.

I appreciate the library approach and I basically agree with you. If anything, I wanted to point out that a normal general language is so general that adding differentiation into it would be highly costly - just this feature would require that every loop and every conditional return be watched (relative to pow(x,x), an even more challenging example is the Newton's method implementation of a continuous function using a loop).

An alternative would be creating a general purpose language just for this feature - an interesting though rather specialized project.

Re: Differentiable Programming Mega-Proposal

#77

Post by excessive »

joe_the_user wrote: post #76
excessive wrote: post #75

Earlier quoted context omitted.

That's a fair point (and worth documenting as part of the library), but I'd be much more likely to implement pow(x, x) carefully than switch to a different language or compiler.

I appreciate the library approach and I basically agree with you. If anything, I wanted to point out that a normal general language is so general that adding differentiation into it would be highly costly - just this feature would require that every loop and every conditional return be watched (relative to pow(x,x), an even more challenging example is the Newton's method implementation of a continuous function using…

I'm not certain, but I suspect you'll hit the halting problem if you tried to be completely general purpose.

Re: Differentiable Programming Mega-Proposal

#78

Post by andrekandre »

optevo wrote: post #36
hsaliak wrote: post #14

How does this compare to Jax? https://github.com/google/jax Why do this in the language instead of a library?

If you were targeting a Lisp you could do this as a (macro) library

that’s basically the conversation that is being had in the linked thread:

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

Post reply on HN