0
$\begingroup$

CNNs (convolutional neural networks) are adept at processing images, as their construction is based on the biological neural networks found in the human eye. "Kernels", sometimes called "filters", are small feature detectors in the form of small matricies that are slid (called "convulving") across an image detecting features in a sample image. This process is computationally intensive, as each time we slide one or more units we have to multiply each kernel value by the section of feature map we are sliding over.

Recently I found here that you can use FFT to do the convolutions up to ~4.8 times faster than with all that multiplication.

Kernels are regularly trained by backpropagation, treating each kernel entry almost like its own axon weight. However with the FFT method I am at a loss as to how to train the kernels.

So, how do you train the CNN kernels when using the FFT method of CNN convolutions? Is backpropagation still relevant?

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you checked the backpropagation algorithm (ref: brilliant.org/wiki/backpropagation)? There is a Python code at the end. Please, check if you could apply FFT similar to that. $\endgroup$
    – Cloud Cho
    Feb 2 at 23:47
  • $\begingroup$ See my attempt at explaining this. Technical points to consider are the restriction of the convolution to a rectangular domain that can be considered as a separate linear operation, and that the forward mode is usually a "reversed filter" convolution that devolves to the scalar product in the "single output" case, as you also described. The reverse operation in the back-propagation of gradients is then the normal convolution. $\endgroup$
    – Lutz Lehmann
    Mar 19 at 14:27

1 Answer 1

Reset to default
0
$\begingroup$

I had that same exact question when trying to develop some kind of implementation of the Conv2D using the FFT. To do this we need to consider that there are three steps that the layer needs to be able to do to actually be able to use it for inference and training:

  • 1° calculate the convolution of the input samples with all of the filters: $$y_{f'}=\sum_f x_f\ast w_{f'f}$$
  • 2° calculate the gradients (derivatives) of the loss with respect to the parameters of the convolution, if you apply the chain rule carefully you will find that this can be done using a convolution, specifically: $$\frac{\partial L}{\partial w_{f'f}} = \frac{\partial L}{\partial y_{f'}}\ast x_f$$
  • 3° calculate the gradients of the inputs with respect to the loss (necessary for the layer before this convolution layer to do backprop as well) which can also be done using a convolution: $$\frac{\partial L}{\partial x_f} = \frac{\partial L}{\partial y_{f'}}\ast w_{f'f}^{T}$$

This means that since you can apply the FFT in all of these steps in the same manner you can apply in the inference step.

If you want to know more you can try reading this 2014 article about doing convolution with the FFT by Yann LeCunn and some of his peers.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .