Chapter 11 · I.11

Problems

A chapter that uses mathematics has to teach that mathematics by making the reader compute. A chapter that only displays equations has failed, however correct the equations are.

M3Load-bearing

5/5 problems5/4 variants10/10 exercisesquota met, and enforced

The contract

5 worked problems, minimum.
4 distinct variants, and no variant more than half of them.
10 exercises, every one with a published solution.
At least one numeric problem — present.
At least one symbolic problem — present.
At least one limit or counterexample problem — present.
At least one complexity or shape problem — present.
At least one ▲▲▲ problem — present.

Numerical instantiationSymbolic derivationDimensional algebraConstructed failureCost accounting

Problem I.11.B01

Slide one kernel, keep its orientation

numeric▲△△

Exact integers and fractions where possible; six decimals otherwise.

STATEMENT

Compute every output of a small valid cross-correlation.

GIVEN

One input channel and one output channel, stride one, no padding, dilation one and zero bias:

\begin{aligned} X&=\begin{bmatrix}1&2&0\\0&1&3\\2&1&0\end{bmatrix},\\[6pt] K&=\begin{bmatrix}1&0\\-1&2\end{bmatrix}. \end{aligned}

FIND

The output shape, four output values, parameter count with a trainable bias, and main-product multiply-accumulates.

STRATEGY

Place the stored kernel on each complete window. Do not flip it. Use (I.11.4) for shape and (I.11.2) for the count.

SOLUTION

Each axis has $3-2+1=2$ outputs. The four sums are

\begin{aligned} Y_{0,0}&=1(1)+2(0)\\ &\quad+0(-1)+1(2)=3,\\ Y_{0,1}&=2(1)+0(0)\\ &\quad+1(-1)+3(2)=7,\\ Y_{1,0}&=0(1)+1(0)\\ &\quad+2(-1)+1(2)=0,\\ Y_{1,1}&=1(1)+3(0)\\ &\quad+1(-1)+0(2)=0. \end{aligned}

Thus $Y=\begin{bmatrix}3&7\\0&0\end{bmatrix}$ . There are four kernel weights and one bias, or five parameters. Four output windows use four weights each, giving 16 multiply-accumulates. A zero current bias is still a parameter if it is trainable.

Answer

Output shape $(1,2,2)$ , values $[[3,7],[0,0]]$ , five parameters and 16 main-product multiply-accumulates.

Check — sanity

The lower windows contain nonzero inputs but have zero output because positive and negative contributions cancel. A zero response need not mean an empty patch.

Check — numeric · i-11-convolution-checks.py

The reproduction script uses only Python’s standard library. From a repository checkout, run:

python3 scripts/snippets/i-11-convolution-checks.py

It checks the forward values, every input and kernel derivative, and all worked-problem and exercise calculations.

Executed in CI. The digits above are the digits it printed.

Where this breaks

Flipping the kernel changes the operation. Adding channels requires summing their responses before adding the output channel’s bias once.

Variation

Set the bias to one. Every output increases by one, producing $[[4,8],[1,1]]$ , while the parameter count remains five.

Problem I.11.B02

Overlapping windows add their gradients

symbolic▲▲▲

Exact integers and fractions where possible; six decimals otherwise.

STATEMENT

Derive and check the kernel, input and bias gradients of I.11.B01.

GIVEN

Use I.11.B01’s $X$ and $K$ . The upstream derivative is

G=\begin{bmatrix}1&2\\-1&1\end{bmatrix}.

Define the scalar objective $F=\sum_{i,j}G_{i,j}Y_{i,j}$ . Treat $G$ as fixed during differentiation.

FIND

The gradient formulas and their complete numerical arrays.

STRATEGY

Differentiate one forward product, then sum every occurrence of each shared weight or overlapping input. Confirm the result using central differences.

SOLUTION

The differential of one output is

\begin{aligned} &dY_{i,j}=db\\ &\quad+\sum_{u,v}X_{i+u,j+v}\,dK_{u,v}\\ &\quad+\sum_{u,v}K_{u,v}\,dX_{i+u,j+v}. \end{aligned}

Multiplying by $G_{i,j}$ and summing gives (I.11.3). For the kernel entries, the sums are

\begin{aligned} dK_{0,0}&=1(1)+2(2)\\ &\quad-1(0)+1(1)=6,\\ dK_{0,1}&=1(2)+2(0)\\ &\quad-1(1)+1(3)=4,\\ dK_{1,0}&=1(0)+2(1)\\ &\quad-1(2)+1(1)=1,\\ dK_{1,1}&=1(1)+2(3)\\ &\quad-1(1)+1(0)=6. \end{aligned}

The bias derivative is $1+2-1+1=3$ . For the input, scatter each $G_{i,j}K$ into its corresponding window and add overlaps:

dX=\begin{bmatrix}1&2&0\\-2&1&4\\1&-3&2\end{bmatrix}.

The centre illustrates why assignment is wrong. Its four contributions are $2$ , $-2$ , $0$ and $1$ , whose sum is one.

The forward objective is $F=1(3)+2(7)-1(0)+1(0)=17$ . With zero bias, the map is linear in $X$ while $K$ is fixed, and linear in $K$ while $X$ is fixed. Consequently,

\begin{aligned} \langle dX,X\rangle&=17,\\ \langle dK,K\rangle&=17. \end{aligned}

These dot products are useful independent checks. The script also perturbs every input, weight and bias by $10^{-6}$ and compares central differences to the analytic result within $10^{-7}$ . Additional tests use padding, stride and dilation, where the same scatter-add rule must follow a different index map.

Answer

$dK=[[6,4],[1,6]]$ , $db=3$ and $dX=[[1,2,0],[-2,1,4],[1,-3,2]]$ .

Check — sanity

The input-gradient shape matches $X$ and the weight-gradient shape matches $K$ . All three occurrences of a nonzero centre contribution are retained.

Where this breaks

This is the derivative of the stated cross-correlation. Introducing another kernel flip while scattering would compute a different derivative. A nonlinear activation after the convolution must be differentiated first.

Variation

If the loss is averaged over the four outputs rather than summed, divide every upstream entry by four. All three gradient arrays scale accordingly; do not divide the already-scaled gradients again.

Problem I.11.B03

Include dilation before counting windows

shape▲▲△

Exact integers and fractions where possible; six decimals otherwise.

STATEMENT

Audit an entire batched convolution without relying on a framework’s inferred shape.

GIVEN

Input layout is $(N,C,H,W)=(2,3,7,8)$ . There are four output channels, a $3$ by $3$ kernel, dilation two, stride two and padding one on every side. Use one group and a trainable output-channel bias.

FIND

Effective kernel span, output shape, weight shape, parameter count and main-product multiply-accumulates.

STRATEGY

Use (I.11.4) on each spatial axis, then (I.11.2) on the resulting grid. Dilation spreads taps; it does not create additional weights.

SOLUTION

The effective kernel width is $2(3-1)+1=5$ on both axes. Therefore

\begin{aligned} H_{\mathrm{out}}&=\left\lfloor\frac{7+2-5}{2}\right\rfloor+1=3,\\ W_{\mathrm{out}}&=\left\lfloor\frac{8+2-5}{2}\right\rfloor+1=3. \end{aligned}

The output shape is $(2,4,3,3)$ . The weight shape is $(4,3,3,3)$ and bias shape is $(4)$ . There are $4\cdot3\cdot3\cdot3+4=112$ parameters.

Each output scalar uses $3\cdot3\cdot3=27$ weights. There are $2\cdot4\cdot3\cdot3=72$ output scalars, giving $72\cdot27=1944$ multiply-accumulates. This dense accounting includes multiplications by padded zero entries; a specialised implementation may skip some.

Answer

Span $5$ by $5$ , output $(2,4,3,3)$ , 112 parameters and 1944 main-product multiply-accumulates.

Check — sanity

Ignoring dilation would give spatial outputs $4$ by $4$ , a different model. The number of weights would not change, which is why a parameter-count check alone cannot catch that shape error.

Where this breaks

The weight layout here is output-channel, input-channel, height, width. A channels-last input convention changes array organisation, not the mathematical count. Named ‘same’ padding need not mean one pixel on each side.

Variation

Keep the input and kernel but set dilation to one. The output becomes $(2,4,4,4)$ , with $3456$ multiply-accumulates and still 112 parameters.

Problem I.11.B04

A one-pixel shift can cross a pooling boundary

counterexample▲▲△

Exact integers and fractions where possible; six decimals otherwise.

STATEMENT

Identify exactly which location changes a pooled representation forgets.

GIVEN

Use one-dimensional width-two max pooling with stride two, no padding. Consider $a=(1,0,0,0)$ , $b=(0,1,0,0)$ and $c=(0,0,1,0)$ . Also consider width-two average pooling with the same stride.

FIND

All pooled outputs. Decide whether the operation is invariant under every one-position right shift and whether its output determines the original input.

STRATEGY

Write the two disjoint windows explicitly. Distinguish a permutation inside one window from movement into another window.

SOLUTION

Max pooling yields

\begin{aligned} P_{\max}(a)&=(1,0),\\ P_{\max}(b)&=(1,0),\\ P_{\max}(c)&=(0,1). \end{aligned}

The shift from $a$ to $b$ stays within the first window and leaves its maximum unchanged. The equally small shift from $b$ to $c$ crosses a window boundary and changes the output.

Average pooling gives $(1/2,0)$ , $(1/2,0)$ and $(0,1/2)$ . The same boundary distinction remains.

Both maps are many-to-one: $a$ and $b$ have different locations but identical pooled outputs. No deterministic inverse receiving only that output can reconstruct both correctly. This proves loss of information for these maps, without claiming that every downsampling transform is lossy.

Answer

Pooling is invariant to these within-window rearrangements, not to every small translation of the whole signal. It cannot recover the lost location from the pooled values alone.

Check — sanity

A two-position shift aligned to the stride moves the pooled response by one position, provided the signal and boundaries are treated consistently. That is an equivariance relation, not an unchanged output.

Where this breaks

The argument depends on the window partition. Changing stride, padding or the reduction changes the equivalence classes of inputs. Extra side information, such as stored argmax indices, also changes what a decoder receives.

Variation

The vectors $(1,1)$ and $(0,2)$ have the same mean but different maxima. Max and average pooling discard different information even in one window.

Problem I.11.B05

What a depthwise factorisation saves

complexity▲▲△

Exact integers and fractions where possible; six decimals otherwise.

STATEMENT

Compare a standard convolution with a depthwise-plus-pointwise replacement.

GIVEN

One example has 32 input channels, 64 output channels and a $28$ by $28$ output grid. The standard kernel is $3$ by $3$ . The replacement uses one depthwise $3$ by $3$ filter per input channel followed by a $1$ by $1$ pointwise layer to 64 channels. Ignore biases and nonlinearities in both cases.

FIND

Weights and multiply-accumulates for both designs, the cost ratio, and a reason why equal shapes do not make their function classes equal.

STRATEGY

Count the depthwise and pointwise weights separately, then multiply by the number of output positions.

SOLUTION

The standard layer has $9\cdot32\cdot64=18432$ weights. The factorised version has $9\cdot32=288$ depthwise weights and $32\cdot64=2048$ pointwise weights, for a total of $2336$ .

Since $28^2=784$ , the main-product counts are

\begin{aligned} M_{\mathrm{standard}}&=18432(784)\\ &=14450688,\\ M_{\mathrm{factorised}}&=2336(784)\\ &=1831424. \end{aligned}

The ratio is

\frac{2336}{18432}=\frac1{64}+\frac19\approx0.126736.

That is about $7.89$ times fewer main-product operations in this counting model, not a measured latency speedup.

Without an intervening nonlinearity, the effective kernel has the form $K_{o,c,u,v}=P_{o,c}D_{c,u,v}$ . For each input channel, all output channels use scalar multiples of its same spatial filter. A general convolution does not impose this restriction.

Answer

Standard: 18,432 weights and 14,450,688 MACs. Factorised: 2,336 weights and 1,831,424 MACs. The smaller operation is a constrained model, not an exact replacement for every standard kernel.

Check — sanity

Both weight counts and MAC counts have the same ratio because the two designs use the same spatial grid. Biases and intermediate activations were explicitly excluded.

Where this breaks

Real runtime also depends on memory traffic, kernel efficiency and hardware. Adding a nonlinearity between the layers changes the function again; it does not remove the need to evaluate accuracy after replacement.

Variation

For spatial width $k$ and output width $C_{\mathrm{out}}$ , the corresponding ratio is $1/C_{\mathrm{out}}+1/k^2$ . At $k=1$ the extra depthwise layer does not create the same saving.

Exercises

Every one has a published solution. A hidden solution is a solution; a missing one is an abandonment.

I.11.X01A stored kernel has an orientationnumeric▲△△

For input $(1,2,3)$ and kernel $(1,2)$ , compute valid stride-one cross-correlation, then repeat after reversing the kernel.

Hint

The windows are $(1,2)$ and $(2,3)$ .

Solution

Cross-correlation gives $(1+4,2+6)=(5,8)$ . Reversing the kernel to $(2,1)$ gives $(2+2,4+3)=(4,7)$ . The second corresponds to the flipped-kernel convention on the same valid windows. Neither answer is a numerical approximation to the other.

A learned filter can be reversed through its learned parameters, so this does not restrict the family of learnable linear maps. But fixed filters, checkpoints and hand calculations must agree on orientation.

I.11.X02Count the fourth window, not a fifthnumeric▲△△

Compute the output length for input seven, kernel three, dilation one, padding one on each side and stride two. List padded-coordinate origins. Then choose padding for a width-four, stride-one kernel to retain length seven.

Hint

Use the effective span, and require the last tap to stay inside the padded input.

Solution

Equation (I.11.4) gives $\lfloor(7+2-3)/2\rfloor+1=4$ . In a padded input of length nine, origins $0,2,4,6$ end at $2,4,6,8$ . Origin eight would end at ten and does not fit.

For width four at stride one, total padding must be three. Splits $(1,2)$ and $(2,1)$ both preserve length but shift alignment differently. Equal integer padding cannot sum to three. The phrase ‘same size’ does not determine which side gets the extra value.

I.11.X06Global averaging distributes a derivativegradient▲△△

One feature map is $[[1,3],[5,7]]$ . Compute its global average and the input gradient when the upstream derivative is two. Does permuting these four feature values change the result?

Hint

The average is a linear map with four equal coefficients.

Solution

The average is $(1+3+5+7)/4=4$ . Each input derivative is $2/4=1/2$ , so the gradient map is $[[0.5,0.5],[0.5,0.5]]$ .

Every permutation retains the same sum and average. This is a statement about the supplied feature values. A translated finite image can change the preceding features at boundaries; global averaging by itself does not prove that the entire image-to-label function is invariant to every translation.

I.11.X03Finite boundaries break a shift identitycounterexample▲▲△

Cross-correlate $(1,2,3)$ with $(1,1,1)$ using zero padding one on both sides and stride one. Compare correlating its cropped right shift $(0,1,2)$ with taking the cropped right shift of its original output.

Hint

A cropped right shift discards the last entry and inserts zero on the left.

Solution

The original output is $(3,6,5)$ . Correlating the shifted input gives $(1,3,3)$ . Shifting the original output gives $(0,3,6)$ . The two disagree at the boundary positions.

This does not contradict I.11.T1: the finite crop removes values that an unrestricted-grid translation would retain. A boundary convention is part of the operator, not an implementation detail outside its mathematics. Circular shifts with compatible circular padding give a different case.

I.11.X04Update the receptive field before the jumpnumeric▲▲△

Track receptive-field span and sampling jump through three width-three layers with strides $(1,2,1)$ and dilation one. All use symmetric padding one. What are the first-output centre and final jump if original pixel centres start at $1/2$ ?

Hint

Use the preceding layer’s jump when growing the span.

Solution

Starting from $(R_0,J_0)=(1,1)$ , (I.11.6) gives

\begin{aligned} (R_1,J_1)&=(3,1),\\ (R_2,J_2)&=(5,2),\\ (R_3,J_3)&=(9,2). \end{aligned}

Every layer’s centre increment is $((3-1)/2-1)J_{\mathrm{previous}}=0$ . The first centre remains $1/2$ ; neighbouring final outputs are two original pixels apart. At the boundary, part of the nominal nine-position span is padding.

Updating the second jump before computing its span would give seven instead of five at layer two. The stride changes spacing between outputs, not the taps inside that layer’s first window.

I.11.X05Different reductions send different gradientsgradient▲▲△

A four-entry pooling window is $(1,3,2,0)$ and its upstream derivative is four. Find max- and average-pooling input gradients. What changes if the window is $(1,3,3,0)$ ?

Hint

The first maximum is unique; the second is tied.

Solution

The unique max routes the upstream derivative to the second entry: $(0,4,0,0)$ . Average pooling sends $4/4=1$ to every entry, giving $(1,1,1,1)$ .

At the tie, max pooling has no unique ordinary derivative. A valid subgradient has the form $(0,4\alpha,4(1-\alpha),0)$ for $0\leq\alpha\leq1$ . An implementation storing one argmax can choose one endpoint. A central difference at the tie need not reproduce that choice.

All these subgradients sum to four: increasing every window entry by the same amount increases its maximum by that amount. The reproduction check uses finite differences only at the unique maximum.

I.11.X08Count channels inside each groupshape▲▲△

A $3$ by $3$ convolution has eight input channels, twelve output channels, four groups and one bias per output channel. Give the weight shape and parameter count. Is a group count of three valid? Then count a depthwise layer with eight input channels and multiplier two.

Hint

Each output channel reads only the input channels assigned to its group.

Solution

With four groups, each output channel reads $8/4=2$ inputs. The weight shape is $(12,2,3,3)$ , with $216$ weights and $12$ biases, or $228$ parameters. Each group has two input and three output channels.

Three groups are invalid because eight is not divisible by three, even though twelve is.

Depthwise multiplier two produces sixteen output channels in eight groups. The weight shape is $(16,1,3,3)$ , giving $144$ weights plus sixteen biases, or $160$ parameters. Two independent spatial filters are learned for each input channel; this layer still does not mix different input channels.

I.11.X09An identity path can still be cancelledcounterexample▲▲△

For $y=x+F(x)$ take $F(x)=-x$ . Compute the output and Jacobian. Now consider a residual branch changing shape from $(N,16,32,32)$ to $(N,32,16,16)$ . Can it be added directly to the input?

Hint

Differentiate the sum, and check every axis before adding tensors.

Solution

The output is zero and the Jacobian is $I-I=0$ . Thus the identity term in (I.11.8) does not give a positive lower bound on the total gradient. It creates a route that can help training, but another route can cancel it.

The second addition is invalid: channel and spatial dimensions differ. One possible shortcut is a $1$ by $1$ projection from 16 to 32 channels with stride two and no padding. It produces $(N,32,16,16)$ . Its derivative is the projection’s Jacobian rather than an identity. The alignment of the two branches still needs checking.

I.11.X10Count what the classifier keepscomplexity▲▲△

A CNN returns 64 feature channels on a $7$ by $7$ grid. Compare a flattened affine head to ten classes with global average pooling followed by an affine ten-class head. Include biases. What distinction can the flattened head express that the pooled head cannot?

Hint

Flattening preserves 49 coordinates per channel; averaging retains one.

Solution

Flattening gives $64\cdot7\cdot7=3136$ inputs. The affine head has $3136\cdot10+10=31370$ parameters. After global averaging it has $64\cdot10+10=650$ .

A flattened head can weight a feature differently at two positions. A pooled head receives the same channel average after any permutation within that channel and cannot distinguish those permutations from that representation alone.

The parameter saving does not prove that the smaller head is better. Location may be nuisance variation for one task and essential evidence for another. The upstream feature extractor can also encode some positional information before pooling, so the limitation is stated at the feature-map interface, not as a universal claim about all CNN classifiers.

I.11.X07Transpose the operator, not its information losssymbolic▲▲▲

A one-dimensional cross-correlation uses kernel $(1,2,3)$ , stride two, padding one and input length four. Write its matrix $A$ . For $x=(1,2,3,4)^{\mathsf T}$ and $g=(1,-1)^{\mathsf T}$ , verify $\langle Ax,g\rangle=\langle x,A^{\mathsf T}g\rangle$ . Choose output padding to return length four with (I.11.5). Is $A^{\mathsf T}$ an inverse?

Hint

The two padded windows are $(0,x_0,x_1)$ and $(x_1,x_2,x_3)$ .

Solution

The matrix and products are

A=\begin{bmatrix}2&3&0&0\\0&1&2&3\end{bmatrix}, \qquad Ax=\begin{bmatrix}8\\20\end{bmatrix},

A^{\mathsf T}g=\begin{bmatrix}2\\2\\-2\\-3\end{bmatrix}.

Both dot products equal $-12$ : $8-20=-12$ and $2+4-6-12=-12$ . That is the adjoint identity behind the backward scatter-add.

The transposed output length is $(2-1)2-2+2+o+1=3+o$ . Choose $o=1$ to return length four. The original matrix has rank at most two, so it cannot distinguish all four-dimensional inputs. Its transpose cannot be a two-sided inverse. Matching the original length is not evidence of inversion.