Machine Learning · Lecture 10a

Lecture 10a
Neural Networks I: What Networks Compute

Part III · Deep learning  |  shallow networks, ReLU networks as piecewise-linear functions, linear regions and hyperplane arrangements, activation functions, composing networks, folding and clipping, deep networks and the power of depth, universal approximation  |  reading: Prince, Understanding Deep Learning, ch. 3–4 (and notebooks 3.1–3.4, 4.1–4.3); Telgarsky (2016)

Cartoon: folding paperA stick figure folds a strip of paper in half, then in half again; a zigzag line is drawn on it. The figure says: two folds, four pieces. A second stick figure says: and with ten folds? Two folds,four pieces. And with tenfolds?
Each layer of a deep ReLU network can fold its input space; the number of pieces doubles with each fold
In this lecture
  1. Shallow networks
  2. Linear regions
  3. Activation functions
  4. Composing networks: folding, clipping and depth
  5. Universal approximation, and what depth buys
  6. Summary, exercises, projects, reading

Logistic regression (Lecture 4) passes a linear function of the inputs through one fixed nonlinearity. A neural network does the same thing many times: it computes many linear functions of the inputs, passes each through a simple nonlinearity, and combines the results linearly; a deep network repeats this in layers, each feeding the next. This lecture asks what functions such networks can represent, before Lecture 10b asks how to train them. With the ReLU nonlinearity the answer is unusually concrete. A ReLU network is a continuous piecewise-linear function, and its power can be measured by counting its linear pieces. Width adds pieces one at a time; depth multiplies them, by folding the input space like paper. A one-hidden-layer network can approximate any continuous function, but some functions that a deep network computes with a handful of units need exponentially many units in one layer.

By the end of this lecture you should be able to write down shallow and deep networks and count their parameters; explain why a ReLU network is piecewise linear and count the pieces of a shallow network in one dimension and the regions in higher dimensions; compare the common activation functions; build clipping and folding functions from ReLUs and explain how composition multiplies linear regions; and state the universal approximation theorem, prove its one-dimensional case, and explain what it does and does not promise.

1 — Shallow networks

definition 10.1 — shallow neural network

A shallow network (one hidden layer) with \(d\) inputs, \(D\) hidden units and one output computes

$$f(x)=\phi_0+\sum_{k=1}^D\phi_k\,a\big(\theta_{k0}+\theta_k^\top x\big),$$

where \(a\) is a fixed nonlinear activation function, \(h_k=a(\theta_{k0}+\theta_k^\top x)\) are the hidden units, \(\theta\) are the first-layer weights and biases, and \(\phi\) the output weights.

It has \(D(d+1)+(D+1)\) parameters. The most common activation is the rectified linear unit,

$$\mathrm{ReLU}(z)=\max(0,z).$$

Each ReLU unit is a "hinge": zero on one side of the point where \(\theta_{k0}+\theta_kx=0\) and linear on the other. A weighted sum of hinges is a continuous piecewise-linear function whose slope changes only where a unit switches on or off. In one dimension the switch points are the joints \(x=-\theta_{k0}/\theta_k\).

proposition 10.1 — shallow ReLU networks are piecewise linear

A shallow ReLU network with one input and \(D\) hidden units is a continuous piecewise-linear function with at most \(D+1\) linear pieces. Conversely, every continuous piecewise-linear function on an interval \([\alpha,\beta]\) with \(D+1\) pieces is computed by such a network with at most \(D+1\) hidden units.

Each unit is linear except at its joint, and a sum of functions that are linear on an interval is linear on it, so \(f\) is linear between consecutive joints: at most \(D\) joints, at most \(D+1\) pieces. It is continuous as a sum of continuous functions.

Conversely, let \(g\) have breakpoints \(\alpha<t_1<\dots<t_D<\beta\), slope \(s_0\) on the first piece and slope change \(c_k\) at \(t_k\). On \([\alpha,\beta]\),

$$g(x)=g(\alpha)+s_0\,\mathrm{ReLU}(x-\alpha)+\sum_{k=1}^{D}c_k\,\mathrm{ReLU}(x-t_k):$$

the first unit supplies the initial slope (it is linear on the whole interval) and each other unit changes the slope at one breakpoint.

That is \(D+1\) units, or \(D\) if the first piece is flat. \(\square\)

Build a shallow network

Three ReLU units (dashed) and their sum plus a constant (sky), on Lecture 1's crash-helmet data. Each unit has a joint, a direction (switching on to the right of the joint, or to the left) and a slope. Try to fit the data by hand, then load the least-squares fit of the code box below.

unit 1
unit 2
unit 3

Three units are exactly the right number for the crash curve: one joint where the head starts to decelerate (about 14 ms), one at the bottom of the dip (21 ms), one where it levels off (30 ms). The widget's slope is the product \(\phi_k|\theta_k|\) of the code's two parameters, which only ever appear multiplied together in one dimension.

code — shallow ReLU networks fitted to the crash-helmet data
import numpy as np, pandas as pd
from scipy.optimize import least_squares

mc = pd.read_csv('../data/mcycle.csv')                     # Lecture 1's crash-helmet data
t, y = mc['times'].to_numpy(), mc['accel'].to_numpy()

def shallow(params, x, D):
    """y = phi_0 + sum_k phi_k ReLU(theta_k0 + theta_k1 x): one input, D hidden ReLU units, one output."""
    th0, th1, phi = params[:D], params[D:2 * D], params[2 * D:]
    H = np.maximum(0, th0[None, :] + th1[None, :] * x[:, None])     # hidden-unit activations, n x D
    return phi[0] + H @ phi[1:]

def fit(D, restarts=100, seed=0):
    rng = np.random.default_rng(seed); best = None
    for r in range(restarts):                               # several random starts: the problem is not convex
        joints = rng.uniform(t.min(), t.max(), D); sign = rng.choice([-1, 1], D)
        p0 = np.concatenate([-sign * joints, sign * 1.0, [y.mean()], rng.normal(0, 1, D)])
        res = least_squares(lambda p: shallow(p, t, D) - y, p0)
        if best is None or res.cost < best.cost:
            best = res
    return best.x

print('hidden units   parameters   training RMSE   joints (ms) where a unit switches on')
for D in [1, 2, 3, 5, 10]:
    p = fit(D)
    rmse = np.sqrt(np.mean((shallow(p, t, D) - y) ** 2))
    joints = np.sort(-p[:D] / p[D:2 * D])
    print(f'{D:12d}   {3 * D + 1:10d}   {rmse:13.2f}   ' + ' '.join(f'{j:.1f}' for j in joints if t.min() <= j <= t.max()))

p20 = fit(10, restarts=20)
print(f'10 units, best of only 20 random starts: training RMSE {np.sqrt(np.mean((shallow(p20, t, 10) - y) ** 2)):.2f}')
hidden units   parameters   training RMSE   joints (ms) where a unit switches on
           1            4           43.31   21.4
           2            7           27.79   23.4 28.4
           3           10           22.56   13.8 21.0 29.8
           5           16           22.40   13.9 14.4 21.0 29.9 40.0
          10           31           22.05   2.5 14.1 17.6 20.0 22.5 29.4
10 units, best of only 20 random starts: training RMSE 26.32

One unit is a single hinge (RMSE 43); two capture the dip (28); three capture the dip and the rebound (22.6). Beyond that the gains are small: five units reach 22.4 and ten 22.0, and the extra joints mostly fine-tune the dip. The last line is a warning for Lecture 10b. Fitting a network is not a convex problem: with only 20 random starting points, the best ten-unit fit found was worse than the three-unit fit, although the ten-unit network can represent every three-unit one. Which minimum the optimiser finds depends on where it starts.

spot check 10.1

A shallow ReLU network has one input and 5 hidden units. What is the largest possible number of linear pieces?

Each unit contributes at most one joint.
\(5+1=6\). Two units with the same joint give fewer; a unit whose joint lies outside the data range adds nothing visible.

2 — Linear regions

With \(d\) inputs, each hidden unit switches on or off across a hyperplane \(\theta_{k0}+\theta_k^\top x=0\) in input space. The \(D\) hyperplanes cut the space into regions; within a region every unit is either on or off, so the network is a single linear function there. The number of regions is the multidimensional version of "number of pieces".

theorem 10.2 — Zaslavsky's count

\(D\) hyperplanes in general position cut \(\mathbb R^d\) into exactly

$$r(D,d)=\sum_{j=0}^d\binom Dj$$

regions. So a shallow ReLU network with \(d\) inputs and \(D\) hidden units has at most

$$\sum_{j=0}^d\binom Dj$$

linear regions, and this number is attained. For \(D\le d\) it is \(2^D\); for fixed \(d\) it grows like \(D^d/d!\).

Add the hyperplanes one at a time. The \(D\)-th hyperplane \(H\) is itself a copy of \(\mathbb R^{d-1}\), and the previous \(D-1\) hyperplanes cut it (in general position) into \(r(D-1,d-1)\) pieces. Each piece of \(H\) splits one existing region into two, so

$$r(D,d)=r(D-1,d)+r(D-1,d-1),$$

with \(r(0,d)=1\) and \(r(D,0)=1\). The binomial sums satisfy the same recursion (Pascal's rule), hence they are equal. This is a special case of Zaslavsky's (1975) theorem on hyperplane arrangements. \(\square\)

Linear regions of a random ReLU network

A ReLU network with 2 inputs, random weights, and the chosen width and depth, drawn on \([-3,3]^2\). Each colour is one activation pattern, that is one linear region. Compare one wide layer with several narrow ones that use the same number of units.

spot check 10.2

At most how many linear regions can a shallow ReLU network with 2 inputs and 4 hidden units have?

\(\binom40+\binom41+\binom42\).
\(1+4+6=11\): four lines in general position cut the plane into 11 regions.

3 — Activation functions

Without a nonlinearity, a network of any depth collapses to a single linear map (a product of matrices is a matrix). The choice of nonlinearity changes both the functions a network represents and, as Lecture 10b shows, how well gradients flow through it during training.

activation\(a(z)\)notes
sigmoid\(1/(1+e^{-z})\)the original choice; saturates at 0 and 1, derivative at most ¼, so gradients shrink through many layers
tanh\(\tanh z\)zero-centred sigmoid; saturates; still used in recurrent networks (Lecture 11)
ReLU\(\max(0,z)\)cheap, no saturation for \(z>0\), piecewise linear; a unit stuck at \(z<0\) for every input gets no gradient ("dead ReLU")
leaky ReLU\(\max(\alpha z,z)\), \(\alpha\approx0.01\)–\(0.1\)keeps a small gradient for \(z<0\)
ELU\(z\) for \(z>0\), \(e^z-1\) otherwisesmooth negative part, outputs closer to zero mean
GELU\(z\,\Phi(z)\), \(\Phi\) the normal CDFa smooth ReLU; the standard in BERT and GPT models
SiLU (swish)\(z\,\sigma(z)\)similar to GELU; used in many vision models and, inside SwiGLU, in Llama-style language models
softplus\(\log(1+e^z)\)smooth version of ReLU; its derivative is the sigmoid

Activation functions and their derivatives

The function (sky) and its derivative (amber, dashed). The derivative is what backpropagation multiplies by at every layer (Lecture 10b), so its size matters as much as the function's shape.

The smooth activations (GELU, SiLU, softplus) are not piecewise linear, so the region-counting picture applies to them only approximately; in practice they behave like softened ReLUs. The sigmoid's derivative is at most 0.25 and is only 0.045 at \(z=-3\), which, multiplied over ten layers, shrinks a gradient by a factor of at least a million. That is the "vanishing gradient" problem that held back deep networks until ReLUs became standard around 2010.

spot check 10.3

The largest value of the sigmoid's derivative is , and the derivative of tanh at 0 is .

Use \(\sigma'=\sigma(1-\sigma)\) and \(\tanh'=1-\tanh^2\); the widget shows both.
\(\sigma'(0)=\tfrac12\cdot\tfrac12=\tfrac14\), and \(\tanh z=2\sigma(2z)-1\) gives \(\tanh'(0)=4\sigma'(0)=1\).
history — from logical neurons to a Nobel Prize

Warren McCulloch and Walter Pitts modelled neurons as threshold logic units in 1943 and showed that networks of them can compute any logical function. Frank Rosenblatt's perceptron (1958, Lecture 4) learned the weights of one such unit. Marvin Minsky and Seymour Papert's Perceptrons (1969) proved what a single layer cannot do (such as XOR, Exercise 1), and with no way to train hidden layers interest collapsed. Backpropagation (Lecture 10b) revived it in the 1980s, and in 1989 George Cybenko and, independently, Kurt Hornik, Maxwell Stinchcombe and Halbert White proved that one hidden layer suffices to approximate any continuous function. The rectifier was used by Kunihiko Fukushima in 1969, but became the default only after Nair and Hinton (2010) and Glorot, Bordes and Bengio (2011). In 2024 John Hopfield and Geoffrey Hinton received the Nobel Prize in Physics "for foundational discoveries and inventions that enable machine learning with artificial neural networks".

4 — Composing networks: folding, clipping and depth

definition 10.2 — deep (fully connected) network

A deep network, or multilayer perceptron, with \(K\) hidden layers computes

$$h^{(0)}=x,\qquad h^{(k)}=a\big(\beta^{(k)}+\Omega^{(k)}h^{(k-1)}\big)\ \ (k=1,\dots,K),\qquad f(x)=\beta^{(K+1)}+\Omega^{(K+1)}h^{(K)},$$

with weight matrices \(\Omega^{(k)}\), bias vectors \(\beta^{(k)}\), and the activation applied entrywise. Layer \(k\) has width \(D_k\) (the length of \(h^{(k)}\)); the depth is \(K\).

It is a composition of shallow networks: the outputs of one layer are the inputs of the next.

Two small ReLU constructions explain what composition does. A clipping function keeps a value inside a range:

$$\operatorname{clip}(z;0,1)=\mathrm{ReLU}(z)-\mathrm{ReLU}(z-1),$$

zero below 0, the identity on \([0,1]\), one above 1. And a fold, the "tent map",

$$T(x)=2\,\mathrm{ReLU}(x)-4\,\mathrm{ReLU}\big(x-\tfrac12\big),$$

maps \([0,\tfrac12]\) up onto \([0,1]\) and \([\tfrac12,1]\) back down onto \([0,1]\): it folds the unit interval in half. Feed its output into a second network \(g\), and \(g\) is applied to both halves of the input, mirrored: whatever \(g\) does on \([0,1]\) now happens twice. Composing \(T\) with itself \(L\) times folds the interval \(L\) times.

Folding with depth

The tent map composed with itself \(L\) times (sky), with the earlier compositions in grey. Each composition is one more layer of two ReLU units.

theorem 10.3 — depth multiplies linear pieces

The \(L\)-fold composition

$$T^{(L)}=T\circ\dots\circ T$$

is computed by a deep ReLU network with \(L\) hidden layers of 2 units and has exactly \(2^L\) linear pieces on \([0,1]\) (a sawtooth with \(2^{L-1}\) teeth).

A shallow ReLU network needs at least \(2^L-1\) hidden units to compute it exactly, and \(2^L\) suffice.

By induction on \(L\): suppose \(T^{(L)}\) has \(2^L\) pieces, each mapping its interval linearly onto all of \([0,1]\) (true for \(L=1\)). Composing with \(T\) splits each piece at the point that maps to \(\tfrac12\), and each half again maps linearly onto \([0,1]\): \(2^{L+1}\) such pieces. Each \(T\) is a layer of two ReLU units (the clipping of the input to \([0,1]\) is automatic since every intermediate value lies in \([0,1]\)).

The lower bound for shallow networks follows from Proposition 10.1: \(2^L\) pieces need \(2^L-1\) joints. \(\square\)

With 10 layers of 2 units (20 units, 61 parameters) the sawtooth has 1,024 pieces; a shallow network needs 1,023 units. Exact representation could be too strict a test, but Telgarsky (2016) proved that depth separations survive approximation: there are functions computed by networks with \(\Theta(k^3)\) layers of constant width that no network with \(O(k)\) layers can approximate (in \(L^1\)) unless it has at least \(2^k\) units. In \(d\) dimensions, Montúfar et al. (2014) showed that a network with \(L\) layers of width \(n\ge d\) can have a number of regions that grows exponentially in \(L\), roughly \((n/d)^{d(L-1)}n^d\).

code — the sawtooth, and what a shallow network needs to match it
# The "tent" fold: a two-unit network mapping [0, 1] onto itself, up and back down
tent = lambda x: 2 * np.maximum(0, x) - 4 * np.maximum(0, x - 0.5)
x = np.linspace(0, 1, 200001)
def pieces(f):                                               # count linear pieces from changes of slope
    s = np.diff(f) / np.diff(x)
    return 1 + int(np.sum(np.abs(np.diff(s)) > 1e-6 * np.abs(s).max()))

f = x.copy()
print('compositions   hidden units   linear pieces')
for L in range(1, 7):
    f = tent(f)
    print(f'{L:12d}   {2 * L:12d}   {pieces(f):13d}')

# A shallow network needs about one unit per piece to match the depth-5 sawtooth (32 pieces)
target = x.copy()
for _ in range(5):
    target = tent(target)
print('\nshallow units (joints evenly spaced, output weights by least squares)   max error')
for D in [8, 16, 30, 31, 63]:
    knots = np.arange(1, D + 1) / (D + 1)
    H = np.column_stack([np.ones_like(x), x] + [np.maximum(0, x - k) for k in knots])
    w = np.linalg.lstsq(H[::50], target[::50], rcond=None)[0]
    print(f'{D:70d}   {np.abs(H @ w - target).max():.4f}')
compositions   hidden units   linear pieces
           1              2               2
           2              4               4
           3              6               8
           4              8              16
           5             10              32
           6             12              64

shallow units (joints evenly spaced, output weights by least squares)   max error
                                                                     8   0.5071
                                                                    16   0.5029
                                                                    30   0.5226
                                                                    31   0.0000
                                                                    63   0.0000

The counts double exactly with each layer. Fitting the depth-5 sawtooth (10 units) with a shallow network whose joints are evenly spaced: 8, 16 or 30 units leave a maximum error of about 0.5, no better than a constant; 31 units, one per joint (plus a linear term, which one more unit would supply), fit it exactly. But exponential counts are a maximum. The code below counts the regions that randomly initialised networks actually create in the plane.

code — how many regions do random networks have?
from math import comb

def regions(widths, seed, R=3.0, m=1500):
    """Count the linear regions of a random ReLU network on [-R, R]^2 by counting distinct
    activation patterns on an m x m grid (a lower bound: tiny regions can be missed)."""
    rng = np.random.default_rng(seed)
    g = np.linspace(-R, R, m); Xg = np.stack(np.meshgrid(g, g), -1).reshape(-1, 2)
    h, codes, d_in = Xg, [], 2
    for w in widths:                                         # He-initialised weights, small random biases
        W = rng.normal(0, np.sqrt(2 / d_in), (d_in, w)); b = rng.normal(0, 0.5, w)
        z = h @ W + b; codes.append(z > 0); h = np.maximum(z, 0); d_in = w
    pattern = np.packbits(np.concatenate(codes, axis=1), axis=1)
    return len(np.unique(pattern, axis=0))

print('architecture                 units   regions found   Zaslavsky maximum for that many units in one layer')
for widths in [[4], [8], [16], [32], [4, 4], [4, 4, 4], [4, 4, 4, 4], [8, 8], [8, 8, 8, 8], [16, 16]]:
    n_units = sum(widths)
    found = np.mean([regions(widths, s) for s in range(3)])
    print(f'{str(widths):26s} {n_units:6d}   {found:13.1f}   {1 + n_units + comb(n_units, 2):10d}')
architecture                 units   regions found   Zaslavsky maximum for that many units in one layer
[4]                             4            10.3           11
[8]                             8            31.3           37
[16]                           16           118.7          137
[32]                           32           433.0          529
[4, 4]                          8            24.7           37
[4, 4, 4]                      12            38.7           79
[4, 4, 4, 4]                   16            44.0          137
[8, 8]                         16            90.7          137
[8, 8, 8, 8]                   32           248.3          529
[16, 16]                       32           415.0          529

Single layers come close to Zaslavsky's maximum (433 regions found for 32 units against 529, some intersections falling outside the window). Deep networks with the same number of units have fewer regions at random initialisation: four layers of 4 units make 44 regions, one layer of 16 makes 119. Hanin and Rolnick (2019) proved that this is typical: for randomly initialised networks, and empirically during training, the number of regions per unit of input volume grows only polynomially with the total number of units, whatever the depth. Depth gives the capacity for exponentially many regions, which training may or may not use; the sawtooth needs carefully coordinated weights. Explore this in the widget of Section 2.

spot check 10.4

The tent map composed 6 times is computed by a network with 6 layers of 2 units. At least how many hidden units does a shallow ReLU network need to compute it exactly?

Count the pieces, then use Proposition 10.1.
\(2^6=64\) pieces need \(63\) joints, so at least 63 units (64 suffice), against 12 in the deep network.
big picture — the multilayer perceptron inside every transformer

The fully connected network of Definition 10.2 is not a museum piece. Every layer of a transformer (Lecture 12) contains a two-layer "feed-forward" MLP applied to each token separately: expand the representation to about four times its width, apply GELU or SwiGLU, project back. These MLP blocks hold about two-thirds of a transformer's parameters (\(8d^2\) of the \(12d^2\) per layer, against \(4d^2\) for attention). Interpretability research reads their hidden units as key–value memories that store facts (Geva et al., 2021). Small MLPs also sit at the end of convolutional networks and inside graph networks (Lecture 9's GIN), and they remain strong baselines for tabular data once well regularised.

5 — Universal approximation, and what depth buys

theorem 10.4 — universal approximation

Let \(a\) be continuous. Shallow networks with activation \(a\) can approximate every continuous function on every compact set \(K\subset\mathbb R^d\) arbitrarily well in the supremum norm (for every \(g\in C(K)\) and \(\varepsilon>0\) there is a shallow network \(f\) with \(\sup_K|f-g|<\varepsilon\)) if and only if \(a\) is not a polynomial (Cybenko, 1989, for sigmoids; Hornik, Stinchcombe and White, 1989; Leshno, Lin, Pinkus and Schocken, 1993, in this form).

Let \(g\) be continuous on \([0,1]\), hence uniformly continuous: for \(\varepsilon>0\) there is \(h\) with

$$|g(x)-g(x')|<\varepsilon/2$$

whenever \(|x-x'|\le h\).

Take knots \(0=k_0<k_1<\dots<k_D=1\) spaced at most \(h\) apart, and let \(f\) be the piecewise-linear interpolant of \(g\) at the knots. By Proposition 10.1, \(f\) is a shallow ReLU network with \(D\) units (here the knot at 0 supplies the initial slope):

$$f(x)=g(0)+\sum_{j=0}^{D-1}\phi_j\mathrm{ReLU}(x-k_j),$$

where \(\phi_0\) is the first slope and \(\phi_j\) the change of slope at \(k_j\).

On each interval \([k_j,k_{j+1}]\), \(f(x)\) lies between \(g(k_j)\) and \(g(k_{j+1})\), each within \(\varepsilon/2\) of \(g(x)\), so \(|f(x)-g(x)|<\varepsilon\). \(\square\)

code — approximating a curve with ReLU units
# Universal approximation in one dimension: a shallow ReLU network that interpolates g at D + 1 knots
g = lambda x: np.sin(2 * np.pi * x) + 0.5 * np.cos(6 * np.pi * x) * x
x = np.linspace(0, 1, 100001)
print('hidden units   max |network - g|   error x units^2')
for D in [4, 8, 16, 32, 64, 128]:
    k = np.linspace(0, 1, D + 1)                             # knots
    slopes = np.diff(g(k)) / np.diff(k)
    phi = np.concatenate([[slopes[0]], np.diff(slopes)])     # each unit changes the slope at its knot
    net = g(0) + sum(p * np.maximum(0, x - kk) for p, kk in zip(phi, k[:-1]))
    err = np.abs(net - g(x)).max()
    print(f'{D:12d}   {err:17.5f}   {err * D**2:15.3f}')
hidden units   max |network - g|   error x units^2
           4             0.81348            13.016
           8             0.29319            18.764
          16             0.08740            22.376
          32             0.02177            22.293
          64             0.00558            22.855
         128             0.00140            22.959

The construction is the proof, and its error falls like \(1/D^2\): error times \(D^2\) settles near 23, in line with the interpolation bound \(\frac{h^2}8\max|g''|\) (Exercise 7). Three cautions keep the theorem in proportion. It is about existence: it says nothing about whether gradient descent will find the weights. It says nothing about the number of units, which for a general \(d\)-dimensional function may have to grow like \(\varepsilon^{-d}\), the curse of dimensionality again. And polynomials, splines, kernels with the RBF kernel and decision trees are universal approximators too. What makes networks special is not universality but which functions they represent efficiently, and the sawtooth shows that depth matters for that.

spot check 10.5

Which statement does the universal approximation theorem support?

What does the theorem assume, and what does it conclude?
It is a density statement: such networks exist. With \(a(z)=z^2\), a shallow network computes only quadratic polynomials, which are not dense in \(C(K)\).
bayes — infinitely wide networks are Gaussian processes

Give a shallow network independent random weights, with output weights scaled by \(1/\sqrt D\). For a fixed input \(x\), the output is a sum of \(D\) independent terms, so by the central limit theorem it becomes Gaussian as \(D\to\infty\), and jointly over any finite set of inputs: the network becomes a Gaussian process (Neal, 1996), with a kernel determined by the activation. For ReLU it is the arc-cosine kernel of Cho and Saul (2009). The same holds layer by layer for deep networks (Lee et al., 2018; Matthews et al., 2018). So the prior over functions that a random wide network represents is exactly one of Lecture 7's Gaussian processes, and exact Bayesian inference with an infinitely wide network is GP regression. Trained finite networks differ from this limit precisely because they learn features, the theme of Lecture 7's neural tangent kernel.

quantum — neural networks as quantum states

A quantum state of \(N\) spins is a vector of \(2^N\) complex amplitudes \(\psi(s)\), one per spin configuration \(s\in\{\pm1\}^N\): far too many to store for \(N\) beyond about 40. Carleo and Troyer (2017) represented \(\psi(s)\) by a neural network that takes the configuration \(s\) as input, a restricted Boltzmann machine with a polynomial number of parameters, and optimised it to minimise the energy by sampling configurations (variational Monte Carlo). These neural-network quantum states matched or beat the best existing methods on ground states of spin models, and have since been extended to deep convolutional and transformer networks for molecules and frustrated magnets. The question of this lecture, which functions a network represents efficiently, becomes a physics question: which entangled states have compact neural representations? Restricted Boltzmann machines with long-range connections can represent states with volume-law entanglement, which tensor-network methods cannot represent compactly (Deng, Li and Das Sarma, 2017).

6 — Summary, exercises, projects, reading

summary

Next: Lecture 10b trains these networks: backpropagation, initialisation, optimisers and regularisation.

exercises 10a
  1. Show that \(\mathrm{ReLU}(z)-\mathrm{ReLU}(-z)=z\), \(|z|=\mathrm{ReLU}(z)+\mathrm{ReLU}(-z)\) and \(\max(u,v)=u+\mathrm{ReLU}(v-u)\). Use them to build a network with two inputs that computes XOR on \(\{0,1\}^2\), which no single linear threshold unit can.

    The identities follow by checking \(z\ge0\) and \(z<0\). XOR: \(f(x_1,x_2)=\mathrm{ReLU}(x_1+x_2)-2\,\mathrm{ReLU}(x_1+x_2-1)\) gives 0, 1, 1, 0 on \((0,0),(0,1),(1,0),(1,1)\). A single threshold unit cannot: its positive set is a half-plane, and the two "1" points have midpoint \((\tfrac12,\tfrac12)\), also the midpoint of the two "0" points, so the classes' convex hulls meet.

  2. Express \(\operatorname{clip}(z;\alpha,\beta)\) for \(\alpha<\beta\) with two ReLUs, and the tent map with two ReLUs, and check that \(T\) maps \([0,1]\) onto itself twice.

    \(\operatorname{clip}(z;\alpha,\beta)=\alpha+\mathrm{ReLU}(z-\alpha)-\mathrm{ReLU}(z-\beta)\). \(T(x)=2\mathrm{ReLU}(x)-4\mathrm{ReLU}(x-\tfrac12)\) equals \(2x\) on \([0,\tfrac12]\) and \(2-2x\) on \([\tfrac12,1]\): each half maps onto \([0,1]\).

  3. Count the parameters of an MLP with 784 inputs, two hidden layers of 256 units and 10 outputs.

    \(784\cdot256+256=200{,}960\); \(256\cdot256+256=65{,}792\); \(256\cdot10+10=2{,}570\). Total 269,322. This is the network Lecture 10b trains on Fashion-MNIST.

  4. Derive \(r(D,2)=1+D+\binom D2\) from the recursion \(r(D,2)=r(D-1,2)+r(D-1,1)\) with \(r(D,1)=D+1\).

    \(r(D,2)=r(0,2)+\sum_{m=0}^{D-1}(m+1)=1+\frac{D(D+1)}2=1+D+\binom D2\). Each new line crosses the previous \(D-1\) lines at \(D-1\) points, cutting it into \(D\) pieces, each of which splits a region.

  5. Show that \(T^{(L)}\) has exactly \(2^L\) linear pieces by a different argument: count the points \(x\in[0,1]\) where \(T^{(L)}(x)=0\) or \(1\).

    \(T^{(L)}(x)\in\{0,1\}\) exactly at the points \(x=j/2^L\), \(j=0,\dots,2^L\) (it equals \(\tfrac12\) at the midpoints between them). Between consecutive such points the function goes monotonically and linearly between 0 and 1, so the pieces are the \(2^L\) intervals \([j/2^L,(j+1)/2^L]\).

  6. Yarotsky (2017) showed that \(x^2=x-\sum_{s\ge1}T^{(s)}(x)/4^s\) on \([0,1]\). Truncating after \(m\) terms gives a deep ReLU network with \(O(m)\) units and error \(2^{-2m-2}\). Check the identity at \(x=\tfrac12\) and \(x=\tfrac14\), and explain why a shallow network needs about \(2^m\) units for the same error.

    At \(x=\tfrac12\): \(T(\tfrac12)=1\), then \(T^{(s)}=0\) for \(s\ge2\), so the right side is \(\tfrac12-\tfrac14=\tfrac14\). At \(x=\tfrac14\): \(T=\tfrac12\), \(T^{(2)}=1\), then 0: \(\tfrac14-\tfrac18-\tfrac1{16}=\tfrac1{16}\). A shallow network is piecewise linear with \(D+1\) pieces, and the best piecewise-linear approximation of \(x^2\) with \(N\) equal pieces has error \(1/(8N^2)\), so error \(2^{-2m-2}\) needs \(N\approx2^{m}/\sqrt2\) pieces.

  7. Show that piecewise-linear interpolation with knot spacing \(h\) has error at most \(\frac{h^2}8\max|g''|\), and compare with the code's \(D^2\times\)error \(\approx23\).

    On \([k,k+h]\), the error \(e=g-f\) vanishes at both ends; by the standard interpolation remainder, \(e(x)=\tfrac12g''(\xi)(x-k)(x-k-h)\), and \(|(x-k)(x-k-h)|\le h^2/4\). With \(h=1/D\), \(D^2\cdot\text{error}\le\max|g''|/8\). For the code's \(g\), \(\max|g''|\approx184\), giving a bound of \(184/8\approx23.0\). The observed 22.96 essentially attains it: for small \(h\), \(g''\) is nearly constant across the knot interval where it is largest, which is exactly when the bound is tight.

  8. Show that \(\mathrm{GELU}(sz)/s\to\mathrm{ReLU}(z)\) as \(s\to\infty\), and that the softplus satisfies \(\log(1+e^{sz})/s\to\mathrm{ReLU}(z)\). What does this say about networks with smooth activations and large weights?

    \(\mathrm{GELU}(sz)/s=z\Phi(sz)\), and \(\Phi(sz)\to1\) for \(z>0\), \(\to0\) for \(z<0\). Softplus: for \(z>0\), \(\log(1+e^{sz})/s=z+\log(1+e^{-sz})/s\to z\); for \(z<0\) it tends to 0. With large weights, smooth-activation networks behave like ReLU networks, so the piecewise-linear picture describes them approximately.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. How many regions do trained networks use?

question
How does the number of linear regions a network uses near its data change during training, and does it predict generalisation?
data
Fashion-MNIST or MNIST, and small tabular datasets.
method
Count regions crossed by line segments between data points (an exact one-dimensional count) and in two-dimensional slices through the data, through training, for networks of varying depth and width; relate to test error and to the predictions of Hanin and Rolnick (2019).
outcome
An empirical map of how trained networks spend their representational capacity, extending published results to new architectures and data.

2. Depth separations in practice

question
When a target function has a compact deep representation (sawtooth, Yarotsky's \(x^2\), parity), do trained deep networks actually find it, and how many samples do shallow and deep networks need?
data
Synthetic targets with known depth requirements, plus a real signal with periodic structure (for example, hourly electricity demand).
method
Train networks of equal parameter count and different depth with several optimisers and initialisations; measure error against sample size and how often training reaches the compact solution.
outcome
Evidence on the gap between what depth can represent and what gradient descent can learn, a central open question.

Reading and sources

Data. Crash-helmet data: B. W. Silverman, JRSS B 47(1), 1–52 (1985), as MASS::mcycle via Rdatasets.

every number in the text and widgets is computed in verify_L10a.py; code-box outputs are pasted from actual runs