Answers.Body: <p>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:</p>
  <p>If a <code>[N,10,10,C]</code> image is convolved with a <code>[F,3,3,C]</code> kernel (both in NHWC format, <code>F = #</code> kernels), using stride &amp; dilation 1 and valid padding, the output is <code>[N,8,8,F]</code> image.</p>
  <p>Therefore the gradients coming back to this layer is also <code>Nx8x8xF</code> which are element-wise multiplied with the activation gradients to get dL/dZ, also <code>[N,8,8,F]</code>. The kernel gradients formula is <span class="math-container">$input * \frac{dL}{dZ}$</span> so this is a <code>[N,10,10,C]</code> dimension image convolved with <code>[N,8,8,F]</code> dimension gradient.</p>
  <p><strong>Convert the gradients tensor into an im2col tensor</strong></p>
  <ol>
  <li>Shuffle the gradient <span class="math-container">$\frac{dL}{dZ}$</span>'s dimensions <code>[N,8,8,F]</code> into <code>[F,N,8,8]</code></li>
  <li>Reshape <code>[F,N,8,8]</code> into <code>[F,N,8,8,1]</code> and broadcast into <code>[F,N,8,8,C]</code> to match the input image's channels, divide it by the number of times broadcasted, C</li>
  <li>Reshape <code>[F,N,8,8,C]</code> into a 2D tensor as <code>[F,N*8*8*C]</code></li>
  </ol>
  <p>Step 2 addresses my question on convolving 2 tensors with mismatching channels dimensions.</p>
  <p><strong>Then extract patches from the input tensor and convert it to an im2col tensor</strong></p>
  <ol>
  <li>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 &amp; 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 <code>[N,P,8,8,C]</code>, P = # patches = 9, the # times the kernels (gradients) slid across the input image</li>
  <li>Shuffle the 5D tensor's dimensions from <code>[N,P,8,8,C]</code> to <code>[P,N,8,8,C]</code></li>
  <li>Reshape the image patches <code>[P,N,8,8,C]</code> into the 2D tensor <code>[P,N*8*8*C]</code></li>
  </ol>
  <p><strong>Now that we have the gradients as <code>[F,N*8*8*C]</code> and <code>[P,N*8*8*C]</code>, we can multiply the two</strong></p>
  <ul>
  <li>Do a contraction (matrix multiplication) along the first dimensions of both, the resulting tensor dimensions are <code>[F,N*8*8*C] x [P,N*8*8*C] = [F,P]</code>.</li>
  <li>The tensor is reshaped from <code>[F,P]</code> to <code>[F,3,3]</code>, then to <code>[F,3,3,1]</code></li>
  <li>Broadcast C times on the last dimension, divide by batch size N, then we get the kernel gradients <code>[F,3,3,C]</code> which match the kernel used during the forward pass, and can be fed to your optimizer of choice during the weights update</li>
  </ul>
  <p>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).</p>
  <p>Edit: Here's my implementation on GitHub (<a href="https://github.com/rkuang9/FLARE/blob/5ca289c4ce1a221ef31ad5186149951518d70e24/flare/layers/conv2d.ipp#L305" rel="nofollow noreferrer">1</a> <a href="https://github.com/rkuang9/FLARE/blob/5ca289c4ce1a221ef31ad5186149951518d70e24/flare/layers/conv2d.ipp#L368" rel="nofollow noreferrer">2</a>)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-09T10:27:51.883Z
Answers.LastActivityDate: 2023-05-11T09:28:42.070Z
Answers.LastEditDate: 2023-05-11T09:28:42.070Z
Answers.UserDisplayName: rkuang25
Answers.Body: <p>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.</p>
  <p>Note that the convolution operations forward and backwards are different.</p>
  <hr />
  <p>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.</p>
  <p><span class="math-container">\begin{align}
  z&amp;=c*_{rev}x\\
  y&amp;=P_Nz
  \end{align}</span></p>
  <p>Let's just consider the one-dimensional case, higher dimensions proceed similarly. Then <span class="math-container">$P_N$</span> cuts out the finite sequence with support <span class="math-container">$N$</span>, <span class="math-container">$y_n=z_n$</span> if <span class="math-container">$n\in N$</span>, else <span class="math-container">$y_n=0$</span>. Similarly for the projections to the support <span class="math-container">$K$</span> of the coefficient sequence <span class="math-container">$c$</span> and <span class="math-container">$M$</span> of the input sequence <span class="math-container">$x$</span>.</p>
  <p>The convention for CNN is to not use the convolution as used for polynomial multiplication, where <span class="math-container">$[a*b]_n=\sum_ka_kb_{n-k}$</span>, but to have it look more like a scalar product,
  <span class="math-container">$$
  [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,
  $$</span>
  <span class="math-container">$rev$</span> for &quot;reverse&quot;, where <span class="math-container">$[rev(c)]_k=c_{-k}$</span>.
  Note that this version of the convolution product is not commutative.</p>
  <p>These all are linear operations, so in principle the gradient back propagation has the same structure as the usual matrix multiplication.</p>
  <p>The structural principle of gradient computation is that gradients <span class="math-container">$\bar u^T=\bar L\frac{\partial L}{\partial u}$</span> act as linear functionals on tangent vectors <span class="math-container">$\dot u$</span>, and that the scalar value <span class="math-container">$\langle \bar u,\dot u\rangle$</span> of it is independent on where in the graph the pairing of gradient and tangent is carried out,
  <span class="math-container">$$
  ⟨\bar y,\dot y⟩=⟨\bar z,\dot z⟩=⟨\bar x,\dot x⟩+⟨\bar c,\dot c⟩.
  $$</span>
  The tangent propagation is, using the product rule,
  <span class="math-container">\begin{align}
  \dot z&amp;=\dot c*_{rev}x+c*_{rev}\dot x\\
  \dot y&amp;=P\dot z
  \end{align}</span>
  Evaluating the defining relations gives
  <span class="math-container">\begin{align}
  ⟨\bar z,\dot z⟩&amp;=⟨\bar y,\dot y⟩=⟨\bar y ,P\dot z⟩=⟨P_N^T\bar y,\dot z⟩  \\
  ⟨\bar x,\dot x⟩+⟨\bar c,\dot c⟩&amp;=⟨\bar z,\dot z⟩=⟨\bar z,(\dot c*_{rev}x)⟩+⟨\bar z,(c*_{rev}\dot x)⟩
  \end{align}</span>
  The first operation <span class="math-container">$\bar z=P^T\bar y$</span> is just zero-padding of the sequence as <span class="math-container">$(0_{k_1},\, y^T,\, 0_{k_2})^T$</span>. If one thinks of all sequences continued indefinitely by zero, then <span class="math-container">$P_N^T$</span> does nothing, as the zeros for the padding are already present.</p>
  <p>To analyze the combination of scalar product and convolution, let's go into the details
  <span class="math-container">\begin{align}
  ⟨\bar z,(\dot c*_{rev}x)⟩
  &amp;=\sum_{n\in N}\bar z_n\sum_{k\in K}\dot c_kx_{n+k}  \\
  &amp;=\sum_{k\in K}\dot c_k\sum_{n\in N}\bar z_nx_{k+n}  \\
  &amp;=⟨(\bar z*_{rev}x),\dot c⟩   \\
  \implies \bar c &amp;= P_K(\bar z*_{rev}x)
  \end{align}</span>
  as <span class="math-container">$\dot c$</span> always only has support <span class="math-container">$K$</span>, so the support of the gradient to it needs to have the same support.</p>
  <p>For the second term one gets similarly
  <span class="math-container">\begin{align}
  ⟨\bar z,(\dot c*_{rev}x)⟩
  &amp;=\sum_{n\in N}\bar z_n\sum_{m\in M}c_{m-n}\dot x_m  \\
  &amp;=\sum_{m\in M}\dot x_m\sum_{n\in N}\bar z_nc_{m-n}  \\
  &amp;=⟨(\bar z*c),\dot x⟩   \\
  \implies \bar x &amp;= P_M(\bar z*c)
  \end{align}</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-07T11:11:52.853Z
Answers.LastActivityDate: 2022-12-07T11:11:52.853Z
Answers.UserDisplayName: Lutz Lehmann
Body: <p>Assume in a convolutional layer's forward pass we have a <span class="math-container">$10\times10\times3$</span> image and five <span class="math-container">$3\times3\times3$</span> kernels, then <span class="math-container">$(10\times10\times3) *( 3\times3\times3\times5)$</span> has the output of dimensions <span class="math-container">$8\times8\times5$</span>. Therefore the gradients fed backwards to this convolutional layer also have the dimensions <span class="math-container">$8\times8\times5$</span>.</p>
  <p>When calculating the derivative of loss w.r.t. kernels, the formula is the convolution <span class="math-container">$input * \frac{dL}{dZ}$</span>. But if the gradients have dimensions <span class="math-container">$8\times8\times5$</span>, how is it possible to convolve it with <span class="math-container">$10\times10\times3$</span>? The gradients have <span class="math-container">$5$</span> channels while the input only has <span class="math-container">$3$</span>.</p>
  <p>Since during the forward pass the kernel window does element-wise multiplication and brings the channels down to <span class="math-container">$1$</span>, do the gradients propagate back to each of the <span class="math-container">$3$</span> channels equally? Should the <span class="math-container">$8\times8\times5$</span> gradients be reshaped into <span class="math-container">$8\times8\times1\times5$</span> and broadcasted into <span class="math-container">$8\times8\times3\times5$</span> before convolving with the layer input?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-14T18:00:14.157Z
Comments.Text: I think this [article](https://pavisj.medium.com/convolutions-and-backpropagations-46026a8f5d2c#:~:text=Chain%20Rule%20in%20a%20Convolutional%20Layer&text=For%20the%20forward%20pass%2C%20we,as%20%E2%88%82L%2F%E2%88%82z%20.) will help you with this question.
Comments.UserDisplayName: Snehal Patel
Tags: <neural-networks><convolutional-neural-networks><backpropagation><convolution>
Title: How Does Convolution Backpropagation Work?
UserDisplayName: rkuang25
ThreadText: # How Does Convolution Backpropagation Work?
  
  (Asked by: username_0 on 2022-10-17)
  
  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?
  
  **Tags:** neural-networks, convolutional-neural-networks, backpropagation, convolution
  
  > **Comments:**
  > **username_1**: I think this [article](https://pavisj.medium.com/convolutions-and-backpropagations-46026a8f5d2c#:~:text=Chain%20Rule%20in%20a%20Convolutional%20Layer&text=For%20the%20forward%20pass%2C%20we,as%20%E2%88%82L%2F%E2%88%82z%20.) will help you with this question.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2022-12-09. Score: 1
  
  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](https://github.com/rkuang9/FLARE/blob/5ca289c4ce1a221ef31ad5186149951518d70e24/flare/layers/conv2d.ipp#L305) [2](https://github.com/rkuang9/FLARE/blob/5ca289c4ce1a221ef31ad5186149951518d70e24/flare/layers/conv2d.ipp#L368))
  
  
  ---
  
  ### Answer by username_2 on 2022-12-07. Score: 0
  
  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}
  
  
  ---
  
  