How can we compute the gradient of max pooling with overlapping regions?

Question

While studying backpropagation in CNNs, I can't understand how can we compute the gradient of max pooling with overlapping regions.

That's also a question from this quiz and can be also found on this book.

Answer 1

When gradients in a neural network can follow multiple paths to same parameter, the different gradient values from the sources can often be added together, because the operations in the forward direction are also sums and $\frac{d}{dx}(y+z) = \frac{dy}{dx} + \frac{dz}{dx}$.

That is the case already with gradients of kernels (which are sums over the image area), and is equally the case for overlapping aggregation, including maximums, minimums or averages.

So in the 1d case, if you have a max pool over the input params $[a_0, a_1, a_2, a_3, a_4]$ a max function $m_0 = max(a_0, a_1, a_2)$, $m_1 = max(a_2, a_3, a_4)$ which overlap at $a_2$, and gradients $\nabla_{\mathbf{m}} J = [\frac{\partial J}{\partial m_0}, \frac{\partial J}{\partial m_1}]$, then you would allocate those gradients to vector $\mathbf{a}$ according to which items in each group was the max of that group, adding them when they overlapped.

Examples:

If $\mathbf{a} = [3,0,1,2,0]$ and $\nabla_{\mathbf{m}}J = [0.7, 0.9]$, then $\nabla_{\mathbf{a}}J = [0.7, 0, 0, 0.9, 0]$

If $\mathbf{a} = [3,0,4,2,0]$ and $\nabla_{\mathbf{m}}J = [0.7, 0.9]$, then $\nabla_{\mathbf{a}}J = [0, 0, 1.6, 0, 0]$

Answer 2

Denote x(h,w) input to max-pooling, and y(h,w) - output.

Then $\frac{dL}{dx}(h,w)= \sum \frac{dL}{dy}(h',w')$

over all y(h',w') which have been obtained from x(h.w) such that y(h',w') = x(h,w).

related to this p 11