What would be the intuition behind using the convolution and cross correlation operation inside Convolutional Neural Networks? I am interested in putting together the theory from Digital Image Processing where these 2x operations are defined, and CNNs. Could anyone help me connect the dots?
1 Answer
A neural network takes every input into a neuron and then through an activation function the neuron produces an output. When applying this method to images we can quickly see that this is not an ideal solution. The similarity of a pixel is much more related to a neighboring pixel.
The convolution operation in deep learning was used for this exact purpose. It is better to focus on the neighborhood of inputs before considering the correlation of that pixel with those on the other side of the image. So we can instead apply a mask that will mix the neighborhood of pixels.
Before we get into some theory, it is important to note that in CNNs although we call it a convolution, it is actually cross-correlation. It is a technicality, but in a CNN we do not flip the filter as is required in typical convolutions. However except for this flip, both operations are identical.
Discrete convolutions
From the wikipedia page the convolution is described as
$(f * g)[n] = \sum_{m=-\inf}^{\inf} f[m]g[n-m]$
For example assuming $a$ is the function $f$ and $b$ is the convolution function $g$,
To solve this we can use the equation first we flip the function $b$ vertically, due to the $-m$ that appears in the equation. Then we will calculate the summation for each value of $n$. Whilst changing $n$, the original function does not move, however the convolution function is shifted accordingly. Starting at $n=0$,
$c[0] = \sum_m a[m]b[-m] = 0 * 0.25 + 0 * 0.5 + 1 * 1 + 0.5 * 0 + 1 * 0 + 1 * 0 = 1$
$c[1] = \sum_m a[m]b[-m] = 0 * 0.25 + 1 * 0.5 + 0.5 * 1 + 1 * 0 + 1 * 0 = 1$
$c[2] = \sum_m a[m]b[-m] = 1 * 0.25 + 0.5 * 0.5 + 1 * 1 + 1 * 0 + 1 * 0 = 1.5$
$c[3] = \sum_m a[m]b[-m] = 1 * 0 + 0.5 * 0.25 + 1 * 0.5 + 1 * 1 = 1.625$
$c[4] = \sum_m a[m]b[-m] = 1 * 0 + 0.5 * 0 + 1 * 0.25 + 1 * 0.5 + 0 * 1 = 0.75$
$c[5] = \sum_m a[m]b[-m] = 1 * 0 + 0.5 * 0 + 1 * 0 + 1 * 0.25 + 0 * 0.5 * 0 * 1 = 0.25$
As you can see that is exactly what we get on the plot $c[n]$. So we shifted around the function $b[n]$ over the function $a[n]$.
2D Discrete Convolution
For example, if we have the matrix in green
with the convolution filter
Then the resulting operation is a element-wise multiplication and addition of the terms as shown below. Very much like the wikipedia page shows, this kernel (orange matrix) $g$ is shifted across the entire function (green matrix) $f$.
You will notice that there is no flip of the kernel $g$ like we did for the explicit computation of the convolution above. This is a matter of notation. This should be called cross-correlation, it is not a true convolution. However, computationally this difference does not affect the performance of the algorithm because the kernel is being trained such that its weights are best suited for the operation, thus adding the flip operation would simply make the algorithm learn the weights in different cells of the kernel to accommodate the flip. So we can omit the flip.
-
$\begingroup$ Thank you for your answer! But I was expecting a little bit more detailed answer on the math and the relationship with DSP field. $\endgroup$ Nov 2, 2018 at 10:13
-
3$\begingroup$ @StefanRadonjic I updated the answer. By the way the definition of intuition is "the ability to understand something immediately, without the need for conscious reasoning." $\endgroup$– JahKnowsNov 3, 2018 at 12:37
-
$\begingroup$ Thank you so much, and thanks for correcting me. I will keep that in mind :) $\endgroup$ Nov 3, 2018 at 16:18
-
$\begingroup$ @JahKnows Thank you for your explanation. But in terms of the redundancy of flipping, does this because we will always land in the same set of parameters despite the non-convexity of the optimization problem? $\endgroup$– Mr.RobotNov 1, 2019 at 5:13