Lab 11
Neural Networks
Overview of the lab
- Neural networks: why and why now
- Brains and the artificial neuron
- Activation functions
- Implementing logical functions: the limits of one neuron
- Network structures and multilayer perceptrons
- Expressive power of MLPs
- Learning: cost function and gradient descent
- Perceptron learning
- Back-propagation
- Train a multilayer perceptron
- Handwritten digit recognition
- Neural networks in Python
Neural networks
Neural networks have existed since the 1950s–60s. Why are they only now so popular? Because now there are fast enough computers and there is enough data to train large networks.
Why go beyond linear models?
- So far we used linear models: linear and logistic regression. Some functions cannot be represented by linear models: linear regression cannot represent a quadratic function, and a linear classifier cannot represent XOR.
- One way around this is to define features (basis functions): linear regression can fit a cubic polynomial with the feature map \(\psi(x) = (1, x, x^2, x^3)\). But the features must be designed by hand, and we may need very many of them.
- Neural networks take a different approach: connect together lots of simple processing units, each computing a linear function followed by a nonlinearity. Together they can compute surprisingly complex functions, and they learn their own features from data.
📖 Sources: the course slides (after Russell & Norvig, AIMA), Roger Grosse's lecture notes Multilayer Perceptrons (University of Toronto), and Samy Baladram's Multilayer Perceptron, Explained: A Visual Guide with Mini 2D Dataset, which walks through a tiny network on an 8-point dataset step by step.
Brains and the artificial neuron
Brains
- About \(10^{11}\) neurons of more than 20 types, \(10^{14}\) synapses, 1–10 ms cycle time.
- A neuron receives signals through its dendrites, sums them in the cell body, and fires along its axon when the total is large enough. Signals are noisy "spike trains" of electrical potential.
The McCulloch–Pitts "unit"
The output is a "squashed" linear function of the inputs: a weighted sum of the inputs, passed through an activation function \(g\).
\(x_j\): inputs · \(w_j\): weights · \(b\): bias · \(g\): activation function · \(a\): the unit's activation (output). The slides write the bias as an extra weight \(W_{0}\) on a fixed input \(a_0 = -1\), i.e. \(b = -W_0\): the same thing.
- Linear regression is such a unit with \(g(z) = z\); a binary linear classifier uses a hard threshold at 0; logistic regression uses \(g = \sigma\), the sigmoid.
- A gross oversimplification of real neurons, but its purpose is to understand what networks of simple units can do.
Try it: one neuron with two inputs
The shading shows the unit's output \(a\) for every input \((x_1, x_2)\). Changing the weights moves the location, orientation and steepness of the cliff: the weights set its direction, the bias shifts it. Click the plot to move the probe input.
Activation functions
| Name | \(g(z)\) | Derivative \(g'(z)\) | Notes |
|---|---|---|---|
| Step / threshold | \(1\) if \(z > 0\), else \(0\) | \(0\) (undefined at 0) | the original perceptron; easy to design by hand, impossible to train with gradients |
| Sigmoid (logistic) | \(\sigma(z) = \dfrac{1}{1 + e^{-z}}\) | \(\sigma(z)(1 - \sigma(z))\) | a soft threshold with outputs in (0, 1); saturates for large \(|z|\) |
| tanh | \(\tanh(z)\) | \(1 - \tanh^2(z)\) | like the sigmoid but in (−1, 1), centred at 0 |
| ReLU (rectified linear unit) | \(\max(0, z)\) | \(1\) if \(z > 0\), else \(0\) | the default in modern deep networks: cheap, does not saturate for \(z > 0\) |
| Linear | \(z\) | \(1\) | used in the output unit for regression |
- Changing the bias moves the threshold location.
- Soft thresholds. With a hard threshold the derivative is 0 almost everywhere, so gradient descent gets no signal and cannot learn the weights. So we replace it with a soft one. This costs no expressive power: scaling up the weights and bias, \(\sigma(5z)\), \(\sigma(20z)\), …, makes the sigmoid as close to a step as we want.
Try it: activation functions and their derivatives
The solid curve is \(g(k z - s)\), the dashed curve its derivative (the learning signal). Increase the steepness \(k\) of the sigmoid: it turns into a step, and its derivative into a narrow spike.
Implementing logical functions
A single threshold unit (inputs 0/1, output 1 if \(W_1 x_1 + W_2 x_2 - W_0 > 0\)) implements the basic logic gates. McCulloch and Pitts: every Boolean function can be implemented by a network of such units.
| Gate | \(W_0\) (bias weight) | \(W_1\) | \(W_2\) | Fires when |
|---|---|---|---|---|
| AND | 1.5 | 1 | 1 | \(x_1 + x_2 > 1.5\) |
| OR | 0.5 | 1 | 1 | \(x_1 + x_2 > 0.5\) |
| NOT | −0.5 | −1 | — | \(-x_1 > -0.5\), i.e. \(x_1 = 0\) |
Expressiveness of perceptrons
- A perceptron (Rosenblatt, 1957, 1960) is a single layer of units with \(g\) = step function. It can represent AND, OR, NOT, majority, etc., but not XOR.
- It represents a linear separator in input space: \(\sum_j W_j x_j > 0\), or \(\mathbf{W} \cdot \mathbf{x} > 0\). The points where it fires lie on one side of a straight line (a hyperplane in more dimensions).
- XOR (1 when exactly one input is 1) puts the two "1" points on opposite corners: no single line separates them. Minsky & Papert (1969) pointed this out and "pricked the neural network balloon" for more than a decade.
Try it: find the weights
Choose a gate to load the weights from the table, then move the sliders. The line is where \(W_1 x_1 + W_2 x_2 = W_0\); the unit fires on the shaded side. For XOR, try to get all four rows right.
Network structures
- Feed-forward networks: single-layer perceptrons, multi-layer perceptrons. The units form a graph without cycles, so everything is computed in one pass from inputs to outputs. Feed-forward networks implement functions and have no internal state.
- Recurrent networks: the graph has cycles, so the output feeds back in.
- Hopfield networks have symmetric weights (\(W_{i,j} = W_{j,i}\)), \(g(x) = \text{sign}(x)\), \(a_i = \pm 1\): holographic associative memory.
- Boltzmann machines use stochastic activation functions (≈ MCMC in Bayes nets).
- Recurrent neural nets have directed cycles with delays ⇒ they have internal state (like flip-flops) and can oscillate; used for sequences.
Multilayer perceptrons (MLP)
The simplest feed-forward network. The units are arranged in layers, and every unit in one layer is connected to every unit in the next: the network is fully connected. The number of hidden units is typically chosen by hand.
- Input layer: one unit per input feature. Output layer: one unit for regression or binary classification, \(K\) units for \(K\)-class classification.
- Hidden layers: everything in between. "Hidden", because we do not know ahead of time what these units should compute: that has to be learned.
- The number of layers is the depth, the number of units in a layer is the width. "Deep learning" = training networks with many layers.
- "MLP" is an unfortunate name: the original perceptron was a particular 1950s algorithm, and MLPs have very little to do with it.
Feed-forward example (units 1, 2 are inputs, 3, 4 hidden, 5 the output). A feed-forward network is a parameterised family of nonlinear functions:
Adjusting the weights changes the function: that is how we will learn. For whole layers we write it with matrices: one weight matrix \(\mathbf{W}^{(\ell)}\) and bias vector \(\mathbf{b}^{(\ell)}\) per layer, and \(\phi\) applied element-wise:
Example: an MLP that computes XOR
XOR = "one of the inputs is 1, but not both of them". Let hidden unit \(h_1\) detect whether at least one input is 1 (OR) and \(h_2\) whether both are 1 (AND). The output fires only if \(h_1 = 1\) and \(h_2 = 0\). All activations are hard thresholds at 0.
Try it: feed the four inputs through
Pick an input. The right plot shows feature learning: in the hidden space \((h_1, h_2)\) the four inputs land on only three points, and there a single line separates XOR. The hidden layer has made the data linearly separable.
Expressive power of MLPs
- Linear networks are no more powerful than one layer. With \(\phi(z) = z\), a deep network computes \(\mathbf{y} = \mathbf{W}^{(L)} \cdots \mathbf{W}^{(2)} \mathbf{W}^{(1)} \mathbf{x}\), which is a single linear layer with \(\mathbf{W} = \mathbf{W}^{(L)} \cdots \mathbf{W}^{(1)}\). The nonlinearity is what gives depth its power.
- Universality. With nonlinear activations, all continuous functions can be represented with 2 layers (one hidden layer), and all functions with 3 layers. The idea: combine two opposite-facing threshold functions to make a ridge; combine two perpendicular ridges to make a bump; add bumps of various sizes and locations to fit any surface.
- The catch: the proof needs exponentially many hidden units (like the proof that decision trees can represent any Boolean function). Universality only says that a large enough network can memorise the training set, which is not very interesting. We want compact networks that compute fast and generalise.
- The power of depth. Deep networks can represent some functions much more compactly. The parity function (1 if an odd number of the inputs are 1) needs an exponentially large shallow network, but a deep network with size linear in the number of inputs: chain XOR units.
Try it: ridges, bumps and curve fitting
Every picture below is built only from sigmoid units. Raise the steepness to sharpen the thresholds. In Fit a curve, each bump uses 2 hidden units, and its height is the target's value at the bump's centre: more bumps, better fit.
Learning: cost function and gradient descent
Learning = adjusting the weights to reduce the error on the training set. We measure the error with a cost function \(J(w)\), e.g. the mean squared error, and look for the weights where it is smallest.
\(\alpha\) is the learning rate. The gradient points uphill, so we step against it.
- \(\nabla_w J < 0\) (negative gradient): increasing \(w\) lowers the cost, so \(w\) grows. \(\nabla_w J > 0\): \(w\) shrinks. At the minimum, \(\nabla_w J = 0\) and the steps stop.
- Starting from an initial weight, we take incremental steps downhill until we reach the minimum cost.
- Learning rate: too low needs many updates before reaching the minimum; just right swiftly reaches it; too high causes drastic updates that overshoot and can diverge.
💡 This is the same gradient descent as in Lab 6.5. The only new part for neural networks is how to compute the derivatives for weights deep inside the network: back-propagation.
Try it: the learning rate
\(J(w) = (w - 2)^2 + 1\), starting at \(w = 5.5\). For this cost any \(\alpha > 1\) diverges. Try the three presets, then your own.
Perceptron learning
Learn by adjusting the weights to reduce the error on the training set. The squared error for an example with input \(\mathbf{x}\) and true output \(y\) is \(E = \tfrac12 \text{Err}^2 = \tfrac12 (y - h_{\mathbf{W}}(\mathbf{x}))^2\). Gradient descent on \(E\):
E.g. a positive error (output too small) ⇒ increase the network output ⇒ increase the weights on positive inputs, decrease them on negative inputs.
- The perceptron learning rule converges to a consistent function for any linearly separable data set.
- It learns the majority function easily, while a decision tree is hopeless (it needs a huge tree). But a decision tree learns the restaurant function easily, and a perceptron cannot represent it (it is not linearly separable).
Try it: train one sigmoid unit
The unit sees each of the four examples in turn and applies the rule (one epoch = one pass over all examples). On AND and OR the error goes to almost 0. On XOR it gets stuck: no line can do it.
Back-propagation learning
For a hidden unit we do not know its "correct" output, so we cannot compute its error directly. Back-propagation passes the error backwards from the output layer, giving every hidden unit its share of the blame.
Output layer: same as for the single-layer perceptron,
\[ W_{j,i} \leftarrow W_{j,i} + \alpha \times a_j \times \Delta_i \qquad \text{where } \Delta_i = \text{Err}_i \times g'(in_i) \]Hidden layer: back-propagate the error from the output layer,
\[ \Delta_j = g'(in_j) \sum_i W_{j,i}\, \Delta_i \qquad\quad W_{k,j} \leftarrow W_{k,j} + \alpha \times a_k \times \Delta_j \]💡 The rules have the same shape at every layer: (input activation) × (delta of the receiving unit). A hidden unit's delta is the weighted sum of the deltas it feeds into, scaled by its own slope \(g'(in_j)\). Most neuroscientists deny that back-propagation occurs in the brain.
Derivation
The squared error on a single example is \(E = \tfrac12 \sum_i (y_i - a_i)^2\), where the sum is over the output nodes. For an output weight, only \(a_i\) depends on \(W_{j,i}\):
For a hidden weight \(W_{k,j}\), every output depends on it through \(a_j\) (chain rule):
So the gradient step \(W \leftarrow W - \alpha \frac{\partial E}{\partial W}\) is exactly the update rule above.
Try it: back-propagation by hand
The 5-unit network from the feed-forward example with sigmoid units and biases, one training example \(\mathbf{x} = (1, 0.5)\) with target \(y = 1\), and \(\alpha = 0.5\). Step through one full update: forward pass, error, output delta, hidden deltas, weight updates. Then repeat the update and watch the error shrink.
In practice
- At each epoch, sum the gradient updates for all examples and apply them (batch gradient descent). Or update after every example or small random mini-batch (stochastic gradient descent, SGD).
- A training curve for 100 restaurant examples: the error keeps dropping until the network finds an exact fit.
- Typical problems: slow convergence, local minima.
- MLPs are quite good for complex pattern recognition tasks, but the resulting hypotheses cannot be understood easily (compare a decision tree).
Train a multilayer perceptron
Following Samy Baladram's visual guide: a tiny MLP, ReLU hidden units, a sigmoid output unit, and the binary cross-entropy loss (see Lab 6.5), trained with gradient descent and back-propagation. The weights start as random values in \([-0.5, 0.5]\).
With a sigmoid output unit, the output delta becomes simply \(\hat{y} - y\): the \(g'(in)\) factor cancels.
Try it: the playground
Press ▶. The shading is the network's output \(\hat{y}\): blue where it predicts class 1 (golf), red where it predicts class 0. The curve is the loss per epoch. The default dataset is an invented 8-point version of the guide's "play golf" example: golf is played at medium temperature and humidity, not at the extremes. No straight line separates it. Try the 2-1 network (no hidden layer) to see it fail. Small networks sometimes get stuck in a local minimum; press New random weights and train again.
positive weight negative weight (thickness = size)
Handwritten digit recognition
The classic benchmark is MNIST: 28 × 28 grayscale images of handwritten digits. Each pixel is a number between 0 (black) and 1 (white), and the network ignores the spatial structure: the image is simply a vector of \(28 \times 28 = 784\) inputs. There are 10 output units, one per digit, and the prediction is the most active one.
- The hope is that the layers build up a hierarchy of features: pixels → edges → shapes (loops, strokes) → digits. A 9 might be "a loop at the top + a line on the right".
- Does the network actually do this? Partly. The first-layer weights of a trained network can be drawn as images, and many of them pick up oriented edges. What deeper layers compute is much harder to see.
| Method (from the slides) | Test error |
|---|---|
| 3-nearest-neighbour (KNN) | 2.4% |
| 400–300–10 unit MLP | 1.6% |
| LeNet: 768–192–30–10 unit MLP | 0.9% |
| Best at the time (kernel machines, vision algorithms) | ≈ 0.6% |
💡 These numbers come from the AIMA slides (early 2000s). Convolutional networks, which use the image's spatial structure, have since pushed MNIST much further: an ensemble of deep networks (Tabik et al., 2020, MNIST-NET10) misclassifies only 10 of the 10 000 test images, i.e. 0.1%.
Try it: draw a digit
A real network, trained in Python and running in your browser: 64–16–10 with sigmoid hidden units and a softmax output. It was trained on scikit-learn's small digits dataset (8 × 8 images with values 0–16, test accuracy). Draw a digit in the box; it is downsampled to 8 × 8 exactly like the dataset (the number of ink pixels in each 4 × 4 block). The 16 small images are the first-layer weights of the hidden units (red = negative, blue = positive): each unit looks for ink in its blue pixels and no ink in its red ones. At 8 × 8 they are coarse stroke detectors rather than the clean edges seen on MNIST. The bars below them are the units' activations.
16 hidden units
10 outputs
Neural networks in Python
1. An MLP from scratch with NumPy (XOR)
Forward pass, binary cross-entropy, back-propagation and gradient descent, written out in full. Each training example is a row of X, so the layers are X @ W + b.
mlp_numpy.py Python
import numpy as np
def sigmoid(z):
return 1 / (1 + np.exp(-z))
X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], dtype=float)
y = np.array([[0], [1], [1], [0]], dtype=float) # XOR
rng = np.random.default_rng(0)
W1, b1 = rng.uniform(-1, 1, (2, 4)), np.zeros(4) # 2 inputs -> 4 hidden units
W2, b2 = rng.uniform(-1, 1, (4, 1)), np.zeros(1) # 4 hidden -> 1 output
lr = 1.0
for epoch in range(5000):
# forward pass
H = sigmoid(X @ W1 + b1) # hidden activations, shape (4, 4)
Y = sigmoid(H @ W2 + b2) # outputs, shape (4, 1)
loss = -np.mean(y * np.log(Y) + (1 - y) * np.log(1 - Y))
# backward pass (binary cross-entropy + sigmoid output: delta = Y - y)
dZ2 = (Y - y) / len(X)
dW2, db2 = H.T @ dZ2, dZ2.sum(axis=0)
dZ1 = (dZ2 @ W2.T) * H * (1 - H) # back-propagate through the sigmoid
dW1, db1 = X.T @ dZ1, dZ1.sum(axis=0)
# gradient descent step
W1 -= lr * dW1; b1 -= lr * db1
W2 -= lr * dW2; b2 -= lr * db2
print(round(loss, 4)) # 0.0014
print(Y.round(3).ravel()) # [0.001 0.999 0.998 0.002]2. The back-propagation example, checked numerically
The same numbers as the by-hand widget, and a check that the back-propagated gradient equals the numerical derivative \(\frac{E(w + \varepsilon) - E(w - \varepsilon)}{2\varepsilon}\).
backprop_by_hand.py Python
import math
def sig(z):
return 1 / (1 + math.exp(-z))
W = {"13": 0.4, "23": -0.6, "14": 0.7, "24": 0.2, "35": 0.5, "45": -0.3,
"b3": 0.1, "b4": -0.2, "b5": 0.3}
a1, a2, y, alpha = 1.0, 0.5, 1.0, 0.5
def forward(W):
a3 = sig(W["13"] * a1 + W["23"] * a2 + W["b3"])
a4 = sig(W["14"] * a1 + W["24"] * a2 + W["b4"])
a5 = sig(W["35"] * a3 + W["45"] * a4 + W["b5"])
return a3, a4, a5, 0.5 * (y - a5) ** 2
a3, a4, a5, E = forward(W)
d5 = (y - a5) * a5 * (1 - a5) # output delta: Err * g'(in5)
d3 = a3 * (1 - a3) * W["35"] * d5 # hidden deltas: g'(in_j) * W_j5 * d5
d4 = a4 * (1 - a4) * W["45"] * d5
print(round(E, 5), round(d5, 5), round(d3, 5), round(d4, 5))
# 0.08235 0.09786 0.01211 -0.00672
grad = {"35": -a3 * d5, "45": -a4 * d5, "b5": -d5,
"13": -a1 * d3, "23": -a2 * d3, "b3": -d3,
"14": -a1 * d4, "24": -a2 * d4, "b4": -d4}
eps = 1e-6
for k in W: # numerical check of every gradient
Wp, Wm = dict(W), dict(W)
Wp[k] += eps; Wm[k] -= eps
numeric = (forward(Wp)[3] - forward(Wm)[3]) / (2 * eps)
assert abs(numeric - grad[k]) < 1e-8
W = {k: W[k] - alpha * grad[k] for k in W} # one gradient descent step
print(round(forward(W)[3], 5)) # 0.07419: the error went down3. scikit-learn: the MLP from the visual guide
The guide's settings: hidden layers (3, 2), ReLU, plain SGD with learning rate 0.1, no momentum, 1000 epochs. On our 8-point golf data the result depends on the random initial weights, which is a small demonstration of local minima.
sklearn_mlp.py Python
import numpy as np
from sklearn.neural_network import MLPClassifier
# (temperature, humidity) on a 0-3 scale -> play golf? (1 = yes)
X = np.array([[0, 0], [3, 0], [0, 3], [3, 3], [1, 1], [2, 1], [1, 2], [2, 2]], dtype=float)
y = np.array([0, 0, 0, 0, 1, 1, 1, 1])
for seed in range(6):
mlp = MLPClassifier(hidden_layer_sizes=(3, 2), activation="relu", solver="sgd",
learning_rate_init=0.1, momentum=0, max_iter=1000, random_state=seed)
mlp.fit(X, y)
print(seed, mlp.score(X, y))
# 0 0.5
# 1 0.5
# 2 0.75
# 3 1.0 <- this start reaches a perfect fit
# 4 1.0
# 5 0.625
print([w.shape for w in mlp.coefs_]) # [(2, 3), (3, 2), (2, 1)]: 14 weights (+ 6 biases)4. The digit recogniser from this page
digits_mlp.py Python
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split
from sklearn.neural_network import MLPClassifier
X, y = load_digits(return_X_y=True) # 1797 images, 8 x 8 = 64 values 0..16
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.25, random_state=0, stratify=y)
mlp = MLPClassifier(hidden_layer_sizes=(16,), activation="logistic",
alpha=1e-3, max_iter=2000, random_state=1)
mlp.fit(X_tr / 16, y_tr) # scale the inputs to 0..1
print(mlp.score(X_te / 16, y_te)) # 0.98
print(mlp.coefs_[0].shape) # (64, 16): the 16 weight imagesSummary: key takeaways
- Most brains have lots of neurons; each neuron ≈ a linear–threshold unit (?): \(a = g(\sum_j w_j x_j + b)\).
- Perceptrons (one-layer networks) are insufficiently expressive: they represent only linear separators, so no XOR.
- Multilayer networks are sufficiently expressive (universal with one hidden layer, but possibly exponentially large; depth helps). The hidden layers learn features that make the problem linearly separable.
- They are trained by gradient descent, with derivatives computed by error back-propagation: \(\Delta_j = g'(in_j) \sum_i W_{j,i} \Delta_i\), \(W_{k,j} \leftarrow W_{k,j} + \alpha\, a_k \Delta_j\). Smooth activations (sigmoid, tanh, ReLU) make this possible; a hard threshold does not.
- Typical problems: choosing the learning rate, slow convergence, local minima, and hypotheses that are hard to understand.
- Many applications: speech, driving, handwriting, fraud detection, etc. The engineering, cognitive modelling and neural system modelling subfields have largely diverged.
25 auto-graded tasks, 100 points: neurons and activation functions, perceptrons and XOR, hidden layers, architectures and parameter counts, the forward pass, gradient descent and the learning rate, back-propagation and training.