3 ms·

Man I'm having a hell of a time imagining how one would write a differentiable program. I guess realistically it would have to be functional programming, where

Man I'm having a hell of a time imagining how one would write a differentiable program. I guess realistically it would have to be functional programming, where each function is itself differentiable, and then you'd have to be very careful with your function composition. I'm incredibly intrigued, but also pretty skeptical. Like it seems like it would be so hard to ensure that you don't leave the domain where your program is differentiable.

nullc 7y ago
There are automatic differentiation libraries for many languages, including C++. The result is generally only piecewise differentiable because, e.g. you obviously cannot differentiate across the hard branch of an if-statement. Usually for optimization you want reverse-mode differentiation, where you learn how the function output-- some optimization objective-- depends on the input variables. The automatic differentiation libraries records all the operations you perform on the input variables and then composes them using the chain rule, working backwards. For some kinds of codebases it's actually pretty natural... e.g. I've taken a big body of C digital signal processing code and in a couple hours gotten gradients for it just by replacing all the floating point variables with special differentiable types from an AD library. These libraries also include collections of standard math lib functions which it knows the derivative for. For the purpose of optimization the fact that your program isn't differentiable everywhere isn't necessarily a problem. You can use gradient free methods for searches across those boundaries, and gradient methods to refine your results within them. If you're optimizing over problems that have thousands of input variables having derivatives is critical to making machine optimization tractable-- unless your search space is particularly trivial and can be well approximated by the simple differentiable models that gradient free local optimization tools use internally. Of course, you could also attempt to directly program your derivatives-- it almost would certainly be much faster to evaluate than transcript based reverse mode AD. But it may be impossible to construct analytical derivatives that cover your whole problem domain, it's often unreasonable hard even when possible, and even if you have them keeping the functions in-sync is difficult and a source of devious bugs.
bmc7505 7y ago
Thanks for checking out our project! Completely understand where you're coming from, I also struggled with imagining how differentiable programs could work, after all, computer programs implement discrete functions! When building it, I learned two surprising facts: (1) We can perform gradient descent on integer functions! [1] There are rigorous assumptions for differentiability (e.g. Lipschitz-continuity, β-smoothness), but most often, these don't apply in the real world. Although many discrete optimization problems can relaxed to semi-differentiable ones, even if a function is not strictly differentiable, we can still derive an approximately correct expression for the gradient. (2) It is possible to symbolically derive functions in discrete spaces! There are many, many examples of this in various settings (e.g. Brzonski's derivative [2], Lambda calculus [3], Boolean algebra [4], et al. [5]). A number of researchers are studying generalized differentiation, or "change propagation" in other topological spaces [6]. Although still very abstract and hard to interpret, these ideas have important applications for incremental computation and together with probabilistic programming [7], may one day lead to an analogous mechanism to gradient descent on a much broader class of functions. With this in mind, Kotlin𝛁 implements symbolic differentiation. Whenever the user writes "+" or "*" in their program and later asks for the derivative, we apply the sum and product rules, and do not consider the question of domain validity. For floating point numbers, we try to perform some consistency checks using finite differences, but ultimately, leave this up to the user to verify whether their their domain is a valid one. Shameless plug, but if you find this interesting, you can learn more about this in Chapter 3 of my M.S. thesis [8]. Please don't hesitate to get in touch if you have any questions or would like to chat! [1]: https://openreview.net/pdf?id=HJGXzmspb https://openreview.net/pdf?id=HJGXzmspb [2]: http://maveric.uwaterloo.ca/reports/1964_JACM_Brzozowski.pdf http://maveric.uwaterloo.ca/reports/1964_JACM_Brzozowski.pdf [3]: https://core.ac.uk/download/pdf/82396223.pdf https://core.ac.uk/download/pdf/82396223.pdf [4]: https://pdfs.semanticscholar.org/a9c8/7568463a5ce8c2cd15ec17e9a54e1158db2b.pdf https://pdfs.semanticscholar.org/a9c8/7568463a5ce8c2cd15ec17... [5]: https://en.wikipedia.org/wiki/Generalizations_of_the_derivative https://en.wikipedia.org/wiki/Generalizations_of_the_derivat... [6]: https://arxiv.org/pdf/1902.05465.pdf https://arxiv.org/pdf/1902.05465.pdf [7]: https://www.cs.ubc.ca/~fwood/CS532W-539W/ https://www.cs.ubc.ca/~fwood/CS532W-539W/ [8]: https://github.com/breandan/kotlingrad/blob/master/latex/thesis/thesis.pdf https://github.com/breandan/kotlingrad/blob/master/latex/the...

nullc 7y ago

There are automatic differentiation libraries for many languages, including C++. The result is generally only piecewise differentiable because, e.g. you obviously cannot differentiate across the hard branch of an if-statement. Usually for optimization you want reverse-mode differentiation, where you learn how the function output-- some optimization objective-- depends on the input variables. The automatic differentiation libraries records all the operations you perform on the input variables and then composes them using the chain rule, working backwards. For some kinds of codebases it's actually pretty natural... e.g. I've taken a big body of C digital signal processing code and in a couple hours gotten gradients for it just by replacing all the floating point variables with special differentiable types from an AD library. These libraries also include collections of standard math lib functions which it knows the derivative for. For the purpose of optimization the fact that your program isn't differentiable everywhere isn't necessarily a problem. You can use gradient free methods for searches across those boundaries, and gradient methods to refine your results within them. If you're optimizing over problems that have thousands of input variables having derivatives is critical to making machine optimization tractable-- unless your search space is particularly trivial and can be well approximated by the simple differentiable models that gradient free local optimization tools use internally. Of course, you could also attempt to directly program your derivatives-- it almost would certainly be much faster to evaluate than transcript based reverse mode AD. But it may be impossible to construct analytical derivatives that cover your whole problem domain, it's often unreasonable hard even when possible, and even if you have them keeping the functions in-sync is difficult and a source of devious bugs.

bmc7505 7y ago

Thanks for checking out our project! Completely understand where you're coming from, I also struggled with imagining how differentiable programs could work, after all, computer programs implement discrete functions! When building it, I learned two surprising facts: (1) We can perform gradient descent on integer functions! [1] There are rigorous assumptions for differentiability (e.g. Lipschitz-continuity, β-smoothness), but most often, these don't apply in the real world. Although many discrete optimization problems can relaxed to semi-differentiable ones, even if a function is not strictly differentiable, we can still derive an approximately correct expression for the gradient. (2) It is possible to symbolically derive functions in discrete spaces! There are many, many examples of this in various settings (e.g. Brzonski's derivative [2], Lambda calculus [3], Boolean algebra [4], et al. [5]). A number of researchers are studying generalized differentiation, or "change propagation" in other topological spaces [6]. Although still very abstract and hard to interpret, these ideas have important applications for incremental computation and together with probabilistic programming [7], may one day lead to an analogous mechanism to gradient descent on a much broader class of functions. With this in mind, Kotlin𝛁 implements symbolic differentiation. Whenever the user writes "+" or "*" in their program and later asks for the derivative, we apply the sum and product rules, and do not consider the question of domain validity. For floating point numbers, we try to perform some consistency checks using finite differences, but ultimately, leave this up to the user to verify whether their their domain is a valid one. Shameless plug, but if you find this interesting, you can learn more about this in Chapter 3 of my M.S. thesis [8]. Please don't hesitate to get in touch if you have any questions or would like to chat! [1]: https://openreview.net/pdf?id=HJGXzmspb https://openreview.net/pdf?id=HJGXzmspb [2]: http://maveric.uwaterloo.ca/reports/1964_JACM_Brzozowski.pdf http://maveric.uwaterloo.ca/reports/1964_JACM_Brzozowski.pdf [3]: https://core.ac.uk/download/pdf/82396223.pdf https://core.ac.uk/download/pdf/82396223.pdf [4]: https://pdfs.semanticscholar.org/a9c8/7568463a5ce8c2cd15ec17e9a54e1158db2b.pdf https://pdfs.semanticscholar.org/a9c8/7568463a5ce8c2cd15ec17... [5]: https://en.wikipedia.org/wiki/Generalizations_of_the_derivative https://en.wikipedia.org/wiki/Generalizations_of_the_derivat... [6]: https://arxiv.org/pdf/1902.05465.pdf https://arxiv.org/pdf/1902.05465.pdf [7]: https://www.cs.ubc.ca/~fwood/CS532W-539W/ https://www.cs.ubc.ca/~fwood/CS532W-539W/ [8]: https://github.com/breandan/kotlingrad/blob/master/latex/thesis/thesis.pdf https://github.com/breandan/kotlingrad/blob/master/latex/the...