# CS207 Final Project: Milestone 1 - October 29 2019
Geng Yichen, Jian Yingsi, Meeus Matthieu, Zhang Lihong

# Introduction




Derivatives come up in every aspect of science and engineering. Calculus taught us how to derive analytical expressions of functional derivatives, but in many cases this is either impossible or too much of a hassle. Therefore, numerical methods or algorithmic approaches to compute the derivative are extremely important. 
Methods of computing functions' derivatives in computer programs can be classified into 4 types: 

(1) Determining derivatives by hands and coding them. <br/>
(2) Symbolic differentiation in computer tools, such as Mathematica and Maple. <br/>
(3) Numerical methods: using finite differences to approxiate derivatives. <br/>
(4) Automatic Differentiation, which is the subject of our project. <br/>

Automatic differentiation (AD) is a set of techniques for evaluating functional derivatives efficiently and accurately in computer programs. For any analytic function f(x) to be differentiated at a point $x_0$, AD first rewrites f(x) as a combination of elementary functions, then determining the derivative values of f(x) through combining derivatives of elementary functions by the chain rule. Since the derivative values of all elementary functions are known and accurate, and the procedures of AD have no potential sources of errors except tiny rounding errors due to machine precision, thus the derivative values obtained by AD are accurate. As for other differentiation methods, manual calculating functional derivatives and coding them by hands can be tedious, time-consuming and prone to make mistakes; symbolic differentiation could return rigmarole and unreadable symbolic expressions; and numerical method of finite differences could be ill-conditioned due to truncation and round-off errors, and is also inappropriate to handle functional derivatives with many independent variables. 

For example, in the numerical method of finite difference, the derivative is calculated as the following where the limit for h is approached but not put to zero:

$$\frac{df}{dx} \approx \frac{f(x+h) - f(x)}{h}$$

While this approach yields decent results in many cases, it is never completely accurate. For too large values of h, the error originates from the intrinsic error of the finite difference derivative. For too small values of h, the error originates from rounding errors. 

Although AD does not show explicit derivative expressions, people usually only want to obtain derivative values at some points rather than symbolic expressions, thus AD is much better than other differentiation methods with respect to determining functional derivative values.

In modern differentiation computation, AD is the most efficient and accurate tool to implement differentiation in computer programs. In this project, we will design an accurate, user-oriented differentiation calculator by implementing AD.


# Background




Automatic differentiation is an algorithmic approach to compute derivatives up until machine precision accuracy. It has two common methods: forward and reverse mode. In this project, only the forward mode will be discussed at first. Forward automatic differentiation leverages the chain rule to split the differentiation of a complex function in elementary functions and makes use of the easy derivatives of elementary functions.  If $h(u(t))$ is the function of which the derivative is required, the chain rule for partial derivatives says:

$$\frac{\partial h}{\partial t} = \frac{\partial h}{\partial u}*\frac{\partial u}{\partial t}$$

Or for $h(u(t), v(t))$:

\begin{equation}
    \frac{\partial h}{\partial t} = \frac{\partial h}{\partial u}*\frac{\partial u}{\partial t} + \frac{\partial h}{\partial v}*\frac{\partial v}{\partial t}
\end{equation}

Hence, the computation of the derivatives of complicated functions that consist of multiple, consequent elementary operations can be split into the multiplication and addition of derivatives of the elementary functions in the following table. Examples of the elementary operations are addition and multiplication but also sine, cosine and log. The complete list of elementary functions that will be incorporated in this package can be found in 'Implementation'. A subset is illustrated in the table below:

| Elementary function        | Example | 
| :-------------: |:-------------:|
| Field Operations    | $+ - * / $ |
| Powers     |$x^2, x^6$|
| Roots     |$\sqrt{x}$|
| Trigonometric     |$sin(x)$|
| Inverse Trigonometric     |$asin(x)$|
| Logaritmic     |$log(x)$|
| Exponential    |$e^x$|

The split of the complex function into its elementary operations is commonly visualized in a so-called computational graph. This summarizes the sequence of operations that need to be done for the evaluation and differentiation of the function. An example for the simple function $f(x,y) = xy + exp(xy) $ is given in the image below. Note that this example comes from Lecture 12.



For functions in higher dimensions h(x): ${\rm I\!R}^m \rightarrow {\rm I\!R}^n$, the entire Jacobian will be computed using the same, simple approach. Recall the definition of the Jacobian J in ${\rm I\!R}^{nxm}$ for function h(x):

$$\mathbf{J}=\left[\begin{array}{cccc}
\frac{\partial h_1}{\partial x_1} & \frac{\partial h_1}{\partial x_2} & .. & \frac{\partial h_1}{\partial x_m} \\
\frac{\partial h_2}{\partial x_1} & \frac{\partial h_2}{\partial x_2} & .. & \frac{\partial h_2}{\partial x_m} \\
.. & .. & .. & .. \\
\frac{\partial h_n}{\partial x_1} & \frac{\partial h_n}{\partial x_2} & .. & \frac{\partial h_n}{\partial x_m}
\end{array}\right]$$

Note that in many cases the gradient of h with respect to an input variable $x_i$ is required. For $x_i$ this will correspond to the i-th column of the Jacobian.

# How to Use AutoDiff

To use the package, users need to use pip to install the package and then import it. 

```python
>>> from AutoDiff.ForwardAd import Var
>>> import numpy as np
>>> x = Var(np.array([2.0]), np.array([1, 0]))
>>> y = Var(np.array([3.0]), np.array([0, 1]))
>>> f = x*y
>>> f.val
array([6.])
>>> f.jacobian
array([3., 2.])
```

# Software Organization


**Porject Directory Structure**



  
                    CS207-FinalProject/
                                       README.md
                                       LICENSE
                                       setup.py
                                       AutoDiff/
                                                _init_.py
                                                ForwardAD.py
                                       docs/
                                                     milestone1.ipynb
                                       Test/
                                            test_suite.py
                                       Demo/
                                            presentation.pdf
                                       ...
                   
                           
**Included Modules and Basic Functionality**

NumPy: A general-purpose array-processing package. It provides a high-performance multidimensional array object, and tools for working with these arrays. For details, see https://numpy.org

pytest: A software test framework, which is a command-line tool that automatically finds written tests, runs the tests, and reports the results. For details, see https://docs.pytest.org/en/latest/

Setuptools: A fully-featured, actively-maintained, and stable library designed to facilitate packaging Python projects. 
For details, see https://setuptools.readthedocs.io/en/latest/

doctest: This module searches for pieces of text (usually in the documentation part) that look like interactive Python sessions, and then executes those sessions to verify that they work exactly as shown. For details, see https://docs.python.org/3/library/doctest.html


**Test**

The test suites live in *CS207-FinalProject/Test/* folder.  We will use Travis CI to run tests and use CodeCov to automatically checks code coverage. 


**Distributing Our Package**

We will use PyPI to distribute our package. The Python Package Index (PyPI) is a repository of software for the Python programming language.


**Packaging**

We will follow the Python Packaging User Guide published by the Python Packaging Authority(PyPA), which is the authoritative resource on how to package, publish, and install Python projects using current tools. We will use Setuptools because it is comprehensive, actively-maintained, and stable to  create an package for easy distibution out of our project.












# Implementation

**Core Data Structures**\
The core data structure is `numpy.array`.

**Classes to be Implemented?**\
Inside the `ForwardAD.py`, we will implement the `Var` class.

**Method and Name Attributes of Classes**\
The `Var` class has two attributes: `self.val`, which stores the value of the current function and `self.jacobian`, which is represented by a `numpy.array` and stores the function's partial derivatives. We will overload operators by dunder methods, including `__add__`, `__sub__`, `__mul__`, `__truediv__`,  `__pow__` and define exponential, logarithmic, square root and trignometric functions. The following is an example of what the structure of `Var` class will look like. We temporarily use `pass` in the content of each method, and we will replace them by the real codes in the following process.

```python
class Var:
    def __init__(self, a, j):
        self.val = a
        self.jacobian = j
    
    def __add__(self, other):
      pass
    
    def __sub__(self, other):
      pass
    
    def __mul__(self, other):
      pass
    
    def __truediv__(self, other):
      pass
    
    def __pow__(self, other):
      pass
    
    def exp(self):
      pass
    
    def log(self):
      pass
    
    def sqrt(self):
      pass
    
    def sin(self):
      pass
    
    def cos(self):
      pass

    def tan(self):
      pass
```

**External Dependencies**\
We will rely on the `NumPy` package.

**Dealing with Elementary Functions**\
We will define methods that represent these elementary functions inside the `Var` class (see the example above). When calling these functions, we can simply use `Var.function_name`. For example,

```python
>>> x = Var(np.array([4.0]), np.array([1]))
>>> f = Var.sqrt(x)
>>> f.val
array([2.])
>>> f.jacobian
array([0.25])
```



bf25c080fd73658d039fbd37bd7e70290200e96b
ipynb
Jupyter Notebook
docs/milestone1.ipynb
BackPropagators/cs207-FinalProject
6ec7d35f1af3b091d8c93c59bc0e8fe286a5fafc
MIT
docs/milestone1.ipynb
BackPropagators/cs207-FinalProject
6ec7d35f1af3b091d8c93c59bc0e8fe286a5fafc
MIT
docs/milestone1.ipynb
BackPropagators/cs207-FinalProject
6ec7d35f1af3b091d8c93c59bc0e8fe286a5fafc
MIT
Qwen/Qwen-72B
1. YES
2. YES