Is this stack of CNN layers valid?

Question

Background

This challenge is about Convolutional neural networks, and its two main building blocks, namely Convolutional layer and Pooling layer.

For simplicity, we ignore the "depth" of the images and intermediate tensors, and just look at the width and height.

Convolutional layer

A convolutional layer works like a kernel in image processing. It is defined by kernel width and height, and kernel mode (min, mid, or max). A min kernel extracts values at positions where the entire kernel overlaps with the original image. For a mid kernel, the center of the kernel is placed over each pixel of the image; for a max kernel, all positions where any pixel overlaps with the kernel is considered.

One pixel per positioning of the kernel is produced, resulting in a 2D array which can be smaller than (min), equal to (mid), or larger than (max) the input image.

Kernel (C is the center)
###
#C#
###

Image
*****
*****
*****
*****
*****

Min kernel convolution (results in 3x3)
###**     **###
#C#**     **#C#
###** ... **###
*****     *****
*****     *****
 ...       ...
*****     *****
*****     *****
###** ... **###
#C#**     **#C#
###**     **###

Mid kernel convolution (results in 5x5)
###           ###
#C#***     ***#C#
###***     ***###
 ***** ... *****
 *****     *****
 *****     *****
  ...       ...
 *****     ***** 
 *****     ***** 
 ***** ... ***** 
###***     ***###
#C#***     ***#C#
###           ###

Max kernel convolution (results in 7x7)

###             ###
#C#             #C#
###****     ****###
  *****     *****
  ***** ... *****
  *****     *****
  *****     *****
   ...       ...
  *****     *****  
  *****     *****  
  ***** ... *****  
  *****     *****  
###****     ****###
#C#             #C#
###             ###

If the input image has IR rows and IC columns, and the kernel has KR rows and KC columns, the output dimensions are defined as follows:

• Min kernel: IR - KR + 1 rows, IC - KC + 1 columns; invalid if the resulting rows or columns are zero or negative
• Mid kernel: IR rows, IC columns; error if either KR or KC is even
• Max kernel: IR + KR - 1 rows, IC + KC - 1 columns

Pooling layer

A pooling layer is defined by window width and height, and the horizontal and vertical stride size (how many units to move at once in either direction). See the following illustration:

3x3 window, 2x2 stride pooling on a 7x7 image
###**** **###** ****###
###**** **###** ****###
###**** **###** ****###
******* ******* *******
******* ******* *******
******* ******* *******
******* ******* *******
                       
******* ******* *******
******* ******* *******
###**** **###** ****###
###**** **###** ****###
###**** **###** ****###
******* ******* *******
******* ******* *******
                       
******* ******* *******
******* ******* *******
******* ******* *******
******* ******* *******
###**** **###** ****###
###**** **###** ****###
###**** **###** ****###

If the input image has IR rows and IC columns, and the pooling layer has the window of WR/WC rows/columns and SH/SV horizontal/vertical stride, the output dimensions are defined as follows:

• Rows: (IR - WR)/SV + 1, error if (IR - WR) % SV != 0 or WR < SV
• Cols: (IC - WC)/SH + 1, error if (IC - WC) % SH != 0 or WC < SV

Stacking multiple layers

The convolutional and pooling layers can be stacked in any arbitrary way, so that the output of the previous layer becomes the input of the next layer. The dimensions of the input image to the entire stack is provided, and the dimensions of each intermediate image should be calculated sequentially. A stack of layers is valid if no error occurs at any layer. The final output size does not matter, as long as it can be calculated without error.

The following stack is valid:

Input image 25x25
1. Min Convolution 3x3         => Intermediate image 23x23
2. Pooling 3x3 with stride 2x2 => Intermediate image 11x11
3. Max Convolution 3x3         => Intermediate image 13x13
4. Max Convolution 4x4         => Intermediate image 16x16
5. Pooling 2x2 with stride 2x2 => Intermediate image 8x8
6. Min Convolution 5x5         => Intermediate image 4x4
7. Pooling 4x4 with stride 3x3 => Output image 1x1

Taking any contiguous subsequence of the stack, starting with the respective (intermediate) image as the input, is also valid. (e.g. steps 2, 3, 4, 5 with input image 23x23)

Any of the following modifications to the 7-layer stack above will result in an invalid stack:

• Replace step 2 with stride 4x4 or 2x4: stride is larger than window in at least one dimension
• Replace step 3 with mid convolution: image size becomes too small at step 7
• Replace step 4 with mid convolution: mid convolution with even kernel dimension is an error
• Replace step 6 with kernel size 9x5 or larger: kernel does not fit in the image (IR-KR+1 is zero or negative, which is an error)

Challenge

Given the input dimensions and the description of a stack of convolutional/pooling layers, determine if it is a valid configuration, i.e. not an error.

The description of the stack can be taken in reasonable ways to represent

• a list (sequence) of two kinds of layers
• for a convolutional layer, the kernel size (width/height; two numbers) and mode (min/mid/max)
• for a pooling layer, the window size (width/height) and stride (horizontal/vertical; four numbers in total)

All numbers (kernel size, window size, stride) are guaranteed to be positive integers.

You may output truthy/falsy by following your language's convention or selecting two distinct values for true/false respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Answer 1

Python 3.8 (pre-release), 138 134 118 bytes

lambda s,l:[s:=[(r:=(I-(m:=M-(M>1))*k)/S+m+0%(k%2+m**2))+(r%1+(S>k)and E)for I,k,S,*_ in zip(s,*L,(1,1))]for M,L in l]

Try it online!

Anonymous function that throws an error only if the given layers are in error. Takes a list of layers, where each layer is either:

• [mode, [KR,KC]] where mode is -1,0,or-1 corresponding to a max,mid, or min convolutional layer, or
• [2, [WR, WC], [SR, SC]] where the 2 indicates a pooling layer

I could save a few bytes if (1,1) could be added as a third element of convolutional layers, but I feel that's redundant information with the mode already differing it from pooling layers.

Commented

f=\
lambda s,l:\
 [
  s:=[             # set s (size) to:
   (
    r:=                # an optimized calculation of the new size (r) along width (i=0) or height (i=1)
                         # (need to set this to r because s is not updated until finishing this element)
                         # [IR - KR + 1, IR, IR + KR - 1, (IR - WR)/SV + 1]
                         # <--> (IR - m * KR)/(SV or 1) + m where m is -1 for max, 0 for mid, 1 for min, and 1 for pool
    (I-                    # (IR-
     (m:=M-(M>1))          #  m  # (need to convert pool(M=2) to 1, leave -1,0,1 unchanged) # maybe something with `M&2` might shorten
     *k)/                  # * KR)/
    S                      # SV
    +m                     # + m
    +0%(               # error if k is even and m==0 (mid):
    k%2+m**2             # This sum gives 0 iff k is even and m==0
    )                    # 0 mod the sum throws ZeroDivisionError if the sum is 0
   )                     # otherwise it is equal to 0 and does not affect the sum
   +(
     r%1+(S>k)         # True if r is not an integer or the stride size is greater than the window size
    and E              # throw NameError (E is not defined) if the above is true
   )                   # otherwise, False equals 0 in sums, so this does not affect the sum
   for I,k,S,*_ in zip(s,*L,(1,1))       # repeat for rows and columns
                                         # The (1,1) provides the default value of S
  ]
  for M,L in l  # repeat for each layer
 ]

Named function + traditional for-loop approach for the same bytecount:

def f(s,l):
 for M,L in l:s=[(r:=(I-(m:=M-(M>1))*k)/S+m+0%(k%2+m**2))+(r%1+(S>k)and E)for I,k,S,*_ in zip(s,*L,(1,1))]

Ungolfed

def f(size, layers):
    while layers:
        [mode, *layer] = layers.pop(0)

        if mode < 2:
            # convolutional, mostly eq to pooling with S=(1,1)
            layer += [(1,1)]

        kernel, stride = layer

        m = 1 if mode > 1 else mode
        for i in 0,1:
            size[i] = (size[i] - m*kernel[i])/stride[i] + m
            # check for fractions
            if size[i] % 1:
                return False
            # can't have even kernel dimension on a mid window
            if m==0 and kernel[i]%2==0:
                return False
            # stride can't be larger than kernel
            if stride[i] > kernel[i]:
                return False
    return True

Answer 2

05AB1E, 45 bytes

sεÐgiĀ«]vyн³Dp-Nè©*-yθ/®+ÐïÊyнÈ®_*y`‹«à~i0q]1

Inspired by @fireflame241's ungolfed Python answer, so make sure to upvote him!

Three loose inputs:

1. The window dimensions [w,h]
2. List of layers, where [[r,c]] is a convolutional layer and [[r,c],[r,c]] is a pooling layer.
3. List of kernel modes, where -1 is max; 0 is mid; 1 is min; and 2 is a pooling layer.

Try it online. (No test suite due to the q, but I've manually checked the four falsey examples.)

Explanation:

s                   # Swap to get the first two (implicit) inputs onto the stack,
                    # with the second input at the top
 ε                  # Map over each layer:
  Ð                 #  Triplicate the layer
   gi               #  If it's length is 1 (thus a convolutional layer):
     Ā              #   Truthify both integers, so we have a pair of 1s: [1,1]
      «             #   Merge it to the layer
 ]                  # Close the if-statement and map
  v                 # Loop over each layer `y`, consisting of two pairs [kernel,stride]:
   yн               #  Get the first pair (the kernel)
     ³              #  Push the third input-list of modes
      Dp-           #  Transform the 2s into 1s (by checking for prime, and subtracting)
         Nè         #  Get the mode at the current loop-index
           ©        #  Store it in variable `®` (without popping)
            *       #  Multiply this mode to the kernel-pair
             -      #  Subtract each from the dimensions-pair
              yθ    #  Get the last pair (the stride)
                /   #  Divide the dimension-pair by the stride-pair
                 ®+ #  And add the modified mode `®` to each
   Ð                #  Triplicate the modified dimensions-pair
    ï               #  Cast the values in the top copy to integers
     Ê              #  Check if the top two pairs are NOT equal
                    #  (1 if the dimension-pair contains decimal values; 0 if integers)
    yн              #  Push the kernel again
      È             #  Check for both values if they're even (1 if even; 0 if odd)
       ®_           #  Check if `®` is 0 (1 if 0; 0 if not)
         *          #  Multiply the checks
    y`              #  Push the kernel-pair and stride-pair separated to the stack
      ‹             #  Check if [kernel-row < stride-row, kernel-column < stride-column]
    «               #  Merge the pairs of checks together
     à              #  Check of any are truthy of this quartet by taking the maximum
    ~               #  Check if either is truthy by taking the bitwise-OR
     i              #  If this is truthy:
      0             #   Push a 0
       q            #   And stop the program
                    #   (after which this 0 is output implicitly as result)
 ]                  # Close the if-statement and loop
  1                 # And push a 1
                    # (which will be output implicitly if we didn't encountered the `q`)

Answer 3

J, 84 bytes

Takes in a list of layers; mode x y for convolution, with _1 0 1 for min mid max, and a 2x2 matrix wx wy ,: sx sy for pooling, and x y for the initial image. Returns 0 if it is a valid description, 1 otherwise.

_ e.&>(1(+_*[><.)@+(-{.)%(]*>:)/@])`((+_*1>])@+}.(]-~*+_*(2|[)+:|@]){.)@.(]3=#)~&.>/

Try it online!

How it works

(…)`(…)@.(]3=#)~&.>/

We fold the list from the right (where initially the 25 25 stands), and based on the left length (3 for convolution, 2 for pooling), we choose from two functions. Whenever we encounter an error, we set to row or column dimension to infinity. For convolution with example _1 3 3 (min 3x3):

((+_*1>])@+}.(]-~*+_*(2|[)+:|@]){.)
           }.(                 ){.  split into 3 3 and _1 as arguments
                            |@]     mode != 0?
                      2|[           3 3 even?
                          +:        not-or, so 1 iff mode = 0 and dimension even
                   _*               if this^ returns 1, convert it to infinity
                 *+                 add to this dim * mode (_3 _3)
              ]-~                   subtract the mode (_2 _2)
           +                        add to the image dimension (23 23)
  (+_*1>])                          if the dimensions are less than 1, add infinity

For pooling, with for example 3 3,:2 2 on the left side, 23 23 on the right side:

(1(+_*[><.)@+(-{.)%(]*>:)/@])
                   (]*>:)/@]  multiple stride with (window greater/equal stride?)
             (-{.)%           (image - window)% mstride, is infinity iff mstride is 0
 1          +                 add one
  (+_*[><.)                   add infinity if flooring a dimensions changes it

An the end, after applying each layer:

_ e.&>       unbox and check if at least one dimension is infinity