Md. Asif Uddin
    Problem I.11.B04

    A one-pixel shift can cross a pooling boundary

    counterexample▲▲△

    Exact integers and fractions where possible; six decimals otherwise.

    STATEMENT

    Identify exactly which location changes a pooled representation forgets.

    GIVEN

    Use one-dimensional width-two max pooling with stride two, no padding. Consider a=(1,0,0,0)a=(1,0,0,0), b=(0,1,0,0)b=(0,1,0,0) and c=(0,0,1,0)c=(0,0,1,0). Also consider width-two average pooling with the same stride.

    FIND

    All pooled outputs. Decide whether the operation is invariant under every one-position right shift and whether its output determines the original input.

    STRATEGY

    Write the two disjoint windows explicitly. Distinguish a permutation inside one window from movement into another window.

    SOLUTION

    Max pooling yields

    Pmax⁡(a)=(1,0),Pmax⁡(b)=(1,0),Pmax⁡(c)=(0,1).\begin{aligned} P_{\max}(a)&=(1,0),\\ P_{\max}(b)&=(1,0),\\ P_{\max}(c)&=(0,1). \end{aligned}

    The shift from aa to bb stays within the first window and leaves its maximum unchanged. The equally small shift from bb to cc crosses a window boundary and changes the output.

    Average pooling gives (1/2,0)(1/2,0), (1/2,0)(1/2,0) and (0,1/2)(0,1/2). The same boundary distinction remains.

    Both maps are many-to-one: aa and bb have different locations but identical pooled outputs. No deterministic inverse receiving only that output can reconstruct both correctly. This proves loss of information for these maps, without claiming that every downsampling transform is lossy.

    Answer

    Pooling is invariant to these within-window rearrangements, not to every small translation of the whole signal. It cannot recover the lost location from the pooled values alone.

    Check — sanity

    A two-position shift aligned to the stride moves the pooled response by one position, provided the signal and boundaries are treated consistently. That is an equivariance relation, not an unchanged output.

    Where this breaks

    The argument depends on the window partition. Changing stride, padding or the reduction changes the equivalence classes of inputs. Extra side information, such as stored argmax indices, also changes what a decoder receives.

    Variation

    The vectors (1,1)(1,1) and (0,2)(0,2) have the same mean but different maxima. Max and average pooling discard different information even in one window.

    Draws on