Making sense of indices in 2D convolution operations in convolutional neural networks

Question

Referring to the answer here: https://www.quora.com/Why-are-convolutional-nets-called-so-when-they-are-actually-doing-correlations, the equation for a discrete 2D convolution is specified as:

$$C(x,y)=\sum_{m=1}^M\sum_{n=1}^NI(m,n)K(x-m,y-n)$$

or

$$C'(x,y)=\sum_{m=1}^M\sum_{n=1}^NI(x-m,y-n)K(m,n)$$

where $I$ is the image and $K$ is the kernel or filter. I can't understand how the indices work. Let's say I have the image:

$\begin{bmatrix}I_{11} & I_{12} & I_{13} & I_{14} & I_{15}\\ I_{21} & I_{22} & I_{23} & I_{24} & I_{25}\\ I_{31} & I_{32} & I_{33} & I_{34} & I_{35}\\ I_{41} & I_{42} & I_{43} & I_{44} & I_{45}\\ I_{51} & I_{52} & I_{53} & I_{54} & I_{55} \end{bmatrix}$ and kernel $\begin{bmatrix}K_{11} & K_{12} & K_{13}\\ K_{21} & K_{22} & K_{23}\\ K_{31} & K_{32} & K_{33}\end{bmatrix}$

Now by the above definition (in this case $M=3$ and $N=3$) $$C_{11} = I_{11}K_{00}+I_{12}K_{0,-1}+I_{13}K_{0,-2}\\ +I_{21}K_{-1,0}+I_{22}K_{-1,-1}+I_{23}K_{-1,-2}+\\ +I_{31}K_{-2,0}+I_{32}K_{-2,-1}+I_{33}K_{-2,-2}$$

or

$$C'_{11} = I_{00}K_{11}+I_{0,-1}K_{12}+I_{0,-2}K_{13}\\ +I_{-1,0}K_{21}+I_{-1,-1}K_{22}+I_{-1,-2}K_{23}+\\ +I_{-2,0}K_{31}+I_{-2,-1}K_{32}+I_{-2,-2}K_{33}$$

Even if I assume that the indices for $C$ or $C'$ run from $2$ to $4$ (instead of $1$ to $3$), then $$C_{22} = I_{11}K_{11}+I_{12}K_{1,0}+I_{13}K_{1,-1}\\ +I_{21}K_{0,1}+I_{22}K_{0,0}+I_{23}K_{0,-1}+\\ +I_{31}K_{-1,1}+I_{32}K_{-1,0}+I_{33}K_{-1,-1}$$

or

$$C'_{22} = I_{11}K_{11}+I_{1,0}K_{12}+I_{1,-1}K_{13}\\ +I_{0,1}K_{21}+I_{0,0}K_{22}+I_{0,-1}K_{23}+\\ +I_{-1,1}K_{31}+I_{-1,0}K_{32}+I_{-1,-1}K_{33}$$

So no matter how the indices are defined, the indices for either $I$ or $K$ go out of bounds in the expression for convolution. How do I make sense of this? What's meant by terms with negative indices like $I_{-1,-2}$ or $K_{0,-1}$?

---

Follow-up doubt: So assuming zero-padding, all terms with non-positive indices are assumed to be $0$. From that, given the two formulas for $C_{22}$ and $C'_{22}$ above, they evaluate to just $I_{11}K_{11}$, since all terms involving non-positive indices vanish. But that doesn't sound right, since from my understanding, it should evaluate to:

$$\begin{bmatrix}I_{11} & I_{12} & I_{13}\\ I_{21} & I_{22} & I_{23}\\ I_{31} & I_{32} & I_{33}\end{bmatrix}: \begin{bmatrix}K_{33} & K_{32} & K_{31}\\ K_{23} & K_{22} & K_{21}\\ K_{13} & K_{12} & K_{11}\end{bmatrix}$$

(where $:$ represents Frobenius inner product) since convolution is the same as cross-correlation with a flipped kernel. So I still can't make sense of the formulas for $C_{22}$ and $C'_{22}$ as I wrote above.

Answer 1

From http://www.deeplearningbook.org/contents/convnets.html,

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. Instead, many neural network libraries implement a related function called the cross-correlation, which is the same as convolution but without flipping the kernel.

The discrete cross correlation function with 1-based indexing for $$I = U*V\ and\ K=M*N$$ is given by $$C(x,y)=\sum_{m=1}^M\sum_{n=1}^NI(x+m-1,y+n-1)K(m,n)$$

where $$x\in(U-M+1)\ and\ y\in(V-N+1)$$

When applying 2-D convolutions, many neural network implementations will reduce the size of the output. To retain the original size in output and to retain information at the borders, many practical use cases add a padding of zeros to the input image.

Coming back to your specific question, in the case where indices go out of bounds, either on the positive side or on the negative side, (which happens when you try to retain the size of the input in your output), values corresponding to them are usually taken as zeros, which is akin to zero-padding in implementation.

Discrete convolutions are actually given by $$(f * g)[n] = \sum_{m=-\infty}^\infty f[n-m] g[m]$$ In practice the limits are made finite because of the same assumption of zero amplitude signal for out of bound indices.