Differentiable programming from scratch
thenumb.at
thenumb.at
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)
(You're dealing with a linear equivalent infinitesimal subsection of the graph - so 𝛿x and 𝛿y scale linearly with each other.)
So remove h:
((f(x + 𝛿x) - f(x))/𝛿x)
(f(x + 𝛿x) - f(x))/𝛿x ≡ (f(x) - f(x - 𝛿x))/𝛿x ≡ (f(x + 𝛿x) - f(x - 𝛿x))/(2 * 𝛿x)
(The cube-root of the other three forms is also a valid differential equation, if you want to be evil about it.)
(f(x + 𝛿x) - f(x - 𝛿x))/(2 * 𝛿x)
Another thing I noticed: the standard (h -> 0) form eliminates all parts of the gradient containing 𝛿x values - which is fine for infinitesimal 𝛿x, but is less ideal for finite Δx.
Here's a resource you might be interested in http://www2.math.umd.edu/~dlevy/classes/amsc466/lecture-note...
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.
[edit] Also, I wouldn't count using Cauchy's Integral Formula as the complex-step method.
I always find it curious how computer scientists end up rediscovering things known for decades, and then get all hyped about it ...
f(x) = a sin(x / a)
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.
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.
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.
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'
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) < threshold:
oldx, x = x, (x + a/x) / 2
return x
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72...
https://www.google.com/search?q=finite+difference+stencil+de...
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?
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.
> 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.
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.
def f(x,a):
return 1 + a * sin(x / a)
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.
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))
def f(x, a=1e-36):
return 1 + a * sin(x / a)
In [49]: print(f(Dual(0,{'epsilon':1})))
f = 1.0
fepsilon = 1.0
In [50]: h = 1e-36; (f(h) - f(0))/h
Out[50]: 0.0
[1] - https://github.com/ujjwalkhandelwal/Dual-numbers-and-automat...
> 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.
[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)
def sin(M):
return im(exp(I*M).n())
⎡0 1⎤
⎢ ⎥
⎣0 0⎦
epsilon = Matrix([[0,1],[0,0]])
In: f(epsilon)
Out:
⎡1 1.0⎤
⎢ ⎥
⎣0 1 ⎦
If we use finite differencing instead, we get:
In: (f(h * eye(2)) - f(0 * eye(2)))/h
Out:
⎡0 0⎤
⎢ ⎥
⎣0 0⎦
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.]
However, like I said, if you have a calcuation method that hides derivatives in terms that have been truncated, then this will not save you.
(-1)*i * x*(2*i + 1) / factorial(i) is not one of those methods -- and sin is rather regular in regard to its Taylor series. So of course it works out in this case, with a normal power series calculation method.
Try a different series or calculation method, and dual numbers will get you a wildly different result. Understand, dual numbers only work well, when you use a method of calculation that front-loads terms that have high bearing on the derivative. Otherwise the missing terms/truncation, causes severe inaccuracy.
However, stenciling might actually perform better in these scenarios.
No. The example works because:
While the exact value of f(x,a) isn't 1, given any inexact representation of real numbers like floating point or fixed point, the value of "a" can be chosen so that f(x,a) has 1 as its closest representation.
Your other claims are probably gibberish. You need to provide an example.
> The key take away here is that the map is not the territory. Most nontrivial functions on computers are implemented as some function that that approximates (the map) the mathematical ideal (the territory). Automatic differentiation gives back a completely accurate derivative of the that function (the map) doing the approximation. Furthermore, the accurate derivative of an approximation to the idea (e.g d_my_sin), is less accurate than and approximation to the (ideal) derivative of the ideal (e.g. my_cos). There is no truncation error in the work the AD did; but there is a truncation error in the sense that we are now using a more truncated approximation that we would write ourselves.
https://www.oxinabox.net/2021/02/08/AD-truncation-error.html
AD is great but if you have a calculation method ill-suited for AD, then you'll get shite results. Why is this surprising?
And yeah, stenciling is mostly for PDEs and other state spaces that we don't have a closed form for. It's generally not used for an analytic function. But you can use it for an analytic function if you tailor the stencil to the function. In fact, you'll just yield a truncated Taylor polynomial if you provide a perfect function-specific stencil.
Stenciling doesn't just deal with the derivative but it tries to come up with approximations involving a fixed number of sample points, the stencil, for any differential operator, ie. the Laplacian, higher order derivatives, etc.
> The term "stencil" was coined for such patterns to reflect the concept of laying out a stencil in the usual sense over a computational grid to reveal just the numbers needed at a particular step. [2]
[0] https://en.wikipedia.org/wiki/Five-point_stencil
[1] https://en.m.wikipedia.org/wiki/Finite_difference_coefficien...
[2] https://en.wikipedia.org/wiki/Stencil_(numerical_analysis)
Another thing that I'm wondering about is how to calculate the length of a function.
What I'm thinking, is that you can treat a function like a piece of string, you take f(x) and generate a pair of functions, one above and one below f(x).
You generate the functions at a fixed (infinitesimal) tangential distance 𝛿t and generate deltas for {x, y}
mul = 𝛿t/((𝛿x)^2 + (𝛿y)^2)^.5
Δx = 𝛿y * mul
Δy = 𝛿x * mul
u(x - Δx) = f(x) + Δy
l(x + Δx) = f(x) - Δy
I have no idea how wrong this is, but if you can point me toward any resources that'll help when I (inevitably) get stuck, it would be very much appreciated.
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 rope its fixed thickness), one in either direction.
For the upper curve {Δx, Δy} = {(n * 𝛿y), -(n * 𝛿x)}, for the lower {(n * 𝛿y), -(n * 𝛿x)}, where n is a normalisation constant 𝛿t/((𝛿x)^2 + (𝛿y)^2)^.5
Once you have these two functions, you can use the integral of the difference to get the area.
That's what I'm thinking anyway.
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]]
Looking at the Weierstrass function, it's a chaotically convergent series with a non-convergent gradient series.
(The standard differential forms don't apply, because the assumption of linearisation at the scale of 𝛿x is invalid, due to the scale invariant properties of the fractal.)
In that case the integral function would be even more convergent since the 'noise' (pretty much) adds to zero.
So can you differentiate via integration, and get a gradient for a related function (with less noise)?
I messed around with this, taking the areas of a pair of little triangle approximations and adding them to get a ~rectangle.
Then divide that area by 𝛿x to get 𝛿y, and divide that by 𝛿x to get 𝛿y/𝛿x.
This was the form that I reached:
let y = f(x)
let F(x) = ∫f(x)𝛿x
𝛿y/𝛿x = (F(x + 𝛿x) + F(x - 𝛿x) - 2 * F(x))/((𝛿x) ^ 2)
let F(x) = x^6
𝛿y/𝛿x = 30(x^4) + 30(x^2)(𝛿x^2) + 2(𝛿x^4)It took me until the end to realise that all I'd done was derive a form for the second derivative of F(x).
https://en.wikipedia.org/wiki/Symmetric_derivative#The_secon...
https://en.wikipedia.org/wiki/Second_derivative#Limit
> The limit is called the second symmetric derivative. Note that the second symmetric derivative may exist even when the (usual) second derivative does not.
> This limit can be viewed as a continuous version of the second difference for sequences.
So it actually can do what I intended it to do, nothing original - but there was a degree of satisfaction in deriving it myself.
d in dx whilst is not the same as h, as it stands its own way now as “operator”.
- programming languages which use neural networks as primitive functions (think `result = sum([mlp(input) for input in list])`. NN's are (understandably) notoriously bad at learning simple operators [1]. Differentiable programming over a language defined by aggregation functions (map/fold/sum/mean/etc.) allows us to bypass learning some simple functions.
- Flipping this around, we can use neural networks that use differentiable programs to regularize the outputs. Assume we have a NN that learns the speed of a car from a video. We know that a car's speed cannot exceed (say) 200mph. Make a differentiable program to express this and use it to regularize the output of the network.
- Reusing the image->NN->speed example again, use the differentiable program to identify speeds/conditions where using a neural network policy is unsafe and switch to a (less-performant) handmade policy instead.
Some more thoughts about this: https://atharvas.prose.sh/differentiable_dsls
[1] https://dselsam.github.io/posts/2018-09-16-neural-networks-o...
(1) everything which makes programs useful is impure device access and state change, discretely sequenced over time
(2) grad. desc. et al. do not learn discrete constraints (hence why NNs are bad at learning operators: they cant. x+x is defined fa. x; not fa x. in the training set).
I haven't heard about this before actually. I'd love to hear more about this! "Impure," here, is PL terminology for functions that affect global state/arguments when you run them. right? So, brainstorming a bit, what this means is that making a diff. programming language that treats a NN module as a pure function won't actually be beneficial? I'm not sure if I'm drawing the correct conclusion but this is a really interesting point. Don't have an answer for this (yet!).
> grad. desc. et al. do not learn discrete constraints
Great Point! To push back a little on this. You're right that any discrete constraint will always mess up the smoothness of the function (eg: less-than-g is not smooth at x=g). However, we can engineer our way around this by relaxing a discrete constraint to its closest smooth approximation! So, we can implement the less-than-g function as a sigmoid that is shifted by +/-g. This introduces a parameter to control the slope of the sigmoid. In practice, I haven't had much difficulty learning programs even with a really steep slope for the sigmoid.
The real-world computers we care about run algorithms whose semantics is given by the properties of the devices real computers use. This double meaning to "computer" has caused a lot of superstition in the ML/AI space.
Real computers are engineering devices which shuffle electrical signals around to useful devices.
There is no reason to think that "pure algorithms" have any use at all, as with, eg., a 200-dim sphere. They're only useful if they can be given a semantics which exploits useful properties of devices. (cf. with physics, where a 200-dim sphere could be useful if it models some actual system).
(2) This isn't enough. Consider learning the rules of chess; or likewise, the inference rules of mathematics. f(x) = 2x^2, f'(x) = 4x, etc.
Search spaces constructed for a grad. desc. search are very infinite; and the solutions we need are infinitely precise. Discrete approaches to search(ing for solutions) are necessary.
Are you hearing yourself talk? Do you know why you have (to just name one example out of many) thousands of pictures on your phone, and not just a few? Because of pure mathematics. Because of compression: Even JPEG2000 from back in the day uses intricate and beautiful compression algorithms based on wavelets.
1) The discrete sequencing is an epiphenomenon. The underlying processes are continuous changes in voltage and current flows. (I'm not sure if Planck scale considerations can throw a wrench in this though. Would love to be educated here.)
2) Our brains do not have ostensibly discrete neural processors. I don't think gradient descent is comparable to how the brain learns, but I think there is some reason to think that it is possible to learn symbolic processes in spite of having a processor that isn't especially built for it.
I agree that reality is fundamentally continuous. However cognition isnt; and many things arent.
A frequency is discrete. A length is continuous. These properties aren't eliminable for one another.
Here, whilst i'd agree that all physical process going on (everywhere) have essential continuous properties; they also have essential discrete ones. The issue is that grad. desc. alone does not give you the right kind of discrete ones.
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.
Don’t worry about the fact that you don’t understand anything. Just keep trying to get results. If you focus on getting results, the understanding will come to you naturally. It’s how I learned ML.
Watching presentations is nice, but tinkering with working code is so much nicer. It’s no surprise you came away feeling like you don’t actually know what you thought you knew — the only way to understand it is to go get some experience.
Also don’t worry that it takes a long time to understand something. This stuff is inherently hard. (My answer to your post is “Yes, of course I feel that way too! I don’t understand a damn thing in most presentations till I go code it myself.” So don’t feel alone!)
> 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. However, polynomial series expansions exist for |x|>1, where similar arguments would apply. Also, Taylor series and Maclaurin series aren't the same thing. A Maclaurin series is a Taylor series centered at 0.
Lastly, is "differential programming" a new term? It seems weird to me that the machine learning community continues to reinvent terminology for already existing things. What is wrong with automatic differentiation? (Not necessarily a question for the author.) It's not really a new paradigm in the sense of "logic programming", "object-oriented programming", "functional programming", etc., and is instead just a technique.
I've written some simple forward-mode automatic differentiation implementations in a few languages, and it's akin to just using a library. It doesn't seem like a paradigm to me.
Reverse-mode automatic differentiation is basically backpropagation. So again, ML seems to just like to rename things. I studied mathematics and have recently been trying to learn some ML. It's pretty annoying that a lot of mathematical terms seem to have been renamed or coopted for something else.
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 < 0.0 then dcos x else dsin (x*x - 3.0*x)
> differentiate testFunction -1.0
0.8414709848078965
> differentiate testFunction 1.0
0.4161468365471424
> differentiate testFunction 0.0
-3.0
[1] https://people.csail.mit.edu/sbangaru/projects/teg-2021/
> This "discretizes then differentiates"
Not sure what you mean. It defines dual numbers, then defines elementary functions on dual numbers (I only did two as an example). From there, you get differentiation for free (i.e., automatically). The only thing that was done manually was defining the testFunction. Everything else would be part of a library that you'd consume.
I'm not sure what you mean by "equational reasoning is broken".
Thank you for the link to the paper. Seems interesting, and I'll read through it more. Although, it is discussing differentiating integrals, which is where their language "discretize-then-differentiate" comes from. From this paper, I sort of get a sense of why differentiable programming might make sense as a concept, but I've only ever seen the term introduced with automatic differentiation, which is what I was balking at (given the content of the original post here). I'll keep reading this paper, but I think what you've mentioned before hasn't convinced me. Thanks for the discussion.
But by this argument (which sounds plausible to me) you have defeated your previous claim that differential programming is really a new paradigm, as it seems you have adopted what bmitc wrote earlier, that differential programming is not a new paradigm but "seems like automatic differentiation just implemented properly".
Analogously, I could write a program in C that does message sends and organizes code in a design pattern called "objects" and "classes". Incredibly painful, but workable sometimes. Some people even call it "object oriented C" and go on to create a library to handle it like [1]. Is object orientation not a paradigm because I've implemented a core piece as a library?
No, because that misses the intangible part of what makes a paradigm a paradigm: I structured my code this way, for a reason. In OOP, that reason is the compartmentalization of concerns. The underlying OOP mechanism gives me a way to reason about composition and substitution of components to minimize how much I have to reason about when writing code. Similarly, in differentiable programming, the differentiability of all things gives me a way to reason about the smooth substitution of things because it more easily lets me reason about how the machine writes code.
You say autodiff is actually not representative of differentiable programming. But if there aren't any other good examples that illustrate differentiable programming, how is differentiable programming (currently) more than autodiff?...
> 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.
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?
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.
Agreed about Maclaurin series.
I didn't know there existed smooth functions with divergent Taylor series. I don't understand how that happens; if we're looking at term $n$ of the Taylor series around some point $a$, it's $f^{(n)}(a) \frac{(x - a)^n}{n!}$, where $f^{(n)}$ is the nth derivative, right? I guess you could have a function whose derivatives eventually start increasing so fast that even if (x - a) is 10^{-100}, the exploding derivative eventually wins?
PARI/GP helpfully informs me that deriv(atan(x)) is 1 - x^2 + x^4 - x^6 + x^8 - x^10 + x^12 - x^14 + O(x^16), which sure sounds like the sort of thing that would diverge when |x| > 1. But presumably that's based on the Maclaurin series for arctan, and you'd get a different result if you were taking a Taylor series around 0.9 or something? In response to taylor(atan(x-9/10), x) PARI/GP says things I will not repeat here, so I guess blindly pounding on the keyboard isn't going to get me very far. Some guidance could be helpful.
I think differentiable programming is a new paradigm in the sense of logic programming and functional programming, and I do think it goes beyond just autodiff (though the linked article only explains autodiff). To the extent that a programming system is differentiable, you can use gradient descent to search for programs that minimize a loss function, not just inputs that do. But even just searching for inputs that minimize a loss function is a pretty different way to program than the conventional approach, even though Ivan Sutherland proposed it as a general approach in SKETCHPAD.
An example of a differentiable programming system is in https://arxiv.org/abs/1605.06640 "Programming with a Differentiable Forth Interpreter", 02016.
Yes, that's the point. :) In that, they're basically re-proving the binomial theorem (or more accurately, using the same method) rather than just using its results with the new dual number arithmetic.
Michael Spivak's Calculus has some great chapters on Taylor polynomials, Taylor's remainder theorem, and Taylor series. I've been looking into this stuff lately, to try and justify mathematically why automatic differentiation works (I've never read anything that does so, including several published papers), and that's where I was reminded of the fact that not everything is gold with Taylor's polynomials on real numbers. Maybe (?) the introduction of dual numbers gives something akin to complex analysis' concept of analytic. Not sure and not there yet.
> I think differentiable programming is a new paradigm in the sense of logic programming and functional programming, and I do think it goes beyond just autodiff (though the linked article only explains autodiff).
After some of the responses, maybe that's where I'm balking at. In that, I've only ever seen differentiable programming mentioned in the context of automatic differentiation. One of the papers posted led me to be more comfortable with the concept of differentiable programming as a distinct thing, in a sort of Mathematica sense, but I'll definitely need to read some more.
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 mathematical development); but I think that there is a bit of a division between computer scientists and mathematicians, so it could be that the whole machinery is mathematically already development and is now being re-development within the mantle of theoretical computer science, in and given new closing in terms of a programming language/semantics that supports the mathematics "natively". But that is more of a guess I'm having.
> One of the papers posted led me to be more comfortable with the concept of differentiable programming as a distinct thing.
Which paper was that?
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'm mainly interested in the dual number approach. With the dual number approach and forward-mode automatic differentiation, there's really no reason to overcomplicate the developing by discuss "propagating tangents". The development can be more much intuitively done because using dual numbers, automatic differentiation just falls out without discussion of propagation.
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.
> One of the papers posted led me to be more comfortable with the concept of differentiable programming as a distinct thing.
I'd still be interested in knowing which of the papera that was ;)
Quote by Pietro Majer from the link: "it is more useful to communicate the (historically non-trivial) idea that there is a difference between a function and a representation of it by means of a formula"
That said, most discussion of differentiable programming is at the level of syntax sugar for reverse mode differentiation, so I can't blame you for that conclusion.
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, unification, or the full-on Warren Abstract Machine.
If someone has a clear example of differential programming that is different than just using automatic differentiation as a technique or library, then that might help.
> 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
I'm not sure what you mean here. Could you elaborate?
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.
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...
[2] Griewank A., Walther A., Evaluating Derivatives, SIAM 2008
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
> 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 achieved
Are you sure about that? I skimmed [1] as I wasn't hadn't read it and it seems to describe a rather restricted set of functions ("types are interpreted as vector spaces and terms as functions defined by power series on these spaces"), as there are many differentiable functions that cannot be defined as power series.
Moreover, in [2] it is only claimed: "Ehrhard and Regnier {i.e. your reference [1]} do not give an operational semantics but they do give rules for symbolic differentiation and it should not be too difficult to use them to give an operational semantics. However their language with its convenient vector space semantics only supports total functions. It therefore cannot be extended to include recursive function definitions or conditionals (even with total predicates, as continuous functions from R^n to the booleans are constant)." So I would not say they cite [1] as a wistful dream ...
> There are only a few slight axiom differences that separate differential, logic, probabilistic, and quantum programming though.
Give me the axioms and their differences and I believe you. :) (Honestly, I'm not even sure if the discussion on which axiomatization captures the existing developments has been settled; it seems to me you have some kind of category theoretic approach in mind where you just change the category and get a new paradigm - I'd be happy to accept this as well, if there is a clear reference, though I'm doubtful one exists ...)
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 programming together with probabilistic programming, as they are paradigms on different "levels"
This distinction is not useful. If I write in a functional or logic programming language, it gets translated into imperative commands for an underlying architecture that is some mix of dataflow, event driven, automata-based, concurrent, etc... that is then further built on top of some physical atoms where an engineer worried about quantum effects. If I write in a quantum programming language, it will probably go through the same process for at least another 5 years. You might argue that quantum is somehow more dictated by the underlying physical model the way that people argue that imperative programming is closer to the physical world than functional programming. But the "level" doesn't change the usefulness of viewing all of these as "paradigms" worthy of study and analysis on their own terms with their own tools. At the level of studying a programming language, the "level" is a useful thing to be aware of for implementations and motivation but usually not for a theory.
> Even more so, is seems that even defining semantics for differential programming is barely in its starting stages
This is also not a useful distinction. OOP was also, infamously, a point of contention between the academic and outside worlds because it was developed and incredibly prevalent without a rigorous theory abstracting it beyond procedural programming. It became a "paradigm" despite that because there was a set of (informal) tools for reasoning about it on its own terms [1].
Likewise, differentiable programming has largely developed to formalize what makes programs written for machine learning frameworks different from programs written in the imperative/object oriented/functional language they are built on. Autodiff has mostly developed in practical usage, so the use cases are front-running the theory. There's increasingly hardware tailored to the execution model and software developers attempting to program it. There are approaches to problems like discontinuities that people have found solutions for without a rigorous theory justifying their use. There's a structure to why and how people are writing code for these applications as well as an operational theory for how to reason about it, but there's very little compositional, equational theory for these choices.
To most people in machine learning, "differentiable programming" is just autodiff with pretty syntax because the term sprung from attempting to put what they are already trying to accomplish with that implementation on more solid theoretical footing as a computable model of a more general logic. That, hopefully, lets us more efficiently explore what a better domain-specific theory might be and if there are better execution models or logical frameworks. Autodiff itself is increasingly used as an umbrella term for many other methods of differentiation with different edge cases, so this is already happening in practice.
To reduce "differentiable programming" to just its implementation ignores that aspect. It would be equivalent to equating machine learning to matrices. Not unreasonable computationally and not a terrible place to start for a theory, but deeply unsatisfying as a mature domain-specific theory.
The main paper I linked [2] is not about autodiff at all. It's an attempt to establish a connection between differentiation in an analysis sense to models of (not otherwise obviously differentiable) program evaluation. The (unrealized) promise is that the centuries of understanding we have for the calculus of infinitesimals can be applied to the less-mature study of lambda calculus and nondeterministic computation. Papers like [3] cite it because it addresses (discrete) structures that analysis is less interested in and potentially provides a way to connect computation, calculus, and whatever it is that we're doing with machine learning.
> Are you sure about that? I skimmed [1] as I wasn't hadn't read it and it seems to describe a rather restricted set of functions ("types are interpreted as vector spaces and terms as functions defined by power series on these spaces"), as there are many differentiable functions that cannot be defined as power series.
Because it's a PL theory paper, it's not concerned with whether all differentiable functions can be represented, but whether all computable functions can be differentiated. And PL theorists are generally more comfortable than most to accept that most functions cannot be computed and choose a more restrictive model that enables more reasoning power. The category [4] is really the better place to start since it lets us also consider models that aren't vector spaces and [2] is best thought of as a prototype that left many gaps in the theory (for example the requirement on coefficients for convergence is wrong, though I can't remember which paper by Lionel Vaux proved this). It can be thought of as computable in finite instances, but it's unsound even when typed due to the zero term and result of sums.
The quote you cite from [3] is easily misunderstood without that context. As a practice-focused paper, it cares very much about computability. Conditionals and loops are possible in [2] since it allows church numerals and fixed point combinators but it introduces a nondeterministic sum which is exponential in the number of evaluation steps and may diverge (doubly so since it's the untyped lambda calculus...) and is difficult to operationalize. That's what I meant by "wildly uncomputable". So, to them, [2] offers a useful mental framework for higher order features, but is not practical. The theory isn't there yet.
The connections between logic, quantum, probabilistic, and differentiable programming can be understood by how the model treats the exponential modality (!) which converts the otherwise linear term to an analytic one. Differentiation decomposes this to give a sum of linear terms. Differential lambda calculus doesn't put any (more) structure on the sum. Probabilistic programming gives the added structure of a probabilistic sum where coefficients are weights. Quantum programming can be modeled via a Fock space [5] for (!) ([5] predates [2] so is not directly discussed as a differential category here). However, it's unclear what the right model for differentiable programming should be if we want something practical for the resulting derivative (much less antiderivative). Daniel Murfet et al [6] have some related work more directly in the context of machine learning.
[1] https://www.cs.cmu.edu/~aldrich/papers/objects-essay.pdf [2] https://www.sciencedirect.com/science/article/pii/S030439750... [3] https://arxiv.org/abs/1911.04523 [4] https://ncatlab.org/nlab/show/differential%20category [5] https://www.researchgate.net/publication/2351750_Fock_Space_... (sadly a researchgate link) [6] http://therisingsea.org
I did read it ;) Because I'm very much interested in this entire topic.
> I hope I can encourage you to think more broadly about what "differentiable programming" means
I'm trying to, but I find it hard. My stance was that differentiable programming seemes like this theory for which only a single example (namely autodiff) existed, as you also said ("autodiff has mostly developed in practical usage, so the use cases are front-running the theory"). But this entire comment of yours really clarified some things for me.
> The main paper I linked [2] is not about autodiff at all. >The quote you cite from [3] is easily misunderstood without that context
You finally convinced me to have a detailed look at this. Thank you for providing the context.
> Conditionals and loops are possible in [2] since it allows church numerals and fixed point combinators but it introduces a nondeterministic sum [...] and is difficult to operationalize. That's what I meant by "wildly uncomputable".
I think I may have misunderstood some of your previous comments (and perhaps vice versa) as it now dawns on me that you use a vocabulary than comes (I guess?) from PL theory and is very different from the one I'm used to, as a mathematician versed in analysis. I'll re-read them.
> Daniel Murfet et al [6] have some related work more directly in the context of machine learning.
I'm actually aware of Daniel Murfet but haven't read his work from last years. Did you have a specific paper from him in mind?
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.
This issue creeps in a lot but I think it comes from the complex analysis, where differentiable function is always smooth and analytic (holomorphic).
The issue primarily revolves around elementary functions, compositions of them, and polynomials.
Differentiable Programming – A Simple Introduction | 159 points, 3 months ago, 49 comments | https://news.ycombinator.com/item?id=31000709
There I mention "The simple essence of automatic differentiation" which posits that by keeping the a differentiated function paired together with its integrand then many functional transformations -- including integration, subexpression deduplication, and even automatic conversion from forward mode to reverse mode -- would be greatly simplified. Allegedly this claim is not backed up by a practical demonstration yet, but imo this is a very intriguing approach.
I understand the specific case of numerical functions, it may make sense if you just want to tweak some parameters a bit like a nn, or for example in quantum diff programming people seem to tweak parameters in some Hamiltonian.
What I actually want is something you will actually change the structure of the program somehow.
If you pretend the entire program is a function f, parameters are just points on your program. Why is moving to different points differentiating. Differentiating is producing a new function f’.
In the case of the NN it makes sense to select different points. But then we do also modify the structure with dropouts etc.