5_Neural_Network_Tutorial_Training_And_Testing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Pre-requisites\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "# For plots\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# To clear print buffer\n",
    "from IPython.display import clear_output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Importing functions from the previous tutorials:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "weights:\n",
      "1\n",
      "(2, 3)\n",
      "[[-0.33589735 -0.396816    0.45849862]\n",
      " [-0.64374374 -2.41279823  0.78403628]]\n",
      "2\n",
      "(1, 3)\n",
      "[[ 1.54182154 -0.12516091 -0.28203429]]\n"
     ]
    }
   ],
   "source": [
    "# Initializing weight matrices from layer sizes\n",
    "def initializeWeights(layers):\n",
    "    weights = [np.random.randn(o, i+1) for i, o in zip(layers[:-1], layers[1:])]\n",
    "    return weights\n",
    "\n",
    "# Add a bias term to every data point in the input\n",
    "def addBiasTerms(X):\n",
    "        # Make the input an np.array()\n",
    "        X = np.array(X)\n",
    "        \n",
    "        # Forcing 1D vectors to be 2D matrices of 1xlength dimensions\n",
    "        if X.ndim==1:\n",
    "            X = np.reshape(X, (1, len(X)))\n",
    "        \n",
    "        # Inserting bias terms\n",
    "        X = np.insert(X, 0, 1, axis=1)\n",
    "        \n",
    "        return X\n",
    "\n",
    "# Sigmoid function\n",
    "def sigmoid(a):\n",
    "    return 1/(1 + np.exp(-a))\n",
    "\n",
    "# Forward Propagation of outputs\n",
    "def forwardProp(X, weights):\n",
    "    # Initializing an empty list of outputs\n",
    "    outputs = []\n",
    "    \n",
    "    # Assigning a name to reuse as inputs\n",
    "    inputs = X\n",
    "    \n",
    "    # For each layer\n",
    "    for w in weights:\n",
    "        # Add bias term to input\n",
    "        inputs = addBiasTerms(inputs)\n",
    "        \n",
    "        # Y = Sigmoid ( X .* W^T )\n",
    "        outputs.append(sigmoid(np.dot(inputs, w.T)))\n",
    "        \n",
    "        # Input of next layer is output of this layer\n",
    "        inputs = outputs[-1]\n",
    "        \n",
    "    return outputs\n",
    "\n",
    "# Compute COST (J) of Neural Network\n",
    "def nnCost(weights, X, Y):\n",
    "    # Calculate yPred\n",
    "    yPred = forwardProp(X, weights)[-1]\n",
    "    \n",
    "    # Compute J\n",
    "    J = 0.5*np.sum((yPred-Y)**2)/len(Y)\n",
    "    \n",
    "    return J\n",
    "\n",
    "# IMPLEMENTING BACK-PROPAGATION WITH LEARNING RATE\n",
    "# Added eta, the learning rate, as an input\n",
    "def backProp(weights, X, Y, learningRate):\n",
    "    # Forward propagate to find outputs\n",
    "    outputs = forwardProp(X, weights)\n",
    "    \n",
    "    # For the last layer, bpError = error = yPred - Y\n",
    "    bpError = outputs[-1] - Y\n",
    "    \n",
    "    # Back-propagating from the last layer to the first\n",
    "    for l, w in enumerate(reversed(weights)):\n",
    "        \n",
    "        # Find yPred for this layer\n",
    "        yPred = outputs[-l-1]\n",
    "        \n",
    "        # Calculate delta for this layer using bpError from next layer\n",
    "        delta = np.multiply(np.multiply(bpError, yPred), 1-yPred)\n",
    "        \n",
    "        # Find input to the layer, by adding bias to the output of the previous layer\n",
    "        # Take care, l goes from 0 to 1, while the weights are in reverse order\n",
    "        if l==len(weights)-1: # If 1st layer has been reached\n",
    "            xL = addBiasTerms(X)\n",
    "        else:\n",
    "            xL = addBiasTerms(outputs[-l-2])\n",
    "        \n",
    "        # Calculate deltaW for this layer\n",
    "        deltaW = -np.dot(delta.T, xL)/len(Y)\n",
    "        \n",
    "        # Calculate bpError for previous layer to be back-propagated\n",
    "        bpError = np.dot(delta, w)\n",
    "        \n",
    "        # Ignore bias term in bpError\n",
    "        bpError = bpError[:,1:]\n",
    "        \n",
    "        # Change weights of the current layer (W <- W + eta*deltaW)\n",
    "        w += learningRate*deltaW\n",
    "\n",
    "# Evaluate the accuracy of weights for input X and desired outptut Y\n",
    "def evaluate(weights, X, Y):\n",
    "    yPreds = forwardProp(X, weights)[-1]\n",
    "    # Check if maximum probability is from that neuron corresponding to desired class,\n",
    "    # AND check if that maximum probability is greater than 0.5\n",
    "    yes = sum( int( ( np.argmax(yPreds[i]) == np.argmax(Y[i]) ) and \n",
    "                    ( (yPreds[i][np.argmax(yPreds[i])]>0.5) == (Y[i][np.argmax(Y[i])]>0.5) ) )\n",
    "              for i in range(len(Y)) )\n",
    "    print(str(yes)+\" out of \"+str(len(Y))+\" : \"+str(float(yes/len(Y))))\n",
    "\n",
    "# Initialize network\n",
    "layers = [2, 2, 1]\n",
    "weights = initializeWeights(layers)\n",
    "\n",
    "print(\"weights:\")\n",
    "for i in range(len(weights)):\n",
    "    print(i+1); print(weights[i].shape); print(weights[i])\n",
    "\n",
    "# Declare input and desired output for AND gate\n",
    "X = np.array([[0,0], [0,1], [1,0], [1,1]])\n",
    "Y = np.array([[0], [0], [0], [1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Batch Gradient Descent\n",
    "\n",
    "Batch Gradient Descent is how we have tried to train our network so far - give it ALL the data points, compute ${\\Delta}W$s by summing up quantities across ALL the data points, change all the weights once, Repeat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose we want to train our 3-neuron network to implement Logical XOR.\n",
    "\n",
    "Inputs are: $X=\\left[\\begin{array}{c}(0,0)\\\\(0,1)\\\\(1,0)\\\\(1,1)\\end{array}\\right]$, and the desired output is $Y=\\left[\\begin{array}{c}0\\\\1\\\\1\\\\0\\end{array}\\right]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We know that in order to train the network, we need to call backProp repeatedly. Let us use a function to do that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TRAINING FUNCTION, USING GD\n",
    "def train(weights, X, Y, nIterations, learningRate=1):\n",
    "    for i in range(nIterations):\n",
    "        # Run backprop\n",
    "        backProp(weights, X, Y, learningRate)\n",
    "        \n",
    "        # Clears screen output\n",
    "        if (i+1)%(nIterations/10)==0:\n",
    "            clear_output()\n",
    "            print(\"Iteration \"+str(i+1)+\" of \"+str(nIterations))\n",
    "            # Prints Cost and Accuracy\n",
    "            print(\"Cost: \"+str(nnCost(weights, X, Y)))\n",
    "            print(\"Accuracy:\")\n",
    "            evaluate(weights, X, Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "weights:\n",
      "1\n",
      "(2, 3)\n",
      "[[ 0.04837515  0.26989845 -0.24049688]\n",
      " [ 0.40457749 -1.12764482  1.62391936]]\n",
      "2\n",
      "(1, 3)\n",
      "[[-0.21690785 -0.77508326  0.61363791]]\n"
     ]
    }
   ],
   "source": [
    "# Initialize network\n",
    "layers = [2, 2, 1]\n",
    "weights = initializeWeights(layers)\n",
    "\n",
    "print(\"weights:\")\n",
    "for i in range(len(weights)):\n",
    "    print(i+1); print(weights[i].shape); print(weights[i])\n",
    "\n",
    "# Take backup of weights to be used later for comparison\n",
    "initialWeights = [np.array(w) for w in weights]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Declare input and desired output for XOR gate\n",
    "X = np.array([[0,0], [0,1], [1,0], [1,1]])\n",
    "Y = np.array([[0], [1], [1], [0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cost: 0.12907524705\n",
      "Accuracy: \n",
      "2 out of 4 : 0.5\n",
      "[[ 0.43886508]\n",
      " [ 0.49374299]\n",
      " [ 0.38577198]\n",
      " [ 0.4543426 ]]\n"
     ]
    }
   ],
   "source": [
    "# Check current accuracy and cost\n",
    "print(\"Cost: \"+str(nnCost(weights, X, Y)))\n",
    "print(\"Accuracy: \")\n",
    "evaluate(weights, X, Y)\n",
    "print(forwardProp(X, weights)[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say we want to train our model 600 times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 400 of 400\n",
      "Cost: 0.124997811474\n",
      "Accuracy:\n",
      "3 out of 4 : 0.75\n",
      "[[ 0.49895486]\n",
      " [ 0.50338071]\n",
      " [ 0.49407386]\n",
      " [ 0.4984321 ]]\n"
     ]
    }
   ],
   "source": [
    "nIterations = 400\n",
    "train(weights, X, Y, nIterations)\n",
    "print(forwardProp(X, weights)[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# In case we want to revert the weight back\n",
    "weights = [np.array(w) for w in initialWeights]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It took our function a long time to train.\n",
    "\n",
    "What if we speed up using adaptive learning rate?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TRAINING FUNCTION, USING GD\n",
    "# Default learning rate = 1.0\n",
    "def trainUsingGD(weights, X, Y, nIterations, learningRate=1.0):\n",
    "    # Setting initial cost to infinity\n",
    "    prevCost = np.inf\n",
    "    \n",
    "    # For nIterations number of iterations:\n",
    "    for i in range(nIterations):\n",
    "        # Run backprop\n",
    "        backProp(weights, X, Y, learningRate)\n",
    "        \n",
    "        #clear_output()\n",
    "        print(\"Iteration \"+str(i+1)+\" of \"+str(nIterations))\n",
    "        cost = nnCost(weights, X, Y)\n",
    "        print(\"Cost: \"+str(cost))\n",
    "        \n",
    "        # ADAPT LEARNING RATE\n",
    "        # If cost increases\n",
    "        if (cost > prevCost):\n",
    "            # Halve the learning rate\n",
    "            learningRate /= 2.0\n",
    "        # If cost decreases\n",
    "        else:\n",
    "            # Increase learning rate by 5%\n",
    "            learningRate *= 1.05\n",
    "        \n",
    "        prevCost = cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Revert weights back to initial values\n",
    "weights = [np.array(w) for w in initialWeights]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 1 of 100\n",
      "Cost: 0.128848112614\n",
      "Iteration 2 of 100\n",
      "Cost: 0.128650869728\n",
      "Iteration 3 of 100\n",
      "Cost: 0.12848026395\n",
      "Iteration 4 of 100\n",
      "Cost: 0.128332996448\n",
      "Iteration 5 of 100\n",
      "Cost: 0.128205816336\n",
      "Iteration 6 of 100\n",
      "Cost: 0.128095601033\n",
      "Iteration 7 of 100\n",
      "Cost: 0.127999422128\n",
      "Iteration 8 of 100\n",
      "Cost: 0.12791459536\n",
      "Iteration 9 of 100\n",
      "Cost: 0.127838714376\n",
      "Iteration 10 of 100\n",
      "Cost: 0.12776966891\n",
      "Iteration 11 of 100\n",
      "Cost: 0.127705648793\n",
      "Iteration 12 of 100\n",
      "Cost: 0.127645135859\n",
      "Iteration 13 of 100\n",
      "Cost: 0.127586886153\n",
      "Iteration 14 of 100\n",
      "Cost: 0.127529905081\n",
      "Iteration 15 of 100\n",
      "Cost: 0.127473418103\n",
      "Iteration 16 of 100\n",
      "Cost: 0.127416839401\n",
      "Iteration 17 of 100\n",
      "Cost: 0.127359740627\n",
      "Iteration 18 of 100\n",
      "Cost: 0.127301821408\n",
      "Iteration 19 of 100\n",
      "Cost: 0.127242882839\n",
      "Iteration 20 of 100\n",
      "Cost: 0.127182804686\n",
      "Iteration 21 of 100\n",
      "Cost: 0.127121526616\n",
      "Iteration 22 of 100\n",
      "Cost: 0.127059033379\n",
      "Iteration 23 of 100\n",
      "Cost: 0.126995343612\n",
      "Iteration 24 of 100\n",
      "Cost: 0.126930501761\n",
      "Iteration 25 of 100\n",
      "Cost: 0.126864572508\n",
      "Iteration 26 of 100\n",
      "Cost: 0.126797637148\n",
      "Iteration 27 of 100\n",
      "Cost: 0.126729791334\n",
      "Iteration 28 of 100\n",
      "Cost: 0.126661143778\n",
      "Iteration 29 of 100\n",
      "Cost: 0.126591815524\n",
      "Iteration 30 of 100\n",
      "Cost: 0.126521939537\n",
      "Iteration 31 of 100\n",
      "Cost: 0.126451660431\n",
      "Iteration 32 of 100\n",
      "Cost: 0.126381134199\n",
      "Iteration 33 of 100\n",
      "Cost: 0.126310527861\n",
      "Iteration 34 of 100\n",
      "Cost: 0.126240018977\n",
      "Iteration 35 of 100\n",
      "Cost: 0.126169794983\n",
      "Iteration 36 of 100\n",
      "Cost: 0.126100052304\n",
      "Iteration 37 of 100\n",
      "Cost: 0.126030995231\n",
      "Iteration 38 of 100\n",
      "Cost: 0.125962834522\n",
      "Iteration 39 of 100\n",
      "Cost: 0.125895785707\n",
      "Iteration 40 of 100\n",
      "Cost: 0.12583006709\n",
      "Iteration 41 of 100\n",
      "Cost: 0.125765897414\n",
      "Iteration 42 of 100\n",
      "Cost: 0.125703493213\n",
      "Iteration 43 of 100\n",
      "Cost: 0.125643065835\n",
      "Iteration 44 of 100\n",
      "Cost: 0.12558481818\n",
      "Iteration 45 of 100\n",
      "Cost: 0.125528941182\n",
      "Iteration 46 of 100\n",
      "Cost: 0.125475610101\n",
      "Iteration 47 of 100\n",
      "Cost: 0.125424980703\n",
      "Iteration 48 of 100\n",
      "Cost: 0.125377185428\n",
      "Iteration 49 of 100\n",
      "Cost: 0.12533232967\n",
      "Iteration 50 of 100\n",
      "Cost: 0.125290488278\n",
      "Iteration 51 of 100\n",
      "Cost: 0.125251702426\n",
      "Iteration 52 of 100\n",
      "Cost: 0.125215976974\n",
      "Iteration 53 of 100\n",
      "Cost: 0.125183278403\n",
      "Iteration 54 of 100\n",
      "Cost: 0.125153533406\n",
      "Iteration 55 of 100\n",
      "Cost: 0.125126628143\n",
      "Iteration 56 of 100\n",
      "Cost: 0.125102408083\n",
      "Iteration 57 of 100\n",
      "Cost: 0.125080678309\n",
      "Iteration 58 of 100\n",
      "Cost: 0.125061203999\n",
      "Iteration 59 of 100\n",
      "Cost: 0.125043710737\n",
      "Iteration 60 of 100\n",
      "Cost: 0.125027884097\n",
      "Iteration 61 of 100\n",
      "Cost: 0.125013367839\n",
      "Iteration 62 of 100\n",
      "Cost: 0.124999759817\n",
      "Iteration 63 of 100\n",
      "Cost: 0.124986604465\n",
      "Iteration 64 of 100\n",
      "Cost: 0.12497338044\n",
      "Iteration 65 of 100\n",
      "Cost: 0.124959481574\n",
      "Iteration 66 of 100\n",
      "Cost: 0.124944188837\n",
      "Iteration 67 of 100\n",
      "Cost: 0.12492663033\n",
      "Iteration 68 of 100\n",
      "Cost: 0.124905725647\n",
      "Iteration 69 of 100\n",
      "Cost: 0.124880110131\n",
      "Iteration 70 of 100\n",
      "Cost: 0.124848033934\n",
      "Iteration 71 of 100\n",
      "Cost: 0.124807230659\n",
      "Iteration 72 of 100\n",
      "Cost: 0.124754751262\n",
      "Iteration 73 of 100\n",
      "Cost: 0.124686761318\n",
      "Iteration 74 of 100\n",
      "Cost: 0.124598303179\n",
      "Iteration 75 of 100\n",
      "Cost: 0.124483025338\n",
      "Iteration 76 of 100\n",
      "Cost: 0.12433286859\n",
      "Iteration 77 of 100\n",
      "Cost: 0.124137651121\n",
      "Iteration 78 of 100\n",
      "Cost: 0.123884387194\n",
      "Iteration 79 of 100\n",
      "Cost: 0.123556010954\n",
      "Iteration 80 of 100\n",
      "Cost: 0.123129051477\n",
      "Iteration 81 of 100\n",
      "Cost: 0.122569925578\n",
      "Iteration 82 of 100\n",
      "Cost: 0.121830095196\n",
      "Iteration 83 of 100\n",
      "Cost: 0.120841446193\n",
      "Iteration 84 of 100\n",
      "Cost: 0.119514949723\n",
      "Iteration 85 of 100\n",
      "Cost: 0.117748246786\n",
      "Iteration 86 of 100\n",
      "Cost: 0.115450497266\n",
      "Iteration 87 of 100\n",
      "Cost: 0.112589941634\n",
      "Iteration 88 of 100\n",
      "Cost: 0.109249438151\n",
      "Iteration 89 of 100\n",
      "Cost: 0.105640175411\n",
      "Iteration 90 of 100\n",
      "Cost: 0.102027696196\n",
      "Iteration 91 of 100\n",
      "Cost: 0.0990064970213\n",
      "Iteration 92 of 100\n",
      "Cost: 0.123641875887\n",
      "Iteration 93 of 100\n",
      "Cost: 0.206124967964\n",
      "Iteration 94 of 100\n",
      "Cost: 0.128853866919\n",
      "Iteration 95 of 100\n",
      "Cost: 0.100914621849\n",
      "Iteration 96 of 100\n",
      "Cost: 0.0954172210932\n",
      "Iteration 97 of 100\n",
      "Cost: 0.0925797728969\n",
      "Iteration 98 of 100\n",
      "Cost: 0.0909633907318\n",
      "Iteration 99 of 100\n",
      "Cost: 0.0897659003613\n",
      "Iteration 100 of 100\n",
      "Cost: 0.0886726139317\n"
     ]
    }
   ],
   "source": [
    "# Train for nIterations\n",
    "# Don't expect same results for running with 20 iterations\n",
    "# as with running twice with 10 iterations - learning rates are different!\n",
    "nIterations = 100\n",
    "trainUsingGD(weights, X, Y, nIterations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that with adaptive learning rate, we reach the desired output much faster!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MNIST Dataset\n",
    "\n",
    "MNIST is a dataset of 60000 images of hand-written numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Load MNIST DATA\n",
    "# Use numpy.load() to load the .npz file\n",
    "f = np.load('mnist.npz')\n",
    "# Saving the files\n",
    "x_train = f['x_train']\n",
    "y_train = f['y_train']\n",
    "x_test = f['x_test']\n",
    "y_test = f['y_test']\n",
    "f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x_train.shape = (60000, 28, 28)\n",
      "y_train.shape = (60000,)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAlMAAACNCAYAAACT6v+eAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3WeAFMX29/HvkhQDIKBEI4JgJoMiiChiAgVFURQxoKhg\nRBC9JpJIUBAEAdM1Z1BQMSCgcPUa0D+KRHPEAIogK2GfF/2c6tnd2djTM917f5836M7sTNX2THf1\nqVOnsnJychARERGR0imX6QaIiIiIxJkGUyIiIiIBaDAlIiIiEoAGUyIiIiIBaDAlIiIiEoAGUyIi\nIiIBaDAlIiIiEoAGUyIiIiIBaDAlIiIiEkCFdL5ZVlZWrMut5+TkZBX1nLLex7LeP1Af40B9LPv9\nA/UxDtRHjyJTIiIiIgFoMCUiIiISgAZTIiIiIgFoMCUiIiISgAZTIiIiIgFoMBVTzZs358EHH+TB\nBx9k27ZtbNu2zf1/s2bNMt08EYmhCRMmkJOTQ05ODkuXLmXp0qXsvffemW6WSCjefPNN5s2bx7x5\n8wK/lgZTIiIiIgGktc5UGMqXL0/VqlXz/fyKK64AYKeddgLggAMOAODyyy9n7NixAPTq1QuAzZs3\nc8cddwBw2223hd7mIA4//HAAXn/9dapUqQJATo5XwuPcc88FoGvXrtSoUSMzDUyTTp06AfDYY48B\n0KFDB1asWJHJJqXETTfdBHifw3LlvHudo48+GoAFCxZkqllSiF133ZVddtkFgJNOOgmA3XffHYDx\n48eTnZ2dsbYV1z777ANA79692b59OwBNmjQBoHHjxnz99deZalrKNGrUCICKFSvSvn17AO69914A\n1+eCzJo1C4CzzjoLgH/++SesZqZExYoVOeKIIwAYOXIkAEceeWQmmxQpd911FwBHHHEE//73v1Py\nmrEYTO21115UqlQJwH1A2rVrB0C1atXo0aNHka/x3XffATBx4kROO+00ADZs2ADAJ598EvkLVatW\nrQB47rnnAKhataobRFk/7Ateo0YN2rRpA8BHH32U67Ew2QmqRo0avPDCC6G+V8uWLQF4//33Q32f\ndDn//PMBGDx4MJD75G7HWaLBBh52rNq2bcvBBx+c9Ll16tRh4MCB6Wpaqf3yyy8ALFy4kK5du2a4\nNalx0EEHAf5364wzzgCgXLly1K1bF/C/Z0V9x+xvMnXqVACuuuoq/vzzz5S3OVWqVq3KW2+9BcBP\nP/0EQO3atd1//6+yoMmll14KwJYtW3jzzTdT8tqa5hMREREJINKRKZvSmjdvXtKpvOKwOw+bPvnr\nr7/c1NCPP/4IwLp16yI5RWRTlM2aNePRRx8FvDvdvFatWgXAnXfeCcCTTz7JokWLAL/fo0aNCr29\nNh3VsGHDUCNT5cqVY9999wVwybFZWUVW+48068eOO+6Y4ZaUXuvWrenduzfgTbuCHx0AuO666wD4\n4YcfAC+6bJ/r9957L51NLbHGjRsDXkTinHPOAaBy5cqA99n79ttvAT9KbFNkPXv2dFNJy5cvT2ub\nS2Ljxo0AZWI6z9g578QTT0zZa5533nkA3H///e4cG3W1a9d2//6vR6ZsxqZixYoAvPPOOzz99NMp\neW1FpkREREQCiHRk6ptvvgHgt99+K1Zkyu5u169fT8eOHQE/V+iRRx4JqZXhue+++wA/Ub4gVgrB\nkmAXLFjgokSHHnpoeA3Mw+7a/vOf/4T6PnXq1OHiiy8GcJGNKN/1F+bYY48FYMCAAbl+vnz5ck4+\n+WQAfv7557S3qyTOPPNMwFtWX7NmTcCPFM6fP98lY48ZMybX72VlZbnHLLE3Kux8M3r0aMDv4667\n7prvuatWreL4448H/Dte+zzWrFnT/U2irFq1agAcdthhGW5J6rz++utA/sjU2rVruf/++wHcIo/E\nHEXLy7XoatzFPWpfkPbt23PjjTcC/jXy999/L/D5vXr1crmNa9asAfxoeSpEejBlf5hBgwa5C8uS\nJUsAL5HcfPzxxwAcd9xxgBeytumFK6+8Mm3tTZXmzZsD/sqgxC+DJcq/9NJLblWiTZvY32bdunUc\nc8wx+X43bHZiCtuMGTPcf9sUZxy1a9eOBx98ECDfzcKYMWMiO+VSoYJ32mjRogUA06dPB7xp6YUL\nFwIwbNgwwAuj77DDDgAunN65c2f3Wh988EF6Gl1CtkjloosuKvA5dkI+7rjj3DTf/vvvH37jQmAp\nBXvttVe+x1q2bOkGh1H9TCYzZcoUAGbOnJnr51u2bCl0ustWSX/66acALlk98bWi+rlNxpLr45xC\nkMy0adNo2LAhAAceeCDgnW8KMnToULfK3W7GP/nkk5S1R9N8IiIiIgFEOjJlZs6c6SqUWoKnhaMv\nvPBCF6GxJEqAzz77DIB+/fqls6mBJNaQAnLVkXrllVcAP5zZoUMHl1xukRpb3vzJJ5+4sLVFt5o1\na+bKJKSaTSXWqlUrlNfPKzGKY3+rOOrTp0+uu17wpsWAlNU+CYMlmSdGCME7FjYdlrhs3H6WGJEC\nr1zJww8/HGZTS82W0ef11VdfuXIcVhrBolLgJ57HjUW3H3roIW699dZcj916662sX78egEmTJqW7\naaW2detWIPfxKQ6bst1tt93yPWYlduJQOyyvFi1a8O6772a6GSmzadOmYkXd7Lq69957u+tiGFE6\nRaZEREREAohFZArIVyDtjz/+cP9t859PPfUUUHQ12yhq1KgRgwYNAvzIy6+//gp4JRzsDv6vv/4C\nYM6cOcyZM6fI17Xl29dee61b0p1qluBp7xUWi3xZWQSA77//PtT3DIMlJF9wwQXus2p3/sOHD89Y\nu4pj2LBhDB06FPBzMWzp/0033ZS0kKElieY1cOBAF02NGjunWGT7tddeA2D16tWsXbu2wN9LV3Q2\nLMOGDcsXmfpfYYsg7NgnO5/dfPPNaW1TaW3dutVdI+160qBBg0w2KWUsH/OQQw7h888/B5LnPu28\n886AH0HeaaedXGTu2WefTXm7FJkSERERCSA2kam87O6pefPmbgmrLTO3u8g4sJVOY8eOdREeywuz\nUgMffPBB4KhPslU6qWL7HhrLV0s1y42rVasWK1euBPy/VRzYNiS2JVCie+65B8BtARE1dkc+dOhQ\nV25k7ty5gH/n9/fff7vnW05C586d3WfPVpZa9M32O4siyyEqaZSmbdu2IbQmvZKVCyirLFo/ZMgQ\ntxLTylskshXjW7ZsSV/jAli/fj1vv/02gFsJH3d77rkn4EcOt27d6vbgTRbhHj9+PODnP/7www+h\n7k8Y28GUJZtffPHFLrHalmi/9dZbbunq5MmTgejub9a0aVMgdy2Ubt26AfHd2DYV++VVqVKFLl26\nAH7Cc2ICs4V6bXosDqw/ibW/bF+oCRMmZKRNRbH6Q5dddhngfY9sEHXqqafme75dkGyXASvzAX5o\n3Sr1x5XttWfTCIkOOeSQXP+/ePHi0OuupVpx96uLOrt5sQ3g7WY7ke3xmqyvNmU9ZMgQXn75ZSD3\nDYOkh9WGsl01LE3innvuSXqNtNpRtiejGTFiRIit1DSfiIiISCCxjUyZNWvWuBGoFUA899xz3d2I\n3T3aUnPbjy8qLBSZlZXlRtmpiEhlMlRfvXr1pD+3chY23WN3ivXr16dSpUqAH3YvV66cuwu0yva2\nHLlChQp8+OGHIbU+HKeeeqrbsdy888479OnTB8i9oCJK7LgkVvG2yMwee+wBQN++fQHo2rWru4u0\navw5OTnurt+q1SeWMIk6K2ZpRQFvueWWfBW1y5Url+97ZtOEffv2Zdu2bWloqSQ6+OCDefHFF4HS\npzjYNNm0adNS1q5MsoKVcWCFgXv37l1gtfq2bdtyww03AP51tHr16m5az64zdu23HUXCosiUiIiI\nSACxj0yBP5dqW4uMHz+eTp06ATBy5EjAK9gF3rxpFJbTW1KgFRTLyclxd1KpkDfvwRIow2ARJHuv\nqVOnuuXziSxXyO4YrKjepk2bWLZsGQAPPPAA4CXdW4TO9qazgnmVK1eOzV58hSWdf/HFF5Hfd8+S\nzS3Bc/fdd+fLL78EkueZWETG8k3q1KnjSny89NJLobc3FSpWrOhyGe241alTB/A+69ZHy4Xq0qWL\ni2AZu7Pu3r27y4ezv6Wkh51nCttSq7AIvp2jTzjhBFc0Oc66du2a6SYUm5WpmDFjhjvP2DFavXo1\n4BUhtS2tLM+4Xr167rtq56wLLrggLW0uE4MpY3sp9ezZk1NOOQXwp/4uueQSABo2bOj28MskW51n\n0yhr1651dbJKy1YGJq5AssrxFg4NgyUn275dtlFoXrZxte1vZTVCiqrKa7V+bFPcL774ImCL08dW\nuiU7Weed9osiS/C3ZPPZs2e7aVzbm85W5T300ENuP80nn3wS8AYh9t9RZ9/FLl268Pzzz+d67Lbb\nbgO879OiRYsAfzp73rx5bnrT2Gd11KhR+T73Ua+enWyA0b59eyA+FdA//fRTt9m7LWCxhRObN29O\n+jsXXnghkH/T8biylcFxWs1nuyXYdXvLli3uHHT22WcD3t6zAOPGjXMr+W1QlZWV5QZflppgFfCP\nPvpod84Kg6b5RERERAIoU5Eps379eh555BHA3z/Mwu7t27d3dyy2D1oUZGdnlzo53iJStlffoEGD\n3JTYuHHjAL9yephGjx4dyuvalK1JNmUWNTZ9m3c/OvAjOStWrEhrm4KwRQAWcSmIRTDsjnH79u2R\njyRaXSGLPtlOBICb3rE6YOvXr3d/A1suf8ghh7gpPCv7YJGqbt26uTIRb7zxBuB9T+zu2oQ5DV9S\nyUojdO/eHfAT8W1aPsosUl7cJfEW0S8rkSmLiJqKFSu6dBf720SNzSBZ24cPH+6iVHkNGDDAJZUn\nq+9m07sWoQszKgWKTImIiIgEUqYiU5bgfPrpp9OyZUvAj0iZZcuWsXDhwrS3rSilST636IfdSdt8\n86xZs+jRo0fqGhcxtuAgyqwKf+LO85YblreYXFliuYCJ0Y0o50yVL1/eFYC1Yn8bN25kyJAhgJ/7\nZXkbLVq0cHlDlqS+atUq+vfvD/h3wVWqVAG8/EEr92EJwK+//rp7f8vnSNxvMtOmTp0K+FGCRJa/\neNVVV6W1Telw/PHHZ7oJKWULfExWVpabxYgqi9pbzqJ9P5KpWbNmvlzFXr16udxpY7M0YVNkSkRE\nRCSA2EemDjjgALc/j83r165dO9/zrHDejz/+GIk9p/Iu2z311FO58sori/37V199Nf/6178Af1dw\ny82wPf0kc6xAXuJn7d577wXSk7+WKbZiKi769evnIlKbNm0CvIiMRRbbtGkD+IVJTzjhBBd9u/32\n2wFv5VHeO2grDfHqq6/y6quvAt5dM/irksD7HkdNXMqOJLK8N8tRnDdvXom2funbt29kt3QqLYvy\n2PFs3LixiyjaCuyoKc4xsOvdGWec4SLAlg/19NNPh9e4IsRuMGUDJTsxXXHFFa6WTzK2R58lIaay\nllMQltxp/9auXZuJEycCfq2l3377DfBO6FbR3aqI169f3yXp2QXMLtZllQ08GzVqVGQ5hUyxZElb\nXp5o8eLF6W5O2sVtqsQ2cAZvyg+8aXNLRra9BhPZY6NGjQIodoXzJ554Ite/UWXJ9paI3aBBA/eY\n3fDZc8JO6i2Odu3aceONNwK4sjf77rtvoVNEVtbCqtmPHz8+X60wG4wVVEohLuzGoF69elxzzTUZ\nbk1wNhDs378/a9euBeCYY47JZJMATfOJiIiIBBKLyFStWrXcklxL/mzcuHGBz3/vvfcYM2YM4Ic6\nozC1V5jy5cu7Ebclj9tUQcOGDfM9f/HixS7ZNfHuuiyzKF6yqE8UHH744W6/Qfu82ZL5yZMnR77a\neSrst99+mW5Cifz000+u1IEl51r0F/zyB7ZoZebMmXz11VdA8SNScfXZZ58BuY9pFM+jkyZNypeI\nfP3117Nhw4YCf8ciWM2aNQNyl4GwkjlTpkwB/EUFcZeTkxPrKvxW1uGiiy4CvP7YvonpSjIvTDSv\nSiIiIiIxEcnIlM1nW0Guww8/vNA7XstFsQKVc+fOLVHyYSbYvl7vv/8+gCvlAH5eWK1atdzPLH/K\nlmqXJFm9rGnbti0PPfRQppuRT7Vq1fItfrB9IC3Juax7++23gcL3PIuS9u3bu61yLEqxdu1al7do\nxTXjfEdfWnbXb1tzxYmVqiiutWvXur0j7dwa91ypvKpUqeL2sItDeZm8rKSIRageffRRbrnllkw2\nKZfIDKZat24NeMmfrVq1AryEuYLYypuJEye6zYw3btwYcitTx8KStgLxkksucRXM85owYYILOdsm\nj/+LCtuwVKLBarzYpuP77befS2C2jUejZMOGDW63BPtXPFbl/PPPP6dJkyYZbk3Bzj//fJcs36dP\nnyKfv2bNGnf9sMH/tGnT8tUnKit69uwJeLts2H6ocWSLe6wunKXwRIWm+UREREQCyEpMvAv9zbKy\nCnyzO+64A8i9L5ZZtmwZs2fPBvyqrjalZ5WJ0yEnJ6fI0EhhfYyDovqYif5ZxXCbepk+fXrS6szF\nEeYxrF27Nk899RTgLdcG+PLLL4HkS+zDEoXPqR2zGTNmsGDBAsBfap+Kfd2i0MewRfG7mEqpPIa2\neMA+d8OHD3e7D8ycORPwp4lmzZrFTz/9VPIGl0IUPqeWGtKkSRNXhT+Ve/NFoY9hK04fFZkSERER\nCSAykak40Ai87PcP1MdUsMrETz/9tCsXYfttWTXxIDmOUehj2PRdVB/jQH30KDIlIiIiEoAiUyWg\nEXjZ7x+oj6lUpUoVt5WTLVc/9NBDgWC5U1HqY1j0XVQf40B99GgwVQL60JT9/oH6GAfqY9nvH6iP\ncaA+ejTNJyIiIhJAWiNTIiIiImWNIlMiIiIiAWgwJSIiIhKABlMiIiIiAWgwJSIiIhKABlMiIiIi\nAWgwJSIiIhKABlMiIiIiAWgwJSIiIhKABlMiIiIiAWgwJSIiIhKABlMiIiIiAWgwJSIiIhJAhXS+\nWVZWVqx3Vc7Jyckq6jllvY9lvX+gPsaB+lj2+wfqYxyojx5FpkREREQCSGtkSkRya9SoEQCvvvoq\nAOXLlwdg7733zlibRESkZBSZEhEREQlAkSmRDLnnnns488wzAahevToAs2fPzmSTRKQM22+//QAY\nNWoUAKeddhoAhx56KMuXL89Yu8oCRaZEREREAohtZOrAAw8E4OSTT6Zfv34AvP/++wAsWbLEPe/u\nu+8G4J9//klzC0Vyq1WrFgDPP/88AG3atCEnx1vk8umnnwJw4YUXZqZxIlKmHXHEES4385dffgFg\n8uTJAPz8888Za1dZociUiIiISABZdmecljdLQa2JSy65BICxY8cCsMsuuxT6/GOOOQaAt956K+hb\nq54Gyftnx8DyfzZv3kzz5s0B2HXXXQE455xzmD9/PgDff/99ga//008/ATBr1iw++OCDkja/SJk6\nho0aNXKf2RNPPNHehyFDhgC4vsbxc5qV5b3dE0884fpmkePvvvsuVW+Ti76Lqe3fueeeC0Dnzp05\n/PDDATjggAPc4++++y4Ap5xyCgB//PFH4PeMyzHceeed3bmrbt26ABx55JF89dVXRf5uFPp40kkn\nAfDss88ydepUAG688UYANm3aFPj1o9DHsBWrj3EbTFmi7ueffw7AHnvsUejz169fD/gX+tdee63U\n760PTfL+3XnnnQBcd911KWvH9u3bWbZsGeBdpBP/Lc5JrCCZOoZt2rThnXfeyfs+9O7dG/D7lgrp\n7uNOO+0EwIoVK6hXrx6Am3qfMWNGqt4mF30Xg/WvZs2agH98bJC0fv16Fi9enOu5Rx99NDvvvDOA\nS1K2wXIQUTqGdevWZffdd8/1s3Xr1gHQsWNHHnzwQcD7jAO0atWKDRs2FPm6mezj/vvvD8Ann3wC\nwNtvv+1udrZv356y94nScQyLinaKiIiIhCx2Cei///47ALfccgsA48aNc3fG33zzDQB77bWXe361\natUA6NKlCxAsMhUnVvSxcuXKAPTq1Yv+/fvnes6cOXMA6Nu3b6D36t69e4GP/fbbbwD83//9X4HP\nWbFihZtSsOPVtGlTDj74YABGjBiR6zWCRKbSzYpyPv744246zHTv3p1Zs2ZlolkpZVMFq1atcpGp\nvHf5Zdm1115LpUqVAGjSpAngTWsbi+YcdNBB6W9cASwReZ999gH86PKYMWPcOdY0btyY//73v4D/\neb755psBuP3229PR3JSw88nAgQPzFcVt1KhRrusGwB133AF4UTj77lqKgh3vqNpxxx1d1HHp0qUA\n9OzZM6URqSiwmSqbeRo6dKibijU33XQT4JeDCIsiUyIiIiIBxC5nKq+PP/6Yww47DPCXl9sdSKIG\nDRoA8MUXX5T6vaI+N3zssccCXsSjV69eAFStWhWAZMd55cqVgH83/f+fV+I8Dfvb2l2rvS74UYsf\nf/yxWH2whPWlS5fmu1OcPn064C9CKI10H8Nhw4YBcMMNN/DKK68AcOmllwKFJ+IHkanPaY8ePXjm\nmWcAePTRRwE477zzUv02QOb62KFDB3d+6dChA+AVPswbdUxk0YDVq1cDxc83Citn6rjjjnORqaef\nfhrAnS8KYhEou8v/+uuvAdh3331L0wQg/cdw4MCBANx11135HsvOznafXVu0lBjhsONrn2f7fBcl\nU5/TMWPGcMUVVwDQsGFDoOwtBmnTpo07lq1atbK2FPj8Rx55pNSzMMXpY+ym+fIaPny4W5lgq1CS\niXpYtjQsjHvIIYcA0LJly3zPsSTJxx57zNXhsmTnzZs3p6Qda9asyfVvECeffDKQe6o2Ozsb8AdT\ncWBJvPaZ/Oqrr7j66quB8AZRmWZTQeBNKQAMHjy42APpqKhTp477jljFaFO1alWXjG0X2A8//JBm\nzZoV+HrlynkTAPZ7mVahQgU3sHvyySeL9TvPPvss4A+mdtxxRwCqVKnCn3/+GUIrU+fWW28FYNCg\nQe5nDz/8MODXWxo7dqz7b/vOzp07F/CS9e0x+ztE1Q477ABA79693QrEsAZRmWKLJ6ZPn+4CAXZ8\nZs6c6VInbOB7xhlnAN7gy8YBYdSd1DSfiIiISACxj0w9++yzbsm5JZdbpCbR8OHDATj99NPT17gQ\n1KhRA/CS6S644ALAT8r/8MMPAS9x0qY8//77b8BPzo+iSpUqMXHiRCD5tFDbtm0Bb0o36rp16wZA\n69atAT/s/Mwzz6QsEhhlFq2xO8CuXbty3333ZbJJxWbT5NOnT2fPPfcs8vk2Xffrr7+6u2WbGrKl\n9PXr13fPt1IfmfbWW2/RtGlToPh1hiw6bKya/9lnn+1qF0WVRQRtMc7XX3/tZjMSo6ZWSmDo0KGA\nv4hi48aNLroV9e/w9ddfD3i1/6yPZY1Fnpo0aeKu+VbyIdGqVasA/3tdv359F8mychGppMiUiIiI\nSACxj0ydc845LgE9WeK5yVswMa7+9a9/Ad4ebvfccw/gV7P966+/Mtau0ujYsSPgVV8+//zzcz22\nZcsWlzAal93Mq1WrxlFHHZX0sXXr1hWau3DllVcC5IqIpLIIarrkTQCNU66i3dUni0pZZGbw4MGu\nGrgVcAS/BIgdx8SIlJXysCrjmVaa6Iot3Pnss88Av8yDJTdHmeU5WXmcAw880JU9uOyyywAvF278\n+PGAXzHcIv4jRoxgypQpaW1zaXXu3BmARYsW8dFHH2W4NeGw2RagRKVl/vzzT3799dcwmgQoMiUi\nIiISSOwiU40bNwbghRdeALx57goViu7Giy++GGq7wmDFSAcPHuzuaq+66irAy3uw1SZRn8fPy5ax\n2nx3+fLl8z0nJyfH5Xlt27YtfY0LYNu2bW5PQlvBZcviFy5cmO/5troPYMCAAQC5iglee+21gB/l\nKKurADPN7ubbtGmT7zH7DNr3b9GiRYW+VmJEytjdc5h3xWHbsmULAFu3bs1wS0rOci0tonjggQe6\n8gfHHXcc4JVLyFuK5bbbbgNwMwBR1q5dO8D/DCfLGwZvayDwV79ZpDFOLC8zKyvLbfljq0sbNGjg\nZjnsXGz7vfbq1SvUc2jsBlOWQGb1TYozkAL/wmUXrTiwZciDBw929WBsABK3AVQiWzafbBBlKlWq\n5Cq02ybAL730EuANpC3BPko6dOjgpvlsEGUX48QLqS29Puqoo+jatWuu19i4cSPgLWe2qvA2TXHW\nWWe5+j6SOjZotZsX8Etb2AW1sEHUbrvt5qaQ2rdvn+uxxYsX8/LLL6e0vZlgS+7tomWKsz9dptkU\nbWIJB1so8NxzzwHehdmmqO+//37AW2YfF7bHp+1Z++WXX7rHbHAxbtw4dtttN8D/m1gqweTJk9PV\n1MBsijknJ4drrrkG8L/DNoAC73wJ6StnoWk+ERERkQBiF5my6T1LFh09enS+u6Vk6tSpE2q7wnDD\nDTcA3gg81YU2M+n5558H/Chjy5Yt3dLyZFq0aJHr31tuuYW7774b8PcUW7t2bWjtLYpVbU+sBv3D\nDz8AXtVd8KpfW4V4Kx7YrVs3F7GyiOO4ceMALyF23rx57r/jwkLw6dxZIahp06YBfjHAP/74g7PP\nPhvwpwgKc+mll7pK98amT3r27Fms14g628PPoqXGKqknqlmzplsUZGVNrLp4YtJ+uhUV1bUI4tix\nYwH49ttvQ29TqliZHPvcZmdnu8Ufto/tJZdc4lJDrJSAlfBYs2ZN0mMZRbbYY9ddd3XXhMTzjpX7\nSHcpEkWmRERERAKIXWTKWJHHVatWUa1atVyPVahQgUmTJgHedgdxZdtztGjRwvXHloW+/vrrGWtX\nUJaPYkuQ99prLxcVsGKA3bt3d3dbefc9K1eunJsrtznyTp06ZWxHdEv+TNzzy7a+sT3NatWq5e54\n7a5ww4YNLhfOchdsqfnUqVNdPsqbb74JFH1nHQVxikgZy5uxf4vrlFNOAeDmm292P7MEbStkGeeo\nlOVJ1a9fnyOOOCLpc6ZOneqKBduWOtWrV3flJewzbAUx85ZASQfLzbR8xmT7KM6ZM8cdzzix/CHL\nHU5cIGAtR4t3AAAJHklEQVTHwyJOiblDTz31FOCfu2644YbYRKasz23atHELPqw/4M98pDsyFfuN\njgt4H1ex1k50tm9cp06dSn1RCnNDx9atW7NkyRLA3zeoevXqgLdBp9WXslpSrVu3DqX+Ulibq5bG\nOeecA/iLBmwVYDJDhgxxU36FCeMYDh48GPDq0Zi8CyMWLVrkqqKbTp06sWDBAsBfhZNYD82mMkta\nbypTG4/uueee+b5bHTt2dH1MpShsOm6rTBPPoVa3yKYOgwjru1i5cmX22GMPwL/g2ufPVrmBn2xu\nF69ktm3blq9+2kMPPeQWj9g0ttXaSpSuY2hTjN27dy/wOXPmzMm3GCQVwu5jp06dAP/m2qryL1++\n3KUf2HSfTY8lsucvXbq00AVBhcnkd9FqS1pF85ycHNenlStXpux9itNHTfOJiIiIBBDbab7CVKpU\nKVfoHfw6KVGpWWQJ8bNnzwa8qS4r3/Doo48CfgXeSZMmucjULrvsAvhRq7LsscceA/wQ7htvvAHk\nX34O/jRCJtg0c1ZWVr6KvFYGYZ999nHTC7aMd8GCBS4p/fHHH3evYc+xyFScWUS4LBk5ciSQv5YY\nEEoULijbk86i9aeccoqr15eMlRCwKbqtW7fmi7TOmDED8Kb5olhpu27duvTt2xeAHj16AH4E8aOP\nPnKRDHuOReriLrGOUnHKVhS2K0McWD2tZN/FdFNkSkRERCSAMhmZGj58eL6fWSG2qIzE7W7OEuQH\nDx7sIlJ52X5f4Ednoli0MiyWVGmJrskiU6mcHy+tnJycAhOwt2/f7h479NBDAa+gp+WlWJE9S5L9\n448/wm6ulEKlSpVo2rQp4N8F5+TkuO+o7VQfJVZ80qp9Z2dnu5wm+9xZRDU7O9vlN9m5cvny5S6C\nanv02QKQqO4H2qlTJ7f4w1gR5EmTJnHqqacCfmQq3cnKqZJYDbw0OnToAMSj+GoytiDLvovz5893\nOcfppsiUiIiISACRjEzVqFED8AuKPfHEE65oZWEsD6lfv375HrPlklFhpR3sbmnixInuZ8buchs2\nbOhWSVkhz8StEeKgTp06XHzxxQBuFaKVBSiKrTKxQoCJLGpl+25lgt3VDxo0iG7dugH+6ijLmbKV\nNQDnnXce4N1N2mony2cpa/vv2fL6uLOtZnr37u0iPOaJJ55w+X2ZzNkoiO09aFGo7t27u/3qkrH8\nqNGjRwNQr149VxTXtoKKakTK9p5LPJfaKj2L6teuXTtfTm2y1YZxYNHukq7Kr1ixIuAVnAW/uHCc\nNG7cmAsvvBDw9xqcMmVKxo5lJAdT9kWwuh+NGjVyFaXtYrN69WrAqzNkIWirip5YW8oqStvvR8Wo\nUaMAPzG+adOmHHvssbmeY/sozZkzxy2Pt37HRe3atQGv1oklC1q/imI1p2xKIXHZtrG9qBJLCqSb\nHcNNmza5i67t5VbYSS6xztQrr7wScisz48QTT4zFRrEFsUGw1Q07/fTT3WO2YGTSpEmRHEQZ+wyu\nX78eKDxFYMcdd3SlBKwOXHZ2ttvnLIrJ5olsoFu1alW3GMAW+dgA4uSTT3a7Ctj0mF2M48amJ3/8\n8UfA36NvypQpSZ9vfwN73Crb9+nTJ8xmppQdu7lz51KvXj3AL0+Trn34ktE0n4iIiEgAkYxM2Z2s\n7XXWtm1b5s+fD/jhWBuRH3XUUbmmUMC7E7OpJNuXKKp72llV7LLKlvdbVAr842r7dFkSIfjLuK+/\n/noXkcp7fLOyslzC5MCBA0NqefFZYnyvXr1cm226IdHDDz8MeAXyAJYsWRLJpfSl9fPPP7s96Qor\n9BgnduebGJGycg95p+WjyhZn2JTztGnTXCqFlQiwxPJBgwa5/ffee+89APr371/otGCUJC4KsIic\nRWMs6XzChAmsW7cO8Es8FBTJiTqLSFm5DpuJAb+0zH777Qd4aRJDhw4F/OuhTQFbukEcWHHmevXq\nufSfxH5niiJTIiIiIgFEejsZG22uXr2ae++9t9i/9/vvv7s7r1SKwhYWYUv1FhaWdH7ffffle8y2\nz0ksA2Dz4bb8PJm//vqL0047DfD3rSsuHUNPWH18//33AX/PxNmzZ8dymw4ramkFVm0J/cqVKznh\nhBOA8PdKTPV3cdiwYYC3PZEVOczrxRdfdGVkwt6rLYxjaOeZiy66yOXPWO6llR0BP0r10ksvleTl\nSyzd38XLL78cgDFjxuRb/LFhwwYXTbXyQakoI5CuPlpOsS342b59u8sRy1ssOdWK1ccoD6bMDjvs\nkG86xy62vXr1cj+zi/IxxxwTSqKkLsQl758lOI4cOdIlsZaUrdizKcPnnnvOTUGUlI6hJ6w+WqK2\nrbKZP39+0oUDQYXdR5siOfPMM3P9fMCAAWmbEorSPplhCOMYXnXVVUDuaR9LMrcdJSZPnswdd9wB\n5E4xCIPON54gfbRriKVTWG2+3r1788ILL5T2ZUtEe/OJiIiIhCySCeh5ZWdnM2bMmKSPnX322Wlu\njZSELRjo27cvL774IuCXOLDE2MRpIFs4ADBv3rxcP4tLEuz/shEjRgD+bu7FrSUWJQcddFCu8irg\nJW2D/5mUaLJFHpUqVXL7mX7wwQcA7vxz1113ZaZxUmKVK1d2U+2WAvLcc88BpC0qVVyKTImIiIgE\nEIucqajQ/HfZ7x+oj3EQZh9Hjx7t7oYtyfzEE08E/HIe6aDvovoYB2H2sX///kyaNAmAxYsXA34i\nenZ2dmleslSUMyUiIiISMkWmSkB3GWW/f6A+xkGYfezUqRNz584FoEePHkD4S6+T0XdRfYyDMPrY\nqlUrwMuPeuCBBwB/pfB3331X4jYGVWZKI0SFvhhlv3+gPsaB+lj2+wfqYxyojx5N84mIiIgEkNbI\nlIiIiEhZo8iUiIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGUiIiI\nSAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGU\niIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgEoMGUiIiISAAaTImIiIgE\noMGUiIiISAD/D2VmfeQeqcmwAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10bdc67f0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# To check MNIST data\n",
    "print(\"x_train.shape = \"+str(x_train.shape))\n",
    "print(\"y_train.shape = \"+str(y_train.shape))\n",
    "fig = plt.figure(figsize=(10, 2))\n",
    "for i in range(20):\n",
    "    ax1 = fig.add_subplot(2, 10, i+1)\n",
    "    ax1.imshow(x_train[i], cmap='gray');\n",
    "    ax1.axis('off')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(In supervised learning) Every (good) dataset consists of a training set and a test set.\n",
    "\n",
    "The training data set consists of data points and their desired outputs.\n",
    "\n",
    "In this case, the data points are grayscale images of hand-written numbers, and their desired outputs are the numbers that have been drawn.\n",
    "\n",
    "The test data set consists of data points whose outputs need to be found."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us implement the following neural network to classify MNIST data:\n",
    "<center>![MNIST NN](images/digitsNN.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initialize network\n",
    "\n",
    "MNIST dataset has images of size 28x28. So the input layer to our network must have $28*28=784$ neurons.\n",
    "\n",
    "Since we are tring to classify whether the image is that of 0 or 1 or 2 ... or 9, we need to have 10 output neurons, each catering to the probability of one number among 0-9.\n",
    "\n",
    "Let our hidden layer (as shown in the diagram) have 15 neurons."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before initializing the network though, let's ensure our inputs and outputs are appropriate for the task at hand."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Are our inputs in the right format and shape?\n",
    "\n",
    "Remember that we give inputs as np.arrays of $n{\\times}784$ dimensions, $n$ being the number of data points we want to input to the network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is ``x_train`` an np.array?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check type of x_train\n",
    "type(x_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yup, ``x_train`` is an np.array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is ``x_train`` in the shape required by the network?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(60000, 28, 28)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check shape of x_train\n",
    "x_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clearly not.\n",
    "\n",
    "We need to reshape this matrix to $60000{\\times}784$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(60000, 784)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Reshaping x_train and x_test for our network with 784 inputs neurons\n",
    "x_train = np.reshape(x_train, (len(x_train), 784))\n",
    "x_test = np.reshape(x_test, (len(x_test), 784))\n",
    "\n",
    "# Check the dimensions\n",
    "x_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now our input is in the right format and shape."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Are our inputs normalized?\n",
    "\n",
    "Remember that we had decided to limit the range of values for the input to 0-1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Are all the values of ``x_train`` between 0 and 1?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Values in x_train lie between 0 and 255\n"
     ]
    }
   ],
   "source": [
    "# Check range of values of x_train\n",
    "print(\"Values in x_train lie between \"+str(np.min(x_train))+\" and \"+str(np.max(np.max(x_train))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our inputs are images, their values range from 0 to 255. We need to bring them down to 0-1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Normalize x_train\n",
    "x_train = x_train / 255.0\n",
    "x_test = x_test / 255.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Values in x_train lie between 0.0 and 1.0\n"
     ]
    }
   ],
   "source": [
    "# Check range of values of x_train\n",
    "print(\"Values in x_train lie between \"+str(np.min(x_train))+\" and \"+str(np.max(np.max(x_train))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perfect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Are our outputs in the right format and shape?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is ``y_train`` an np.array?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check type of y_train\n",
    "type(y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yup, ``y_train`` is an np.array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember that we have 10 neurons in the output layer. That means our output needs to be of ${n{\\times}10}$ dimensions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is the shape of ``y_train`` $n{\\times}10$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(60000,)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check shape of y_train\n",
    "y_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nope, ``y_train`` is of shape $60000{\\times}1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What are its values like?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "0\n",
      "4\n",
      "1\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(y_train[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So ``y_train`` carries the numbers of the digits the images represent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to make a new binary array of $60000{\\times}10$ and insert a 1 in the column corresponding to the number of the digit its image shows.\n",
    "\n",
    "For example, the first row of our new y_train should look like $\\left[\\begin{array}{c}0&0&0&0&0&1&0&0&0&0\\end{array}\\right]$, since it represents 5. This is called one-hot encoding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Make new y_train of nx10 elements\n",
    "new_y_train = np.zeros((len(y_train), 10))\n",
    "for i in range(len(y_train)):\n",
    "    new_y_train[i, y_train[i]] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Make new y_test of nx10 elements\n",
    "new_y_test = np.zeros((len(y_test), 10))\n",
    "for i in range(len(y_test)):\n",
    "    new_y_test[i, y_test[i]] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.  0.  0.  0.  0.  1.  0.  0.  0.  0.]\n",
      "[ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.]\n"
     ]
    }
   ],
   "source": [
    "# Check first row of y_train\n",
    "print(new_y_train[0])\n",
    "print(new_y_test[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that new_y_train is correctly shaped and formatted, let us reassign the name y_train to the matrix new_y_train."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Reassign the name \"y_train\" to new_y_train\n",
    "y_train = new_y_train\n",
    "y_test = new_y_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initialize the network"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Initialize network\n",
    "layers = [784, 15, 10]\n",
    "weights = initializeWeights(layers)\n",
    "\n",
    "# Take backup of weights to be used later for comparison\n",
    "initialWeights = [np.array(w) for w in weights]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nprint(\"weights:\")\\nfor i in range(len(weights)):\\n    print(i+1); print(weights[i].shape); print(weights[i])\\n'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Please don't print the weights\n",
    "# There are 15*784=11760 weights in the first layer,\n",
    "# + 10*15=150 weights in the second layer\n",
    "'''\n",
    "print(\"weights:\")\n",
    "for i in range(len(weights)):\n",
    "    print(i+1); print(weights[i].shape); print(weights[i])\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train the network\n",
    "\n",
    "Use the proper inputs ``x_train`` and ``y_train`` to train your neural network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How many iterations do you want to perform? How much should be the learning rate? Should it be adaptive? How many neurons per layer?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember that there are 60,000 images in the training set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 1 of 1\n",
      "Cost: 1.97857726345\n",
      "Time: 3.7738959789276123 seconds\n"
     ]
    }
   ],
   "source": [
    "# Train the network using Gradient Descent\n",
    "# Let's check how much time it takes for 1 iteration\n",
    "\n",
    "# Set options\n",
    "nIterations = 1\n",
    "learningRate = 1.0\n",
    "\n",
    "# Start time\n",
    "start = time.time()\n",
    "\n",
    "# Train\n",
    "trainUsingGD(weights, x_train, y_train, nIterations, learningRate)\n",
    "\n",
    "# End time\n",
    "end = time.time()\n",
    "\n",
    "print(\"Time: \"+str(end - start)+\" seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "See how it takes SO LONG for just one iteration?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem: Batch Gradient Descent computes error, delta, etc. over the entire input data set**\n",
    "\n",
    "Solution: Don't change weights over the entire data set, repeatedly use a randomly sampled subset of the data set.\n",
    "\n",
    "This is called the Monte Carlo method, and in this case it has been developed into Stochastic Gradient Descent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mini-batch Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We shall define a $minibatchSize$ lesser than the number of data points input to the network ($n$). Say $minibatchSize = 100$.\n",
    "\n",
    "**Mini-batch GD**:\n",
    "\n",
    "For every epoch:\n",
    "- randomly group the input data set into mini-batches of ($minibatchSize=$) 100 images:\n",
    "    - randomly shuffle the entire data set\n",
    "    - consider every 100 images as one mini-batch - so there are ``int(n/minibatchSize)`` number of mini-batches\n",
    "- use gradient descent on every mini-batch to update weights\n",
    "- Repeat.\n",
    "\n",
    "If $minibatchSize=n$, this is the same as Batch Gradient Descent.\n",
    "\n",
    "If $minibatchSize=1$, i.e. we update the weights after backpropagating for only one image, it is called **Stochastic Grdient Descent**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, at every iteration we are using gradient descent on only $minibatchSize$ number of images.\n",
    "\n",
    "Mathematical proofs exist on why this works better than gradient descent, under some assumptions (like stationarity, which holds true for our purposes)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's code Mini-batch Gradient Descent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TRAINING USING MINI-BATCH GRADIENT DESCENT\n",
    "# Default learning rate = 1.0\n",
    "def trainUsingMinibatchGD(weights, X, Y, minibatchSize, nEpochs, learningRate=1.0):\n",
    "    # For nIterations number of iterations:\n",
    "    for i in range(nEpochs):\n",
    "        # clear output\n",
    "        #clear_output()\n",
    "        print(\"Epoch \"+str(i+1)+\" of \"+str(nEpochs))\n",
    "        \n",
    "        # Make a list of all the indices\n",
    "        fullIdx = list(range(len(Y)))\n",
    "        \n",
    "        # Shuffle the full index\n",
    "        np.random.shuffle(fullIdx)\n",
    "        \n",
    "        # Count number of mini-batches\n",
    "        nOfMinibatches = int(len(X)/minibatchSize)\n",
    "        \n",
    "        # For each mini-batch\n",
    "        for m in range(nOfMinibatches):\n",
    "            # Compute the starting index of this mini-batch\n",
    "            startIdx = m*minibatchSize\n",
    "            \n",
    "            # Declare sampled inputs and outputs\n",
    "            xSample = X[fullIdx[startIdx:startIdx+minibatchSize]]\n",
    "            ySample = Y[fullIdx[startIdx:startIdx+minibatchSize]]\n",
    "\n",
    "            # Run backprop\n",
    "            backProp(weights, xSample, ySample, learningRate)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using MinibatchGD, training upto the same accuracy should take lesser time than GD."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Initialize network\n",
    "layers = [784, 30, 10]\n",
    "weights = initializeWeights(layers)\n",
    "\n",
    "# Take backup of weights to be used later for comparison\n",
    "initialWeights = [np.array(w) for w in weights]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5570 out of 60000 : 0.09283333333333334\n"
     ]
    }
   ],
   "source": [
    "# Evaluate initial weights on training data\n",
    "evaluate(weights, x_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "948 out of 10000 : 0.0948\n"
     ]
    }
   ],
   "source": [
    "# Evaluate initial weights on test data\n",
    "evaluate(weights, x_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Let's first use Batch Gradient Descent ($minibatchSize = size\\;of \\;full\\;input$) to evaluate the accuracy and time with one iteration "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 of 1\n",
      "Training accuracy:\n",
      "5889 out of 60000 : 0.09815\n",
      "Test accuracy:\n",
      "1012 out of 10000 : 0.1012\n",
      "Time: 2.8622570037841797 seconds\n"
     ]
    }
   ],
   "source": [
    "# Train the network ONCE using Batch Gradient Descent to check accuracy and time\n",
    "\n",
    "# Re-initialize weights\n",
    "weights = [np.array(w) for w in initialWeights]\n",
    "\n",
    "# Set options for batch gradient descent\n",
    "minibatchSize = len(y_train)\n",
    "nEpochs = 1\n",
    "learningRate = 3.0\n",
    "\n",
    "# Start time\n",
    "start = time.time()\n",
    "\n",
    "# Train\n",
    "trainUsingMinibatchGD(weights, x_train, y_train, minibatchSize, nEpochs, learningRate)\n",
    "\n",
    "# End time\n",
    "end = time.time()\n",
    "\n",
    "# Evaluate accuracy\n",
    "print(\"Training accuracy:\")\n",
    "evaluate(weights, x_train, y_train)\n",
    "print(\"Test accuracy:\")\n",
    "evaluate(weights, x_test, y_test)\n",
    "\n",
    "# Print time taken\n",
    "print(\"Time: \"+str(end-start)+\" seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Okay, let's check with Stochastic Gradient Descent, i.e. $minibatchSize = 1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 of 1\n",
      "Training accuracy:\n",
      "44816 out of 60000 : 0.7469333333333333\n",
      "Test accuracy:\n",
      "7539 out of 10000 : 0.7539\n",
      "Time: 21.746292114257812 seconds\n"
     ]
    }
   ],
   "source": [
    "# Train the network ONCE using Stochastic Gradient Descent to check accuracy and time\n",
    "\n",
    "# Re-initialize weights\n",
    "weights = [np.array(w) for w in initialWeights]\n",
    "\n",
    "# Set options of stochastic gradient descent\n",
    "minibatchSize = 1\n",
    "nEpochs = 1\n",
    "learningRate = 3.0\n",
    "\n",
    "# Start time\n",
    "start = time.time()\n",
    "\n",
    "# Train\n",
    "trainUsingMinibatchGD(weights, x_train, y_train, minibatchSize, nEpochs, learningRate)\n",
    "\n",
    "# End time\n",
    "end = time.time()\n",
    "\n",
    "# Evaluate accuracy\n",
    "print(\"Training accuracy:\")\n",
    "evaluate(weights, x_train, y_train)\n",
    "print(\"Test accuracy:\")\n",
    "evaluate(weights, x_test, y_test)\n",
    "\n",
    "# Print time taken\n",
    "print(\"Time: \"+str(end-start)+\" seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stochastic Gradient Descent took more time, but gave much better accuracy in just 1 epoch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Let's now check for Mini-batch Gradient Descent, with $minibatchSize = $ (say) $10$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 of 1\n",
      "Training accuracy:\n",
      "52428 out of 60000 : 0.8738\n",
      "Test accuracy:\n",
      "8752 out of 10000 : 0.8752\n",
      "Time: 4.0647711753845215 seconds\n"
     ]
    }
   ],
   "source": [
    "# Train the network ONCE using Mini-batch Gradient Descent to check accuracy and time\n",
    "\n",
    "# Re-initialize weights\n",
    "weights = [np.array(w) for w in initialWeights]\n",
    "\n",
    "# Set options of mini-batch gradient descent\n",
    "minibatchSize = 10\n",
    "nEpochs = 1\n",
    "learningRate = 3.0\n",
    "\n",
    "# Start time\n",
    "start = time.time()\n",
    "\n",
    "# Train\n",
    "trainUsingMinibatchGD(weights, x_train, y_train, minibatchSize, nEpochs, learningRate)\n",
    "\n",
    "# End time\n",
    "end = time.time()\n",
    "\n",
    "# Evaluate accuracy\n",
    "print(\"Training accuracy:\")\n",
    "evaluate(weights, x_train, y_train)\n",
    "print(\"Test accuracy:\")\n",
    "evaluate(weights, x_test, y_test)\n",
    "\n",
    "# Print time taken\n",
    "print(\"Time: \"+str(end-start)+\" seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, (in 1 epoch) Mini-batch Gradient descent gives comparable accuracy to Stochastic Gradient Descent, which is much better than the accuracy given by Batch Gradient Descent, in much lesser time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classifying MNIST data set\n",
    "\n",
    "Let us try to classify the MNIST data set up to more than 99%. This means deciding the number of layers, size of each layer, number of Epochs, the mini-batch size, and the learning (constant, for now).\n",
    "\n",
    "Let us try, $layers = [784$ (input layer, because each MNIST image is 28$x$28)$, 30$ (hidden layer)$, 10$ (outputs layer, one neuron for each digit)$], nEpochs = 30, minibatchSize = 10, learningRate = 3.0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 of 50\n",
      "Epoch 2 of 50\n",
      "Epoch 3 of 50\n",
      "Epoch 4 of 50\n",
      "Epoch 5 of 50\n",
      "Epoch 6 of 50\n",
      "Epoch 7 of 50\n",
      "Epoch 8 of 50\n",
      "Epoch 9 of 50\n",
      "Epoch 10 of 50\n",
      "Epoch 11 of 50\n",
      "Epoch 12 of 50\n",
      "Epoch 13 of 50\n",
      "Epoch 14 of 50\n",
      "Epoch 15 of 50\n",
      "Epoch 16 of 50\n",
      "Epoch 17 of 50\n",
      "Epoch 18 of 50\n",
      "Epoch 19 of 50\n",
      "Epoch 20 of 50\n",
      "Epoch 21 of 50\n",
      "Epoch 22 of 50\n",
      "Epoch 23 of 50\n",
      "Epoch 24 of 50\n",
      "Epoch 25 of 50\n",
      "Epoch 26 of 50\n",
      "Epoch 27 of 50\n",
      "Epoch 28 of 50\n",
      "Epoch 29 of 50\n",
      "Epoch 30 of 50\n",
      "Epoch 31 of 50\n",
      "Epoch 32 of 50\n",
      "Epoch 33 of 50\n",
      "Epoch 34 of 50\n",
      "Epoch 35 of 50\n",
      "Epoch 36 of 50\n",
      "Epoch 37 of 50\n",
      "Epoch 38 of 50\n",
      "Epoch 39 of 50\n",
      "Epoch 40 of 50\n",
      "Epoch 41 of 50\n",
      "Epoch 42 of 50\n",
      "Epoch 43 of 50\n",
      "Epoch 44 of 50\n",
      "Epoch 45 of 50\n",
      "Epoch 46 of 50\n",
      "Epoch 47 of 50\n",
      "Epoch 48 of 50\n",
      "Epoch 49 of 50\n",
      "Epoch 50 of 50\n",
      "Training accuracy:\n",
      "58180 out of 60000 : 0.9696666666666667\n",
      "Test accuracy:\n",
      "9397 out of 10000 : 0.9397\n"
     ]
    }
   ],
   "source": [
    "# TRAIN A NETWORK TO CLASSIFY MNIST\n",
    "\n",
    "# Initialize network\n",
    "layers = [784, 30, 10]\n",
    "weights = initializeWeights(layers)\n",
    "\n",
    "# Take backup of weights to be used later for comparison\n",
    "initialWeights = [np.array(w) for w in weights]\n",
    "\n",
    "# Set options of mini-batch gradient descent\n",
    "minibatchSize = 10\n",
    "nEpochs = 50\n",
    "learningRate = 3.0\n",
    "\n",
    "# Train\n",
    "trainUsingMinibatchGD(weights, x_train, y_train, minibatchSize, nEpochs, learningRate)\n",
    "\n",
    "# Evaluate accuracy\n",
    "print(\"Training accuracy:\")\n",
    "evaluate(weights, x_train, y_train)\n",
    "print(\"Test accuracy:\")\n",
    "evaluate(weights, x_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About 93%-95%.. What if we increase the mini-batch size?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 of 10\n",
      "Epoch 2 of 10\n",
      "Epoch 3 of 10\n",
      "Epoch 4 of 10\n",
      "Epoch 5 of 10\n",
      "Epoch 6 of 10\n",
      "Epoch 7 of 10\n",
      "Epoch 8 of 10\n",
      "Epoch 9 of 10\n",
      "Epoch 10 of 10\n",
      "Training accuracy:\n",
      "53245 out of 60000 : 0.8874166666666666\n",
      "Test accuracy:\n",
      "8846 out of 10000 : 0.8846\n"
     ]
    }
   ],
   "source": [
    "# TRAIN A NETWORK TO CLASSIFY MNIST\n",
    "\n",
    "# Initialize network\n",
    "layers = [784, 10, 10, 10]\n",
    "weights = initializeWeights(layers)\n",
    "\n",
    "# Take backup of weights to be used later for comparison\n",
    "initialWeights = [np.array(w) for w in weights]\n",
    "\n",
    "# Set options of mini-batch gradient descent\n",
    "minibatchSize = 10\n",
    "nEpochs = 30\n",
    "learningRate = 3.0\n",
    "\n",
    "# Train\n",
    "trainUsingMinibatchGD(weights, x_train, y_train, minibatchSize, nEpochs, learningRate)\n",
    "\n",
    "# Evaluate accuracy\n",
    "print(\"Training accuracy:\")\n",
    "evaluate(weights, x_train, y_train)\n",
    "print(\"Test accuracy:\")\n",
    "evaluate(weights, x_test, y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Coming up next\n",
    "\n",
    "In the next tutorial, we shall see the different types of optimizations that can be done in gradient descent, and compare their performances."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}