<commit_before>---
layout: post
title: "Xmas blog: Andrew Ng's missing notes on back-propagation"
date: 2017-12-25 08:00:00 -0400
author: <NAME>
categories: machine-learning deep-learning supervised-learning
javascript:
  katex: true
---

I used to work with machine learning techniques from Genetic Algorithms in my PhD to different flavor multivariate analysis techniques in high energy physics such Bayesian Neural Networks, Boosted Decision Tree, and Neuroevolution of Augmented Topologies (a combination or neural networks and genetic algorithms).

So, I was puzzled by the raise of *deep learning* in recent years. In particular when I realized most of the deep learning revolution was driven by supervised training of multilayered neural networks using old-school back-propagation algorithm. I do remembered reading in the 90's [Introduction to the theory of neural computation](https://www.amazon.com/Introduction-Theory-Neural-Computation-Institute/dp/0201515601) in where back-propagation is fully described to implement steepest descent already including momentum and adaptive learning rate.

This was the reason I decided was time to get some training on this and I took the very good [Andrew Ng's deep learning specialization at coursera](https://www.coursera.org/specializations/deep-learning). My goal was to understand exactly what change that made deep learning a new trend. From what I gather, it seems most of the recent revolution is driven by three main reasons:

* The huge amount computer power from new GPUs.
* The explosion of labeled data generated by technology.
* The availability of highly scalable algorithms for supervise algorithms.

It likely the popularity of the old steepest decent with back propagation is due mostly to the fact they can be easily vectorized making them a natural fit to implement them in GPUs.

Andrew Ng's courses is targeted for a large audience and therefore some part of the technical details are omitted. However, he does put emphasis in the need to know some calculus, and he introduces some basic concepts anytime he can. But when deriving the back propagation algorithm, he avoid its derivation and just draft basic heuristics to motivate the result.

In this post, I write down my notes in where I derive Andrew's version of back propagation using his own notation. I am assuming you are tacking the course, or otherwise you are familiar with the subject. This derivation is based on directly applying the chain rule that was mention by Andrew but omitted entirely in the first course of the specialization[^1]. Finally, the post is not having any programming examples, because there are planting of frameworks with efficient implementation of this algorithm[^2].

The next figure shows a deep neural network (multilayered neural network) using the Andrew's notation.

{% include image file="neural-networks.svg" %}

The activation value for the *j*-node in the *l*-layer when input the *i*-example in the training set \\| a^{\[l\](i)}_j \\| is computed using the following forward propagation algorithm:

<p>%%
\begin{aligned}
z^{[l](i)}_j &= \sum^{n^{[l-1]}}_{k=1} w^{[l]}_{jk} a^{[l-1](i)}_k + b^{[l]}_j \\
a^{[l](i)}_j &= g^{[l]}\left(z^{[l](i)}_j\right)
\end{aligned}
%%</p>

where \\|g^{\[l\]}(\cdot)\\| is the activation function in the *l*-layer. These equations can be written in using matrix and vector notation as

<p>%%
\begin{aligned}
Z^{[l]} &= W^{[l]} A^{[l-1]} + B^{[l]} \\
A^{[l]} &= g^{[l]}\left(Z^{[l]}\right)
\end{aligned}
%%</p>

If there are \\|L\\| layers and in each one there are \\|n^{\[l\]}\\| nodes, and your training set contains \\| m \\| examples, then the dimension of the previous matrices and vectors are:

<p>%%
\begin{aligned}
A^{[l]}, Z^{[l]} &\in \mathbb{R}^{\left(n^{[l]} \times m\right)} \\
W^{[l]} &\in \mathbb{R}^{\left(n^{[l]} \times n^{[l-1]}\right)} \\
B^{[l]} &\in \mathbb{R}^{\left(n^{[l]} \times m\right)}
\end{aligned}
%%</p>

Supervised learning goal is to minimize of the *cost* function \\|\mathcal{C}\\| define as the average of a *loss* function \\|\mathcal{L}\\| over the whole training set

<p>%%
\mathcal{C} = \frac{1}{m} \sum^m_{i=1} \mathcal{L}\left(A^{[L](i)},Y^{(i)}\right)
%%</p>

in where the loss function introduces the notion of how wrong is the activation value for the last layer relative to the labels of your training set \\|\{Y^{(i)}\}\\|. The detail of the loss function depends on the type of learning being done like logistic regression, softmax regression, or multitasking learning as a few examples. We do not need to assume any particular function form for the loss function to derive back-propagation algorithm.

The minimization of cost function is done using by updating neural network weights \\|\{W^{\[l\]}\}\\| and bias \\|\{B^{\[l\]}\}\\| using the steepest or gradient descent algorithm as follows

<p>%%
\begin{aligned}
W^{[l]} & = W^{[l]} - \alpha dW^{[l]} \\
B^{[l]} & = B^{[l]} - \alpha dB^{[l]} \\
\end{aligned}
%%</p>

in where \\| dW^{[l]} \\| and \\| dB^{[l]} \\| is Andrew's short notation for the gradient of the cost function relatively network weights and biases. More details will be given shortly.

The main tool to derive back-propagation equations is the chain rule in derivatives.  \\|f: \mathbb{R}^n \rightarrow \mathbb{R}\\| and \\|G: \mathbb{R}^m \rightarrow \mathbb{R}^n\\|

<p>%%
\frac{\partial}{\partial x_i} f(G(X)) = \sum^n_{i=1} \frac{\partial f}{\partial g_j}\Big\vert_{G(X)} \frac{\partial g_j}{\partial x_i}\Big\vert_{X}
%%</p>

<p>%%
\begin{aligned}
{\color{blue} da^{[l](i)}_j} = \frac{\partial \mathcal{\color{blue} L}}{\partial a^{[l](i)}_j} & = \sum^{n^{[l+1]}}_{j'=1} \frac{\partial \mathcal{L}}{\partial z^{[l+1](i)}_{j'}} \frac{\partial z^{[l+1](i)}_{j'}}{\partial a^{[l](i)}_j} \\  
&= \sum^{n^{[l+1]}}_{j'=1} dz^{[l+1](i)}_{j'} w^{[l+1]}_{j'j} \\
{\color{blue} dA^{[l]}} &= W^{[l+1]\top} {\color{blue} dZ^{[l+1]}}
\end{aligned}
%%</p>

<p>%%
\begin{aligned}
{\color{blue} dz^{[l](i)}_j} = \frac{\partial \color{blue}\mathcal{L}}{\partial z^{[l](i)}_j} &= \sum^{n^{[l]}}_{j'=1} \frac{\partial \mathcal{L}}{\partial a^{[l](i)}_{j'}} \frac{\partial a^{[l](i)}_{j'}}{\partial z^{[l](i)}_j} \\  
&= \sum^{n^{[l]}}_{j'=1} da^{[l](i)}_{j'} g^{[l]'}\left(z^{[l](i)}_j\right)\delta_{j'j} \\
{\color{blue} dZ^{[l]}} &= {\color{blue} dA^{[l]}} \odot g^{[l]'}\left(Z^{[l]}\right)
\end{aligned}
%%</p>

<p>%%
\begin{aligned}
{\color{red} dw^{[l]}_{jk}} = \frac{\partial \color{red}\mathcal{C}}{\partial w^{[l]}_{jk}} &= \sum^{m}_{i=1}\sum^{n^{[l]}}_{j'=1} \frac{\partial \mathcal{C}}{\partial z^{[l](i)}_{j'}} \frac{\partial z^{[l](i)}_{j'}}{\partial w^{[l]}_{jk}} \\  
&= \frac{1}{m} \sum^{m}_{i=1} {\color{blue} dz^{[l](i)}_{j}} a^{[l-1](i)}_{k} \\
{\color{red} dW^{[l]}} &= \frac{1}{m} {\color{blue} dZ^{[l]}} A^{[l-1]\top}
\end{aligned}
%%</p>

<p>%%
\begin{aligned}
{\color{red} db^{[l]}_{j}} = \frac{\partial \color{red}\mathcal{C}}{\partial b^{[l]}_{j}} &= \sum^{m}_{i=1}\sum^{n^{[l]}}_{j'=1} \frac{\partial \mathcal{C}}{\partial z^{[l](i)}_{j'}} \frac{\partial z^{[l](i)}_{j'}}{\partial b^{[l]}_{j}} \\  
&= \frac{1}{m} \sum^{m}_{i=1} {\color{blue} dz^{[l](i)}_{j}} \\
{\color{red} dB^{[l]}} &= \frac{1}{m} \sum^{m}_{i=1} \left({\color{blue} dZ^{[l]}}\right)_{ji}
\end{aligned}
%%</p>

<p>%%
\begin{aligned}
{\color{blue} dA^{[l]}} &= W^{[l+1]\top} {\color{blue} dZ^{[l+1]}} \\
{\color{blue} dZ^{[l]}} &= {\color{blue} dA^{[l]}} \odot g^{[l]'}\left(Z^{[l]}\right) \\
{\color{red} dW^{[l]}} &= \frac{1}{m} {\color{blue} dZ^{[l]}} A^{[l-1]\top} \\
{\color{red} dB^{[l]}} &= \frac{1}{m} \sum^{m}_{i=1} \left({\color{blue} dZ^{[l]}}\right)_{ji}
\end{aligned}
%%</p>

[^1]: [Neural Networks and Deep Learning](https://www.coursera.org/learn/neural-networks-deep-learning).

[^2]: Example are [tensorflow](https://www.tensorflow.org/) or [Matlab](https://www.mathworks.com/help/nnet/deep-learning-basics.html).<commit_msg>More drafting of xmas blog.<commit_after>---
layout: post
title: "Xmas blog: Andrew Ng's missing notes on back-propagation"
date: 2017-12-25 08:00:00 -0400
author: <NAME>
categories: machine-learning deep-learning supervised-learning
javascript:
  katex: true
---

I used to work with machine learning techniques from Genetic Algorithms in my PhD to different flavor multivariate analysis techniques in high energy physics such Bayesian Neural Networks, Boosted Decision Tree, and Neuroevolution of Augmented Topologies (a combination or neural networks and genetic algorithms).

So, I was puzzled by the raise of *deep learning* in recent years. In particular when I realized most of the deep learning revolution was driven by supervised training of multilayered neural networks using old-school back-propagation algorithm. I do remembered reading in the 90's [Introduction to the theory of neural computation](https://www.amazon.com/Introduction-Theory-Neural-Computation-Institute/dp/0201515601) in where back-propagation is fully described to implement steepest descent already including momentum and adaptive learning rate.

This was the reason I decided was time to get some training on this and I took the very good [Andrew Ng's deep learning specialization at coursera](https://www.coursera.org/specializations/deep-learning). My goal was to understand exactly what change that made deep learning a new trend. From what I gather, it seems most of the recent revolution is driven by three main reasons:

* The huge amount computer power from new GPUs.
* The explosion of labeled data generated by technology.
* The availability of highly scalable algorithms for supervise algorithms.

It likely the popularity of the old steepest decent with back propagation is due mostly to the fact they can be easily vectorized making them a natural fit to implement them in GPUs.

<NAME>'s courses is targeted for a large audience and therefore some part of the technical details are omitted. However, he does put emphasis in the need to know some calculus, and he introduces some basic concepts anytime he can. But when deriving the back propagation algorithm, he avoid its derivation and just draft basic heuristics to motivate the result.

In this post, I write down my notes in where I derive Andrew's version of back propagation using his own notation. I am assuming you are tacking the course, or otherwise you are familiar with the subject. This derivation is based on directly applying the chain rule that was mention by Andrew but omitted entirely in the first course of the specialization[^1]. Finally, the post is not having any programming examples, because there are planting of frameworks with efficient implementation of this algorithm[^2].

The next figure shows a deep neural network (multilayered neural network) using the Andrew's notation.

{% include image file="neural-networks.svg" %}

The activation value for the *j*-node in the *l*-layer when input the *i*-example in the training set \\| a^{\[l\](i)}_j \\| is computed using the following forward propagation algorithm:

<p>%%
\begin{aligned}
z^{[l](i)}_j &= \sum^{n^{[l-1]}}_{k=1} w^{[l]}_{jk} a^{[l-1](i)}_k + b^{[l]}_j \\
a^{[l](i)}_j &= g^{[l]}\left(z^{[l](i)}_j\right)
\end{aligned}
%%</p>

where \\|g^{\[l\]}(\cdot)\\| is the activation function in the *l*-layer. These equations can be written in using matrix and vector notation as

<p>%%
\begin{aligned}
Z^{[l]} &= W^{[l]} A^{[l-1]} + B^{[l]} \\
A^{[l]} &= g^{[l]}\left(Z^{[l]}\right)
\end{aligned}
%%</p>

If there are \\|L\\| layers and in each one there are \\|n^{\[l\]}\\| nodes, and your training set contains \\| m \\| examples, then the dimension of the previous matrices and vectors are:

<p>%%
\begin{aligned}
A^{[l]}, Z^{[l]} &\in \mathbb{R}^{\left(n^{[l]} \times m\right)} \\
W^{[l]} &\in \mathbb{R}^{\left(n^{[l]} \times n^{[l-1]}\right)} \\
B^{[l]} &\in \mathbb{R}^{\left(n^{[l]} \times m\right)}
\end{aligned}
%%</p>

Supervised learning goal is to minimize of the *cost* function \\|\mathcal{C}\\| define as the average of a *loss* function \\|\mathcal{L}\\| over the whole training set

<p>%%
\mathcal{C} = \frac{1}{m} \sum^m_{i=1} \mathcal{L}\left(A^{[L](i)},Y^{(i)}\right)
%%</p>

in where the loss function introduces the notion of how wrong is the activation value for the last layer relative to the labels of your training set \\|\{Y^{(i)}\}\\|. The detail of the loss function depends on the type of learning being done like logistic regression, softmax regression, or multitasking learning as a few examples[^3]. We do not need to assume any particular function form for the loss function to derive back-propagation algorithm.

The minimization of cost function is done using by updating neural network weights \\|\{W^{\[l\]}\}\\| and bias \\|\{B^{\[l\]}\}\\| using the steepest or gradient descent algorithm as follows

<p>%%
\begin{aligned}
W^{[l]} & = W^{[l]} - \alpha dW^{[l]} \\
B^{[l]} & = B^{[l]} - \alpha dB^{[l]}
\end{aligned}
%%</p>

in where \\| dW^{[l]} \\| and \\| dB^{[l]} \\| is Andrew's short notation for the gradient of the cost function relatively network weights and biases, more details of the notation will be given shortly.

The goal of the back-propagation algorithm is to compute the gradient of the cost function for an arbitrary deep neural network efficiently. The main tool to derive back-propagation equations is the chain rule of derivatives[^4]. The rule says that the derivative the composition of two functions \\|f: \mathbb{R}^n \rightarrow \mathbb{R}\\| and \\|G: \mathbb{R}^m \rightarrow \mathbb{R}^n\\| is given by the following expression:

<p>%%
\frac{\partial}{\partial x_i} f(G(X)) = \sum^n_{i=1} \frac{\partial f}{\partial g_j}\Big\vert_{G(X)} \frac{\partial g_j}{\partial x_i}\Big\vert_{X}
%%</p>

or in words, the derivative of the composition of two function can be written as the sum the derivatives of the individual functions that make the composition.

We now derived the expression for two very important auxiliaries gradients. The first one is the gradient of the loss function as a function of activation node activation:

<p>%%
\begin{aligned}
{\color{blue} da^{[l](i)}_j} = \frac{\partial \mathcal{\color{blue} L}}{\partial a^{[l](i)}_j} & = \sum^{n^{[l+1]}}_{j'=1} \frac{\partial \mathcal{L}}{\partial z^{[l+1](i)}_{j'}} \frac{\partial z^{[l+1](i)}_{j'}}{\partial a^{[l](i)}_j} \\  
&= \sum^{n^{[l+1]}}_{j'=1} dz^{[l+1](i)}_{j'} w^{[l+1]}_{j'j} \\
{\color{blue} dA^{[l]}} &= W^{[l+1]\top} {\color{blue} dZ^{[l+1]}}
\end{aligned}
%%</p>

in where I used the *blue* color to designate this gradient is of the loss function instead of the cost function. The second gradient is also of the loss function relative to the value of the nodes before applying the activation function:

<p>%%
\begin{aligned}
{\color{blue} dz^{[l](i)}_j} = \frac{\partial \color{blue}\mathcal{L}}{\partial z^{[l](i)}_j} &= \sum^{n^{[l]}}_{j'=1} \frac{\partial \mathcal{L}}{\partial a^{[l](i)}_{j'}} \frac{\partial a^{[l](i)}_{j'}}{\partial z^{[l](i)}_j} \\  
&= \sum^{n^{[l]}}_{j'=1} da^{[l](i)}_{j'} g^{[l]'}\left(z^{[l](i)}_j\right)\delta_{j'j} \\
{\color{blue} dZ^{[l]}} &= {\color{blue} dA^{[l]}} \odot g^{[l]'}\left(Z^{[l]}\right)
\end{aligned}
%%</p>

in where the notation \\|\odot\\| represent the element-wise or Hadamard product[^5].

<p>%%
\begin{aligned}
{\color{red} dw^{[l]}_{jk}} = \frac{\partial \color{red}\mathcal{C}}{\partial w^{[l]}_{jk}} &= \sum^{m}_{i=1}\sum^{n^{[l]}}_{j'=1} \frac{\partial \mathcal{C}}{\partial z^{[l](i)}_{j'}} \frac{\partial z^{[l](i)}_{j'}}{\partial w^{[l]}_{jk}} \\  
&= \frac{1}{m} \sum^{m}_{i=1} {\color{blue} dz^{[l](i)}_{j}} a^{[l-1](i)}_{k} \\
{\color{red} dW^{[l]}} &= \frac{1}{m} {\color{blue} dZ^{[l]}} A^{[l-1]\top}
\end{aligned}
%%</p>

<p>%%
\begin{aligned}
{\color{red} db^{[l]}_{j}} = \frac{\partial \color{red}\mathcal{C}}{\partial b^{[l]}_{j}} &= \sum^{m}_{i=1}\sum^{n^{[l]}}_{j'=1} \frac{\partial \mathcal{C}}{\partial z^{[l](i)}_{j'}} \frac{\partial z^{[l](i)}_{j'}}{\partial b^{[l]}_{j}} \\  
&= \frac{1}{m} \sum^{m}_{i=1} {\color{blue} dz^{[l](i)}_{j}} \\
{\color{red} dB^{[l]}} &= \frac{1}{m} \sum^{m}_{i=1} \left({\color{blue} dZ^{[l]}}\right)_{ji}
\end{aligned}
%%</p>

<p>%%
\begin{aligned}
{\color{blue} dA^{[l]}} &= W^{[l+1]\top} {\color{blue} dZ^{[l+1]}} \\
{\color{blue} dZ^{[l]}} &= {\color{blue} dA^{[l]}} \odot g^{[l]'}\left(Z^{[l]}\right) \\
{\color{red} dW^{[l]}} &= \frac{1}{m} {\color{blue} dZ^{[l]}} A^{[l-1]\top} \\
{\color{red} dB^{[l]}} &= \frac{1}{m} \sum^{m}_{i=1} \left({\color{blue} dZ^{[l]}}\right)_{ji}
\end{aligned}
%%</p>

[^1]: [Neural Networks and Deep Learning](https://www.coursera.org/learn/neural-networks-deep-learning).

[^2]: Example are [tensorflow](https://www.tensorflow.org/) or [Matlab](https://www.mathworks.com/help/nnet/deep-learning-basics.html).

[^3]: [Logistic regression](https://en.wikipedia.org/wiki/Logistic_regression), [Softmax regression](https://en.wikipedia.org/wiki/Softmax_function), and [Multi-task learning](https://en.wikipedia.org/wiki/Multi-task_learning).

[^4]: [Chain rule](https://en.wikipedia.org/wiki/Chain_rule)

[^5]: [Hadamard product](https://en.wikipedia.org/wiki/Hadamard_product_(matrices))
{'fraction_non_alphanumeric': 0.20348293595137915, 'fraction_numerical': 0.008882655446470314, 'mean_word_length': 4.765835579514825, 'pattern_counts': {'":': 0, '<': 50, '<?xml version=': 0, '>': 50, 'https://': 15, 'lorem ipsum': 0, 'www.': 10, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3230315', 'n_tokens_mistral': 5693, 'n_tokens_neox': 5456, 'n_words': 1920}