.. role:: python(code) :language: python .. `neural network jacobian ` `numpy basics ` `back-propagation and gradient descent ` .. index:: deep learning; layer deep learning; back-propagation deep learning; gradient deep learning; fit layer gradient .. _`sec:back_prop_real`: Real case ^^^^^^^^^ .. note:: In this section, indices enable to number the nodes in a layer (example: :math:`a_j` is the :math:`j`-th node of the last layer which has :math:`n_j` nodes). A forward neural network transform an input :math:`x` composed by :math:`n_i` components :math:`x_i` into an output layer :math:`j` composed by :math:`n_j` components :math:`a_j`. Between those, several hidden layers are found. An example in the training data is composed by a pair :math:`(x, y)`: an input and a target. A target is composed by :math:`n_j` components :math:`y_j` (same number as the output layer). Every layer can have a different number of nodes. The figure :ref:`Real case FNN (basecase)` shows this graph. Many edges, weights and biases are omitted for clarity. Every node of each layer is actually connected to every node of the next. The dashed lines on the right symbolize a comparison between the output layer :math:`j` and the training target :math:`y`. The dotted lines indicate the index of nodes inside a layer. Focusing on the last layer :math:`j`, the only weight and bias which appear are the weight :math:`w_{jk}` between nodes :math:`a_k` and :math:`a_j` and the bias :math:`b_j` of node :math:`a_j`. The goal is to be able to compute the gradients of the loss function with respect to :math:`w_{jk}` and :math:`b_j`. These gradients will be used in the gradient descent algorithm to optimize these weights and biases in order to minimize the loss function over all the training examples. Let us use :math:`t` as the index for the :math:`n_t` training example pairs :math:`(x, y)_t`. .. _`fig:real_fnn_basecase`: .. figure:: backprop.dot.png :width: 600 :alt: Simple case FNN - basecase Real case FNN - (basecase) Regression ~~~~~~~~~~ Similarly to the :ref:`simple case `, the cost :math:`J` is shown in equation :eq:`eq:cost_real_case` from the comparison of the training targets to all the predictions made by the network. As mentioned, the simplest cost for regression is the average norm 2 of the difference between training targets and estimations. .. math:: :label: eq:cost_real_case J = \cfrac{1}{n_t} \sum _t \cfrac{1}{2} \sum _j (a_{jt} - y_{jt})^2 For clarity, the averaging over :math:`t` will be dropped for the time being. Since the gradient of a sum is the sum of the gradients, let us write down the equation for a single training example, then at the very end, the averaging over training data will be seamlessly reintroduced. .. math:: :label: eq:cost_real_case_simplified J = \cfrac{1}{2} \sum _j (a_{j} - y_{j})^2 A value of the node :math:`a_j` is obtained in two steps from all the values of the previous layer nodes :math:`a_k`. First one obtains the intermediate variable :math:`z_j` using the weights :math:`w_{jk}` and bias :math:`b_j` of the edge leading to the node :math:`a_j` from the :math:`k` layer, then the activation function :math:`\sigma(z_j)` is used, see equations :eq:`eq:steps_node_value_aj_real_case`: .. math:: :label: eq:steps_node_value_aj_real_case z_j &= b_j + \sum_k w_{jk} \cdot a_k \\ a_j &= \sigma(z_j) The derivation chain rule is applied to compute the gradient terms for the last layer, see equations :eq:`eq:chain_rule_simple_case_wj` and :eq:`eq:chain_rule_simple_case_bj`. The equations are the same as the :ref:`sec:back-prop:simple case` because only a single term of the sum has a :math:`w_{jk}` term in it for a specific value of :math:`(j, k)` as illustrated in figure :ref:`Real case FNN - (w_jk)`. .. _`fig:real_fnn_wjk`: .. figure:: backprop_wjk.dot.png :width: 600 :alt: Simple case FNN - wjk Real case FNN - (:math:`w_{jk}`) .. math:: :label: eq:chain_rule_ream_case_wjk \cfrac{\partial J}{\partial w_{jk}} &= \left( \cfrac{\partial J}{\partial a_j}\cfrac{\partial a_j}{\partial z_j} \right) \cfrac{\partial z_j}{\partial w_{jk}} \\ &= \underbrace{ \left( (a_j - y_j)\cdot \overbrace{\sigma'(z_j)}^{=1 \textrm{ if linear last layer}} \right) }_{ \cfrac{\partial J}{\partial z_j} } \cdot a_k .. math:: :label: eq:chain_rule_real_case_bj \cfrac{\partial J}{\partial b_j} &= \cfrac{\partial J}{\partial z_j} \cfrac{\partial z_j}{\partial b_j} \\ &= \cfrac{\partial J}{\partial z_j} \cdot 1 To obtain the node :math:`a_k` from all the nodes :math:`a_{k\ell}`: .. math:: :label: eq:steps_node_value_ak_real_case z_k &= b_k + \sum_{\ell} w_{k\ell} \cdot a_{\ell} \\ a_k &= \sigma(z_k) The derivation chain rule is also applied to compute the gradient terms for the second to last layer, see equations :eq:`eq:chain_rule_real_case_wkl` and :eq:`eq:chain_rule_real_case_bk`. However, as illustrated in figure :ref:`Real case FNN - (w_kl)`, this time all the nodes :math:`a_j` are affected by a change in :math:`w_{k\ell}` and a summation is required. .. _`fig:real_fnn_wkl`: .. figure:: backprop_wkl.dot.png :width: 600 :alt: Simple case FNN - wkl Real case FNN - (:math:`w_{k\ell}`) .. math:: :label: eq:chain_rule_real_case_wkl \cfrac{\partial J}{\partial w_{k\ell}} &= \sum_j \cfrac{\partial J}{\partial z_j} \left( \cfrac{\partial z_j}{\partial a_k}\cfrac{\partial a_k}{\partial z_k} \right) \cfrac{\partial z_k}{\partial w_{k\ell}} \\ &= \underbrace{ \left( \sum_j \cfrac{\partial J}{\partial z_j} \cdot \left( w_{jk} \cdot\sigma'(z_k) \right) \right) }_{ \cfrac{\partial J}{\partial z_k} } \cdot a_{\ell} .. math:: :label: eq:chain_rule_real_case_bk \cfrac{\partial J}{\partial b_k} &= \cfrac{\partial J}{\partial z_k} \cfrac{\partial z_k}{\partial b_k} \\ &= \cfrac{\partial J}{\partial z_k} \cdot 1 From this point, the method should seem straightforward. Equation :eq:`eq:chain_rule_real_case_wkl` shows how to obtain the sensitivity :math:`\cfrac{\partial J}{\partial z_k}` of the cost to a variation of :math:`z_k` from the sensitivities of the forward next layer :math:`\cfrac{\partial J}{\partial z_j}`. This step is repeated from right to left to compute the cost gradient component for every weight and bias. For example, the next step is to obtain the gradient terms relative to the :math:`\ell` layer. Figure :ref:`Real case FNN - (w_lm)` shows that a change in the :math:`w_{\ell m}` coefficients impacts the values of all nodes of all forward layers. However, the sensitivities :math:`\cfrac{\partial J}{\partial z_k}` are already known. The main task is only to obtain the :math:`\cfrac{\partial J}{\partial z_\ell}` from them, see equations :eq:`eq:chain_rule_real_case_wlm` and :eq:`eq:chain_rule_real_case_bl`. .. _`fig:real_fnn_wlm`: .. figure:: backprop_wlm.dot.png :width: 600 :alt: Simple case FNN - wlm Real case FNN - (:math:`w_{\ell m}`) .. math:: :label: eq:chain_rule_real_case_wlm \cfrac{\partial J}{\partial w_{\ell m}} &= \sum_k \cfrac{\partial J}{\partial z_k} \left( \cfrac{\partial z_k}{\partial a_\ell}\cfrac{\partial a_\ell}{\partial z_\ell} \right) \cfrac{\partial z_\ell}{\partial w_{\ell m}} \\ &= \underbrace{ \left( \sum_k \cfrac{\partial J}{\partial z_k} \cdot \left( w_{k\ell} \cdot\sigma'(z_\ell) \right) \right) }_{ \cfrac{\partial J}{\partial z_\ell} } \cdot a_{m} .. math:: :label: eq:chain_rule_real_case_bl \cfrac{\partial J}{\partial b_\ell} &= \cfrac{\partial J}{\partial z_\ell} \cfrac{\partial z_\ell}{\partial b_\ell} \\ &= \cfrac{\partial J}{\partial z_\ell} \cdot 1 Once all the gradients components are calculated, they must be averaged on several inputs to form a correction for the :ref:`gradient descent`. Multi-class classification ~~~~~~~~~~~~~~~~~~~~~~~~~~ For multi-class classification, even if the loss function seems very different, the final expression for the gradient is very similar. With the loss function for a single training example, a single non zero term corresponding to the correct class in the following sum: .. math:: :label: eq:loss_multi_single J &= - \sum_{j} y_{j} \ln(a_{j}) &= - \ln(a_{j=j^*}) With :math:`j^*` the index of the correct class, the chain rule for the last layer is: .. math:: :label: eq:chain_rule_ream_case_wjk_multiclass \cfrac{\partial J}{\partial w_{jk}} &= \left( \cfrac{\partial J}{\partial a_j}\cfrac{\partial a_j}{\partial z_j} \right) \cfrac{\partial z_j}{\partial w_{jk}} \\ &= \left( \left(- \cfrac{1}{ a_{j=j^*}} \right) \cdot a_{j=j^*} (y_{j=j^*}-a_{j=j^*}) \right) \cdot a_k \\ &= \underbrace{ \left( a_{j=j^*} - y_{j=j^*} \right)}_{\cfrac{\partial J}{\partial z_j}} \cdot a_k .. &= \left( \left(- \sum_{j} \cfrac{y_{j}}{ a_{j}} \right) \cdot\sigma'(z_j) \right) \cdot a_k \\ This expression is similar as the one obtained for regression for a linear last layer. .. note:: Both for regression or multi-class classification, the gradient is null when the estimation meets the target exactly: if the prediction is perfect, no need for a correction. .. hint:: Concerning the implementation of these type of expression: + try to identify matrix multiplication disguised in index notation. (then use :python:`dot`) + remember that you can always transpose a matrix if the summation is carried along the row index. + take advantage of numpy element-wise operations. + take advantage of `numpy broadcasting rules `_. + a 1d array can be converted into a 2d array with one size equal to 1 using :python:`np.newaxis`. .. admonition:: Exercise (easy) Lower case symbols are 1d array; upper case symbols are 2d array. Implement concisely the following equations (use non square 2d arrays): 1. :math:`w_i = u_i v_i` 2. :math:`v_i = \sum_j u_j A_{ij}` 3. :math:`v_j = \sum_i u_i A_{ij}` 4. :math:`B_{ij} = A_{ij} u_j` 5. :math:`B_{ij} = A_{ij} u_i` 6. :math:`A_{ij} = u_i v_j` .. _`ex:numpy`: .. collapse:: Correction .. literalinclude:: ../../../../../../src/ai/fnn/numpy_training.py :name: numpy_training :linenos: :caption: src .. admonition:: Exercise (difficult) 1. How would you calculate :math:`\cfrac{\partial a_j}{\partial x_i}` (first, for a single :math:`j, i` pair, then for any :math:`j` and a given :math:`i`)? How to generalize to the entire jacobian (any :math:`j, i`)? 2. Draw by hand the shape of every operation required to implement the jacobian with matrix product, transpose and broadcast. 3. Analyze the following code and map every operation to the previous question. .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.jacobian :name: jacobian :linenos: :caption: src .. _`ex:jacobian`: .. collapse:: Correction 1. .. math:: \cfrac{\partial a_j}{\partial x_i} &= \cfrac{\partial a_j}{\partial z_j} \sum _k \cfrac{\partial z_j}{\partial a_k} \cfrac{\partial a_k}{\partial x_i} \\ &= \sigma'(z_j) \sum _k w_{jk} \cfrac{\partial a_k}{\partial x_i} \\ &= \sigma'(z_j) \sum _k w_{jk} \sigma'(z_k) \sum _l w_{kl} \cfrac{\partial a_l}{\partial x_i}\\ &= \sigma'(z_j) \sum _k w_{jk} \sigma'(z_k) \sum _l w_{kl} \sigma'(z_l) \sum _m w_{lm} \cfrac{\partial a_m}{\partial x_i} When reaching the first layer, the :math:`\cfrac{\partial a_m}{\partial x_i}` is simpler: .. math:: \cfrac{\partial a_m}{\partial x_i} &= \cfrac{\partial a_m}{\partial z_m} \cfrac{\partial z_m}{\partial x_i} \\ &= \sigma'(z_m) w_{mi} As a result, if an inference has been performed for a given input :math:`x`, then all the :math:`z` and :math:`a` are up to date. Then, the calculation looks a little like an inference: .. math:: \cfrac{\partial a_m}{\partial x_i} = \sigma'(z_m) w_{mi} &~ \textrm{which is a vector varying } m \\ \sum _m w_{lm} \cfrac{\partial a_m}{\partial x_i} &~ \textrm{ is a product between weight matrix and the previous vector } \\ \sigma'(z_l) \sum _m w_{lm} \cfrac{\partial a_m}{\partial x_i} &~ \textrm{can be obtained with a broadcast of the activation derivative vector } \\ \sum _l w_{kl} \cfrac{\partial a_l}{\partial x_i} &~ \textrm{ is a product between weight matrix and the previous vector } One can just as easily obtain the full jacobian matrix if one considers the first line as a matrix for all :math:`m` and :math:`i`. When only linear activation functions are used, the gradient is logically found to be the product of every weight matrices. 2. .. figure:: jacobian.png :width: 800 :alt: Jacobian Jacobian 3. The only trick is to start by the :python:`jacobian` variable with the identity matrix, this way every layer is treated the same way: + weights dot current jacobian + transpose + broadcast the activation derivative + transpose back + repeat .. admonition:: Exercise (difficult) The goal is to implement the to following methods: .. literalinclude:: ../../../../../../src/ai/fnn/fnn_empty_2.py :pyobject: FNN.parameter_gradient :name: parameter_gradient :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn_empty_2.py :pyobject: FNN.fit :name: fit :linenos: :caption: src The first implements the back-propagation algorithm; the second the gradient descent algorithm. Do not bother to implement a stopping criteria in the gradient descent, use a fixed number of iterations. Do not bother to implement stochastic gradient descent either. Some helper methods may help to factorize and shorten the code: .. literalinclude:: ../../../../../../src/ai/fnn/fnn_empty_2.py :pyobject: FNN.init_parameters_gradient_zero :name: init_parameters_gradient_zero :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn_empty_2.py :pyobject: FNN.get_layer_activation_activation_derivative :name: get_layer_activation_activation_derivative :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn_empty_2.py :pyobject: FNN.get_left_a_or_input :name: get_left_a_or_input :linenos: :caption: src Finally, to adapt for regression or multi-class classification: .. literalinclude:: ../../../../../../src/ai/fnn/fnn_empty_2.py :pyobject: FNN.last_layer_dJdz :name: last_layer_dJdz :linenos: :caption: src .. collapse:: Hints 1 Start by drawing by hand every operation involved in the back-propagation clearly showing transpose, matrix multiplication and broadcast. The back-propagation goes from last layer to first layer. The trick is to propagate the successive :math:`\cfrac{\partial J}{\partial z}`. Treat the last layer separately to get the :math:`\cfrac{\partial J}{\partial z_j}` in :python:`last_layer_dJdz`; you can use the last layer activation to determine if this is a regression or a multi-class classification. For the multi-class classification case the target which one-hot encoded makes the :math:`\cfrac{\partial J}{\partial z_j}` easy to implement with an element-wise operation. To compute the mean gradient for every training example, a loop over this examples and some arrays and vectors to cumulate all the individual gradients are useful. .. collapse:: Hints 2 :math:`\cfrac{\partial J}{\partial z_j}` is an element-wise operation between 2 :python:`Vector` (that is the reason why the activations and activation derivatives were implemented vectorized). :math:`\cfrac{\partial J}{\partial w_{jk}}` is a broadcast between a vertical 1 column 2d array and a 1d vector :math:`a_k` in order to get the :math:`k` index along the column. The result is a :python:`Array2d`. .. collapse:: Hints 3 The :math:`\cfrac{\partial J}{\partial z_k}` operation is a matrix product between a matrix :math:`w_{jk} \cdot\sigma'(z_k)` and the vector :math:`\cfrac{\partial J}{\partial z_j}` which has just been calculated previously. The operation :math:`w_{jk} \cdot\sigma'(z_k)` is a simple broadcast. The operation :math:`\cfrac{\partial J}{\partial w_{kl}}` is similarly as previous hint, a broadcast between a vertical 1 column 2d array and a 1d vector :math:`a_l` in order to get the :math:`l` index along the column. The result is a :python:`Array2d`. .. _`ex:back-prop`: .. collapse:: Correction .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.init_parameters_gradient_zero :name: init_parameters_gradient_zero_corr :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.get_layer_activation_activation_derivative :name: get_layer_activation_activation_derivative_corr :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.get_left_a_or_input :name: get_left_a_or_input_corr :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.last_layer_dJdz :name: last_layer_dJdz_corr :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.parameter_gradient :name: parameter_gradient_corr :linenos: :caption: src .. literalinclude:: ../../../../../../src/ai/fnn/fnn.py :pyobject: FNN.fit :name: fit_corr :linenos: :caption: src