Translation invariance in max-pooling and cascading with convolutional layer

Apparently, one of the advantages of max-pooling is translation invariance:

It provides a form of translation invariance. Imagine cascading a max-pooling layer with a convolutional layer. There are 8 directions in which one can translate the input image by a single pixel. If max-pooling is done over a 2x2 region, 3 out of these 8 possible configurations will produce exactly the same output at the convolutional layer. For max-pooling over a 3x3 window, this jumps to 5/8.

I am assuming the author means doing a translation to the left/right of the image, passing through a max-pooling layer and convolving. Then comparing the outputs of the convolution with the same process but for a different translation direction

I even did a Python script to illustrate the process of max-pooling -> convolution with 8 different translations by one pixel and the original matrix

from itertools import product

from cv2 import warpAffine
from matplotlib.pyplot import figure, gca, imshow, show, subplot
from numpy import asarray, concatenate, eye, float32, max, min, mod, reshape, zeros
from numpy.random import binomial
from scipy.signal import convolve2d
from skimage.measure import block_reduce

def list_to_2d(x):
return reshape(asarray(x), (len(x), 1))

def npix_to_m(x):
return concatenate((eye(2), list_to_2d(item)), axis=1)

def show_images(xl):
vmin = min(asarray(xl))
vmax = max(asarray(xl))
figure(figsize=(4.6,4.6))
for (x, i) in zip(xl, range(len(xl))):
subplot(3, 3, i+1)
gca().xaxis.set_major_locator(plt.NullLocator())
gca().yaxis.set_major_locator(plt.NullLocator())
imshow(x, interpolation='None', cmap='gray', vmin=vmin, vmax=vmax)
show()

x = float32(binomial(3, 0.5, (10,10)))

translations = list(product((-1, 0, 1), repeat=2))

M_list = [npix_to_m(item) for item in translations]

x_trans = [warpAffine(x, M, (10,10)) for M in M_list]
show_images(x_trans)
print 'Original matrices\n'

x_maxp = [block_reduce(x, block_size=(2,2), func=max) for x in x_trans]
show_images(x_maxp)
print 'Max-pooled matrices\n'

filt = float32(binomial(3, 0.5, (2,2)))
x_conv = [convolve2d(x, filt, mode='valid') for x in x_maxp]
show_images(x_conv)
print 'Convolved max-pooled matrices\n'


These are the outputs:

As you can see none of them are exactly the same. So what am I not understanding here?

The idea of complex cell layer is to "pool" a set of simple cells and acquire the same data from those simple cells (e.g invariant translation, rotation invariant, etc). One nice illustration is the computational model of Neocognitron https://youtu.be/Qil4kmvm2Sw?t=6m9s

As for the example of translating 2x2 and 3x3 matrix by one pixel in deeplearning.net, I think one possible explanation is that the Pooling map returns the same value for the subsequent Convolution map. Considering the following 4x4 image with our significant data in 2x2 region (row = 2, col = 2) to (3,3):

0 0 0 0
0 1 6 0
0 2 3 0
0 0 0 0

The Max-Pooling map always look at the region (2,2) and (3,3) and it returns 6. If our data were translated (moved) one pixel, there would be 8 different ways to do that. Among those there are 3 ways that keep region ((2,2); (3,3)) has 6 as the maximum value:

drow = 1, dcol = 0
0 0 0 0
0 0 0 0
0 1 6 0
0 2 3 0

drow = 0, dcol = -1
0 0 0 0
1 6 0 0
2 3 0 0
0 0 0 0

drow = 1, dcol = -1
0 0 0 0
0 0 0 0
1 6 0 0
2 3 0 0

That said, if our data is represented by the maximum value then the recognition will work for all those 3 cases.

When applying the same translation process (by 1 pixel) for 3x3 matrix

1 2 3
4 5 6
7 8 9

The the maximum value at the corner (1, 3, 7, 9) will be retained in 3 translations, the value in the middle of each edge (2, 4, 6, 8) will be retained in 5 translations. The simple cells are responsible for line/edge detection, so probably the center position (5) is left out.

That's how I understand translation invariance. I'm not completely sure though, since the author stated that "[...]produce exactly the same output at the convolutional layer." It would be great if the author of deeplearning.net could explain a bit more on that.