14
$\begingroup$

In convolutional neural networks (CNN) the matrix of weights at each step gets its rows and columns flipped to obtain the kernel matrix, before proceeding with the convolution. This is explained on a series of videos by Hugo Larochelle here:

Computing the hidden maps would correspond to doing a discrete convolution with a channel from the previous layer, using a kernel matrix [...], and that kernel is computed from the hidden weights matrix $W_{ij}$, where we flip the rows and the columns.

enter image description here

If we were to compare the reduced steps of a convolution to regular matrix multiplication as in other types of NN, expediency would be a clear explanation. However, this might not be the most pertinent comparison...

In digital imaging processing the application of convolution of a filter to an image (this is a great youtube video for a practical intuition) seems related to:

  1. The fact that convolution is associative while (cross-)correlation is not.
  2. The possibility to apply filters in the frequency domain of the image as multiplications, since convolution in the time domain is equivalent to multiplication in the frequency domain (convolution theorem).

In this particular technical environment of DSP correlation is defined as:

$$F\circ I(x,y)=\sum_{j=-N}^{N}\sum_{i=-N}^N\, F(i,j)\,I(x+i, y+j)$$

which is essentially the sum of all the cells in a Hadamard product:

$$\small F\circ I(x,y)=\Tiny\begin{bmatrix}F[-N,-N]\,I[x-N,y-N]&\cdots&F[-N,0]\,I[x-N,y-N]&\cdots& F[-N,N]\,I[x-N,y+N]\\ \vdots&\ddots&\vdots&\ddots&\vdots\\ F[0,-N]\,I[x,y-N]&\cdots&F[0,0]\,I[x,y]&\cdots& F[0,N]\,I[x,y+N]\\ \vdots&\ddots&\vdots&\ddots&\vdots\\ F[N,-N]\,I[x+N,y-N]&\cdots&F[N,0]\,I[x+N,y]&\cdots& F[N,N]\,I[x+N,y+N]\\ \end{bmatrix}$$

where $F(i,j)$ is a filter function (expressed as a matrix), and $I(x,y)$ is the pixel value of an image at location $(x,y)$:

enter image description here

The objective of cross-correlation is to assess how similar is a probe image to a test image. The calculation of a cross-correlation map relies on the convolution theorem.


On the other hand, convolution is defined as:

$$F* I(x,y)=\sum_{j=-N}^{N}\sum_{i=-N}^N\, F(i,j)\,I(x-i, y-j)$$

which as long as the filter is symmetric, it is the same as a correlation operation with the rows and columns of the filter flipped:

$$\small F* I(x,y)=\Tiny\begin{bmatrix}F[N,N]\,I[x-N,y-N]&\cdots&F[N,0]\,I[x-N,y-N]&\cdots& F[N,-N]\,I[x-N,y+N]\\ \vdots&\ddots&\vdots&\ddots&\vdots\\ F[0,N]\,I[x,y-N]&\cdots&F[0,0]\,I[x,y]&\cdots& F[0,-N]\,I[x,y+N]\\ \vdots&\ddots&\vdots&\ddots&\vdots\\ F[-N,-N]\,I[x+N,y-N]&\cdots&F[-N,0]\,I[x+N,y]&\cdots& F[-N,-N]\,I[x+N,y+N]\\ \end{bmatrix}$$

enter image description here


Convolution in DSP is meant to apply filters to the image (e.g. smoothing, sharpening). As an example, after convolving Joseph Fourier's face with a Gaussian convolution filter: $\small\begin{bmatrix} 1&4&7&4&1\\ 4&16&26&16&4\\ 7&26&41&26&7\\ 4&16&26&16&4\\ 1&4&7&4&1\end{bmatrix}$ the edges on his face are fuzzier:

enter image description here


Computationally, both operations are a Frobenius inner product, amounting to calculating the trace of a matrix multiplication.


Questions (reformulating after comments and first answer):

  1. Is the use of convolutions in CNN linked to FFT?

From what I gather so far the answer is no. FFTs have been used to speed up GPU implementations of convolutions. However, FFT are not usually part of the structure or activation functions in CNNs, despite the use of convolutions in the pre-activation steps.

  1. Is convolution and cross-correlation in CNN equivalent?

Yes, they are equivalent.

  1. If it is a simple as "there is no difference", what is the point of flipping the weights into the kernel matrix?

Neither the associativity of convolution (useful in math proofs), nor any considerations regarding FTs and the convolution theorem are applicable. In fact, it seems as though the flipping doesn't even take place (cross-correlation being simply mislabeled as convolution) (?).

$\endgroup$
  • $\begingroup$ Antoni can you point to any source where they flip the weights? As @hossein pointed out you can do anything with crosscorrelation that you can do with convolutions, just by flipping the ordering. So all this frequency domain stuff is irrelevant. $\endgroup$ – seanv507 Mar 27 '17 at 6:13
  • $\begingroup$ @seanv507 I edited my OP to include the source for what I believe you are asking me. I do get that convolution is the same operation as cross-correlation with a flipped filter matrix, but I don't get why we go over the "pain" of the discrete convolution if there isn't anything to it that couldn't be accomplished with correlation. The answer given is clearly knowledgeable, but it could be fitted into a comment, and does not explain the reason behind two distinct operations (is it a "tradition" from DSP carried over to ML?), the implications as to the learning process, and the relation to FT's. $\endgroup$ – Antoni Parellada Mar 27 '17 at 12:23
  • 1
    $\begingroup$ Antoni, there is no need to flip. It's more of a convention; in dsp people talk about convolution rather than cross correlation, and cross correlational neural networks doesn't roll off the tongue. But the more natural (for humans to interpret) operation is cross correlation (you are template matching) for CNN (consider eg a vertical edge filter rather than a rotation symmetric) . So I think Hugo larochelle is maybe talking about numerical libraries where convolution rather than cross correlation is standard function.(he is effectively saying cross correlation can be done by a convolution.) $\endgroup$ – seanv507 Mar 27 '17 at 20:54
  • 1
    $\begingroup$ Antoni, agree on the 2 first questions/answers, and my comment was answering the 3rd question. $\endgroup$ – seanv507 Mar 27 '17 at 21:04
  • 1
    $\begingroup$ While there isn't necessarily a direct link between CNN's and FFT's, there is evidence that shows that you can obtain speedup of CNN's by using FFT's when you retain the usual convolution sum. See here for example: arxiv.org/pdf/1312.5851.pdf $\endgroup$ – Alex R. Mar 27 '17 at 21:34
8
$\begingroup$

There are no differences in what neural networks can do when they use convolution or correlation. This is because the filters are learned and if a CNN can learn to do a particular task using convolution operation, it can also learn to do the same task using correlation operation (It would learn the rotated version of each filter).

To find more details about the reasons that people sometimes find it more intuitive to think about convolution than correlation, this post may be useful.

There remains this question that if there is no difference between convolution and cross-correlation, what is the point of flipping the weights into the kernel matrix? I would like to include some sentences from the Deep learning book by Ian Goodfellow et al. to answer this question:

"The only reason to flip the kernel is to obtain the commutative property. While the commutative property is useful for writing proofs, it is not usually an important property of a neural network implementation... Many machine learning libraries implement cross-correlation but call it convolution."

The takeaway is that although convolution is a favorite operation in classic machine vision applications, it is replaced by correlation in many of the implementations of the convolutional neural networks.

$\endgroup$
  • $\begingroup$ Thank you. I read with attention the blog you link to, and it seems as though the use of convolution is not simply equivalent to correlation, and does respond to frequency-domain feature selection. I am looking for an answer elaborating on this. $\endgroup$ – Antoni Parellada Mar 26 '17 at 10:19
  • $\begingroup$ As I know, they are equivalent in what they can do, since both do a dot product of two matrices, but the convolution flips the filter matrix before dot product, and since CNNs learn the filters, they can learn the flipped filters. $\endgroup$ – Hossein Mar 26 '17 at 11:00
  • $\begingroup$ +1 to Hosseins explanation, but -1 for the blog link. The blog is mainly focused on hardware, and he is a CS guy with no background in convolution and other signal processing concepts. $\endgroup$ – seanv507 Mar 27 '17 at 6:03
  • $\begingroup$ I would like to still insist on having some additional paragraph on the relationship (or lack thereof) between convolution in CNNs and Fourier transforms. $\endgroup$ – Antoni Parellada Mar 28 '17 at 21:04
2
$\begingroup$

There's a practical reason for the link between FFTs and convolution.

Convolution is slow in the time/image domain. Applying an $n \times n$ filter to one pixel requires $O(n^2)$ multiplications and additions. Applying it to every pixel in an $N \times N$ image thus requires $n^2N^2$ operations. This grows quickly, and the large number of operations not only requires extra time, but also introduces more numerical error.

The Convolution Theorem says that convolution in the time domain is equivalent to pointwise multiplication in the frequency domain. FFTs are fast: they have good asymptotic performance $O(N^2 \log N^2)$ and the actual implementations are often highly optimized. Switching to the Fourier domain thus lets you perform a convolution in $O(N^2)$ time (which is dominated by the pointwise multiplication), instead of $O(n^2N^2)$. This can provide a considerable speedup, even though it seems much more complicated to go down the FFT -> multiplication -> inverse FFT route. More here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.