12
$\begingroup$

According to the survey paper on autodiff (linked) Autodiff works on inputs that cannot be specified in closed form but can be described by a sequence of code, each component of which is differentiable. Autodiff also works on code that can be symbolically differentiated but in this latter case the benefits are less obvious and more subtle. However, I haven't been able to come up with an example where autodiff works but symbolic diff will not work.

My question is: does there exist a simple example of autodiff with a code input that will not work with symbolic diff?

Note: I realize simple is somewhat arbitrarily defined so let's say in less than 20 lines of code so that the answer isn't too long to read. If 20 lines isn't enough then something like the minimal number of lines in code would work.

$\endgroup$
9
$\begingroup$

It's state-dependent control flow that's an issue.

function f(u)
  z = 0.0
  while z < 10.0
    z += u
    u += z^2
  end
  return u
end

What's the program for computing the derivative? Automatic differentiation would give you:

function f(_u)
  u = (_u,1.0) # seed the input derivative for the jvp in direction of basis e1
  z = (0.0,0.0)
  while z[1] < 10.0
    z += u
    u += (z[1]^2,2z[1]*z[2]) # by d(z^2)/dz = 2z
  end
  return u # first output is the primal, second is the derivative w.r.t. input
end

That's what dual number arithmetic will actually build under the hood. Now what's the symbolic derivative? You need to know what u is to know the full expression, so that's hard. If you know what the input value u was, the computational graph for the second term of the tuple is precisely the derivative w.r.t. the input _u, so if you knew how many times you'd loop, you could have this symbolic expression. With automatic differentiation this is okay because you only ever want values out, so there you go you get values from this program. But this program cannot tangibly give you the LaTeX to paste into your paper for the derivative w.r.t. any possible _u, which is why "it isn't symbolically differentiable".

So the moral of the story is, AD and symbolic differentiation is more the same than different. The way I generated that code is by symbolically taking the derivative of the steps of the program to build the program for the derivative as the second part of the tuple. But having a program that gives you symbolic expressions is not necessarily a satisfying answer to "give me the symbolic derivative".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A symbolic derivative computation would give you the derivative with respect to u. You would then use the chain rule to multiply by the derivative of u with respect to the other independent variable. If this code was refactored to keep "u" constant and choose another variable to accumulate, it would make the computation a lot easier to see. An automatic differentiation algorithm could be refactored to output a symbolic expression instead of a calculated one. $\endgroup$ – Juan Jan 15 at 16:26
  • $\begingroup$ I didn't say it's impossible, it's just hard. You'd have to figure out what all of the different expressions really are (i.e. it can be written as an expression for each range of u values), and then differentiate each of the expressions. If you actually want all of this, you can get an expression explosion unless you find a nice way to write a general form. Thus doing this all automatically is hard. But AD on this is easy. $\endgroup$ – Chris Rackauckas Jan 15 at 16:54
  • $\begingroup$ Please see my answer below: scicomp.stackexchange.com/a/34211/7681 The Stack Overflow answer I reference point to a paper that points out that expression explosion is a myth. A position I agree with. $\endgroup$ – Juan Jan 15 at 17:37
  • $\begingroup$ @ChrisRackauckas I like the answer and I think I follow what is going on here. It would be more clear if the answer had a autodiff derivative, e.g. say w/$u=2$, could you add that to the explanation? e.g. working out the autodiff tape or jacobian vector product, either of which is fine so whichever is easier/simpler. $\endgroup$ – Lucas Roberts Jan 15 at 21:30
  • $\begingroup$ @Juan yes, expression explosion is a myth, but that doesn't solve this problem. One way we have implemented symbolic tools like ModelingToolkit.jl in Julia actually rely on AD to generate the derivative expressions because of this equivalence. However, there are infinitely many expressions here because the input effect. You can write down a computer program for what the expression would be for any input u. While that's a satisfactory AD answer, that isn't a satisfactory answer to "the symbolic derivative of u". That's the issue. $\endgroup$ – Chris Rackauckas Jan 15 at 21:43
4
$\begingroup$

The paper you linked answers the question. Autodiff (or hand differentiation) can differentiate branched program statements. For example, limiters, entropy fixes branching in flux statements, and the like. It can be rather helpful for min max statements as well. You can see an example below:

 Function(Vn_bar, a_bar, ul, cl, ur, cr)
   lambda1    = abs(Vn_bar-a_bar)
   lambda2    = abs(Vn_bar)
   lambda4    = abs(Vn_bar+a_bar)

   epsdummy   = max(lambda1-(ul-cl), (ur-cr)-lambda1)
   eps1       = max(0, epsdummy)
   epsdummy   = max(lambda2-ul, ur-lambda2)
   eps2       = max(0, epsdummy)
   epsdummy   = max(lambda4-ul-cl, ur+cr-lambda4)
   eps4       = max(0, epsdummy)

   if (lambda1 < eps1) lambda1 = .5_dp*(lambda1**2/eps1+eps1)
   if (lambda2 < eps2) lambda2 = .5_dp*(lambda2**2/eps2+eps2)
   if (lambda4 < eps4) lambda4 = .5_dp*(lambda4**2/eps4+eps4)
   y = sqrt(lambda1**2 + lambda2**2 + lambda4**2)
   do while(y < 10) 
      y = y**2
   end do
   return y

This is an example where we provide 6 inputs that we can differentiate with respect to (Vn_bar, a_bar, ul, cl, ur, cr) and a function y, whose derivative we are taking. You can see that we have many branch statements here, max and min functions and a loop, all dependent on the state itself. AD or hand differentiation can handle this, even though it doesn't have a real symbolic derivative.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for the response, could you clarify in this case your function arguments to be differentiated? It is a little hard to follow without a signature and a return for me to figure out what you mean. $\endgroup$ – Lucas Roberts Jan 15 at 3:29
  • 4
    $\begingroup$ Why do you think it doesn't have "a real symbolic derivative"? It looks like a piecewise defined differentiable function to me, which surely has a (piecewise defined) closed-form derivative. It is not pretty to write or compute, but it is perfectly well defined. (You may have nondifferentiable points at the boundary of the various intervals, but that's a different problem no matter how you compute it.) $\endgroup$ – Federico Poloni Jan 15 at 12:44
  • $\begingroup$ I was trying to come up with a quick example from somewhere. But you're right that it could be defined as a very ugly piecewise function. $\endgroup$ – EMP Jan 15 at 15:49
  • $\begingroup$ I changed it a little bit to make it truly non-symbolicly differentiable now $\endgroup$ – EMP Jan 15 at 15:51
  • 1
    $\begingroup$ this answer is essentially the same as the one from Chris, only much more verbose. $\endgroup$ – GoHokies Jan 16 at 14:38
1
$\begingroup$

An automatic differentiation program could be refactored to output a symbolic representation, instead of a numerical one. Therefore the 2 forms would be equivalent.

Please see the non-accepted answer here: https://stackoverflow.com/a/55607008/104910

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ OTOH, the paper says "We will also show that the phenomenon of “expression swell” does not originate from the differentiation process but from transforming a DAG into a tree when disallowing common sub-expressions." suggesting that typical ways of doing symbolic differentiation do have expression swell. $\endgroup$ – Oscar Smith Jan 16 at 0:37
-1
$\begingroup$

AD is symbolic differentiation of each line of a computer code. But more useful since it gives you another computer code, you dont have to recode the derivative yourself.

If you have some exotic function whose derivative is not known to the AD tool you are using, then it cannot give you the answer of course.

If you have an explicit function, then symbolic diff can always be done, but becomes unwieldy/cumbersome/error-prone if you have a complex expression, as others have given example above.

Discontinuous functions will also be differentiated by AD by taking one sided derivative.

For example $f(x) = max(x,0)$ may be implemented in the code as

$$ f(x) = \begin{cases} 0 & x \le 0 \\ x & x > 0 \end{cases} $$

Then the AD will give the derivative as

$$ f'(x) = \begin{cases} 0 & x \le 0 \\ 1 & x > 0 \end{cases} $$

So even if branching is present in a code, there is an underlying symbolic derivative one can write down.

A more complex example is an implicit function $$ F(x,a)=0, \qquad y = G(x) $$ where $F$ is implemented as a computer code. Here you may not be able to write down an explicit formula for $dy/da$ ? Because there is no explicit formula for $x=x(a)$. Even AD cannot give you the derivative here since it does not know the function $x=x(a)$. In practice we get an approximation to $x$ say $x_h$ by applying some Newton method. $$ x_h = F_h^{-1}(a), \qquad y_h = G(x_h) $$ where $F_h^{-1}$ denotes the Newton method. Now AD can work, but there is also a symbolic derivative underlying it, but it is something you would rather not write down yourself.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ the paper I've linked to in the post disputes the claim that "AD is symbolic differentiation of a computer code." but acknowledges that the nomenclature is a bit fuzzy, especially across domains. The confusion I have is whether there exists an example where symbolic differentiation is not possible and autodiff can still give an answer. The consensus is yes there do exist problem instances where autodiff works when symbolic differentiation does not. $\endgroup$ – Lucas Roberts Jan 15 at 21:14
  • $\begingroup$ AD is just applying symbolic diff to each line of code. So if AD gives a useful answer, then there is an underlying symbolic expression, but maybe too complex to write down on paper. When you ask "symbolic diff works" you mean does there exist a formula, then yes it does. But if you mean, can I write it down with reasonable effort, then you can say symbolic diff does not always work. $\endgroup$ – cfdlab Jan 16 at 3:33
  • $\begingroup$ fair points, semantics matter here and the language is a bit confusing. I also appreciate the different perspective of implicit function theorem. A function is a function whether you have a closed form or a computational procedure to evaluates the points to a given approximation. $\endgroup$ – Lucas Roberts Jan 17 at 2:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.