<jupyter_start><jupyter_text>BackpropagationThis document will explain the code I used to attempt to implement the backpropagation machine learning algorithm as well as an attempt to explain my understainding of it. Later on once I have more experience I will reflect on this. What is it?Backpropagation is an algorithm that is used in neural networks to learn. It is a form of supervised learning where the user gives it training examples with features and a desired output. The machine can try to predict the output then it will use a mutivariable function in order to calculate the error of each weight and bias. It does this for each training example then it tries to find the minimum of this function (essentially finding out what weights and biases correspond to the lowest error) by using gradient descent. The algorithm starts at the last layer then it goes back one layer at a time to the last layer which is why its called backpropagation.  The Datasetthe dataset I used was a simple one which is a XOR gate. It has two inputs and each can either be one or a zero. The output will be zero if both inputs are zeros or ones.|Input|Output||-----|------||0, 0 |   0  ||0, 1 |   1  ||1, 0 |   1  ||1, 1 |   0  |This dataset is small which means that during testing I dont have to wait long periods of time just to see how well the program did.  The Neural NetworkThe architecture of the neural network was simple, but I wanted my program to be able to use any size of neural network. In this example I used one with an input layer, one hidden layer, and the output layer which has only one output.![Alt Text](https://raw.githubusercontent.com/Christian-Zwinkels-CAS/Machine-Learning-Attempt/master/Supervised_Learning/Backpropagation/xor_2-Copy.png)W1 and W2 are sets of weights represented as matricies: $$ W^{(1)} = \begin{bmatrix}w_{1} &w_{2}\\ w_{3} &w_{4} \end{bmatrix} $$$$ W^{(2)} = \begin{bmatrix}w_{5} &w_{6}\end{bmatrix} $$ How it predictsThe neural network is given a trainig exaple say 0, 0 to get the hidden layers. Lets see for example how it calculates the value at h1: $$ x1 * w_{1} + x2 * w_{2} + b^{(1)} $$Where b is a real number called the bias which is in each perceptron.We can calculate the value of x1 and x2 simultaneously by using matrices: $$ \begin{bmatrix}h1\\ h2\end{bmatrix} = \sigma \left ( \begin{bmatrix}w_{1} &w_{2}\\ w_{3} &w_{4} \end{bmatrix}\begin{bmatrix}x1\\ x2\end{bmatrix} + \begin{bmatrix} b^{(1)} \\ b^{(2)} \end{bmatrix}\right ) $$And for the final output layer: $$ y = \sigma \left ( \begin{bmatrix}w5\\ w6\end{bmatrix}\begin{bmatrix}h1\\ h2\end{bmatrix} + b^{(y)}\right) $$$ \sigma $ is the activation function which in this case is the sigmoid funciton. The activation function takes an input and turns it into a value between zero and one. $$ \sigma (x) = \frac{1}{1+e^{-x}} $$Initially the weights are random values and the biases are zeros, but after training these values would have changed. This whole process is called the forward pass. How it learnsBackpropagation uses a technique called gradient descent where it tries to find the minimum of a function that takes all the parameters in order to calculate the error called the cost function. The cost functionFirstly the machine needs to know how wrong it was, and to do that an error function is defined. Let $ x^{(i)} $ be the ith training example, $ y^{(i)} $ be the training examples's desired output, and $ \hat{y}^{(i)} $ be the machine's prediction. We define the error of that training example to be the squared error: $$ C(x^{(i)}) = (\hat{y}^{(i)} -  y^{(i)})^{2}$$We want to know how well it did over all the training examples so we take the average squared error for each training example letting $ m $ equal the number of training examples letting $ W $ be the set of all the weights: $$ C(W) = \frac{1}{m}\sum_{i=1}^{m}(\hat{y}^{(i)}-y^{(i)})^{2} $$ Gradient descentWe can not plot the cost function due to it being a multivariable function with the number of inputs being the number of weights and biases, but I will show a more simplified example in order to give an intuition of whats going on. I will later link a video that shows a really nice animation and explanation to what is going on.A simple cost funtion with just one parameter is a parabola:![Cost function simple graph placeholder](Screenshot_1.png)We start at a random value of $ w $ and the goal is to minimize the cost so we need to tell the computer to change $ w $ in a way that it will get closer to the minimum point of the graph. The negative of the derivative of the graph corresponds to lowering the value of the cost funtion so we take the derivative of the cost function with respect to $ w $ If we have two parameters the simplified version of the cost funtion will be a paraboloid so instead of taking a derivative we have to take a partial derivative for every weight.To compute this derivative we have to use the chain rule. This is where I will let the video do the explaining as it really hepls having animations and writing all the process will make this document really long. (https://www.youtube.com/watch?v=tIeHLnjs5U8)[![IMAGE ALT TEXT HERE](http://img.youtube.com/vi/tIeHLnjs5U8/0.jpg)](http://www.youtube.com/watch?v=tIeHLnjs5U8)This process repeates itself for the amount of iterations specified.  CodeI used python due to its simple syntax and popularity meaning that there are a lot of resources to help me. The only module I used was NumPy. I wanted to make this as from scratch as possible.First I imported Numpy:<jupyter_code>import numpy as np<jupyter_output><empty_output><jupyter_text>Then I defined the activation function and its derivative:<jupyter_code>def sigmoid(x):
    return 1/(1 + np.exp(-x))

def d_sigmoid(x):
    return sigmoid(x) * (1 - sigmoid(x))<jupyter_output><empty_output><jupyter_text>Made the dataset (XOR gate truth table):<jupyter_code>data_in = np.array([[0, 0],
                    [0, 1],
                    [1, 0],
                    [1, 1]])

data_out = np.array([0, 1, 1, 0])<jupyter_output><empty_output><jupyter_text>Initialized the architechture of the weights making sure to use loops so I can change the architecture easily. The weights started out as random values from the normal distribution and the biases as zeros:<jupyter_code>layer_sizes = (2, 2, 1)
weight_sizes = [(y, x) for y, x in zip(layer_sizes[1:], layer_sizes[:-1])]
weights = [np.random.standard_normal(s) for s in weight_sizes]
biases = [np.zeros((s, 1)) for s in layer_sizes[1:]]<jupyter_output><empty_output><jupyter_text>In this notebook the code will be a bit different from now on as I want it to be organized a bit better, I make a function to fowardpropagate a sample which stores all the layers in a list of numpy arrays which it then returns:<jupyter_code>def feedforward(X):
    a = X.reshape((layer_sizes[0], 1))  # Turns it into a column matrix
    z = a
    layers = []
    for w, b in zip(weights, biases):
        z = np.dot(w, z) + b
        layers.append(z)
    layers_sigmoid = [sigmoid(i) for i in layers]
    layers_sigmoid.insert(0, a)  # Adds the activation layers to the begging
    return layers, layers_sigmoid<jupyter_output><empty_output><jupyter_text>For the backpropagation I will explain each step of the process separately and then put it into a function.First I assign variables to use the returned values frow the feed forward step of a random trainig example:<jupyter_code>ri = np.random.randint(len(data_in))
layers, layers_sigmoid = feedforward(data_in[ri])<jupyter_output><empty_output><jupyter_text>I calculate the error $ \hat{y}^{(ri)} - y^{(ri)} $ of each output layer and put it in a column matrix (in this case it only has one element):<jupyter_code>cost_matrix = layers_sigmoid[-1] - data_out[ri]<jupyter_output><empty_output><jupyter_text>I calculate $ \delta^{L} $ or the error of the last layer output errors into a matrix which in this case will only have one element. I calculate this by multiplying $ \frac{\partial C}{\partial a^{L}} = 2(\hat{y}^{(i)}-y^{(i)}) $ (a matrix of the partial derivative of the cost function with respect to the final layer outputs) and $ \frac{\partial a^{L}}{\partial z^{L}} = \sigma '(z^{L}) $ where $ z^{L} $ is the last layer predictions without the activation function applied and $ a^{L} $ is with the activation function applied. In the end: $$ \delta^{L} = \frac{\partial C}{\partial a^{L}} \frac{\partial a^{L}}{\partial z^{L}} $$<jupyter_code>delC_dela = 2 * cost_matrix  
dela_delz = d_sigmoid(layers[-1])
delta_L = delC_dela * dela_delz
print(delta_L)<jupyter_output>[[-0.22331546]]<jupyter_text>Having $ \delta^{L} $ means that I can calculate $ \delta $ for each layer also known as $ \delta^{l} $. I made a list that had numpy arrays with each one being the values of $ \delta $ with the same size as the corresponding layer weight matrix so that later on I can apply the changes to the weights all at the same time. The formula used to calculate this is: $$ \delta^{l} = \left (\left (w^{l+1}\right)^{T}\delta^{l+1}\right ) \odot \sigma'\left (z^{l} \right ) $$Where $ w^{l+1} $ and $ \delta^{l+1} $ refer to the next layer weights (transposed) and deltas. The $ \odot $ is called the Hadamard product and a simple explanation of it would be:$$ \begin{bmatrix}2 \\3 \end{bmatrix} \odot \begin{bmatrix}4 \\5\end{bmatrix} = \begin{bmatrix}2*4 \\3*5\end{bmatrix} $$It is not a common operation but numpy has a good implimentation of it.\I also needed to make sure that using the loop that I used the iterated variable (i, its l in the original code but I cahnged it here because I would confuse l with 1 sometimes) would never reach zero otherwise it will mess up everything. In this case it should return a 2x1 and a 1x1 matrix inside the list and the last entry of that list should be delta_L.<jupyter_code>delta_l = []
delta_l.append(delta_L)  # Adds the last layer deltas

for i in range(1, len(layer_sizes) - 1):
    d = -i - 1
    if d == 0:
        break

    g = np.dot(weights[-i].T, delta_l[0]) * d_sigmoid(layers[-i - 1])
    delta_l.insert(0, g)
print(delta_l)<jupyter_output>[array([[-0.03535966],
       [ 0.03116512]]), array([[-0.22331546]])]<jupyter_text>As you can see it does just that. Each matrix of weights is ordered so that the row contains all the weights connected to a perceptron. Now I need to calculate $ \frac{\partial{z}}{\partial{w}} $ which are just equal to the previous layers (the one where teh weights stem from). I made a list of numpy arrays with each element being $ \frac{\partial{z}}{\partial{w}} $ for that weight.<jupyter_code>delz_delw = []
for i in range(1, len(layer_sizes)):
    r = layers_sigmoid[-i - 1].T * np.ones((weight_sizes[-i]))
    delz_delw.insert(0, r)<jupyter_output><empty_output><jupyter_text>Remember that the goal was to calculate $ \frac{\partial{C}}{\partial{w}} $ which is $ \frac{\partial C}{\partial a} \frac{\partial a}{\partial z} \frac{\partial{z}}{\partial{w}} $ and if you recall $ \delta = \frac{\partial C}{\partial a} \frac{\partial a}{\partial z} $ then $ \frac{\partial{C}}{\partial{w}} = \frac{\partial{z}}{\partial{w}} \delta $ which is what I calculated.<jupyter_code>delC_delw = [np.zeros(w) for w in weight_sizes]
for i in range(len(delta_l)):
    delC_delw[i] = delta_l[i] * delz_delw[i]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10411515365595196, 'fraction_numerical': 0.013511126810314376, 'mean_word_length': 4.3218984962406015, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 43, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, '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}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '278716', 'license': 'MIT', 'n_tokens_mistral': 3468, 'n_tokens_neox': 3335, 'n_words': 1538, 'path': 'Supervised_Learning/Backpropagation/Backpropagation.ipynb', 'repo_name': 'Christian-Zwinkels-CAS/Machine-Learning-Attempt', 'size': '11324'}