3 ms·

Better example would be symbolic differentiation[1][2] which requires more quirks even in modern languages[3][4] [1] https://mitpress.mit.edu/sicp/full-text/si

by ungzd 9y ago

Better example would be symbolic differentiation[1][2] which requires more quirks even in modern languages[3][4] [1] https://mitpress.mit.edu/sicp/full-text/sicp/book/node39.html https://mitpress.mit.edu/sicp/full-text/sicp/book/node39.htm... [2] https://github.com/clojure-numerics/expresso https://github.com/clojure-numerics/expresso [3] http://docs.sympy.org/latest/tutorial/intro.html#a-more-interesting-example http://docs.sympy.org/latest/tutorial/intro.html#a-more-inte... [4] https://github.com/yuemingl/SymJava#examples https://github.com/yuemingl/SymJava#examples

vog 9y ago
Note that the simplistic approach doesn't scale well, as terms tend to "explode" in size and hence computation time. There is a whole sub field of mathematics / computer science called "algorithmic differentiation", also known as "automatic differentiation". The goal is to take an existing computer program and transform it into another computer program that calculates the derivatice just as efficiently (up to a constant factor of ~2 to 5, depending on how you measure), and with about the same numeric stability (by usual measures). And this is just the start. Classic differentiation is also called "forward" mode. Understanding the "reverse mode", and why you want this for gradients, is even more mind-bending. There is a whole world to discover here. The book "Evaluating Derivatives" is a good starting point for anyone interested. http://epubs.siam.org/doi/book/10.1137/1.9780898717761 http://epubs.siam.org/doi/book/10.1137/1.9780898717761 There are also many of beautiful papers on that topic.
- conistonwater 9y ago
  It doesn't stop at forward-mode, and reverse-mode, because finding the optimal mode relates to a complicated graph problem, which, IIRC, is NP-hard in general. Not only that, but most of the difficulty is in getting these tools to work on arbitrary codebases, making it more a software engineering problem rather than a maths problem.
  - vog 9y ago
    > It doesn't stop at forward-mode, and reverse-mode, because finding the optimal mode relates to a complicated graph problem, which, IIRC, is NP-hard in general. Yes, there are combined forward-reverse-mode approaches as well as "cross country" approaches. That's in part of what I menat with a "whole world to discover". > Not only that, but most of the difficulty is in getting these tools to work on arbitrary codebases, making it more a software engineering problem rather than a maths problem Depending on your viewpoint, it is neither SE nor math, but a PL (programming languages) issue, meaning that viewing the program e.g. as register machine (classic assembly) yields to different approaches than viewing it as lambda calculus expression (which provided great results, but it is hard to transport the results back to languages like Fortran or C++).
- dreamcompiler 9y ago
  Exactly. I've just started exploring dual numbers which are needed for automatic differentiation [0]. It's mind-blowing stuff, and it's easy to code in Lisp. [0] https://en.m.wikipedia.org/wiki/Dual_number https://en.m.wikipedia.org/wiki/Dual_number
- monochromatic 9y ago
  What do you mean by reverse mode? I assumed integration, but that doesn't seem to be what you're talking about.
  - conistonwater 9y ago
    It's also sometimes called adjoint mode. See this: https://en.wikipedia.org/wiki/Automatic_differentiation#Reverse_accumulation https://en.wikipedia.org/wiki/Automatic_differentiation#Reve...

by ungzd 9y ago

vog 9y ago

Note that the simplistic approach doesn't scale well, as terms tend to "explode" in size and hence computation time. There is a whole sub field of mathematics / computer science called "algorithmic differentiation", also known as "automatic differentiation". The goal is to take an existing computer program and transform it into another computer program that calculates the derivatice just as efficiently (up to a constant factor of ~2 to 5, depending on how you measure), and with about the same numeric stability (by usual measures). And this is just the start. Classic differentiation is also called "forward" mode. Understanding the "reverse mode", and why you want this for gradients, is even more mind-bending. There is a whole world to discover here. The book "Evaluating Derivatives" is a good starting point for anyone interested. http://epubs.siam.org/doi/book/10.1137/1.9780898717761 http://epubs.siam.org/doi/book/10.1137/1.9780898717761 There are also many of beautiful papers on that topic.

conistonwater 9y ago
It doesn't stop at forward-mode, and reverse-mode, because finding the optimal mode relates to a complicated graph problem, which, IIRC, is NP-hard in general. Not only that, but most of the difficulty is in getting these tools to work on arbitrary codebases, making it more a software engineering problem rather than a maths problem.
- vog 9y ago
  > It doesn't stop at forward-mode, and reverse-mode, because finding the optimal mode relates to a complicated graph problem, which, IIRC, is NP-hard in general. Yes, there are combined forward-reverse-mode approaches as well as "cross country" approaches. That's in part of what I menat with a "whole world to discover". > Not only that, but most of the difficulty is in getting these tools to work on arbitrary codebases, making it more a software engineering problem rather than a maths problem Depending on your viewpoint, it is neither SE nor math, but a PL (programming languages) issue, meaning that viewing the program e.g. as register machine (classic assembly) yields to different approaches than viewing it as lambda calculus expression (which provided great results, but it is hard to transport the results back to languages like Fortran or C++).
dreamcompiler 9y ago
Exactly. I've just started exploring dual numbers which are needed for automatic differentiation [0]. It's mind-blowing stuff, and it's easy to code in Lisp. [0] https://en.m.wikipedia.org/wiki/Dual_number https://en.m.wikipedia.org/wiki/Dual_number
monochromatic 9y ago
What do you mean by reverse mode? I assumed integration, but that doesn't seem to be what you're talking about.
- conistonwater 9y ago
  It's also sometimes called adjoint mode. See this: https://en.wikipedia.org/wiki/Automatic_differentiation#Reverse_accumulation https://en.wikipedia.org/wiki/Automatic_differentiation#Reve...