Definition and examples

The first notion we must understand to make sense of AAD is that of a calculation graph. Every calculation defines a graph. The nodes are all the elementary mathematical calculations involved: , , , , , , , , and so forth.¹ The edges that join two nodes represent operation to argument relations: child nodes are the arguments to the calculation in the parent node. The (childless nodes) are scalar numbers and inputs to the calculation.²

The structure of the graph reflects precedence among operators: for instance the graph for is:

because multiplication has precedence, unless explicitly overwritten with parentheses. The graph for is:

The graph also reflects the order of calculation selected by the compiler among equivalent ones. For instance, the graph for could be:

or:

The compiler selects one of the possible calculation orders. Hence, the graph for the calculation code is not unique, but the graph for a given execution of the code is, the compiler having made a choice among the equivalent orders.³ We work with the unique graphs that reflect the compiler's choice of the calculation order, and always represent calculations left to right. Hence, the graph:

represents and:

represents .

The following example computes a scalar out of 5 scalars (where is purposely left out of the calculation) with the formula:

We also compute and export the partial derivatives by finite differences for future reference. We will be coming back to this code throughout the chapter.⁴

Its graph (assuming the compiler respects the left-to-right order in the code) is:

It is important to understand that complicated, compound calculations, even those that use OO (object-oriented) architecture and nested function calls, like the ones that compute the value of an exotic option with MC simulations or FDM, or even the value of the xVA on a large netting set, or any kind of valuation or other mathematical or numerical calculation, all define a similar graph, perhaps with billions of nodes, but a calculation graph all the same, where nodes are elementary operations and edges refer to their arguments.

Calculation graphs and computer programs

It is also important to understand that calculation graphs refer to mathematical operations, irrespective of how computer programs store them in variables. For instance, the calculation graph for:

is most definitely not:

but:

Although the variable is reused and overwritten in the calculation of the sum, the sum defines a new calculation of its own right in the graph. Graph nodes are calculations, not variables.

Similarly, recursive function calls define new calculations in the associated graph: the following recursive implementation for the factorial:

defines the following graph when called with 3 as argument:

The fact that the function is defined recursively is irrelevant; the graph is only concerned with mathematical operations and their order of execution.

Directed Acyclic Graphs (DAGs)

Computer programs do not define just any type of graph.

First, notice that a calculation graph is not necessarily a tree, a particularly simple type of graph most people are used to working with, where every child has exactly one parent.⁵ In the example on page 323, the node has two parents and the node has three. Calculation graphs are not trees, so reasoning and algorithms that apply to trees don't necessarily apply to them.

Second, the edges are directed, calculation to arguments. An edge from to means that is an argument to the calculation of , like in , which is of course not the same as . Graphs where all edges are directed are called directed graphs. Calculation graphs are always directed.

Finally, in a calculation graph, a node cannot refer to itself, either directly or indirectly. The following graph, for instance:

is not a calculation graph, and no code could ever generate a graph like this. The reason is that the arguments to a calculation must be evaluated prior to the calculation.

Graphs that satisfy such property are called acyclic graphs. Therefore, calculation graphs are directed acyclic graphs or DAGs. We will be applying some basic results from the graph theory shortly, so we must identify exactly the class of graphs that qualify as calculation graphs.

DAGs and control flow

The DAG of a calculation only represents the mathematical operations involved, not the control flow. There are no nodes for , , , and friends. A DAG represents the chain of calculations under one particular control branch. For instance, the code

has the DAG:

when executed with a positive input and the different DAG:

when executed with a negative input. It doesn't have a composite dag of the type:

This is not a calculation DAG.

We work with calculation DAGs, not code DAGs. Calculation DAGs refer to one particular execution of the code, with a specific set of inputs, and a unique control branch, resulting in a specific output. They don't refer to the code that produced the calculation. AAD differentiates calculations, not code. It follows that AAD does not differentiate through the control flow itself: since there are no “if” nodes in the calculation DAG, the AAD “derivative” of an “if” statement is 0.

This may look at first sight like a flaw with AAD, but how is any type of differentiation supposed to differentiate through control flow, something that is by nature discontinuous and not differentiable?

We will discuss control flow and discontinuities further in Chapter 11. For now, we focus on building DAGs and applying them for the computation of differentials in constant time.

Building a DAG

A DAG is not just a theoretical representation of some calculation. We apply operator overloading to explicitly build a calculation DAG in memory at run time, as follows. This code is incomplete, we only instantiate the , and nodes, and extremely inefficient because every operation allocates memory for its node on the DAG. We also don't implement const correctness and focus on functionality. This code is for demonstration purposes only. We suggest readers take the time to fully understand it. This inefficent code nonetheless demonstrates the DNA of AAD.

First, we create classes for the various types of nodes, , , , and leaf, in an object-oriented hierarchy:

We apply a classical composite pattern (see GOF, [25]) for the nodes in the graph. Concrete nodes are derived for each operation type and hold their arguments by base class pointers. The systematic use of smart pointers guarantees an automatic (if inefficient) memory management. It has to be shared pointers because multiple parents may share a child. We can't have a parent release a child while other nodes are still referring to it. When all its parents are gone, the node is released automatically.

Next, we design a custom number type. This type holds a reference to the node on the graph corresponding to the operation last assigned to it. When such a number is initialized, it creates a leaf on the graph. We use this custom type in place of doubles in our calculation code.

is a C++11 standard function associated with smart pointers that returns a copy of the smart pointer of the proper type with its stored pointer casted dynamically.⁶ This is necessary because only leave nodes store a value.

Next, we overload the mathematical operators and functions for the custom number type so that when these operators and functions are executed with this type, the program does not evaluate the operator as normal, but instead constructs the corresponding node on the graph.

This completes our “AAD” code; we can now build graphs automatically. This is where the first A in AAD comes from. We don't build the DAG by hand. The code does it for us when we instantiate it with our number type. We could hard replace “double” by “Number” in the calculation code, or make two copies, one with doubles, one with Numbers. The best practice is template the calculation code on its number type, like this:

and call it with our custom type like that:

Because we called with Numbers in place of doubles, line 5 does not calculate anything. All mathematical operations within execute our overloaded operators and functions. So, in the end, what this line of code does is construct in memory the DAG for the calculation of .

We templated the code of for its number representation type. To template calculation code in view of running of it with AAD is called instrumentation. In Chapter 12, we instrument our simulation code.

Traversing the DAG

Lazy evaluation What can we do with the DAG we just built?

First, we can calculate it. We evaluate the DAG itself, without reference to the function , the execution of which code built the DAG in the first place.

How do we proceed exactly? First, note that arguments to an operation must be computed before the operation. This means that the processing of a node starts with the processing of its children.

Second, we know that nodes may have more than one parent in a DAG. Those nodes will be processed multiple times if we are not careful. For this reason, we start the processing of a node with a check that this node was not processed previously. If this is verified, then we process its children, and then, and only then, we evaluate the operation on the node itself, mark it as processed, and cache the result of the operation on the node in case it is needed again from a different parent. If the node was previously processed, we simply pick its cached result.

In this sequence, the only step that is specific to evaluation is the execution of the operation on the node. All the rest is graph traversal logic and applies to evaluation as well as other forms of visits we explore next.

If we follow these rules, starting with the top node, we are guaranteed to visit (evaluate) each node exactly once and in the correct order for the evaluation of the DAG.

Hence, we have the following graph traversal and visit algorithm: starting with the top node,

1. Check if the node was already processed. If so, exit.
2. Process the child nodes.
3. Visit the node: conduct the calculation, cache the result.
4. Mark the node as processed.

The third line of the algorithm is the only one specific to evaluation. The rest only relates to the order of the visits. More precisely, the traversal strategy implemented here is well known to the graph theory. It is called “depth-first postorder” or simply postorder. Depth-first because it follows every branch down to a leaf before moving on to the next branch. Postorder because the children (arguments) of a node are always visited (evaluated) before the node (operation). It follows that visits start on the leaf nodes and end on the top node. Postorder implements a bottom-up traversal strategy and guarantees that every node in a DAG is processed exactly once, where children are always visited before their parents. It is the natural order for an evaluation. But we will see that other forms of visits may require a different traversal strategy.

We implement our evaluation algorithm, separating traversal and visit logic into different pieces of code. The traversal logic goes to the base class, which also stores a flag that tells if a node was processed and caches the result of its evaluation. For our information only, the order of calculation is also stored on the (base) nodes. Finally, we code a simple recursive method to reset the processed flags on all nodes.

The algorithm isn't optimal, as most of the code in this chapter. Next, we code the specific evaluation visitor as a virtual method: evaluation is different for the different concrete nodes (sum in a node, product in a node, and so on):

We start the evaluation of the DAG from the Number that holds the result and, therefore, refers to the top node of the DAG. Recall that Numbers contain a shared pointer to the last assignment.

Now we can evaluate the DAG:

The evaluation of the mathematical operations in the calculation did not happen on line 5. That just constructed the DAG. Nothing was calculated. The calculation happened on line 7 in the call to , directly from the DAG after it was built. That it returns the exact same result as a direct function call (with double as the number type) indicates that our code is correct.

To see this more clearly, we can change the inputs on the DAG and evaluate it again, without any further call to the function that built the DAG. The new result correctly reflects the change of inputs, as readers may easily check:

This pattern to store a calculation in the form a DAG, or another form that lends itself to evaluation, instead of conducting the evaluation straightaway (or eagerly), and conducting the evaluation at a later time, directly from the DAG, possibly repeatedly and possibly with different inputs set directly on the DAG, is called lazy evaluation. Lazy evaluation is what makes AAD automatic; it is also the principle behind, for example, expression templates (see Chapter 15) and scripting (see our publication [11]).

Calculation order There is more we can do with a DAG than evaluate it lazily. For instance, we can store the calculation order number on the node, which will be useful for what follows. We identify the nodes by their calculation order and store it on the node. We reuse our postorder code; we just need a new visit function. In this case, the visits don't depend on the concrete type of the node; we don't need a virtual visit function, and we can code it directly on the base node.

The lambda defines a data member that starts at 0. Since C++14, lambdas not only capture environment variables, but can also define other internal variables in the capture clause. The evaluation of the lambda modifies its member, so the lambda must be marked mutable.

Our DAG is numbered after the execution of the code above, and each node is identified by its postorder. We can log the intermediate results in the evaluation as follows:

after evaluation of the DAG. When we evaluate the DAG repeatedly with different inputs, we get different logs accordingly:

For the first evaluation we get the log:

• Processed node 1 result = 3
• Processed node 2 result = 5
• Processed node 3 result = 1
• Processed node 4 result = 5
• Processed node 5 result = 2
• Processed node 6 result = 7
• Processed node 7 result = 21
• Processed node 8 result = 4
• Processed node 9 result = 3.04452
• Processed node 10 result = 12.1781
• Processed node 11 result = 33.1781
• Processed node 12 result = 24.0445
• Processed node 13 result = 797.751

For the second evaluation, we get different logs reflecting .

We can display the DAG, this time identifying nodes by their evaluation order:

and intermediate results (for the first evaluation):

Reverse engineering There is even more we can do with the DAG. For instance, we can reverse engineer an equivalent calculation program:

We get the log:

• y1 = 3
• y2 = 5
• y3 = 1
• y4 = y2 * y3
• y5 = 2
• y6 = y4 + y5
• y7 = y1 * y6
• y8 = 4
• y9 = log(y7)
• y10 = y8 * y9
• y11 = y7 + y10
• y12 = y7 + y9
• y13 = y11 * y12

We reconstructed an equivalent computer program from the DAG. Of course, we can change the inputs and generate a new computer program that reflects the new values of the leaves and produces different results.

Note that we managed to make visits (evaluation, instruction logging) depend on both the visitor and the concrete type of the visited node. Different things happen according to the visitor (evaluator, instruction logger) and the node (, and so forth). We effectively implemented GOF's visitor pattern; see [25]. This pattern is explained in more detail and systematically applied to scripts in our publication [11] (where we study trees, not DAGs, but the logic is the same).

We learned to automatically generate DAGs from templated calculation code with operator overloading. We learned to traverse DAGs in a specific order called postorder and visit its nodes in different ways: lazily evaluate the DAG or reverse engineer an equivalent sequence of instructions.

This covered the “Automatic” in “Automatic Adjoint Differentiation.”⁷ We now move on to “Adjoint Differentiation” and use the DAG to calculate differentials, all of them, in a single traversal; hence the key constant time property.

Before we do this, we need a detour through basic formalism and adjoint mathematics.

Preorder traversal

An intuitive candidate is preorder. Like postorder, preorder is a depth-first traversal pattern, but one that visits each node before its children. We reprint the postorder code and write the preorder code below (on the base Node class). We also add a method propagateAdjoints() on the Number class to start adjoint propagation visits in preorder from the result's node:

Here is the result:

• Propagating node 13 adjoint = 1
• Propagating node 11 adjoint = 24.0445
• Propagating node 7 adjoint = 24.0445
• Accumulating leaf 1 adjoint = 168.312
• Propagating node 6 adjoint = 72.1336
• Propagating node 4 adjoint = 72.1336
• Accumulating leaf 2 adjoint = 72.1336
• Accumulating leaf 3 adjoint = 360.668
• Accumulating leaf 5 adjoint = 72.1336
• Propagating node 10 adjoint = 24.0445
• Accumulating leaf 8 adjoint = 73.2041
• Propagating node 9 adjoint = 96.1781
• Propagating node 7 adjoint = 28.6244
• Accumulating leaf 1 adjoint = 368.683
• Propagating node 6 adjoint = 158.007
• Propagating node 4 adjoint = 230.14
• Accumulating leaf 2 adjoint = 302.274
• Accumulating leaf 3 adjoint = 1511.37
• Accumulating leaf 5 adjoint = 230.14
• Propagating node 12 adjoint = 33.1781
• Propagating node 7 adjoint = 61.8025
• Accumulating leaf 1 adjoint = 801.3
• Propagating node 6 adjoint = 343.414
• Propagating node 4 adjoint = 573.555
• Accumulating leaf 2 adjoint = 875.829
• Accumulating leaf 3 adjoint = 4379.14
• Accumulating leaf 5 adjoint = 573.555
• Propagating node 9 adjoint = 129.356
• Propagating node 7 adjoint = 67.9623
• Accumulating leaf 1 adjoint = 1277.04
• Propagating node 6 adjoint = 547.301
• Propagating node 4 adjoint = 1120.86
• Accumulating leaf 2 adjoint = 1996.69
• Accumulating leaf 3 adjoint = 9983.43
• Accumulating leaf 5 adjoint = 1120.86
• a0 = 9983.43
• a1 = 1120.86
• a2 = 1277.04
• a3 = 73.2041
• a4 = 0

We conducted 35 visits through a DAG with 13 nodes. All nodes were visited, but many were visited multiple times. For example, node 7 propagated 4 times.

However, the derivatives are wrong. We recall that we computed them with finite differences earlier, and the correct values are: 950.736, 190.147, 443.677, 73.2041, and 0.

Actually, the values are incorrect because nodes are visited multiple times. Every time, their adjoint accumulated so far is propagated so their arguments accumulate adjoints multiple times. This is easily remedied by setting the adjoint to 0 after its propagation to child nodes. This way, only the part of the adjoint accumulated since the previous propagation is propagated the next time around:

Now we get the correct values, exactly the same derivatives we had with finite differences, but we still visited 35 nodes out of 13, and the remedy we implemented is really a hack: if every node was visited once, as it should, such remedy would not be necessary.

Note that AAD and finite differences agree on differentials, at least to the fourth significant figure. This illustrates that analytic derivatives produced by AAD are not different, in general, from the numerical derivatives produced by bumping. They are just computed a lot faster.

At least AAD is faster when implemented correctly. A poor implementation may well perform slower than finite differences. Our implementation so far certainly does. Efficient memory management and friends are addressed in the next chapter, but DAG traversal is addressed now. Our implementation will not fly unless we visit each node in the DAG once; 35 visits to 13 nodes is not acceptable. Preorder is not the correct traversal strategy.

Breadth-first traversal

Preorder is still a depth-first strategy in the sense that it sequentially follows paths on the DAG down to a leaf.

We may try a breadth-first strategy instead, where visits are scheduled by level in the hierarchy: top node first, then its children, left to right, then all the children of the children, and so forth.

Breadth-first traversal cannot be implemented recursively.⁹ It is implemented as follows: start on the top node with an empty queue of (pointers on) nodes. Process a node in the following manner:

1. Send the children to the back of the queue.
2. Visit the node.
3. Process all nodes in the queue from the front until empty.

Easy enough. The implementation takes a few lines:

The caller is unchanged.

Unfortunately, breadth-first is no better than preorder: it computes the correct results (providing we still zero adjoints after propagation) but still conducts 35 visits, and node 7, for instance, still propagates four times. The order is not the same, but the performance is identical.

Breadth-first is not the answer.