How is the extrapolation variant of the parity problem defined?

Question

In the paper PonderNet: Learning to Ponder (Banino et al. 2021), the authors define the following "Parity" task:

input vectors had 64 elements, of which a random number from 1 to 64 were randomly set to 1 or −1 and the rest were set to 0. The corresponding target was 1 if there was an odd number of ones and 0 if there was an even number of ones.

The authors refer to this variant of the problem as "interpolation". They then go on to define an "extrapolation" variant:

Next we moved to test the ability of PonderNet to allow extrapolation. To do this we consider input vectors of 96 elements instead. We train the network on input vectors up from integers ranging from 1 to 48 elements and we then evaluate on integers between 49 and 96.

Initially, I interpreted this such that given an input vector of 96 elements, we can generate a training sample by sampling a subvector from a random range in the first 48 elements, and a testing sample by sampling a subvector from a random range in the second 48 elements.

For example, changing 96 to 16 for simplicity:

• given vector: 0000 0100 1001 0001
• random train range (can only select between 0 and 8): [0, 4]
  • resulting train sample: 0000, label 0
• random test range (can only select between 8 and 16): [8, 15]
  • resulting test sample: 1001 000, label 0

In a sense this is "extrapolation", because the test sample is of greater length than the train sample.

However it could very well happen that a test sample is shorter than than a train sample, or that they are the same length, etc., and with that I'm not sure if that still constitutes "extrapolation".

Another interpretation that I've seen (e.g. in this video at ~31:00) is that the training samples can be of any length between 1 and 48, while the testing samples can be of any length between 49 and 96. This would ensure that the testing samples are always longer than the training samples. I think this better aligns with the authors goal of designing a harder task, but I am not sure if this is indeed what they did or not, especially since this would make the "we consider input vectors of 96 elements instead" phrase a bit out of place.

I've tried looking at Adaptive Computation Time for Recurrent Neural Networks (Graves, 2016), where the parity problem was seemingly originally defined, but no mention of extrapolation is made.

Any thoughts?

Answer 1

I emailed the authors and got the following answer, which clarified it for me:

Sorry if this was not clear enough in the paper. If I recall correctly, the vector length is always fixed (96 in this case). What changes is the difficulty (number of ±1s, which is the number over which the parity operation is applied). In the extrapolation task, the difficulty of the examples was different between training and test: it was always somewhere between 1-48 ones in the training, and 49-96 in the evaluation/test.