4
$\begingroup$

What is the intuitive idea behind automatic differentiation?

If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f?

double f(double x, double y)
{
    double res = x*x;
    double res2 = x*y;
    double res3 = res + res2
    return res3;
}

If I read the corresponding Wikipedia entry correctly I need nothing besides the chain rule, but I don't understand how this can be done in practice.

My understanding so far is that I use a table of the derivatives of all involved basic functions, such as:

  • $dx/dx=1$
  • $dy/dx=0$
  • $d(x*y)/dx=y$
  • $d(x+y)=dx/dx+0$
  • $d(x^2)/dx=2x$

How do I get the final function from this?

I would expect something like this:

double f(double x, double y, double* dx)
{
    *dx = 0;
    double res = x*x;
    ? *dx = 2*x ?
    double res2 = x*y;
    ? *dx = *dx ?
    double res3 = res + res2
    ? *dx = ??? ?

    return res3;
}

Edit: I have found this video "Beautiful Differentiation" of a talk at the International Conference on Functional Programming (ICFP) 2009, by Marcom Wallace which explains the topic quite well.

$\endgroup$
  • $\begingroup$ @vonbrand I did not know automatic differentiation was a thing, and apparently I don't remember the scope of A=B well. Thanks for the correction! $\endgroup$ – Raphael Jan 30 '14 at 13:09
6
$\begingroup$

The function is given as a "decorated" tree. Your sample function has a root node decorated "+", with one child representing $x^2$ and the other $yx$. The first child has root node "^", with children "$x$" and "2", both leaves. The second child has root node "*" with children "$y$" and "$x$".

In principle, automatic differentiation just applies the rules of differentiation recursively. In your case, we start with $\partial f/\partial x = \partial(x^2)/\partial x + \partial (yx)/\partial x$. To compute $\partial (yx)/\partial x$, we use the product rule: $$ \frac{\partial(yx)}{\partial x} = y \frac{\partial(x)}{\partial x} + \frac{\partial(y)}{\partial x} x. $$ For variables we know that $\partial x/\partial x = 1$ while $\partial y/\partial x = 0$, and simplification (one of the basic building blocks in any computer algebra system) gives $\partial(yx)/\partial x = y$. It is similar for $x^2$, though here the rule is more complicated: $(f^g)' = f^g (gf'/f+g'\log f)$.

In practice, there are probably some optimizations. Using pattern matching techniques (that is, by having specific rules) we can, for example, recognize $x^2$ for what it is, and directly calculate $\partial(x^2)/\partial x = 2x$. Similarly, if there is a subtree not depending on $x$, we could directly conclude that its derivative with respect to $x$ is zero.

$\endgroup$
  • $\begingroup$ Is this symbolic or automatic differentiation? $\endgroup$ – user13187 Jan 29 '14 at 7:51
  • $\begingroup$ This is symbolic differentiation. The resulting derivative can be "unpacked" into C code by performing DFS on the resulting function tree. Details left to the reader. $\endgroup$ – Yuval Filmus Jan 29 '14 at 14:10
  • $\begingroup$ The idea is the same. The same approach works. Either you explicitly construct the expression tree from the code, or you can just compute the derivatives of all variables line-by-line. This amounts to the same thing. If there are any function calls, you will need to use the chain rule. $\endgroup$ – Yuval Filmus Jan 29 '14 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy