Live data from Hacker News

Differentiable programming from scratch

thenumb.at

61–70 of 112 posts

Re: Differentiable programming from scratch

#61
post #46
post #37

One thing that I've thought about, when using calculus in programs, you're often dealing with a very small (but finite) Δx, rather than an infinitesimal 𝛿x. And I don't think that the common differential equation is the ideal form when dealing with that situation. (Take for example g(x) = -f(-x), the gradients at x and -x are not equivalent for Δx, but would be for 𝛿x.) Anyway, (limit(h -> 0)((f(x + h) - f(x))/h) W…

Is h use instead of 𝛿 or Δ, because it is applicable to both partial and normal differential. 𝛿 Is always a partial symbol to me. d in dx whilst is not the same as h, as it stands its own way now as “operator”.

No, the h here is a number, not an operator.

Re: Differentiable programming from scratch

#62
post #9
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.

Julia's AD is compatible with control flow. They have their own issues, but Zygote + ChainRules actually work pretty well

Re: Differentiable programming from scratch

#63
A pet peeve of mine is that differentiable programming is co-opted almost entirely by deep learning + neural networks. The idea of differentiable programming is much bigger than SGD, and in fact neural networks are typically a simple program to differentiate. Full differentiable programming requires solving much more involved problems around control flow than just implementing numerical forward/reverse mode for math operations with well defined and understood gradients.

Re: Differentiable programming from scratch

#64
Thank you for sharing, this was a great article!

I had to implement autodiff from scratch for Nx (https://github.com/elixir-nx/nx) about 18 months ago and this would have helped me so much! I spent roughly a month chasing a bug because I was not handling the case of duplicated incoming nodes and you outline it very clearly. I will be recommending the article from now on to anyone who needs to understand how autodiff works.

Re: Differentiable programming from scratch

#65
post #52
post #48

Earlier quoted context omitted.

If you're interested in how to best calculate derivatives numerically using a finite difference rather than an infinitesimal, try having a look at the Wikipedia page on numerical differentiation. The punchline is that you can control the error in f'(x) much better if you use many displacements, ie. f'(x) = a1 f(x + b1 h) + a2 f(x + b2 h) + a3 f(x + b3 h)..., where the bi are chosen and the ai depend on the bi and h.

Such methods are doomed. Consider the function f(x) = a sin(x / a) for very small a. Finite differencing methods would approximate f'(0) as 0 as f(x) is very close to 0, but the actual value of f'(0) is 1. Differentiation is a discontinuous operator, and cannot be accurately estimated using numerical methods. Only exact methods, which include the dual numbers, can produce accurate results.

Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. Given that these techniques underpin various areas of modern engineering, I'd say your statement that 'differentiation [...] cannot be accurately estimated using numerical methods' is demonstrably incorrect. I think you're fishing for something like 'there exist functions whose derivatives cannot be accurately estimated numerically'. Presumably some assumptions have been made which rule out such functions in using finite difference schemes in practical applications.

Re: Differentiable programming from scratch

#66
post #60

Earlier quoted context omitted.

Fair enough. The bet I had in mind was the function you'd already stated as intractable: f(x) = a sin(x / a), the value of a is up to you, within reason (no IEEE fp shenanigans.) If you'd rather some other consequence than silencing, please suggest one. I am tired of hearing your panaceas. Symbolic differentiation is also exact but intractible. What makes the duals yield exactness in any way that isn't prone to the s…

I'm not going to accept your bet because I don't understand its conditions (and what's the point?), but I accept your challenge. Also, I'm going to f*** around bigly with floating point. def f(x,a): return 1 + a * sin(x / a) Now let epsilon = 2.2204460492503133e-36. Consider f(x, epsilon). The function should always return 1 in floating point, so any finite differencing method will estimate its derivative as 0. But o…

I am aware of AD. All AD does is use the chain rule on the Taylor (or otherwise) approximations of all arithmetic functions used in the calculation of the target function. It's symbolic but only at the single arithmetic operation level. The chain rule is concealed under rules on epsilon. The reason epsilon's square equals 0 is to eliminate any higher order derivatives as soon as they appear. If the derivative is abnormal in a way such that the normal truncated calculative formulas would conceal it, then AD would fail to give an accurate result as well.

Re: Differentiable programming from scratch

#67

Earlier quoted context omitted.

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…

I don't really see the distinction. In the basic case of using gradients to optimize a NN, what's really being optimized are the parameters of a function expressing the NN error. We're just following the gradient downhill to find whatever minimum of this function the gradient leads us to (hopefully the global minimum, as is likely to be the case with lots of parameters).

In this "learning to learn" paper the optimization function (used to update the gradients at each step of the gradient descent algorithm) has been parameterized, and we're instead using gradient descent to find a minimum of that parameterized function.

So, yes, differentiable programming isn't limited to minimizing the losses of neural nets, but as the grandparent poster pointed out, the whole concept obviously only applies to parameterized programs calculating some numerical output that we want to miminize.

Re: Differentiable programming from scratch

#68
post #60

Earlier quoted context omitted.

I'm not going to accept your bet because I don't understand its conditions (and what's the point?), but I accept your challenge. Also, I'm going to f*** around bigly with floating point. def f(x,a): return 1 + a * sin(x / a) Now let epsilon = 2.2204460492503133e-36. Consider f(x, epsilon). The function should always return 1 in floating point, so any finite differencing method will estimate its derivative as 0. But o…

I am aware of AD. All AD does is use the chain rule on the Taylor (or otherwise) approximations of all arithmetic functions used in the calculation of the target function. It's symbolic but only at the single arithmetic operation level. The chain rule is concealed under rules on epsilon. The reason epsilon's square equals 0 is to eliminate any higher order derivatives as soon as they appear. If the derivative is abno…

You've just described the dual numbers, which provide a way of implementing forward-mode autodiff.

  > If the derivative is abnormal in a way such that the normal
  > truncated calculative formulas would conceal it, then AD
  > would fail to give an accurate result as well.
What I'm seeing directly contradicts that. I've tested the example above (the one I called f(x,a) with a=1e-36, trying to find its derivative at x=0), and it gave the right answer with dual numbers, but not with finite differencing. So what you're saying isn't true. I'll post a minimal implementation here later.

[edit]

I've used Sympy out of laziness, which is inelegant. I don't know how clear this will be.

First of all, I have to change the number 1 in the definition of f(x,a) into a matrix. We need this because we'll be representing dual numbers as matrices, and you can't add the scalar 1 to a matrix:

  one = eye(2)
  
  def f(x, a=1e-36):
    return one + a * sin(x / a)
Sympy doesn't have its own implementation of `sin`, so we'll need to provide one:

  def sin(M):
    return im(exp(I*M).n())

At the dual number ε, we have f(ε) = f(0) + ε f'(0). The dual number ε will be represented as the matrix

  ⎡0  1⎤
  ⎢    ⎥
  ⎣0  0⎦
As code:

  epsilon = Matrix([[0,1],[0,0]])
Evaluating f on the above matrix gives:

  In: f(epsilon)
  Out: 
  ⎡1  1.0⎤
  ⎢      ⎥
  ⎣0   1 ⎦
Which tells us that f(0) ≈ 1 and f'(0) ≈ 1. Both are correct.

If we use finite differencing instead, we get:

  In: (f(h * eye(2)) - f(0 * eye(2)))/h
  Out: 
  ⎡0  0⎤
  ⎢    ⎥
  ⎣0  0⎦
So it's claiming incorrectly that the derivative at 0 is 0. No finite differencing scheme can fix this because floating point causes the function f to become constant.

Autodiff using the dual numbers has pulled off the seemingly impossible.

[edit: An early typo caused the code to produce an incorrect result. Now fixed, and my claim holds.]

Re: Differentiable programming from scratch

#69
post #60

Earlier quoted context omitted.

I'm not going to accept your bet because I don't understand its conditions (and what's the point?), but I accept your challenge. Also, I'm going to f*** around bigly with floating point. def f(x,a): return 1 + a * sin(x / a) Now let epsilon = 2.2204460492503133e-36. Consider f(x, epsilon). The function should always return 1 in floating point, so any finite differencing method will estimate its derivative as 0. But o…

I am aware of AD. All AD does is use the chain rule on the Taylor (or otherwise) approximations of all arithmetic functions used in the calculation of the target function. It's symbolic but only at the single arithmetic operation level. The chain rule is concealed under rules on epsilon. The reason epsilon's square equals 0 is to eliminate any higher order derivatives as soon as they appear. If the derivative is abno…

> If the derivative is abnormal in a way such that the normal truncated calculative formulas would conceal it, then AD would fail to give an accurate result as well.

The following is proof of otherwise. First implement the dual numbers by borrowing the code from here [1]. Then define the sine function in a crude way:

  from math import factorial
  
  def sin(x):
      return sum((-1)**i * x**(2*i + 1) / factorial(i) for i in range(100))
We then define f:

  def f(x, a=1e-36):
      return 1 + a * sin(x / a)
and use the dual numbers to estimate the derivative at 0:

  In [49]: print(f(Dual(0,{'epsilon':1})))
  f = 1.0
  fepsilon = 1.0
We get 1 as the estimate, which is correct! For comparison, we may try using finite differencing to estimate the derivative at 0:

  In [50]: h = 1e-36; (f(h) - f(0))/h
  Out[50]: 0.0
The estimate for the derivative is 0 here, which is wrong. The finite differencing cannot be improved using stencil theory because the estimate of f(x) is always exactly 1 under floating point, and therefore the estimate for f'(x) is always exactly 0. Dual numbers win.

[1] - https://github.com/ujjwalkhandelwal/Dual-numbers-and-automat...

Re: Differentiable programming from scratch

#70
post #65
post #52

Earlier quoted context omitted.

Such methods are doomed. Consider the function f(x) = a sin(x / a) for very small a. Finite differencing methods would approximate f'(0) as 0 as f(x) is very close to 0, but the actual value of f'(0) is 1. Differentiation is a discontinuous operator, and cannot be accurately estimated using numerical methods. Only exact methods, which include the dual numbers, can produce accurate results.

Finite difference derivatives are the basis for a range of numerical methods for solving differential equations. Given that these techniques underpin various areas of modern engineering, I'd say your statement that 'differentiation [...] cannot be accurately estimated using numerical methods' is demonstrably incorrect. I think you're fishing for something like 'there exist functions whose derivatives cannot be accura…

> Finite difference derivatives are the basis for a range of numerical methods for solving differential equations.

I thought the basis usually involved rewriting the equation in terms of integrals, which can be estimated using quadrature. Numerical quadrature does not have the same problems as finite differencing because integration is a continuous operator. How accurate are these methods you're proposing? Could they be improved using autodiff (via the dual numbers or via reverse-mode autodiff)? Do you have a reference, so I can understand your point better? I'm sceptical and I'm not inclined to believe you yet.

Post reply on HN