4 ms·

Operational Calculus for Differentiable Programming

64 points by bmc7505 8y ago

whatshisface 8y ago
One thing that is not entirely clear to me about constructions like these is the behavior of array indexing. I understand how to differentiate the assignment of x+y into the variable z, but if I use X as an index into memory and then write Y at that location, the proper result of differentiation looks a lot less clear. One reason for that is my memory locations are discrete points, but X must be treated as if it was continuous, if functions over it are to be differentiable.
- radarsat1 8y ago
  My understanding is that the trick to differentiable key-value stores is to treat the key as a probability over locations, and to treat the value as a weighted sum using these probabilities. From (pdf) https://aclweb.org/anthology/D16-1147 https://aclweb.org/anthology/D16-1147
- choeger 8y ago
  Intuitively you only use the value of X in that case, not the derivative. I don't know if that yields a consistent or useful language, though, since you'd also need to consider the reverse operation. In general I think that languages that need such a calculus (Modelica's functions come to mind) would show a lot of such complications when implements a rigorous description of the semantics.
- hjorthjort 8y ago
  From page 2: "The presented theoretical model enables analytic investigations of differentiable programs through algebraic tools [...]; i.e. the presented operators can take the same role as higher order functions in functional programming." So maybe we should think more in terms of lambda calculus and pure functional programming? There, you don't really write Y to memory location X. In section 5.5 they describe how they "generalize the notion of an iteration from the integers, n ∈ N, to the reals, x ∈ R, and consider fractional iterations."
amuresan 8y ago
Could someone with a better understanding of the topic give a brief example of how this can be used in practice?
- ivan_ah 8y ago
  This is a theory paper so no immediate practical applications. Potential applications would be generalizing derivative calculations used in currently ML libraries, see https://en.wikipedia.org/wiki/Automatic_differentiation https://en.wikipedia.org/wiki/Automatic_differentiation and http://www.cs.nuim.ie/~gunes/files/Baydin-MSR-Slides-20160201.pdf#page=6 http://www.cs.nuim.ie/~gunes/files/Baydin-MSR-Slides-2016020... Useful quote from paper: "We have been inspired by the development of differentiable programming to formalize a theoretical model, that encompasses the ideas underlying differentiable programming and provides a more general setting for investigations of differentiable programs. The presented theoretical model enables analytic investigations of differentiable programs through algebraic tools, that are closer to the field of programming; i.e. the presented operators can take the same role as higher order functions in functional programming."
- Someone 8y ago
  Let’s say you wrote a function f(x) and want to know where it is zero. The traditional way is Newton’s method (https://en.wikipedia.org/wiki/Newton's_method https://en.wikipedia.org/wiki/Newton's_method) That requires you to compute f’(x) at various points. You could either pick some small epsilon and approximate it as (f(x+ε)-f(x-ε))/2ε or implement a function that symbolically computes it (likely returning better approximations). This kind of stuff gives you the latter for free. That’s less work (more so if you’re continuously tweaking the definition of f(x)) and less error prone (once the bugs have been ironed out :-) ). Now, you’ll ask “who ever wants to compute zeroes?”. Turns out that’s basically (1) what machine learning does. It searches for a maximum, but that can be done using Newton’s method (https://en.wikipedia.org/wiki/Newton's_method#Minimization_and_maximization_problems https://en.wikipedia.org/wiki/Newton's_method#Minimization_a...) (One problem that these kinds of approaches overlook is that of numerical stability. I fear many uses will see implementers help their automatic differentiation tooling to improve numerical stability) (1) yes, I’m painting in very broad strokes, losing detail.
keithalewis 8y ago
It's funny/not funny nobody can give a concrete example of how to apply this. AFAICT the last (only?) example in the paper is about copying memory. I know an easier way to do that.

64 points by bmc7505 8y ago

One thing that is not entirely clear to me about constructions like these is the behavior of array indexing. I understand how to differentiate the assignment of x+y into the variable z, but if I use X as an index into memory and then write Y at that location, the proper result of differentiation looks a lot less clear. One reason for that is my memory locations are discrete points, but X must be treated as if it was continuous, if functions over it are to be differentiable.

radarsat1 8y ago
My understanding is that the trick to differentiable key-value stores is to treat the key as a probability over locations, and to treat the value as a weighted sum using these probabilities. From (pdf) https://aclweb.org/anthology/D16-1147 https://aclweb.org/anthology/D16-1147
choeger 8y ago
Intuitively you only use the value of X in that case, not the derivative. I don't know if that yields a consistent or useful language, though, since you'd also need to consider the reverse operation. In general I think that languages that need such a calculus (Modelica's functions come to mind) would show a lot of such complications when implements a rigorous description of the semantics.
hjorthjort 8y ago
From page 2: "The presented theoretical model enables analytic investigations of differentiable programs through algebraic tools [...]; i.e. the presented operators can take the same role as higher order functions in functional programming." So maybe we should think more in terms of lambda calculus and pure functional programming? There, you don't really write Y to memory location X. In section 5.5 they describe how they "generalize the notion of an iteration from the integers, n ∈ N, to the reals, x ∈ R, and consider fractional iterations."

amuresan 8y ago

Could someone with a better understanding of the topic give a brief example of how this can be used in practice?

ivan_ah 8y ago
This is a theory paper so no immediate practical applications. Potential applications would be generalizing derivative calculations used in currently ML libraries, see https://en.wikipedia.org/wiki/Automatic_differentiation https://en.wikipedia.org/wiki/Automatic_differentiation and http://www.cs.nuim.ie/~gunes/files/Baydin-MSR-Slides-20160201.pdf#page=6 http://www.cs.nuim.ie/~gunes/files/Baydin-MSR-Slides-2016020... Useful quote from paper: "We have been inspired by the development of differentiable programming to formalize a theoretical model, that encompasses the ideas underlying differentiable programming and provides a more general setting for investigations of differentiable programs. The presented theoretical model enables analytic investigations of differentiable programs through algebraic tools, that are closer to the field of programming; i.e. the presented operators can take the same role as higher order functions in functional programming."
Someone 8y ago
Let’s say you wrote a function f(x) and want to know where it is zero. The traditional way is Newton’s method (https://en.wikipedia.org/wiki/Newton's_method https://en.wikipedia.org/wiki/Newton's_method) That requires you to compute f’(x) at various points. You could either pick some small epsilon and approximate it as (f(x+ε)-f(x-ε))/2ε or implement a function that symbolically computes it (likely returning better approximations). This kind of stuff gives you the latter for free. That’s less work (more so if you’re continuously tweaking the definition of f(x)) and less error prone (once the bugs have been ironed out :-) ). Now, you’ll ask “who ever wants to compute zeroes?”. Turns out that’s basically (1) what machine learning does. It searches for a maximum, but that can be done using Newton’s method (https://en.wikipedia.org/wiki/Newton's_method#Minimization_and_maximization_problems https://en.wikipedia.org/wiki/Newton's_method#Minimization_a...) (One problem that these kinds of approaches overlook is that of numerical stability. I fear many uses will see implementers help their automatic differentiation tooling to improve numerical stability) (1) yes, I’m painting in very broad strokes, losing detail.

keithalewis 8y ago

It's funny/not funny nobody can give a concrete example of how to apply this. AFAICT the last (only?) example in the paper is about copying memory. I know an easier way to do that.