{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Deep XOR #\n", "\n", "The goal of this notebook is to illustrate, step by step, the modelling of an [XOR gate](https://en.wikipedia.org/wiki/Exclusive_or) using a simple neural network trained via gradient descent.\n", "\n", "This is basically a little exercise I decided to go through to have a better understanding of how neural networks work. Here you'll find the derivation of all necessary equations and their implementation in [numpy](http://www.numpy.org/). \n", "Hopefully it may help other practitioners too. Life is sharing (openly on github) :)\n", "\n", "(The whole thing is inspired by Section 6.2 of the absolutely fantastic [The Deep Learning Book](http://www.deeplearningbook.org/), and [this](http://cs231n.github.io/neural-networks-case-study/#net))" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np # That's all we need :)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Data ##\n", "\n", "We randomly generate a handful of examples to later train our model. \n", "There are only 4 different unique input combinations to XOR:\n", "* $0 \\oplus 0 = 0$\n", "* $0 \\oplus 1 = 1$\n", "* $1 \\oplus 0 = 1$\n", "* $1 \\oplus 1 = 0$\n", "\n", "Thus, $N$ observations randomly sampled from these 4 pairs of ones and zeroes are generated and stored in $X \\in \\mathbb{N}^{N \\times 2}$, and passed through the XOR operation to obtain the target set of labels $Y \\in \\mathbb{N}^{N \\times 2}$, which we encode as one-hot vectors." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def gen_data(N):\n", " \"\"\"Generates an XOR dataset using one-hot vector encoding.\n", " \n", " Parameters\n", " ----------\n", " N: int\n", " Number of observations to be generated.\n", " \n", " Returns\n", " -------\n", " X: np.ndarray((N, 2))\n", " Matrix containing an observation per row, representing the input\n", " to the XOR operation (observations).\n", " Y: np.ndarray((N, 2))\n", " Result of the XOR operation for each row, encoded with \n", " one-hot vector per row (targets).\n", " \"\"\"\n", " X = np.random.randint(0, 2, size=(N, 2))\n", " Y = np.zeros((N, 2))\n", " Y[np.arange(N), [int(np.logical_xor(x[0], x[1])) for x in X]] = 1\n", " return X, Y\n", "\n", "def xor_print(X, Y, N):\n", " \"\"\"Prints out an XOR dataset.\n", " \n", " Parameters\n", " ----------\n", " X: np.ndarray((N, 2))\n", " Observations.\n", " Y: np.ndarray((N, 2))\n", " Targets.\n", " N: int\n", " Number of observations to be printed.\n", " \"\"\"\n", " [print(str(x[0]) + ' XOR ' + str(x[1]) + ' = ' + str(np.argmax(y))) \n", " for x, y in zip(X[:N], Y[:N])]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Model ##\n", "\n", "To approximate the XOR function, which is non-linear, we need a non-linear model (see the bonus section at the end of this notebook if you're curious to know why).\n", "Since neural networks are so [cool](http://i.imgur.com/FNoToht.jpg), we design a feedforward neural network with a single hidden layer (ok, that's not too *deep*, but nowadays it seems almost impossible to write something interesting without this magic [word](https://cdn.meme.am/instances/500x/72561253.jpg) in it, hence the title of this notebook).\n", "\n", "The network has two output units $\\hat{y}_1$ and $\\hat{y}_2$, representing the likelihood of having a 0 or a 1, respectively, thus framing the problem as **classification**. The network diagram may look as follows:\n", "![Feedforward Neural Network2](./images/diagram_sm.png)\n", "\n", "Where the weights $W_1, W_2$ and basis $b_1, b_2$ are the coefficients to be learned, $\\mathbf{x} = \\{x_1, x_2\\}$ is the input, $\\mathbf{h} = \\{h_1, h_2\\}$ is the content of the hidden layer, and $\\mathbf{\\hat{y}} = \\{\\hat{y}_1, \\hat{y}_2\\}$ is the output of the network.\n", "\n", "Each layer is composed by a standard affine transformation plus its non-linear activation. We use a rectified linear unit (ReLU) $\\sigma$ for the activation of the hidden layer. Formally:\n", "\n", "$$\\mathbf{h} = \\sigma(\\mathbf{x}^T W_1 + b_1) = \\text{max}\\{\\mathbf{0}, \\mathbf{x}^T W_1 + b_1\\}$$\n", "\n", "For the output layer, we use the standard softmax function, which is the common activation used for classification problems. To simplify the math, we decompose the output layer into its linear equation and its activation:\n", "\n", "$$\\begin{equation}\n", "\\mathbf{z} = \\mathbf{h}^T W_2 + b_2 \\\\\n", "\\mathbf{\\hat{y}} = \\frac{e^\\mathbf{z}}{\\sum_j^2 e^{z_j}}\n", "\\end{equation}$$\n", "\n", "Note how the denominator of the softmax function sums only twice: once for each class (i.e., 0 and 1). This function essentially squashes the predictions and then normalizes them, thus yielding a set of proper probabilities.\n", "\n", "### Multiple Inputs ###\n", "\n", "If we focus on multiple observations $X = \\{\\mathbf{x}_1^T, \\mathbf{x}_2^T, \\ldots, \\mathbf{x}_N^T\\}$ instead of a single one $\\mathbf{x}_i$ we can rewrite the equations as follows:\n", "\n", "$$\\begin{equation}\n", "H = \\sigma(X W_1 + b_1) = \\text{max}\\{\\mathbf{0}, X W_1 + b_1\\} \\\\\n", "Z = H W_2 + b_2\\\\\n", "\\hat{Y} = \\frac{e^Z}{\\sum_j^2 e ^{\\mathbf{z}_j}}\n", "\\end{equation}$$\n", "\n", "where the biases $b_1, b_2$ are broadcasted across their respective inputs.\n", "\n", "We can now implement a function that computes a multiple input forward pass of the network using numpy:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def forward_pass(X, W1, W2, b1, b2):\n", " \"\"\"Computes a forward pass of the network. Once the coefficients are trained,\n", " this should compute the XOR on all x \\in X.\n", " \n", " Parameters\n", " ----------\n", " X: np.ndarray((N, 2))\n", " Inputs to the network.\n", " W1: np.ndarray((2, n_hidden))\n", " Set of weights for the first layer.\n", " W2: np.ndarray((n_hidden, 2))\n", " Set of weights for the second layer.\n", " b1: np.ndarray((1, n_hidden))\n", " Bias for the first layer.\n", " b2: np.ndarray((1, 2))\n", " Bias for the second layer.\n", " \n", " Returns\n", " -------\n", " H: np.ndarray((N, n_hidden))\n", " Content of the hidden layer.\n", " Y_est: np.ndarray((N, 2))\n", " Output of the network, the two columns represent the likelihood of\n", " having a 0 or a 1, in this order.\n", " \"\"\"\n", " # Hidden layer forward pass\n", " H = np.maximum(0, np.dot(X, W1) + b1) # ReLU activation\n", " \n", " # Second layer forward pass without activation\n", " linear = np.dot(H, W2) + b2\n", " \n", " # Softmax activation (output)\n", " Y_est = np.exp(linear) / np.sum(np.exp(linear), axis=1, keepdims=True) # [N x 2]\n", " return H, Y_est" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Initialization ##\n", "\n", "We can initialize our training coefficients randomly (there are [fancier](http://jmlr.org/proceedings/papers/v9/glorot10a/glorot10a.pdf) ways, but this problem is not that sophisticated after all). Notice how it would be straightforward to include more hidden units in our hidden layer by just changing the `n_hidden` argument. Feel free to play with this parameter, it seems to converge faster with 3 or 4 units. But for now, let's stick to our original model of 2 hidden units." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def init_coefficients(n_hidden=2):\n", " \"\"\"Initializes the training coefficients randomly.\n", " \n", " Parameters\n", " ----------\n", " n_hidden: int > 0\n", " Number of hidden layers.\n", " \n", " Returns\n", " -------\n", " W1: np.ndarray((2, n_hidden))\n", " Set of weights for the first layer.\n", " W2: np.ndarray((n_hidden, 2))\n", " Set of weights for the second layer.\n", " b1: np.ndarray((1, n_hidden))\n", " Bias for the first layer.\n", " b2: np.ndarray((1, 2))\n", " Bias for the second layer.\n", " \"\"\"\n", " # Input -> Hidden layer weights and bias\n", " W1 = np.random.random(size=(2, n_hidden))\n", " b1 = np.zeros((1, n_hidden)) # bias\n", "\n", " # Hidden -> Output layer weights and bias\n", " W2 = np.random.random(size=(n_hidden, 2))\n", " b2 = np.zeros((1, 2)) # bias\n", " \n", " return W1, b1, W2, b2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Loss Function ##\n", "\n", "Next step is to define an appropriate differentiable loss function that allows us to train our network. The loss should be small when we are obtaining successful results with the current parameters, and high otherwise.\n", "\n", "The **cross-entropy** function is commonly used in classification problems, since its derivative is quite simple and yet successfully captures the cost of the network for a given set of parameters.\n", "\n", "The average cross-entropy is defined as:\n", "\n", "$$L = - \\frac{1}{N}\\sum_{i}^N \\sum_{j}^2 y_{ij} \\log(\\hat{y}_{ij}) $$\n", "\n", "Let's quickly inspect this function. If we have a perfect prediction (e.g., $\\mathbf{y}_i = \\{0, 1\\}$ and $\\mathbf{\\hat{y}}_i = \\{0, 1\\}$), then $L_i$ is 0, as desired. Whereas, if we have completely wrong one (e.g., $\\mathbf{y}_i = \\{0, 1\\}$ and $\\mathbf{\\hat{y}}_i = \\{1, 0\\}$), then we get $L_i = \\infty$, also as required. Alrighten.\n", "\n", "We can now implement this function in numpy. To avoid the instability of computing $\\log(0)$, we can simply multiply each of the predicted results with the target value, and sum across them (one will be zero). This is essentially like \"selecting\" the likelihood of the correct class:\n", "\n", "$$L = - \\frac{1}{N}\\sum_{i}^N y_{ik} \\log(\\hat{y}_{ik}) + (1 - y_{ik}) \\log(\\hat{y}_{in}) = - \\frac{1}{N}\\sum_{i}^N \\log(\\hat{y}_{ik}) \\qquad\\text{where}\\qquad y_{ik} = 1$$\n", "\n", "And here its implementation:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def compute_loss(Y, Y_est):\n", " \"\"\"Computes the averate cross-entropy loss.\n", " \n", " Parameters\n", " ----------\n", " Y: np.ndarray((N, 2))\n", " Target labels (XOR correct results).\n", " Y_est: np.ndarray((N, 2))\n", " Estimated XOR values.\n", " \n", " Returns\n", " -------\n", " loss: float\n", " Loss value: the average cross-entropy.\n", " \"\"\"\n", " N = Y.shape[0]\n", " return - np.sum(np.log(np.sum(Y * Y_est, axis=1))) / float(N)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Training ##\n", "\n", "As it is common in neural networks, we use [gradient descent](https://en.wikipedia.org/wiki/Gradient_descent) to train our set of weights $W_1, W2$ and biases $b_1, b_2$.\n", "This method makes use of the partial derivates of the whole model to identify the steepest direction (the gradient) of each trainable variable in order to minimize, step by step, the given loss function $L$.\n", "\n", "The [chain-rule](http://www.sosmath.com/calculus/diff/der04/der04.html) formula will help us in this process, *backpropagating* the gradient from the output of the network to its input. So, let us begin.\n", "\n", "### Gradient of the output layer ###\n", "\n", "The ([fun](http://jokideo.com/wp-content/uploads/meme/2014/06/Reaction-Pic---not-funny.jpg)) derivative of our loss function with respect to the softmax output of our model is:\n", "\n", "$$\\begin{split}\n", "\\frac{\\partial L}{\\partial z_{ij}} & = \\frac{\\partial L}{\\partial \\hat{y}_{ij}} \\frac{\\partial \\hat{y}_{ij}}{\\partial z_{ij}} \\\\\n", "& = \\frac{\\partial}{\\partial\\hat{y}_{ij}} \\left( - \\sum_{j}^2 y_{ij} \\log(\\hat{y}_{ij}) \\right) \\frac{\\partial \\hat{y}_{ij}}{\\partial z_{ij}}\\\\\n", "& = - \\sum_{j}^2 y_{ij} \\frac{1}{\\hat{y}_{ij}} \\frac{\\partial \\hat{y}_{ij}}{\\partial z_{ij}} \\\\\n", "& = - \\sum_{j}^2 y_{ij} \\frac{1}{\\hat{y}_{ij}} \\frac{\\partial}{\\partial z_{ij}} \\frac{e^{z_{ij}}}{\\sum_m^2e^{z_{im}}} \\\\\n", "& = - \\sum_{j}^2 y_{ij} \\frac{1}{\\hat{y}_{ij}} \\frac{e^{z_{ij}}\\sum_m^2 e^{z_{im}} - e^{z_{ij}}e^{z_{ij}}}{(\\sum_m^2e^{z_{im}})^2} \\\\\n", "& = - y_{ik} \\frac{1}{\\hat{y}_{ik}} \\frac{e^{z_{ik}}\\sum_m^2 e^{z_{im}} - e^{z_{ik}}e^{z_{ik}}}{(\\sum_m^2e^{z_{im}})^2} - (1 - y_{ik}) \\frac{1}{\\hat{y}_{in}} \\frac{e^{z_{in}}\\sum_m^2 e^{z_{im}} - e^{z_{in}}e^{z_{in}}}{(\\sum_m^2e^{z_{im}})^2}\\\\\n", "& = - y_{ik} \\frac{1}{\\hat{y}_{ik}} \\frac{e^{z_{ik}}}{\\sum_m^2e^{z_{im}}} \\frac{\\sum_m^2 e^{z_{im}} - e^{z_{ik}}}{\\sum_m^2e^{z_{im}}}\\\\\n", "& = - y_{ik} \\frac{1}{\\hat{y}_{ik}} \\hat{y}_{ik} \\frac{\\sum_m^2 e^{z_{im}} - e^{z_{ik}}}{\\sum_m^2e^{z_{im}}} \\\\\n", "& = - y_{ik} \\left( \\frac{\\sum_m^2 e^{z_{im}}}{\\sum_m^2e^{z_{im}}} - \\frac{e^{z_{ik}}}{\\sum_m^2e^{z_{im}}} \\right)\\\\\n", "& = - y_{ik} ( 1 - \\hat{y}_{ik})\\\\\n", "& = - y_{ik} + y_{ik}\\hat{y}_{ik}\\\\\n", "& = - y_{ij} + 1\\hat{y}_{ij}\\\\\n", "& = \\hat{y}_{ij} - y_{ij}\\\\\n", "\\end{split}$$\n", "\n", "Applied to all our datapoints, the result would be:\n", "\n", "$$\\begin{equation}\n", "\\frac{\\partial L}{\\partial \\mathbf{z}_{j}} = - \\frac{1}{N} \\frac{\\partial}{\\partial \\mathbf{z}_{j}} \\sum_{j}^2 \\mathbf{y}_{j} \\odot \\log(\\mathbf{\\hat{y}}_{j}) = \\frac{\\mathbf{\\hat{y}}_{j} - \\mathbf{y}_{j}}{N}\\\\\n", "\\frac{\\partial L}{\\partial Z} = \\frac{\\hat{Y} - Y}{N}\n", "\\end{equation}$$\n", "\n", "where $\\odot$ is the element-wise product. Let's implement this in numpy:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def compute_loss_diff(Y, Y_est):\n", " \"\"\"Computes the averate cross-entropy loss derivative.\n", " \n", " Parameters\n", " ----------\n", " Y: np.ndarray((N, 2))\n", " Target labels (XOR correct results).\n", " Y_est: np.ndarray((N, 2))\n", " Estimated XOR values.\n", " \n", " Returns\n", " -------\n", " dloss: np.ndarray((N, 2))\n", " Loss value: the average cross-entropy derivative.\n", " \"\"\"\n", " return (Y_est - Y) / float(Y.shape[0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Gradient of the hidden layer\n", "\n", "We have computed the partial derivative with respect to our last layer, now let's do the same with respect to our hidden layer. This will help us when obtaining the partial derivatives to our trainable coefficients, which is ultimately what we want to obtain.\n", "\n", "Again, let's apply the chain-rule to derive this:\n", "\n", "$$\\begin{split}\n", "\\frac{\\partial L}{\\partial H} & = \\frac{\\partial L}{\\partial \\hat{Y}} \\frac{\\partial \\hat{Y}}{\\partial Z} \\frac{\\partial Z}{\\partial H} \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} \\frac{\\partial Z}{\\partial H} \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} \\frac{\\partial}{\\partial H} H W_2 + b_2 \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} W_2^T\\\\\n", "\\end{split}$$\n", "\n", "Including the ReLU activation function $\\sigma$ from the first layer will simplify the math later for backpropagation, let's do it:\n", "\n", "$$\\begin{split}\n", "\\frac{\\partial L}{\\partial \\sigma} & = \\frac{\\partial L}{\\partial \\hat{Y}} \\frac{\\partial \\hat{Y}}{\\partial Z} \\frac{\\partial Z}{\\partial H}\\frac{\\partial H}{\\partial \\sigma} \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} W_2^T \\frac{\\partial H}{\\partial \\sigma}\\\\\n", "& = \\frac{\\hat{Y} - Y}{N} W_2^T \\frac{\\partial}{\\partial \\sigma}\\sigma(X W_1 + b_1)\\\\\n", "& = \\frac{\\hat{Y} - Y}{N} W_2^T \\frac{\\partial}{\\partial \\sigma}\\text{max}\\{\\mathbf{0}, X W_1 + b_1\\}\\\\\n", "& = \\frac{\\hat{Y} - Y}{N} W_2^T \\mathbb{1}\\{X W_1 + b_1 > 0\\}\\\\\n", "\\end{split}$$\n", "\n", "As you can see, the derivative of a ReLu function $\\mbox{max}\\{0, x\\}$ is simply the indicator $\\mathbb{1}\\{x > 0\\}$. If this is not obvious, here's a [further explanation](http://kawahara.ca/what-is-the-derivative-of-relu/).\n", "\n", "Since we know that this $\\mathbb{1}\\{X W_1 + b_1 > 0\\}$ will always be true as long as $\\mathbb{1}\\{H > 0\\}$ is true (since $H$ is already rectified), we can further simplify the formula by:\n", "\n", "$$\\begin{split}\n", "\\frac{\\partial L}{\\partial \\sigma} = \\frac{\\hat{Y} - Y}{N} W_2^T \\mathbb{1}\\{X W_1 + b_1 > 0\\} = \\frac{\\hat{Y} - Y}{N} W_2^T \\mathbb{1}\\{H > 0\\}\\\\\n", "\\end{split}$$\n", "\n", "Let's put this derivative in a function." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def compute_hidden_diff(H, W2, dloss):\n", " \"\"\"Computes the derivative of the first hidden layer, including it's activation.\n", " \n", " Parameters\n", " ----------\n", " H: np.ndarray((N, n_hidden))\n", " Output of the hidden layer.\n", " W2: np.ndarray((n_hidden, 2))\n", " Coefficients of the hidden to output layer.\n", " dloss: np.ndarray((N, 2))\n", " Derivative of the output layer.\n", " \n", " Returns\n", " -------\n", " dhidden: np.ndarray((N, n_hidden))\n", " Derivative of the hidden layer.\n", " \"\"\"\n", " dhidden = np.dot(dloss, W2.T)\n", " dhidden[H <= 0] = 0 # ReLU backprop\n", " return dhidden" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Gradient of the trainable coefficients \n", "\n", "Now that we have the derivative of the loss function with respect to the output (second layer), we can easily compute the gradient of the trainable coefficients $W_2$ and $b_2$ using backpropagation. Let's do it:\n", "\n", "$$\\begin{split}\n", "\\frac{\\partial L}{\\partial W_2} & = \\frac{\\partial L}{\\partial \\hat{Y}} \\frac{\\partial \\hat{Y}}{\\partial Z} \\frac{\\partial Z}{\\partial W_2} \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} \\frac{\\partial Z}{\\partial W_2} \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} \\frac{\\partial}{\\partial W_2} H W_2 + b_2 \\\\\n", "& = H^T \\frac{\\hat{Y} - Y}{N}\\\\\n", "\\\\\n", "\\frac{\\partial L}{\\partial b_2} & = \\frac{\\partial L}{\\partial \\hat{Y}} \\frac{\\partial \\hat{Y}}{\\partial Z} \\frac{\\partial Z}{\\partial b_2} \\\\\n", "& = \\frac{\\hat{Y} - Y}{N} \\frac{\\partial}{\\partial b_2} H W_2 + b_2 \\\\\n", "& = \\frac{\\hat{Y} - Y}{N}\\\\\n", "\\end{split}$$\n", "\n", "Analogously, since we have computed the derivative of the loss function with respect to the hidden layer, we can now compute the one with respect to the rest of trainable coefficients $W_1$ and $b_1$:\n", "\n", "$$\\begin{split}\n", "\\frac{\\partial L}{\\partial W_1} & = \\frac{\\partial L}{\\partial \\hat{Y}} \\frac{\\partial \\hat{Y}}{\\partial Z} \\frac{\\partial Z}{\\partial H}\\frac{\\partial H}{\\partial \\sigma}\\frac{\\partial \\sigma}{\\partial W_1} \\\\\n", "& = \\frac{\\partial L}{\\partial \\sigma} \\frac{\\partial}{\\partial W_1} X W_1 + b_1\\\\\n", "& = X^T \\frac{\\partial L}{\\partial \\sigma}\\\\\n", "& = X^T \\frac{\\hat{Y} - Y}{N} W_2^T \\mathbb{1}\\{H > 0\\}\\\\\n", "\\\\\n", "\\frac{\\partial L}{\\partial b_1} & = \\frac{\\partial L}{\\partial \\hat{Y}} \\frac{\\partial \\hat{Y}}{\\partial Z} \\frac{\\partial Z}{\\partial H}\\frac{\\partial H}{\\partial \\sigma}\\frac{\\partial \\sigma}{\\partial b_1} \\\\\n", "& = \\frac{\\partial L}{\\partial \\sigma} \\frac{\\partial}{\\partial b_1} X W_1 + b_1\\\\\n", "& = \\frac{\\partial L}{\\partial \\sigma}\\\\\n", "& = \\frac{\\hat{Y} - Y}{N} W_2^T \\mathbb{1}\\{H > 0\\}\\\\\n", "\\end{split}$$\n", "\n", "All of which could be modularized and implemented in a backpropagation function like this:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def backprop(x, dx):\n", " \"\"\"Computes the backpropagation for a given layer.\n", " \n", " Parameters\n", " ----------\n", " x: np.ndarray((N, n_in))\n", " Input layer.\n", " dx: np.ndarray((N, n_out))\n", " Derivative of the input layer.\n", " \n", " Returns\n", " -------\n", " dW: np.ndarray((n_in, n_out))\n", " Derivative of the loss with respect to the W matrix.\n", " db: np.ndarray((1, n_out))\n", " Derivative of the loss with respect to b.\n", " \"\"\"\n", " dW = np.dot(x.T, dx)\n", " db = np.sum(dx, axis=0, keepdims=True)\n", " return dW, db" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Gradient Descent\n", "\n", "Almost done! We now can use the gradients with respect to the trainable coefficients computed above to update the actual trainable coefficients step by step. This will be done iteratively, with a specific learning rate $\\gamma$, until convergence.\n", "\n", "Here the formula, applied to all $\\mathcal{W} \\in \\{W_1, b_1, W_2, b_2\\}$:\n", "\n", "$$\\mathcal{W} := \\mathcal{W} - \\gamma \\frac{\\partial L}{\\partial \\mathcal{W}}$$\n", "\n", "Let's write a function to do so:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def update_step(x, dx, step):\n", " \"\"\"Update step of gradient descent. Updates the trainable coefficients. \n", " \n", " Parameters\n", " ----------\n", " x: np.ndarray\n", " Trainable coefficient.\n", " dx: np.ndarray\n", " Derivative of the loss with respect to the trainable coefficient.\n", " step: float\n", " Step size of gradient descent.\n", " \n", " Returns\n", " -------\n", " nx: np.ndarray\n", " Updated trainable coefficient in the direction of its gradient.\n", " \"\"\"\n", " return x - step * dx" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Whole Thing\n", "\n", "Alrighten. The last thing to do is to put all the pieces together. We will do so in a single training loop, that will go over a few thousand epochs. \n", "\n", "It may be interesting to play around with the `step` variable, to see how much faster (but more likely to fall into bad local minima) the whole thing will be if set high enough; and how slow (but less likely to fall into those terrible places) it would be with a sufficiently small step.\n", "\n", "In the last line of this implementation I update the whole training set with new randomly generated data. While this is not necessary (and makes the whole training noticeably slower), it seems to help to obtain better results. Feel free to play with it (i.e., remove it or just update the set after a few epochs).\n", "\n", "Another interesting parameter is the number of training observations `N`. While it often converges with 100 observations, that's not always the case. I guess the more observations, the more local minima around the gradient we'll find, but it might result in a faster convergence too (when it does converge). Also notice how sensible this parameter is in terms of computation efficiency." ] }, { "cell_type": "code", "execution_count": 86, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\tEpoch 0: loss 0.684157\t acc 80.0%\n", "\tEpoch 1000: loss 0.671128\t acc 100.0%\n", "\tEpoch 2000: loss 0.555213\t acc 100.0%\n", "\tEpoch 3000: loss 0.374493\t acc 100.0%\n", "\tEpoch 4000: loss 0.198592\t acc 100.0%\n", "\tEpoch 5000: loss 0.114024\t acc 100.0%\n", "\tEpoch 6000: loss 0.074607\t acc 100.0%\n", "\tEpoch 7000: loss 0.052104\t acc 100.0%\n", "\tEpoch 8000: loss 0.045177\t acc 100.0%\n", "\tEpoch 9000: loss 0.029315\t acc 100.0%\n" ] } ], "source": [ "# Create some training data\n", "N = 100\n", "X, Y = gen_data(N)\n", "\n", "# Initialize the coefficients randomly\n", "W1, b1, W2, b2 = init_coefficients()\n", "\n", "# Learning parameters\n", "n_epochs = 10000\n", "step = 0.01\n", "\n", "# Main training loop\n", "for n_epoch in range(n_epochs):\n", " # Forward pass of the network, catching the two layers' outputs\n", " H, Y_est = forward_pass(X, W1, W2, b1, b2)\n", " \n", " # Average cross-entropy loss\n", " loss = compute_loss(Y, Y_est)\n", " \n", " # Gradient of the second (output) layer\n", " dloss = compute_loss_diff(Y, Y_est)\n", " \n", " # Gradient of the hidden layer\n", " dhidden = compute_hidden_diff(H, W2, dloss)\n", " \n", " # Backpropagation over all trainable coefficients\n", " dW2, db2 = backprop(H, dloss)\n", " dW1, db1 = backprop(X, dhidden)\n", " \n", " # Update step\n", " W1 = update_step(W1, dW1, step)\n", " b1 = update_step(b1, db1, step)\n", " W2 = update_step(W2, dW2, step)\n", " b2 = update_step(b2, db2, step)\n", " \n", " # Printout\n", " if n_epoch % 1000 == 0:\n", " acc = np.sum(Y[np.arange(N), np.argmax(Y_est, axis=1)]) / float(N) # Accuracy\n", " print(\"\\tEpoch %d: loss %f\\t acc %.1f%%\" % (n_epoch, loss, (acc * 100)))\n", " \n", " # Generate more data randomly (this might prevent falling into bad local minima)\n", " X, Y = gen_data(N) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# The Test\n", "\n", "Finally, we can generate more data and see how well the model generalizes. You should get 100% in most trained models if you use the default parameters from the cell above." ] }, { "cell_type": "code", "execution_count": 82, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Accuracy in Test set: 100.00%\n", "1 XOR 1 = 0\n", "0 XOR 1 = 1\n", "0 XOR 1 = 1\n", "0 XOR 0 = 0\n", "0 XOR 0 = 0\n", "0 XOR 0 = 0\n", "1 XOR 0 = 1\n", "1 XOR 1 = 0\n", "0 XOR 0 = 0\n", "0 XOR 0 = 0\n" ] } ], "source": [ "X_test, Y_test = gen_data(N)\n", "_, Y_est = forward_pass(X_test, W1, W2, b1, b2)\n", "acc = np.sum(Y_test[np.arange(N), np.argmax(Y_est, axis=1)]) / float(N)\n", "print(\"Accuracy in Test set: %.2f%%\" % (acc * 100))\n", "\n", "# Let's print some of our Deep XOR results, just for fun\n", "xor_print(X_test, Y_est, 10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# The End\n", "\n", "So that's it. We have trained a feedwordard neural network with a hidden layer to model an XOR gate. We have implemented it using numpy. And it worked (at least most of the times).\n", "\n", "I'm pretty sure there might be some bugs in the code / math. But that's why this is here, to learn with you, titans. Thus, pull requests are welcome :)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Bonus: XOR, Y U Not Work With Linear Models?\n", "\n", "As explained in Section 6.2 of the Deep Learning book, the XOR operation is not linear. Therefore, it is not possible to model it with simple linear regression. To illustrate this, we can actually try to fit one of these simple models and find the results analytically.\n", "\n", "We are gonna frame this as **regression** (instead of classification), so let's say that $\\mathbf{y} \\in \\mathbb{R}^N$ are the labels (notice how this is now a simple vector instead of an $N \\times 2$ matrix) and $X \\in \\mathbb{R}^{N \\times 2}$ the observations set (as before). The model we want to approximate is:\n", "\n", "$$ \\mathbf{\\hat{y}} = X \\mathbf{w} + b $$\n", "\n", "where $\\mathbf{w} \\in \\mathbb{R}^2$ and $b \\in \\mathbb{R}$ are the trainable coefficients.\n", "\n", "To simplify the math we can include the bias as an extra coefficient in $\\mathbf{w}$ by adding a column of ones in $X$, resulting in:\n", "\n", "$$ \\mathbf{\\hat{y}} = X \\mathbf{w}$$\n", "\n", "where $X \\in \\mathbb{R}^{N \\times 3}$ and $\\mathbf{w} \\in \\mathbb{R}^3$.\n", "\n", "Let the \"loss function\" in this case be the Mean Squared Error (MSE), which is standard for regression problems:\n", "\n", "$$\\text{MSE} = \\frac{1}{N} \\sum_i^N (y_i - \\hat{y}_i)^2 = \\frac{1}{N} (\\mathbf{y} - \\mathbf{\\hat{y}})^2$$\n", "\n", "We can derive the set of normal equations to solve this optimization problem analytically:\n", "\n", "\n", "$$\\begin{equation}\n", "\\text{argmin}_{\\mathbf{w}} \\text{MSE}\\\\\n", "\\frac{\\partial \\text{MSE}}{\\partial \\mathbf{w}} = 0\\\\\n", "\\frac{\\partial}{\\partial \\mathbf{w}} \\frac{1}{N} (\\mathbf{y} - (X \\mathbf{w}))^2 = 0 \\\\\n", "\\frac{\\partial}{\\partial \\mathbf{w}} \\mathbf{y}^T\\mathbf{y} - 2 \\mathbf{y}^TX \\mathbf{w} + (X\\mathbf{w})^2 = 0 \\\\\n", "-2 X^T\\mathbf{y} + 2X^TX\\mathbf{w} = 0 \\\\\n", "-X^T\\mathbf{y} + X^T X\\mathbf{w} = 0 \\\\\n", "X^T X\\mathbf{w} = X^T\\mathbf{y} \\\\\n", "\\mathbf{w} = (X^T X)^{-1}X^T\\mathbf{y}\\\\\n", "\\end{equation}$$\n", "\n", "This system is called the set of *normal equations*, and if we plug in our 4 possible types of inputs as $X$ and $\\mathbf{y}$:\n", "\n", "* $0 \\oplus 0 = 0$\n", "* $0 \\oplus 1 = 1$\n", "* $1 \\oplus 0 = 1$\n", "* $1 \\oplus 1 = 0$\n", "\n", "and solve for $\\mathbf{w}$ the result is:\n", "\n", "* $b = 0.5$ $(= w_0)$\n", "* $\\mathbf{w} = [0, 0]^T$\n", "\n", "As we can see, we will always get 0.5 when trying to use this linear model that best minimizes the MSE. Therefore, we need something more powerful, more non-linear, more fanciful, more doge, such as neural networks. Hence, Deep XOR.\n", "\n", "Here the implementation in numpy:" ] }, { "cell_type": "code", "execution_count": 85, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b = 0.5, w = [0.0, 0.0]\n" ] } ], "source": [ "# Normal equations, solving with the four unique examples:\n", "X = np.array([[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]) # Added the bias as ones in the first column\n", "y = np.array([0, 1, 1, 0])\n", "b, w1, w2 = np.dot(np.linalg.inv(np.dot(X.T, X)), np.dot(X.T, y))\n", "print(\"b = {}, w = [{}, {}]\".format(b, w1, w2))" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [default]", "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": 1 }