exercise_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DATA20001 Deep Learning - Exercise 2\n",
    "\n",
    "**Due Tuesday November 14, before 12:00 PM (noon)**\n",
    "\n",
    "In this first exercise we are going to write our own simple feedforward neural network using just Python and numpy (the standard numeric library for Python). In future exercises we'll use [Keras](https://keras.io/), which is a high-level neural networks library that does a lot of things automatically. Still, it's very useful to at least once do it \"by hand\" to understand how neural networks really work.\n",
    "\n",
    "Please read the explanations below carefully, and read the existing code.  <span style=\"background-color: yellow\">Places where you have to fill in your own code (this is the exercise part!) are mentioned in the text with a yellow background like this.</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2.1. Single neuron network (2 points)\n",
    "\n",
    "In this first exercise we're implementing just a simple neuron, or *perceptron*, as visualised below.  We'll have just three inputs and one output neuron, and will skip the bias for now.\n",
    "\n",
    "![Perceptron](figs/perceptron.png)\n",
    "\n",
    "Notice how the perceptron is basically just performing a sum of the individual inputs multiplied by the corresponding weights mapped through an activation function $f(\\cdot)$.  This can also be expressed as a dot product of the weight vector $\\textbf{w}$ and the input vector $\\textbf{x}$. Thus: $\\hat{y}=f(\\textbf{w}^T \\textbf{x})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll start the Python program by importing the libraries we're going to need.\n",
    "\n",
    "*You need to select and run each field of Python code to run it. You can run it by clicking the \"Run\" button above or pressing Shift-Enter on the keyboard. If you make changes in the code you can just rerun that part.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training data\n",
    "\n",
    "Next, we'll define our very simple dataset and the desired target values.  Below, each row is a single example: the first three columns the input and the last column the desired output.\n",
    "\n",
    "    0 0 1  0  \n",
    "    0 1 1  0  \n",
    "    1 0 1  1  \n",
    "    1 1 1  1  \n",
    "\n",
    "You might notice that our desired outputs are equal to the first column of the input.  We're not \"telling\" our network that, however.  Instead we'll see if it can learn that just from the data.\n",
    "\n",
    "Now let's construct this as the `X` and `y_target` matrices in Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Our input data is a matrix, each row is one input sample\n",
    "X = np.array([[0,0,1],\n",
    "              [0,1,1],\n",
    "              [1,0,1],\n",
    "              [1,1,1]])\n",
    "    \n",
    "# The desired output as a column vector in 2-D array format (.T means transpose)\n",
    "y = np.array([[0,0,1,1]]).T\n",
    "\n",
    "print('X=',X)\n",
    "print('y=',y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Activation function\n",
    "\n",
    "Next, we need to define the activation function $f(\\cdot)$.\n",
    "\n",
    "<span style=\"background-color: yellow\">Write the code for the sigmoid function below.</span>\n",
    "\n",
    "**Hint:** you can use the [mathematical functions from numpy](https://docs.scipy.org/doc/numpy/reference/routines.math.html) simply by prefixing with `np.`, e.g., `np.sin(x)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define f() as the sigmoid function\n",
    "def f(x):\n",
    "    return "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will use the sigmoid function for the exercise, but let's also plot some other common choices for the activation function. Feel free to experiment with the others as well later in the exercise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.arange(-4,4,.01)\n",
    "plt.figure()\n",
    "plt.plot(x, np.maximum(x,0), label='ReLu')\n",
    "plt.plot(x, f(x), label='sigmoid')\n",
    "plt.plot(x, np.tanh(x), label='tanh')\n",
    "plt.axis([-4, 4, -1.1, 1.5])\n",
    "plt.title('Activation functions')\n",
    "l = plt.legend()\n",
    "\n",
    "# Delete temporary variables, so not to cause any confusion later :-)\n",
    "del x, l"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialise weights\n",
    "\n",
    "We'll initialise our weights randomly, so that their mean is zero (it's good to not have them biased in any direction)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(42)\n",
    "\n",
    "# initialize weights randomly with mean 0\n",
    "w = 2*np.random.random((3,1)) - 1\n",
    "\n",
    "print('w=', w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Forward propagation\n",
    "\n",
    "Now let's try one round of forward propagation.  This means taking an input sample and moving it forward through the network, finally calculating the output of the network.\n",
    "\n",
    "Remember that for our single neuron this is simply $\\hat{y} = f(\\mathbf{w}^T \\mathbf{x})$, where $\\mathbf{x}$ is one input vector.\n",
    "\n",
    "In our program we've put all input vectors as rows of the matrix `X`, we can access the first row by `X[0]`. Let's store it in the variable `X0` for easier access. We'll use `reshape` to make sure it's expressed as a column vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X0=np.reshape(X[0], (3,1))\n",
    "print(X0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output for the first input can then be calculated according to the formula given above. For the multiplication we use [numpy's `dot` function](https://docs.scipy.org/doc/numpy/reference/generated/numpy.dot.html) as it performs matrix multiplication when given 2-D arrays."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_out = f(np.dot(w.T, X0))\n",
    "\n",
    "print('y_out=', y_out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our desired result is stored in `y[0]`.  If you check back, you can see we defined it to be 0. You can see that our network is pretty far away from the right answer. This is why we need to backpropagate, to adjust the weights in the right direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Backpropagation\n",
    "\n",
    "The next step is to update the weights by propagating the error backwards in the network.  Exactly how this is done depends on the activation function, or more specifically its derivative. (The ReLU and sigmoid cases were shown in the first week's lectures!)\n",
    "\n",
    "Recall that the weight update is given as $\\Delta w_{ji} = -\\epsilon \\delta_j h_i$. Here, our network has only one layer, so $h_i$ is just the input, i.e., $h_i=x_i$, and a single output neuron so there is no need for index $j$. \n",
    "\n",
    "In matrix form we can calculate this in one go for all the weights:\n",
    "\n",
    "$$\\Delta \\textbf{w} = -\\epsilon \\delta \\textbf{x}_0$$\n",
    "\n",
    "where $\\textbf{x}_0$ is our first input sample in variable `X0`.\n",
    "\n",
    "Below you can find the same formula in Python code, except that <span style=\"background-color: yellow\">you need to fill in the Python code to calculate the gradient term $\\delta$.</span>\n",
    "\n",
    "Recall that $y$ is the desired output, i.e. `y[0]` in the Python code, and $\\hat{y}$ is `y_out` here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# epsilon determines the step size in the gradient descent, you can experiment with different values if you want\n",
    "eps = 0.5 \n",
    "\n",
    "# Fill in the code for the gradient term\n",
    "grad = \n",
    "\n",
    "# Calculate the weight update\n",
    "w_delta = -eps * grad * X0\n",
    "\n",
    "print(w_delta)\n",
    "\n",
    "# Update the weight\n",
    "w += w_delta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try a forward propagation again with the same input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_out=f(np.dot(w.T, X0))\n",
    "\n",
    "print('y_out=', y_out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should notice that the result has moved (very slightly) towards the correct answer (that is zero).\n",
    "\n",
    "Now what is needed is more iterations!  But first, we'll discuss batch training...\n",
    "\n",
    "\n",
    "### Batch training\n",
    "\n",
    "With real-world data it is very slow to handle each example one-by-one like we did above.  Instead one typically uses so called mini batches of several input examples at once.  We'll demonstrate it here just by using the full input matrix `X` at once in one big batch.\n",
    "\n",
    "As each input example is one row in $\\textbf{X}$, instead of a single column vector as before, the forward propagation step looks a bit different mathematically: $\\hat{\\textbf{y}} = f(\\textbf{X}\\textbf{w})$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_out = f(np.dot(X, w))\n",
    "print(y_out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we'll get the corresponding output (each value in `y_out`) for each input (each row in `X`) in a single matrix multiplication.  The error and weight updates can similarly all be calculated in a single go using matrix multiplications similar to the steps we did a above with single vectors.\n",
    "\n",
    "In this exercise we'll stick to just doing one sample at a time, as the batch mode makes it a bit more complicated to understand.  Of course, if you want you can implement everything here in batch mode as well as an additional exercise :-)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training iterations\n",
    "\n",
    "Let's finally do some real training of our network. Remember that each time we'll first calculate the outputs with our given input (forward propagation), then we'll check how much the output differ from the desired output and propagate the error back (backward propagation).  We'll do this for each sample data point, and then iterate this over and over again using a for loop.\n",
    "\n",
    "Below is most of the code needed, <span style=\"background-color: yellow\">you just need to fill in how to calculate the gradient $\\delta$</span>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# For training we need to iterate over the training set several times\n",
    "# You can adjust how many times by changing the value of N\n",
    "num_iters = 1000\n",
    "\n",
    "eps = 0.5\n",
    "\n",
    "# We'll also calculate the mean square error (MSE) in every round so we can see how it develops,\n",
    "# mse is just an array to store these for each round\n",
    "mse = np.zeros(num_iters)\n",
    "\n",
    "# For-loop for the iterations\n",
    "for it in range(num_iters):\n",
    "    \n",
    "    # For-loop going over each sample in X\n",
    "    for n in range(len(X)):\n",
    "        # Extract the n:th sample and the corresponding desired output\n",
    "        x_n = np.reshape(X[n], (3,1))\n",
    "        y_n = y[n]\n",
    "        \n",
    "        # Forward propagation\n",
    "        y_out = f(np.dot(w.T, x_n))\n",
    "\n",
    "        # Let's keep track of the sum of squared errors\n",
    "        mse[it] += np.square(y_out - y_n)\n",
    "    \n",
    "        # Fill in the code for the gradient term\n",
    "        grad = \n",
    "    \n",
    "        # Calculate the weight update\n",
    "        w_delta = -eps * grad * x_n\n",
    "\n",
    "        # Update the weights\n",
    "        w += w_delta\n",
    "\n",
    "    # Divide by the number of elements to get the mean of the squared errors\n",
    "    mse[it] /= len(X)\n",
    "\n",
    "y_out = f(np.dot(X, w))\n",
    "print(\"Output after training, y_out\")\n",
    "print(y_out)\n",
    "print(\"Desired output, y\")\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here you should see that the output of the network after training is pretty close to the desired output, i.e., the two first ones are close to zero, and the two last ones close to one.\n",
    "\n",
    "Finally, let's plot the mean squared error over time (iterations of the training)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure()\n",
    "plt.plot(range(num_iters), mse, label=\"MSE\")\n",
    "l = plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see the error going down pretty quickly in the beginning and then slowing down."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2.2. Two layer network (2 points)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try a slightly more difficult example. We'll use the same input data, but a different desired output.\n",
    "\n",
    "**Note:** if you haven't just done Exercise 2.1, you'll need to go back to the first Python box and run the import statements again to get numpy loaded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.array([[0,0,1],\n",
    "              [0,1,1],\n",
    "              [1,0,1],\n",
    "              [1,1,1]])\n",
    "    \n",
    "y = np.array([[0,1,1,0]]).T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll reset the weights. <span style=\"background-color: yellow\">You also need to define the function `f()` again or reuse it from Exercise 2.1.</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's reset the weights first\n",
    "w = 2*np.random.random((3,1)) - 1\n",
    "\n",
    "# We'll use sigmoid again so you can call f() from above"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below is a copy of the single neuron network we created in the previous exercise minus the <span style=\"background-color: yellow\">gradient calculation that you have to fill in yourself</span>.  You copy your gradient formula from the previous exercise and try with the new data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_iters = 1000\n",
    "eps = 0.5\n",
    "\n",
    "for it in range(num_iters):\n",
    "    for n in range(len(X)):\n",
    "        x_n = np.reshape(X[n], (3,1))\n",
    "        y_n = y[n]\n",
    "        \n",
    "        # Forward propagation\n",
    "        y_out = f(np.dot(w.T, x_n))\n",
    "\n",
    "        # Fill in the code for the gradient term\n",
    "        grad = \n",
    "    \n",
    "        # Calculate the weight update\n",
    "        w_delta = -eps * grad * x_n\n",
    "\n",
    "        # Update the weights\n",
    "        w += w_delta\n",
    "\n",
    "# Now let's see the output for each input sample with the trained weights\n",
    "# Using batch mode we can do this in a single line\n",
    "y_out = f(np.dot(X, w))\n",
    "print(\"Output after training, y_out\")\n",
    "print(y_out)\n",
    "print(\"Desired output, y\")\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see the network is not able to solve the problem, it's not even close. You can try to increase the number of iterations, but it won't help. This is in fact just the XOR problem as discussed in the lectures (you'll notice that the last column of the input data is just ones, and thus irrelevant). You'll need a two layer network to solve it.\n",
    "\n",
    "Let's add a single hidden layer, for example with 4 hidden nodes (you can experiment with this number if you like).\n",
    "\n",
    "![Two layer network](figs/two_layer.png)\n",
    "\n",
    "The input to the network is $\\mathbf{x}$ as before.  The first hidden layer calculates $\\textbf{h} = f(\\textbf{U}^Tx)$, note that $\\textbf{U}$ is now a $3 \\times 4$ matrix.  The output layer calculates $\\hat{y} = f(\\textbf{w}^T\\textbf{h})$.\n",
    "\n",
    "We'll start by initialising the weights randomly again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(42)\n",
    "\n",
    "num_hidden = 4\n",
    "\n",
    "# initialize weights randomly with mean 0\n",
    "u = 2*np.random.random((3,num_hidden)) - 1\n",
    "w = 2*np.random.random((num_hidden,1)) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next you'll need to <span style=\"background-color: yellow\">fill in the missing parts for both the forward and backward propagation</span>.  Below we have provided a skeleton for doing the iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_iters = 2000\n",
    "eps = 0.5\n",
    "\n",
    "for it in range(num_iters):\n",
    "    for n in range(len(X)):\n",
    "        x_n = np.reshape(X[n], (3,1))\n",
    "        y_n = y[n]\n",
    "\n",
    "        # Calculate h\n",
    "        h = \n",
    "        \n",
    "        # Calculate y_out\n",
    "        y_out = \n",
    "        \n",
    "        # Calculate the gradient\n",
    "        grad = \n",
    "\n",
    "        w_delta = -eps * grad * h\n",
    "        \n",
    "        # Calculate the weight updates for u\n",
    "        # hint: you can do this with matrices, but it might easier to understand if you \n",
    "        # perform a for loop over i (hidden nodes) and k (input nodes) and calculate \n",
    "        # each u_ik update separately\n",
    "    \n",
    "        # Update the weights, note: it's important the w weights are updated at the end,\n",
    "        # the above calculation should be done with the old weights\n",
    "        w += w_delta\n",
    "    \n",
    "y_out = f(np.dot(f(np.dot(X, u)), w))\n",
    "print(\"Output after training, y_out\")\n",
    "print(y_out)\n",
    "print(\"Desired output, y\")\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see outputs very similar to the desired ones if you have succeeded."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2.3. Two-layer network with Keras (2 points)\n",
    "\n",
    "Finally, let's make the same network as in the previous exercise but using the Keras library.\n",
    "\n",
    "Below is all the setup and training code, you just need to <span style=\"background-color: yellow\">add the code that creates the two feed-forward layers (called fully connected or dense layers).</span> Remember to also include the sigmoid activation. You can find the [documentation of Keras online](https://keras.io/getting-started/sequential-model-guide/), in particular you might want to see the [documentation on Keras layers](https://keras.io/layers/core/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import the needed Keras libraries\n",
    "from keras.models import Sequential\n",
    "from keras.layers import Dense, Activation\n",
    "from keras import optimizers\n",
    "\n",
    "# Dataset, same as before\n",
    "X = np.array([[0,0,1],\n",
    "              [0,1,1],\n",
    "              [1,0,1],\n",
    "              [1,1,1]])\n",
    "    \n",
    "y = np.array([[0,1,1,0]]).T\n",
    "\n",
    "# Same parameters as before\n",
    "num_hidden = 4\n",
    "batch_size = 1\n",
    "num_iters = 2000\n",
    "\n",
    "# Setting up the neural network by adding each layer in sequence\n",
    "model = Sequential()\n",
    "\n",
    "# First, add the hidden layer including sigmoid activation here\n",
    "\n",
    "# Second, the output layer, also with a sigmoid\n",
    "\n",
    "# Here we use stochastic gradient descent with epsilon (i.e. the learning rate) = 0.5\n",
    "sgd = optimizers.SGD(lr=0.5)\n",
    "model.compile(loss='mean_squared_error', optimizer=sgd)\n",
    "\n",
    "# Finally, this line runs the actual training\n",
    "model.fit(X, y, epochs=num_iters, batch_size=1, verbose=1)\n",
    "\n",
    "# Check the output with the trained weights\n",
    "y_out = model.predict(X, batch_size=1)\n",
    "print(y_out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might not get exactly the same result as with our own network as the weights were initialised differently, and Keras only supports more advanced optimizers. (So the gradient descent isn't done exactly in the same way.)\n",
    "\n",
    "You probably noticed that Keras did a lot of things automatically that we had to do ourselves in the numpy examples above. <span style=\"background-color: yellow\">In particular, what things did Keras do automatically \"behind the scenes\" just for the few lines that you added yourself to create the network layers? Please write 1-3 sentences in the field below.</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write your short answer here. (Double-click the field to start writing.)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}