Implement the Max-Pooling operation from Convolutional Neural Networks

Question

In convolutional neural networks, one of the main types of layers usually implemented is called the Pooling Layer. Sometimes, the input image is big (and therefore time consuming especially if you have a big input set) or there is sparse data. In these cases, the objective of the Pooling Layers is to reduce the spatial dimension of the input matrix (even though you would be sacrificing some information that could be gathered from it).

A Max-Pooling Layer slides a window of a given size \$k\$ over the input matrix with a given stride \$s\$ and get the max value in the scanned submatrix. An example of a max-pooling operation is shown below:

In the example above, we have an input matrix of dimension 4 x 4, a window of size \$k=2\$ and a stride of \$s=2\$.

Task

Given the stride and the input matrix, output the resulting matrix.

Specs

• Both the input matrix and the window will always be square.
• The stride and the window size will always be equal, so \$s=k\$.
• The stride is the same for the horizontal and the vertical direction
• The stride \$s\$ will always be a nonzero natural number that divides the dimension of the input matrix. This guarantees that all values are scanned by the window exactly once.
• Input is flexible, read it however you see fit for you.
• Standard loopholes are not allowed.

Test Cases

Format: 
s , input, output

2, [[2, 9, 3, 8], [0, 1, 5, 5], [5, 7, 2, 6], [8, 8, 3, 6]] --> [[9,8], [8,6]]
1, [[1, 2, 3], [4, 5, 6], [7, 8, 9]] --> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
4, [[12, 20, 30, 0], [8, 12, 2, 0], [34, 70, 37, 4], [112, 100, 25, 12]] --> [[112]]
3, [[0, 1, 2, 3, 4, 5, 6, 7, 8], [9, 10, 11, 12, 13, 14, 15, 16, 17], [18, 19, 20, 21, 22, 23, 24, 25, 26], [27, 28, 29, 30, 31, 32, 33, 34, 35], [36, 37, 38, 39, 40, 41, 42, 43, 44], [45, 46, 47, 48, 49, 50, 51, 52, 53], [54, 55, 56, 57, 58, 59, 60, 61, 62], [63, 64, 65, 66, 67, 68, 69, 70, 71], [72, 73, 74, 75, 76, 77, 78, 79, 80]] --> [[20, 23, 26], [47, 50, 53], [74, 77, 80]]

This is code-golf, so shortest answers in bytes wins!

Answer 1

Python 3, 101 108 bytes

def f(m,w):r=range(0,len(m),w);return[[max(sum([x[i:i+w]for x in m[j:j+w]],[]))for i in r]for j in r]

Thanks to Jo King and Jonathan Allan for some more bytes off!

Try it online!

Alternate (longer) version as a single Lambda expression:

Try it online!

Answer 2

Jelly, 6 bytes

»⁹/Z$⁺

A dyadic Link accepting the matrix (list of lists) on the left and the window size on the right which yields a matrix (list of lists).

Try it online!
Or see all windows of a 24*24 grid pooled at each possible granularity

How?

»⁹/Z$⁺ - Link: M, k
    $  - last two links as a monad - i.e. f(X) where X is initially M
  /    -   reduce (X)...
 ⁹     -     ...in chunks of: chain's right argument (k)
»      -     ...by: (left) maximum (right) (this vectorises across the k rows)
   Z   -   transpose the resulting matrix
     ⁺ - repeat the last link - i.e. f(that result)

Answer 3

Octave with Image Package, 38 bytes

@(M,s)blockproc(M,[s s],@(b)max(b(:)))

Try it online!

Answer 4

J, 15 14 bytes

-1 byte, thanks @Bubbler

The left argument is the matrix and the right argument is the stride.

>./@,;.3~2 2&$

Try it online!

Answer 5

J, ₁₃ 12 bytes

>./\&|:^:2~-

Try it online!

... When I said ";.3 is the right tool for the job", I was wrong. This challenge is so simple that an alternative method can get to fewer bytes.

How it works

>./\&|:^:2~-  Left argument: matrix, Right argument: stride (s)
           -  Negate the right argument
       ^:2~   Run the thing twice, with flipped arguments:
              (now the left is -s, right is matrix)
    &|:         Transpose both the matrix and -s
                (transpose on -s is no-op)
>./\            Run "reduce by max" on each of non-overlapping intervals of
                length s, in the primary dimension
              By running this twice, we achieve max pooling in two dimensions

Answer 6

Python 2, 68 bytes

lambda M,k:eval("map(lambda*l:map(max,zip(*[iter(l)]*k)),*"*2+"M))")

Try it online!

---

74 bytes

lambda M,k:eval("zip(*map(lambda*N:map(max,*N*2),*k*[iter("*2+"M)])))]))")

Try it online!

I can't even ...

Answer 7

APL (Dyalog Unicode), 20 bytes

{⌈⌿⍤2⌈/⍵}⊢⍴⍨4⍴÷⍨∘≢,⊣

Try it online!

I'm pretty sure converting the dfn part into an atop (⌈⌿⍤2⌈/) should work (and save a byte), but there seems to be an anomaly that prevents me from running multiple test cases with that version.

How it works

{⌈⌿⍤2⌈/⍵}⊢⍴⍨4⍴÷⍨∘≢,⊣  left: stride (s), right: matrix
              ÷⍨∘≢    a = size of matrix divided by stride
                  ,⊣  Concatenate a with s
            4⍴        Create a length-4 array (a s a s)
         ⊢⍴⍨          Reshape the matrix into a 4-dimensional array with shape a,s,a,s
{       }             Pass the result into the dfn...
     ⌈/⍵              Take the max through the 4th axis (shape: a,s,a)
 ⌈⌿⍤2                 Take the max through the 2nd axis (shape: a,a)

APL also has an operator called "Stencil" ⌺ that is similar to J's "Subarrays" ;.3, but it has a weird starting location, making it clunky to use for this challenge.

Answer 8

J, 23 bytes

(#@];~@$1{.~[)>./@,;.1]

Try it online!

Answer 9

05AB1E, 8 7 bytes

ôεø¹ôεZ

-1 byte thanks to @Grimy.

Stride as first input and matrix as second input.

Try it online or verify all test cases.

Explanation:

ô        # Split the rows of the (implicit) input-matrix into
         # the (implicit) input-integer amount of groups
         #  i.e. [[12,20,30,0],[8,12,2,0],[34,70,37,4],[112,100,25,12]] and 2
         #   → [[[12,20,30,0],[8,12,2,0]],[[34,70,37,4],[112,100,25,12]]]
 ε       # Map each group of rows to:
  ø      #  Zip/transpose; swapping rows/columns
         #   i.e. [[12,20,30,0],[8,12,2,0]] → [[12,8],[20,12],[30,2],[0,0]]
   ¹ô    #  Split the columns into the input-integer amount of groups as well
         #   i.e. [[12,8],[20,12],[30,2],[0,0]] → [[[12,8],[20,12]],[[30,2],[0,0]]]
     ε   #  Inner map over each block:
      Z  #   And get the flattened maximum of the block
         #    i.e. [[12,8],[20,12]] → 20
         # (after which the result is output implicitly)

Answer 10

Wolfram Language (Mathematica), 23 bytes

BlockMap[Max,#2,{#,#}]&

Try it online!

Answer 11

dzaima/APL, 14 12 bytes

⊣t¨t←⌈/⍬∘⍮⍛⍴

Try it online!

Answer 12

JavaScript (ES6), 85 bytes

Takes input as (s)(matrix).

s=>m=>m.map((r,y)=>r.map((v,x)=>(r=M[Y=y/s|0]=M[Y]||[])[x=x/s|0]>v?0:r[x]=v),M=[])&&M

Try it online!

Answer 13

Charcoal, 24 bytes

ＮθＩＥ⪪ＥＡＥ⪪ιθ⌈λθＥ§ι⁰⌈Ｅι§νμ

Try it online! Link is to verbose version of code. Outputs each maximum on its own line, with matrix rows double-spaced. Explanation:

Ｎθ                          Input the stride
      Ａ                     Input matrix
     Ｅ                      Map over rows
         ι                  Current row
        ⪪ θ                 Split (horizontally) into windows
       Ｅ                    Map over windows
            λ               Current window
           ⌈                Take the maximum
    ⪪        θ              Split vertically into windows
   Ｅ                        Map over windows
              Ｅ§ι⁰          Map over horizontal maxima
                   Ｅι       Map over windowed rows
                     §νμ    Get windowed cell
                  ⌈         Take the maximum
  Ｉ                         Cast to string for implicit print

Ｅ§ι⁰Ｅι§νμ is effectively the nearest Charcoal has to a transpose operation, although obviously I can at least take the maximum of the transposed column in situ.

Answer 14

Python 3, 275 196 184 163 159 111 bytes

def f(s,m):r=range(len(m)//s);return[[max(b for k in range(s)for b in m[i*s+k][j*s:][:s])for j in r]for i in r]

Try it online!

Thanks to:
- @randomdude999 for saving me 12 bytes
- @Jitse for saving 48 bytes

Answer 15

Stax, 11 bytes

ó╚←XF«≡ûÖçx

Run and debug it at staxlang.xyz!

Unpacked (13 bytes) and explanation

X/{Mx/{:f|Mmm
X                Save window size to register X
 /               Take groups of X rows
  {         m    Map block over groups:
   M               Transpose (gets list of column segments)
    x/             Take groups of X column segments (our windows)
      {    m       Map block over windows:
       :f|M          Flatten and take maximum

Leaves the result on the stack, since arrays print as strings. That makes the output hard to determine. Here's a pretty version.

Answer 16

Ruby, 57 bytes

->m,w{g=->r{r.transpose.each_slice(w).map &:max};g[g[m]]}

Try it online!

Answer 17

Japt, 24 bytes

mòY=UÊzV)Õc òYp)®rwÃòV y

Try it

U.m("ò", // split each row by..
 Y = U.l().z(V)) // input size / s
.y() // transpose
.c() // flatten
.ò(Y.p()) // split in Y*Y chunks
.m(function(Z) { return Z.r("w") }) // max of each
.ò(V) // rematrix
.y() // retranspose