{
"cells": [
{
"cell_type": "markdown",
"source": [
"# Foundations of Machine Learning - Session 06\n",
"\n",
"- *Course*: Foundations of Machine Learning\n",
"- *Session*: 06\n",
"- *Unit*: Multi-Layer Perceptron\n",
"\n",
"This notebook develops a Multi-Layer perceptron of arbitary depth in Numpy and trains it using the IGD algorithm."
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 1,
"outputs": [],
"source": [
"import numpy as np\n",
"from typing import Sequence, Tuple\n",
"\n",
"def sigmoid(z):\n",
" return 1 / (1 + np.exp(-z))"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Training Loop\n",
"\n",
"This week, we will begin implementing the MLP a bit differently than in previous exercises: the first thing we define is the overall training loop. In the cell below, the main training loop is already implemented. It closely follows the notation of the IGD algorithm from the lecture; the corresponding pseudo-code lines from slide `ML:IV-115` are listed in-code in the comments. Take a look at the functions signature and corresponding docstrings. Especially the `shape` argument is important: it specifies the structure of our MLP.\n",
"\n",
"The train function calls five other functions that implement the main logic of our network:\n",
"- `initialize_random_weights` - constucts W_h, i.e., the weight matrices for each layer of the MLP\n",
"- `forward` - the forward pass of the MLP, i.e., the function evaluation\n",
"- `backward_delta` - the residual backward pass, i.e., the first part of calculating the derivative of the loss\n",
"- `backward_weight` - the weight backward pass, i.e., the second part of calculating the derivative of the loss\n",
"- `update` - updates the parameters of the MLP for the next step\n",
"\n",
"In the following, we will implement each of these functions. Try to step through the code and the lecture slide side-by-side to match parts between both."
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 2,
"outputs": [],
"source": [
"def train(D: Sequence[Tuple[Sequence[float], int]], shape: Sequence[int] = (2, 3, 4, 1), n_iter: int = 4000, eta: float = 0.1):\n",
" \"\"\"\n",
" Main training loop for training an MLP. Returns the trained weights.\n",
" :param D: Dataset, sequence of (x, c) where x is a feature vector and c is the class label\n",
" :param shape: the MLP specification; sequence of ints, where each specifies the layer size of the corresponding layer. They can take arbitrary values, but the first and last must match the training dataset used. At least two layers need to be specified.\n",
" :param n_iter: number of iterations to train the MLP for\n",
" :param eta: learning rate\n",
" :return: the trained weights\n",
" \"\"\"\n",
" # (1) Initialization\n",
" W_h = initialize_random_weights(shape)\n",
" # (2) Outer loop (over epochs)\n",
" for t in range(n_iter):\n",
" # (4) Inner loop (over training examples)\n",
" for x, c in D:\n",
" # Add leading 1 to x (w_0)\n",
" x = np.hstack([1, x])\n",
" # Reshape x to a column vector\n",
" x = np.reshape(x, (len(x), 1))\n",
" # (5) Forward propagation\n",
" y_h = forward(W_h, x)\n",
" y = y_h[-1][1:]\n",
" # (6) Calculation of residual vector\n",
" delta = c - y\n",
" # (7a) Backpropagation of residuals\n",
" delta_h = backward_delta(W_h, delta, y_h)\n",
" # (7b) Backpropagation of weights\n",
" delta_W_h = backward_weight(W_h, delta_h, y_h, x, eta)\n",
" # (8) Weight update\n",
" W_h = update(W_h, delta_W_h)\n",
"\n",
" return W_h"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Initialization\n",
"\n",
"The first function called is `initialize_random_weights` - it does exactly what the name suggests: randomly initialize the networks weights. This means that for each specified layer, a matrix of the correct shape has to be constructed and filled with random values. All matrices that together define the MLP are kept in a single list, that we call `W_h`.\n",
"\n",
"**Exercise** implement the initialization function to construct a list of weight matrices that correspond to the specified network shape. Each matrix is initially filled with random values.\n",
"\n",
"**Hints**:\n",
"- the first entry is an empty list, since the input layer has no preceding weights; this also means that all subsequent indexing starts at 1, ignoring the empty first entry\n",
"- each weight matrix has a size of `(n_units, n_units_prev + 1)`, where `n_units` is the number of units specified for this layer in `shape`, and `n_units_prev` is the number of units in the preceding layer.\n",
"- use random values from a standard normal distribution to initialize each matrix"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 3,
"outputs": [],
"source": [
"def initialize_random_weights(shape: Sequence[int]):\n",
" \"\"\"\n",
" Initialize the weight matrices of an MLP according to the specified shape. Each entry in shape specifies the layer size of the corresponding layer. They can arbitrary values here, but the first and last must match the training dataset used. At least two\n",
" layers need to be specified.\n",
" :param Sequence[int] shape: number of units in all network layers\n",
" :returns Sequence[np.array]): list of matrices, one for each network layer\n",
" \"\"\"\n",
" W_h = [[]] # the first element is empty; so that we'll count from 1\n",
" for i in range(1, len(shape)):\n",
" l_s = shape[i]\n",
" l_prev = shape[i - 1]\n",
" W_h_s = np.random.normal(size=(l_s, l_prev + 1))\n",
" W_h.append(W_h_s)\n",
" return W_h\n"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Forward Pass\n",
"\n",
"The forward pass of the network sequentially steps through the layers and applies the model function $\\mathbf{y}$ parametrized by that layers weight matrix at every step. In the first layer, the network input is taken for $\\mathbf{x}$, in any subsequent one the output of the previous layer becomes the input for the next. Thus, the calculation for a layer $s$ can be expressed as:\n",
"\n",
"$$ \\mathbf{y}^{h_s}(\\mathbf{x}) = \\begin{pmatrix} 1 \\\\ \\sigma(W^{h_s}\\mathbf{y}^{h_{s-1}}(\\mathbf{x}))\\end{pmatrix} $$\n",
"\n",
"This corresponds to line 5 of the lecture pseudocode. For the implementation, we want to save each layers individual output (called \"activation\") in the variable `y_h`. The first entry of this list is just $\\mathbf{x}$. The subsequent entries then correspond to the output of the model function at each layer.\n",
"\n",
"**Exercise**: implement `forward`.\n",
"\n",
"*Hints*:\n",
"- `y_h` needs to be of the same length as `W_h`\n",
"- the first entry of `y_h` is `x`\n",
"- you can use `np.vstack` to add the preceding 1 to each output\n",
"- the final entry (with preceding 1 remove, i.e., `y_h[-1][1:]`) corresponds to the final model output, i.e. `y` (see training loop)"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 4,
"outputs": [],
"source": [
"def forward(W_h: Sequence[np.array], x: np.array) -> Sequence[np.array]:\n",
" \"\"\"\n",
" Forward propagation step.\n",
" :param W_h: List of weight matrices parametrizing each layer.\n",
" :param x: Input data.\n",
" :returns: Sequence of activations as calculated for each layer.\n",
" \"\"\"\n",
" # we store all hidden activations in a list\n",
" y_h = [np.empty(0) for s in range(len(W_h))]\n",
" # x first\n",
" y_h[0] = x\n",
" # Loop over hidden layers\n",
" for s in range(1, len(W_h)):\n",
" # compute activation for every layer based on previous layers' output\n",
" y_h[s] = np.vstack([1, sigmoid(W_h[s] @ y_h[s - 1])])\n",
" return y_h"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Backpropagation Part I\n",
"\n",
"The notation of the lecture specifies two backwards passes in line (7a) and line (7b); the first calculates the delta at each layer of the network. This is implemented in the `backward_delta` function. Note that this works *backwards*: we first calculate it for the last layer of the network, then for the second to last, and so forth.\n",
"\n",
"For the last layer, the delta is expressed as\n",
"$$ \\delta^{h_d} = \\delta \\circledcirc \\mathbf{y(x)} \\circledcirc (1 - y(\\mathbf{x}))$$\n",
"\n",
"For every subsequent one (down to the first), the delta is expressed as\n",
"\n",
"$$ \\delta^{h_s} = \\left[\\left(\\left(W^{h_{s+1}}\\right)^T\\delta^{h_{s+1}\\right) \\circledcirc \\mathbf{y^{h_s}(x)} \\circledcirc (1 - y^{h_s}(\\mathbf{x})) \\right]_{1,\\dots,l_s}$$\n",
"\n",
"Note the subscript at the end of the formula, which removes the preceding $1$ that was added in the forward pass. Similar to `y_h`, each layers delta is stored in a list `delta_h` for later access.\n",
"\n",
"**Exercise**: implement the first part of the backward step, `backward_delta`.\n",
"\n",
"*Hints*:\n",
"- `delta_h` needs to be of the same length as `W_h`\n",
"- the first entry of `delta_h` is calculated using $\\mathbf{y}$, check the training loop to see how you can access it.\n",
"- remember that the calculation goes *backwards*, i.e., implement it with a loop counting down (`range(len(W_h)-2, 0, -1)`).\n",
"- you can use `[1:]` to remove the preceding number from each output\n",
"- $\\circledcirc$ is written as `*` in numpy."
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 5,
"outputs": [],
"source": [
"def backward_delta(W_h: Sequence[np.array], delta: float, y_h: Sequence[np.array]) -> Sequence[np.array]:\n",
" \"\"\"\n",
" Computes the layer-wise delta in the backwards step of the MLP.\n",
" :param W_h: Sequence of weight matrices corresponding to each layer.\n",
" :param delta: overall residuals of the model.\n",
" :param y_h: activation values of the models' forward pass.\n",
" :return: layer-wise delta\n",
" \"\"\"\n",
" # we store all delta_h_s in a list\n",
" delta_h = [np.empty(0) for s in range(len(W_h))]\n",
" # delta_h_d last\n",
" delta_h[-1] = delta * y_h[-1][1:] * (1 - y_h[-1][1:])\n",
" for s in range(len(W_h)-2, 0, -1):\n",
" delta_h[s] = ((W_h[s + 1].T @ delta_h[s + 1]) * y_h[s] * (1 - y_h[s]))[1:]\n",
" return delta_h"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Backpropagation Part II\n",
"\n",
"The second part of backpropagation is calculating how much each weight is to be adjusted, i.e., the weight delta. This depends on the learning rate $\\eta$ and is implemented in `backward_weight`, which corresponds to line (7b) in the lectures pseudocode.\n",
"\n",
"Each layers weight adjustments are given as\n",
"\n",
"$$ \\Delta W^{h_{s}} = \\eta\\cdot\\left(\\delta^{h_s} \\otimes \\mathbf{y}^{h_{s-1}}(\\mathbf{x}) \\right)$$\n",
"\n",
"For the first layer, $\\mathbf{y}^{h_{s-1}}(\\mathbf{x})$ corresponds to just the input $\\mathbf{x}$. The weight delta of each layer is to be stored in `delta_W_h` for later access.\n",
"\n",
"\n",
"*Exercise*: implement `backward_weight`.\n",
"\n",
"**Hints**:\n",
"- `delta_W_h` needs to be the same length as `W_h`\n",
"- the first entry of `delta_W_h` is computed with `x`\n",
"- computation of `delta_W_h` can be done in any order (entries are not dependent on each other, only on `delta_h` and `y_h`)\n",
"- for dyadic product operator $\\otimes$ as written in the pseudocode, the transpose of the second operand is implicit. Numpy uses the same @-operator for dyadic products as for matrix multiplications, so we have to transpose explicitly (i.e., $A \\otimes B$ is `a @ b.T` in numpy)"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 6,
"outputs": [],
"source": [
"def backward_weight(W_h: Sequence[np.array], delta_h: Sequence[np.array], y_h: Sequence[np.array], x: np.array, eta: float) -> Sequence[np.array]:\n",
" \"\"\"\n",
" Compute the weight delta for every layer in the MLP.\n",
" :param W_h: weight matrix parametrizing the MLP\n",
" :param delta_h: hidden deltas from the first part of the backwards pass\n",
" :param y_h: hidden activations from the forward pass\n",
" :param x: model input\n",
" :param eta: learning rate\n",
" :returns: the calculated weight deltas for this training iteration\n",
" \"\"\"\n",
" delta_W_h = [np.empty(0) for s in range(len(W_h))]\n",
" delta_W_h[1] = eta * (delta_h[1] @ x.T)\n",
" for s in range(2, len(W_h)):\n",
" delta_W_h[s] = eta * (delta_h[s] @ y_h[s - 1].T)\n",
" return delta_W_h"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Updating Weights\n",
"\n",
"Given the weight deltas of the current training iteration, the models weights can now be adjusted to their new values with the `update` function. Here, each weight matrix $W^{h_s}$ is simply added to its counterpart in $\\Delta W^{h_s}$.\n",
"\n",
"**Exercise** implement `update`.\n",
"\n",
"*Hints*\n",
"- the first entry of `W_h` and `delta_W_h` can be ignored"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 7,
"outputs": [],
"source": [
"def update(W_h: Sequence[np.array], delta_W_h: Sequence[np.array]) -> Sequence[np.array]:\n",
" \"\"\"\n",
" Updates the MLPs weights.\n",
" :param W_h: current weight matrices.\n",
" :param delta_W_h: delta to modify the current weight matrices with.\n",
" :returns: updated weight matrices\n",
" \"\"\"\n",
" for s in range(1, len(W_h)):\n",
" W_h[s] += delta_W_h[s]\n",
" return W_h"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Training the MLP\n",
"\n",
"Now that all functions are implemented, we can start the training loop. For intial testing, we will use the XOR example dataset extensively used throughout the exercises to illustrate the capabilities of the MLP."
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 8,
"outputs": [],
"source": [
"### The XOR example dataset.\n",
"xs = np.array([\n",
" [0, 0],\n",
" [0, 1],\n",
" [1, 0],\n",
" [1, 1]\n",
"])\n",
"cs = [0, 1, 1, 0]\n",
"D = list(zip(xs, cs))"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 9,
"outputs": [
{
"data": {
"text/plain": "[[],\n array([[ 1.37107214, -0.31422941, -1.37358117],\n [-2.00045273, -0.88677966, -0.46300245],\n [-0.88678897, 0.91218597, 2.70966558]]),\n array([[-0.71765915, 0.38370861, -1.00650147, -0.83902179],\n [-0.88373678, 1.70899583, -1.13266279, -0.34096361],\n [ 0.80838467, -0.52725177, 0.71017812, -1.83168177],\n [-0.10618718, 1.97656448, 0.94163576, 0.7352752 ]]),\n array([[-0.15977313, 0.24331651, 0.43834092, -1.02970279, 0.30369411]])]"
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"w = train(D, shape=(2,3,4,1), eta=0.1, n_iter=1_000)\n",
"w"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Inference\n",
"\n",
"Given the trained weights, we now want to do *inference*, i.e., let the model predict outputs. For that, we implement a `predict` function that takes samples and the learned weights as input, and predicts a value for each sample.\n",
"\n",
"**Exercise**: write a `predict` function that applies the learned weights to infer the model's output.\n",
"\n",
"*Hints*\n",
"- don't forget to modify the `x` in the same was as in the original training loop; prepend a 1 and reshape it into column orientation\n",
"- you can use the `forward` function to predict the output. Note that you only need the last of the hidden activations, i.e., $\\mathbf{y}$.\n",
"- the output should be a numpy array with one prediction for each input sample, rounded to two digits\n"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 10,
"outputs": [],
"source": [
"def predict(X, W_h):\n",
" \"\"\"\n",
" Predicts an output for the given samples and weights.\n",
" :param X: input data\n",
" :param W_h: weight parameters\n",
" :returns: predicted output for input data as calculated by the MLP\n",
" \"\"\"\n",
" pred = []\n",
" for x in X:\n",
" x = np.hstack([1, x])\n",
" x = np.reshape(x, (len(x), 1))\n",
" pred.append(forward(W_h, x)[-1][1:].flatten().round(2))\n",
" return np.array(pred).flatten().tolist()\n"
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "markdown",
"source": [
"## Testing & Where to go from here\n",
"\n",
"You can use the cell below to test if the MLP successfully learns the non-linear XOR problem. Play around with different network shapes, learning rates, and number of iterations and observe how the output changes.\n",
"\n",
"Of course, you can import any of the previously used \"real\" datasets and see how the MLP performs compared to the other approaches implemented in this lab."
],
"metadata": {
"collapsed": false
}
},
{
"cell_type": "code",
"execution_count": 11,
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Predictions: [0.03, 0.97, 0.97, 0.02]\n",
" Truth: [0, 1, 1, 0]\n"
]
}
],
"source": [
"w = train(D, shape=(2, 3, 4, 1), n_iter=10_000)\n",
"print(f\"Predictions: {predict(xs, w)}\")\n",
"print(f\" Truth: {cs}\")"
],
"metadata": {
"collapsed": false
}
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 0
}