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

91–100 of 112 posts

Re: Differentiable programming from scratch

#91

Post by data_maan »

oddity wrote: post #78
data_maan wrote: post #26

Earlier quoted context omitted.

It seems you haven't read my references? As your [2] is my [3] from above! > The existence of a different kind of CPU isn't a meaningful distinction at the level of discussing paradigms. Well, that was my point above: You can't really lump quantum programming together with probabilistic programming, as they are paradigms on different "levels". > practical papers like [2] cite it wistfully as a dream of what could be…

I don't usually respond to old comments, so I don't know if you'll read this, but I hope I can encourage you to think more broadly about what "differentiable programming" means. Different fields have a different perspective on the same set of tools because those tools have different pathological cases in different areas. Context really matters. > Well, that was my point above: You can't really lump quantum programmin…

P.S. (In case you return once more to read comments.)

It seems like these are problems that could benefit from a PL-theory mathematical analysis cross-collaboration.

I would have sent you a private message via email, but couldn't find any info on your HN profile; my email is there.

Re: Differentiable programming from scratch

#92

Post by Doxin »

data_maan wrote: post #83
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...

This! I always find it curious how computer scientists end up rediscovering things known for decades, and then get all hyped about it ...

I figure it's because math people aren't great at communication with people outside their domain. Point in case being Wikipedia articles on math being absolute gobledygook to non-math people.

Re: Differentiable programming from scratch

#93

Post by ogogmad »

joe__f wrote: post #85
ogogmad wrote: post #70

Earlier quoted context omitted.

> 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…

Well, there are many different methods and certainly some are based on numerical integration as you say. The most simple method based on finite difference derivatives is Euler's method which uses the scheme given by OP, with error O(h). This can be extended to Runge-Kutta methods which use a finite difference with n terms and have error O(h^(n-1)), and which to my knowledge are common and widely used to solve ODEs. Y…

> I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain

Autodiff is an algorithm for computing derivatives in areas like Deep Learning. It's an exact method with two main variants -- forward mode and reverse mode -- differing in terms of when each of them is more efficient. It's implemented in widely-used numerical libraries like PyTorch and TensorFlow. The simplest implementations use the dual numbers to implement the forward mode variant. More sophisticated implementations implement the reverse mode variant. Wikipedia has plenty on it.

Re: Differentiable programming from scratch

#94

Post by godelski »

Doxin wrote: post #92
data_maan wrote: post #83

Earlier quoted context omitted.

This! I always find it curious how computer scientists end up rediscovering things known for decades, and then get all hyped about it ...

I figure it's because math people aren't great at communication with people outside their domain. Point in case being Wikipedia articles on math being absolute gobledygook to non-math people.

To be fair, I can't get computer scientists to read any math books. But I don't think this is quite odd. The only people I know that go out and read math books are mostly (current or former) mathematicians or physicists (which a random sprinkling of others). I'm not sure it is exactly mathematicians faults that your third grade teacher impressed upon you that math is hard and useless.

Re: Differentiable programming from scratch

#95

Post by joe__f »

ogogmad wrote: post #93
joe__f wrote: post #85

Earlier quoted context omitted.

Well, there are many different methods and certainly some are based on numerical integration as you say. The most simple method based on finite difference derivatives is Euler's method which uses the scheme given by OP, with error O(h). This can be extended to Runge-Kutta methods which use a finite difference with n terms and have error O(h^(n-1)), and which to my knowledge are common and widely used to solve ODEs. Y…

> I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain Autodiff is an algorithm for computing derivatives in areas like Deep Learning. It's an exact method with two main variants -- forward mode and reverse mode -- differing in terms of when each of them is more efficient. It's implemented in widely-used numerical libraries like PyTorch and TensorFlow.…

Ok I had a look at wiki and it's clear to me how the dual numbers encode differentiation and the theory behind how autodiff works. How do the two fit together? I didn't follow that part

Re: Differentiable programming from scratch

#96

Post by kragen »

bmitc wrote: post #75
data_maan wrote: post #29

Earlier quoted context omitted.

> I've been looking into this stuff lately, to try and justify mathematically why automatic differentiation works. What do you mean by that? Isn't the theory (at least the mathematical, abstract version of it) already fully represented in books like Griewank that I mentioned in another comment here in this post? I remember seeing somewhere a rather well develop theory using dual numbers (but this was a purely mathema…

> Isn't the theory (at least the mathematical, abstract version of it) already fully represented in books like Griewank that I mentioned in another comment here in this post? I guess it's in there somewhere, but like many of the papers, I find that book to overcomplicate things and just not to my liking. I also don't see any mention of dual numbers, although it's probably somewhat implicit in the development (maybe).…

I think autodiff is mostly interesting because of optimization by gradient descent, and gradient descent is only efficient using reverse-mode autodiff, which can't be done with dual numbers.

I think optimization by gradient descent (and its variants like Adam) is interesting because it's the only optimization algorithm family I know of whose runtime scales linearly oreven near-linearly with the number of dimensions, so for large-dimensionality problems it's the only computationally feasible algorithm. Also, though it's only guaranteed to find the optimum for differentiable convex problems, in practice it seems to work well enough to be interesting for nonconvex problems.

I think optimization is interesting because it allows you to solve arbitrary inverse problems, or at least continuous relaxations of them.

Re: Differentiable programming from scratch

#97

Post by ogogmad »

joe__f wrote: post #95
ogogmad wrote: post #93

Earlier quoted context omitted.

> I don't know what autodiff is, or how the dual numbers fit in here. I'd be interested to learn if you want to explain Autodiff is an algorithm for computing derivatives in areas like Deep Learning. It's an exact method with two main variants -- forward mode and reverse mode -- differing in terms of when each of them is more efficient. It's implemented in widely-used numerical libraries like PyTorch and TensorFlow.…

Ok I had a look at wiki and it's clear to me how the dual numbers encode differentiation and the theory behind how autodiff works. How do the two fit together? I didn't follow that part

You define a dual number type in your programming language of choice, and overload the operators +, -, *, /, , sin, cos, etc. Then you take a function which computes a numerical function f which is defined using the previous operations, and simply evaluate them on a dual number. It's "automatic" because, assuming the right programming language, a user-defined numerical function will often be able to take in many different kinds of numbers, like complex numbers, real numbers, arbitrary precision floats, and even user-defined classes like the dual numbers.

Re: Differentiable programming from scratch

#98

Post by joe__f »

ogogmad wrote: post #97
joe__f wrote: post #95

Earlier quoted context omitted.

Ok I had a look at wiki and it's clear to me how the dual numbers encode differentiation and the theory behind how autodiff works. How do the two fit together? I didn't follow that part

You define a dual number type in your programming language of choice, and overload the operators +, -, *, /, , sin, cos, etc. Then you take a function which computes a numerical function f which is defined using the previous operations, and simply evaluate them on a dual number. It's "automatic" because, assuming the right programming language, a user-defined numerical function will often be able to take in many diff…

Ah thankyou, it was so neat and automatic that I missed the punchline. It looks like you'll always calculate f and f' together and it's not possible to calculate only f' though? Seems like this could waste time in some applications?

I can see how this is the solution to the problem of calculating the numerical derivative of a known function composed of finite combinations of rational functions and a set of specified functions, elementary or special. I don't see how it's relevant to solving ODEs numerically though, given that in that case you don't know the functional form of f or f'

Re: Differentiable programming from scratch

#99

Post by ogogmad »

joe__f wrote: post #98
ogogmad wrote: post #97

Earlier quoted context omitted.

You define a dual number type in your programming language of choice, and overload the operators +, -, *, /, , sin, cos, etc. Then you take a function which computes a numerical function f which is defined using the previous operations, and simply evaluate them on a dual number. It's "automatic" because, assuming the right programming language, a user-defined numerical function will often be able to take in many diff…

Ah thankyou, it was so neat and automatic that I missed the punchline. It looks like you'll always calculate f and f' together and it's not possible to calculate only f' though? Seems like this could waste time in some applications? I can see how this is the solution to the problem of calculating the numerical derivative of a known function composed of finite combinations of rational functions and a set of specified…

> I can see how this is the solution to the problem of calculating the numerical derivative of a known function composed of finite combinations of rational functions and a set of specified functions, elementary or special.

Yes and no. It's worth taking into account that you can apply it to some functions defined using conditions and loops. For instance, if f is the sqrt function defined using Newton's method, then autodiff via the dual numbers will compute an estimate for f'(x) = 1/(2 * sqrt(x)). More explicitly:

  def f(a):
    x = 1
    oldx = 2
    threshold = 1e-10
    while abs(x - oldx)
^ You can evaluate f on a dual number. This algorithm contains conditions and loops.

Re: Differentiable programming from scratch

#100

Post by goldenkey »

yarg wrote: post #80
goldenkey wrote: post #79

Earlier quoted context omitted.

Not exactly sure what you are getting at but it does remind me of the Cauchy's Integral Formula which shows that differentiation is equivalent to integration. https://en.wikipedia.org/wiki/Cauchy%27s_integral_formula

Trying to measure the length of a curve f(x). I turn the curve into a fixed infinitesimal thickness (2 * 𝛿t) 'rope' and measure the area. Then I divide the area by the thickness to get the length. The rope is defined as the area between two curves, both of them manipulations of f(x). The curves are generated by moving each point (in f(x)) a constant infinitesimal distance at a tangent to the function (this gives the…

I'm a brainlet or maybe it's the 10+ hours of work I did today but I just can't grasp it right now.

There are a lot of ways to take integrals though, so I wouldn't doubt your method could work. Generally though the holes in a lot of these integration methods is their inability to work with functions that are pathological: https://en.wikipedia.org/wiki/Pathological_(mathematics)

|group1 = Types of integrals |list1 = * [[Riemann integral]] * [[Lebesgue integration|Lebesgue integral]] * [[Burkill integral]] * [[Bochner integral]] * [[Daniell integral]] * [[Darboux integral]] * [[Henstock–Kurzweil integral]] * [[Haar measure|Haar integral]] * [[Hellinger integral]] * [[Khinchin integral]] * [[Kolmogorov integral]] * [[Lebesgue–Stieltjes integration|Lebesgue–Stieltjes integral]] * [[Pettis integral]] * [[Pfeffer integral]] * [[Riemann–Stieltjes integral]] * [[Regulated integral]]

|group2 = Integration techniques |list2 = * [[Integration by substitution|Substitution]] * [[Trigonometric substitution|Trigonometric]] * [[Euler substitution|Euler]] * [[Weierstrass substitution|Weierstrass]] * [[Integration by parts|By parts]] * [[Integration by partial fractions|Partial fractions]] * [[Integration using Euler's formula|Euler's formula]] * [[Integral of inverse functions|Inverse functions]] * [[Order of integration (calculus)|Changing order]] * [[Integration by reduction formulae|Reduction formulas]] * [[Integration using parametric derivatives|Parametric derivatives]] * [[Leibniz integral rule#Evaluating definite integrals|Differentiation under the integral sign]] * [[Laplace transform#Evaluating improper integrals|Laplace transform]] * [[Contour integration]] * [[Laplace's method]] * [[Numerical integration]] * [[Simpson's rule]] * [[Trapezoidal rule]] * [[Risch algorithm]]

Post reply on HN