Coders Packet

Forward Accumulation method for differentiation in Python

By Aakash sharma

Forward Accumulation is a simple method for calculating the derivative of a complex function by repeatedly calculating derivative of its simple parts, developed in Python.

**Forward Accumulation**\
Forward Accumulation methode works by building a computation graph of computation, and repeatedly computing the derivative of higher-level terms from lower-level terms using derivative-chain rule.

**Theory**\
The derivative rule is given by:

df(g(x))/dx = (df(x)/dg(x)) * (dg(x)/dx) ...(1)
d(u * v)/dx = v * du/dx + u * dv/dx ...(2)
d(u + v)/dx = du/dx + dv/dx

A mathematical equation is composed of functions, addition, substraction, multiplication and division. A complex mathematical equation can be decomposed into smaller sub-equations, and derivative of it can be computed using derivative-rules.

**Computation Graph**\
A computation graph is a graph structure which is composed of numeral, and opeator nodes. The leaves of tree represent a variable, while internal nodes represent an operator. Overall the graph represent a complex mathematical equation, As shown in fig.
![Computation Graph](https://github.com/aakash140799/Algorithms/blob/master/Images/Computation Graph.png?raw=true)\

**Working**
In Forward Accumulation methode, we repeatedly compute the derivative of smaller nodes. From smaller nodes, we compute derivative of higher nodes.
Such as, For above graph


we start from buttom for variable a,
at node a, da/da = 1
at node b, db/da = 0
at node c, dc/da = d(a+b)/da = da/da + db/da = 0 + 1 = 1
at node d, dd/da = d(b+1)/da = db/da + 1/da = 0 + 0 = 0
at node e, de/da = d(c*d)/da = d*(dc/da) + c*(dd/da) = (b+1)*(1) + (a+b)*(0) = b+1


we start from buttom for varoable b,
at node a, da/db = 0
at node b, db/db = 1
at node c, dc/db = d(a+b)/db = da/db + db/db = 1
at node d, dd/db = d(b+1)/db = db/db + d1/db = 1
at node e, de/db = d(c*d)/db = c*(dd/db) + d*(dc/db) = (a+b)*(1) + (b+1)*(1) = a + 2*b + 1


**Disadvantage**\
We need to iterate over the computation graph for every base variable. This problem is not present in backward accumulation methode.

Download Complete Code

Comments

No comments yet