## autodiff32 Documentation

## Introduction

Differentiation, or the process of finding a derivative, is an extremely important mathematical operation with a wide range of applications. The discovery of extrema or zeros of functions is essential in any optimization problem, and the solving of differential equations is fundamental to modern science and engineering. Differentiation is essential in nearly all quantitative disciplines: physicists may take the derivative of the displacement of a moving object with respect to time in order to find the velocity of that object, and data scientists may use derivatives when optimizing weights in a neural network. 

Naturally, we would like to compute the derivative as accurately and efficiently as possible. Two classical methods of calculating the derivative have clear shortcomings. Symbolic differentiation (finding the derivative of a given formula with respect to a specified variable, producing a new formula as its output) will be accurate, but can be quite expensive computationally. The finite difference method ($\frac{\partial f}{\partial x} = \frac{f(x+\epsilon)-f(x)}{\epsilon}$ for some small $\epsilon$) does not have this issue, but will be less precise as different values of epsilon will give different results. This brings us to automatic differentiation, a less costly and more precise approach.

__Extension:__ For this project, we have implemented forward-mode automatic differentiation as well as reverse-mode automatic differentiation. It is important to have both methods accessible to have accuracy as well as optimal efficiency. 

Automatic differentiation can be used to compute derivatives to machine precision of functions $f:\mathbb{R}^{m} \to \mathbb{R}^{n}$

The forward mode is more efficient when $n\gg m$.
   - This corresponds to the case where the number of functions to evaluate is much greater than the number of inputs.
   - Actually computes the Jacobian-vector product $Jp$.
   
The reverse mode is more efficient when $n\ll m$.
   - This corresponds to the case where the number of inputs is much greater than the number of functions.
   - Actually computes the Jacobian-transpose-vector product $J^{T}p$.

## Background

Automatic differentiation breaks down the main function into elementary functions, evaluated upon one another. It then uses the chain rule to update the derivative at each step and ends in the derivative of the entire function.

To better understand this process, let's look at an example. Consider the example function

\begin{equation}
f(x) = x + 4sin(\frac{x}{4})
\end{equation}

We would like to compute the derivative of this function at a particular value of x. Let's say that in this case, we are interested in evaluating the derivative at $x=\pi$. In other words, we want to find $f'(\pi)$ where $f'(x) = \frac{\partial f}{\partial x}$

We know how to solve this _symbolically_ using methods that we learned in calculus, but remember, we want to compute this answer as accurately and efficiently as possible, which is why we want to solve it using automatic differentiation. 

### The Chain Rule

To solve this using automatic differentiation, we need to find the decomposition of the differentials provied by the chain rule. Remember, the chain rule is a formula for computing the derivative of the composition of two or more functions. So if we have a function $h\left(u\left(t\right)\right)$ and we want the derivative of $h$ with respect to $t$, then we know by the chain rule that the derivative is $\dfrac{\partial h}{\partial t} = \dfrac{\partial h}{\partial u}\dfrac{\partial u}{\partial t}.$ The chain rule can also be expanded to deal with multiple arguments and vector inputs (in which case we would be calculating the _gradient)_.

Our function $f(x)$ is composed of elemental functions for which we know the derivatives. We will separate out each of these elemental functions, evaluating the derivative at each step using the chain rule. 

### Forward-mode differentiation

Using forward-mode differentiation, the evaluation trace for this problem looks like:

| Trace    | Elementary Operation | Derivative | $f'(a)$ |
| :------: | :----------------------: | :------------------------------:  | :------------------------------: |
| $x_{3}$  | $\pi$ | $1$ | $\pi$ | $1$ |
| $x_{0}$  | $\frac{x_{3}}{4}$ | $\frac{\dot{x}_{3}}{4}$ | $\frac{1}{4}$ |
| $x_{1}$  | $\sin\left(x_{0}\right)$ | $\cos\left(x_{0}\right)\dot{x}_{0}$ | $\frac{\sqrt{2}}{8}$|
| $x_{2}$  | $4x_{1}$ | $4\dot{1}_{3}$ | $\frac{\sqrt{2}}{2}$ |
| $x_{4}$  | $x_{2} + x_{3}$| $\dot{x}_{2} + \dot{x}_{3}$ | $1 + \frac{\sqrt{2}}{2}$ |

This evaluation trace provides some intuition for how forward-mode automatic differentiation is used to calculate the derivative of a function evaluated at a certain value ($f'(\pi) = 1 + \frac{\sqrt{2}}{2}$). 

</img>
*Figure 1: Forward-mode computational graph for example above*

### Reverse-mode automatic differentiation

Using reverse-mode differentiation, sometimes called backpropagation, the trace on the right is evaluated top to bottom intsead. 

| Trace    | Elementary Operation | Derivative &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| $f'(a)$ |
| :------: | :----------------------: | :------------------------------: | :------------------------------: |
| $x_{3}$  | $\pi$ | $\frac{\partial{x_0}}{\partial{x_3}}\bar{x_0} + \bar{x_4} = \cos(\frac{\pi}{4}) + 1$ | $1 + \frac{\sqrt{2}}{2}$ |
| $x_{0}$  | $\frac{x_{3}}{4}$ | $\frac{\partial{x_1}}{\partial{x_0}}\bar{x_1} = 4\cos(\frac{\pi}{4})$ | $2\sqrt{2}$ |
| $x_{1}$  | $\sin\left(x_{0}\right)$ | $\frac{\partial{x_2}}{\partial{x_1}}\bar{x_2}$| $4$|
| $x_{2}$  | $4x_{1}$ | $\frac{\partial{x_4}}{\partial{x_2}}\bar{x_4}$ | $1$ |
| $x_{4}$  | $x_{2} + x_{3}$| $1$ | $1$ | $1$ 

</img>
*Figure 2: Reverse-mode computational graph for example above*

You may notice that when we computed the derivative above, we "seeded" the derivative with a value of 1. This seed vector doesn't have to be 1, but the utility of using a unit vector becomes apparent when we consider a problem involving directional derivatives.

The definition of the directional derivative (where $p$ is the seed vector)
$$D_{p}x_{3} = \sum_{j=1}^{2}{\dfrac{\partial x_{3}}{\partial x_{j}}p_{j}}$$

can be expanded to

\begin{align}
  D_{p}x_{3} &= \dfrac{\partial x_{3}}{\partial x_{1}}p_{1} + \dfrac{\partial x_{3}}{\partial x_{2}}p_{2} \\
             &= x_{2}p_{1} + x_{1}p_{2}
\end{align}

If we choose $p$ to be a the unit vector, we can see how this is beneficial:

$p = \left(1,0\right)$ gives $\dfrac{\partial f}{\partial x}$

$p = \left(0,1\right)$ gives $\dfrac{\partial f}{\partial y}$

So to summarize, the forward mode of automatic differentiation is really computing the _product of the gradient of our function with the seed vector:_

$$D_{p}x_{3} = \nabla x_{3}\cdot p.$$ 

If our function is a vector, then the forward mode actually computes $Jp$ where $J = \dfrac{\partial f_{i}}{\partial x_{j}}, \quad i = 1,\ldots, n, \quad j = 1,\ldots,m$ is the Jacobian matrix. Often we will really only want the "action" of the Jacobian on a vector, so we will just want to compute the matrix-vector product $Jp$ for some vector $p$. Using the same logic, the reverse mode actually computes the Jacobian-transpose-vector product $J^{T}p$.

Automatic differentiation can be used to compute derivatives to machine precision of functions $f:\mathbb{R}^{m} \to \mathbb{R}^{n}$

## How to Use autodiff32
### Installation

**1) Create a virtual environment (optional)**

From the terminal, create a virtual environment:

_(The command below will create the virtual environment in your present working directory, so consider moving to a project folder or a known location before creating the environment)_

```virtualenv env```

activate the virtual environment:

```source env/bin/activate```

if you plan to launch a jupyter notebook using this virtual environment, run the following to install and set up jupyter in your virtual environment:

```python -m pip install jupyter```

```python -m ipykernel install --user --name=env```

**3) Install the autodiff32 package**

In the terminal, type:
```pip install autodiff32```
Package dependencies will be taken care of automatically!

_(Alternatively, it is also possible to install the autodiff32 package by downloading this GitHub repository. If you choose that method, use the requirements.txt file to ensure you have installed all necessary dependencies.)_

## Tutorial

It is easy to use the autodiff32 package in a Jupyter notebook, as we will demonstrate here:

_(Alternatively, you can start a Python interpreter by typing ```Python``` into the terminal, or work from your favorite Python IDE.)_

_(Remember, if you are using a virtual environment, follow steps 1 through 3 above and then type ```jupyter notebook``` into your terminal to launch a notebook. Inside the notebook, switch the kernel to that of your virtual environment.)_


```python
pip install autodiff32
```

    Collecting autodiff32
      Downloading https://files.pythonhosted.org/packages/b6/8c/88fccbf0cc72968be09e75c7bd9f6811d6c675bba90d825e2fc5dfdd145e/autodiff32-0.1.2-py3-none-any.whl
    Requirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (from autodiff32) (1.17.4)
    Installing collected packages: autodiff32
    Successfully installed autodiff32-0.1.2



```python
import autodiff32 as ad
import math # only necessary for this particular example

"""
Initialize an AutoDiff object  
with the number you would like to pass into your function
"""
X = ad.AutoDiff(math.pi)

"""
Define your function of interest
"""
func = X + 4*ad.sin(X/4)
"""
Look at the derivative of your function 
evaluated at the number you gave above
"""
print("derivative:",func.der)

"""
Look at the value of your function 
evaluated at the number you gave:
"""
print("value:", func.val)
```

    derivative: 1.7071067811865475
    value: 5.970019778335983


Notice that this is the same equation used in our example above: $f(x) = x + 4(sin(\frac{x}{4}))$. Just for fun, let's see if the derivative that we calculated in the evolution trace is the same as the result using autodiff32:


```python
print("autodiff32 derivative:", func.der)
print("evolution trace derivative:", 1+math.sqrt(2)/2)
```

    autodiff32 derivative: 1.7071067811865475
    evolution trace derivative: 1.7071067811865475


We can see that the derivative calculated using autodiff32 is the same as the derivative calulated by walking manually through the evolution trace!

Now what if your function if interest has a **vector input** (X has more than one value)? In that case, use the following workflow:


```python
import numpy as np
X = ad.AutoDiff(np.array([1,2,3]))
func = X**2
print("value:", func.val)
print("derivative:",func.der)
```

    value: [1 4 9]
    derivative: [2. 4. 6.]


Notice that there are three values and three derivatives. This is because your function and its derivative have been evaluated at the three values you provided.


Now what if your function if interest is a **multivariate function** (has more than just an X variable)? In that case, use the following workflow:


```python
X,Y = ad.Multi_AutoDiff_Creator(X = 2, Y = 4).Vars
func = X**2 + 3*Y
print("value:", func.val)
print("derivative:",func.der)
```

    value: 16
    derivative: [4. 3.]


Notice that the derivative has two values. This is the derivative of your function with respect to X and Y, evaluated at the values of X and Y you provided.


Now what if you actually have **multiple functions of interest**? In that case, use the following workflow:


```python
X,Y = ad.Multi_AutoDiff_Creator(X = 2, Y = 4).Vars
func = np.array([X+Y, 2*X*Y]) # two functions!

# get value and derivatives of function separately
print("value of first function:", func[0].val)
print("derivative of first function:",func[0].der)

print("\nvalue of second function:", func[1].val)
print("derivative of second function:",func[1].der)

# return the Jacobian matrix
J = ad.Jacobian(func)
print("\nJacobian matrix:\n",J.value())
```

    value of first function: 6
    derivative of first function: [1. 1.]
    
    value of second function: 16
    derivative of second function: [8. 4.]
    
    Jacobian matrix:
     [[1. 1.]
     [8. 4.]]


Notice that you have an additional option here! You can return the values and derivatives of the functions as you would normally (except that you indicate the index of the function when asking for the value or derivative), _or_ you can return the **Jacobian matrix** which contains the derivatives with respect to X and Y for each of the functions.


Now what if your function if interest is a **multivariate function AND it has vector inputs**? In that case, use the following workflow:

_Please note that the workflow here is significantly different from the rest of the package!_

_This is due to the complexities of handling the derivatives of vector inputs for multivariate functions. We wanted to give you, the user, as much functionality as possible, even if that meant sacrificing a bit in user-friendliness._


```python
# For a single multivariate function evaluated at vector value inputs

# define your variables and their vector values
X = [1,2,3]
Y = [2,3,3]
Z = [3,5,3]
W = [3,5,3]

# put them together in a list, in the order they will be used in your function!
VarValues = [X, Y, Z, W]

# define your function
# Vars[0] represents X, Vars[1] represents Y, etc.
func = lambda Vars:3*Vars[0] + 4*Vars[1] + 4*Vars[2]**2 + 3*Vars[3]

# find the values and derivatives
Values, Derivatives = ad.MultiVarVector_AutoDiff_Evaluate(VarValues,func)

print("values:\n", Values)
print("\nderivatives:\n", Derivatives)

```

    values:
     [ 56 133  66]
    
    derivatives:
     [[ 3.  4. 24.  3.]
     [ 3.  4. 40.  3.]
     [ 3.  4. 24.  3.]]


Now what if you have **multiple multivariate functions of interest with vector inputs**? In that case, use the following workflow:

_Please note that the workflow here is significantly different from the rest of the package!_

_This is due to the complexities of handling the derivatives of vector inputs for multivariate functions. We wanted to give you, the user, as much functionality as possible, even if that meant sacrificing a bit in user-friendliness._


```python
# For a single multivariate function evaluated at vector value inputs

# define your variables and their vector values
X = [1,2,3]
Y = [2,3,3]
Z = [3,5,3]
W = [3,5,3]

# put them together in a list, in the order they will be used in your function!
VarValues = [X, Y, Z, W]

# define your functions
# Vars[0] represents X, Vars[1] represents Y, etc.
func = lambda Vars:np.array([3*Vars[0] + 4*Vars[1] + 4*Vars[2]**2 + 3*Vars[3],    # first function
                                     5*Vars[0] + 6*Vars[1] + 7*Vars[2]**2 + 1*Vars[3]])   # second function
# find the values and derivatives
Values, Derivatives = ad.MultiVarVector_AutoDiff_Evaluate(VarValues,func)

print("values:\n", Values)
print("\nderivatives:\n", Derivatives)
```

    values:
     [[ 56  83]
     [133 208]
     [ 66  99]]
    
    derivatives:
     [[[ 3.  4. 24.  3.]
      [ 5.  6. 42.  1.]]
    
     [[ 3.  4. 40.  3.]
      [ 5.  6. 70.  1.]]
    
     [[ 3.  4. 24.  3.]
      [ 5.  6. 42.  1.]]]


**Extension Usage Demo**



```python
 
# For univariate /Multivariate Scalar Function
Graph = ad.ComputationalGraph()
X = ad.Node(value = 3, Graph = Graph)
Y = ad.Node(value = 4, Graph = Graph)
Z = ad.Node(value = 1, Graph = Graph)

G = 2*X + 3*Y*Z + 2*Z
Graph.ComputeValue()
Graph.ComputeGradient(-1)
print("Derivative for X is: ",X.deri)
print("Derivative for Y is: ",Y.deri)
print("Derivative for Z is: ",Z.deri)
print("Value of Function is: ",G.value)
```

    Derivative for X is:  2.0
    Derivative for Y is:  3.0
    Derivative for Z is:  14.0
    Value of Function is:  20



```python
#For univariate or Multivariate Vector Functions with single value
import numpy as np
Graph = ad.ComputationalGraph()
X = ad.Node(value = 3, Graph = Graph)
Y = ad.Node(value = 4, Graph = Graph)
Z = ad.Node(value = 1, Graph = Graph)

G = np.array([-2*ad.sinr(X),  #please use sinr for sin operation on the node
               2*Y + Z*Y,
               3*X+3*Y*X+2*Z])

Func = ad.ReverseVecFunc(G,X =X,Y= Y,Z= Z)
Value ,Derivative = Func.value(Graph)
print("The value for the vector function is: ")
print(Value)
print("The derivative for the vector function is: ")
print(Derivative)
```

    The value for the vector function is: 
    [-0.28224002 12.         47.        ]
    The derivative for the vector function is: 
    [[ 1.97998499  0.          0.        ]
     [ 0.          3.          4.        ]
     [15.          9.          2.        ]]



```python
#SERIES OF VALUES For vector functions
D = 3 # number of variables
x = [1,2,3]
y = [6,7,4]
z = [3,8,1]
Values = np.array([x,y,z])
G = np.array([-2*X,  #please use sinr for sin operation on the node
               2*Y + Z*Y,
               3*X+3*Y*X+2*Z])
Func = ad.ReverseVecFunc(G,X =X,Y= Y,Z= Z)
Vals,Deris=Func.Seriesvalue(Values,D,Graph)
print("The value for the vector function is: ")
print(Vals)
print("The derivative for the vector function is: ")
print(np.array(Deris))
```

    The value for the vector function is: 
    [[-2 30 27]
     [-4 70 64]
     [-6 12 47]]
    The derivative for the vector function is: 
    [[[-2.  0.  0.]
      [ 0.  5.  6.]
      [21.  3.  2.]]
    
     [[-2.  0.  0.]
      [ 0. 10.  7.]
      [24.  6.  2.]]
    
     [[-2.  0.  0.]
      [ 0.  3.  4.]
      [15.  9.  2.]]]



```python
import numpy as np
Graph = ad.ComputationalGraph()
X = ad.Node(value = 3, Graph = Graph)
F = 3*X**2
Xvals= np.array([[3,2,4]]) #Please input Xvals as a 2 dimensional array
Vals, deri = Graph.SeriesValues(Xvals,1,Graph)
print(Vals)
print(deri)
```

    [27, 12, 48]
    [[18.0], [12.0], [24.0]]


## Software Organization
### Directory Structure
Our structure is as follows:

    /cs207-FinalProject
        README.md
        LICENSE
        .gitignore
        .travis.yml
        setup.py
        requirements.txt
        docs/
            milestone1.ipynb
            milestone2.ipynb
            documentation.ipynb
        autodif32/
            __init__.py
            AutoDiffObj.py
            Elementary.py
            ElementaryReverse.py
            Graph.py
            JacobianVectorFunc.py
            MultivariateVarCreator.py
            MultivariateVectorAutoDiffEvaluate.py
            MultivariateVectorVarCreator.py
            ReverseJacobVectorFunc.py
            ReverseMode.py
        test/
            __init__.py
            autodiffobj_test.py
            elementary_test.py
            Reverse_test.py
            JacobianVectorFunc_test.py
            

### Modules

The ```AutoDiffObj``` module creates an AutoDiff object based on the scalar value you would like to evaluate a function and its derivative at. It overloads the basic operations including multiply, add, negative, subtract, powers, division, and equality. It also includes a Jacobian method, which returns the Jacobian of the function. If the function is univariate, then the Jacobian is just the derivative. If the function is multivariate (not yet implemented), then the Jacobian will be an array.

The ```Elementary``` module implements some of the elementary functions for use in the forward mode of autodifferentiation, including exp, log, sqrt, sin, cos, tan, asin, acos, atan, sinh, cosh and tanh.

The ```ElementaryReverse``` module implements some of the elementary functions for use in the reverse mode of autodifferentiation. These functions are made distinct from those in the Elementary module by an r at the end of the function name (expr, logr, sqrtr, sinr, cosr, tanr, asinr, acosr, atanr, sinhr, coshr and tanhr).

The ```Graph``` module implements the ComputationalGraph class which allows each node to be recorded in sequence in a graph for later use in value and derivative computation. This module also implements the ComputeValue and ComputeGradient functions, which compute the value and gradient using reverse mode and leveraging the computational graph.

The ```JacobianVectorFunc``` module implements the Jacobian method for vector inputs.

The ```MultivariateVarCreator``` module takes in the values of each variable in a user defined multivariate function, and returns len(kwargs) number of AutoDiff class variables with derivative (seed) as an np.array. The MultivariateVarCreator class acts as a helper function for user to create multiple AutoDiff Objects conveniently (instead of manually create many AutoDiff objects) to use in the evaluation of the multivariate function. Please note that the implementation of multivariate functions is still in progress.

The ```MultivariateVectorAutoDiffEvaluate``` module implements the MultiVarVector_AutoDiff_Evaluate function, which autodifferentiates and evaluates a multivariate function using forward mode at user defined vector input values.

The ```MultivariateVectorVarCreator``` module implements the Multi_Vector_AutoDiff_Creator class, which instantiates multiple AutoDiff objects (for use in multivariate functions).

The ```ReverseJacobVectorFunc``` implements the ReverseVecFunc class, which takes the vector function and variables as inputs, and computes the value and the Jacobian matrix using the reverse mode of automatic differentiation. 

The ```ReverseMode``` module implements the node class, which is a single AutoDiff Object used for reverse mode.


### Testing Suite
Our testing files live in the `test/` directory. The tests are run using pytest.



### Installation procedure

1) For general users, install the autodiff32 package using pip (see 'How to Use autodiff32' above for complete instructions)

```pip install autodiff32```

2) For developers, feel free to clone this repository, and use the requirements.txt file to ensure you have installed all necessary dependencies. 

## Implementation details

The current implementation of AutoDiff32 allows for scalar univariate inputs to functions. Core classes include the AutoDiff class, . AutoDiff32 is externally dependent on numpy, and this dependency has been automatically taken care of in the released version of the package (as well as in the requirements.txt file if the user chooses to manually download the package). AutoDiff32 has implemented a number of elementary functions, as listed above in the description of the basic modules. 

We plan to continue development of the AutoDiff32 package to allow for vector inputs as well as multivariate inputs. This will require robust Jacobian matrix functionality. 

In addition to the currently implemented forward mode, we plan to build out the reverse mode of auto differentiation as an advanced feature.



### Forward mode Details:

The core data structure (and also external dependencies) for our implementation will be numpy arrays, and the core classes we have implemented are described below:

1) An ***AutoDiff class*** which stores the current value and derivative for the current node. The class method will conatin overloading operators such as plus, minus, multiply, etc.

```python
"""
Initialize an Automatic Differentiation object which stores its current value and derivative

Note that the derivative needs to not be a scalar value

For multivariable differentiation problems of a scalar function, the derivative will be a vector
"""

def __init__(self,value,der=1) :
  #Store the value of the Autodiff object
  #Store derivative of autodiff object (default value is 1)


#overloading operators to enable basic operations between classes and numbers (not exhaustive):

"""
These methods will differentiate cases in which other is a scalar, a vector, a class, or any child class

All of these operators will return AutoDiff classes
"""
def __mult__(self,other):
def __rmult__(self,other):
def __radd__(self,other): 
def __add__(self,other):


```

Multivariate functions (both scalar and vector) can be also evaluated using the AutoDiff class as below, and the resulting Jacobian will be a vector array:

```python
X = AutoDiff(1,np.array([1,0]))
Y =  AutoDiff(1,np.array([0,1]))

func = X + 2*Y
```

While this way of defining and evaluating multivariate functions is feasible, it is very inconvenient for the users to have to keep track of the dimensionality of the derivatives. For,example, the above func definition will raise an error if Y's derivative is defined as np.array([0,0,1]). This potential problem in dimensionality will also be a cause difficulties in the error handling process in the code. 

The way we tackle this problem is to create a helper class called **Multi_AutoDiff_Creator** as described below:

2) A ***Multi_AutoDiff_Creator class*** which helps the user create variable objects from a multivariable function

```python

"""
This class helps users initialize different variables from a multivariable function without explicitly specifying them using separate AutoDiff classes

It will need to import AutoDiff Class
"""
	def __init__(self,*args,**kwargs):
    '''
    INPUT : variables as kwargs such as (X=3,Y =4)
    RETURN : X number of autodiff objects with length kwargs and each with its 'vector' derivatives

    '''
    #Demo and comparison

    '''initiate a multivariable function using Multi_AutoDiff_Creator class'''
    X,Y= Multi_AutoDiff_Creator(X = 1., Y=3.).Vars #X,Y are autodiff object with derivative [1,0] and [0,1]
    func = X + 2*Y*X 
```

Notice that this class only serves as a **helper class** to ensure that every variable created has the correct format of dimensionality. The class itself has no influence on the forward mode differentation process.

For better calculation of the derivatives of our elementary functions, we also introduce our elementary function methods.

3) An ***Elementary function*** file which calculate derivatives for elementary functions as described previously
```python  
    #Elementary Function Derivative (not exhaustive):
    def exp(self,ADobj):
    def tan(self,ADobj):
    def sin(self,ADobj):
    def cos(self.ADobj):
    '''
   RETURN an AutoDiff object if ADobj is an AutoDiff object with related value and derivative for the particular elementary functions
   Return np.exp/tan/sin(ODobj) if ODobj is a number
    '''

```

4) A ***Jacobian*** class which helps the user compute the Jacobian matrix for vector functions evaluated at a single point
```python 
class Jacobian:
	def __init__(self,vector_func):
		#The Jacobian class is initiated by a vector function

	def value(self):
    # Return the Jacobian value of the vector functions evaluated at a single point by looping through the vector function
    '''
      x, y = ad.Multi_AutoDiff_Creator(x=2, y=3).Vars
      #Define a vector function
      func = np.array([x+y, 2*x*y])
      Jacob = ad.Jacobian(func)
      print(Jacob.value()) # this class method output the full jacobian matrix as an np array
      '''
```


## Extension


**Description**

The implementation of reverse mode also lies in the same autodiff32 package with no additional extension requirements.

We implemented the reverse mode of automatic differentiation in which users can evaluate univariate and multivariate scalar/vector functions with series or single values. The alogorithm is based on the computational flow chart (graph) for reverse mode discussed in class, in which each node is recorded in sequence in a Graph for later use in value and derivative computation. In particular, each node stores its value, the graph it connects to, and the index it has in the graph. In order to backward compute the derivative for our root node, each node records the parent which produced it through some operations, and also the oepration type ("plus","sub",etc.) itself. 

We find this more intuitive and pedagogical than using recursion, and potentially can be more computationally efficient since each node only has to remeber its direct children, but not the indirect ones. The graph and node can also be reused easily, which makes it simpler and more computationally efficient in our evaluation for multiple values of our variables.

The high level mathematical ideas will be similar to that of the forward mode, the only additional thing that will be helpful to keep in mind is the chain rule, which is:

\begin{aligned}
\frac{dz}{dx} = \frac{dz}{dy}\times\frac{dy}{dx}
\end{aligned}

This will help use understand how we can calculate the derivatives by starting to set seed value of 1 for our function, which is:
\begin{aligned}
\frac{dz}{df} = 1
\end{aligned}
For example, if we would like to calculate the derivative for $f = 2x$ backward,by letting $z=f$,we will have:

\begin{aligned}
\frac{dz}{dx}=\frac{dz}{df}\times\frac{df}{dx} = 1 \times 2 = 2  
\end{aligned}






###Implementation Details for Reverse Mode

The reverse mode implementation will have the following classes:

1) A **Node** class which serve as single automatic differentiation object.All the node will be connected to the same graph for a given function.
```python 
class Node:
  #INITIATOR
  '''
    The Node class is initiated with the paramters mentioned below. The node 
    will connect to the graph as soon as it is created.
  '''
  def __init__(values,Graph,derivative,leftparentnode,rightparentnode,derivative = 0):


  def CheckConstant(x):
    #Check if x is a Node or not. If it is ,return it,
    # if not,return a new node with Node.value = x ,and connect it to the Graph.
  
  #OVERLOADING OPERATORS
  '''
  perform subtraction between nodes
  Return
  ======
  A new node which store the value,the graph it connects to, and self as its left nod and other as its right node. 
  '''
  def __mul__(self,other):
  def __sub__(self,pther):
  def __truediv__(self,other):


```

2 A **ComputationalGraph** class which stores the nodes of a given function in sequence and compute the value and the gradient of the function and the root variables.

```python

class ComputationalGraph:
  
  def __init__(self):
    # the graph is initialized by an empty list
  def append(self):
    #append the node in sequence in the graph and record its index for later computation
  def ValidOp(self):
    # sturcturely store every valid operator in this reverse mode computation
     '''
    RETURN
    ======
    Valid operator code if valid otherwise raise error
    '''
  def ComputeValue(self):
    #Compute the Value of the function by a forward pass of th graph

  def ComputeGradient(self,lastindex  = -1):
    '''
    Backward propagate through the graph to calcutate the derivative of the  nodes and store it in each node by looping through the list in a reverse order and update the parent nodes using child nodes.
    INPUT : Last index is the seed : dz/df = 1

    RETURN
    ======
    NONE
    All the values after computation is stored in each node in the list
    '''
  def SeriesValues(self,args):
    #compute the value and derivatives for 
    #a series of values for a function (illustration in detail in the How to use session)
    '''
    RETURN
    ===
    A two dimensional  Array for derivatives and one dimensional array for values
    Values for the funtion evaulated at different points
    Derivatives of root variables evaluated at different points
    '''

```

3) A class **ReverseVecFunc** which calculate the value and derivative for vector functions evaluated at different points
```python 

class ReverseVecFunc:

  def __init__(self):
    #it stores the variables and the functions when the class is initialized.
  def value(self,Graph):
    #it computes the Jacobian and the value for vector functions for a given single value of variable
  def SeriesValues(self,values,dimension,Graph):
    '''
    INPUT 
    =====
    value = values of the functions
    dimension : the number of variables
    Graph : the graph to be connected
    RETURN
    ======
    The value and the jacobian (both in 2D nparrays) of the function at a series of values
    

    '''
    #pseudocodes
    initialize a valuelist = []
    for each function in vection functions:
       calculate its gradients and values using Wrapper(args)
       append it to a valuelist 

    def Wrapper(args):
      # A helper function to help calculate the values and derivative for a series values
      '''
      INPUT 
      =====
      value = values of the functions
      dimension : the number of variables
      Graph : the graph to be connected
      Returns the derivatives and values of a single function evaluated different values
      '''

```
4) Additional **ElementaryReverse.py** which defines the elementary functions operations for the Node objects
```python

'''
NOTE
=====
In order to differentiate between reverse mode elementary functions and forward mode ones, all the elementary function in reverse mode will have a "r" as the last alphabet.

If user would like to use these function with a constant , please use built in functions in Numpy: such as : np.exp(2), np.sin(3) etc.

RETURN
=====
New Node object that stores the value after related computation and its relevant leftparent node (which is itself). The node returned wont have any rightparent node.

'''
def expr(x):
def logr(x):
def sqrtr(x):
  ...
```


## Future Features
As we have seen, automatic differentiation is an efficient and accurate way to compute derivatives, so it makes sense
to try to apply this where we can. One of the most popular methods that use the derivative is gradient descent.
Gradient descent is an optimization problem where we try to minimize some function. We do this by taking some starting point
and moving in the direction
of the steepest part of the function, or the most negative gradient. To find this minimum point, it makes sense that
want the gradient to be precise, so the point is precise, so automatic differentiation is the natural choice.

Building onto that idea, another use of this could be in neural networks. The entire concept of a neural network
is centered around optimizing its weights, and at each step and each time the node weights update, we need to calculate
lots of partial derivatives, so once again, it makes sense to use automatic differentiation.
Similarly, the concept of deep learning is essentially a large collection of neural networks, so the same utility
from automatic differentiation can be gained here.

Another interesting application can be found in statistics, namely, in a Markov chain Monte Carlo sampling method, called
the Hamiltonian Monte Carlo Algorithm. Without diving into deep statistical explanations, this is an algorithm to create a
random sample from a probability distribution that is difficult to get normally. Most Markov chain Monte Carlo algorithms
coverge quite slowly, and as a result explore the sampling slowly as well. The hamiltonian algorithm
does a better job with convergence, but at the cost of having to evaluate complicated gradients of probability models along the way. 
However, with automatic differentiation, the user no longer has to manually derive the gradients, and this cost can be reduced significantly.

ref:http://jmlr.org/papers/volume18/17-468/17-468.pdf

4214112d8f4f278e364d96995939d39ad0242d3b
ipynb
Jupyter Notebook
docs/documentation.ipynb
ELAA207/cs207-FinalProject
6e4f265c220a2a156bab51e7717878dea252256c
MIT
2019-10-26T12:46:22.000Z
2019-10-26T12:46:22.000Z
docs/documentation.ipynb
ELAA207/cs207-FinalProject
6e4f265c220a2a156bab51e7717878dea252256c
MIT
2019-11-19T07:33:03.000Z
2019-12-10T14:53:05.000Z
docs/documentation.ipynb
ELAA207/cs207-FinalProject
6e4f265c220a2a156bab51e7717878dea252256c
MIT
Qwen/Qwen-72B
1. YES
2. YES