.. role:: python(code) :language: python .. index:: auto-differentiation computation graph reverse differentiation forward / backward sweep back-propagation topographic order deep learning; auto-differentiation deep learning; topographic order .. `Unary computation graph ` `Binary (division) computation graph ` `First derivative automatic differentiation ` .. _`sec:autodif`: Automatic Differentiation ^^^^^^^^^^^^^^^^^^^^^^^^^ When using neural network packages, one of the most ubiquitous yet hidden feature is the automatic differentiation. Without diving too deep, especially in the performance optimization domain, the basic principle is worth understanding. But first, why not using one of the method of differentiation you already know: + symbolic: using symbolic variables everywhere, by opposition to 'normal' variable which stores only numbers, is theoretically possible, but in practice untractable in term of computation cost. Imagine deep neural networks, with millions of parameters. + numerical approximation: using local numerical slope suffers means that the entire network is evaluated with a forward pass for every parameter. The automatic differentiation is both exact up to machine accuracy, and efficient accounting for the structure of the problem. First order derivative ~~~~~~~~~~~~~~~~~~~~~~ Even if it is not sufficient for our purpose, it is still useful to understand a simpler algorithm limited to first order differentiation. Two ingredients are introduced, first, the notion of **computation graph**, second, the concept of **forward** and **backward** sweeps. There are two types of operations: unary or binary operations. Unary operation """"""""""""""" A unary operation represents taking a function of a variable, for example: .. math:: :label: eq:ad_unary u &= f(x) \\ v &= g(u) In this configuration, the derivatives can be obtained applying the chain rule: .. math:: \cfrac{\partial v}{\partial x} = \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{f'(x)} For a specific :math:`f=\sin` function and a specific :math:`x` value one gets: .. math:: :label: eq:ad_unary_chain x &= \cfrac{\pi}{6} \\ u &= \sin(x) = \cfrac{1}{2}\\ \cfrac{\partial v}{\partial x} &= \underbrace{\cfrac{\partial v}{\partial u}}_{\textrm{known}} \cos(x) = \cfrac{\partial v}{\partial u} \cfrac{\sqrt{3}}{2} This case can be symbolized by the two following graphs. The first represents the evaluation of the overall function :math:`u`, then :math:`v`, etc. This is the forward sweep from top to bottom. The circle nodes are variables; the double rectangular nodes are top the value and bottom the derivative value; the diamond nodes are applied functions. .. figure:: unary_forward.png :width: 100 :alt: unary forward Forward sweep for a unary operation The second represents the evaluation of the derivatives from bottom to top. The very last derivative represents the variation of the last variable with respect to itself; which is :math:`1`. The last derivative is then known, as a result, step by step one can backtrack all the successive derivatives. .. figure:: unary_backward.png :width: 100 :alt: unary backward Backward sweep for a unary operation .. admonition:: Exercise (easy) Draw the computation graph and calculate the derivative of :math:`\ln(\sin(x))` at :math:`x=\cfrac{\pi}{3}`. .. _`ex:computation_graph_unary`: .. collapse:: Correction The symbolic calculation gives: .. math:: \cfrac{\partial }{\partial x} \ln(\sin(x)) = \cfrac{\cos(x)}{\sin(x)} .. figure:: correction_unary_forward.png :width: 100 :alt: forward ln(sin(x)) Forward sweep .. figure:: correction_unary_backward.png :width: 100 :alt: backward ln(sin(x)) Backward sweep The second type of operation is binary. All the common calculus operator are binary: addition, multiplication, division, etc. Binary: addition """""""""""""""" .. math:: :label: eq:ad_add u &= x+y \\ v &= g(u) The derivatives can be obtained applying the chain rule: .. math:: :label: eq:ad_add_chain \cfrac{\partial v}{\partial x} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{=1} \\ \cfrac{\partial v}{\partial y} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial y} }_{=1} .. figure:: add_forward.png :width: 120 :alt: add forward Forward sweep for the add operation .. figure:: add_backward.png :width: 140 :alt: add backward Backward sweep for the add operation Binary: multiplication """""""""""""""""""""" .. math:: :label: eq:ad_mult u &= x y \\ v &= g(u) The derivatives can be obtained applying the chain rule: .. math:: :label: eq:ad_mult_chain \cfrac{\partial v}{\partial x} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{=y} \\ \cfrac{\partial v}{\partial y} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial y} }_{=x} .. figure:: mult_forward.png :width: 120 :alt: multiplication forward Forward sweep for the multiplication operation .. figure:: mult_backward.png :width: 140 :alt: multiplication backward Backward sweep for the multiplication operation .. admonition:: Exercise (easy) Draw the computational graph for the division operation. .. _`ex:ad_div`: .. collapse:: Correction .. math:: :label: eq:ad_div u &= \cfrac{x}{y} \\ v &= g(u) The derivatives can be obtained applying the chain rule: .. math:: :label: eq:ad_div_chain \cfrac{\partial v}{\partial x} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial x} }_{=\cfrac{1}{y}} \\ \cfrac{\partial v}{\partial y} &= \underbrace{ \cfrac{\partial v}{\partial u}}_{g'(u)} \underbrace{\cfrac{\partial u}{\partial y} }_{=\cfrac{-x}{y^2}} .. figure:: div_forward.png :width: 120 :alt: division forward Forward sweep for the division operation .. figure:: div_backward.png :width: 200 :alt: division backward Backward sweep for the division operation Reverse order """"""""""""" Imagine the following computation graph: .. figure:: order_forward.png :width: 140 :alt: order forward Forward sweep (order) The first step of the reverse sweep gives: .. figure:: order_backward_first.png :width: 140 :alt: order backward first Backward sweep (order, first step) At this stage, there are two possibilities: + either, one continues upward with the right branch which leads temporarily to a :math:`3+3` in the :math:`x` derivative, then go back to where one stopped and continue up the left branch, which leads to a :math:`1+\exp(9)` in the :math:`u` derivative, and finally :math:`(3+3) + (3(1+\exp(9)) + 3(1+\exp(9)))` in the :math:`x` derivative. + or, first one levels up the left branch and get a :math:`1+\exp(9)` in the :math:`u` derivative, then :math:`3(1+\exp(9)) + 3(1+\exp(9))` in the :math:`x` derivative. Obviously, the second solution is the correct one if you check the symbolic derivative. It means that the **traversal order** of the computation graph is important, one needs to ensure that an intermediate derivative is fully calculated before propagating backward. This ordering has already been encountered in the traversal algorithm section, it is the **topographic order**. .. figure:: order_backward.png :width: 200 :alt: order backward Backward sweep (order) Implementation """""""""""""" A simple implementation of a first order auto-differentiation can be based on the following data structure: .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: Node :name: node_class_first :linenos: :caption: src and the following function to obtain the first derivative: .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: differentiate :name: differentiate_first :linenos: :caption: src The :python:`forward` operations (addition, multiplication, etc) build a computation graph. Then, the reverse sweep starting from the final node and going backward in a topographic order executes all the :python:`backward` operation described above. .. admonition:: Exercise (intermediate) 1. The :python:`Node` class is not commented on purpose. Explain briefly the role you imagine for every attributes and methods. 2. Define a single :python:`forward` unary operation the corresponding :python:`backward` operation, such as :math:`\log` for example. Use it (potentially composed several times :math:`\log(\log(\cdots))`) and check out the forward pass value and name. 3. In the :python:`differentiate` function, you see that first, the traversal order is obtained, then the backward callback is executed on every node from the very end to the very start. The only missing brick is the function :python:`topological_sort`. Implement it. Test it. Then, test the entire algorithm on the unary function of your choice. 4. Define a single :python:`forward` binary operation the corresponding :python:`backward` operation, such as the multiplication. Use it (potentially composed several times :math:`((x * x) * x)`) and check out the forward pass value and name. Test it. Check the topographic order. Test the entire algorithm. 5. Implement and test all the other useful operations. .. _`ex:ad_first`: .. collapse:: Correction 1. A :python:`forward` operation takes one (unary) or two (binary) nodes and produces a result node. Depending on the forward operation (addition, multiplication etc), the result :python:`val` attribute value is calculated from the :python:`val` of the single or double :python:`parents`. The :python:`val` attribute represents the content of the first rectangular node. A node can represent either a variable, or a constant. The attribute :python:`is_constant` records this point. A node can either be created as constant manually, or be automatically constant if all its parents are constant. The :python:`backward` attribute is a callable which takes a node and computes set the local derivative value in the parent node(s). The :python:`index` attribute is a unique node identifier. The :python:`_counter` class attribute keeps count of how many nodes were created in order to produce a unique :python:`index`. (The :python:`name` is the less transparent and most optional. It is mostly useful for debugging. It will be used to represent in a readable format each operation "(:python:`name` first parent \*\|+\|... :python:`name` second parent)".) 2. .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: log_forward :name: log_forward :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: log_backward :name: log_backward :linenos: :caption: src 3. .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: topological_sort :name: topological_sort :linenos: :caption: src .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_first.py :pyobject: test_topological_sort :name: test_topological_sort :linenos: :caption: tests 4. .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: multiplication_forward :name: multiplication_forward :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :pyobject: multiplication_backward :name: multiplication_backward :linenos: :caption: src .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_first.py :pyobject: x_val :name: x_val :linenos: :caption: tests .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_first.py :pyobject: x_pow_one_by_one :name: x_pow_one_by_one :linenos: :caption: tests .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_first.py :pyobject: assert_derivatives :name: assert_derivatives :linenos: :caption: tests .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_first.py :pyobject: test_derivatives_pow_one_by_one :name: test_derivatives_pow_one_by_one :linenos: :caption: tests 5. .. literalinclude:: ../../../../../../src/ai/fnn/autodiff_first.py :name: autodiff_first :linenos: :caption: src .. literalinclude:: ../../../../../../tests/ai/fnn/test_autodiff_first.py :name: test_autodiff_first :linenos: :caption: tests