Neural Networks

The Linear Models unit ended on a limitation: however we squash a linear score, the decision boundary underneath stays a flat hyperplane. Until now we chose features first, then fit a linear model on top; a neural network learns the features and the final combination simultaneously. A nonlinear function between linear maps lets the model represent curved decision boundaries, and the chain rule lets us train the resulting composition with gradient descent.

Why Linear Models Are Not Enough

The smallest dataset that defeats a linear model has four points. XOR labels the corners of the unit square by whether exactly one of the two coordinates is \(1\): \[ (0,0) \mapsto 0, \qquad (1,0) \mapsto 1, \qquad (0,1) \mapsto 1, \qquad (1,1) \mapsto 0. \]

The four XOR points have alternating labels at the corners of a square, so no straight line separates the two classes.

Claim: No linear decision boundary separates the XOR labels.

Proof of Claim Suppose some line \(w_1 x_1 + w_2 x_2 + b = 0\) correctly separated the two classes, positive on the label-\(1\) side. Then \(w_1\cdot 1 + w_2 \cdot 0 + b > 0\) and \(w_1 \cdot 0 + w_2 \cdot 1 + b > 0\) (both label-\(1\) points), while \(w_1\cdot 0+w_2\cdot 0+b < 0\) and \(w_1\cdot 1+w_2\cdot 1+b<0\) (both label-\(0\) points). Adding the two label-\(1\) inequalities gives \(w_1+w_2+2b > 0\). Adding the two label-\(0\) inequalities gives \(w_1+w_2+2b < 0\). These two conclusions contradict each other, so no such line exists.

We prove the claim at the board in class; the proof is also in the block above. In the plot, each dashed line we might try leaves a teal label-\(1\) point on the same side as a cardinal label-\(0\) point. The fix is to give the model several cuts, plus something nonlinear to combine them with. Last lecture’s closing example, two interleaved spirals, fails the same way; we come back to those once we have a model that can handle them.

A Neuron: Linear Map Plus Nonlinearity

A neuron is a linear map followed by a nonlinearity. On an input \(\mathbf{x} \in \mathbb{R}^d\) it computes the single number \[ a\big(\langle\mathbf{w},\mathbf{x}\rangle + b\big), \] where \(\mathbf{w}\in\mathbb{R}^d\) is a weight vector, \(b\in\mathbb{R}\) is a bias, and \(a:\mathbb{R}\to\mathbb{R}\) is the activation function, fixed in advance rather than learned. Three common choices:

  • ReLU: \(a(z) = \max(0, z)\), zero for negative inputs and the identity for positive ones.
  • Sigmoid: \(a(z) = \sigma(z) = \frac{1}{1+e^{-z}}\), the squashing function from last lecture.
  • Tanh: \(a(z) = \tanh(z)\), shaped like the sigmoid but centered at \(0\) and ranging over \((-1,1)\).
Sigmoid, hyperbolic tangent, and rectified linear activation functions shown across the same input range.

In the plot, all three curves are flat on the left and rising on the right. The sigmoid and tanh flatten out, so their derivatives fall to nearly zero once \(|z|\) is large, while ReLU keeps rising with slope \(1\) and bends only at \(z=0\). That flat side is useful for representation, but its zero derivative can also hide a bad solution from gradient descent. Problem 11 makes the distinction concrete on XOR.

(The step function \(a(z) = \mathbb{1}[z \geq 0]\) directly encodes which side of the line contains the input, but its derivative is zero everywhere it is defined. ReLU makes the same split while remaining differentiable almost everywhere.)

One neuron is still one cut with a bend at the end, no more expressive than logistic regression; everything beyond a hyperplane has to come from combining neurons.

Stacking Neurons into a Network

A layer applies many neurons to the same input at once, a matrix multiplication followed by an elementwise activation, and a multi-layer perceptron (MLP) feeds each layer’s outputs into the next as inputs. Writing \(\mathbf{h}^{(0)} = \mathbf{x}\) for the input and indexing layers with a parenthesized superscript, the network of \(L\) layers is defined by \[ \mathbf{h}^{(l)} = a\big(\mathbf{W}^{(l)}\mathbf{h}^{(l-1)} + \mathbf{b}^{(l)}\big), \qquad l = 1, \ldots, L, \] where layer \(l\) has \(d_l\) neurons, weight matrix \(\mathbf{W}^{(l)} \in \mathbb{R}^{d_l \times d_{l-1}}\), bias \(\mathbf{b}^{(l)} \in \mathbb{R}^{d_l}\), and an activation applied to each entry separately. The input layer has \(d_0 = d\) features; the last layer usually skips the activation so its output can be a real number (regression) or logits (classification, handed to last lecture’s softmax); every weight and bias is a parameter we train.

A multilayer perceptron sends inputs forward through two layers and propagates derivatives backward along the same connections.

In the diagram, the gray pills are the input’s coordinates, the teal pills are neurons, and the teal edges the entries of the two weight matrices; the teal arrow is the forward pass turning \(\mathbf{x}\) into \(\hat y\), the cardinal arrow the backward pass we build in a moment, running the same edges in reverse.

Here is a network of exactly that shape, small enough to solve XOR by hand: \[ h_1 = \mathrm{ReLU}(x_1+x_2), \qquad h_2 = \mathrm{ReLU}(x_1+x_2-1), \qquad \hat y = h_1 - 2h_2 . \] Check all four corners:

\((x_1,x_2)\) \(h_1\) \(h_2\) \(\hat y = h_1-2h_2\) XOR label
\((0,0)\) \(0\) \(0\) \(0\) \(0\)
\((1,0)\) \(1\) \(0\) \(1\) \(1\)
\((0,1)\) \(1\) \(0\) \(1\) \(1\)
\((1,1)\) \(2\) \(1\) \(0\) \(0\)

Can you find a different pair of hidden neurons that also solves it?

Two hidden neurons divide the plane into regions that let a neural network classify all four XOR corners correctly.

In the left panel, the shading is the network’s output over the whole square, with teal triangles at the label-\(1\) corners and cardinal circles at the label-\(0\) corners. Each hidden neuron contributes one crease, and the two creases together fold the flat output into a ridge running along the anti-diagonal. Both hidden neurons see the input only through the sum \(x_1+x_2\), so the output does too, and the right panel plots it against that sum: a tent that climbs from \(0\), peaks at height \(1\) when \(x_1+x_2=1\), and falls back through \(0\) at \(x_1+x_2=2\). The four corners land at heights \(0,1,1,0\), which is XOR.

The universal approximation theorem makes this intuition precise: one hidden layer of sufficient width can approximate any continuous function on a bounded domain to any accuracy. The theorem does not say how many neurons that takes, or whether gradient descent will find them. Problem 11 holds the architecture fixed and asks whether the ability to represent XOR prevents training from getting stuck. The same ReLU that builds the two creases above also has a flat side through which backpropagation sends no signal.

Training still requires a gradient through several composed functions.

The Chain Rule, Reviewed

Training a network still means gradient descent on a loss \(\mathcal{L}\), now a deep composition of functions rather than one linear map. Recall the chain rule for a scalar composition \(f(g(x))\): \[ \frac{\partial f}{\partial x} = \frac{\partial f}{\partial g}\cdot\frac{\partial g}{\partial x}. \] When \(f\) depends on \(x\) through \(m\) intermediate values \(g_1(x), \ldots, g_m(x)\), the multivariate chain rule collects one term per route from the input to the output: \[ \frac{\partial f}{\partial x} = \sum_{i=1}^m \frac{\partial f}{\partial g_i}\cdot\frac{\partial g_i}{\partial x}. \] A nudge to \(x\) reaches \(f\) along \(m\) separate paths, each multiplying the nudge by the sensitivities of its own links, and the total effect is the sum over all of them. For a layer with vector inputs and outputs, each scalar factor in the chain rule becomes a matrix.

Backpropagation applies the rule systematically: compute and store every intermediate value on a forward pass, then walk backward through the network, computing each layer’s gradients from those already computed one layer downstream.

Backpropagation by Hand

We run both passes on one input, as we will at the board. Take a \(2\)-input, \(2\)-hidden-neuron, \(1\)-output network with weights \[ \mathbf{W}^{(1)} = \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}, \quad \mathbf{b}^{(1)} = \begin{bmatrix}0\\0\end{bmatrix}, \quad \mathbf{w}^{(2)} = \begin{bmatrix}1 \\ -1\end{bmatrix}, \quad b^{(2)} = 0, \] writing the single output neuron’s weights as a vector \(\mathbf{w}^{(2)}\in\mathbb{R}^2\) rather than a \(1\times 2\) matrix. Take input \(\mathbf{x} = (1,2)\), target \(y=1\), and squared error as the loss: \[ \mathcal{L} = (\hat y - y)^2 . \]

Forward pass. Push the input through the first layer and then the ReLU, writing \(\mathbf{z}^{(1)}\) for the pre-activations and \(\mathbf{h}\) for the hidden activations: \[ \mathbf{z}^{(1)} = \mathbf{W}^{(1)}\mathbf{x} + \mathbf{b}^{(1)} = \begin{bmatrix}1\cdot1 + (-1)\cdot 2 \\ 1\cdot 1 + 1\cdot 2\end{bmatrix} = \begin{bmatrix}-1\\3\end{bmatrix}, \qquad \mathbf{h} = \mathrm{ReLU}(\mathbf{z}^{(1)}) = \begin{bmatrix}0\\3\end{bmatrix}. \] Combine the two hidden activations with the output weights, and the loss follows: \[ \hat y = \langle \mathbf{w}^{(2)}, \mathbf{h}\rangle + b^{(2)} = 1\cdot 0 + (-1)\cdot 3 = -3, \qquad \mathcal{L} = (-3-1)^2 = 16. \]

Backward pass. Start at the output, where the derivative of the loss is immediate: \[ \frac{\partial \mathcal{L}}{\partial \hat y} = 2(\hat y - y) = 2(-3-1) = -8 . \] Push that number through the output layer, once for the weights it multiplied and once for the activations it multiplied: \[ \nabla_{\mathbf{w}^{(2)}} \mathcal{L} = \frac{\partial \mathcal{L}}{\partial \hat y}\cdot \mathbf{h} = -8 \begin{bmatrix}0\\3\end{bmatrix} = \begin{bmatrix}0\\-24\end{bmatrix}, \qquad \nabla_{\mathbf{h}} \mathcal{L} = \frac{\partial \mathcal{L}}{\partial \hat y}\cdot \mathbf{w}^{(2)} = -8\begin{bmatrix}1\\-1\end{bmatrix} = \begin{bmatrix}-8\\8\end{bmatrix}. \] The weight gradient scales each output weight’s update by the hidden activation it multiplied. The activation gradient multiplies the output error by the same weights.

Next, push through the ReLU, whose derivative is \(1\) where \(z^{(1)}_i > 0\) and \(0\) where \(z^{(1)}_i < 0\), so the gradient is masked entry by entry: \[ \nabla_{\mathbf{z}^{(1)}}\mathcal{L} = \nabla_{\mathbf{h}}\mathcal{L} \odot \begin{bmatrix}\mathbb{1}[z_1^{(1)}>0]\\\mathbb{1}[z_2^{(1)}>0]\end{bmatrix} = \begin{bmatrix}-8\\8\end{bmatrix}\odot\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}0\\8\end{bmatrix}, \] where \(\odot\) is entrywise multiplication. The first hidden neuron was inactive (\(z_1^{(1)}=-1<0\)), so its gradient is zero and every weight feeding it remains unchanged through this step. The Depth-enablers lecture studies how repeated zero or small derivatives affect deep networks.

Finally, push through the first layer: \[ \nabla_{\mathbf{W}^{(1)}}\mathcal{L} = (\nabla_{\mathbf{z}^{(1)}}\mathcal{L})\,\mathbf{x}^\top = \begin{bmatrix}0\\8\end{bmatrix}\begin{bmatrix}1 & 2\end{bmatrix} = \begin{bmatrix}0&0\\8&16\end{bmatrix}, \qquad \nabla_{\mathbf{b}^{(1)}}\mathcal{L} = \nabla_{\mathbf{z}^{(1)}}\mathcal{L} = \begin{bmatrix}0\\8\end{bmatrix}. \] That last weight gradient is an outer product, the object the Linear Algebra lecture built out of one column and one row: entry \((i,j)\) is neuron \(i\)’s incoming error times input \(j\). These four arrays are everything one gradient descent step needs: subtract \(\alpha\) times each from the corresponding parameter.

We used squared error to keep the arithmetic small; for classification only the first line changes. The last layer produces a vector of logits \(\mathbf{z}\), whose starting gradient was derived last lecture: \[ \nabla_{\mathbf{z}}\mathcal{L} = \mathbf{p} - \mathbf{y} , \] where \(\mathbf{p} = \mathrm{softmax}(\mathbf{z})\) is the predicted distribution over classes and \(\mathbf{y}\) is the one-hot label. Softmax minus one-hot replaces the scalar output derivative above; the rest of the backward pass is unchanged. The demo uses this classification gradient.

The Matrix View

Every step of both passes was a matrix operation, and none depended on having exactly two neurons per layer. Take any two adjacent layers: write \(\mathbf{u}\in\mathbb{R}^{d_{l-1}}\) for the input to a layer, \(\mathbf{W}\in\mathbb{R}^{d_l\times d_{l-1}}\) for its weights, and \(\mathbf{v} = \mathbf{W}\mathbf{u}\in\mathbb{R}^{d_l}\) for its output (the activation only contributes the elementwise mask we saw above). Differentiate entry by entry, using the multivariate chain rule for the input and the single route for a weight: \[ \begin{align*} \frac{\partial \mathcal{L}}{\partial u_j} &= \sum_{i=1}^{d_l} \frac{\partial \mathcal{L}}{\partial v_i}\,\frac{\partial v_i}{\partial u_j} = \sum_{i=1}^{d_l} \frac{\partial \mathcal{L}}{\partial v_i}\,[\mathbf{W}]_{i,j} = \big[\mathbf{W}^\top \nabla_\mathbf{v}\mathcal{L}\big]_j , \\ \frac{\partial \mathcal{L}}{\partial [\mathbf{W}]_{i,j}} &= \frac{\partial \mathcal{L}}{\partial v_i}\,\frac{\partial v_i}{\partial [\mathbf{W}]_{i,j}} = \frac{\partial \mathcal{L}}{\partial v_i}\, u_j = \big[(\nabla_\mathbf{v}\mathcal{L})\,\mathbf{u}^\top\big]_{i,j} . \end{align*} \] The first line sums one route per downstream entry \(v_i\); the second has a single route, because the weight \([\mathbf{W}]_{i,j}\) touches the loss only through \(v_i\), and its entries assemble into an outer product. In vector form, the two gradients are: \[ \nabla_{\mathbf{u}}\mathcal{L} = \mathbf{W}^\top \nabla_{\mathbf{v}}\mathcal{L}, \qquad \nabla_{\mathbf{W}}\mathcal{L} = (\nabla_{\mathbf{v}}\mathcal{L})\,\mathbf{u}^\top , \] exactly the pattern of the hand computation above, now for layers of any width.

The forward pass through the layer costs \(O(d_l d_{l-1})\), one multiply-add per weight, and the backward pass costs the same twice over, so backpropagation delivers the gradient of every parameter for a small constant factor times one forward pass. The obvious alternative, nudging one parameter and re-running the network to see what happens to the loss, costs a full forward pass per parameter, which for a modern network means billions of forward passes for one gradient step. Both directions are also matrix operations, precisely the computation graphics hardware was built to do quickly (backpropagation dates to the 1980s; GPUs, built for rendering, made training at useful scale affordable).

Learned Decision Regions

The demo trains this architecture, full-batch and with no autodiff library, on the spirals from the opening and plots the nonlinear decision region.

The wider network uses the same derivation as the \(2\)-\(2\)-\(1\) network, with larger matrices. Composing linear maps with ReLUs makes the loss non-convex in the parameters, so the Optimization lecture’s convex-bowl guarantee no longer applies. Gradient descent often finds useful parameters despite that non-convexity, as the demo shows on the spiral data.

Scaling the Training Procedure

Hand-deriving every partial derivative and evaluating every step on the full dataset do not scale to larger problems. Next lecture introduces automatic differentiation and estimates the full gradient from a batch using the Monte Carlo method from Unit 1. The dead neuron in our hand computation illustrates a problem that grows with depth; the Depth-enablers lecture explains why and introduces ways to preserve gradients.

A neural network composes linear maps with simple nonlinearities, and the chain rule computes its gradient for a small constant multiple of the cost of a forward pass.