6 ms·

You don't need induction for (x+x'e)^n+1. The binomial formula can be applied once the arithmetic on dual numbers is introduced. > We can use this result to pr

• adgjlsfhk1 4y ago
  The idea behind the term "differential programming" is that many traditional autodiff systems force you into a highly restricted subset of the language or DSL (e.g. no loops, no if statements etc). Differential programming is a term used to describe systems that let you take derivatives of your entire source code. This lets you do things like AD through a simulation or optimization algorithm which can be really powerful for applying ML techniques to domains that are less typically suited to ML approaches (circuits, physics, differential equations etc)
  • bmitc 4y ago
    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 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.
    • oddity 4y ago
      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.
      • bmitc 4y ago
        > Autodiff does not work with for loops or if statements. Is that necessarily true? Here is an incomplete automatic differentiation implementation that handles if statements just fine in a function definition. Unless you mean something else. type Dual = {Real: float; Epsilon: float} with static member (~-) (x: Dual) = {Real = -x.Real; Epsilon = -x.Epsilon} static member (+) (x: Dual, y: Dual) = { Real = x.Real + y.Real Epsilon = x.Epsilon + y.Epsilon } static member (+) (x: Dual, c: float) = {x with Real = x.Real + c} static member (+) (c: float, y: Dual) = {y with Real = c + y.Real} static member (-) (x: Dual, y: Dual) = x + (-y) static member (-) (x: Dual, c: float) = x + (-c) static member (-) (c: float, y: Dual) = c + (-y) static member (*) (x: Dual, y: Dual) = { Real = x.Real * y.Real Epsilon = x.Real * y.Epsilon + x.Epsilon * y.Real } static member (*) (c: float, y: Dual) = {Real = c; Epsilon = 0} * y static member (*) (x: Dual, c: float) = x * {Real = c; Epsilon = 0} let dcos (x: Dual) = {Real = cos x.Real; Epsilon = -(sin x.Real) * x.Epsilon} let dsin (x: Dual) = {Real = sin x.Real; Epsilon = (cos x.Real) * x.Epsilon} let differentiate (f: Dual -> Dual) a = let x = f {Real = a; Epsilon = 1.0} x.Epsilon let testFunction (x: Dual) = if x.Real < 0.0 then dcos x else dsin (x*x - 3.0*x) Using that gives: > differentiate testFunction -1.0 0.8414709848078965 > differentiate testFunction 1.0 0.4161468365471424 > differentiate testFunction 0.0 -3.0 Now, of course, one needs to be careful interpreting the result at a = 0.0. That's because the testFunction is not differentiable at that point due to a jump discontinuity there, but we still get a value back. But as far as I know, this is simply an issue with automatic differentiation in that it only correctly tells you what the derivative is if it exists at the given point.
  • data_maan 4y ago
    Mathematician here. > Differential programming is a term used to describe systems that let you take derivatives of your entire source code. I think the way this is stated is incorrect. What would the derivative of a program that outputs the reverse the input string be? It would be meaningless. It seems rather to be the case that it describes systems that let you take derivatives of your entire source code where that source code describes a numerical function. Perhaps it is obvious to state this, but I keep seeing differentiable programming being described as "taking a derivative of the source code" and it seems annoyingly imprecise. > This lets you do things like AD through a simulation or optimization algorithm This is also, taken literally, not a correct statement. It's not the algorithm which you want to differentiate, but a hard-to-differentiate function within the algorithm (which is always a gradient-descent type algorithm, as it otherwise makes no sense to consider derivatives; there is the entire domain of derivative-free optimization BTW). So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously.
    • radarsat1 4y ago
      > So, in case of (stochastic) gradient descent to train a neural network, that would be the neural network that you want to use AD on, not the gradient descent algorithm. Obviously. The specific proposal of differential programming as a paradigm that goes beyond simple applications of gradient descent for optimising NNs is exactly to apply gradient descent to optimise learning (and other) algorithms themselves. This may be to select hyperparameters, or to select among a family of algorithms, or to include differentiable constraints in the solver, etc. I wonder, are you familiar with now classic paper, Learning to learn by gradient descent by gradient descent? [0] https://arxiv.org/abs/1606.04474 https://arxiv.org/abs/1606.04474
      • selestify 4y ago
        Wow, it’s interesting that a paper from 2016 is already classic. This field moves fast!
        • deleted 4y ago
• oddity 4y ago
  Object oriented programming, for example, doesn't let me have a variable hold half of one object and half of another or let the language derive the code that gave me that object at runtime, but object oriented + differentiable programming does. It's no less of a paradigm than logic, quantum, or probabilistic programming. If you want to, you can view differentiable programming as extending logic programming with a product and chain rule (+ some additional constraints) that allows (smooth, if you want it) interpolation between data and code. 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.
  • bmitc 4y ago
    You don't need OOP plus another paradigm to do automatic differentiation though. I've implemented automatic differentiation, albeit "simple" versions and only forward-mode at this point, but there's really nothing special about the implementations. Logic programming, on the other hand and for example, needs something much more substantial to be implemented as a library in an existing language, such as backtracking, 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?
    • oddity 4y ago
      I don't need OOP to do a hash table lookup and then an indirect function call with the receiver as the first argument either but that ignores that there's more to a paradigm than the algorithm I use for facilitating it. You can embed unification of expression trees as a library in C++. People implement backtracking all the time in almost every language. Talking about differentiable programming as if it's just autodiff is missing the point of what a programming paradigm is. There's a mechanism, yes, but that's just a means to an end of efficiently enabling a different way of approaching programming. In the case of differentiable programming, that's continuous code and continuous data enabling program search that doesn't have to use purely discrete methods (like logic programming). If that sounds like autodiff and backprop, then yes, that's because that's a good way to implement it. Tensorflow and PyTorch are DSLs embedded in Python and C++ both useable and used for more than just implementing neural networks, but most people aren't happy calling a library a language until it has a parser and a file extension. > I'm not sure what you mean here. Could you elaborate? Most programming languages assume that a variable can only contain one value, or a composite value of values. Differentiable programming lets code be smoothly transformed from one to the other while being meaningful at all points between. In an object oriented case, this would be like having a variable contain an object that behaves like some known object A or object B selectively depending on which choice maximizes the success of the program at any given moment.
• deleted 4y ago
  [deleted]
• kragen 4y ago
  Agreed about the binomial formula, but don't you need induction to prove the binomial theorem? That is, if you have some sort of set that's like the naturals except that Peano's axiom of induction doesn't apply (such as the naturals plus Alberto and Cristina, who are one another's successors) is the binomial theorem necessarily true in it? 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 https://arxiv.org/abs/1605.06640 "Programming with a Differentiable Forth Interpreter", 02016.
  • bmitc 4y ago
    > Agreed about the binomial formula, but don't you need induction to prove the binomial theorem? 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.
• ithinkso 4y ago
  > That's not exactly true. For example, arctan = tan^-1 is smooth on R, but its Taylor series only converges for |x|<=1. This issue creeps in a lot but I think it comes from the complex analysis, where differentiable function is always smooth and analytic (holomorphic).
  • bmitc 4y ago
    But as far as I know, there is no corresponding dual analysis. The dual numbers do not form a field. The issue primarily revolves around elementary functions, compositions of them, and polynomials.
    • ithinkso 4y ago
      Yeah, I was only trying to explain where the issue (assuming smooth=analytic, that you rightfully pointed out) might have come from
      • bmitc 4y ago
        Ahh, gotcha. I'm trying to figure this out myself. I've always been intrigued by automatic differentiation but have never been satisfied by any article addressing its mathematical justification.
        • data_maan 4y ago
          Neither have I ...