Convolution backward: CNN backprop

Worked solutions

Problem 1

1. Output $i$ reads $x_i, x_{i+1}, \dots, x_{i+k-1}$, so it needs $i + k - 1 \le n - 1$, that is $i \le n - k$.The window has $k$ entries starting at $i$, and a valid correlation uses no padding, so the window must lie inside $x$.
2. $i$ runs over $0, 1, \dots, n - k$, which is $n - k + 1$ values.Counting from $0$ adds one to the largest index.
3. $y_0 = 2\cdot1 + (-1)\cdot2 + 1\cdot0 + 1 = 1$.Window $(x_0, x_1, x_2) = (1, 2, 0)$, each entry multiplied by the kernel entry in the same position, plus $b$.
4. $y_1 = 2\cdot2 + (-1)\cdot0 + 1\cdot(-1) + 1 = 4$.The window moves one step: $(x_1, x_2, x_3) = (2, 0, -1)$.
5. $y_2 = 2\cdot0 + (-1)\cdot(-1) + 1\cdot3 + 1 = 5$.Window $(x_2, x_3, x_4) = (0, -1, 3)$, the last one that fits since $n - k = 2$.
6. $m = n - k + 1$; here $m = 3$ and $y = (1, 4, 5)$Each $w_a$ was used three times, once per window: this is the weight sharing whose consequence for the gradient is Problem 2.

Problem 2

1. $\partial y_i/\partial w_a = x_{i+a}$ for every $i = 0, \dots, m-1$.Only the term $w_a x_{i+a}$ of the sum contains $w_a$, and every output has such a term because the same kernel is applied at every position.
2. $\dfrac{\partial L}{\partial w_a} = \sum_{i=0}^{m-1} \dfrac{\partial L}{\partial y_i}\,x_{i+a} = \sum_i dy_i\,x_{i+a}$.$L$ depends on $w$ only through $y$, and by step 1 every one of the $m$ outputs contains $w_a$, so the chain rule has $m$ terms.
3. $\sum_i dy_i\,x_{i+a} = \operatorname{corr}(x, dy)_a$.The definition of $\operatorname{corr}(u, v)_a = \sum_i v_i\,u_{a+i}$ with $u = x$ and $v = dy$: $dy$ plays the kernel and slides over $x$, giving $n - m + 1 = k$ outputs, one per kernel entry.
4. $\partial y_i/\partial b = 1$ for every $i$, so $\partial L/\partial b = \sum_i dy_i$.$b$ is added to every output, so the chain rule sums $dy$ over all of them.
5. $dw = \operatorname{corr}(x, dy)$, that is $dw_a = \sum_i dy_i\,x_{i+a}$; $db = \mathbf{1}^\top dy$The kernel gradient is a sum over positions for the same reason the minibatch page's bias gradient is a sum over examples: one parameter, many uses, and the chain rule adds the contributions.

Problem 3

1. $x_j$ appears in $y_i$ exactly when $j = i + a$ for some $0 \le a \le k - 1$, and then its coefficient is $w_{j-i}$.Put $a = j - i$ in the term $w_a x_{i+a}$: kernel entry $j - i$ is the one that lands on $x_j$ when the window starts at $i$.
2. $dx_j = \sum_i dy_i\,w_{j-i}$, summing over the $i$ with $0 \le j - i \le k - 1$.The chain rule sums over the outputs whose windows contain $x_j$. Inputs near the ends lie in fewer windows: $x_0$ lies only in window $0$.
3. Let $\tilde d = \operatorname{pad}_{k-1}(dy)$, so $\tilde d_t = dy_{t-k+1}$ for $k - 1 \le t \le m + k - 2$ and $\tilde d_t = 0$ otherwise.With $k - 1$ zeros at each end, every term $w_{j-i}$ in step 2 can be written without a range condition: indices that fall outside $dy$ hit a zero.
4. $\operatorname{corr}(\tilde d, \operatorname{flip}(w))_j = \sum_c w_{k-1-c}\,\tilde d_{j+c} = \sum_c w_{k-1-c}\,dy_{j+c-k+1}$.The definition of $\operatorname{corr}$ with kernel $\operatorname{flip}(w)$, then step 3; the result has $(m + 2k - 2) - k + 1 = m + k - 1 = n$ entries, one per input.
5. Put $i = j + c - k + 1$; then $k - 1 - c = j - i$ and the sum becomes $\sum_i dy_i\,w_{j-i}$.A change of summation index; as $c$ runs over $0, \dots, k-1$, $j - i$ runs over the same range, so the terms match step 2 one for one.
6. $dx = \operatorname{corr}(\operatorname{pad}_{k-1}(dy), \operatorname{flip}(w))$, that is $dx_j = \sum_i dy_i\,w_{j-i}$The second form is the true convolution $dy * w$, which is why the flip appears: the forward pass reads the kernel forwards as the window moves right, so seen from a fixed input $x_j$ the kernel index $j - i$ decreases as the window index $i$ increases. The forward pass is a correlation and the input gradient is a convolution.

Problem 4

1. $(Pw)_i = \sum_a x_{i+a}\,w_a = y_i - b$.Row $i$ of $P$ is window $i$ of $x$, so its product with $w$ is the sum in the definition.
2. $(Tx)_i = \sum_j T_{ij}\,x_j = \sum_{a=0}^{k-1} w_a\,x_{i+a} = y_i - b$.Only the $j$ with $0 \le j - i \le k - 1$ contribute; put $a = j - i$.
3. $\partial y/\partial w = P$ and $\partial y/\partial x = T$.$y$ is affine in $w$ for fixed $x$, and affine in $x$ for fixed $w$; the Jacobian of $Mv + c$ with respect to $v$ is $M$.
4. $dw = P^\top dy$ and $dx = T^\top dy$.For a scalar $L$, the gradient with respect to an input is the transposed Jacobian times the gradient at the output.
5. $(P^\top dy)_a = \sum_i x_{i+a}\,dy_i$ and $(T^\top dy)_j = \sum_i w_{j-i}\,dy_i$.$(M^\top v)_j = \sum_i M_{ij}v_i$; these are Problem 2, step 2 and Problem 3, step 2.
6. $dw = P^\top dy$ and $dx = T^\top dy$, the same vectors as Problems 2 and 3$P$ is what libraries call the im2col matrix, one window per row, and building it turns the layer and its kernel gradient into ordinary matrix products. $T$ is the layer as a dense $m \times n$ matrix: banded, with the kernel copied along each row and zeros elsewhere. Its transpose sends each $dy_i$ back to window $i$, which is Problem 3's flipped kernel; $T$ itself is never formed.

Problem 5

1. $dw_0 = 1\cdot2 + 0\cdot(-1) + (-2)\cdot3 = -4$.Problem 2: $dw_a$ is $dy$ dotted with the window of $x$ starting at $a$; for $a = 0$ that is $(x_0, x_1, x_2) = (2, -1, 3)$.
2. $dw_1 = 1\cdot(-1) + 0\cdot3 + (-2)\cdot0 = -1$ and $dw_2 = 1\cdot3 + 0\cdot0 + (-2)\cdot1 = 1$.The windows $(x_1, x_2, x_3) = (-1, 3, 0)$ and $(x_2, x_3, x_4) = (3, 0, 1)$.
3. $db = 1 + 0 - 2 = -1$.Problem 2: the sum of $dy$.
4. $\operatorname{pad}_2(dy) = (0, 0, 1, 0, -2, 0, 0)$ and $\operatorname{flip}(w) = (-1, 2, 1)$.Problem 3 with $k - 1 = 2$ zeros at each end.
5. $dx_0 = 0\cdot(-1) + 0\cdot2 + 1\cdot1 = 1$, $dx_1 = 0\cdot(-1) + 1\cdot2 + 0\cdot1 = 2$, $dx_2 = 1\cdot(-1) + 0\cdot2 + (-2)\cdot1 = -3$.Slide $\operatorname{flip}(w)$ along the padded $dy$, starting at positions $0$, $1$, $2$.
6. $dx_3 = 0\cdot(-1) + (-2)\cdot2 + 0\cdot1 = -4$ and $dx_4 = (-2)\cdot(-1) + 0\cdot2 + 0\cdot1 = 2$.Positions $3$ and $4$, the last that fit in a length-$7$ vector. Spot check with $dx_j = \sum_i dy_i\,w_{j-i}$: $x_0$ is only in window $0$, under $w_0 = 1$, so $dx_0 = dy_0 = 1$.
7. $dw = (-4, -1, 1)$, $db = -1$, $dx = (1, 2, -3, -4, 2)$Five entries in $dx$ and three in $dw$, the shapes of $x$ and $w$.

Problem 6

1. $Y$ is $(n_1 - k_1 + 1) \times (n_2 - k_2 + 1)$.Problem 1 in each direction separately: the window must fit vertically and horizontally.
2. $\partial L/\partial K_{ac} = \sum_{i,j} dY_{ij}\,X_{i+a,\,j+c} = \operatorname{corr}(X, dY)_{ac}$.Problem 2 in two dimensions: $K_{ac}$ is used at every output position $(i, j)$ with coefficient $X_{i+a,j+c}$, and the chain rule sums over all of them.
3. $\partial L/\partial b = \sum_{i,j} dY_{ij}$.$b$ is added to every entry of $Y$.
4. $X_{pq}$ appears in $Y_{ij}$ with coefficient $K_{p-i,\,q-j}$ whenever $0 \le p - i \le k_1 - 1$ and $0 \le q - j \le k_2 - 1$, so $dX_{pq} = \sum_{i,j} dY_{ij}\,K_{p-i,\,q-j}$.Problem 3, steps 1 and 2, with one offset per direction.
5. $\sum_{i,j} dY_{ij}\,K_{p-i,\,q-j} = \operatorname{corr}(\operatorname{pad}_{k_1-1,k_2-1}(dY), \operatorname{rot}(K))_{pq}$.Problem 3, steps 3 to 5, in each direction: flipping both axes of $K$ is turning it through $180^\circ$, and the padding gives $n_1 \times n_2$ outputs.
6. $dK = \operatorname{corr}(X, dY)$; $db = \sum_{i,j} dY_{ij}$; $dX = \operatorname{corr}(\operatorname{pad}_{k_1-1,k_2-1}(dY), \operatorname{rot}(K))$The shapes are $k_1 \times k_2$, a scalar and $n_1 \times n_2$, those of $K$, $b$ and $X$. Nothing new happens in two dimensions: each axis behaves like the 1-D layer.

Problem 7

1. $K_{f,c}$ appears only in output channel $f$, through the term $\operatorname{corr}(X^{(n)}_c, K_{f,c})$, and it appears there for every example $n$.Each filter makes one output channel, its slice $c$ reads only input channel $c$, and the filters are shared across the batch.
2. $dK_{f,c} = \sum_n \operatorname{corr}(X^{(n)}_c, dY^{(n)}_f)$.Problem 6, step 2, for each example, summed over examples because the parameter is shared, as on the minibatch page.
3. $db_f = \sum_n \sum_{i,j} dY^{(n)}_{f,ij}$.$b_f$ is added to every position of output channel $f$ in every example.
4. $X^{(n)}_c$ appears in every output channel $f$ of example $n$, through $\operatorname{corr}(X^{(n)}_c, K_{f,c})$, and in no other example.Every filter reads every input channel; examples do not interact.
5. $dX^{(n)}_c = \sum_f \operatorname{corr}(\operatorname{pad}_{k_1-1,k_2-1}(dY^{(n)}_f), \operatorname{rot}(K_{f,c}))$.Problem 6, step 5, for each output channel the input reaches, added because the chain rule sums over every path.
6. $dK_{f,c} = \sum_n \operatorname{corr}(X^{(n)}_c, dY^{(n)}_f)$; $db_f = \sum_n\sum_{i,j} dY^{(n)}_{f,ij}$; $dX^{(n)}_c = \sum_f \operatorname{corr}(\operatorname{pad}_{k_1-1,k_2-1}(dY^{(n)}_f), \operatorname{rot}(K_{f,c}))$The three sums are over the three kinds of sharing: the kernel gradient sums over positions (inside $\operatorname{corr}$) and examples, the bias gradient over positions and examples, and the input gradient over the filters that read the channel. No gradient sums over input channels, because each slice $K_{f,c}$ reads one channel only.

Problem 8

1. $dw_a = \sum_i dy_i\,x_{si+a}$.Problem 2 with window $i$ starting at $si$ instead of $i$: $w_a$ is still used once per output, now with coefficient $x_{si+a}$.
2. $x_j$ appears in $y_i$ with coefficient $w_{j-si}$ when $0 \le j - si \le k - 1$, so $dx_j = \sum_i dy_i\,w_{j-si}$ over those $i$.Problem 3, steps 1 and 2, with window $i$ starting at $si$.
3. Let $u$ be $dy$ with $s - 1$ zeros inserted between neighbouring entries: $u_{si} = dy_i$, other entries $0$, length $s(m-1) + 1$. Then $dx_j = \sum_t u_t\,w_{j-t}$.The nonzero entries of $u$ sit at $t = si$, so the sum over $t$ is the sum over $i$ in step 2; the zeros contribute nothing.
4. That is Problem 3's formula with $u$ in place of $dy$, which gives the first $s(m-1) + k$ entries of $dx$; inputs $x_j$ with $j \ge s(m-1) + k$ lie in no window, and their gradient is $0$.The last window starts at $s(m-1)$ and ends at $s(m-1) + k - 1$; when $s$ does not divide $n - k$, the inputs after it are never read.
5. For $n = 8$, $k = 3$, $s = 2$: $m = \lfloor 5/2 \rfloor + 1 = 3$, the last window covers $x_4, x_5, x_6$, and $x_7$ is never read.Step 4 with $s(m-1) + k = 7$.
6. $dw_a = \sum_i dy_i\,x_{si+a}$; $dx_j = \sum_i dy_i\,w_{j-si}$ (over $0 \le j - si \le k-1$), which is Problem 3 applied to $dy$ with $s - 1$ zeros inserted between its entries; for $n = 8$, $k = 3$, $s = 2$, $dx_7 = 0$This is why the backward pass of a strided convolution is called a transposed convolution: it is $T^\top dy$ for the strided $T$ of Problem 4, and the inserted zeros are how a stride-$1$ routine computes it.

Problem 9

1. Let $\tilde x = \operatorname{pad}_p(x)$, of length $n + 2p = n + k - 1$; then $y$ has $(n + k - 1) - k + 1 = n$ entries.Problem 1 applied to $\tilde x$.
2. $d\tilde x = \operatorname{corr}(\operatorname{pad}_{k-1}(dy), \operatorname{flip}(w))$ and $dw = \operatorname{corr}(\tilde x, dy)$.Problems 3 and 2 hold for any input vector, padded or not.
3. $x_j = \tilde x_{j+p}$, and the padding entries are constants, so $dx_j = d\tilde x_{j+p}$.$x$ reaches $L$ only through $\tilde x$, entry for entry; the gradients that land on the zeros are discarded because nothing upstream produced them.
4. $d\tilde x_{j+p} = \sum_c w_{k-1-c}\,dy_{j+p+c-(k-1)} = \sum_c \operatorname{flip}(w)_c\,dy_{j+c-p}$.Problem 3, step 4, at index $j + p$, with $k - 1 = 2p$.
5. $\sum_c \operatorname{flip}(w)_c\,dy_{j+c-p} = \operatorname{corr}(\operatorname{pad}_p(dy), \operatorname{flip}(w))_j$.Entry $j + c$ of $\operatorname{pad}_p(dy)$ is $dy_{j+c-p}$, or $0$ when that index falls outside $dy$.
6. $dx = \operatorname{corr}(\operatorname{pad}_p(dy), \operatorname{flip}(w))$ and $dw = \operatorname{corr}(\operatorname{pad}_p(x), dy)$The backward pass of a same convolution is a same convolution with the flipped kernel, which is why frameworks can reuse the forward routine for it. In two dimensions the flip becomes $\operatorname{rot}(K)$.

Problem 10