🚀 go-pugleaf

robertd@kauri.vuw.ac.nz (Dr R Davies*xrbd*) writes:

>In article <l71d15INNakq@almaak.usc.edu> ajayshah@almaak.usc.edu (Ajay Shah)
>   writes:

>Could you explain the connection with matrix packages a little more.

>To do symbolic manipulation in C++ you will probably want to use the kind of
>representation I use in my matrix package, Newmat. Of course the basic
>concept in that representation is taken from the reading I have done about
>symbolic manipulation.

Oh -- you are the author of newmat.  Thanks!

On to automatic differentiation.  No, automatic differentiation is NOT
symbolic differentiation.  The key point in AD is we never evaluate
the functional form of the derivatives.  We merely use the rules of
calculus to numerically evaluate the derivatives at a given point.

This is all very new to me, and I'm not perfectly clear on this
myself.  I tried explaining it to someone on email and came up with
what follows.  It may well be perfectly wrong.  If someone can explain
better, please do so.


The broad idea is like this.  Suppose we are evaluating a expression
f(x,y,z) = x + (y*z).  If we overload '*' and '+' then it's possible
to maintain the bookkeeping.

Let's start at y*z (which is where the evaluation would start too).
From calculus we know that this subexpression contributes nothing to
f'_x, and that f'_y = z, f'_z = y.  So we build a "gradient vector"
composed of the values [0, z, y].  I'm using algebraic notation here,
but the code would use the actual realisations of what is seen for z
and y.

Next we look at x.  From calculus we know f'_x = 1 and the other two
are 0.  So for "x" we build a "gradient vector" of [1, 0, 0].

From calculus we know that across a '+' one must add gradient vectors,
so finally we get

[1, z, y]

which is correct :-)

It's extremely important to think of this as dealing with _values_ of
z and y, and not the symbols.  Otherwise the complexity blows up.
When we use numerical realisations of each step of the differentiation
process, there is no complexity constraint in doing arbitrarily
complex expressions.

Of course, we would need associated machinery for math.h and for
vectors and matrices too.

As implemented in C++, you would simply write the expression f = x +
(y*z); and as a side-effect, the gradient vector would get created.
Now ain't that great?  (Now you agree with my statement in the posting
of how C++ is the language of choice for this problem?)


I think this strategy is going to revolutionise the way we actually do
nonlinear maximisations.  I think it's going to obsolete algorithms
like the BFGS and conjugate gradients etc. because with this in hand
we get exact hessians and higher.  We get large gains in efficiency by
using higher derivatives (see the Kalaba-Tisher paper for example).
We will endup replacing the status quo of libraries like NPSOL by
something totally different, and the bonus is that the replacement is
not in fortrash!  I like it!

        -ans.
-- 
Ajay Shah, (213)749-8133, ajayshah@usc.edu