Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a new positional encoding method for Transformer-like architectures. Different from the previous methods that learn embeddings vectors for each position, the proposal instead learns an encoding function based on a set of Fourier features. The method by design learns an inductive bias and is parameter-efficient. While simple, the proposal outperforms the previous methods on a range of vision tasks.
main_review: [Originality]
- The idea of using the Fourier feature to approximate shift-invariant Gaussian kernel is not new [24,25]. However, the authors re-cast this basic idea to learn the position encoding, since the Gaussian kernel can encode euclidean distance between two points essentially. This is new in that previous position encoding methods learn positon-wise embedding vectors directly, which suffers from training and testing inconsistency due to the supervision sparsity.

[Quality]
- The proposal is well ablated and compared with various baselines in the experiments.
- Extensive experiments on various types of vision tasks and transformer models demonstrate the proposal's generality.

[Clarity]
- The motivation of the paper is well illustrated with several figures. 
- The description of the method is well written and its implementation details are well-summarized in the algorithm box.

[Significance]
- The positional encoding method in Transformer-architectures has rarely been thoroughly studied. The proposal shows the drawback of the previous methods and presents a new way of encoding positions in Transformer using Fourier features. While simple, it consistently outperforms the previous approaches on various vision tasks. The results should be shared with the community to rethink the current position encoding methods.

[Suggestion]
- Please compare the positional similarity visualization with the previous approaches. We can then see at what point the proposal performs better than the previous approaches. Also, please discuss what type of errors still exist in the current proposal.
- Please also show some qualitative results of the learned positional similarity along with the input image. This might be more intuitive for the reader. Moreover, if possible, please show how the well-learned positional similarity also positively affects the content-matching as well.
limitations_and_societal_impact: None
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Attention-based models are invariant to permutations, that is why for problems where positions matter (like speech and text data) positional embeddings are crucial for these models. There are a lot of different approaches how to encode positional information (sinusoidal positional embedding; absolute learnable positional embedding; relative positional embedding, both learnable and sinusoidal; etc.). In this paper authors propose a new way of encoding positions which is applicable for multi-dimensional case where position $x\in\mathbb{R}^n, n\geq 1$. Proposed encoding is a learnable Fourier feature mapping: first, authors define sinusoidal positional encoding for a multi-dimensional position vie a learnable linear projection of the position which defines both the orientation and wavelength of Fourier feature and then computing Fourier features themselves; second, obtained embedding is mapped into the final representation via multi-layer perceptron. All learnable parameters in the positional embedding are independent to the sequence length (which especially important in the context of the recent ViT models where upsampling/downsampling of the positional embeddings grid is done as positional embeddings  are sequence length dependent). The learnable matrix of Fourier features is initialized from the normal distribution which provides a useful inductive bias of $L_2$ distance between different positions in case of inner product of Fourier features. Authors state that with this inductive bias and multi-layer perceptron on top of Fourier features complex positional relationships could be captured (experimentally demonstrated for widget captioning task and 4D positions for which $L_2$ distance is not defined).

Improvements provided by the proposed positional embedding are demonstrated 
- for tasks with 2D positions in an image: 
  - Reformer model for image generation task on ImageNet 64x64 dataset 
  - DETR model for object detection task on COCO 2017 detection dataset (faster convergence also observed for DETR experiments)
- for widget captioning task in graphical user interfaces with 4D positions representing bounding box (also better generalization to unseen positions is observed)
main_review: **Originality**

Authors propose a novel positional embedding for multi-dimensional positions generalized from the sinusoidal positional embedding with a linear projection and MLP on top of the Fourier features. Techniques used for the approach, sinusoidal positional embedding, MLP, Fourier features, are well known, but proposed combination is novel and also introduces now inductive bias on distance between positions (encoding function is initialized in a way that inner product of Fourier features approximates Euclidean distance).
Original sinusoidal positional embedding was defined for 1D positions only (as proposed for machine translation and NLP tasks). In recent works, for 2D positions in images positional embedding is defined as a concatenation of representations for each of the position dimensions (or learnable embedding). With that respect authors propose natural (learnable transformation) generalization of 1D positions to MD positions with sinusoidal embedding (Fourier features). Overall, related works and comparison with them are very well covered.

**Quality** 

Proposed positional embedding is shown to be effective via experiments for three different tasks: it shows better performance and faster convergence. However, some additional clarification on implementation details and ablations (for example to show that improvement is coming not only because MLP but because learnable Fourier features) are needed.

- One of the key statements in the proposed method is providing $L_2$ distance or more complex relationships for positions (which is absent in all previous approaches for multi-dimensional cases). Some clarifications and additional ablations are needed here: 
  - (Fig. 3b) Transformer MD-Sine (line 231): could authors provide the exact formula of combining constant frequencies? If I understood correctly then this baseline is useless as by math definition embedding depends on $(x_1 + x_2)$ which is not suited for MD case embedding definition at all. Thus Transformer MD-Sine should have different frequencies for $x_1$ and $x_2$.
  - (Fig 3d) Another ablation is to initialize $W_r$ from another distribution (not normal) and use either in fixed or learnable regime to understand better how inductive bias of $L_2$ initialization is useful (both with MLP and without MLP on top of Fourier features).
  - (Fig 3d) One of the baselines should be defined by Eq. (2) and fixed (not learnable) random matrix $W_r\sim\mathcal{N}(0, \gamma^{-2})$. This embedding checks if $L_2$ inductive bias really matters (both with MLP and without MLP on top of Fourier features).
  - Thanks for additional analysis on the inner product of embeddings in Appendix.
- Generalization study.
  - Authors several time discuss in the paper potential improvements for other image resolutions different from the train one or on positions not seen during training. However, results only shown for widget captioning. What about DETR and image generation experiments? Why do authors think that proposed positional embedding could adequately learn relative positions and perform extrapolation well?
  - Could authors tell more about the unseen positions for experiment in Table 2. Are they out of convex hull of training positions or inside? I suppose generalization to unseen positions will have different behaviour for positions inside convex hull (interpolation can be solved even if we have sparse points) and outside (extrapolation will be very bad anyway; maybe our inductive bias and MLP solve a bit this problem though).
- Another helpful baseline is no positional embedding at all as for some tasks it was observed to be not so bad and far away from the standard positional embeddings. Good to have this baseline for comprehensive comparison.
- How was $gamma$ hyper-parameter chosen for different tasks (1 for image generation and 100 for widget captioning)?
- For DETR experiments in Fig. 4 why did authors stop at 100k updates? Seems models are not fully converged yet.
- Additional ablations are needed: apply MLP to the sine-2D and embed-2D, sine-4D and embed-4D to make sure that proposed way of Fourier features plays important role and indeed is needed in MD version (from fig. 3 seems that sin-2D and learnable-Fourier have similar results, so probably the main component is just MLP itself and we don't need $L_2$ inductive bias).
- Appendix, Eq. 3: is it used in every transformer block or only for the first one for all experiments in the paper? Do authors do any scaling of positional embedding before adding it to the content one? Could it be that there is a need of proper scaling in case of no MLP modulator?
- Appendix line 91: what exactly improvement do authors observe with KL loss usage? Can it be reached via proper setting $\gamma$ for initialization (why not setting it 1 as for DETR and image generation)? Can this skewed behaviour be connected to unbalanced dataset with respect to positions? Why should this skewed behaviour be fixed to be symmetrical if we wanted to have more complicated mapping? Do authors observe the same trend in case of no MLP modulator? 

**Clarity**

The paper is very well written (clear and well organized), there are only minor typos which are listed below. Thanks authors for very nice visualizations in Background Section (Section 2). For experiments authors uses default architectures and parameters from previous works and vary positional embedding (additional changes in the training hyper-parameters are provided to reproduce experiments). There are all code references to the original models and information about resources configuration.

- line 28 "which a position" -> "where a position"
- line 163 "are initialized" -> "is initialized"
- Sentence at lines 46-48: this overhead is valuable only for embedding approach (where learnable embedding is used) not for the fixed sinusoidal positional embedding (for any position we can simply compute sinusoidal positional embedding and do necessary concatenations)
- In introduction (lines 48-50) the problem of the different sizes between train and test images is mentioned as a drawback for current approaches in case of ViT and DeiT models. Probably, this sentence should be reformulated a bit as during reading I was expecting that authors will solve this issue too with proposed approach (proposed approach still does not solve the problem).
- Sentence at lines 57-58: agree, that now embedding can handle samples with arbitrary length but main question is how it generalizes to unseen image sizes for example (generalization can be poor as we saw for NLP for long sequences which led to relative positional embedding works). For example, it is not clear why proposed embedding is doing better job than special treatments in ViT and DeiT.
- Fig. 1 refers to positional embedding from the "Attention is all you need paper" where sinusoidal fixed positional embedding is used. Why then it is learned? 
- Fig. 2b - what is the matrix $W_r$ used here? Some random matrix from normal distribution?
- Could authors add example how 2D positions are defined for pixels on images (from left upper corner as (0, 0) and right bottom (resolution, resolution); or something else)?
- Appendix line 67 "(Figure 2" -> "Figure 2" - remove bracket, line 91 "forLearned" -> "for Learned"
- Appendix Fig 3, 4 recheck $\gamma$ in captions
- line 275 "We" -> "we"
- Table 1 last column the bold value is wrong, another row should be bold.

**Significance**

Positional embedding problem is still actual and should be revisited in the light of new recent applications of transformers to vision tasks, like classification, detection and video processing. As soon as images are 2D we need to have positional embedding which uses the entire 2D structure and has necessary inductive biases from the problem formulation. There are potentially other tasks with more complex structure for multi-dimensional positions and current work provides a general way to encode  these multi-dimensional positions. The paper demonstrates that knowing multi-dimensional structure is beneficial for the tasks.
limitations_and_societal_impact: The paper is about general technique for positions encoding for attention-based models that is why the paper results itself have no societal impact. Results are limited to attention-based models or other (potential) models which are permutation invariant.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a new position encoding method to for the attention mechanism. The proposed method is similar to the Sinusoidal PE that both use a continuous function, [sin, cos], instead of discrete embedding. However, the proposed method does not depend on a fixed frequency for each dimension, a weight Wr is used to map input position x into a random(but learnable) low-dimensional space. The projected feature is then passed to a Sinusoidal function, fourier features. A MLP layer is applied on the resulting fourier feature to build the final position vector for down-stream tasks.


main_review: To my knowledge, this fourier feature based position encoding is original. The similarity of the traditional PE[32] suffers from decaying faster in some directions due to the orthogonality, thus it fails modelling L2 distance, (Based on Fig 2(a), I can imagine L1 or other distances also do not work, please correct me if I am wrong.) The proposed method solves this problem by approximating a gaussian kernel based on fourier features due to its efficiency[24]. The learned weight Wr is claimed to be a multi-dimension generalization of [24] and each dimension is not considered separately. The method is validated on various tasks, image generation, object detection and captioning.
limitations_and_societal_impact: From the ablation study for image generation, Fig. 3, the (most) gain seems due to the use of fourier feature, MLP slightly improves the performance, and the learnable weight looks like cannot deliver constant and solid improvement. The improvement for object detection is not that obvious compared to MLP, only AP and AP75 are shown. I wonder if the method can also deliver improvement on AP50, AP{S,M,L}. A table may better show the difference. The general idea of this study is interesting, but its efficacy can be further validated or discussed, current results cannot obviously show the advantage.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a learnable positional encoding function based on Fourier features, where Fourier positional encodings (which favours L2-distance similarity) are passed to an MLP with learnable parameters to learn the final positional encoding. 
main_review: **Strengths**:

The proposed approach seems novel and has several advantages; it can represent a multi-dimensional input space, has a fixed representation size for any input positional length, can learn the final similarity distance rather than being fixed, and shows relative improvement on unseen test-set positional cases. The authors show improved performance on multiple tasks, including image generation, object detection, and captioning. 

**Weaknesses:** 

While the proposed approach seems promising, the following points either need further justification or clarification:

**1- Distance function:**
- It is not clear why L2 distance, which is motivated in Introduction and later sections (such as Figure 2(b)) is the desired similarity function.

- Figure 1 shows how a transformer gets diffused positional similarity for distances not seen during training. No such figure is shown for the proposed model (such as the model of Section 4.3) for unseen cases, to visualise how the model handles unseen positions/distances.

- Even if we consider the L2 distance shown in Eq (4) is the desired function, the final similarity is obtained by Eq(5), which applies an MLP and W_p on top of Fourier features. Image 1 to 4 shown in appendix visualise r_x.r_y, while the final learned distance similarity is learned by Eq(5). The output of Eq(5) can better indicate what type of function the model is finally learning. Why authors have not visualised the output of this function?


**2- Capacity of embedding function:**

- How much the capacity of the embedding function has an impact on the results. In Figure 3(c), an MLP with a higher capacity gets closer to Fourier+MLP. If one increases the capacity of both models (MLP and Fourier+MLP), such as adding one to multiple layers, how much do the results change? The question is to what extent the capacity of MLP plays a role in the results, regardless of whether the passed data is in non-Fourier or Fourier embedding?

**3- clarity:**

In some sections it is not easy to follow the paper, sometimes descriptions are provided without first clarifying what they mean. For example, in Algorithm 1 and the paragraph above it, it is not clear what N (number of positions) and G (positional groups) mean. Authors could clarify it in the example of the bounding box they mentioned before it, but no connection is made.

- In Algorithm 1, the variables F and H are not defined, neither in the text. Previously W_r and W_p were used to talk about learning variables of Fourier and MLP. It is only in the line of initialization (which is after) that F and H are first mentioned, where it becomes clear that F indicates the dimensionality of W_r. 

- Are W1, B1, W2, B2 mentioned in Algorithm 1 part of W_p? If so, it should be clarified.

- In Section 4.3, it is not clear how different grouping (1/4 vs 2/2 vs 4/1) changes the algorithm and hence the results. So, how this grouping impact the result?

**4- correctness:**

- In the equation written between equations 2 and 3 (let's call it equation 2.5), the dot product of r_x and r_y does not match with the second term.  Particularly, when one applies r_x.r_y, there is concatenation of cosine and sine 
components (yielding cos(a)cos(b)||sin(a)sin(b), with || being concatenation of two terms), which is not equivalent to the second term that yields cos(a)cos(b)+sin(a)sin(b). Am I missing something?

- In line 187, the L2 distance between two positions should be between a pair of (x1,y1) and another pair (x2,y2) and not between the same x and y, since x-y of the same pair does not capture any meaningful information. Can authors clarify?
limitations_and_societal_impact: **Regarding checklist:**

- The code is not provided, while authors have answered Yes.

- I did not see any section on the limitation of the proposed approach, while authors have answered Yes.
review_title: null

Meta-review: The paper presents a positional encoding method for Transformer-like embedding which outperforms the previous methods on various vision tasks.

Reviewers noticed that the improvement of the method was somewhat marginal, however they still found that the results and presented approach could be useful to the community as positional encoding has rarely been thoroughly studied.

Decision: Accept (Poster)