Differentiable Programming from Scratch
thenumb.at
Differentiable Programming from Scratch
1–10 of 22 posts
Re: Differentiable Programming from Scratch
#2"Now that we understand differentiation, let’s move on to programming. So far, we’ve only considered mathematical functions, but we can easily translate our perspective to programs. For simplicity, we’ll only consider pure functions, i.e. functions whose output depends solely on
its parameters (no state)."
I think I've seen this notion that the constraint is pureness also in documentation of autodiff libraries, but this cannot be strong enough, right?
It easy enough to come up with functions that are nowhere differentiable. So my question is, what are the actual requirements a state of the art autodiff library has for the input function and why do people focus on the pureness aspect if that is probably the least of the problems.
Re: Differentiable Programming from Scratch
#3"Now that we understand differentiation, let’s move on to programming. So far, we’ve only considered mathematical functions, but we can easily translate our perspective to programs. For simplicity, we’ll only consider pure functions, i.e. functions whose output depends solely on its parameters (no state)." I think I've seen this notion that the constraint is pureness also in documentation of autodiff libraries, but t…
If the function is pure, autodiff can produce a result. If the function is not differentiable for a given input, the result produced by autodiff of course cannot be the derivative (since none exists) but it could be another number (e.g. a subderivative) that is useful in some of the ways a derivative would have been useful.
Re: Differentiable Programming from Scratch
#4Historical fact: Differentiable programming was a little known secret back in the 90's, used mainly by engineers simulating numerically stiff systems like nukes and chemicals in FORTRAN 95. It then disappeared for nearly 30 yrs before rediscovery by the ML/AI researchers!
Re: Differentiable Programming from Scratch
#5I’m not deep into autodiff (just recall some calculus from university), but the syntax in this post reminds me a lot of ML (the programming language, not machine learning)
I know autodiff isn’t lambda calculus, but the expression-based structure and evaluation rules feel similar. Couldn’t this be implemented in something like ML or Clojure? Just wondering what the custom DSL adds that existing functional languages wouldn’t already support
Re: Differentiable Programming from Scratch
#6"Now that we understand differentiation, let’s move on to programming. So far, we’ve only considered mathematical functions, but we can easily translate our perspective to programs. For simplicity, we’ll only consider pure functions, i.e. functions whose output depends solely on its parameters (no state)." I think I've seen this notion that the constraint is pureness also in documentation of autodiff libraries, but t…
State is just values which are not considered to be variable function inputs - in other words each time you change state you have new functions.
For example f(x, y) = xy and then defining a differentiable function g(x) = f(x, a). You can imagine “a” being a state variable.
Re: Differentiable Programming from Scratch
#7I’m not deep into autodiff (just recall some calculus from university), but the syntax in this post reminds me a lot of ML (the programming language, not machine learning) I know autodiff isn’t lambda calculus, but the expression-based structure and evaluation rules feel similar. Couldn’t this be implemented in something like ML or Clojure? Just wondering what the custom DSL adds that existing functional languages wo…
There is an F# implementation (Microsoft flavoured ML) called DiffSharp
Re: Differentiable Programming from Scratch
#8I’m not deep into autodiff (just recall some calculus from university), but the syntax in this post reminds me a lot of ML (the programming language, not machine learning) I know autodiff isn’t lambda calculus, but the expression-based structure and evaluation rules feel similar. Couldn’t this be implemented in something like ML or Clojure? Just wondering what the custom DSL adds that existing functional languages wo…
I didn't see a DSL anywhere, just normal JS code.
As to what it adds?
- It's more accessible to a wider audience (and looks like how you'd implement autodiff in most languages)
- It runs in the browser trivially (powering those demos)
- The author (potentially) didn't have to learn a new language just to get started
- Programs are not fully differentiable, or at the very least there are some crazy edge cases and dragons lurking if you attempt to make them so. A dedicated whitelist of supported operations isn't necessarily a bad design, contrasted with an implicit whitelist in Clojure (depending on the implementation of course, but there wasn't a lot of source-to-source boilerplate even in this example, so I assume the benefit of a functional language would be stripping away some of the characteristics I think are important).
Re: Differentiable Programming from Scratch
#9"Now that we understand differentiation, let’s move on to programming. So far, we’ve only considered mathematical functions, but we can easily translate our perspective to programs. For simplicity, we’ll only consider pure functions, i.e. functions whose output depends solely on its parameters (no state)." I think I've seen this notion that the constraint is pureness also in documentation of autodiff libraries, but t…
Purity, interestingly, is not a requirement. You can represent any closure as something implicitly captured, and you can represent mutable state as an immutable input with a different, related, immutable output. For any autodiff library not also throwing in dense+sparse decompositions (none of the major ones do any such optimization; the programmer has to manually choose which things to represent how), that doesn't even waste any more space for reverse-mode autodiff than your other options (i.e., you need to maintain the before and after state anyway, give or take your particular checkpointing scheme, and if you don't have a way to represent the delta cheaply then contrasted with the underlying mutable forward pass which probably was faster and cheaper than the alternatives, the differentiation is probably quite expensive). Purity is often easier to code around, especially in "complicated" languages with many features you'd like to support, but it's not mandatory.
In terms of actual requirements, something that's sufficient [0] is for every sub-component to be differentiable and for no dynamic control flow to depend on the things being differentiated. In practice, most libraries wind up requiring something like this, mostly because it's very hard to do anything else. As an example, define f(x) := 0 for floats with an even LSB and 1 for floats with an odd LSB. Define g(x) := 1 - f(x). Neither of these are meaningfully differentiable, but g(x) + f(x) is identically equal to one. Autodiff relies crucially on the fact that it can perform local transformations, and that sort of whole-program analysis is (a) impossible in general, and (b) hard even when it's possible.
For local-only autodiff (the only thing people ever do), the thing that's necessary is for every sub-component to have a derivative-like operator defined such that if the sub-components are composed into a differentiable function then the normal chain rule and other autodiff compositions of those operators is also differentiable and represents the derivative in question (along with some requirements on dynamic control flow -- they don't have to be quite as strict as I described, but it's impossible to relax in general that with local-only autodiff, so that dynamic requirement from the above paragraph is also necessary).
There are few (zero?) components where that's possible -- an adversary can always come up with a composition violating the derivative being incorrect. However, for some interesting functions (like eigenvalues and eigenvectors) in the normal way people use them, these sorts of things can be defined. E.g., the eigenvalue derivative is not unique (up to a choice of phase), but if your composition also doesn't depend on phase then you're still fine.
[0] Even for things like differentiating through a loop converging to a value, this property holds, with one meaningful exception: The error in the derivative compared with the true function you're approximating will still converge to zero with enough iterations, but that number can be much higher than you need to get the function itself to converge. You _will_, however, get the derivative of the approximation perfect.
Re: Differentiable Programming from Scratch
#10>Unfortunately, finite differences have a big problem: they only compute the derivative of f in one direction. If our input is very high dimensional, computing the full gradient of f becomes computationally infeasible, as we would have to evaluate f for each dimension separately.
And it is terribly unstable numerically. f(x) and f(x+h) are very similar, h is very small. You have to expect destructive cancellation to happen. For black boxes it is the only real alternative though, you can do a bit better by taking a derivative in both directions.