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

Differentiable programming from scratch

thenumb.at

Post reply on HN
Print view View original

11–20 of 112 posts

Re: Differentiable programming from scratch

#11

Post by oddity »

bmitc wrote: post #8
oddity wrote: post #6

Earlier quoted context omitted.

Object oriented programming, for example, doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime, but object oriented + differentiable programming does. It's no less of a paradigm than logic, quantum, or probabilistic programming. If you want to, you can view differentiable programming as extending logic programming with a pro…

You don't need OOP plus another paradigm to do automatic differentiation though. I've implemented automatic differentiation, albeit "simple" versions and only forward-mode at this point, but there's really nothing special about the implementations. Logic programming, on the other hand and for example, needs something much more substantial to be implemented as a library in an existing language, such as backtracking, u…

I don't need OOP to do a hash table lookup and then an indirect function call with the receiver as the first argument either but that ignores that there's more to a paradigm than the algorithm I use for facilitating it. You can embed unification of expression trees as a library in C++. People implement backtracking all the time in almost every language. Talking about differentiable programming as if it's just autodiff is missing the point of what a programming paradigm is.

There's a mechanism, yes, but that's just a means to an end of efficiently enabling a different way of approaching programming. In the case of differentiable programming, that's continuous code and continuous data enabling program search that doesn't have to use purely discrete methods (like logic programming). If that sounds like autodiff and backprop, then yes, that's because that's a good way to implement it. Tensorflow and PyTorch are DSLs embedded in Python and C++ both useable and used for more than just implementing neural networks, but most people aren't happy calling a library a language until it has a parser and a file extension.

> I'm not sure what you mean here. Could you elaborate?

Most programming languages assume that a variable can only contain one value, or a composite value of values. Differentiable programming lets code be smoothly transformed from one to the other while being meaningful at all points between. In an object oriented case, this would be like having a variable contain an object that behaves like some known object A or object B selectively depending on which choice maximizes the success of the program at any given moment.

Re: Differentiable programming from scratch

#12

Post by data_maan »

oddity wrote: post #6
bmitc wrote: post #2

You don't need induction for (x+x'e)^n+1. The binomial formula can be applied once the arithmetic on dual numbers is introduced. > We can use this result to prove the same property for any smooth function f. Examining the Taylor expansion of f at zero (also known as its Maclaurin series): That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x| 1, where simila…

Object oriented programming, for example, doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime, but object oriented + differentiable programming does. It's no less of a paradigm than logic, quantum, or probabilistic programming. If you want to, you can view differentiable programming as extending logic programming with a pro…

Seems a bit of conflation of notions going on here: Just because logic/quantum/probabilistic all end with "programming", it doesn't mean that they all are what is called a "programming paradigm" in the typical sense [0]. Where does a paradigm end and a library implementation begin?

For example, varying how a program arrives at the answer induces impertive/OOP vs. declarative paradigms [0]. On the other hand, quantum programming assumes a radically different type of "CPU" (i.e. instruction set) on which your program runs - which in turn obviously changes everything. But this can safely by implemented within existing paradigms, e.g. ProjectQ [1] is implemented in an OOP language: Python. Thus, I would not call this a new programming paradigm (unfortunately [0] does that, but I think that is bad form).

> you can view differentiable programming as extending logic programming [...] that allows interpolation between data and code.

Reference? I have browsed one of the standard references [2] on automatic differentiation and googled a bit and could not find something that supports your statement. Even more so, is seems that even defining semantics for differential programming is barely in its starting stages [3].

> differentiable programming is at the level of syntax sugar for reverse mode differentiation, so I can't blame you for that conclusion.

By the same argument you could say that probabilistic programming is just syntax sugar for painless specification of statistical models.

Care to provide a reference where differential programming is presented as something more than "syntax sugar"?

[0] https://en.wikipedia.org/wiki/Programming_paradigm#Further_p...

[1] https://projectq.ch/

[2] Griewank A., Walther A., Evaluating Derivatives, SIAM 2008

[3] https://arxiv.org/pdf/1911.04523.pdf

Re: Differentiable programming from scratch

#13

Post by bmitc »

oddity wrote: post #9
bmitc wrote: post #5

Earlier quoted context omitted.

But I would wager that those are poor implementations of automatic differentiation, as the property that automatic differentiation works with for loops, if statements, etc. is inherent to automatic differentiation. So differential programming seems like automatic differentiation just implemented properly. I've written some simple forward-mode automatic differentiation implementations in a few languages, and it's akin…

Autodiff does not work with for loops or if statements. The current solutions effectively pick a few promising traces through the program and then assume that nothing else exists. To handle it more elegantly (for things like preserving equational reasoning or avoiding exponential blowup) you need to address it at the level of language semantics.

> Autodiff does not work with for loops or if statements.

Is that necessarily true? Here is an incomplete automatic differentiation implementation that handles if statements just fine in a function definition. Unless you mean something else.

    type Dual = {Real: float; Epsilon: float} with
        static member (~-) (x: Dual) = {Real = -x.Real; Epsilon = -x.Epsilon}

        static member (+) (x: Dual, y: Dual) = { Real = x.Real + y.Real
                                                 Epsilon = x.Epsilon + y.Epsilon }
        static member (+) (x: Dual, c: float) = {x with Real = x.Real + c}
        static member (+) (c: float, y: Dual) = {y with Real = c + y.Real}

        static member (-) (x: Dual, y: Dual) = x + (-y)
        static member (-) (x: Dual, c: float) = x + (-c)
        static member (-) (c: float, y: Dual) = c + (-y)

        static member (*) (x: Dual, y: Dual) = { Real = x.Real * y.Real
                                                 Epsilon = x.Real * y.Epsilon + x.Epsilon * y.Real }
        static member (*) (c: float, y: Dual) = {Real = c; Epsilon = 0} * y
        static member (*) (x: Dual, c: float) = x * {Real = c; Epsilon = 0}

    let dcos (x: Dual) = {Real = cos x.Real; Epsilon = -(sin x.Real) * x.Epsilon}
    let dsin (x: Dual) = {Real = sin x.Real; Epsilon = (cos x.Real) * x.Epsilon}

    let differentiate (f: Dual -> Dual) a =
        let x = f {Real = a; Epsilon = 1.0}
        x.Epsilon

    let testFunction (x: Dual) = if x.Real
Using that gives:

    > differentiate testFunction -1.0
      0.8414709848078965

    > differentiate testFunction 1.0
      0.4161468365471424

    > differentiate testFunction 0.0
      -3.0
Now, of course, one needs to be careful interpreting the result at a = 0.0. That's because the testFunction is not differentiable at that point due to a jump discontinuity there, but we still get a value back. But as far as I know, this is simply an issue with automatic differentiation in that it only correctly tells you what the derivative is if it exists at the given point.

Re: Differentiable programming from scratch

#14

Post by data_maan »

adgjlsfhk1 wrote: post #3
bmitc wrote: post #2

You don't need induction for (x+x'e)^n+1. The binomial formula can be applied once the arithmetic on dual numbers is introduced. > We can use this result to prove the same property for any smooth function f. Examining the Taylor expansion of f at zero (also known as its Maclaurin series): That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x| 1, where simila…

The idea behind the term "differential programming" is that many traditional autodiff systems force you into a highly restricted subset of the language or DSL (e.g. no loops, no if statements etc). Differential programming is a term used to describe systems that let you take derivatives of your entire source code. This lets you do things like AD through a simulation or optimization algorithm which can be really power…

Mathematician here.

> Differential programming is a term used to describe systems that let you take derivatives of your entire source code.

I think the way this is stated is incorrect. What would the derivative of a program that outputs the reverse the input string be? It would be meaningless.

It seems rather to be the case that it describes systems that let you take derivatives of your entire source code where that source code describes a numerical function. Perhaps it is obvious to state this, but I keep seeing differentiable programming being described as "taking a derivative of the source code" and it seems annoyingly imprecise.

> This lets you do things like AD through a simulation or optimization algorithm

This is also, taken literally, not a correct statement. It's not the algorithm which you want to differentiate, but a hard-to-differentiate function within the algorithm (which is always a gradient-descent type algorithm, as it otherwise makes no sense to consider derivatives; there is the entire domain of derivative-free optimization BTW). So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously.

Re: Differentiable programming from scratch

#15

Post by data_maan »

bmitc wrote: post #13
oddity wrote: post #9

Earlier quoted context omitted.

Autodiff does not work with for loops or if statements. The current solutions effectively pick a few promising traces through the program and then assume that nothing else exists. To handle it more elegantly (for things like preserving equational reasoning or avoiding exponential blowup) you need to address it at the level of language semantics.

> Autodiff does not work with for loops or if statements. Is that necessarily true? Here is an incomplete automatic differentiation implementation that handles if statements just fine in a function definition. Unless you mean something else. type Dual = {Real: float; Epsilon: float} with static member (~-) (x: Dual) = {Real = -x.Real; Epsilon = -x.Epsilon} static member (+) (x: Dual, y: Dual) = { Real = x.Real + y.Re…

@bmitc: Reading your replies (some of which seem to have been written the same time I wrote mine), it seems we are on the same page; I'm also a mathematician and I also have some qualms with how people invent new names for automatic differentiation :) I had a look at your bio and couldn't find any email address. Would you perhaps be interested in having a longer, scientific discussion about AD?

Re: Differentiable programming from scratch

#16

Post by oddity »

data_maan wrote: post #12
oddity wrote: post #6

Earlier quoted context omitted.

Object oriented programming, for example, doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime, but object oriented + differentiable programming does. It's no less of a paradigm than logic, quantum, or probabilistic programming. If you want to, you can view differentiable programming as extending logic programming with a pro…

Seems a bit of conflation of notions going on here: Just because logic/quantum/probabilistic all end with "programming", it doesn't mean that they all are what is called a "programming paradigm" in the typical sense [0]. Where does a paradigm end and a library implementation begin? For example, varying how a program arrives at the answer induces impertive/OOP vs. declarative paradigms [0]. On the other hand, quantum…

The existence of a different kind of CPU isn't a meaningful distinction at the level of discussing paradigms. The semantics are different, so the abstract machine is different. The fact that I need a different set of atoms in my desktop to use it doesn't change the programming language part of the discussion.

The main paper to read is [1] which introduces a syntactic notion of differentiation in the lambda calculus connecting substitution and nondeterministic choice to differentiation in the calculus of infinitesimals sense and also introduces a meaningful notion of Taylor expansion of arbitrary programs. This paper is mostly of academic interest, though. The resulting expansion is wildly uncomputable meaning that more modern, practical papers like [2] cite it wistfully as a dream of what could be achieved. How to computably handle most of the constructs we care about in a general programming sense is very active, open research. At the time the paper was introduced, it was more influential on (and influenced by) work on probabilistic and quantum programming through their related models of linear logic [3]. There are only a few slight axiom differences that separate differential, logic, probabilistic, and quantum programming though, so if you're willing to accept one as a "paradigm", then you should accept the others.

[1] https://www.sciencedirect.com/science/article/pii/S030439750... [2] https://arxiv.org/abs/1911.04523 [3] https://ncatlab.org/nlab/show/differential%20category

Re: Differentiable programming from scratch

#18

Post by radarsat1 »

data_maan wrote: post #14
adgjlsfhk1 wrote: post #3

Earlier quoted context omitted.

The idea behind the term "differential programming" is that many traditional autodiff systems force you into a highly restricted subset of the language or DSL (e.g. no loops, no if statements etc). Differential programming is a term used to describe systems that let you take derivatives of your entire source code. This lets you do things like AD through a simulation or optimization algorithm which can be really power…

Mathematician here. > Differential programming is a term used to describe systems that let you take derivatives of your entire source code. I think the way this is stated is incorrect. What would the derivative of a program that outputs the reverse the input string be? It would be meaningless. It seems rather to be the case that it describes systems that let you take derivatives of your entire source code where that…

> So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously.

The specific proposal of differential programming as a paradigm that goes beyond simple applications of gradient descent for optimising NNs is exactly to apply gradient descent to optimise learning (and other) algorithms themselves. This may be to select hyperparameters, or to select among a family of algorithms, or to include differentiable constraints in the solver, etc.

I wonder, are you familiar with now classic paper, Learning to learn by gradient descent by gradient descent?

[0] https://arxiv.org/abs/1606.04474

Re: Differentiable programming from scratch

#19

Post by oddity »

bmitc wrote: post #13
oddity wrote: post #9

Earlier quoted context omitted.

Autodiff does not work with for loops or if statements. The current solutions effectively pick a few promising traces through the program and then assume that nothing else exists. To handle it more elegantly (for things like preserving equational reasoning or avoiding exponential blowup) you need to address it at the level of language semantics.

> Autodiff does not work with for loops or if statements. Is that necessarily true? Here is an incomplete automatic differentiation implementation that handles if statements just fine in a function definition. Unless you mean something else. type Dual = {Real: float; Epsilon: float} with static member (~-) (x: Dual) = {Real = -x.Real; Epsilon = -x.Epsilon} static member (+) (x: Dual, y: Dual) = { Real = x.Real + y.Re…

This "discretizes then differentiates" to borrow terminology from [1] which is one of the more accessible presentations and papers. The program might evaluate correctly, but equational reasoning (like you might want for any kind of automated optimizations) is broken. In a toy example like this where you're doing everything manually then you probably don't care, but for larger systems, it gets tiring to do the mental equivalent of assembly programming.

[1] https://people.csail.mit.edu/sbangaru/projects/teg-2021/

Post reply on HN