How translation invariance is achieved in CNNs?

Question

I am trying to understand how translation invariance is achieved in CNNs. For example, consider the following simple binary classification problem: predicting whether the letter that appears on an image is A or B.

We want our network to be translation invariant. That is, if we translate our input, the final output (i.e. the predicted probability) should be the same in both the original and the translated version of the image. Mathematically, we want:

$$y = f(T(x)) = f(x)$$

where $x$ is the original image and $T(x)$ its translated version. For example, in the following image:

our output $y$ must be the same.

Can someone explain how this translation invariance is achieved with the MaxPooling layers?

My view (possibly wrong)

First, I will present how I understand the network achieves this translation invariance and then I will provide an explanation why we need pooling.

1. Given that the feature maps of a CNN are equivariant (thanks to the convolution operation) as we translate the input these feature maps vary in the same way. That is, if a feature was present in position $x$ of the feature map, after we translate the image by $T$, it will appear now in position $T(x)$. Visualizing this:

And as we go deeper into the network where it learns to recognizes A or B, these feature maps will follow the same behavior. So assuming multiple Conv layers (reducing the dimensionality, e.g. from input 28x28 to 2x2) eventually we will get either a black (presence of A) or a white pixel (not presence of A).

2. The case where I think MaxPooling is useful is if we consider a slightly different input image such as in the following example.

Now the \ edge has move slightly to the right compared to the /. This slight translation is captured by the first Conv1 layer. But what about the Conv2 layer? Will it be able to detect the presence of the edge?

This might not be the case as shown in the final image. In the right figure we must detect a face, but if the relative positions are slightly changed (mouth is translated slightly downwards), then we might not detect the face at all.

However, if we use a MaxPooling layer between Conv1 and Conv2 then we will get the same feature map as in the case of the original image (putting the feature again into "focus" for the next layer).

Answer 1

Take a vector: $V_1 = [v_1, v_2, ..., v_n]$
Calculate the max: $m_1 = \max V_1 = v_i$
Shuffle the vector: $V_2 = mix(V_1)$
Calculate the max: $m_2 = \max V_2 = v_j$

The only possible outcome is that $m_1 = m_2$

taking the maximum creates an invariance... if you keep on staking convolution and max pooling, ending up with a single value, then you are totally invariant to translation, instead if you stop before that, you are "almost" invariant"

Answer 2

When you apply a convolutional layer to an image $x$, you obtain a certain list of values:

$$h_1(x), h_2(x), h_3(x), ..., h_n(x) \tag 1$$

where each $h_i$ is just the function that applies the convolutional filter to a particular patch of the image, and $n$ equals the number of patches (determined by the size of the filter, the size of the image, and the stride).

If the image $x$ consists of a solid blank background with some shape drawn on it, and you translate that shape within the image boundaries, producing a new image $x'$, now when you pass that in you'll get:

$$h_1(x'), h_2(x'), h_3(x'), ..., h_n(x') \tag 2$$

The point is that the list of values (2) is just a shuffling of the list of values (1). For example, if $h_i(x)$ is the result of lining up the kernel with the top-left of the shape in $x$, then for some $j$ the function $h_j$ will correspond to that same position for $x'$, and so $h_j(x')=h_i(x)$.

(This is not quite correct if the stride of the convolution is bigger than one - in that case what list of values you end up with depends on how the position of the shape in the image lines up with the stride, but the list (2) will still be "approximately" a shuffling of (1))

Now if the next step of your network involves piping all these values into some symmetric function such as max or sum or mean, the output of the network is guaranteed to be the same for $x'$ as for $x$.