1
$\begingroup$

I was trying to pin point precisely mathematically what the convolution does for a simple 1D example (i.e. $x \in \mathbb{R}^D$ as opposed to an image $x \in \mathbb{R}^{D_1 \times D_2}$).

The precise mathematical definition of the convolution (as expressed by Y.Bengio's book ) is:

$$ s(i) = (I * K)(i) = \sum^{\infty}_{a = - \infty} I[a] K[i - a]$$

So I was trying to apply that equation to a simple example of a convolution of a CNN.

So I had the simple example where the kernel (filter/template) was the function as follows:

$ k(x) = \begin{cases} \begin{array}{cc} k_{-3} & x = -3 \\ k_{-2} & x = -2 \\ k_{-3} & x = -1 \\ 0 & otherwise \end{array} \end{cases} $

Say that we have a 1D image $ I \in \mathbb{R}^D$. We could just graph its values as the y axis in a graph and the indices as the x-axis.

So mathematically, s(1) would be:

$$s(1) = \sum^{\infty}_{a = - \infty} I[a] K[1 - a] $$ $$s(1) = I[2]K[-1] + I[3]K[-2] + I[4]K[-3] = I[2]k_{-3} + I[3]k_{-2} + I[4]k_{-1} $$

Which makes sense to me when the kernel and the vector are visualized as function on the real line.

However, what I have a hard time interpreting is what $K[i -a]$ means when we are trying to convolve a vector with another vector $I[a]$. Usually, if we imagine them in the real line it makes sense, but $K$ having negative indexes makes no sense to me. Usually $K[i-a]$ means to "reflect" the values around the y-axis and then translate to the right by i units. However, that doesn't quite make sense to me in the discrete case.

What particularly confuses me is how the "real" convolution (I described in this simple example) relates to the convolution expressed in the Stanford tutorial with the following gif:

enter image description here

Can someone explain that to me? How does the reflection work with discrete indices? Is it just reversing the array? Also, how would that explain what the offset/translation is suppose to mean in this context? What is the deal with negative indices?

$\endgroup$
4
  • 1
    $\begingroup$ Many years ago I published a plain, simple explanation of discrete convolution. It can still be found at directionsmag.com/entry/convolution/129753. (Links there are broken. The continuations to parts 2 and 3 are at directionsmag.com/entry/convolution-part-2-of-3/129751 and directionsmag.com/entry/convolution-part-3-of-3/129750.) $\endgroup$
    – whuber
    Jul 9, 2015 at 14:49
  • $\begingroup$ @whuber the thing is that I am not confused about the convolution in terms of mathematics. I understand the definition when we have actual functions defined on real numbers. What confuses me is that in a CNN we have a list of numbers and it doesn't makes sense to me to reflect/translate the list of numbers. To start off negative indices don't really make sense and stuff like that. Its very ambiguous what the convolution is in a CNN to and the gif that I pasted doesn't seem to implement exactly what the convolution is. I'm just confused on whats going on in CNNs. $\endgroup$ Jul 9, 2015 at 15:37
  • 1
    $\begingroup$ My article is not about the mathematics--it is about explaining exactly what the formula is doing. (It was written for a very nonmathematical audience.) The indexes are offsets, so negative indexes make perfect sense. $\endgroup$
    – whuber
    Jul 9, 2015 at 15:45
  • $\begingroup$ @whuber in the example from the gif I gave from Stanford guide, the kernel/filter is being flipped, right? $\endgroup$ Jul 10, 2015 at 5:38

1 Answer 1

1
$\begingroup$

First, are you familiar with convolution in the 2 dimensional case? It will look like this:

$$ s(i, j) = (I * K)(i, j) = \sum^{\infty}_{a = - \infty} \sum^{\infty}_{b = - \infty} I[a, b] K[i - a, j-b]$$

You can still envision $K[i-a, j-b]$ as a reflection (about the origin) and translation.

Second, yes, I think the Stanford tutorial is using a flipped kernel (though the one they picked is rotationally symmetric so it doesn't matter).

Finally, if you treat the 2-D matrix as being zero everywhere else (including for negative indices) it should make sense what's going on.

$\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.