Machine Learning from First Principles

Chapter 15 · Part IV: Deep Learning

Neural Networks

After this chapter you will be able to

  • Explain why stacking linear layers needs nonlinear activations, using the XOR problem.
  • Write the forward pass of a multilayer perceptron in matrix form for a mini-batch.
  • Derive backpropagation for a two-layer network and explain why it costs about as much as the forward pass.
  • Choose activation functions and initialize weights to preserve signal variance.
  • Verify gradients numerically and train a network with mini-batch SGD or Adam.
  • Use automatic differentiation in PyTorch.

15.1From Linear Models to Neural Networks

Every model so far computed a linear score $\vw\T\vx+b$ of fixed features. Its decision boundary is a hyperplane, so it cannot solve even simple problems such as XOR: label the four points $(\pm1,\pm1)$ positive when the two coordinates have the same sign. No line separates them.

Chapter 4 gave one fix: hand-designed features such as $x_1x_2$ make XOR linearly separable. Neural networks automate this. Instead of designing features, we learn them: a first layer computes many features $h_k=\phi(\vw_k\T\vx+b_k)$, each a linear score passed through a fixed nonlinear function $\phi$, and a second layer computes a linear model of those features. Both layers are trained together by gradient descent.

Why the nonlinearity is essential. Without $\phi$, two linear layers collapse into one: $\mW_2(\mW_1\vx+\vb_1)+\vb_2=(\mW_2\mW_1)\vx+(\mW_2\vb_1+\vb_2)$, still a linear function. Any depth of purely linear layers is just one linear layer. The nonlinearity is what makes depth meaningful.

A historical note. The perceptron (Section 6.6) was a single linear unit with a step-function output, trained by a simple error-correcting rule. Its inability to represent XOR, publicized in 1969, contributed to a long decline of interest in neural networks, which ended when backpropagation made multilayer networks trainable (Rumelhart et al. 1986).

15.2The Multilayer Perceptron

A multilayer perceptron (MLP), or fully connected feed-forward network, with $L$ layers computes

$$\vh^{(0)}=\vx,\qquad \vz^{(l)} = \mW^{(l)}\vh^{(l-1)}+\vb^{(l)},\qquad \vh^{(l)} = \phi\big(\vz^{(l)}\big),\quad l=1,\dots,L-1, \tag{15.1}$$

and an output layer $\vz^{(L)}=\mW^{(L)}\vh^{(L-1)}+\vb^{(L)}$ followed by the output function appropriate to the task: identity for regression, sigmoid for binary classification, softmax for $K$ classes (Chapter 6). The vectors $\vh^{(l)}$ are the hidden layers, and their sizes (the widths) are hyperparameters. If layer $l$ has $m_l$ units, then $\mW^{(l)}\in\R^{m_l\times m_{l-1}}$.

Mini-batches as matrices. With a batch of $B$ examples stacked as rows of $\mX\in\R^{B\times d}$, the same computation is $\mathbf{Z}^{(l)}=\mathbf{H}^{(l-1)}\mW^{(l)\top}+\mathbf 1\vb^{(l)\top}$, a single matrix multiplication per layer. Neural network computation is overwhelmingly matrix multiplication, which is why GPUs, built for exactly that, made deep learning practical.

Activation functions.

Name$\phi(z)$$\phi'(z)$
Sigmoid$1/(1+e^{-z})$$\phi(z)(1-\phi(z))\le\frac14$
Tanh$\tanh z$$1-\tanh^2z\le1$
ReLU$\max(0,z)$$\mathbb 1[z>0]$
GELU$z\,\Phi(z)$ ($\Phi$: standard normal CDF)smooth, close to ReLU

Sigmoid and tanh saturate: for large $|z|$ their derivatives are nearly zero, and gradients passing through many such layers shrink geometrically (the vanishing gradient problem). ReLU does not saturate for positive inputs, is cheap, and made deep networks much easier to train; it is the default for MLPs and convolutional networks. Transformers usually use GELU or related smooth variants (Chapter 19).

How expressive are MLPs? The universal approximation theorem (Cybenko 1989) states that a network with a single hidden layer and enough units can approximate any continuous function on a bounded domain to any accuracy. For ReLU networks this is intuitive: each hidden unit contributes a “hinge,” and a sum of hinges can approximate any curve piece by piece. The theorem says nothing about how many units are needed or whether gradient descent will find the weights; in practice, deeper networks represent many functions far more efficiently than wide shallow ones, because each layer can build on the features of the previous one.

15.3Backpropagation

Training uses gradient descent, so we need the gradient of the loss with respect to every weight. Backpropagation computes all of them in one backward sweep using the chain rule (Section 2.3).

Computational graphs

Any computation can be drawn as a directed graph whose nodes are intermediate values and whose edges are elementary operations. The forward pass evaluates the graph from inputs to loss. The backward pass visits the nodes in reverse order and computes, for each node $v$, the adjoint $\bar v=\partial\Loss/\partial v$. If $v$ feeds into nodes $u_1,\dots,u_k$, the chain rule gives

$$\bar v = \sum_{i=1}^k \bar u_i\,\pd{u_i}{v} . \tag{15.2}$$

Each node needs only the adjoints of its direct children and its own local derivatives. Every intermediate value is reused, which makes the backward pass cost a small constant times the forward pass, regardless of the number of parameters. Computing each partial derivative separately by finite differences would instead cost one forward pass per parameter: billions of passes for a large model.

Backpropagation for a two-layer network

Take one hidden layer with activation $\phi$, a softmax output, and cross-entropy loss, for a mini-batch $\mX\in\R^{B\times d}$ with one-hot labels $\mathbf Y\in\R^{B\times K}$:

$$\begin{aligned}\mathbf Z_1 &= \mX\mW_1 + \vb_1\T, & \mathbf H &= \phi(\mathbf Z_1), \\ \mathbf Z_2 &= \mathbf H\mW_2 + \vb_2\T, & \mathbf P &= \softmax(\mathbf Z_2), \\ \Loss &= -\frac1B\sum_{i,k}Y_{ik}\log P_{ik} . &&\end{aligned}$$

(Here, to match code, $\mW_1\in\R^{d\times m}$ and $\mW_2\in\R^{m\times K}$ multiply from the right.) Working backward, using Equation (6.7) for the output layer:

$$\begin{aligned}\bar{\mathbf Z}_2 &= \tfrac1B(\mathbf P-\mathbf Y),\end{aligned} \tag{15.3}$$ $$\begin{aligned}\bar\mW_2 &= \mathbf H\T\bar{\mathbf Z}_2, \qquad \bar\vb_2 = \textstyle\sum_i(\bar{\mathbf Z}_2)_{i,:},\end{aligned} \tag{15.4}$$ $$\begin{aligned}\bar{\mathbf H} &= \bar{\mathbf Z}_2\mW_2\T,\end{aligned} \tag{15.5}$$ $$\begin{aligned}\bar{\mathbf Z}_1 &= \bar{\mathbf H}\odot\phi'(\mathbf Z_1),\end{aligned} \tag{15.6}$$ $$\begin{aligned}\bar\mW_1 &= \mX\T\bar{\mathbf Z}_1, \qquad \bar\vb_1 = \textstyle\sum_i(\bar{\mathbf Z}_1)_{i,:}.\end{aligned} \tag{15.7}$$

Here $\odot$ is element-wise multiplication. Each line is the chain rule applied to one operation:

  • For a matrix product $\mathbf C=\mA\mB$, the adjoints are $\bar\mA=\bar{\mathbf C}\mB\T$ and $\bar\mB=\mA\T\bar{\mathbf C}$. (Check the shapes: they must match $\mA$ and $\mB$.) This gives Equations (15.4), (15.5), and (15.7).
  • An element-wise function multiplies the incoming adjoint by its derivative element-wise, giving Equation (15.6).
  • A bias added to every row receives the sum of the rows of the adjoint.

Notice the pattern: the gradient of a weight matrix is (input to that layer)$\T$ times (adjoint of that layer’s output). Deeper networks simply repeat Equations (15.5), (15.6), and (15.7) layer by layer.

Gradient checking

Backprop code is easy to get subtly wrong: a missing transpose or a forgotten factor of $1/B$ still produces a model that trains, just badly. Always verify a new implementation against centered finite differences,

$$\pd{\Loss}{\theta_j}\approx\frac{\Loss(\vtheta+h\mathbf e_j)-\Loss(\vtheta-h\mathbf e_j)}{2h},\qquad h\approx10^{-5},$$

on a few random parameters, in double precision. The relative error $|a-b|/\max(|a|,|b|)$ should be around $10^{-7}$ or smaller. Project 3 includes a gradient checker.

15.4Initialization

Symmetry breaking. If all weights start at zero (or any equal value), every hidden unit in a layer computes the same function and receives the same gradient, so they stay identical forever. Initial weights must be random.

Preserving variance. The scale of the random weights matters. Consider $z_i=\sum_{j=1}^{m}W_{ij}h_j$ with independent zero-mean weights of variance $s^2$ and inputs of second moment $\E[h_j^2]=q$. Then $\Var(z_i)=m\,s^2q$. If $m\,s^2>1$, the signal grows by that factor at every layer and explodes in a deep network; if $m\,s^2<1$, it shrinks to nothing. The same argument applies to gradients flowing backward. Two standard choices keep the variance roughly constant:

  • Xavier/Glorot (Glorot and Bengio 2010): $s^2=1/m$ (or $2/(m_{\text{in}}+m_{\text{out}})$), suited to tanh and sigmoid.
  • He/Kaiming (He et al. 2015): $s^2=2/m$, suited to ReLU. The factor 2 compensates for ReLU zeroing half of its inputs: if $z$ is symmetric around zero, $\E[\relu(z)^2]=\frac12\E[z^2]$.

Biases are usually initialized to zero. Normalization layers and residual connections (Chapter 16) make deep networks much less sensitive to initialization, but the principle of preserving signal scale remains central.

15.5Training in Practice

A typical training loop:

  1. Shuffle the training data each epoch and iterate over mini-batches.
  2. Forward pass: compute predictions and the loss.
  3. Backward pass: compute gradients.
  4. Update the parameters with SGD with momentum or Adam (Chapter 3).
  5. Every so often, compute the loss and accuracy on a validation set.

Reading learning curves. Plot training and validation loss against epochs. If both are high and flat, the model underfits or the learning rate is wrong. If training loss keeps falling while validation loss turns upward, the model is overfitting; stop at the validation minimum (early stopping) or add regularization (weight decay, dropout, data augmentation; Chapter 16). A useful first sanity check is to train on a tiny subset (say, 20 examples): a correct implementation should drive the training loss nearly to zero. If it cannot, there is a bug.

The loss landscape. The loss of a neural network is not convex: permuting the hidden units of a layer gives a different weight vector with exactly the same loss, so there are many equivalent minima. Fortunately, for large networks, bad local minima appear to be rare; the practical difficulties are saddle points, plateaus, and poorly conditioned regions, which momentum and adaptive methods handle well.

15.6Automatic Differentiation and PyTorch

Deriving Equations (15.3), (15.4), (15.5), (15.6), and (15.7) by hand is instructive once. In practice, automatic differentiation (autodiff) libraries record the computational graph as the forward pass runs and apply the reverse sweep for you. This is not symbolic differentiation (no formulas are manipulated) and not numerical differentiation (no finite differences): it applies the exact chain rule to the actual operations executed, so it handles loops, branches, and arbitrary code.

import torch
import torch.nn as nn

model = nn.Sequential(
    nn.Linear(2, 32), nn.ReLU(),
    nn.Linear(32, 32), nn.ReLU(),
    nn.Linear(32, 3),                 # logits for 3 classes
)
opt = torch.optim.Adam(model.parameters(), lr=1e-2)
loss_fn = nn.CrossEntropyLoss()       # softmax + cross-entropy, computed stably

X = torch.randn(300, 2)
y = (torch.atan2(X[:, 1], X[:, 0]) * 3 / (2 * torch.pi) + 1.5).long() % 3

for epoch in range(500):
    logits = model(X)                 # forward pass builds the graph
    loss = loss_fn(logits, y)
    opt.zero_grad()                   # clear gradients from the previous step
    loss.backward()                   # reverse-mode autodiff fills p.grad
    opt.step()                        # parameter update
print(f"final loss {loss.item():.3f}")

PyTorch’s nn.Linear uses a default initialization close to the Xavier/He scale, and nn.CrossEntropyLoss takes raw logits and applies log-softmax internally with the stability tricks of Section 6.4.

15.7Why Depth Helps

The universal approximation theorem says that one hidden layer is enough in principle. Why, then, are practical networks deep? Because depth can be exponentially more efficient than width.

Counting linear pieces. A ReLU network computes a continuous piecewise-linear function. On a line, a network with one hidden layer of $m$ ReLU units has at most $m+1$ linear pieces, since each unit contributes one kink. Composition behaves differently: if $f$ has $a$ pieces that each sweep across the whole range of $g$, then $g\circ f$ can have about $a$ times as many pieces as $g$. The tent map on $[0,1]$, built from just two ReLUs,

$$t(x)=2\relu(x)-4\relu\big(x-\tfrac12\big)=\begin{cases}2x, & x\le\frac12,\\ 2-2x, & x>\frac12,\end{cases} \tag{15.8}$$

maps $[0,1]$ onto itself twice. Composing it $k$ times, which is a network of depth $k$ and width 2, gives a sawtooth with $2^k$ linear pieces. A one-hidden-layer network needs at least $2^k-1$ units to represent it exactly, and Telgarsky (2016) proved that it needs exponentially many units even to approximate it: there are functions that deep narrow networks compute easily and shallow networks cannot, a depth separation.

import numpy as np

def tent_layer(h):
    # tent map t(x) = 2x on [0, 1/2], 2 - 2x on [1/2, 1], built from two ReLUs:
    # t(x) = 2 relu(x) - 4 relu(x - 1/2)
    return 2 * np.maximum(h, 0) - 4 * np.maximum(h - 0.5, 0)

def deep_sawtooth(x, k):
    h = x
    for _ in range(k):                 # k layers of 2 ReLU units each
        h = tent_layer(h)
    return h

def count_pieces(y, x):
    slope = np.diff(y) / np.diff(x)
    return 1 + np.sum(np.abs(np.diff(slope)) > 1e-6)

x = np.linspace(0, 1, 2**16 + 1)
for k in [1, 2, 4, 8, 12]:
    print(f"depth {k:2d}: {2 * k:3d} ReLU units -> {count_pieces(deep_sawtooth(x, k), x):5d} linear pieces")
# A one-hidden-layer ReLU network with m units on a line has at most m + 1 pieces,
# so matching depth 12 (4096 pieces) needs at least 4095 hidden units.

Why this matters for real data. Sawtooth functions are artificial, but the mechanism, reusing intermediate results, is what deep networks exploit. Real data are compositional: images are made of objects, objects of parts, parts of textures and edges; sentences of phrases, phrases of words, words of characters. A deep network can compute an edge detector once and reuse it in every part detector, and a part detector once and reuse it in every object detector; a shallow network must represent every combination separately. Empirically, at a fixed parameter budget, deeper networks generalize better on such data, up to the point where optimization becomes the bottleneck. That bottleneck, and the techniques that removed it, are the subject of Chapter 16.

15.8Implementation

Here is the same two-layer network in NumPy, implementing Equations (15.3), (15.4), (15.5), (15.6), and (15.7) directly.

import numpy as np

def init(d, m, K, rng):
    return {"W1": rng.normal(0, np.sqrt(2 / d), (d, m)), "b1": np.zeros(m),
            "W2": rng.normal(0, np.sqrt(1 / m), (m, K)), "b2": np.zeros(K)}

def forward(p, X):
    Z1 = X @ p["W1"] + p["b1"]
    H = np.maximum(Z1, 0)                                # ReLU
    Z2 = H @ p["W2"] + p["b2"]
    Z2 = Z2 - Z2.max(1, keepdims=True)
    P = np.exp(Z2) / np.exp(Z2).sum(1, keepdims=True)    # softmax
    return Z1, H, P

def loss_and_grads(p, X, Y):
    B = X.shape[0]
    Z1, H, P = forward(p, X)
    loss = -np.sum(Y * np.log(P + 1e-12)) / B
    dZ2 = (P - Y) / B                                    # (nn-bp1)
    g = {"W2": H.T @ dZ2, "b2": dZ2.sum(0)}              # (nn-bp2)
    dH = dZ2 @ p["W2"].T                                 # (nn-bp3)
    dZ1 = dH * (Z1 > 0)                                  # (nn-bp4), ReLU'
    g["W1"], g["b1"] = X.T @ dZ1, dZ1.sum(0)             # (nn-bp5)
    return loss, g

def grad_check(p, X, Y, h=1e-5, trials=5, rng=np.random.default_rng(0)):
    _, g = loss_and_grads(p, X, Y)
    for name in p:
        for _ in range(trials):
            idx = tuple(rng.integers(s) for s in p[name].shape)
            old = p[name][idx]
            p[name][idx] = old + h; lp, _ = loss_and_grads(p, X, Y)
            p[name][idx] = old - h; lm, _ = loss_and_grads(p, X, Y)
            p[name][idx] = old
            num = (lp - lm) / (2 * h)
            rel = abs(num - g[name][idx]) / max(1e-12, abs(num) + abs(g[name][idx]))
            assert rel < 1e-5, (name, idx, rel)
    print("gradient check passed")

15.9Common Pitfalls

Pitfall: Forgetting to zero gradients

PyTorch accumulates gradients into .grad. Forgetting opt.zero_grad() sums gradients across steps and silently breaks training.

Pitfall: Applying softmax twice

nn.CrossEntropyLoss expects logits. Passing probabilities (after your own softmax) still runs but trains poorly.

Pitfall: Dead ReLUs

A ReLU unit whose input is negative for every example outputs zero and receives zero gradient, so it never recovers. A learning rate that is too high often kills many units at once. Lower the learning rate or use a leaky variant.

15.10Summary

  • Without nonlinear activations, any stack of linear layers is a single linear map.
  • An MLP alternates affine maps and element-wise nonlinearities; mini-batch computation is matrix multiplication.
  • Backpropagation applies the chain rule in reverse over the computational graph, costing a small multiple of the forward pass. A weight’s gradient is (layer input)$\T$ times (output adjoint).
  • Initialize randomly with variance $1/m$ (Xavier) or $2/m$ (He, for ReLU) to keep signals stable; check gradients numerically.
  • Autodiff libraries such as PyTorch record the graph and compute exact gradients automatically.
  • Depth can be exponentially more efficient than width: $k$ layers of two ReLUs compute a sawtooth with $2^k$ pieces, which a one-hidden-layer network needs $2^k-1$ units to match.

15.11Exercises

  1. MathConstruct by hand a network with two ReLU hidden units that solves XOR on $\{(\pm1,\pm1)\}$.
  2. MathFor $\mathbf C=\mA\mB$ and a scalar loss $\Loss$, show that $\bar\mA=\bar{\mathbf C}\mB\T$ by writing $C_{ik}=\sum_jA_{ij}B_{jk}$ and applying the chain rule entry by entry.
  3. MathShow that if $z\sim\Normal(0,v)$ then $\E[\relu(z)^2]=v/2$, and derive the He initialization variance.
  4. MathIn a network of $L$ sigmoid layers, show that the gradient reaching the first layer contains a product of $L$ factors $\sigma'(z)\le\frac14$. What does this imply for $L=20$?
  5. CodingRun grad_check on the NumPy network, then deliberately introduce a bug (drop the $1/B$, or remove the ReLU derivative) and confirm the checker catches it.
  6. CodingTrain the NumPy network on a three-armed spiral data set with hidden widths 2, 8, and 64. Plot the decision regions. What is the smallest width that fits the training data?
  7. MathShow that a one-hidden-layer ReLU network with $m$ units, viewed as a function of a scalar input, has at most $m+1$ linear pieces. Then prove by induction that the $k$-fold composition of the tent map Equation (15.8) has exactly $2^k$ pieces on $[0,1]$.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.