# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Demystifying Neural Network
#
# ### Training Neural Network - Backpropagation
# - Intro : complexity in computation
# - what is backpropatagion? What's the goal?
# - How to calculate backpropagation
#     - feed forward
#     - error calculation
#     - backward propagation
# - code implementation of back propagation

# I thought that the topic of backpropagation deserves a whole chapter since I struggled to fully understand the concept. You know one of those concepts that you just think about it, it seems like it makes sense.But then once you actually sit down and try to write it out or even implement it via code, you just get stuck. This was one of those concepts for me.
#
# I found a great source to understand backpropagation by [<NAME>](https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/). If you want more detailed expalanation with additional information, please visit his website. In this chapter, I am going to use his example described in his guide to calculate myself backpropagation, and end with code implementation of backpropagation. 

# ____________________

# ### Intro : complexity in computation

# I describe briefly last time how weights are updated via gradient descent. However, I didn't delve into how those gradients are calculated. I mean, we know that we would take slope of the cost function, and how much $w$ wiggles, as we wiggle a cost function. But what if there are million or even trillion wieghts? (which is said to be a common case in deep networks) Since any nueron in one layer can be connected to any neuron in the next layer, wouldn't computation grow exponentially?
#
# Thanks to backpropagation (will be explained shortly), computation is not going to blow up exponentially. This is because weights and biases close to input layer that influence cost function can only influence the cost function only by going through layers that are close to the right side of the network. If you look at the figure below, $w_1$, $w_2$, $w_3$, $w_4$ can only influene the cost function only by going through $h_1$ and $h_2$.
#
# That said, a lot of computations that we need to do in one column of neurons has already been computed in the column on the right. Therefore, computation is not going to grow exponentially. Professor Winston during one of his neural net lecture said "what's computed is computed and need not be recomputed" (I really enjoy his random but intellectual jokes during his lectures). 
#
# - amount of computation:
#     1. depth: if we increase the number of layers (depth), the amount of computation will increase **linearly**.
#     2. width: any neuron in one column can be connected to any neuron in the next column. The amount of computation is proportional to the number of connections: $w^2$

# ____________________

# ### what is backpropagation? What's the goal?

# Backpropagation is a method for training a neural network by minimizing a cost function. The name comes from the fact that it uses 'can't-stop-won't-stop" chain rule to 'propagate' an error computed at the output (commonly referred to as top layers as we are 'backpropagating') to distribute backwards all the way down to bottom layers. Backpropagation computes the contribution of each parameter (weights and biases) had in the loss value by calculating derivatives (gradients). 
#
# We can think of backpropagation as defining the gradient descent algorithm. We are repeatedly changing positions of weights to find a minimum of the cost function. This enables a neural network to optimize its weights so that the network can learn how to correctly map inputs to outputs. 

# ____________________

# ### How backpropagation is calculated?
#
# Now, let's go through few steps of backpropagation. I've read about backpropagation enough, but in most cases, one learns most not by staring at an arbitrary chain rule formula but by writing it out and calculating it by oneself. So I'm going to do that now.

# <img src="img/blog2_figure1.png" width="450" height="150" />

# ____________________

# #### Feed Forward
# Note that at the neurons $h_i$, $w_i$ and $b_i$ are summed with input values. And at the neurons $a_i$ and $z_i$, the values calculated at $h_i$ go through a sigmoid activation function $$a(h) = \sigma(h) = \frac{1}{1+e^{-h}}$$
# *Forgive me for some rounding errors. I just wanted to write them all out rather than typing precise numbers.*
#
# Thus, at $h_1 = w_1 * x_1 + b_1$ which is, $0.15 * 0.05 + 0.2 * 0.1 + 0.35 * 1 = 0.3775$
#
# Using $h_1$ as the input, $a_1 = \frac{1}{1+e^{-0.3775}} = 0.5932$
#
# Going through the same process above, we can also get the value of $a_2 = 0.5968$
#
# Using above calculated values as inputs, we also calculate the values for $h_3$, $h_4$, $z_1$, $z_2$.
#
# $$h_3 = w_5 * a_1 + w_6 * a_2 + b_2$$ 
# which is, 
# $$0.4 * 0.5932 + 0.45 * 0.5968 + 0.6 * 1 = 1.1059$$
#
# Then, this value also goes through a sigmoid activation function and outputs $z_1$.
# $$z_1 = \frac{1}{1+e^{-1.1059}} = 0.7514$$
#
# Going through the same process above, we get the value of $z_2 = 0.7729$
#

# ____________________

# #### Error calculation

# Using mean squared error function that I introduced in part1, we can calculate the total error of our neural network.
#
# $$E_{total} = \sum \dfrac{1}{2}(predicted_{z_1} - true_{z_1})^2$$
# $$\dfrac{1}{2}(predicted_{z_1} - true_{z_1})^2 = \dfrac{1}{2}(0.7514 - 0.01)^2 = 0.2748$$
#
# Repeating the above process with $z_2$ also, then we get the error of $0.0236$
#
# $$E_{total} = 0.2748 + 0.0236 = 0.2984$$

# ____________________

# #### Backpropagation calculation
# *Note that I wrote the equation starting from the output layer and ending at the bottom layer*
# ##### top layer
# - Let's first consider how $w_5$ contributes to the loss value above.
# - $E_{total}$ refers to the sum of errors generated at the output neurons
#
# By chain rule,
# $$\dfrac{\partial E_{total}}{\partial w_5} = \dfrac{\partial E_{total}}{\partial z_1} * \dfrac{\partial z_1}{\partial h_3} * \dfrac{\partial h_3}{\partial w_5}$$
#
# Let's break down above equation into 3 when calculating.
#
# - Let's look at the first term : $\dfrac{\partial E_{total}}{\partial w_5}$
#
# $$E_{total} = \dfrac{1}{2}(predicted_{z_1} - desired_{z_1})^2 + \dfrac{1}{2}(predicted_{z_2} - desired_{z_2})^2$$
#
# $$\dfrac{\partial E_{total}}{\partial z_1} = \dfrac{\partial E_{total}}{\partial } = 2 * \dfrac{1}{2}(predicted_{z_1} - desired_{z_1})^{2-1} * -1 + 0$$
#
# $$\dfrac{\partial E_{total}}{\partial z_1} = -(predicted_{z_1} - desired_{z_1}) = -(0.01 - 0.7513) = 0.7414$$
#
# - Now let's calculate the second term: $\dfrac{\partial z_1}{\partial h_3}$  
# Since $z_1 = \frac{1}{1+e^{h_3}}$, its derivative is $\dfrac{\partial z_1}{\partial h_3} = z_1 (1-z_1) = 0.7514 (1-0.7514) = 0.1868$   
# - Then the last term: $\dfrac{\partial h_3}{\partial w_5}$   
# $h_3 = w_5 * a_1 + w_6 * a_2 + b_2$   
# $\dfrac{\partial h_3}{\partial w_5} = 1 * a_1 + 0 + 0 = a_1 = 0.5933$  

# - Finally, we multiply all the calculated derivatives above to get $\dfrac{\partial E_{total}}{\partial w_5}$  
# $\dfrac{\partial E_{total}}{\partial w_5} = \dfrac{\partial E_{total}}{\partial z_1} * \dfrac{\partial z_1}{\partial h_3} * \dfrac{\partial h_3}{\partial w_5} = 0.7414 * 0.1868 * 0.5932 = 0.0822$  
#
# This derivative is subtracted from the current weight of $w_5$ to decrease the error. Let's set a learning rate $\eta$ to 0.5.
# $w_5^+ = w_5 - \eta * \dfrac{\partial E_{total}}{\partial w_5} = 0.4 - 0.5 * 0.0822 = 0.3589$  
#
# Our weight $w_5$ is updated!   
#
# This process can also be repeated for $w_5, w_6, w_7, w_8$.

# #### bottom layer
# - Now for the bottom layer. Above was a lengthy process. However, rest assured. Most of the calculations will be reused.
# - Let's consider $w_1$
#
# <img src="img/blog2_figure2.png" width="450" height="150" />
#
# $$\dfrac{\partial E_{total}}{\partial w_1} = \dfrac{\partial E_{total}}{\partial a_1} * \dfrac{\partial a_1}{\partial h_1} * \dfrac{\partial h_1}{\partial w_1}$$
#
# $\dfrac{\partial E_{total}}{\partial a_1}$ can be expanded to $\dfrac{\partial E_{z_1}}{\partial a_1} + \dfrac{\partial E_{z_2}}{\partial a_1}$
#
# Through the figure above, we can see that $w_1$ can only influence the cost function only by going through the top layer. This will be reflected on the chain rule.  
# We can reuse the the value of $\dfrac{\partial E_{z_1}}{\partial h_3}$ that we calculated above.  
# $$\dfrac{\partial E_{z_1}}{\partial h_3} = \dfrac{\partial E_{total}}{\partial z_1} * \dfrac{\partial z_1}{\partial h_3} = 0.7414 * 0.1868 = 0.1385$$ 
# $\dfrac{\partial h_3}{\partial a_1}$ is equal to $w_5$ as $h_3 = w_5 * a_1 + w_6 * a_2 + b_2$ 
#
# Thus,
# $$\dfrac{\partial h_3}{\partial a_1} = w_5 * 1 + w_6 * 0 + 0 = w_5 = 0.40$$
#
# Plugging in the above calculated values,  
# $$\dfrac{\partial E_{z_1}}{\partial a_1} = \dfrac{\partial E_{z_1}}{\partial h_3} * \dfrac{\partial E_{h_3}}{\partial a_1} = 0.1385 * 0.40 = 0.0554$$
#
# Repeating the above process to get $\dfrac{\partial E_{z_2}}{\partial a_1}$, we can get the value of $-0.1905$  
# Therefore, 
# $$\dfrac{\partial E_{total}}{\partial h_1} = \dfrac{\partial E_{z_1}}{\partial a_1} + \dfrac{\partial E_{z_2}}{\partial a_1} = 0.0554 - 0.1905 = 0.0364$$  
# Now we have to calculate $\dfrac{\partial E_{a_1}}{\partial h_1}$ and $\dfrac{\partial E_{h_1}}{\partial w_1}$. We are almost there!  
# $$a_1 = {\partial w_1} = \frac{1}{1+e^{-h_1}}$$
# $$\dfrac{\partial a_1}{\partial h_1} = a_1 (1- a_1) = 0.5933 (1 - 0.5933) = 0.2413$$   
# For $\dfrac{\partial E_{h_1}}{\partial w_1}$, since $h_1 = w_1 * x_1 + w_2 * x_2 + b_1$  
# $\dfrac{\partial E_{h_1}}{\partial w_1} = x_1 = 0.05$  
#
# Plugging in everything we calculated to the formula: $\dfrac{\partial E_{total}}{\partial w_1} = \dfrac{\partial E_{total}}{\partial a_1} * \dfrac{\partial a_1}{\partial h_1} * \dfrac{\partial h_1}{\partial w_1}$  
# $$\dfrac{\partial E_{total}}{\partial w_1} = 0.0364 * 0.2413 * 0.05 = 0.000439$$
# With this value, we can now update $w_1$ as below:  
# $$w_1^+ = w_1 - \eta * \dfrac{\partial E_{total}}{\partial w_1} = 0.15 - 0.5 * 0.000439 = 0.1498$$
#
# This can be repeated for $w_2, w_3, w_4$ also.

# ### Let's conclude with backpropagation implementation code
# - <NAME>'s book is a great source to learn neural network code implementation.

# +
import random
import numpy as np

class NeuralNetwork(object):
    """the list sizes include the number of neurons from the input layer to the output layer
    If the argument is given as [3, 3, 2] this means that the number of input neurons is 3, 
    that of hidden layer neurons is 3 and that of output neurons is 2."""
    def __init__(self, sizes):
        
        self.n_layers = len(sizes)
        self.sizes = sizes
        self.biases = [np.random.randn(y,1) for y in sizes[1:]]
        self.weights = [np.random.randn(y,x) for (x,y) in zip(sizes[1:], sizes[1:])]
    
    def feedforward(self, a):
        for b, w in zip(self.biases, self.weights):
            a = sigmoid(np.dot(w,a)+b)
        return a
    
    def sigmoid(self, z):
        return 1.0 /(1.0+np.exp(-z))
    
    def sigmoidPrime(self, z):
        return sigmoid(z) * (1.0-sigmoid(z))
    
    def costPrime(self, output_activations, y):
        return (output_activations - y)
    
    def backpropagation(self, x, y):
        
        d_b = [np.zeros(b.shape) for b in self.biases]
        d_w = [np.zeros(w.shape) for w in self.weights]
        
        #forward pass
        activation = x
        activations = [x]
        zs = []
        for b, w in zip(self.biases, self.weights):
            z = np.dot(w, activation)+b
            zs.append(z)
            activation = sigmoid(z)
            activations.append(activation)
        
        #backward pass
        d_C = self.costPrime(activations[-1], y) * sigmoidPrime(zs[-1])
        d_b[-1] = d_C
        d_w[-1] = np.dot(d_C, activation[-2].transpose())
        
        for layer in range(2, self.num_layers):
            z = zs[-1]
            sg_prime = sigmoidPrime(z)
            delta = np.dot(self.weights[-layer+1].transpose(), delta) * sg_prime
            d_b[-layer] = d_C
            d_w[-layer] = np.dot(d_C, activations[-layer-1].transpose())
        return (d_b, d_w)

StarcoderdataJupyterScriptsDedupFiltered