Where the chapters meet

STATEMENT

Show that no perceptron computes XOR, that a two-unit ReLU network does, and then backpropagate through that network after one of its weights has been disturbed and take a gradient step.

GIVEN

The four XOR examples: $(0,0)\mapsto0$, $(0,1)\mapsto1$, $(1,0)\mapsto1$, $(1,1)\mapsto0$. The network, with $s=x_1+x_2$:

The loss is the mean squared error over the four examples. For the second part, $v_2=-1.8$ and the step size is $1$.

FIND

Why no threshold unit $\mathbf 1[w_1x_1+w_2x_2+b>0]$ fits the data; the network’s outputs; after disturbing $v_2$, the loss and the gradients with respect to $v_2$, the bias of $h_2$ and the bias of $h_1$; the new $v_2$.

STRATEGY

Write the perceptron’s four conditions as inequalities (I.2). For the network, only the example $(1,1)$ has an error after the disturbance, so the backward pass of I.6 runs through one example.

SOLUTION

No perceptron. The examples require $b\leq0$ for $(0,0)$, $w_2+b>0$ and $w_1+b>0$ for the two positives, and $w_1+w_2+b\leq0$ for $(1,1)$. Adding the middle two gives $w_1+w_2+2b>0$, so $w_1+w_2+b>-b\geq0$, contradicting the last. The positives and negatives are not linearly separable (I.2.P04), and no learning rule changes that.

The network. At $s=0,1,1,2$ the hidden units are $(0,0)$, $(1,0)$, $(1,0)$ and $(2,1)$, so

The ReLU’s kink at $s=1$ is what a linear map cannot supply (I.3.P01): the network bends the line $s$ once and folds the fourth example back to zero.

Disturbed. With $v_2=-1.8$ the last output is $2-1.8=0.2$ and the others are unchanged. The loss is $0.2^2/4=0.01$. The output error is $\delta=2(0.2-0)/4=0.1$ at $(1,1)$ and zero elsewhere, so

One step. Gradient descent moves $v_2$ to $-1.8-1\cdot0.1=-1.9$, back towards $-2$. The gradient supplied the direction and the step size of $1$ was a choice (I.7.P01). Repeating the step halves the remaining error each time: $-1.95$, then $-1.975$, approaching $-2$ without reaching it.

Check — sanity

The gradient with respect to $v_2$ is positive because raising $v_2$ makes the wrong output $0.2$ larger. The script confirms it with a central finite difference.

STATEMENT

Compare the derivative of a quantity $L$ steps downstream with respect to its start, for a saturating stack, a plain recurrence, a gated carry line and a residual stack, and find the limit of each as $L$ grows.

GIVEN

Four scalar chains, each evaluated where its per-step derivative is constant:

• a sigmoid stack at its centre, derivative $\sigma'(0)=0.25$ per step (I.3);
• a recurrence $h_t=\tanh(wh_{t-1})$ near $0$ with $w=0.9$ (I.9);
• an LSTM carry line with forget value $f=0.95$ (I.10);
• a residual stack $x_{l+1}=x_l+a\tanh(x_l)$ near $0$, with $a=+0.05$, $a=-0.05$ or $a=-1$ (I.11).

FIND

Each per-step factor; the product after $L=20$ and $L=100$ steps; the limit as $L\to\infty$; what sets each base.

STRATEGY

By the chain rule (I.6), the derivative across $L$ steps is the product of the per-step derivatives. Each chain here has a constant per-step factor, so each product is a power.

SOLUTION

Per-step factors. The sigmoid stack multiplies by $0.25$. The recurrence by $w\tanh'(0)=0.9$. The carry line by $f=0.95$. The residual stack by $1+a\tanh'(0)=1+a$: $1.05$, $0.95$ or $0$.

Products.

The rows are the sigmoid stack, the recurrence, the carry line and the residual stack with $a=+0.05$.

The residual stack with $a=-0.05$ gives the carry line’s numbers, and with $a=-1$ the product is exactly $0$ after one step.

Limits. Every product of a constant base is geometric: it goes to $0$ when the base is below $1$ in size and grows without bound when it is above. Only a base of exactly $1$ survives every depth. None of the four mechanisms abolishes the geometry; they differ in what sets the base.

What sets each base. In the sigmoid stack it is the activation’s slope, at most $0.25$, so depth alone destroys the signal (I.3.P02). In the recurrence it is a weight times a slope, and pushing it towards $1$ means asking a weight matrix to have norm near one everywhere (I.9.P02). On the carry line it is a learned gate, close to $1$ without any weight matrix being involved (I.10.P02). In the residual stack it is $1$ plus the branch’s slope, near $1$ when the branch is small, and it can be driven to $0$ by a branch that cancels the identity (I.11.X09).

Check — sanity

The carry line keeps $36$ per cent after twenty steps where the plain recurrence keeps $12$ per cent, although its factor differs by only $0.05$: small differences in the base compound.

STATEMENT

For one parameter whose per-example gradients are independent, compare the mean and the variance of a gradient step under a mean reduction and a sum reduction, then change the batch size.

GIVEN

Per-example gradients $g_i$ with mean $\mu$ and variance $\sigma^2=4$, independent across examples. A batch of $B=32$. Learning rate $\eta=0.1$. The step is $-\eta$ times the batch gradient, where the batch gradient is either $\bar g=\tfrac1B\sum g_i$ or $\sum g_i$.

FIND

The variance of each batch gradient; the standard deviation of each step; the learning rate that makes the sum’s step match the mean’s; the mean’s variance at $B=128$.

STRATEGY

Variance scales with the square of a constant and adds over independent terms (Variance and covariance · 0.PR.03).

SOLUTION

Variances. The sum of $B$ independent terms has variance $B\sigma^2=128$. Dividing by $B$ divides the variance by $B^2$: $\operatorname{Var}\bar g=\sigma^2/B=0.125$.

Steps. With $\eta=0.1$ the mean’s step has standard deviation $0.1\sqrt{0.125}=0.035355$ and the sum’s $0.1\sqrt{128}=1.131371$, exactly $B=32$ times larger. Its expected size, $\eta B\mu$, is also $32$ times larger. The two runs are not the same algorithm with different noise; the sum is the mean with a learning rate $32$ times higher.

Matching. The sum’s step equals the mean’s when $\eta_{\text{sum}}=\eta/B=0.003125$. The reduction is part of the loss (I.4.P04): changing it silently changes the learning rate by the batch size.

Larger batch. At $B=128$ the mean’s variance is $4/128=0.03125$, a quarter of the value at $32$. Quadrupling the batch halves the standard deviation of the step and leaves its expected value unchanged. The batch size is a statement about gradient noise (I.7.P02); the direction it estimates does not depend on it.

Check — sanity

The ratio of the two standard deviations is $1.131371/0.035355=32=B$, as the scaling argument requires.

STATEMENT

Let the last element of a sequence of length $64$ depend on the first, and count what a recurrent network, a dilated causal convolution and message passing on the path graph each need to achieve that.

GIVEN

Length $T=64$, width $d=128$. Each architecture uses layers with two $d\times d$ weight matrices and one bias:

• a recurrent layer, $\vec h_t=\tanh(\mat U\vec x_t+\mat W\vec h_{t-1}+\vec b)$ (I.9);
• a causal convolution with kernel width $2$ and dilations $1,2,4,\ldots$, one weight matrix per tap (I.9.P03, I.11);
• a message-passing layer on the path graph $1$–$2$–$\cdots$–$64$, $\mat H'=\sigma(\mat H\mat W_0+\mat A\mat H\mat W_1)$ (I.14).

FIND

Parameters per layer; the number of layers each needs; total parameters; the number of steps that must run one after another.

STRATEGY

A recurrent layer reaches every earlier step. A dilated stack’s receptive field adds the dilation times one less than the kernel width at each layer. Message passing reaches one hop per layer (I.14.T2).

SOLUTION

Per layer. Each has $2d^2+d=2\cdot16{,}384+128=32{,}896$ parameters.

Recurrent. One layer suffices: $\vec h_{64}$ depends on $\vec x_1$ through the state (I.9.P01). Total $32{,}896$ parameters. But step $t$ needs step $t-1$, so $64$ steps run one after another.

Dilated convolution. With kernel width $2$ the receptive field after $L$ layers is $1+(1+2+\cdots+2^{L-1})=2^L$. Reaching $64$ positions takes $L=6$ layers, $197{,}376$ parameters. Every position of a layer can be computed at once, so only $6$ stages run in sequence.

Message passing. Node $64$ is $63$ hops from node $1$, so $63$ layers are needed and $2{,}072{,}448$ parameters, with $63$ stages in sequence. The graph network also lacks what the other two have for free: it cannot tell the node before from the node after (I.14.P02), so it does not even know which end of the path is the start.

Check — sanity

Each count follows from one rule: the recurrence carries state across steps, the dilated stack doubles its reach per layer, and message passing adds one hop per layer. $2^6=64$ and $64-1=63$.

STATEMENT

Fit labels drawn by coin flips exactly with a small ReLU network, compare it with a straight line, and show that the zero training loss predicts nothing about new points.

GIVEN

Inputs $x=0,1,2,3$ with labels $(0,1,0,1)$, which were drawn by fair coin flips. The network is $f(x)=x-2\operatorname{relu}(x-1)+2\operatorname{relu}(x-2)$. The line is the least-squares fit $y=a+bx$. New inputs $0.5$, $1.5$ and $2.5$ get labels from fresh coin flips. Losses are mean squared errors.

FIND

The network’s training loss; the line and its training loss; the expected loss of each, and of the constant $0.5$, on the new points.

STRATEGY

Evaluate the network piece by piece. For a prediction $p$ and a label that is $0$ or $1$ with probability one half, the expected squared error is $(p-\tfrac12)^2+\tfrac14$.

SOLUTION

The network. Its slopes are $1$ before $x=1$, $-1$ between $1$ and $2$, and $1$ after $2$. So $f(0)=0$, $f(1)=1$, $f(2)=0$, $f(3)=1$: the labels exactly, training loss $0$. Two ReLU units and a linear term were enough to put a kink at every change of label (I.5.P02).

The line. With $\bar x=1.5$ and $\bar y=0.5$, the slope is $\sum(x-\bar x)(y-\bar y)/\sum(x-\bar x)^2=1/5=0.2$ and the intercept $0.5-0.2\cdot1.5=0.2$. Its residuals are $-0.2$, $0.6$, $-0.6$ and $0.2$, so its training loss is $0.2$.

New points. The network predicts $0.5$ at all three, so its expected loss is $\tfrac14=0.25$, exactly that of the constant $0.5$. The line predicts $0.3$, $0.5$ and $0.7$, with expected loss $\tfrac13(0.04+0+0.04)+0.25=0.276667$.

So the network with zero training loss does no better than a constant on new points, and the line, which fitted worse, does slightly worse still. Neither number on the training set said anything about the new points, because the labels carried no pattern to learn. That is I.1.P05: the training loss cannot tell memorisation from generalisation.

The same failure, twice more. Chapter I.12 met it in the autoencoder as wide as its input, whose zero loss reconstructed points far from the data just as exactly (I.12.X04), and in the width-one decoder that threaded a curve through every training point (I.12.B04). In all three the capacity to fit was the problem, and only held-out data revealed it.

Check — sanity

No predictor can beat $0.25$ in expectation on fair coin flips, since $(p-\tfrac12)^2+\tfrac14$ is smallest at $p=\tfrac12$. Both the network and the constant reach that floor on these three points.

STATEMENT

Trace every shape through a convolutional variational autoencoder for $28\times28$ images, count its parameters, and find the line of a colleague’s code that would fail.

GIVEN

Encoder: two $3\times3$ convolutions with stride $2$ and padding $1$, from $1$ channel to $16$ and from $16$ to $32$; a flatten; a linear layer to $2k$ numbers with $k=16$, split into $\vec\mu$ and $\log\vec\sigma^2$. Decoder: a linear layer from $k$ back to the flattened size; a reshape; two transposed convolutions with the same kernel, stride and padding and output padding $1$, from $32$ channels to $16$ and from $16$ to $1$. All layers have biases. The colleague wrote the encoder’s linear layer as taking $32\cdot8\cdot8$ inputs.

FIND

Every spatial size; the flattened size; the shapes of $\vec\mu$, $\vec\sigma$, $\vec\varepsilon$ and $\vec z$ for a batch of $B$; each layer’s parameters and the total; the colleague’s error.

STRATEGY

Use (I.11.4) for the convolutions and (I.11.5) for the transposed ones. The reparameterisation of (I.13.6) acts coordinate by coordinate, so it keeps the code’s shape.

SOLUTION

Encoder sizes. $\lfloor(28+2-3)/2\rfloor+1=14$, then $\lfloor(14+2-3)/2\rfloor+1=7$. The feature map is $32\times7\times7$, which flattens to $1{,}568$ numbers.

The code. The linear layer returns $(B,32)$, split into $\vec\mu$ and $\log\vec\sigma^2$, each $(B,16)$. The noise $\vec\varepsilon$ and the code $\vec z=\vec\mu+\vec\sigma\odot\vec\varepsilon$ are $(B,16)$.

Decoder sizes. The linear layer returns $(B,1568)$, reshaped to $(B,32,7,7)$. Each transposed layer gives $(n-1)\cdot2-2+2+1+1=2n$: $7\to14$ and $14\to28$. Without the output padding the sizes would be $13$ and $25$, as I.12.B05 found.

Parameters.

The total is $86{,}433$. Almost nine tenths of it, $76{,}864$, sits in the two linear layers on either side of the code.

The error. $32\cdot8\cdot8=2{,}048$, but the feature map is $7\times7$, so the flattened tensor has $1{,}568$ entries. The matrix product fails at the first batch. The colleague halved $28$ to $14$ and then to $8$, rounding the wrong way; (I.11.4) takes the floor and gives $7$.

The loss. Each example’s reconstruction term sums over $784$ pixels and its KL over $16$ coordinates, both then averaged over the batch. Averaging the reconstruction over pixels as well would train with $\beta=784$ (I.13.X07).

Check — sanity

The decoder’s sizes are the encoder’s read backwards, and its linear layer mirrors the encoder’s with $k$ inputs where the encoder had $2k$ outputs: $26{,}656$ against $50{,}208$.

STATEMENT

Classify the four nodes of the paw graph with one graph convolution and a softmax, derive the gradient with respect to the weights, take one step, and read off what the averaging did to the node whose own features disagree with its neighbours’.

GIVEN

The paw graph of I.14, with $\hat{\mat A}$ from (I.14.5). Node features $\mat X$ have rows $(1,0)$, $(1,0)$, $(0,1)$, $(0,1)$, and the labels are classes $1$, $1$, $2$, $2$. Logits $\mat Z=\hat{\mat A}\mat X\mat W$ with $\mat W=\mat I$ at the start, a softmax on each row, and the mean cross-entropy over the four nodes. Step size $1$.

FIND

$\hat{\mat A}\mat X$; the loss; the gradient $\partial\mathcal L/\partial\mat W$; the loss after one step; each node’s probability of its own class.

STRATEGY

Softmax with cross-entropy has the gradient $\mat P-\mat Y$ with respect to the logits (I.4.P03). Divide by four for the mean, then apply the chain rule for a matrix product (I.6).

SOLUTION

Averaged features. With degrees $(3,3,4,2)$ counted with self-loops,

one row per node. Node $3$‘s row mixes its own class-$2$ feature with two class-$1$ neighbours, and the two entries come out almost equal.

Loss. With $\mat W=\mat I$ these rows are the logits. Each node’s probability of its own class is $0.593389$ for nodes $1$ and $2$, $0.506550$ for node $3$ and $0.701312$ for node $4$, and the mean cross-entropy is $0.519686$.

Gradient. With $\mat G=(\mat P-\mat Y)/4$, the chain rule gives

Its first row is $(-0.064314,\,0.064314)$ and its second $(0.079503,\,-0.079503)$.

Each row sums to zero because each row of $\mat P-\mat Y$ does: adding the same number to both logits of a node changes no probability.

One step. $\mat W\leftarrow\mat W-\partial\mathcal L/\partial\mat W$ lowers the loss to $0.499356$. The step strengthens the link from the first averaged feature to class $1$ and from the second to class $2$.

What the averaging did. Node $3$‘s own features say class $2$ with no doubt. After one convolution its probability of class $2$ is $0.506550$, barely above a coin: its two class-$1$ neighbours contribute $0.577350$ to its average, against $0.603553$ from itself and node $4$. A sum layer with its own self-weight, (I.14.3), could keep that evidence; the convolution’s fixed average cannot. This is the first round of the smoothing in I.14.P03.

Check — sanity

Node $4$, whose only neighbour is node $3$, is the most confident: its average has no class-$1$ feature at all, so its first logit is $0$.

STATEMENT

Prove that a deep linear autoencoder, of any depth and widths, attains no lower reconstruction loss than principal components with as many components as its narrowest layer, and that it attains exactly that loss. Connect the result to the linear β-VAE of I.13 as β goes to zero.

GIVEN

Centred data with covariance eigenvalues $\lambda_1\geq\cdots\geq\lambda_d$. A linear autoencoder $\hat{\vec x}=\mat W_L\cdots\mat W_1\vec x$ whose layer widths are $d=n_0,n_1,\ldots,n_{L-1},n_L=d$, with $k=\min_\ell n_\ell<d$. For the numbers, the four points of I.12, with widths $2,3,1,3,2$.

FIND

A lower bound on the loss, a choice of weights that attains it, and the loss for the four points; the link to I.13.T3.

STRATEGY

The product of the layers is one matrix whose rank is limited by the narrowest layer. Then I.12.T1 applies to that one matrix.

SOLUTION

The product is one map. Without nonlinearities the network computes $\mat M=\mat W_L\cdots\mat W_1$, a single linear map (I.3.B05). Every vector that leaves the narrowest layer lies in a space of dimension $k$, so the image of $\mat M$ has dimension at most $k$: $\operatorname{rank}\mat M\leq k$ (Rank, eigenvalues and the singular value decomposition · 0.LA.04).

The bound. The loss depends on the weights only through $\mat M$, as $\operatorname{tr}\big((\mat I-\mat M)\mat S(\mat I-\mat M)^{\mathsf T}\big)$ (I.12.2). A matrix of rank at most $k$ factors as $\mat D\mat E$ with $\mat E$ of shape $k\times d$, so I.12.T1 applies: $\mathcal L\geq\lambda_{k+1}+\cdots+\lambda_d$. $\blacksquare$

Attaining it. Let $\mat U_k$ hold the top $k$ eigenvectors. Map the input to $\mat U_k^{\mathsf T}\vec x$ in the first layers, carry those $k$ numbers unchanged through every later layer, padding with zeros where a layer is wider than $k$, and map back with $\mat U_k$ at the end. Every width is at least $k$, so each step is possible, and the product is $\mat U_k\mat U_k^{\mathsf T}$, which attains the bound. $\blacksquare$

The four points. With widths $2,3,1,3,2$, the narrowest is $1$. The layers $\begin{bmatrix}0.8&0.6\\0&0\\1&0\end{bmatrix}$, $\begin{bmatrix}1&0&0\end{bmatrix}$, $\begin{bmatrix}1\\0\\0\end{bmatrix}$ and $\begin{bmatrix}0.8&0&0\\0.6&0&0\end{bmatrix}$ multiply to $\begin{bmatrix}0.64&0.48\\0.48&0.36\end{bmatrix}=\vec u_1\vec u_1^{\mathsf T}$, and the loss is $1=\lambda_2$. The extra rows in the first layer and the extra width in the third change nothing: depth and width beyond the bottleneck buy no expressiveness here.

The link to I.13. By I.13.T3 the linear β-VAE has distortion $\lambda_2+\cdots+\lambda_d+\beta\sigma^2$, which tends to the same bound as $\beta\to0$. A deterministic linear autoencoder of any depth, and a linear VAE whose code becomes free, end at one point: the principal subspace.

Check — sanity

If every width were at least $d$, then $k=d$, the bound would be an empty sum, and the identity would be reachable: depth cannot make a linear autoencoder compress unless some layer is narrow.