Demystifying Differentiable Programming (2018)

by noelwelsh • 6 years ago

110 42 6 years ago

sdenton43• 6 years ago

I dream of a day where I can write a program with some stupid thresholds/flags, run it for a while, and automatically learn better thresholds...

joe_the_user• 6 years ago

That sounds appealing. How would the program know what "better" was?

saagarjha• 6 years ago

You’d profile for the metric you cared about, like execution time or memory usage.

aaron-santos• 6 years ago

Defining a loss function comes to mind. Checkout JAX[1] or Autograd[2]. As this is essentially a different programming paradigm there are a ton of opportunities, but it is fresh enough such that there is little to no history of software engineering differentiable programs. Design patterns, rules of thumb, and standard practices have yet to be defined.

[1] https://github.com/google/jax

[2] https://github.com/HIPS/autograd

exdsq• 6 years ago

You can define ‘better’ as quantifiable metrics like execution time. Check out the use of program synthesis in compilers for a actual use case of something similar :)

hinkley2• 6 years ago

I long for a program that can “dream”: Do offline analysis of the statistics from the previous run, speculate on different settings and replay them in a sandbox to find out.

With more and more cores coming, I expect to see this sort of thing happen once we accept that we can’t really use all of them.

ignoramous• 6 years ago

Do offline analysis of the statistics from the previous run, speculate on different settings and replay them

Reminds me of Dynimize https://news.ycombinator.com/item?id=17025627

noelwelsh6• 6 years ago

From the programming language point of view, what's interesting to me is that this means, I think, that there is a differentiation monad. This arises because monads are equivalent to continuations and hence anything you can express with continuations can also be expressed as a monad.

I haven't seen this discussed before, except in the context of category theory (https://ncatlab.org/nlab/show/differentiation) I'm not sure how this ties into the programming language point of view.

edflsafoiewq3• 6 years ago

Can you unpack this a little? What exactly is the monad?

noelwelsh6• 6 years ago

If you speak Scala, here's code for reverse mode differentiation as a monad. The flatMap / bind operation becomes the the chain rule.

If this "explanation" (scare quotes because it's not really an explanation, just a code dump) doesn't work for you let me know and I can try a different approach.

  final case class AD[A](v: A, k: Double => Double) {
    // Chain rule
    def flatMap[B](f: A => AD[B]): AD[B] = {
      val self = this
      val next = f(v)
      AD(next.v, (d: Double) => next.k(d) * self.k(d))
    }

    def +(that: AD[Double])(implicit ev: A =:= Double): AD[Double] =
      AD(this.v + that.v, (d: Double) => this.k(d) + that.k(d))

    def *(that: AD[Double])(implicit ev: A =:= Double): AD[Double] =
      AD(this.v * that.v, (d: Double) => (this.k(d) * that.v) + (that.k(d) * this.v))

    def sin(implicit ev: A =:= Double): AD[Double] =
      this.flatMap(x => AD(Math.sin(x), (d) => Math.cos(x) * d))

    def gradient: Double =
      this.k(1.0)
  }
  object AD {
    def pure(x: Double): AD[Double] =
      AD(x, d => 1.0)
  }

tome8• 6 years ago

I don't find this very convincing. Continuations are well known to be completely mystifying. I wrote up what I believe to be a much simpler reverse mode AD transformation that uses only basic concepts:

http://h2.jaguarpaw.co.uk/posts/automatic-differentiation-wo...

samth• 6 years ago

Your notes, while simple, don't cover many of the things the paper does, such as binding or functions or sharing.

tome8• 6 years ago

You're right they don't cover functions. I don't understand what about binding or sharing they don't deal with though. Could you elaborate?

bjz_2• 6 years ago

Continuations are well known to be completely mystifying.

Could you elaborate on what leads you to think this?

tome8• 6 years ago

I don't believe that continuations are a corner of programming language theory that is well-loved and and well-understood by programmers at large, are they? Even amongst experienced functional programmers they seem to be thought of as rather difficult. Oleg Kiselyov has written extensively on them but his work has not been brought to the masses in the same way that his work in iteratees has.

http://okmij.org/ftp/continuations/index.html

dunefox• 6 years ago

Also this: https://2019.ecoop.org/details/ecoop-2019-papers/11/Automati... by Simon Peyton Jones

DarmokJalad1701• 6 years ago

I was able to follow till the end of Section 2.1. Was completely lost afterwards.

tiarkrompf3• 6 years ago

Co-author here - nice to see this discussed and happy to answer questions

nestorD• 6 years ago

I have not read the paper yet but, reading the abstract, the idea of using continuation to store the differentiation information is reminiscent of the technique used in Zygote[0].

Is there some parenty between the ideas ?

[0] https://arxiv.org/abs/1810.07951v4

tome8• 6 years ago

I believe Zygote's approach is based on the backpropagator of Pearlmutter and Siskind. The back propagator approach seems much simpler to me, although the authors of this paper suggest that it requires non-local program transformations

The implementation proposed by Pearlmutter and Siskind returns a pair of a value and a backpropagator ... Doing this correctly requires a non-local program transformation ... Further tweaks arerequired if a lambda uses variables from an outer scope ... In contrast to Pearlmutter and Siskind [2008], using delimited continuations enables reverse-mode AD with only local transformations. Any underlying non-local transformations are implicitly resolved by shift and reset.

I'll have to look more carefully to understand how the CPS version avoids non-local program transformations.

lidHanteyk• 6 years ago

Can any continuations work? I think that single-usage delimited continuations, as in E, are not able to implement the reverse-mode AD technique directly. This is because your continuations are called multiple times.

Thanks for this paper. Along with the string of "compiling to categories" papers, our understanding of AD has improved greatly.

Demystifying Differentiable Programming (2018)

Related Stories