CNN - upsampling backprop gradients across average-pooling layer

Question

How to up-sample gradients, during back-propagation, across an average-pooling layer?

For this purpose, let

$$ A^{[l]} = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}; \quad P^{[l]} = \begin{bmatrix} p_{11} & p_{12} \\ p_{21} & p_{22} \\ \end{bmatrix} = \begin{bmatrix} \frac{a_{11} + a_{12} + a_{21} + a_{22}}{4} & \frac{a_{12} + a_{13} + a_{22} + a_{23}}{4} \\ \frac{a_{21} + a_{22} + a_{31} + a_{32}}{4} & \frac{a_{22} + a_{23} + a_{32} + a_{33}}{4} \\ \end{bmatrix} \\ \frac{\mathrm{d}J}{\mathrm{d}P^{[l]}} = \begin{bmatrix} \frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{\mathrm{d}J}{\mathrm{d}p_{12}} \\ \frac{\mathrm{d}J}{\mathrm{d}p_{21}} & \frac{\mathrm{d}J}{\mathrm{d}p_{22}} \\ \end{bmatrix} $$

where, $A^{[l]}$ is the activation of layer-$l$ , and $P^{[l]}$ is the matrix obtained after average-pooling $A^{[l]}$ using a $2 \times 2$ pooling window, and $J$ is the cost function.

Given this, how to compute $\frac{\mathrm{d}J}{\mathrm{d}A^{[l]}}$?

• (Source) says, "the error is multiplied by $\frac{1}{2×2}$ and assigned to the whole pooling block (all units get this same value)." $\rightarrow$ then what would be the gradient $\frac{\mathrm{d}J}{\mathrm{d}a_{22}}$, which is a member of all the pooling blocks.
• (Source) the question mentions the up-sampling strategy, but doesn't mention what $\beta$ is.
• (Source) says, "if we have mean pooling then upsample simply uniformly distributes the error for a single pooling unit among the units which feed into it in the previous layer." $\rightarrow$ which is still vague.
• (Source) Zhang, Zhifei. "Derivation of backpropagation in convolutional neural network (cnn)." University of Tennessee, Knoxville, TN (2016). $\rightarrow$ pg.4, eq.32 results in the following up-sampled gradients $$ \frac{\mathrm{d}J}{\mathrm{d}A^{[l]}} = \begin{bmatrix} \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}} \\ \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}} \\ \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{21}} & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{21}} & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}} \\ \end{bmatrix} $$ Is this correct? And, if it is, then is there a mathematical basis for why the gradients are up-sampled this way?

Answer 1

It is not right. When the pool windows overlap, derivatives must be added. This is not explicitly stated in Sources 1-3. I couldn't see it in Source 4 as well but I'm not too sure as the document is long.

Addition happens simply because of the chain rule: $$\frac{\partial J}{\partial a_{ij}}=\sum_{m,n}\frac{\partial J}{\partial p_{mn}}\frac{\partial p_{mn}}{\partial a_{ij}}$$

For example, for $a_{12}$, we'll have

$$\begin{align}\frac{\partial J}{\partial a_{12}}& =\frac{\partial J}{\partial p_{11}}\frac{\partial p_{11}}{\partial a_{12}} +\frac{\partial J}{\partial p_{12}}\frac{\partial p_{12}}{\partial a_{12}} +\frac{\partial J}{\partial p_{21}}\frac{\partial p_{21}}{\partial a_{12}} +\frac{\partial J}{\partial p_{22}}\frac{\partial p_{22}}{\partial a_{12}}\\ &=\frac{\partial J}{\partial p_{11}}\frac{1}{4} +\frac{\partial J}{\partial p_{12}}\frac{1}{4} +\frac{\partial J}{\partial p_{21}}0 +\frac{\partial J}{\partial p_{22}}0\\ &=\frac{\partial J}{\partial p_{11}}\frac{1}{4} +\frac{\partial J}{\partial p_{12}}\frac{1}{4} \end{align}$$

It doesn't matter if this is pooling, upsampling/downsampling etc. We have a bunch of numbers $a_{ij}$, we transform and calculate a bunch of another numbers $p_{mn}$ and propagate until the loss is calculated. This should be treated like a usual transformation in order to comply with the mathematics.

Answer 2

This is based on gunes's answer above.

We can vectorize all the matrices as follows:

$$ \mathrm{vec}(A^{[l]}) = \begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \\ a_{12} \\ a_{22} \\ a_{32} \\ a_{13} \\ a_{23} \\ a_{33} \\ \end{bmatrix}; \qquad \mathrm{vec}(P^{[l]}) = \begin{bmatrix} p_{11} \\ p_{21} \\ p_{12} \\ p_{22} \\ \end{bmatrix}\\ \qquad \frac{\mathrm{d}J}{\mathrm{d}\{\mathrm{vec}(P^{[l]})\}} = \begin{bmatrix} \frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{\mathrm{d}J}{\mathrm{d}p_{21}} & \frac{\mathrm{d}J}{\mathrm{d}p_{12}} & \frac{\mathrm{d}J}{\mathrm{d}p_{22}} \end{bmatrix} \qquad\text{eq.1} $$

then compute the gradient $\frac{\mathrm{d}J}{\mathrm{d}A^{[l]}}$, as follows:

Note: I'm using the numerator-layout, so, the derivatives are technically Jacobians.

$$ \frac{\mathrm{d}J}{\mathrm{d}\{\mathrm{vec}(A^{[l]})\}} = \frac{\mathrm{d}J}{\mathrm{d}\{\mathrm{vec}(P^{[l]})\}} \frac{\mathrm{d}\{\mathrm{vec}(P^{[l]})\}}{\mathrm{d}\{\mathrm{vec}(A^{[l]})\}} \qquad\text{eq.2}\\ $$

here, $$ \begin{align} \frac{\mathrm{d}\{\mathrm{vec}(P^{[l]})\}}{\mathrm{d}\{\mathrm{vec}(A^{[l]})\}} & = \begin{bmatrix} \frac{\partial}{\partial a_{11}} & \frac{\partial}{\partial a_{21}} & \frac{\partial}{\partial a_{31}} & \frac{\partial}{\partial a_{12}} & \frac{\partial}{\partial a_{22}} & \frac{\partial}{\partial a_{32}} & \frac{\partial}{\partial a_{13}} & \frac{\partial}{\partial a_{23}} & \frac{\partial}{\partial a_{33}} \end{bmatrix} \otimes \begin{bmatrix} p_{11} \\ p_{21} \\ p_{12} \\ p_{22} \\ \end{bmatrix} \\ & = \begin{bmatrix} \frac{\partial p_{11}}{\partial a_{11}} & \frac{\partial p_{11}}{\partial a_{21}} & \frac{\partial p_{11}}{\partial a_{31}} & \frac{\partial p_{11}}{\partial a_{12}} & \frac{\partial p_{11}}{\partial a_{22}} & \frac{\partial p_{11}}{\partial a_{32}} & \frac{\partial p_{11}}{\partial a_{13}} & \frac{\partial p_{11}}{\partial a_{23}} & \frac{\partial p_{11}}{\partial a_{33}} \\ \frac{\partial p_{21}}{\partial a_{11}} & \frac{\partial p_{21}}{\partial a_{21}} & \frac{\partial p_{21}}{\partial a_{31}} & \frac{\partial p_{21}}{\partial a_{12}} & \frac{\partial p_{21}}{\partial a_{22}} & \frac{\partial p_{21}}{\partial a_{32}} & \frac{\partial p_{21}}{\partial a_{13}} & \frac{\partial p_{21}}{\partial a_{23}} & \frac{\partial p_{21}}{\partial a_{33}} \\ \frac{\partial p_{12}}{\partial a_{11}} & \frac{\partial p_{12}}{\partial a_{21}} & \frac{\partial p_{12}}{\partial a_{31}} & \frac{\partial p_{12}}{\partial a_{12}} & \frac{\partial p_{12}}{\partial a_{22}} & \frac{\partial p_{12}}{\partial a_{32}} & \frac{\partial p_{12}}{\partial a_{13}} & \frac{\partial p_{12}}{\partial a_{23}} & \frac{\partial p_{12}}{\partial a_{33}} \\ \frac{\partial p_{22}}{\partial a_{11}} & \frac{\partial p_{22}}{\partial a_{21}} & \frac{\partial p_{22}}{\partial a_{31}} & \frac{\partial p_{22}}{\partial a_{12}} & \frac{\partial p_{22}}{\partial a_{22}} & \frac{\partial p_{22}}{\partial a_{32}} & \frac{\partial p_{22}}{\partial a_{13}} & \frac{\partial p_{22}}{\partial a_{23}} & \frac{\partial p_{22}}{\partial a_{33}} \\ \end{bmatrix} \\ & = \begin{bmatrix} \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\ \end{bmatrix} \qquad\text{eq.3} \end{align} $$

from eq.1, eq.2, and eq.3, we have

$$ \begin{align} \frac{\mathrm{d}J}{\mathrm{d}\{\mathrm{vec}(A^{[l]})\}} & = \begin{bmatrix} \frac{\partial J}{\partial a_{11}} & \frac{\partial J}{\partial a_{21}} & \frac{\partial J}{\partial a_{31}} & \frac{\partial J}{\partial a_{12}} & \frac{\partial J}{\partial a_{22}} & \frac{\partial J}{\partial a_{32}} & \frac{\partial J}{\partial a_{13}} & \frac{\partial J}{\partial a_{23}} & \frac{\partial J}{\partial a_{33}} \\ \end{bmatrix} \\ & = \begin{bmatrix} \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{11}} \\ \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{11}} + \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{21}}\biggr) \\ \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{21}} \\ \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{11}} + \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}}\biggr) \\ \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{11}} + \frac{\mathrm{d}J}{\mathrm{d}p_{21}} + \frac{\mathrm{d}J}{\mathrm{d}p_{12}} + \frac{\mathrm{d}J}{\mathrm{d}p_{22}}\biggr) \\ \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{21}} + \frac{\mathrm{d}J}{\mathrm{d}p_{22}}\biggr) \\ \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}} \\ \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{12}} + \frac{\mathrm{d}J}{\mathrm{d}p_{22}}\biggr) \\ \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{22}} \\ \end{bmatrix}^\intercal \end{align} $$

And, reshaping the above matrix, we get

$$ \frac{\mathrm{d}J}{\mathrm{d}A^{[l]}} = \begin{bmatrix} \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{11}} & \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{11}} + \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{21}}\biggr) & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{21}} \\ \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{11}} + \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}}\biggr) & \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{11}} + \frac{\mathrm{d}J}{\mathrm{d}p_{21}} + \frac{\mathrm{d}J}{\mathrm{d}p_{12}} + \frac{\mathrm{d}J}{\mathrm{d}p_{22}}\biggr) & \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{21}} + \frac{\mathrm{d}J}{\mathrm{d}p_{22}}\biggr) \\ \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{12}} & \frac{1}{4}\biggl(\frac{\mathrm{d}J}{\mathrm{d}p_{12}} + \frac{\mathrm{d}J}{\mathrm{d}p_{22}}\biggr) & \frac{1}{4}\frac{\mathrm{d}J}{\mathrm{d}p_{22}} \\ \end{bmatrix} $$