5 ms·

Can someone further clarify the distinction between automatic and symbolic differentiation? The author claims that using symbolic differentiation on his exampl

• laughinghan 11y ago
  To the best of my understanding: - 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 https://github.com/jwmerrill/PowerSeries.jl
  • throwaway39210 11y ago
    > 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?
    • gh02t 11y ago
      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.
      • throwaway39210 11y ago
        > 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.html http://deeplearning.net/software/theano/library/gradient.htm... [2] 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) -> 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]
• abecedarius 11y ago
  Here's some code I just hacked up to show the idea: https://github.com/darius/sketchbook/blob/master/misc/autodiff.py https://github.com/darius/sketchbook/blob/master/misc/autodi... 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 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.
  • klipt 11y ago
    > 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).
    • abecedarius 11y ago
      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/symbdiff.py 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.py 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.)
• qcoh 11y ago
  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 f(x + is) = f(x) + f'(x) is + f''(x) (-s^2)/2 + ... Just looking at the imaginary part gives you: Im(f(x+is))/s = f'(x) + O(s^2). 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 DualNumber x = DualNumber(0.5, 1); DualNumber approx = 1 + x + x^2/2 + x^3/6 + x^4/24; cout << approx.EpsCoeff() << endl; (Sorry if this not a good explanation but I've spent too much time on it :P)