# How Does Convolution Backpropagation Work?

Assume in a convolutional layer's forward pass we have a $$10\times10\times3$$ image and five $$3\times3\times3$$ kernels, then $$(10\times10\times3) *( 3\times3\times3\times5)$$ has the output of dimensions $$8\times8\times5$$. Therefore the gradients fed backwards to this convolutional layer also have the dimensions $$8\times8\times5$$.

When calculating the derivative of loss w.r.t. kernels, the formula is the convolution $$input * \frac{dL}{dZ}$$. But if the gradients have dimensions $$8\times8\times5$$, how is it possible to convolve it with $$10\times10\times3$$? The gradients have $$5$$ channels while the input only has $$3$$.

Since during the forward pass the kernel window does element-wise multiplication and brings the channels down to $$1$$, do the gradients propagate back to each of the $$3$$ channels equally? Should the $$8\times8\times5$$ gradients be reshaped into $$8\times8\times1\times5$$ and broadcasted into $$8\times8\times3\times5$$ before convolving with the layer input?

I figured it out a while ago and double-checked my results with TensorFlow, so I'm fairly confident with the implementation. Here is what I did using Eigen Tensor and the im2col method:

If a [N,10,10,C] image is convolved with a [F,3,3,C] kernel (both in NHWC format, F = # kernels), using stride & dilation 1 and valid padding, the output is [N,8,8,F] image.

Therefore the gradients coming back to this layer is also Nx8x8xF which are element-wise multiplied with the activation gradients to get dL/dZ, also [N,8,8,F]. The kernel gradients formula is $$input * \frac{dL}{dZ}$$ so this is a [N,10,10,C] dimension image convolved with [N,8,8,F] dimension gradient.

Convert the gradients tensor into an im2col tensor

1. Shuffle the gradient $$\frac{dL}{dZ}$$'s dimensions [N,8,8,F] into [F,N,8,8]
2. Reshape [F,N,8,8] into [F,N,8,8,1] and broadcast into [F,N,8,8,C] to match the input image's channels, divide it by the number of times broadcasted, C
3. Reshape [F,N,8,8,C] into a 2D tensor as [F,N*8*8*C]

Step 2 addresses my question on convolving 2 tensors with mismatching channels dimensions.

Then extract patches from the input tensor and convert it to an im2col tensor

1. Extract image patches from the input image, using the same amount of padding during forward pass (following the convention that if uneven padding, the extra goes to the bottom & left) and the same stride and dilation (but the latter 2 are swapped), with the gradients from the previous step 2 playing the role of kernel, resulting in the 5D tensor [N,P,8,8,C], P = # patches = 9, the # times the kernels (gradients) slid across the input image
2. Shuffle the 5D tensor's dimensions from [N,P,8,8,C] to [P,N,8,8,C]
3. Reshape the image patches [P,N,8,8,C] into the 2D tensor [P,N*8*8*C]

Now that we have the gradients as [F,N*8*8*C] and [P,N*8*8*C], we can multiply the two

• Do a contraction (matrix multiplication) along the first dimensions of both, the resulting tensor dimensions are [F,N*8*8*C] x [P,N*8*8*C] = [F,P].
• The tensor is reshaped from [F,P] to [F,3,3], then to [F,3,3,1]
• Broadcast C times on the last dimension, divide by batch size N, then we get the kernel gradients [F,3,3,C] which match the kernel used during the forward pass, and can be fed to your optimizer of choice during the weights update

With Eigen Tensor, if you wrap all of this as a function with the return type auto to keep everything as an operation, you can lazily evaluate it into a 4D tensor using Eigen::ThreadPoolDevice with 2+ threads for improved speed (2-3 times faster than a single thread on my machine).

Edit: Here's my implementation on GitHub (1 2)

Yes, you are right that you just zero-pad to get the right dimensions. The operation in color space is just a scalar product, so that you could get the backwards operation in that dimension also just per the formulas of the matrix-vector product.

Note that the convolution operations forward and backwards are different.

The forward pass of the convolution layer has two elementary steps: first the convolution operation and then the cutting out of the fully convolved center sequence.

\begin{align} z&=c*_{rev}x\\ y&=P_Nz \end{align}

Let's just consider the one-dimensional case, higher dimensions proceed similarly. Then $$P_N$$ cuts out the finite sequence with support $$N$$, $$y_n=z_n$$ if $$n\in N$$, else $$y_n=0$$. Similarly for the projections to the support $$K$$ of the coefficient sequence $$c$$ and $$M$$ of the input sequence $$x$$.

The convention for CNN is to not use the convolution as used for polynomial multiplication, where $$[a*b]_n=\sum_ka_kb_{n-k}$$, but to have it look more like a scalar product, $$[c*_{rev}x]_n = \sum_{m\in M} c_{m-n}x_m=\sum_{k\in K}c_kx_{k+n}=[rev(c)*x]_n,$$ $$rev$$ for "reverse", where $$[rev(c)]_k=c_{-k}$$. Note that this version of the convolution product is not commutative.

These all are linear operations, so in principle the gradient back propagation has the same structure as the usual matrix multiplication.

The structural principle of gradient computation is that gradients $$\bar u^T=\bar L\frac{\partial L}{\partial u}$$ act as linear functionals on tangent vectors $$\dot u$$, and that the scalar value $$\langle \bar u,\dot u\rangle$$ of it is independent on where in the graph the pairing of gradient and tangent is carried out, $$⟨\bar y,\dot y⟩=⟨\bar z,\dot z⟩=⟨\bar x,\dot x⟩+⟨\bar c,\dot c⟩.$$ The tangent propagation is, using the product rule, \begin{align} \dot z&=\dot c*_{rev}x+c*_{rev}\dot x\\ \dot y&=P\dot z \end{align} Evaluating the defining relations gives \begin{align} ⟨\bar z,\dot z⟩&=⟨\bar y,\dot y⟩=⟨\bar y ,P\dot z⟩=⟨P_N^T\bar y,\dot z⟩ \\ ⟨\bar x,\dot x⟩+⟨\bar c,\dot c⟩&=⟨\bar z,\dot z⟩=⟨\bar z,(\dot c*_{rev}x)⟩+⟨\bar z,(c*_{rev}\dot x)⟩ \end{align} The first operation $$\bar z=P^T\bar y$$ is just zero-padding of the sequence as $$(0_{k_1},\, y^T,\, 0_{k_2})^T$$. If one thinks of all sequences continued indefinitely by zero, then $$P_N^T$$ does nothing, as the zeros for the padding are already present.

To analyze the combination of scalar product and convolution, let's go into the details \begin{align} ⟨\bar z,(\dot c*_{rev}x)⟩ &=\sum_{n\in N}\bar z_n\sum_{k\in K}\dot c_kx_{n+k} \\ &=\sum_{k\in K}\dot c_k\sum_{n\in N}\bar z_nx_{k+n} \\ &=⟨(\bar z*_{rev}x),\dot c⟩ \\ \implies \bar c &= P_K(\bar z*_{rev}x) \end{align} as $$\dot c$$ always only has support $$K$$, so the support of the gradient to it needs to have the same support.

For the second term one gets similarly \begin{align} ⟨\bar z,(\dot c*_{rev}x)⟩ &=\sum_{n\in N}\bar z_n\sum_{m\in M}c_{m-n}\dot x_m \\ &=\sum_{m\in M}\dot x_m\sum_{n\in N}\bar z_nc_{m-n} \\ &=⟨(\bar z*c),\dot x⟩ \\ \implies \bar x &= P_M(\bar z*c) \end{align}