.. role:: python(code)
   :language: python

.. index::
    higher order derivative


..
    `  <>`


.. _`sec:higher_order`:

Higher order derivatives
~~~~~~~~~~~~~~~~~~~~~~~~



The previous section showed the basics of auto-differentiation. 
However, what one really need is to be able to differentiate at higher orders: 
either, second derivatives or cross-derivatives (coordinates and network parameters). 

For the moment, one is able to encode an expression with forward operations, building a computation graph. 
Then, the backward sweep computes the numerical value of all intermediate derivatives. 
However, these *numerical values* are just numerical values. 
It is for the moment impossible to differentiate a second time or with respect to an other parameter. 
What is really required, is to build the computation graph of all the operations of the backward sweep. 

It means that first, a computation graph of the initial expression is obtained during the first forward sweep. 
Then, all the backward operations must build another computation graph of all the operations required to obtain the first derivative. 
Next, this process can be once again repeated, by operating a backward sweep on the computation graph of the first derivative, 
building the computation graph of the second derivatives, and so on and so on.

.. note::

    A backward sweep is just a succession of operations, its computation graph can be built. 
    Then, additional backward sweeps can be performed starting from the nodes representing the derivatives 
    in order to get higher order differentiation and cross-derivatives.


To be able to build the computation graph of a backward sweep, one has to remember the operations involved:

+ set the leaf node to one
+ go backward in a topological order
+ apply the backward operation and cumulate the intermediate result
+ repeat the last two steps

Let us take a trivial example:

.. math::
    :label: eq:ex_higher_order_simple

    f(x) &= x^2 \\
    \cfrac{\partial f}{\partial x}  &= 2 x \\
    \cfrac{\partial^2  f}{\partial x^2} &= 2 

The forward graph is:

.. figure:: ex_higher_simple_forward.png
    :width: 120
    :alt: ex_higher_simple_forward

    Forward sweep (higher)

For the backward sweep, the multiplication with one and the first cumulate with zero creates several useless operations (grey edges):

.. figure:: ex_higher_simple_backward_first.png
    :width: 300
    :alt: ex_higher_simple_backward_first

    Backward sweep (higher)

Dropping the useless stuff:

.. figure:: ex_higher_simple_backward_first_simplified.png
    :width: 120
    :alt: ex_higher_simple_backward_first_simplified

    Simplifified first backward sweep (higher)

The second backward sweep gives:

.. figure:: ex_higher_simple_backward_second.png
    :width: 120
    :alt: ex_higher_simple_backward_second

    Simplifified second backward sweep (higher)

Finally, all the operations together:

.. figure:: ex_higher_simple_all.png
    :width: 350
    :alt: ex_higher_simple_all

    Overall (higher)

Example
"""""""

A slightly less trivial example with a function of two variables (to see how cross-derivatives can be obtained):

.. math::
    :label: eq:ex_higher_order

    f(x,y) &= (x y)^2 \\
    \cfrac{\partial f}{\partial x}  &= 2 x y^2 \\
    \cfrac{\partial f}{\partial y} &= 2 x^2 y \\
    \cfrac{\partial^2  f}{\partial x^2} &= 2  y^2 \\
    \cfrac{\partial^2  f}{\partial x \partial y} &= 4 x y

The forward graph is:    

.. figure:: higher_ex_first_forward.png
    :width: 120
    :alt: higher_first_forward

    Forward sweep (higher)


Let us take this simple example, and list very pedantically  *every* operation of the backward sweep. 
The previous edges are dashed.

.. figure:: higher_ex_first_backward.png
    :width: 500
    :alt: higher_first_backward

    Backward sweep (higher)


To clarify, let us drop the multiplication by a constant :math:`1` and the addition to a constant :math:`0` 
which are the grey edges, one gets:

.. figure:: higher_ex_first_backward_simplified.png
    :width: 400
    :alt: higher_first_backward_simplified

    Backward sweep simplified (higher)

Starting from the node representing the :math:`\cfrac{\partial f}{\partial x}` (d), a backward sweep is performed:

.. figure:: higher_ex_second_backward_from_dx.png
    :width: 500
    :alt: higher_second_backward

    Second backward sweep simplified (higher)

If everything so far is put together, the overall computation graph is obtained. 
The bottom left red solid  node is :math:`\cfrac{\partial f}{\partial x}`; 
the  bottom right blue solid  node is :math:`\cfrac{\partial f}{\partial y}`; 
the central left red dashed node is :math:`\cfrac{\partial^2 f}{\partial x^2}`; 
the bottom central purple dashed node is :math:`\cfrac{\partial^2 f}{\partial x \partial y}`; 

.. figure:: higher_ex_all.png
    :width: 700
    :alt: higher_all

    Overall (higher)


Implementation
""""""""""""""

As expected, even though the process is plain and systematic, it is very tedious. 
Let us implement it. 
The key point to grasp is that formerly, all the intermediate derivatives were just numerical values stored in a :python:`dict`, 
however from now on, all the operations leading to such derivatives are recorded in a computation graph. 
It implies two major changes:

+ the derivative values become :python:`Node` instead of :python:`float`
+ the operations used to calculate derivatives: the :python:`backward` operations, must now on use the :python:`forward` operations 
  in order to create the computation graph of every backward sweep.

.. literalinclude:: ../../../../../../src/ai/fnn/autodiff_higher.py
      :pyobject: Node
      :name: node_class_higher
      :linenos:       
      :caption: src  

The attribute :python:`operation` is there only for debugging purposes, as is the :python:`name`. 
The :python:`differentiate` function is almost identical:

.. literalinclude:: ../../../../../../src/ai/fnn/autodiff_higher.py
      :pyobject: differentiate
      :name: differentiate_higher
      :linenos:       
      :caption: src  


.. admonition:: Exercise (intermediate)

    Implement and test the multiplication and addition backward operations.

.. _`ex:ad_mult_add_higher`:

.. collapse:: Correction

    .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_higher.py
      :pyobject: multiplication_backward
      :name: multiplication_backward_higher
      :linenos:       
      :caption: src 

    .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_higher.py
      :pyobject: addition_backward
      :name: addition_backward_higher
      :linenos:       
      :caption: src 

    .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_higher.py
      :pyobject: x_val
      :name: x_val_higher
      :linenos:       
      :caption: tests 

    .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_higher.py
      :pyobject: x_pow_one_by_one
      :name: x_pow_one_by_one_higher
      :linenos:       
      :caption: tests 

    .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_higher.py
      :pyobject: x_sum_one_by_one
      :name: x_sum_one_by_one_higher
      :linenos:       
      :caption: tests 

    .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_higher.py
      :pyobject: assert_derivatives
      :name: assert_derivatives_higher
      :linenos:       
      :caption: tests 

    .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_higher.py
      :pyobject: test_derivatives_pow_one_by_one
      :name: test_derivatives_pow_one_by_one_higher
      :linenos:       
      :caption: tests 
      
    .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_higher.py
      :pyobject: test_derivatives_sum_one_by_one
      :name: test_derivatives_sum_one_by_one_higher
      :linenos:       
      :caption: tests