lectures/neuralNetworks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "49fcd9b9",
   "metadata": {},
   "source": [
    "# Neural Networks\n",
    "\n",
    "A Neural Network is an artificial system capable of learning to perform inormation processing tasks. The system is modeled on biological systems consisting of a (large) number of interconnected *Neurons*.\n",
    "Examples of Applications of Neural Networks are:\n",
    " - Image recognition\n",
    " - Language processing (f.ex ChatGPT)\n",
    " - Data processing\n",
    " - Game playing\n",
    " - Handwriting recognition\n",
    " \n",
    " In the following we are going to use recognition of handwritten digits as an example.\n",
    " \n",
    " ![neuralHandigits](neuralHandigits.png)\n",
    " \n",
    " The aim is to create a network to recognize handwritten digits as the example above.\n",
    " In the process we will learn about the basics of Neural Networks, how to implement a network and also\n",
    " using python libraries to create and use Neural Networks.\n",
    " \n",
    " The text and code below closely follows the book by Michael Nielsen \n",
    " \n",
    " ![book](http://neuralnetworksanddeeplearning.com/index.html\n",
    " \n",
    " The code, training and test data for the book is found on Github\n",
    " \n",
    "     `git clone https://github.com/mnielsen/neural-networks-and-deep-learning.git`\n",
    "     \n",
    " The code was originaly written in Python2.7 but has been updated to Python3 by Michal Daniel Dobrzanski\n",
    " and is downloaded by\n",
    " \n",
    "      git clonehttps://github.com/MichalDanielDobrzanski/DeepLearningPython35)\n",
    " \n",
    " \n",
    " ## Perceptrons\n",
    " A perceptron is a computational element capable of taking a number of input values\n",
    " \n",
    " ![neuralPerceptron](neuralPerceptron.png)\n",
    " \n",
    " and calculating an output value. The output value is either 0 or 1. The output is computed\n",
    " by the simple mathematical model\n",
    " \n",
    " \\begin{eqnarray}\n",
    "   output = \n",
    "   \\left\\{\n",
    "  \\begin{array}{cc}\n",
    "    0 & \\mbox{if}\\,\\, \\sum_j^N x_j w_j \\le threshold \\\\\n",
    "    1 & \\mbox{if}\\,\\, \\sum_j^N x_j w_j  > threshold\n",
    "   \\end{array}\n",
    "   \\right. .\n",
    "  \\end{eqnarray}\n",
    "  \n",
    "  The weights $w_j$ reflects the importance of the input value relative to the output.\n",
    "  $N$ is the total number of inputs. Each input is a single number.\n",
    "  \n",
    "  This simple device is capable of making simple decisisons. For example decide wether all inputs  are equal to the value of 1 given that the possible input values are 0 or 1. If all weights are set to one and the threshold set to 3 the output will be equal to 1 if all three inputs are equal to 1, but zero in all other cases. \n",
    "  \n",
    "If one of the inputs are considered to be more important than the others, f.ex. imagine the conditions for a passenger plane to take of is that there is enough fuel, all passengers have boraded and the weather is good.\n",
    "If fuel is considered the most important condition, this can be weighted by 3 and the threshold could be set to 5. The other inputs are weighted by 1. In this case the plane will never leave unless there is enough fuel.\n",
    "If the threshold is set to 4, then the plane might leave even if the weather is bad or there are no passengers. \n",
    "Obviously this is a rather crude decisison making device, but it can make some decisisons. The thinking is now\n",
    "if we connect together a number of perceptrons in a network, there might be some chance that more complex (and presumably better) decisisons might be taken. \n",
    "\n",
    "![neuralPerceptronNet](neuralPerceptronNet.png)\n",
    "\n",
    "The network shown above consists of columns of perceptrons and connections between them. (There is still only one output, but connected to different other perceptrons). Each column is called a layer. The outputs from one\n",
    "layer is connected to the inputs of another layer.\n",
    "It is also customary to add an extra layer for the input values.\n",
    "\n",
    "The notation used for each perceptron is usually made a bit simpler by using\n",
    "\n",
    "\\begin{eqnarray}\n",
    "   output = \n",
    "   \\left\\{\n",
    "  \\begin{array}{cc}\n",
    "    0 & \\mbox{if}\\,\\,  w \\cdot x +b \\le 0\\\\\n",
    "    1 & \\mbox{if}\\,\\, w \\cdot x +b >  0\n",
    "   \\end{array}\n",
    "   \\right. .\n",
    "  \\end{eqnarray}\n",
    "  where we have used the vector $w=(w_0,\\cdots,w_{n-1})$ and $x=(x_0,\\cdots,w_{n-1})$ for weights and input values. $b$ is now equal to $-threshold$. $n$ would be the number of inputs and weights.\n",
    "  \n",
    "  \n",
    "## Sigmoid neurons  \n",
    "It can be shown that networks of perceptrons is capable of performing any kind of computation.\n",
    "In that respect the perceptron networks are the same as the computers we already have. In order to get beyond this model the network is modified to be capable of learning.\n",
    "\n",
    "To introduce learning experience shows that there is one property the perceptrone is lacking.\n",
    "![neuralSmallchange](neuralSmallchange.png)\n",
    "\n",
    "We need to have a node in the network to be sensitive to small changes, such that a small change in the input or the weights\n",
    "creates a small change in the output. A perceptrone is not capable of this since a small change in the input weights might flip the output from 0 to 1, or vice versa.\n",
    "\n",
    "To accomodate this the Sigmoid neuron is introduced in place of a perceptron.\n",
    "\n",
    "![neuralSigmoid](neuralSigmoid.png)\n",
    "\n",
    "The Sigmoid neuron is pictured in the same way as a perceptrone except that the inputs can now vary continously between 0 and 1, the weights are also real numbers and the output is a real number between 0 and 1.\n",
    "To this end we use the Sigmoid function\n",
    "\n",
    "\\begin{eqnarray}\n",
    "  \\sigma(z) = \\frac{1}{1+\\exp(-z)}.\n",
    "\\end{eqnarray}\n",
    "  \n",
    "For a neuron this becomes\n",
    "\\begin{eqnarray}\n",
    "  \\sigma(z) = \\frac{1}{1+\\exp(-w\\cdot x -b)}.\n",
    "\\end{eqnarray}\n",
    "\n",
    "The Sigmoid function approches 1 when $w\\cdot x +b $ is positively large, and approaches zero when $w\\cdot x +b$ is large and negative. Comparing the Sigmoid function with the step function, which is the output from a perceptrone, we see that the Sigmoid function is a smoothed step function.\n",
    "\n",
    "![neuralStep](neuralStep.png)\n",
    "\n",
    "The Sigmoid function is called the *Activation* function for the neuron. Other activation functions are possible, but here we stay with the Sigmoid function. Because the activation function is smooth and differentiable we have\n",
    "\n",
    "\\begin{eqnarray}\n",
    "  \\Delta output \\approx \\sum_{j=0}^n \\frac{\\partial output}{\\partial w_j} + \\frac{\\partial output}{\\partial b}\n",
    "\\end{eqnarray}\n",
    "\n",
    "which means that a small change in the weights creates a small change in the output.\n",
    "\n",
    "# Neural network architecture\n",
    "\n",
    "![neuralNet](neuralNet.png)\n",
    "\n",
    "The leftmost layer in the network shown above is the input layer and represent the data input. The rightmost layer is called the output layer and contains the neuron creating the actual output. The layer in the middle is a \n",
    "so called hidden layer.\n",
    "\n",
    "![neuralNet2](neuralNet2.png)\n",
    "\n",
    "It is possible to have several hidden layers, as in the network above.\n",
    "The way a network works is by accepting some kind of data at the input layer and the output layer\n",
    "delivering some kind of result.\n",
    "An example is a network designed to recognize a handwritten digit. An image of the handwriting is used as an input. Assume the image contains 64 by 64 pixels = 4096 pixels. This would be the data contained in the\n",
    "input layer. The output will contain a single number with a value of less than 0.5 signaling that the input\n",
    "is not a 1 digit, and a value larger than 0.5 signaling that the input is a 1 digit.\n",
    "\n",
    "The general architecture of the network shown above is that the data flows from the left to the right.\n",
    "One hidden layer gets inputs from the previous layer. There is no data flowing backwards from a layer to the right to another layer. This kind of networks are called *feed-forward* networks.\n",
    "\n",
    "# A network for recognizing handwritten digits\n",
    "\n",
    "Our aim now is to construct a network which is capable of recognizing a single handwritten digit,\n",
    "\n",
    "![neuralDigit](neuralDigit.png)\n",
    "\n",
    "like the 5 digit shown above. To do this we will use the network shown below\n",
    "\n",
    "\n",
    "![neuralDigitnet](neuralDigitnet.png)\n",
    "\n",
    "The input layer consist of 784 pixels derived from an image consisting of 28 by 28 pixels. The input data\n",
    "is grayscale with values from 0 to 1.\n",
    "The second layer is the hidden layer and consist of 15 neurons. We will not consider this a fixed number but vary with deifferent values, so we assume the number of hidden layers is a variable named $n$.\n",
    "The output layer consists of 10 neurons, one for each digit from 0 to 9. To decide what digit the input is we will\n",
    "select the neuron with the largest output value.\n",
    "This is all there is to this network, the next task is to find out how we can teach the network to recognize handwritten digits.\n",
    "\n",
    "# Network learning\n",
    "\n",
    "The main task is now to figure out how we can make the network described above learn the task of handwritten digit \n",
    "recognition. The main idea is to collect together a large number of handwritten digits and then adjust the weights and biases of each neuron to recognize each digit in the way we have described. This is in principle an optimization problem. If we denote the input as the vector $x$ where the components consists of the\n",
    "input pixels and the output as a vector $y(x)$ where the components consists of the output layer, we can \n",
    "define a simple cost function\n",
    "\n",
    "\\begin{eqnarray}\n",
    "  C(w,b) = \\sum_{x}\\lVert y(x) - a \\rVert\n",
    "\\end{eqnarray}\n",
    "\n",
    "and minimize $C(w,b)$ with respect to the weights and biases. $a$ is here the desired output.\n",
    "The sum is over all training inputs.\n",
    "In our case, with a small number of neurons, this can be accomplished with a global search algorithm, f.ex Simulated Annealing. \n",
    "However, if the number of neurons is very large, this will take too much time and a simpler algorithm, like steepest decscent og conjugate gradient search would be better and take less time.\n",
    "\n",
    "# Training dataset\n",
    "\n",
    "Before looking at how to do the optimization we need a training data set. We will use the *MNIST* dataset containig a large number of scanned handwritten digits\n",
    "\n",
    "![neuralMNIST](neuralMNIST.png)\n",
    "\n",
    "The scanned dataset consists of 60000 images of handwritten digits from 250 different people. The images are grayscale and sampled with 28 by 28 pixels, each pixel contain a real number between 0 and 1.\n",
    "In addition to the training data there are also 10000 images to be used for testing the network.\n",
    "In the following we will regard each image as a vector $x$ containing 748 components. This is the input\n",
    "to the network. The desired output, $y(x)$ will be a vector with 10 components\n",
    "\n",
    "\\begin{eqnarray}\n",
    "y = (0,0,0,0,0,0,1,0,0,0)\n",
    "\\end{eqnarray}\n",
    "\n",
    "Here component no 7 is one, signaling that the network recognized the digit 7.\n",
    "\n",
    "\n",
    "# Stochastic steepest desecent\n",
    "\n",
    "We will use the very simple steepest descent algorithm for optimizing the weights and biases.\n",
    "The unknowns in our problem are the weights $w_k$ and the biases $b_l$. In component notation the steepest\n",
    "descent algorithm is trying to find a minimum of the cost function $C$ by updating the unknowns as\n",
    "\n",
    "\\begin{eqnarray}\n",
    "  w'_k = w_k -\\frac{\\eta}{m}\\sum_{x_j}\\frac{C_{x_j}}{\\partial w_k}  \\nonumber\\\\\n",
    "  b'_l = b_l -\\frac{\\eta}{m}\\sum_{x_j}\\frac{C_{x_j}}{\\partial b_l}  \n",
    "\\end{eqnarray}\n",
    "$\\eta$ is the step length.\n",
    "Here we do not include all of the input datasets $x_j$ in the summation, only a limited\n",
    "number selected randomly. We then average the gradient over this subset. The idea is to minimize \n",
    "the cost of computing the gradient, and if we select a representative subset of the input data set, the\n",
    "gradient will hopefully be correct to the degree that the minimization is actually working.\n",
    "This approach is called stochastic steepest descent.\n",
    "\n",
    "![neuralGradient](neuralGradient.png)\n",
    "\n",
    "\n",
    "# Computation of the gradient\n",
    "\n",
    "The most challenging part of this project is the actual computation of the gradient of\n",
    "the cost function. We will use the automatic-derivative backward, or as it is sometimes called,\n",
    "backpropagation method.\n",
    "\n",
    "First a clear (but a bit cumbersome) notation for the weights, biases and activation functions must be defined.\n",
    "\n",
    "By $w^l_{jk}$ we mean the weight from neuron no $k$ in layer no $l-1$ to neuron no $j$ in layer no $l$.\n",
    "\n",
    "\n",
    "![neuralNotation](neuralNotation.png)\n",
    "\n",
    "For the biases we use $b^l_j$ for neuron no $j$ in layer no $l$. The activation functions are denoted\n",
    "by the same notation, $a^l_j$.\n",
    "The activation function in layer no $l$ now becomes \n",
    "\n",
    "\\begin{eqnarray}\n",
    "a^l_j = \\sigma\\left(\\sum_k w^l_{jk} a^{l-1}_k + b^l_j\\right)\n",
    "\\end{eqnarray}\n",
    "\n",
    "We se that $w^l_{jk}$ can be regarded as the elements of a matrix with indices $jk$, and $a^l_k$ as\n",
    "a vector with components denoted by the $k$ index. The sum above over $k$ is then the matrix product\n",
    "of the matrix $w^l$ with the vector $a^l$. The above equation can then be written\n",
    "\n",
    "\\begin{eqnarray}\n",
    "a^l = \\sigma\\left(w^l a^l + b^l\\right)\n",
    "\\end{eqnarray}\n",
    "\n",
    "We will also use the notation \n",
    "\n",
    "\\begin{eqnarray}\n",
    "z^l = w^l a^l + b^l\n",
    "\\end{eqnarray}\n",
    "\n",
    "So that we have\n",
    "\n",
    "\\begin{eqnarray}\n",
    "a^l = \\sigma(z^l)\n",
    "\\end{eqnarray}\n",
    "\n",
    "We will also need the *Hadamard* product, or more conventionaly the *schur* product of two vectors which is the element wise product as in\n",
    "\n",
    "\\begin{eqnarray}\n",
    "a\\odot b = a_i b_i\n",
    "\\end{eqnarray}\n",
    "\n",
    "Using this notation the cost function $C$ is now\n",
    "\n",
    "\\begin{eqnarray}\n",
    "C = \\frac{1}{2}\\lVert y(x)-a^L(x)\\lVert^2\n",
    "\\end{eqnarray}\n",
    "\n",
    "Here $y(x)$ is th desired output and $a^L(x)$ is the activation output with input x where\n",
    "$L$ denotes the number of layers in the network. \n",
    "\n",
    "Finaly we will need the derivatives of the cost function. At the moment we will consider only\n",
    "derivatives with respect to $z^l$, bacuse this is the quantity which is most conveniently related\n",
    "to the backpropagation method. Considering derivatives in terms of biases and weights is also possible, but is \n",
    "more naturally connected to the forward method.\n",
    "\n",
    "We define then the so called sensistivity or error as\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\delta^l_j = \\frac{\\partial C}{\\partial z^l_j}\n",
    "\\end{eqnarray}\n",
    "\n",
    "The error in the output layer can now be written in this notation as\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\delta^L_j = \\frac{\\partial C}{\\partial a^L_j} \\sigma'(z^L_j)\n",
    "\\end{eqnarray}\n",
    "where the prime denotes differentiation.\n",
    "If we are using the $L_2$ norm we can compute the above equation as\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\frac{1}{2}\\frac{\\partial (y_j - a^L_j)^2 }{\\partial a^L_j} = (a^L_j-y_j)\n",
    "\\end{eqnarray}\n",
    "\n",
    "Using our new notation we then have\n",
    "\\begin{eqnarray}\n",
    "\\delta^L = (a^L-y)\\odot\\sigma'(z^L)\n",
    "\\end{eqnarray}\n",
    "\n",
    "\n",
    "\n",
    "This will be the first step in the computation of the gradient. We will use the automatic differentiation\n",
    "backward method to compute all necessary derivatives using the chain rule.\n",
    "\n",
    "The next step will be to compute the derivative of layer no $l-1$ in terms of the derivatives in layer\n",
    "no $l$.\n",
    "\n",
    "The derivative in layer no $l$ is equal to\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\delta^l_j = \\frac{\\partial C}{\\partial z^l_j}\n",
    "\\end{eqnarray}\n",
    "\n",
    "Now we use the chain rule as we did in the lectures on automatic differentiation\n",
    "and write\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\delta^l_j = \\sum_k \\frac{\\partial C}{\\partial z^{l+1}_k}\\frac{\\partial z^{l+1}_k}{\\partial z^l_j},\n",
    "\\end{eqnarray}\n",
    "\n",
    "since $z^l$ in principle depends on all components in the next layer.\n",
    "\n",
    "Which by definition is now\n",
    "\\begin{eqnarray}\n",
    "\\delta^l_j = \\sum_k \\delta^{l+1}_k\\frac{\\partial z^{l+1}_k}{\\partial z^l_j}\n",
    "\\end{eqnarray}\n",
    "\n",
    "To compute the z derivatives we use the definition of z\n",
    "\n",
    "\\begin{eqnarray}\n",
    "z^{l+1}_k = \\sum_j w^{l+1}_{kj}a^{l+1}_j+b^{l+1}_k = \\sum_j w^{l+1}_{kj} \\sigma^l_j(z^l_j) + b^{l+1}_k\n",
    "\\end{eqnarray}\n",
    "\n",
    "So evaluating the derivative we have \n",
    "\n",
    "\\begin{eqnarray}\n",
    "  \\frac{\\partial z^{l+1}_k}{\\partial z^l_j} =  w^{l+1}_{kj} {\\sigma'}^l_j(z^l_j)\n",
    "\\end{eqnarray}\n",
    "\n",
    "Inserting in the equation for the error above we have\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\delta^l_j = \\sum_k\\delta^{l+1}_k w^{l+1}_{kj} {\\sigma'}^l_j(z^l_j)\n",
    "\\end{eqnarray}\n",
    "\n",
    "In matrix notation this is the same as\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\delta^l = \\left(w^{l+1})\\right)^T \\delta^{l+1} \\odot {\\sigma'}^l(z^l)\n",
    "\\end{eqnarray}\n",
    "\n",
    "We will eventualy also need the derivatives of the bias at each neuron with respect to the cost function.\n",
    "\n",
    "Again we use the definition of z\n",
    "\n",
    "\\begin{eqnarray}\n",
    "z^l_j = \\sum_k w^l_{jk}a^{l-1}_k + b^l_j\n",
    "\\end{eqnarray}\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\frac{\\partial C}{\\partial b^l_j} & = & \\frac{\\partial C}{\\partial z^l_j}\\frac{\\partial z^l_j}{\\partial b^l_j}\\nonumber\\\\      \n",
    "                                  & = & \\delta^l_j \n",
    "\\end{eqnarray}\n",
    "                                  \n",
    "We also will need the derivative of the cost function with respect to weights\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\frac{\\partial C}{\\partial w^l_{jk}} & = & \\frac{\\partial C}{\\partial z^l_j}\n",
    "                                          \\frac{\\partial z^l_j}{\\partial w^l_{kj}} \\nonumber\\\\\n",
    "                                     & = &  \\delta^l_j a^{l-1}_k \n",
    "\\end{eqnarray}\n",
    "                           \n",
    "                         \n",
    "Summarizing we now have all necessary equations to compute the gradient:\n",
    "\n",
    " 1. $\\delta^L = (a^L-y)\\odot\\sigma'(z^L)$\n",
    " 2. $\\delta^l = \\left(w^{l+1}\\right)^T \\delta^{l+1} \\odot {\\sigma'}^l(z^l)$\n",
    " 3. $\\frac{\\partial C}{\\partial b^l_j} = \\delta^l_j$\n",
    " 4. $\\frac{\\partial C}{\\partial w^l_{jk}} = \\delta^l_j a^{l-1}_k$\n",
    " \n",
    " \n",
    " # Python implementation of network\n",
    " \n",
    "     class Network(object):\n",
    "\n",
    "       def __init__(self, sizes): \n",
    "        self.num_layers = len(sizes)\n",
    "        self.sizes = sizes\n",
    "        self.biases = [np.random.randn(y, 1) for y in sizes[1:]]\n",
    "        self.weights = [np.random.randn(y, x)\n",
    "                        for x, y in zip(sizes[:-1], sizes[1:])]\n",
    "                        \n",
    " The `sizes`is a python list which contains the number of neurons in each layer. To use the Network class we\n",
    " can f.ex write\n",
    "        \n",
    "        net = Network([3,15,10]) \n",
    "        \n",
    " which creates an object with 3 neurons in the first layer, 15 neurons in the second layer and 10 neurons \n",
    " in the third layer. The `biases`is a list of numpy arrays where each list item is a vector. `biases[0]`\n",
    " contains a numpy vector holding all the biases for the first layer.\n",
    " `weights[0]` contains a numpy matrix containg the weights connecting the first and second layer.\n",
    " The weights and biases are initialized with random numbers.\n",
    " \n",
    " The Sigmoid function are defined by a small function\n",
    " \n",
    "     def sigmoid(z):\n",
    "    \"\"\"The sigmoid function.\"\"\"\n",
    "    return 1.0/(1.0+np.exp(-z))\n",
    "    \n",
    " The action of the network is implemented as\n",
    " \n",
    "     def feedforward(self, a):\n",
    "        \"\"\"Return the output of the network if ``a`` is input.\"\"\"\n",
    "        for b, w in zip(self.biases, self.weights):\n",
    "            a = sigmoid(np.dot(w, a)+b)\n",
    "        return a\n",
    " \n",
    " The most complicated routine is the stochastic gradient search routine, which in addition\n",
    " to computing weights and biases using the training data also runs a test using the test data set.\n",
    " \n",
    "    def SGD(self, training_data, epochs, mini_batch_size, eta,\n",
    "            test_data=None):\n",
    "        \n",
    "        training_data = list(training_data)\n",
    "        n = len(training_data)\n",
    "\n",
    "        if test_data:\n",
    "            test_data = list(test_data)\n",
    "            n_test = len(test_data)\n",
    "\n",
    "        for j in range(epochs):\n",
    "            random.shuffle(training_data)\n",
    "            mini_batches = [\n",
    "                training_data[k:k+mini_batch_size]\n",
    "                for k in range(0, n, mini_batch_size)]\n",
    "            for mini_batch in mini_batches:\n",
    "                self.update_mini_batch(mini_batch, eta)\n",
    "            if test_data:\n",
    "                print(\"Epoch {} : {} / {}\".format(j,self.evaluate(test_data),n_test))\n",
    "            else:\n",
    "                print(\"Epoch {} complete\".format(j))\n",
    "                \n",
    "  The `training_data` are lists of pairs of input and desired output data. `epochs`are the maximum\n",
    "  number of iterations performed and the `mini_batch_size`is size of each subdata set used in the gradient\n",
    "  computation. `eta`is the step length, or as it is called here, the learning rate.\n",
    "  \n",
    "  The `update_mini_batch` routine is doing the actual steepest descent search and are updating\n",
    "  the weights and biases. However, the actual gradient computation is hidden in the \n",
    "  `backprop` function.\n",
    "  \n",
    "        def update_mini_batch(self, mini_batch, eta):\n",
    "            \"\"\"Update the network's weights and biases by applying\n",
    "            gradient descent using backpropagation to a single mini batch.\n",
    "            The ``mini_batch`` is a list of tuples ``(x, y)``, and ``eta``\n",
    "            is the learning rate.\"\"\"\n",
    "            nabla_b = [np.zeros(b.shape) for b in self.biases]\n",
    "            nabla_w = [np.zeros(w.shape) for w in self.weights]\n",
    "            for x, y in mini_batch:\n",
    "                delta_nabla_b, delta_nabla_w = self.backprop(x, y)\n",
    "                nabla_b = [nb+dnb for nb, dnb in zip(nabla_b, delta_nabla_b)]\n",
    "                nabla_w = [nw+dnw for nw, dnw in zip(nabla_w, delta_nabla_w)]\n",
    "            self.weights = [w-(eta/len(mini_batch))*nw\n",
    "                        for w, nw in zip(self.weights, nabla_w)]\n",
    "            self.biases = [b-(eta/len(mini_batch))*nb\n",
    "                       for b, nb in zip(self.biases, nabla_b)]\n",
    "                       \n",
    "   The backpropagation routine is a straightforward implementation of the algorithm we \n",
    "   have described. Except for some differences in numbering the implementation below follows\n",
    "   the computations we outlined for the gradient.\n",
    "                       \n",
    "       def backprop(self, x, y):\n",
    "        \"\"\"Return a tuple ``(nabla_b, nabla_w)`` representing the\n",
    "        gradient for the cost function C_x.  ``nabla_b`` and\n",
    "        ``nabla_w`` are layer-by-layer lists of numpy arrays, similar\n",
    "        to ``self.biases`` and ``self.weights``.\"\"\"\n",
    "        nabla_b = [np.zeros(b.shape) for b in self.biases]\n",
    "        nabla_w = [np.zeros(w.shape) for w in self.weights]\n",
    "        # feedforward\n",
    "        activation = x\n",
    "        activations = [x] # list to store all the activations, layer by layer\n",
    "        zs = [] # list to store all the z vectors, layer by layer\n",
    "        for b, w in zip(self.biases, self.weights):\n",
    "            z = np.dot(w, activation)+b\n",
    "            zs.append(z)\n",
    "            activation = sigmoid(z)\n",
    "            activations.append(activation)\n",
    "        # backward pass\n",
    "        delta = self.cost_derivative(activations[-1], y) * \\\n",
    "            sigmoid_prime(zs[-1])\n",
    "        nabla_b[-1] = delta\n",
    "        nabla_w[-1] = np.dot(delta, activations[-2].transpose())\n",
    "        # Note that the variable l in the loop below is used a little\n",
    "        # differently to the notation in Chapter 2 of the book.  Here,\n",
    "        # l = 1 means the last layer of neurons, l = 2 is the\n",
    "        # second-last layer, and so on.  It's a renumbering of the\n",
    "        # scheme in the book, used here to take advantage of the fact\n",
    "        # that Python can use negative indices in lists.\n",
    "        for l in range(2, self.num_layers):\n",
    "            z = zs[-l]\n",
    "            sp = sigmoid_prime(z)\n",
    "            delta = np.dot(self.weights[-l+1].transpose(), delta) * sp\n",
    "            nabla_b[-l] = delta\n",
    "            nabla_w[-l] = np.dot(delta, activations[-l-1].transpose())\n",
    "        return (nabla_b, nabla_w)\n",
    "\n",
    "To start with all z vectors and activations are computed for all layers. This is the forward\n",
    "step. After that the backpropagation is done by first computing the cost function using the\n",
    "`cost_derivative` function.\n",
    "Then the gradients for the weights and biases are computed starting with the last layer. The\n",
    "expressions in the last loop follows the formulas developed for the gradients.\n",
    "    \n",
    "Below I have put the entire `Network`class into a cell\n",
    " \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f47b303f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 0 : 9014 / 10000\n",
      "Epoch 1 : 9200 / 10000\n",
      "Epoch 2 : 9297 / 10000\n",
      "Epoch 3 : 9348 / 10000\n",
      "Epoch 4 : 9388 / 10000\n",
      "Epoch 5 : 9375 / 10000\n",
      "Epoch 6 : 9391 / 10000\n",
      "Epoch 7 : 9455 / 10000\n",
      "Epoch 8 : 9425 / 10000\n",
      "Epoch 9 : 9458 / 10000\n",
      "Epoch 10 : 9472 / 10000\n",
      "Epoch 11 : 9467 / 10000\n",
      "Epoch 12 : 9443 / 10000\n",
      "Epoch 13 : 9480 / 10000\n",
      "Epoch 14 : 9499 / 10000\n",
      "Epoch 15 : 9488 / 10000\n",
      "Epoch 16 : 9506 / 10000\n",
      "Epoch 17 : 9476 / 10000\n",
      "Epoch 18 : 9485 / 10000\n",
      "Epoch 19 : 9480 / 10000\n",
      "Epoch 20 : 9509 / 10000\n",
      "Epoch 21 : 9504 / 10000\n",
      "Epoch 22 : 9508 / 10000\n",
      "Epoch 23 : 9509 / 10000\n",
      "Epoch 24 : 9516 / 10000\n",
      "Epoch 25 : 9509 / 10000\n",
      "Epoch 26 : 9500 / 10000\n",
      "Epoch 27 : 9510 / 10000\n",
      "Epoch 28 : 9514 / 10000\n",
      "Epoch 29 : 9508 / 10000\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "network.py\n",
    "~~~~~~~~~~\n",
    "IT WORKS\n",
    "\n",
    "A module to implement the stochastic gradient descent learning\n",
    "algorithm for a feedforward neural network.  Gradients are calculated\n",
    "using backpropagation.  Note that I have focused on making the code\n",
    "simple, easily readable, and easily modifiable.  It is not optimized,\n",
    "and omits many desirable features.\n",
    "\"\"\"\n",
    "\n",
    "#### Libraries\n",
    "# Standard library\n",
    "import random\n",
    "\n",
    "class Network(object):\n",
    "\n",
    "    def __init__(self, sizes):\n",
    "        \"\"\"The list ``sizes`` contains the number of neurons in the\n",
    "        respective layers of the network.  For example, if the list\n",
    "        was [2, 3, 1] then it would be a three-layer network, with the\n",
    "        first layer containing 2 neurons, the second layer 3 neurons,\n",
    "        and the third layer 1 neuron.  The biases and weights for the\n",
    "        network are initialized randomly, using a Gaussian\n",
    "        distribution with mean 0, and variance 1.  Note that the first\n",
    "        layer is assumed to be an input layer, and by convention we\n",
    "        won't set any biases for those neurons, since biases are only\n",
    "        ever used in computing the outputs from later layers.\"\"\"\n",
    "        self.num_layers = len(sizes)\n",
    "        self.sizes = sizes\n",
    "        self.biases = [np.random.randn(y, 1) for y in sizes[1:]]\n",
    "        self.weights = [np.random.randn(y, x)\n",
    "                        for x, y in zip(sizes[:-1], sizes[1:])]\n",
    "\n",
    "\n",
    "    def feedforward(self, a):\n",
    "        \"\"\"Return the output of the network if ``a`` is input.\"\"\"\n",
    "        for b, w in zip(self.biases, self.weights):\n",
    "            a = sigmoid(np.dot(w, a)+b)\n",
    "        return a\n",
    "    \n",
    "    def SGD(self, training_data, epochs, mini_batch_size, eta,\n",
    "            test_data=None):\n",
    "        \"\"\"Train the neural network using mini-batch stochastic\n",
    "        gradient descent.  The ``training_data`` is a list of tuples\n",
    "        ``(x, y)`` representing the training inputs and the desired\n",
    "        outputs.  The other non-optional parameters are\n",
    "        self-explanatory.  If ``test_data`` is provided then the\n",
    "        network will be evaluated against the test data after each\n",
    "        epoch, and partial progress printed out.  This is useful for\n",
    "        tracking progress, but slows things down substantially.\"\"\"\n",
    "\n",
    "        training_data = list(training_data)\n",
    "        n = len(training_data)\n",
    "\n",
    "        if test_data:\n",
    "            test_data = list(test_data)\n",
    "            n_test = len(test_data)\n",
    "\n",
    "        for j in range(epochs):\n",
    "            random.shuffle(training_data)\n",
    "            mini_batches = [\n",
    "                training_data[k:k+mini_batch_size]\n",
    "                for k in range(0, n, mini_batch_size)]\n",
    "            for mini_batch in mini_batches:\n",
    "                self.update_mini_batch(mini_batch, eta)\n",
    "            if test_data:\n",
    "                print(\"Epoch {} : {} / {}\".format(j,self.evaluate(test_data),n_test))\n",
    "            else:\n",
    "                print(\"Epoch {} complete\".format(j))\n",
    "\n",
    "    def update_mini_batch(self, mini_batch, eta):\n",
    "        \"\"\"Update the network's weights and biases by applying\n",
    "        gradient descent using backpropagation to a single mini batch.\n",
    "        The ``mini_batch`` is a list of tuples ``(x, y)``, and ``eta``\n",
    "        is the learning rate.\"\"\"\n",
    "        nabla_b = [np.zeros(b.shape) for b in self.biases]\n",
    "        nabla_w = [np.zeros(w.shape) for w in self.weights]\n",
    "        for x, y in mini_batch:\n",
    "            delta_nabla_b, delta_nabla_w = self.backprop(x, y)\n",
    "            nabla_b = [nb+dnb for nb, dnb in zip(nabla_b, delta_nabla_b)]\n",
    "            nabla_w = [nw+dnw for nw, dnw in zip(nabla_w, delta_nabla_w)]\n",
    "        self.weights = [w-(eta/len(mini_batch))*nw\n",
    "                        for w, nw in zip(self.weights, nabla_w)]\n",
    "        self.biases = [b-(eta/len(mini_batch))*nb\n",
    "                       for b, nb in zip(self.biases, nabla_b)]\n",
    "\n",
    "    def backprop(self, x, y):\n",
    "        \"\"\"Return a tuple ``(nabla_b, nabla_w)`` representing the\n",
    "        gradient for the cost function C_x.  ``nabla_b`` and\n",
    "        ``nabla_w`` are layer-by-layer lists of numpy arrays, similar\n",
    "        to ``self.biases`` and ``self.weights``.\"\"\"\n",
    "        nabla_b = [np.zeros(b.shape) for b in self.biases]\n",
    "        nabla_w = [np.zeros(w.shape) for w in self.weights]\n",
    "        # feedforward\n",
    "        activation = x\n",
    "        activations = [x] # list to store all the activations, layer by layer\n",
    "        zs = [] # list to store all the z vectors, layer by layer\n",
    "        for b, w in zip(self.biases, self.weights):\n",
    "            z = np.dot(w, activation)+b\n",
    "            zs.append(z)\n",
    "            activation = sigmoid(z)\n",
    "            activations.append(activation)\n",
    "        # backward pass\n",
    "        delta = self.cost_derivative(activations[-1], y) * \\\n",
    "            sigmoid_prime(zs[-1])\n",
    "        nabla_b[-1] = delta\n",
    "        nabla_w[-1] = np.dot(delta, activations[-2].transpose())\n",
    "        # Note that the variable l in the loop below is used a little\n",
    "        # differently to the notation in Chapter 2 of the book.  Here,\n",
    "        # l = 1 means the last layer of neurons, l = 2 is the\n",
    "        # second-last layer, and so on.  It's a renumbering of the\n",
    "        # scheme in the book, used here to take advantage of the fact\n",
    "        # that Python can use negative indices in lists.\n",
    "        for l in range(2, self.num_layers):\n",
    "            z = zs[-l]\n",
    "            sp = sigmoid_prime(z)\n",
    "            delta = np.dot(self.weights[-l+1].transpose(), delta) * sp\n",
    "            nabla_b[-l] = delta\n",
    "            nabla_w[-l] = np.dot(delta, activations[-l-1].transpose())\n",
    "        return (nabla_b, nabla_w)\n",
    "\n",
    "    def evaluate(self, test_data):\n",
    "        \"\"\"Return the number of test inputs for which the neural\n",
    "        network outputs the correct result. Note that the neural\n",
    "        network's output is assumed to be the index of whichever\n",
    "        neuron in the final layer has the highest activation.\"\"\"\n",
    "        test_results = [(np.argmax(self.feedforward(x)), y)\n",
    "                        for (x, y) in test_data]\n",
    "        return sum(int(x == y) for (x, y) in test_results)\n",
    "\n",
    "    def cost_derivative(self, output_activations, y):\n",
    "        \"\"\"Return the vector of partial derivatives \\partial C_x /\n",
    "        \\partial a for the output activations.\"\"\"\n",
    "        return (output_activations-y)\n",
    "\n",
    "#### Miscellaneous functions\n",
    "def sigmoid(z):\n",
    "    \"\"\"The sigmoid function.\"\"\"\n",
    "    return 1.0/(1.0+np.exp(-z))\n",
    "\n",
    "def sigmoid_prime(z):\n",
    "    \"\"\"Derivative of the sigmoid function.\"\"\"\n",
    "    return sigmoid(z)*(1-sigmoid(z))\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "mnist_loader\n",
    "~~~~~~~~~~~~\n",
    "A library to load the MNIST image data.  For details of the data\n",
    "structures that are returned, see the doc strings for ``load_data``\n",
    "and ``load_data_wrapper``.  In practice, ``load_data_wrapper`` is the\n",
    "function usually called by our neural network code.\n",
    "\"\"\"\n",
    "\n",
    "#### Libraries\n",
    "# Standard library\n",
    "import pickle\n",
    "import gzip\n",
    "\n",
    "# Third-party libraries\n",
    "import numpy as np\n",
    "\n",
    "def load_data():\n",
    "    \"\"\"Return the MNIST data as a tuple containing the training data,\n",
    "    the validation data, and the test data.\n",
    "    The ``training_data`` is returned as a tuple with two entries.\n",
    "    The first entry contains the actual training images.  This is a\n",
    "    numpy ndarray with 50,000 entries.  Each entry is, in turn, a\n",
    "    numpy ndarray with 784 values, representing the 28 * 28 = 784\n",
    "    pixels in a single MNIST image.\n",
    "    The second entry in the ``training_data`` tuple is a numpy ndarray\n",
    "    containing 50,000 entries.  Those entries are just the digit\n",
    "    values (0...9) for the corresponding images contained in the first\n",
    "    entry of the tuple.\n",
    "    The ``validation_data`` and ``test_data`` are similar, except\n",
    "    each contains only 10,000 images.\n",
    "    This is a nice data format, but for use in neural networks it's\n",
    "    helpful to modify the format of the ``training_data`` a little.\n",
    "    That's done in the wrapper function ``load_data_wrapper()``, see\n",
    "    below.\n",
    "    \"\"\"\n",
    "    f = gzip.open('mnist.pkl.gz', 'rb')\n",
    "    training_data, validation_data, test_data = pickle.load(f, encoding=\"latin1\")\n",
    "    f.close()\n",
    "    return (training_data, validation_data, test_data)\n",
    "\n",
    "def load_data_wrapper():\n",
    "    \"\"\"Return a tuple containing ``(training_data, validation_data,\n",
    "    test_data)``. Based on ``load_data``, but the format is more\n",
    "    convenient for use in our implementation of neural networks.\n",
    "    In particular, ``training_data`` is a list containing 50,000\n",
    "    2-tuples ``(x, y)``.  ``x`` is a 784-dimensional numpy.ndarray\n",
    "    containing the input image.  ``y`` is a 10-dimensional\n",
    "    numpy.ndarray representing the unit vector corresponding to the\n",
    "    correct digit for ``x``.\n",
    "    ``validation_data`` and ``test_data`` are lists containing 10,000\n",
    "    2-tuples ``(x, y)``.  In each case, ``x`` is a 784-dimensional\n",
    "    numpy.ndarry containing the input image, and ``y`` is the\n",
    "    corresponding classification, i.e., the digit values (integers)\n",
    "    corresponding to ``x``.\n",
    "    Obviously, this means we're using slightly different formats for\n",
    "    the training data and the validation / test data.  These formats\n",
    "    turn out to be the most convenient for use in our neural network\n",
    "    code.\"\"\"\n",
    "    tr_d, va_d, te_d = load_data()\n",
    "    training_inputs = [np.reshape(x, (784, 1)) for x in tr_d[0]]\n",
    "    training_results = [vectorized_result(y) for y in tr_d[1]]\n",
    "    training_data = zip(training_inputs, training_results)\n",
    "    validation_inputs = [np.reshape(x, (784, 1)) for x in va_d[0]]\n",
    "    validation_data = zip(validation_inputs, va_d[1])\n",
    "    test_inputs = [np.reshape(x, (784, 1)) for x in te_d[0]]\n",
    "    test_data = zip(test_inputs, te_d[1])\n",
    "    return (training_data, validation_data, test_data)\n",
    "\n",
    "def vectorized_result(j):\n",
    "    \"\"\"Return a 10-dimensional unit vector with a 1.0 in the jth\n",
    "    position and zeroes elsewhere.  This is used to convert a digit\n",
    "    (0...9) into a corresponding desired output from the neural\n",
    "    network.\"\"\"\n",
    "    e = np.zeros((10, 1))\n",
    "    e[j] = 1.0\n",
    "    return e\n",
    "\n",
    "#Script to run the network\n",
    "\n",
    "#Load the training and test data\n",
    "training_data, validation_data, test_data = load_data_wrapper()\n",
    "\n",
    "#Create the network first try with 30 neurons internal layers\n",
    "net = Network([784, 30, 10])\n",
    "#Run the network\n",
    "net.SGD(training_data, 30, 10, 3.0, test_data=test_data)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70922267",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "83e14308",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}