You'd be surprised how many applications are using techniques for optimization that not only work poorly but require more work. Many programmers, academics, and students who browse HN may benefit from AD but don't know about it.
At the time this post was written, there was no good autodiff implementation for any language that anyone actually used for ML, meaning Python, Matlab, or Java. That's changed now; for example, Python autograd [1] is quite seamless and plays well with the entire Numpy stack.
The bigger trend, though, has been towards DSLs such as Theano or Tensorflow (and Torch to a lesser degree) that include autodiff as a first class design consideration. The ability to build complicated networks out of modular parts, and have the gradient calculations automatically fall out, has been a major driver of the recent explosive progress in deep learning research, as has easy portability between CPU and GPU execution. It'll be exciting to see what happens as these tools mature and especially if they find applications in other fields.
Can someone further clarify the distinction between automatic and symbolic differentiation?
The author claims that using symbolic differentiation on his example (f(x)=sin(x+sin(x+...+sin(x+sin(x))...))) builds a "huge expression that would take much more time to compute" than automatic differentiation. At the top of the article there's also an update noting an "explosion of great tools for automatic differentiation" recently, which I assume is referring to machine/deep learning frameworks like Theano, TensorFlow, etc. However, from my understanding, building an entire computational graph to express the gradient via the chain rule (backpropagation) is exactly what these frameworks do, and by the author's brief description that seems to fall under symbolic differentiation. So which one are these frameworks doing -- symbolic or automatic differentiation? And, concretely, how would they differ if they were instead doing the other one?
Edit: I've been doing some further reading trying to understand this, and it's only confusing me further. Wikipedia has this diagram [1] which supposedly illustrates the relationship between the two -- what the hell is going on here? The only interpretation I can come up with from it is that automatic differentiation takes code (written in a computer programming language) as input and produces code to compute the gradient, whereas in symbolic differentiation, the input and output are mathematical expressions. But this doesn't seem like a meaningful distinction to me...both math and computer code are languages; functions written in programming languages are mathematical functions (the ones that can actually be correctly called "functions", anyway). Someone please help me out here; what am I missing?
- with numerical differentiation, you take an algorithm to approximate a function, you repeatedly evaluate that, and you use the results to approximate the derivative
- with symbolic differentiation, you take a symbolic, exact representation of a function (which you could evaluate with floating-point numbers to approximate its values if you wanted to use numerical differentiation instead), and you apply rules like linearity and the product rule to get a symbolic, exact representation of the derivative, which you evaluate with floating-point numbers to approximate the derivative
- with automatic differentiation, you take an algorithm to approximate a function, which must be implemented using basic floating-point operations, and you apply rules like linearity and the product rule to the operations used to implement the approximation, and you get an algorithm that approximates the function's derivative
Put another way, when people say they're using symbolic or automatic differentiation to "calculate" the derivative of a function, "calculate" means different things: in the one, they're "calculating" the exact, symbolic expression for the derivative (which can optionally be evaluated); in the other, they're "calculating" the floating-point approximation of the values of the derivative.
To me, automatic differentiation is GENIUS. My friend, who's written a Julia package [1] based on some of the ideas behind automatic differentiation, introduced me to them; unfortunately, according to him, numerical differentiation is usually more practical. I don't remember why but I'm going to ask him.
> Put another way, when people say they're using symbolic or automatic differentiation to "calculate" the derivative of a function, "calculate" means different things: in the one, they're "calculating" the exact, symbolic expression for the derivative (which can optionally be evaluated); in the other, they're "calculating" the floating-point approximation of the values of the derivative.
If this is correct, then both Theano and TensorFlow are definitely doing symbolic differentiation, no? The `grad` function in Theano (and the equivalent in TF, not sure what it's called) takes a computation graph (a symbolic expression of a mathematical function) as input and produces a computational graph expressing the gradient (which as you said, can then optionally be evaluated at specified points). So maybe the author wasn't referring to these types of frameworks when he said there have recently been an explosion of these autodiff tools? Or are Theano and TF and the like, in fact, autodiff tools as opposed to "symdiff" tools, but I'm still missing the point somehow?
It's not correct. They are doing AD, not symbolic differentiation.
Think of AD as evaluating the derivative step-by-step as you proceed through the program (or nodes in the expression graph in Theano's model). In contrast, symbolic differentiation instead would be to evaluate the entire program in terms of symbolic variables to produce a final expression for your quantity of interest as a function of the inputs, then differentiating that and substituting concrete values in.
> In contrast, symbolic differentiation instead would be to evaluate the entire program in terms of symbolic variables to produce a final expression for your quantity of interest as a function of the inputs, then differentiating that and substituting concrete values in.
This describes Theano exactly though... You build up a static, symbolic computation graph representing a mathematical function, and then you can call theano.tensor.grad(...) on that graph to get another computation graph, a symbolic representation of the gradient. Everything is completely symbolic at this point -- you could prettyprint the computation graph output by Theano's `grad` function and get exactly what symbolic differentiation seems to give you. You can then call theano.function(...) on either of those graphs to get an actual (Python) function which you can substitute concrete values into.
edit: in fact, Theano's own docs on its gradient-related functions [1] call it "symbolic differentiation" right at the top.
edit2: I decided to try this on the author's sin(x+...) example he uses as a pathological case for symbolic differentiation. Theano has exactly the behavior he warned that symbolic differentiation has -- you get a symbolic expression whose size grows with the loop range. It's quite large even with a size of 3 [2] (let alone 100).
import theano
from theano import tensor as T
def f(x):
y = x
for i in range(3):
y = (x + y).sin()
return y
x = T.scalar(name='x')
my_function = f(x)
print "my_function =", theano.pprint(my_function)
my_gradient = T.grad(my_function, x)
print "my_gradient =", theano.pprint(my_gradient)
Is that blowup perhaps an artifact of displaying the result as an expression, but where the result as an internal data structure is more compact, because of sharing? That's what I'd expect, although I haven't tried Theano yet.
That is, I'd expect the sin((x + x)) which appears twice to be just one internal node which is referenced twice, and so on.
That's my understanding, it does not compute the expression directly unless you ask it to. Could be wrong though, I've only used it a few times.
AD does involve symbolic differentiation of each individual instruction, but instead of keeping the symbolic expression it is replaced with the numeric value, so the whole expression is never computed. It isn't magic and there are cases where it blows up. For instance, there are two basic ways to implement it, forward and backward propagation, each of which is good for a certain situation that the other is terrible at.
As pointed out by others, the blowup is an artifact of the visual representation, under-the-hood Theano does automatic differentiation (which they consider to be an optimization on symbolic differentiation, which is why they keep calling it that):
> In this way Theano can be used for doing efficient symbolic differentiation (as the expression returned by T.grad will be optimized during compilation), even for function with many inputs. (see automatic differentiation for a description of symbolic differentiation).
You can think of AD as differentiating a function that is defined in terms of composition... e.g. f(g(h(x))), where (loosely) x is the initial state of your function and f, g, and h are differentiable mappings from one state to another. In this analogy, in a procedural language f, g, and h would be lines in your source code, which modify the overall program state to produce some final value. There are a few different ways to actually do it (including the rather tricky concept of "dual numbers"), but ultimately it amounts to differentiating the overall program f(g(h(x)) recursively using the chain rule. It's [often] more efficient than direct symbolic differentiation because of this recursive evaluation - think of it as something like tail-call optimization.
It's not an approximate method, nor does it care [directly] about floating point. If you have implemented some f' that approximates a mathematical function f and you use AD to differentiate f', you are calculating the exact derivative of f', not an approximation of the derivative of f. It's an important distinction.
I found dual numbers pretty intuitive, but I was a math major and studied abstract algebra and stuff, that way of thinking is definitely an acquired taste.
To be clear, when you say f' you're not talking about Newton's notation for the derivative of f, you're talking about a function from floats to floats that is the approximation/algorithmic implementation of f (which is R->R), right?
I don't really see why the distinction is particularly important. The reason the exact derivative of f' that you get from AD is useful is because it also approximates the derivative of f, right? If it were possible to make some pathological choice of f' (that is, algorithmic implementation of f) such that the result from AD is a poor approximation of the derivative of f, that's not really a successful use of AD on f, right? So when I say I'm gonna "use AD to get a derivative of f", I'm really saying I'm going to use AD on a good choice of an approximation of f to get a good approximation of the derivative of f, right?
I suppose if infinite precision analog computing were possible, or in the context of theoretical real-valued register machines (does anyone still study that?), it matters that AD is exact on the algorithmic implementation, but we're not in or anywhere near those contexts, are we?
> To be clear, when you say f' you're not talking about Newton's notation for the derivative of f, you're talking about a function from floats to floats that is the approximation/algorithmic implementation of f (which is R->R), right?
Yep. I probably should have used f* instead of f' because of context. R->R isn't necessary however, it should generalize quite a bit.
As to why the distinction is important, it's because of sensitivity. Approximating a function rarely also approximates its derivative well unless it is constructed to do so (e.g. k-th order Hermite polynomials). As an example, consider the simplest approximation scheme, basic polynomial fitting. They will guarantee that your fit matches the true function at all sample points, but the derivative might (and usually will) be wildly different. You have to be extremely careful differentiating approximate schemes and relating them to the true derivative. Usually what you're interested in for AD is the derivative of the approximate scheme and not an approximate derivative for the exact function (e.g., sensitivity analysis).
And I agree that dual numbers are intuitive to me as well, but I think it requires a decent bit of background as to why they work.
At the bottom it computes both the value and the derivative of x^3 at x=2. x^3 is 8 and 3x^2 is 12.
For comparison, symbolic differentiation is implemented halfway down http://norvig.com/paip/macsymar.lisp where there are the rules you learn in calculus class, lines like
(d (u + v) / d x = (d u / d x) + (d v / d x))
which means code that looks at the formula as source code and rewrites it. It blows up in the example the OP brings up, because it's working on an expression instead of on a DAG; I think if you made up a DAG-adapted symbolic differentiator it could output a compact sequence of formulas for the derivative, though I haven't tried it. It should be equivalent to symbolically evaluating the code from autodiff.py.
> I think if you made up a DAG-adapted symbolic differentiator
That's essentially what autodiff is. It works on the DAG, whereas "symbolic" diff insists that the DAG is a tree (so reused components have to be duplicated, which leads to blowup).
Yes, that's one way to look at it. However, here's a Python symbolic differentiator I just coded now to make a more direct comparison, since Norvig's Lisp is very different from my Python in lots of distracting ways: https://github.com/darius/sketchbook/blob/master/misc/symbdi...
This symbolic differentiator could be made to not blow up, by memoizing, i.e. decorating with https://github.com/darius/sketchbook/blob/master/regex/memo.... . It'd still have the difference that it constructs an explicit formula in x, as a data structure; the autodiff code instead takes a particular x as input and calculates a value for just that x, where the value includes both an 'actual value' and a 'derivative' component. (Your library and compiler could get fancy and inline that computation at compile time back into a pair of formulas, and then yes, they ought to be exactly equivalent.)
Thanks, these posts are the only thing I've read that have made sense to me thus far (probably because they mostly confirm my suspicion, that there's not really a strong distinction between 'symbolic' and 'automatic' differentiation, but there are perceived differences based on whether the computation graph is compiled and optimized, and whether the graph is pretty-printed at some point...). Your Python symbolic differentiator is exactly a mini-Theano (or a mini-any deep learning framework). Each `Function` instance (or `Op` in Theano) defines its output and gradient with respect to its input (given gradient wrt output).
If this code is correct(and it appears to be), then it show to me that a small portion of code explains this idea much better than the dozens of explanations I found on the internet.
The frustrating part is reading lots of words/math formulas explanations without understanding them and then seeing some diagram/executable code and thinking "that's it? so many hours wasted try to understand something so simple.. why didn't you draw a diagram? why didn't you show some executable code? WHY?!"
Thanks for commenting -- I've had that feeling too, of frustration on struggling with some wodge of formulas bedecked with indices and weighted with implicit assumptions of unclear scope. Modern programming languages can usually express these things about as concisely, with the great advantage that you can engage with the code and it'll push back. You wonder "why isn't it this way?" and just try it.
Symbolic differentiation is what you learned in school and do by hand. Automatic differentiation is, as far as I understand it, you take your nice function, develop it into a Taylor series around x:
f(x + h) = f(x) + f'(x) h + f''(x) h^2 / 2 + ...
Suppose that f is a really, really nice function (defined and holomorphic in a large enough domain in the complex numbers and a Taylor expansion with real coefficients). The curious thing happens when you think of h as just an indeterminate and you evaluate it, for instance, at i s, where i =sqrt(-1) and s is a tiny number. Then
This means you can compute the derivative with an O(s^2) error just by evaluating at a complex number. The only thing needed was that all operations are implemented not just for real numbers but complex numbers.
Instead of the R-algebra R[i] = C, why not try to use the R-algebra R[ε] and evaluate at ε, where ε is a symbol with ε^2 = 0? Remember, i is also just a symbol with the property i^2 = -1!!!
f(x + ε) = f(x) + f'(x) ε + f''(x) ε^2/2 + ...
Since 0 = ε^2 = ε^3 = ..., all higher order terms vanish and you get
f'(x) = coefficient of ε in f(x + ε).
(Compare with the complex numbers: Im = "coefficient of i" but this time around, there is no error)
Everything that you need is to know how to implement arithmetic operations for numbers in R[ε], e.g.
(a+b ε) + (c + d ε) = (a+c) + (b+d) ε
(a+b ε) (c + d ε) = ac + (ad + bc) ε + bd ε^2 = ac + (ad + bc) ε
A problem occurs when you try to divide by ε. This is simply undefined in R[ε], which, unlike C is not a field. But not all is lost, suppose you want to divide (a + b ε) by (c + d ε), where c is not 0, then
(a+b ε) / (c + d ε) = (a + b ε) (c - d ε) / (c^2 + (-cd + cd) ε) = something with ε in the numerator / c^2,
That is, division by ε only occurs when you divide by 0 in the first place.
To recapitulate: If you have a class DualNumber with overloaded +, -, * , /, ^, you can find the derivative of, say, the fourth-order approximation of e^x at x = 0.5, by computing
Symbolic calculates the symbolic representation of the derivative, autodiff just calculates the (numerical value of the) derivative by adjusting the computation graph.
I had a need for this in an unrelated problem area - ragdoll physics. In 1996-1997 I came out with Falling Bodes, the first ragdoll physics system that worked right. It was a spring-damper system, not an impulse-constraint system like most game engines; this produces more accurate and better looking collisions, but is more expensive computationally. So it was used as an animation tool, not for games.
The rigid body dynamics system used Featherstone's algorithm. This models a tree of links and joints, a skeleton. You put in forces and torques at each joint, and the algorithm computes accelerations at each joint and the root node. Those accelerations then have to be integrated to get velocities and positions. As positions change, so do contact forces. If you don't want to get interpenetration in collisions, the contact forces must be allowed to become very large. We used exponential springs as the contact model to achieve this.
Numerically, this means integrating a very stiff system of differential equations. Explicit integration, like Runge-Kutta 4, works, but you have to monitor the error term and cut the time step when necessary. During the early parts of a hard collision, the time step may have to drop into the microsecond range. This is why this approach doesn't work well for games; it's not constant-time. (If you don't cut the time step, your simulation goes "sprong", and things go flying off into space. Some games still do this.)
An alternative is to use implicit integration, where you work backwards to solve the next step to be consistent with the previous one. Implicit integration works with larger timesteps on stiff systems. (There's still error, but it acts in the direction of draining energy from the moving system, which is much better than adding it.) This requires gradients of the function that the Featherstone algorithm is computing. The brute-force approach is to compute the gradients (the Jacobian) by perturbing each input by a small amount, running the Featherstone algorithm, measuring the differences, and obtaining the slopes numerically. This is slow.
Ideally, you'd like to have analytical Jacobians. That's where automatic differentiation would help. Differentiating Featherstone's algorithm analytically is hard, but might be possible today.
We used SD/Fast, which is a C code generator for Featherstone's algorithm. Straightforward implementations of Featherstone have lots of switches and conditionals as they deal with the topology of the skeleton being simulated. SD/Fast took in the link and joint description and turned out C code for that structure. This gets rid of most of the conditionals. It unwound the code more than you'd want to do today; there was much loop unrolling at the source level. (Before superscalar CPUs, unwinding loops was a win; today, tiny tight loops are a win.)
Anyway, it's possible that the tools being developed in machine learning could be applied to game physics in that way. At the visual level, the difference is that big objects bounce like big objects, with slower collision rebound times. In impulse-constraint systems, all bounces are instantaneous, which is why, in video games, everything seems to be too light.
The caveats are worth reading before the rest of it. How long does it take to write down the derivative of a loss function, compared to trusting that your automatic diff did what you expected? I can tell you: not long.
30 comments
[ 3.5 ms ] story [ 76.9 ms ] threadhttp://ceres-solver.org/index.html
[0] https://en.wikipedia.org/wiki/PROSE_modeling_language
The bigger trend, though, has been towards DSLs such as Theano or Tensorflow (and Torch to a lesser degree) that include autodiff as a first class design consideration. The ability to build complicated networks out of modular parts, and have the gradient calculations automatically fall out, has been a major driver of the recent explosive progress in deep learning research, as has easy portability between CPU and GPU execution. It'll be exciting to see what happens as these tools mature and especially if they find applications in other fields.
[1] https://github.com/HIPS/autograd
Some resources for Common Lisp I found:
- AD in Lisp paper: http://www.cs.berkeley.edu/~fateman/papers/ADIL.pdf
- A library: https://github.com/masonium/cl-autodiff (basics seem to work, but it definitely could use some love to grow)
The author claims that using symbolic differentiation on his example (f(x)=sin(x+sin(x+...+sin(x+sin(x))...))) builds a "huge expression that would take much more time to compute" than automatic differentiation. At the top of the article there's also an update noting an "explosion of great tools for automatic differentiation" recently, which I assume is referring to machine/deep learning frameworks like Theano, TensorFlow, etc. However, from my understanding, building an entire computational graph to express the gradient via the chain rule (backpropagation) is exactly what these frameworks do, and by the author's brief description that seems to fall under symbolic differentiation. So which one are these frameworks doing -- symbolic or automatic differentiation? And, concretely, how would they differ if they were instead doing the other one?
Edit: I've been doing some further reading trying to understand this, and it's only confusing me further. Wikipedia has this diagram [1] which supposedly illustrates the relationship between the two -- what the hell is going on here? The only interpretation I can come up with from it is that automatic differentiation takes code (written in a computer programming language) as input and produces code to compute the gradient, whereas in symbolic differentiation, the input and output are mathematical expressions. But this doesn't seem like a meaningful distinction to me...both math and computer code are languages; functions written in programming languages are mathematical functions (the ones that can actually be correctly called "functions", anyway). Someone please help me out here; what am I missing?
[1] https://en.wikipedia.org/wiki/Automatic_differentiation#/med...
- with numerical differentiation, you take an algorithm to approximate a function, you repeatedly evaluate that, and you use the results to approximate the derivative
- with symbolic differentiation, you take a symbolic, exact representation of a function (which you could evaluate with floating-point numbers to approximate its values if you wanted to use numerical differentiation instead), and you apply rules like linearity and the product rule to get a symbolic, exact representation of the derivative, which you evaluate with floating-point numbers to approximate the derivative
- with automatic differentiation, you take an algorithm to approximate a function, which must be implemented using basic floating-point operations, and you apply rules like linearity and the product rule to the operations used to implement the approximation, and you get an algorithm that approximates the function's derivative
Put another way, when people say they're using symbolic or automatic differentiation to "calculate" the derivative of a function, "calculate" means different things: in the one, they're "calculating" the exact, symbolic expression for the derivative (which can optionally be evaluated); in the other, they're "calculating" the floating-point approximation of the values of the derivative.
To me, automatic differentiation is GENIUS. My friend, who's written a Julia package [1] based on some of the ideas behind automatic differentiation, introduced me to them; unfortunately, according to him, numerical differentiation is usually more practical. I don't remember why but I'm going to ask him.
[1]: https://github.com/jwmerrill/PowerSeries.jl
If this is correct, then both Theano and TensorFlow are definitely doing symbolic differentiation, no? The `grad` function in Theano (and the equivalent in TF, not sure what it's called) takes a computation graph (a symbolic expression of a mathematical function) as input and produces a computational graph expressing the gradient (which as you said, can then optionally be evaluated at specified points). So maybe the author wasn't referring to these types of frameworks when he said there have recently been an explosion of these autodiff tools? Or are Theano and TF and the like, in fact, autodiff tools as opposed to "symdiff" tools, but I'm still missing the point somehow?
Think of AD as evaluating the derivative step-by-step as you proceed through the program (or nodes in the expression graph in Theano's model). In contrast, symbolic differentiation instead would be to evaluate the entire program in terms of symbolic variables to produce a final expression for your quantity of interest as a function of the inputs, then differentiating that and substituting concrete values in.
This describes Theano exactly though... You build up a static, symbolic computation graph representing a mathematical function, and then you can call theano.tensor.grad(...) on that graph to get another computation graph, a symbolic representation of the gradient. Everything is completely symbolic at this point -- you could prettyprint the computation graph output by Theano's `grad` function and get exactly what symbolic differentiation seems to give you. You can then call theano.function(...) on either of those graphs to get an actual (Python) function which you can substitute concrete values into.
edit: in fact, Theano's own docs on its gradient-related functions [1] call it "symbolic differentiation" right at the top.
edit2: I decided to try this on the author's sin(x+...) example he uses as a pathological case for symbolic differentiation. Theano has exactly the behavior he warned that symbolic differentiation has -- you get a symbolic expression whose size grows with the loop range. It's quite large even with a size of 3 [2] (let alone 100).
[1] http://deeplearning.net/software/theano/library/gradient.htm...
[2]
->my_function = sin((x + sin((x + sin((x + x))))))
my_gradient = ((((fill(sin((x + sin((x + sin((x + x)))))), TensorConstant{1.0}) * cos((x + sin((x + sin((x + x))))))) [... much much more]
That is, I'd expect the sin((x + x)) which appears twice to be just one internal node which is referenced twice, and so on.
AD does involve symbolic differentiation of each individual instruction, but instead of keeping the symbolic expression it is replaced with the numeric value, so the whole expression is never computed. It isn't magic and there are cases where it blows up. For instance, there are two basic ways to implement it, forward and backward propagation, each of which is good for a certain situation that the other is terrible at.
> In this way Theano can be used for doing efficient symbolic differentiation (as the expression returned by T.grad will be optimized during compilation), even for function with many inputs. (see automatic differentiation for a description of symbolic differentiation).
http://deeplearning.net/software/theano/tutorial/gradients.h...
It's not an approximate method, nor does it care [directly] about floating point. If you have implemented some f' that approximates a mathematical function f and you use AD to differentiate f', you are calculating the exact derivative of f', not an approximation of the derivative of f. It's an important distinction.
To be clear, when you say f' you're not talking about Newton's notation for the derivative of f, you're talking about a function from floats to floats that is the approximation/algorithmic implementation of f (which is R->R), right?
I don't really see why the distinction is particularly important. The reason the exact derivative of f' that you get from AD is useful is because it also approximates the derivative of f, right? If it were possible to make some pathological choice of f' (that is, algorithmic implementation of f) such that the result from AD is a poor approximation of the derivative of f, that's not really a successful use of AD on f, right? So when I say I'm gonna "use AD to get a derivative of f", I'm really saying I'm going to use AD on a good choice of an approximation of f to get a good approximation of the derivative of f, right?
I suppose if infinite precision analog computing were possible, or in the context of theoretical real-valued register machines (does anyone still study that?), it matters that AD is exact on the algorithmic implementation, but we're not in or anywhere near those contexts, are we?
Yep. I probably should have used f* instead of f' because of context. R->R isn't necessary however, it should generalize quite a bit.
As to why the distinction is important, it's because of sensitivity. Approximating a function rarely also approximates its derivative well unless it is constructed to do so (e.g. k-th order Hermite polynomials). As an example, consider the simplest approximation scheme, basic polynomial fitting. They will guarantee that your fit matches the true function at all sample points, but the derivative might (and usually will) be wildly different. You have to be extremely careful differentiating approximate schemes and relating them to the true derivative. Usually what you're interested in for AD is the derivative of the approximate scheme and not an approximate derivative for the exact function (e.g., sensitivity analysis).
And I agree that dual numbers are intuitive to me as well, but I think it requires a decent bit of background as to why they work.
At the bottom it computes both the value and the derivative of x^3 at x=2. x^3 is 8 and 3x^2 is 12.
For comparison, symbolic differentiation is implemented halfway down http://norvig.com/paip/macsymar.lisp where there are the rules you learn in calculus class, lines like
which means code that looks at the formula as source code and rewrites it. It blows up in the example the OP brings up, because it's working on an expression instead of on a DAG; I think if you made up a DAG-adapted symbolic differentiator it could output a compact sequence of formulas for the derivative, though I haven't tried it. It should be equivalent to symbolically evaluating the code from autodiff.py.That's essentially what autodiff is. It works on the DAG, whereas "symbolic" diff insists that the DAG is a tree (so reused components have to be duplicated, which leads to blowup).
This symbolic differentiator could be made to not blow up, by memoizing, i.e. decorating with https://github.com/darius/sketchbook/blob/master/regex/memo.... . It'd still have the difference that it constructs an explicit formula in x, as a data structure; the autodiff code instead takes a particular x as input and calculates a value for just that x, where the value includes both an 'actual value' and a 'derivative' component. (Your library and compiler could get fancy and inline that computation at compile time back into a pair of formulas, and then yes, they ought to be exactly equivalent.)
The frustrating part is reading lots of words/math formulas explanations without understanding them and then seeing some diagram/executable code and thinking "that's it? so many hours wasted try to understand something so simple.. why didn't you draw a diagram? why didn't you show some executable code? WHY?!"
Everything that you need is to know how to implement arithmetic operations for numbers in R[ε], e.g.
A problem occurs when you try to divide by ε. This is simply undefined in R[ε], which, unlike C is not a field. But not all is lost, suppose you want to divide (a + b ε) by (c + d ε), where c is not 0, then That is, division by ε only occurs when you divide by 0 in the first place.To recapitulate: If you have a class DualNumber with overloaded +, -, * , /, ^, you can find the derivative of, say, the fourth-order approximation of e^x at x = 0.5, by computing
(Sorry if this not a good explanation but I've spent too much time on it :P)Can you clarify the difference between autodiff and symbolic diff?
Thanks
The rigid body dynamics system used Featherstone's algorithm. This models a tree of links and joints, a skeleton. You put in forces and torques at each joint, and the algorithm computes accelerations at each joint and the root node. Those accelerations then have to be integrated to get velocities and positions. As positions change, so do contact forces. If you don't want to get interpenetration in collisions, the contact forces must be allowed to become very large. We used exponential springs as the contact model to achieve this.
Numerically, this means integrating a very stiff system of differential equations. Explicit integration, like Runge-Kutta 4, works, but you have to monitor the error term and cut the time step when necessary. During the early parts of a hard collision, the time step may have to drop into the microsecond range. This is why this approach doesn't work well for games; it's not constant-time. (If you don't cut the time step, your simulation goes "sprong", and things go flying off into space. Some games still do this.)
An alternative is to use implicit integration, where you work backwards to solve the next step to be consistent with the previous one. Implicit integration works with larger timesteps on stiff systems. (There's still error, but it acts in the direction of draining energy from the moving system, which is much better than adding it.) This requires gradients of the function that the Featherstone algorithm is computing. The brute-force approach is to compute the gradients (the Jacobian) by perturbing each input by a small amount, running the Featherstone algorithm, measuring the differences, and obtaining the slopes numerically. This is slow.
Ideally, you'd like to have analytical Jacobians. That's where automatic differentiation would help. Differentiating Featherstone's algorithm analytically is hard, but might be possible today.
We used SD/Fast, which is a C code generator for Featherstone's algorithm. Straightforward implementations of Featherstone have lots of switches and conditionals as they deal with the topology of the skeleton being simulated. SD/Fast took in the link and joint description and turned out C code for that structure. This gets rid of most of the conditionals. It unwound the code more than you'd want to do today; there was much loop unrolling at the source level. (Before superscalar CPUs, unwinding loops was a win; today, tiny tight loops are a win.)
Anyway, it's possible that the tools being developed in machine learning could be applied to game physics in that way. At the visual level, the difference is that big objects bounce like big objects, with slower collision rebound times. In impulse-constraint systems, all bounces are instantaneous, which is why, in video games, everything seems to be too light.