Dual Numbers and Automatic Differentiation (2014)
blog.demofox.org
blog.demofox.org
The cost of Dual numbers (a form of forward-mode differentiation) scales linearly with the number of derivatives (just like finite differencing, but more accurate). Backpropagation, or reverse-mode differentiation, is a constant factor times the cost of a function evaluation. For neural nets with millions of parameters, backpropagation is going to be millions of times faster than dual numbers.
This guy did neural nets with dual numbers in julia and found it to take ~1.2 times as long as standard backpropagation, which suggests that if you had dedicated hardware for it it would be very nice.
Dual numbers are just the wrong approach for neural nets, which have many parameters. The amazing thing about backprop / reverse-mode differentiation is that you get the derivatives wrt all the weights in one reverse sweep through the network.
Fede_V's points about the drawbacks of the technique are valid in C++, but Julia's duck-typing makes being generic the default (including in the standard library). ForwardDiff works out of the box, for free, in a huge number of cases.
There certainly is run-time checking in julia (true duck-typing) if you are not careful with how you write your functions, but I doubt that ForwardDiff, for example, uses it.
f(x) = x^2 + 2
- Using Dual Numbers requires that all functions that you call into accept templated parameters. If you want to use GSL, BLAS, or any other mature math library, you are probably out of luck.
- Even if you are willing to port the code and modify the functions to accept templated parameters, very highly optimized math libraries make assumption not just about the behaviour of numbers (their API, defined by how they behave under addition/subtraction, etc) but also about their ABI. For example, a well tuned LAPACK like OpenBlas or MKL has very well tuned loop sizes to optimize cache behaviour assuming that floats are of a particular size.
For matrix-based code, a good note on derivative propagation is https://people.maths.ox.ac.uk/gilesm/files/NA-08-01.pdf — the symbols with dots on top are forward-propagated derivatives like dual numbers. The symbols with bars on top are back-propagated derivatives, which is what you want to compute lots of derivatives at once. "Machine learning" libraries like Theano, TensorFlow, and Autograd will compute the reverse mode operation for many linear algebra expressions automatically, and use reasonable libraries like BLAS+LAPACK or Eigen under the hood.
auto lambda =
[](auto x, auto y)
{
// The Rosenbrock function.
auto d0 = y[0] - x[0]*x[0];
auto d1 = 1 - x[0];
return 100 * d0*d0 + d1*d1;
};
// The lambda function will be copied and
// automatically differentiated. The derivatives
// are computed using templates, not numerically.
//
// No need to derive or compute derivatives
// manually!
auto func = make_differentiable<1, 1>(lambda);
It was worthwhile research reading through the implementation to understand the applications.
[0]: https://github.com/ceres-solver/ceres-solver/blob/master/inc...
Not remarkable, but works.
f = lambda x: x * 5 + x ** 2 - 2 / x + 3 / x ** 2
print(derive(f, 6))So a 1 Dimensional geometric algebra with the signature e_1e_1 = ee := 0 is isomorphic to dual numbers.
On the other hand, little-o notation [1] was invented for exactly this purpose. It is easy to evaluate derivatives using it, for example (x+ε)^3 = x^3+3x^2ε+o(ε), and so ((x+ε)^3 - x^3)/ε = 3*x^2 + o(1), and o(1) tends to 0 for ε tends to 0.
[1] https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...
The reason is that to have automatic differentiation one needs to keep in principle the epsilon^n for any order and the dual number just take epsilon^2 = 0 which is an strong limitation.
For example with dual number you can say that:
limit(x->0) (sin(x) - 1) / x = 1
just by doing x = epsilon but they will fail with:
limit(x->0) (cos(x) - 1) / x^2 = -1/2
because the quadratic terms you need will go to zero for x = epsilon.
>needs to keep in principle the epsilon^n for any order and
>the dual number just take epsilon^2 = 0 which is an strong
>limitation.
Actually not. Differentiation in an abstract sense is the change of the function, approximated linearly. This means: when you do normal differentiation, you basically do already throw away the squared terms. The Leibniz notation for a differentiated function df/dx is really explicit about this principle - as opposed to the Newton notation f'(x).
What these people call dual numbers automatic differentiation is a really powerful tool. In a more abstract sense, having an object and adding a small epsilon to it, allows you differentiate much more general objects. For instance I could ask: how does a function S[f] of a function change with respect to a function f. I know this sounds like abstract non-sense but you can for example calculate the curve of a rope with it by solving dS[f] = 0 to f.
>limit(x->0) (sin(x) - 1) / x = 1
>just by doing x = epsilon
No, that's not the case. If you use the L'Hospital rules, you throw away the epsilon (it's constant) and the derivatives of both enumerator and denominator don't change. Thus the two limits stay the same.
That is not a valid statement. Perhaps you meant this?
limit(x->0) sin(x) / x = 1
Imho, the article is not very convincing, since Dual numbers require double amount of work per operation (making the computation of the derivative not "free" or "automatic").
The concept, however, seems very interesting, so I'm wondering about other applications.
Had I known about it at the time, it would have saved me a few headaches when I was writing a game mod that computed orbital intercepts.
So, the "work" is almost nothing vs. computing derivatives by hand, which requires entirely different math. Furthermore, the actual CPU instructions are generally lower with a Dual implementation, usually because transcendentals and the like aren't computed over and over again—although this is obviously computation-dependent.
An example of a project that uses automatic differentiation in a really useful way is the Ceres Solver.[0]
I'm not sure where the term "Dual Numbers" came from, but in the numerical math community, this is known as Complex Step Differentiation. https://en.wikipedia.org/wiki/Numerical_differentiation#Comp...
Complex step is only straightforward for first-derivatives. For second-order and above, there are a number of competing techniques. One of them is multicomplex numbers.
From a performance perspective, Automatic Differentiation pretty much outperforms complex step methods in most situations. The only reason to use complex step methods is when you have a very fast language with a complex types (i.e. FORTRAN) and you need a quick-and-easy way of getting 1st order derivatives.
Otherwise, just use AD.