We saw in the last chapter how by evaluating $\partial C/\partial w_i$ and using them for gradient descent, we may be able to find the values of $w_i$'s for which $C$ is minimum. This will materialize our function and we can then use it to make predictions.

C2.1 It's Not That Easy Yet

As good as it may sound, we are still far from being able to use the constructs we have built so far for real predictions. The main problem is finding $\partial C/\partial w_i$. Though, still easier than solving $\partial C/\partial w_i=0$, it's still overwhelmingly difficult with our model that has a large number of coefficients woven into multi-layered composite functions, where each function is now not even linear anymore. There are three interesting phenomena, or call them tricks, that will get our job done.

All of these depend upon differentiation and the first two engage the chain rule of differentiation, and actually have intuitive explanations as well.

C2.2 Chain Rule of Differentiation - It's Magic!

First, a little bit on the chain rule itself. If there exists a function $g(x)$ such that $x$ appears in $g$ only in a particularly modified way, say as specified by $f(x)$, we write $g=g(f(x))$. In such cases, it can be easily shown that rate of change of $g$ w.r.t. $x$ = rate of change of $g$ w.r.t. f $\times$ rate of change of $f$ w.r.t. $x$. That is to say, $\frac{dg}{dx}=\frac{dg}{df}.\frac{df}{dx}$.

This makes sense, isn't it? For example, for a given value of $x$, $f$ might be changing very rapidly w.r.t. $x$, but if $g$ is changing very slowly w.r.t. $f$, we expect the rate of change of $g$ w.r.t. $x$ to be equal to the former suppressed by the latter.

Further if in $g$, it's not just $f$ that uses $x$, but a bunch of $f_1$, $f_2$, $f_3$ etc., then $\frac{dg}{dx}=\frac{\partial g}{\partial f_1}.\frac{\partial f_1}{\partial x}+\frac{\partial g}{\partial f_2}.\frac{\partial f_2}{\partial x}+$...

We'll have some interesting intuitional analogies coming later in this chapter.

The first relation above is called the Chain Rule of Differentiation, and the second one, Multivariate Chain Rule of Differentiation

Now, let's look into the three tricks we were talking about. But before that we need to acquaint ourselves with the formal conventional terminology used in neural networks.

C2.3 Machine Learning Formal Notation

We shall use the following vocabulary henceforth, which is mostly universally used for depicting machine learning formulae.

• The coefficients $a_i$'s are called the weights, denoted by $w_i$'s. These weights connect one artificial neuron to another.
• The learning rate - the proportionality constant with which we would change the weights (in order to minimize $C$) - is denoted by $\eta$.
• The different artificial neurons, call them nodes, are not all connected to each other, instead there are layers. The output from (activation of) all the nodes in one layer are fed into all the nodes of the next layer and so on, modified by the weight $w$. The $w$ connecting the $j$th node in $l-1$ layer to the $i$th node in the $l$ layer is denoted by $w_{ij}^l$.

• All the layers except the first and the last are called the hidden layers. First one is the input layer, and the last, output layer.
• All the indices are 1-based and not 0-based.
• Based on the above definitions, the input to the $i$th node in the layer $l$ is given by $z_i^l=\sum _j{w}_{ij}^l{a}_j^{l-1}$. That is, it is the sum of the terms obtained by multiplying the activation (output) of each node in its previous layer ($a_j^{l-1}$) multiplied by the weight connecting that node to the concerned node ($w_{ij}^l$).
• For determining the output of the $i$th node in layer $l$ ($a_j^l$), we add the inherent factor (the bias $b$) to the input $z_i$, and pass it to the activation function, also known as the transfer function. As explained in the last chapter, $\frac{1}{1+e^{-}z}$ is a common choice for an activation function, and it is denoted by σ(z). We will use σ for activation function in our analysis henceforth just to keep ourselves reminded about the non-linearity of the function (but note that there could be any such function in its place). $$a_j^l=\sigma \left(z_j^l\right)=\sigma (\sum _k{w}_{jk}^l{a}_k^{l-1}+b_j^l)$$This output is then passed on to all the nodes in the next layer modified by different weights, and so on.
• Finally, to make things easier to read, we bring in matrix notation^↕ which enables us the drop the subscripts $i$, $j$, $k$. Thus the activation equation becomes:
  $$\begin{array}{r}{a}^l=\sigma (w^l{a}^{l-1}+b^l)\end{array}$$
• The activations of the last (output) layer are simply the predicted results $\hat{y}$, and those are used to generate $C$, the cost function. Thus, $$C=C(\hat{y})=C(w,b)$$The above means that we want to be looking at both $\partial C/\partial w_i$ and $\partial C/\partial b_i$.
  But the $b$'s can be easily included into the $w$'s by using a little algebraic trick - by writing $b_i^l=w_{0i}^l$ which means the summation starts from 0 instead of 1. Then, we have $z_i^l=\sum _j{w}_{ij}^l{a}_j^{l-1}$. Let's call this $z_i^l$ the total input at node $i$ in layer $l$. And this allows to conveniently write $C=C(w)$, and just be focused on $\partial C/\partial w_i$.

C2.4 What are We Trying to Do?

Our goal is to find the $w_i$'s for which $C$ is minimum. And for that, we have to find $\partial C/\partial w_i$ iteratively. First we will find the values of these partial derivatives at random values of $w_i$'s, and then using the values of the derivatives we will modify values of $w_i$'s slightly as per the formula: $$w_i\to w_i^{new}=w_i-\eta \frac{\partial C}{\partial w_i}$$

There are both theoretical and practical difficulties. First, let's see how we can tackle the former using differentiation rules. Later, we'll see how things like stochastic gradient descent can help us overcome the practical difficulties.

C2.5 The First Use of Differentiation in finding $\partial C/\partial w$

Consider this zoomed-in portion of a neural network. $a$ is the output of node $M$ that gets multiplied by the weight $w$ and goes into a function $z$. Here we have shown the node N using two circles in the middle - having $z$ and $\sigma$. The last circle having $C$ is not a node of the neural network. Remember:

$$z_i^l=\sum _j{w}_{ij}^l{a}_j^{l-1}$$

In our zoomed-in picture, we are looking at just one layer and $z$ at only one node, so we can ignore the superscript $l$ and the subscript $i$ for time being and simply write $z=\sum _j{w}_j{a}_j$ where $a_j$ is understood to be the $j$^th activation of the previous layer. One of these $w_j$'s and $a_i$'s are the $w$ and $a$ shown above. It is important to note that this $z$ shown above is the only function that uses this $w$. Then, this $z$ is fed into another function $\sigma (z)$, which is the output of node $N$. This output is eventually used by the $C$ function (there may be many layers between $N$ and $C$).

Applying the chain rule of differentiation:$$\begin{array}{rl}\frac{\partial C}{\partial w}& =\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial w}\\ & =\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}.\frac{\partial z}{\partial w}\end{array}$$
$\frac{\partial z}{\partial w}$ is simply $a$ (look the definition of $z$ above). Hence:

$$\begin{array}{}\text{(1)}& \frac{\partial C}{\partial w}& =\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}.a\end{array}$$

This is our first Mentos moment! The sensitivity of $C$ w.r.t. any $w$ is directly proportional to the output of the node ($a$) this $w$ is coming from. Although $C$ uses $w$ through so many intermediary functions and combinations, this basic relationship holds true.

This is actually something quite intuitive to us and we apply it in our everyday lives. Click the button below for exploring an analogy.

C2.6 The Second Use of Differentiation in finding $\partial C/\partial w$

Let's continue. In the equation $\frac{\partial C}{\partial w}=a.\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}$, how do we look at the last two factors on the right hand side?
$\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}$ is actually $\frac{\partial C}{\partial z}$. So, we can say that this is basically how $C$ changes w.r.t. the total input $z$ at the node $w$ is connecting to. So, summarily, if we name the two nodes on the left and right of $w$ as in and out nodes respectively:

$$\begin{array}{rl}& \text{Rate of change of }C\text{ w.r.t. any }w\\ & =\text{Output of the }\mathit{\text{in}}\text{ node}\\ & \times \text{Rate of change of }C\text{ w.r.t. total input at the }\mathit{\text{out}}\text{ node}\end{array}$$

Let's look at the second factor again - $\frac{\partial C}{\partial z}=\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}$. This is actually used heavily in further analysis, and has been given its own identity - error at the out node ($a_{out}$), denoted as $\delta$.
Now, $\sigma$ is simply the output of the out node $N$ above, $\partial C/\partial \sigma$ is nothing but $\frac{\partial C}{\partial a_{out}}$.
Also, $\frac{\partial \sigma }{\partial z}$ can be written as ${\sigma }^{\prime }(z)$, i.e. the differential of $\sigma$ at $z_{out}$.
Thus, we have:$$\begin{array}{rl}\delta & =\text{Rate of change of }C\text{ w.r.t. total input at the }\mathit{\text{out}}\text{ node}\\ & =\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}\\ & =\frac{\partial C}{\partial a_{out}}.{\sigma }^{\prime }(z_{out})\end{array}$$

Also,$$\begin{array}{rl}\frac{\partial C}{\partial w}=& \text{Rate of change of }C\text{ w.r.t. any }w\\ =& a_{in}.\frac{\partial C}{\partial \sigma }.\frac{\partial \sigma }{\partial z}\\ \text{(1a)}& =& \boxed{{\displaystyle a_{in}.{\delta }_{out}}}=& a_{in}.\frac{\partial C}{\partial a_{out}}.{\sigma }^{\prime }(z_{out})\end{array}$$

Thus,
$$\boxed{{\displaystyle \begin{array}{rl}& \text{Rate of change of }C\text{ w.r.t. any }w\\ & =\text{Output of the }\mathit{\text{in}}\text{ node}\\ & \times \text{Rate of change of }C\text{ w.r.t. output of the }\mathit{\text{out}}\text{ node}\\ & \times \text{how rapidly }\sigma \text{ is changing at the }\mathit{\text{out}}\text{ node}\end{array}}}$$

The first and the last term of the three factors above are easily found out when we have the training data. Let's see what we can do for the middle term: $$\frac{\partial C}{\partial a_{out}}=\text{Rate of change of }C\text{ w.r.t. output of the }\mathit{\text{out}}\text{ node}$$
Let's look at the zoomed-in picture again with slightly more detail. Once again the smaller circles having $z$'s are actually part of the nodes shown just after them.

The output from the out node ($N$) - $a_N$ or $a_{out}$, shown as $o$ in the figure for the sake of clarity - is fed to multiple nodes and is actually used by the activation formulae of all the nodes in the layer $l+1$. Thus, $a_{out}$ is seen by C exclusively through all the ${\sigma }_i$'s (in the layer $l+1$) as shown in the figure. This realization allows us to summon the multivariate chain rule of differentiation:$$\begin{array}{rl}\frac{\partial C}{\partial a_{out}}& =\frac{\partial C}{\partial {\sigma }_1^{l+1}}\frac{\partial {\sigma }_1^{l+1}}{\partial a_{out}}+\frac{\partial C}{\partial {\sigma }_2^{l+1}}\frac{\partial {\sigma }_2^{l+1}}{\partial a_{out}}+\cdots \\ & =\frac{\partial C}{\partial {\sigma }_1^{l+1}}\frac{\partial {\sigma }_1^{l+1}}{\partial a_{out}}+\frac{\partial C}{\partial {\sigma }_2^{l+1}}\frac{\partial {\sigma }_2^{l+1}}{\partial a_{out}}+\cdots \\ & =\frac{\partial C}{\partial {\sigma }_1^{l+1}}\frac{\partial {\sigma }_1^{l+1}}{\partial z_1}\frac{\partial z_1}{\partial a_{out}}+\frac{\partial C}{\partial {\sigma }_2^{l+1}}\frac{\partial {\sigma }_2^{l+1}}{\partial z_2}\frac{\partial z_2}{\partial a_{out}}+\cdots \\ & =(\frac{\partial C}{\partial a_1^{l+1}}{\sigma }_1^{\prime }(z_1))\frac{\partial z_1}{\partial a_{out}}+(\frac{\partial C}{\partial a_2^{l+1}}{\sigma }_2^{\prime }(z_2))\frac{\partial z_2}{\partial a_{out}}+\cdots \text{(just changed symbols)}\end{array}$$

This RHS of this equation is bubbling with insights. If you look at the definition of $\delta$ above, the terms in the parentheses are nothing else but $\delta$ at the corresponding nodes. And terms like $\frac{\partial z_1}{\partial a_{out}}$ are nothing else but $w_1^{l+1}$ etc. Using these two substitutions, we get:
$$\frac{\partial C}{\partial a_{out}}={\delta }_1^{l+1}.w_1^{l+1}+{\delta }_2^{l+1}.w_2^{l+1}+\cdots$$

Substituting this value of $\frac{\partial C}{\partial a_{out}}$ into the definition of $\delta$: $$\begin{array}{rl}{\delta }_{out}& =\frac{\partial C}{\partial a_{out}}.{\sigma }^{\prime }(z_{out})\\ & =({\delta }_1^{l+1}.w_1^{l+1}+{\delta }_2^{l+1}.w_2^{l+1}+\cdots ).{\sigma }^{\prime }(z_{out})\\ \text{(2)}& \text{Or, }{\delta }_i^l& =({\delta }_1^{l+1}.w_{1i}^{l+1}+{\delta }_2^{l+1}.w_{2i}^{l+1}+\cdots ).{\sigma }^{\prime }(z_i^l)\boxed{{\displaystyle \phantom{{\delta }_i^l=({\delta }_1^{l+1}.w_{1i}^{l+1}+{\delta }_2^{l+1}.w_{2i}^{l+1}+\cdots ).{\sigma }^{\prime }(z_i^l)}}}\end{array}$$

This is our second Mentos moment! This gives us a way to find ${\delta }_i^l$ if we know all the ${\delta }_j^{l+1}$'s: The error ($\delta$) at any node is the weighted sum of the errors in the nodes in the next layer multiplied by how fast $\sigma$ is changing at the given node. Thus, if can somehow find the values of $\delta$s in the last node, we can start moving back and keep on finding the $\delta$ for the inner nodes, and thus $\frac{\partial C}{\partial w}=a_{in}.{\delta }_{out}$ for any $w$.

This is aptly called backpropagation of errors, and is quite symmetrical to the forward propagation that normally happens in a neural network. In the latter we calculate the output of the nodes in a layer by virtue of knowing the output of the nodes in the previous layer. In the former (backpropagation), we find the errors in the nodes of the a layer by virtue of knowing the errors of the nodes of the next layer. Note that in both, we look at only the weights connected to the node in question.

Using matrix notation^↕, we can drop the index $i$, and can write Eqn. $(2)$ succinctly for all the nodes in layer $l$: $$\begin{array}{}\text{(2a)}& {\delta }^l=((w^{l+1}{)}^T{\delta }^{l+1})\odot {\sigma }^{\prime }(z^l)\end{array}$$

C2.7 The Third Use of Differentiation in finding $\partial C/\partial w$

We are close to be able to find $\partial C/\partial w$. The last thing remaining is to find the starting point of the backpropagation of errors. For this, we will have to go to the last layer - the output layer. From the definition of $\delta$, we have for any node, $\delta =\frac{\partial C}{\partial a}.{\sigma }^{\prime }(z)$, which, for any node $j$ in the last layer $L$ becomes ${\delta }_j^L=\frac{\partial C}{\partial a_j^L}.{\sigma }^{\prime }(z_j^L)$.

The formulae we have derived so far are completely general and they do not depend upon particular choices of specific functions (except for having general restrictions such as regarding smoothness, differentiability etc.). Now, in order to refine our formulae further, for the first time we need to bring in specific cost function. Our ideas still maintain their general nature, but now we are stepping into the arena of providing practical solutions. Ok, so the most common choice for cost function is the quadratic one, given by $C=\frac{1}{2}\sum _j(y_j-{\hat{y}}_j{)}^2=\frac{1}{2}\sum _j(y_j-a_j^L{)}^2$. This means that $\partial C/\partial a_j^L=(y_j-a_j^L)$. With $\partial C/\partial a_j^L$ known, we can find ${\delta }_j^L$, and hence for all the $\delta$'s in the last layer, we have:

$$\begin{array}{}\text{(3)}& {\delta }^L={\mathrm{\nabla }}_{a}C\odot {\sigma }^{\prime }(z^L)\end{array}$$

This is the third Mentos moment! Now we have everything to kick-start our calculations. We start with finding ${\delta }^L$, i.e. the errors in the last-layer-nodes. For that we need $a^L$ which we calculate using random values of $w$'s. We also need to decide on activation functions which can be different for different layers (or even nodes). Then we move backward finding $\delta$'s using eqn. $(2)$. And finally, we use these $\delta$'s to find $\partial C/\partial w$ using eqn. $(1a)$ (calculating other $a^l$ meanwhile).

This completes backpropagation. We then start forward-propagation using gradient descent. We use the values of $\partial C/\partial w$ in finding new values of $w$'s using the eqn. in the section C2.4 What are We Trying to Do?^↕ With the new values of $w$'s, we eventually find new values of $a_j^L$'s which equips us to start backpropagation again!

C2.8 Summary - Chapter 2

We have learnt the mathematical notation and laid the theoretical foundation for materializing neural network. In particular, we have found out a way for applying gradient descent in a multilayered neural network and adjusting the weights so that can think about predicting now.

But not so fast! We need to look at some practical problems and their solutions such as stochastic gradient descent, and vanishing or exploding gradients. This we will do in the next chapter.