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

51–60 of 112 posts

Re: Differentiable programming from scratch

#51

Post by ogogmad »

godelski wrote: post #49
yarg wrote: 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…

You really just derived the central derivative. Yes, this derivative is more accurate. The issue is that you can't use it on the edges. For the boundaries you're stuck with lower precision. Here's a resource you might be interested in http://www2.math.umd.edu/~dlevy/classes/amsc466/lecture-note...

The central derivative is equal to Im(f(x + j h) / h) where j is the split-complex number which squares to 1, "Im" is the imaginary-part function, and h is a small real number. When j is replaced with the dual number epsilon, this instead equals the actual derivative, as is shown in the article. You can also replace j with the complex number i, producing the complex-step method.

Central difference and complex-step are both bad approximations to the actual derivative. Of these, the complex-step method is the most ridiculous because it requires extending a function to act on complex numbers, while not extending it to the closely-related dual numbers.

Re: Differentiable programming from scratch

#52

Post by ogogmad »

joe__f wrote: post #48
yarg wrote: 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…

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.

Re: Differentiable programming from scratch

#53

Post by vladf »

ogogmad wrote: post #51
godelski wrote: post #49

Earlier quoted context omitted.

You really just derived the central derivative. Yes, this derivative is more accurate. The issue is that you can't use it on the edges. For the boundaries you're stuck with lower precision. Here's a resource you might be interested in http://www2.math.umd.edu/~dlevy/classes/amsc466/lecture-note...

The central derivative is equal to Im(f(x + j h) / h) where j is the split-complex number which squares to 1, "Im" is the imaginary-part function, and h is a small real number. When j is replaced with the dual number epsilon, this instead equals the actual derivative, as is shown in the article. You can also replace j with the complex number i, producing the complex-step method. Central difference and complex-step ar…

"Ridiculous" is not a word I'd use... sometimes symbolic derivatives are intractable, in which case complex step derivatives provide high-precision numerical derivatives which are otherwise unattainable.

https://vladfeinberg.com/2020/07/05/discrete-residues.html

Re: Differentiable programming from scratch

#54

Post by ogogmad »

vladf wrote: post #53
ogogmad wrote: post #51

Earlier quoted context omitted.

The central derivative is equal to Im(f(x + j h) / h) where j is the split-complex number which squares to 1, "Im" is the imaginary-part function, and h is a small real number. When j is replaced with the dual number epsilon, this instead equals the actual derivative, as is shown in the article. You can also replace j with the complex number i, producing the complex-step method. Central difference and complex-step ar…

"Ridiculous" is not a word I'd use... sometimes symbolic derivatives are intractable, in which case complex step derivatives provide high-precision numerical derivatives which are otherwise unattainable. https://vladfeinberg.com/2020/07/05/discrete-residues.html

No. The dual numbers are very similar to the complex numbers and produce exact results. Ridiculous is true and fair.

[edit] Also, I wouldn't count using Cauchy's Integral Formula as the complex-step method.

Re: Differentiable programming from scratch

#55

Post by goldenkey »

ogogmad wrote: post #52
joe__f wrote: 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.

This is not true. Doomed is sensational. With proper perturbation analysis, one can choose an appropriate stencil and formula that has desired error bounds.

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72...

https://www.google.com/search?q=finite+difference+stencil+de...

Re: Differentiable programming from scratch

#56

Post by ogogmad »

goldenkey wrote: post #55
ogogmad wrote: 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.

This is not true. Doomed is sensational. With proper perturbation analysis, one can choose an appropriate stencil and formula that has desired error bounds. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72... https://www.google.com/search?q=finite+difference+stencil+de...

Won't work on my example. Given any differentiable function f:R -> R, you can add a very small function to it that dramatically changes its derivative. But maybe this is too pathological to bother about.

Over the complex numbers, this phenomenon doesn't happen. This can be shown, for instance, using the maximum modulus principle. You can therefore use Cauchy's Integral Formula to accurately estimate derivatives. But why not then just use the dual numbers?

Re: Differentiable programming from scratch

#57

Post by goldenkey »

ogogmad wrote: post #56
goldenkey wrote: post #55

Earlier quoted context omitted.

This is not true. Doomed is sensational. With proper perturbation analysis, one can choose an appropriate stencil and formula that has desired error bounds. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72... https://www.google.com/search?q=finite+difference+stencil+de...

Won't work on my example. Given any differentiable function f:R -> R, you can add a very small function to it that dramatically changes its derivative. But maybe this is too pathological to bother about. Over the complex numbers, this phenomenon doesn't happen. This can be shown, for instance, using the maximum modulus principle. You can therefore use Cauchy's Integral Formula to accurately estimate derivatives. But…

I see your edit - fair point, analyticity does make complex functions much more well-behaved than their real counterparts. Still, this isn't a death knell like you previously claimed.

Let's put up a bet. I win the bet if I provide a polynomial approximation of f'(x), R[f(x)], bounded by a maximum of 5% error, on the interval (-1, 1), by November 1st, 2022. If I fail to, or resign by then, you win.

If I win, you agree to silence yourself for 1 year, regarding the split-complex and dual numbers, no longer touting them as a panacea.

If I lose, I'll agree to make a YouTube video extolling the virtues of a mathematical subject of your choice, such as these types of numbers.

Re: Differentiable programming from scratch

#58

Post by ogogmad »

goldenkey wrote: post #57
ogogmad wrote: post #56

Earlier quoted context omitted.

Won't work on my example. Given any differentiable function f:R -> R, you can add a very small function to it that dramatically changes its derivative. But maybe this is too pathological to bother about. Over the complex numbers, this phenomenon doesn't happen. This can be shown, for instance, using the maximum modulus principle. You can therefore use Cauchy's Integral Formula to accurately estimate derivatives. But…

I see your edit - fair point, analyticity does make complex functions much more well-behaved than their real counterparts. Still, this isn't a death knell like you previously claimed. Let's put up a bet. I win the bet if I provide a polynomial approximation of f'(x), R[f(x)], bounded by a maximum of 5% error, on the interval (-1, 1), by November 1st, 2022. If I fail to, or resign by then, you win. If I win, you agree…

I don't fully understand your bet (and I don't take kindly to being asked to silence myself). I don't have time at the moment to craft an example. I might play around a bit with the edges of floating point. Differentiation is indeed discontinuous, so with enough determination I should be able to win such a bet. My function would probably be a sigmoid function which would go from -a to +a (for small a) over a very small interval [-b,b], where b can equal a.

> If I win, you agree to silence yourself for 1 year, regarding the split-complex and dual numbers, no longer touting them as a panacea.

I never said these numbers were a panacea. I said the dual numbers were an exact method. In this comment [1], which is what you're referring to, I said that the connection with other planar algebras was cute, but you mischaracterised what I said, which was rude. The algebras are pertinent because the article mentioned the dual numbers.

[1] - https://news.ycombinator.com/item?id=32305644

Re: Differentiable programming from scratch

#59

Post by goldenkey »

ogogmad wrote: post #58
goldenkey wrote: post #57

Earlier quoted context omitted.

I see your edit - fair point, analyticity does make complex functions much more well-behaved than their real counterparts. Still, this isn't a death knell like you previously claimed. Let's put up a bet. I win the bet if I provide a polynomial approximation of f'(x), R[f(x)], bounded by a maximum of 5% error, on the interval (-1, 1), by November 1st, 2022. If I fail to, or resign by then, you win. If I win, you agree…

I don't fully understand your bet (and I don't take kindly to being asked to silence myself). I don't have time at the moment to craft an example. I might play around a bit with the edges of floating point. Differentiation is indeed discontinuous, so with enough determination I should be able to win such a bet. My function would probably be a sigmoid function which would go from -a to +a (for small a) over a very sma…

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 same finitude as other approximations?

I see a lot of beasts but only one individual claiming to tame them with ease and exactness.

If it comes across as rude, that's not my intent. Moreso to have some clarity and to have your claims be validated.

Re: Differentiable programming from scratch

#60

Post by ogogmad »

goldenkey wrote: post #59
ogogmad wrote: post #58

Earlier quoted context omitted.

I don't fully understand your bet (and I don't take kindly to being asked to silence myself). I don't have time at the moment to craft an example. I might play around a bit with the edges of floating point. Differentiation is indeed discontinuous, so with enough determination I should be able to win such a bet. My function would probably be a sigmoid function which would go from -a to +a (for small a) over a very sma…

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 over the dual numbers, the function should have f(e, epsilon) = e, where e is the dual number imaginary. In other words, the dual numbers return the correct value of the derivative at x=0, which is 1. You should be able to use any Python implementation of the dual numbers; my own one uses Sympy. Actually, you might be able to use Scipy and represent dual numbers as matrices.

Look up automatic differentiation because you're not aware of it, and it is the subject of the article. You seem to misunderstand symbol methods. The problem of finding an exact derivative at a single point is not as hard as finding the symbolic derivative everywhere. You're referring to the product rule and chain rule, but these are not needed to find derivatives at single points.

Post reply on HN