Learnable Fourier Features for Multi-dimensional Spatial Positional Encoding
Authors: Yang Li
Si Si
Gang Li
Cho-Jui Hsieh
Samy Bengio
Venue: NeurIPS 2021 Poster (2021)
Keywords: Positional encoding
Transformer
Fourier features
multi-dimensional spatial tasks
image classification
image generation
object detection
widget captioning
UI modeling

Abstract: Attentional mechanisms are order-invariant. Positional encoding is a crucial component to allow attention-based deep model architectures such as Transformer to address sequences or images where the position of information matters. In this paper, we propose a novel positional encoding method based on learnable Fourier features. Instead of hard-coding each position as a token or a vector, we represent each position, which can be multi-dimensional, as a trainable encoding based on learnable Fourier feature mapping, modulated  with  a  multi-layer perceptron. The representation is particularly advantageous for a spatial multi-dimensional position, e.g., pixel positions on an image, where $L_2$ distances or more complex positional relationships need to be captured. Our experiments based on several public benchmark tasks show that our learnable Fourier feature representation for multi-dimensional positional encoding outperforms existing methods by both improving the accuracy and allowing faster convergence.

Learnable Fourier Features for Multi-Dimensionall Spatial Positional Encoding
Yang Li
Si Google Research Mountain View, CA
Gang Li Google Research Mountain View, CA leebird@google.co com
Google Research Mountain View, CA
1 Liyangggoogle.cmm com
sisidaisy@google.cm
Cho-Jui Hsieh UCLA Los Angeles, CA chohsiehêcs ucla.
Samy Bengio
Google Research Mountain View, CA bengio@gmail.com
Abstract
Attentional mechanisms are order-invariant. Positional encoding is crucial com- ponent to allow attention-based deep model architectures such as Transformer address sequences or images where the position of information matters. In this paper, we propose a novel positional encoding method based on learnable Fourier features. Instead of hard-coding each position as a token or vector, we represent each position, which can be nulti-dimensional, as trainable encoding based on learnable Fourier feature mapping, modulated with multi-layer perceptron. The representation is particularly advantageous for spatial multi-dimennional position, e.g., pixel positions on an image, where L.2 distances or more complex positional relationships need to be captured. Our experiments based on several public benchmark tasks show that our learnable Fourier feature representation for multi-dimensional positional encoding outperforms existing methods by both improving the accuracy and allowing faster convergence.
Introduction
Attentional mechanisms central component in many deep architectures [] 25 which allow a model to selectively focus on specific information in the context. Transformer 38 and its many 3 which solely based attentional mechanisms, have advanced the state of the art on many tasks that involve data with inherent temporal and spatial orders, e.g..
variants, such 29
38
16
machine translation 38 image generation [16]. and object detection 3
contrast to recurrent the ordinal information as computation progresses based sequential or spatial dependencies, attentional mechanisms are order invariant. allows model to directly access information at an arbitrary position in a sequence space. The lack of ordinal information in the model is not an issue when attentional mechanisms are combined with a recurrent or convolutional architecture [ 25). However, it is crucial for Transformer-aiie models where the entire model is built based on attentional mechanisms.
27 or convolutional architectures [88] which automatically capture
To capture positional information in the data, e.g., the token position in sentence or the pixel coordinates in an image, positional encoding has been introduced 10 38
where position in
CCurrently at Apple.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

one or wwo-dimensional space is mapped to a vector space by either learning or heuristics- based approaches. The representation of an imput, by combining both its positional encoding and content representation, e.g., word embeddings, then participates in downstream computation for attentional mechanisms. The original Transformer model uses a fixed sinusoidal encoding with predefined wavelengths [38]. However, the predefined features lack flexibility and may not capture important position information in a task-dependent manner. To encode positions in a more flexible and data-driven way, position embedding approaches (e.g., one used in BERT [8] introduce trainable embedding vectors for each (absolute or relative) position. Unfortunately, this data-driven approach comes at the cost of introducing a large amount of extra learnable parameters proportional to sequence lengths times the hidden dimension size. Moreover, it is non- trivial to apply position embedding to problems with variable sequence lengths.
In this paper, we consider the problem of designing a position encoding for multi mitiiiiiienional spatial positions, such as pixel positions in an image or object hounding boxes in spatial structure such as Uls. Existing methods typically use sinusoidal position encoding with hand-crafted frequencies or learned embedding to encode each dimension independently and then combine the resulting vector representations via concatenation, e.g., 129 3 g
Unfortunately, these approaches, by concatenating the representation of each dimension, are not effective to capture desired positional similarity on an image, such as L2 distance or more complex positional relationships. While embedding based approaches have the potential to learn complex positional relationships, since the number of unique positions grows exponentially to the input dimension, the approach incurs large overhead in 2D and could be infeasible scaling higher dimensional space. In addition, special treatments to adjust the learned position embedding when the test image sizes differ from training, such as bicubic interpolation used in DeiT' (37 Vision Transformer (9]. To avoid these special adjustments, it is an important for positional encoding to handle unseen positions.
needed
The main contributions of our work are as follows. We design novel positional encoding method that learns a function to map multi-dimensional positions into a vector space. The function extracts position information based on a set of Fourier features and passing them to an MLP. The encoding function is learnable and is initialized in such a way that the inner products of our positional encodings dimens-dime
approximate Euclidean distances. The inductive bias can be desirable in a 2D space and by learning from the data, the representation can be adapted to a specific problem. Since method learns encoding function instead of embedding vectors for each position, it is naturally inductive and can handle test samples with arbitrary length. Our method is parameter-efficien in the sense that the number of parameters do not grow with sequence length. To allow complex positional relationships, our representation is also composable by encoding each subset of dimensions, in a multi- dimensional space, using shared learnable Fourier features. We evaluate our method on a number of tasks where Transformer-basee models have been used for problems with multi-dimennional positions, including image generation [16). object detection [3] and image classification (,, which all involve 2D positions (vertical and horizontal) in images. We also evaluate our method on natural language generation in graphical user interfaces, which involve modeling a sparse spatial structure of UI objects on the screen, where each object is characterized by 4-coordinate values (top, left, bottom, and right) 20) These experiments show that our positional encoding method consistently outperforms existing methods by both improving accuracy and accelerating learning.
2 Background
2.1 Positional Encoding
In Transformer models, the self-attentional mechanism determines the strength between each pair of items based on the dot product similarity of their vector representations, which are derived from an item's 's content embedding and positional encoding (38] (Appendix/A) A Although positional encoding (PE) does not function alone in determining the attention strength, the benefit of having the inductive bias of positional relevance in the PE is evidenced by the success of the sinusoidal positional encoding originally proposed in Transformer (88 (Equation)
P 10000 D PE(p, 2d + 1) = cos
P
PE(p, 2d) = sin
2d
(1)
1000024/D
D
2

---

The other category of approaches for PE is to treat each position then be uniquely represented as learnable embedding vector [9 10 16 8]. The approach which encodes scalar position, p, using sinusoidal functions with different constant frequencies for each dimension, of a D-dimensional encoding vector. The dot product of this encoding representation naturally captures positional similarity in a 1D sequence in parameter-free fashion.
discrete token that can
can capture arbitrarily complex relationships between positions by learning from data, but can be difficult to generalize for positions that are rarely encountered during training. For ex- ample, the heatmap map in Figure shows the positional similarity learned by a Transformer model for machine translation task on En-De WMT32k [38]. Towards the diagonal, i.e., po- sitions that are closer, there tends to be higher similarity because each token attends to itself the most. However, the trend is diffused for large positions, i.c., when a sequence is long, because fewer training examples have long sequences. For what is followed, model will not be able to correctly represent large positions in long sequence at training and test time.
There has been extensive work in extending posi- tional encoding for different modeling tasks, e.g.. handling long-range sequences 7 43 or tree struc-
60
tures 33 or enhancing vision tasks using input- dependent positional encoding [6]. Our work is re-
200
lated to the effort of using a continuous function in-
stead of embedding retrieval for modeling positions.
180
0
Previous work [40] uses complex embedding func-
278
tions to model 1D positions. It has been shown that
position encoding in ID space can be learned as a Neural ODE system (23). However, their approach cannot be extended to 2D or higher-dimensional problems. More recently, previous work has pro- posed learnable sinusoidal representations for ID positions [39] in language tasks. In contrast, fo- cus on representing 2D or even higher dimensional positions in spatial tasks.
Figure 1: The heatmap shows the dot product similarity of positional embeddings learned by Transformer model for the En-De WMT32k machine translation task.
Our work different from the body of work on relative positional encoding, which directly represents pairwise positional relation between query and key [5] | 2 32 [1] Because there are O(N2) of pairwise relations for N positions, relative positional attention only feasible for a small range, e.g.. within clip distance or local range, although recent work (4 has achieved linear complexity by approximating relative positional encoding. Because relative positional encoding directly participates in the computation of the attention matrix, instead of addressing the representation of individual input items, it cannot be casily plugged into many existing Transformer architectures. In contrast, our method is fully compatible with many Transformer benchmarks models. In work, focus representing individual multi-diimesional spatial positions such that these representations achieve desirable pairwise relation later during attention computation.
2.2 Encoding Multi- Silti--Dmeenional Spatial Positions
A common approach for positional encoding for 2D problem is to encode each positional dimension (vertical and horizontal) independently using either sinusoidal (Equation or direct embedding- based methods, and then concatenate these representations to form the final positional encoding 22) 3 16 J. Although the approach of sinusoidal concatenation allows the model to capture the positional (spatial) relationships orthogonally along each axis, the similarity decays much faster along other directions, as shown in Figure 2(a] which ideally should decay at the same rate along all the directions for modeling L2 distances as shown in Figure 2(b)
While concatenating learned embedding has the capacity to model complex spatial relations between positions, they can be difficult to generalize. It is even brittle for addressing problems involving higher-dimensional positions. For example, for modeling spatial structures in UIs [9 20 recent work takes a collection of UI objects as input and the positional attribute of each object is its spatial configuration on the screen, which involves 4 coordinate values: [top, left, bottom, right]. The occurrence of unique object positions can be sparse, which makes it difficult for model to
3

---

110
100
R
(a) nmusoidal-concatenatio encoding.
(b) 2D Fourier feature PE.
Figure 2: The similarities of the center position to the rest positions on the 2D space, based on the dot product between their positional encoding of each approach.
generalize. There are positions that rarely seen during training might occur at test time. Motivated by these analyses, we intend develop a positional encoding method for representing a multi- dimensional position by taking into account all the dimensions holistically, and meanwhile enabling effective inductive bias and learnability in the representation.
2.3 Fourier Features
The task of mapping data points to a vector space such as their dot product achieves certain distance
metric has been extensively investigated in the literature of kernel functions (30 31 17 42 12 36)
k(x,,) v) =())2<())
where x, E Rd and k(z, y) is a shift-invariant kernel function; and =xx) and 2(y) are feature mapping respectively.
Fourier features kernel, with k(r, exp( | |--yl where || - y/I is the Fuclidean distance between two points, and which each point is multi-dimensionn position in our context. This unique attribute inspired us to represent multi-dimennional position via Fourier features, which basis for our approach for positional encoding.
30 are a common technique approximate a Gaussian kernel, a
Random Fourier features have also been applied in deep learning models, e.g., approximating the attention matrix in Transformer [5]. Recently, adaptive random Fourier features (21] have been proposed for better kernel approximation that show improvement on classification tasks. In contrast, we propose learnable Fourier features for spatial positional encoding and integrate the method in various Transformer- based deep architectures that show improvements on multi-dimensional spatial tasks.
3 Learnable Fourier Features Positional Encoding
We propose to learn position encoding function that maps an A M-dimensional position RM into a K-ddimensional feature vector. This K K-dimensional vector will then be used in downstream computation for attention mechanisms. The proposed encoding function composed with the following two components:
Learnable Fourier Features
To extract useful features from the input position x, consider the following feature extraction layer motivated by the idea Fourier features (30 31]. Given an
M -idimensional position, x RM we acquire a D-dimensional Fourier feature vector representation for the position, Ta E RD as follows:
Ts cos xW,
sin xW7]
(2)
where is the concatenation of two vectors. This can also be viewed as the generalization of sinusoidal position encoding to the multi-dimennsonall case, while we set W, R xM which

---

defines both the orientation and wavelength of Fourier features, as trainable parameters. Since cos(a a b) cos a cos b + sin a sin b, we have the following:
1 sum (cs ()) = hww Tx Ty = D
yy
(3)
where is the dot product. Therefore, vectors in the form of (2 enjoys the shift-invariance property- the dot product of r, and ry function of x-=-- y and the function parameterized by W,. Learning Wr is equivalent to obtaining the most informative function on x that can be useful for the downstream task.
In our algorithm, the linear projection W, is initialized by drawing from a normal distribution
W, N( 3)
When the linear projection weights are drawn in such way, according to random Fourier features [30 BT the dot product between two feature vectors, Tn and Tg. approximates the Gaussian kernel over the original positions.
| y 12
Tyy = exp
(5)
Figure 2(b) visualizes this representation, which introduces useful inductive bias of L2 distances into the model.
MLP layer To feed the representation to the downstream computation, we give the representation additional capacity by modulating the features with a multi Multi-layyerre perceptron:
PE = @(Ta, 0)W,, p.
(6)
where o(-) is the perceptron parameterized by 0. W are trainable parameters for projecting the representation onto target dimension of positional encoding for combining with content embedding. Our purpose with MLP here is very different from previous work that uses non-linear transformation such as an RNN to capture positional dynamics 226 23 These previous works do not handle non-sequential multi-dimensional positions.
The learnable parameters in our position encoding function are W, for Fourier features and 0, Wp for the MLP layer. The size of these matrices are independent of the sequence length. Furthermore, the position encoding function can be applied to any input position 2, our method can be easily applicd when training and testing involve different positions, e.g., images with different resolutions. Compared to the previous sinusoidal representation (Equation TT representation is learnable and multi-dimensional. Compared to the discrete embedding- based approach, our representation treats each dimension of position continuous-valued vector, which alleviates the sparsity issue with discrete positions. Previous work has revealed that using sinusoidal activation functions might suffer optimization problems due vanishing gradients in extreme cases (28) although we do not observe much difficulty in training our positional encodings.
Our representation is applicable for many 2D spatial tasks, e.g., image-related tasks. For tasks involving higher-dinng ligher-dimmnsional positions, the positional similarity between positions might be more complicated than L2 distances. For example, to model the spatial structure of natural scene graphical user interface, given two objects in the structure, x and y. coordinate values, [ T2, T3y Ta] and [31, y2 Vs. val, represent the object's 's top, left, bottom, and right position. The L2 distance between the two positions Ei= (I: )² will capture neither the minimum nor the maximum distance between the two objects, or any vertical or horizontal alignments of them. To address this issue, we hypothesize that complex spatial relationships can be built on top of shift-invariant relations enabled by our positional encoding. Specifically, we can partition groups, and apply the same encoding pipeline to each group of coordinate values. The process is similar to applying convolution over partitions with the kernel and stride sizes to be the group size. We can then concatenate the output all the groups to form the final positional encoding. We will elaborate on this use case in the UI modeling experiment (Section 4.4) An implementation of our positional encoder based on tensor operation detailed Algorithm in which Equation 2 and 6 are realized in Line and 2.
mineti-dimensional position into
5

---

Algorithm 1:
Compute the Fourier feature positional encoding of multi-dimensional position.
Input: tensor in the shape of [N, G, MJ that represents positions where each position
in the shape of [G, M] that represents G positional groups and each group has M-dimensional positional values.
Output:
PEx in the shape of [N, D] where D is the depth of the positional encoding. Hyperparameter: The depth of the Fourier feature dimension |L], the hidden layer dimension |H] and the positional encoding dimension D, and
Initialization: Initialize learnable weights W, E R 1ET xM by sampling from (0, ? ?=?);
Initialize learnable weights W1 E RIFIXIMI B1 E R H1, W2 E R. H|x & and Bg E R.B
F VIFI cos XW sin XW?) (Eq.))
2 Y + GeLU + W2 + B3 (Eq. 6
PEx +- Reshape Y into the shape of [N, D]:
return PEx.
4 Experiments
We evaluate our approach on a range of benchmark tasks using Transformer-based models in comparison with several existing positional encoding methods.
4.1 Image Generation
We compare our method with existing positional encoding approaches based on Reformer [66 for the image generation task the ImageNet 64x64 dataset [4]. Reformer is Transformer-baser model that uses locality-sensitive hashing and reversible residual layers to efficiently handle long sequences. Reformer flattens 64x64 image into sequence (Lenggth=64xx44331222285
in raster scan red-green-blue order. Reformer as an auto-regressive model predicts the pixel value at each position by attending to previous positions. We equip Reformer with different positional encoding methods.
Embed-2D: Reformer's 's default positional encoding concatenates the embedding of each dimension from two embedding matrices: vertical [64, 384] and horizontal [64, 384].
Embed-/ ID: The baseline method assigns learnable embedding to each position in the flattened sequence, from an embedding matrix of [64 x 64, 768), which ignores the 2D structure an image and lets the model learn positional relations all by itself.
Sine-2D) and Sine- Similar to Embed-21) and Embed- but they instead encode position using Transformer's constant sinusoidal formulation (Equation
Learnable-Fourier MLP: Our method that implements Algorithm [ using the hyperparam- eter F = 384, H = 32, D = 768. We picked these dimensions for our method to have roughly the same number of parameters Embed-2D, the benchmark of Reformer.
We leave the RGB axis to use the direct embedding as the original Reformer: [3, 256). The concate- nation of the pixel position encoding and the RGB index embedding results in an representation that has the same depth (1024) as the one in the original paper, which allows the rest of the model intact.
We follow the experimental procedure as detailed in the Reformer paper. All our experiments used 6-layer, 8-head-attention Reformer, with dmmode 1024, d,f 4096, and 7heaad 8. These models implemented based the Reformer codebase in Trax The training for each Reformer model is parallelized across 32 TPU v2 cores, and each batch contains 8 sequences (images) on each core. We trained each model variant for 100k steps, which took about 24 hours to complete.
As shown in Figure 33, our method, Learnable- + MLP, outperforms all the baselines in terms of convergence speed and achieves better accuracy, i.e., lower bits per dim at the end. The Reformer's original positional encoder, Embed-2D, is the second best. Sine-2D clearly outperforms Sine-1D, and Embed- ID achieves similar performance as Sin
hhttps://gitee /ttp:///a//////aaaooooo///////// httpsh/www.......accceeeeeeeeeta

---

Sinc-10
Embed-111 1D
135
mablle
Sine-997
22-
Embedd 20
244
Maarrabll-FF Fouriar MLP
2.5-
10-
20-
348
(a) Comparison w/ baselines.
(b) Comparison w/ individual components.
Figure 3: Bits per dim (bpd) w.r.t. training steps on evaluating Reformer on the held-out data of the ImageNet 64x64 dataset for image generation, using different positional encoding methods. The plot shows the mean and 95% confidence interval based on 3 repeats of experiments for each method.
To understand how each component in our method contributes to the overall performance, we com- pare Boemable-Fourrer-MLL with its components Learnable-Fourier and MLP alone. MLP takes a 2D position as input and outputs a 768-dimensional positional encoding. Our experiment shows that Learnable-Forrier Fourier+MLP (see Figure It is worth noting that Carmable-Fourice shows competitive perfor- mance for the first 30k steps, which indicates that benefits from an effective bias for capturing meaningful positional relationships.
MLP alone does not perform as good as their combination, Learnable-
4.2 Object Detection
We evaluate the proposed positional encoding in DETR (3, recent model that uses a Transformer for end-to-end object detection. It uses a Transformer to take the output from a ResNet, i.e., a feature map with the spatial dimensions of 42 x 42. Similar to Reformer, positional encoding represents each position in the grid as part of the input to the Transformer encoder in DETR. We experiment with the default 6-layer Encoder-Decode the COCO 2017 object detection dataset (22 that has 18k images for training and 5k for validation. We equip the DETR model with different positional encoding methods, including Sine-2D that is DETR's 's default method,
setup in DETR, with the same set of hyperparameters, on
Embed-21 2D and MLP. The model implementations are based on the DETR codebase which are ported into JAX The training for each DETR model is parallelized across 64 TPU v3 cores with a batch size of 64 images. We let each model train for 300 epochs converge, which took about 3 days. We follow the experimental procedure of the DETR paper, and report accuracy on the validation set.
DETR uses image augmentation in both training and validation. Each image is randomly resized to several specific dimensions with the smaller side of the image at one of the following sizes: 480, 512, 544, 576, 608, 640, 672, 704, 736, 768, and 800. For positional encoding, all image positions normalized to a range of (0, 1). Normalization is valuable because of random resizing and cropping during image augmentation results in images with different sizes. Embed-2D treats each position as discrete value, and all the methods except Embed-2D leverages position normalization. As shown in Table Baarnable-Fourie--MM
offers the best performance across all the metrics. Sine-2D and MLP perform competitively while Embed-2D has the worst performance.
To investigate how each encoding generalizes to unseen image sizes, modify the benchmark by reserving the three largest sizes: 736, 768, and 800 for validation only. We also disable position normalization. As result, there are large positions that are never seen during training, which requires each method to generalize (or extrapolate) to these positions. As shown in Table [ the benefit of Fearnable-Fourier-MML.. is more pronounced, and the performance gap between Embed-2D and the other methods is further increased.
httpp:://github..co//oooo/t
7

---

Table 1: The impact of different positional encodings on DETR for object detection.
Method
AP
AP
AP
smail
Almedium
A.large
Sine-2D
40.1
60.4
42.6
18.5
43.6
58.8
Embed-2D
39.3
59.8
41.4
18.7
42.5
57.5
MLP
40.0
60.3
42.2
18.6
43.7
58.1
Learnable-Fourier<MLL.P
40.2
60.7
42.7
18.8
43.8
59.1
Table 2: Performance of each method for object detection involving unseen image dimensions.
Method
AP
A AP30
AP75
AP APsmail
A Ameedium
A APtarge
Sine-2D
38.9
59,6
40.9
17.5
42.5
57.5
Embed-2D
36.6
58.2
37.7
15.9
40.0
55.3
MLP
38.6
59.5
40.3
17.1
42.1
57.1
39.5
60.0
41.6
18.9
43.0
58.0
4.3 Image Classification
We evaluate the proposed positional encoding on image classification, another popular task images, based on Vision Transformer (VIT) 191. a Transformer-only architecture that does not use CNN for image embedding. The default positional encoding in VIT is Embed-1D ID.. In this experiment, we focus on the ViT-B/16 model that a 12-layer Transformer encoder with Hidden size=768, MLP_size==300 and 12 attention heads. The input VIT-B/16
14 14 image grid where each cell corresponds to 16 16 image patch. We train each model on the ImageNet dataset for 90 epochs, and report its accuracy the ImageNet validation dataset. Learnable Fourier+MI.P achieved better performance (Precision @ 1=74.5%) on the validation dataset than ED (Precision @ 1=73.6%)
Dosovitskiy et.al. investigated several positional encoding methods in their work (sce Table in (9], including Embed-1D, Embed-2D and relative positional encoding. They pre-trained these models on the large JFT dataset (300 million examples) and then report their performance linear tasks. They found the model suffers when no positional encoding is used but there are no significant impacts for using each of these positional encoding methods. We suspect that given such large model (86M Params), it is not difficult for any of these positional encoding methods to learn the small number of unique positions (14 14 196) the image. In their experiment, Embed-1ID achieves 64.206% accuracy, Embed-2ID 64.001 % and Relative Positional Encoding 64.032%. We experimented Sarrabll--ourrrrMMMMM in this experiment, which achieved 64. 64.732% accuracy.
ImageNet 5-shot
4.4 Widget Captioning
So far, we have investigated tasks that handle 2D positions in an image. In this experiment, we investigate even higher-dimene -iehe--dimennional positions. In a widget captioning task (20), the model is trained generate natural language description of widgets in graphical user interfaces, e-g., buttons and icons. A significant part of the model is to encode a UI screen structure, which consists of collection of 2D objects of different sizes, using Transformer encoder. To represent the spatial configuration each object, the original model assigns learnable embedding vector to every discrete coordinate value of each dimension of the object bounding box, including the left, top, right, and bottom dimensions. The four embedding vectors then jointly represent bounding box on the screen. We refer this baseline as Embed-4D. Li et al. found that position encoding has a significant impact on the performance of widget captioning models (see Table 6 in Appendix F of the paper (20)..
Because there is no obvious distance metrics between bounding boxes, hypothesize that an appropriate metric can be learned on top of L2 distances of specific dimensions. To do so, We evaluate three different partitions of bounding box dimensions, and use our method encode each group in parallel as detailed in Algorithm[] Learnable-Fouier-MLL.. --1MMMPP-//1 1/4 treats all the 4 coordinate dimensions [(top, left, bottom, right)] as one group, i.e., G 1; Learnable-Fouriers 2/2 splits the 4 dimensions into 2 groups [(top, left), (bottom, right)]. i.e., G = 2; and finally Fourier--/ encodes groups of 1-dimensional value [(top), (left), (bottom), (right)], i.c., G 4. We also add the sinusoidal approach to the comparison, which

---

represents each positional dimension separately and then uses their concatenation to as the positional encoding a bounding box (referred as Sine-4D..
Table 3: The performance of different positional encoding methods on the widget captioning test set. SOTA shows the results from the original paper, which is reproduced by Embed-4D in our experiment.
Method
BLEU-1
BLEU-2
ROUGE
CIDEr
METOER
SPICE
SOTA (20
44.9
32.2
44.7
97.0
31.7
17.6
Embed-4D
45.2
31.9
45.0
97.0
31.7
17.3
MLP
34.0
23.5
33.7
70.3
23.7
10.2
Sine-4D
44.9
31.9
43.9
94.9
31.0
16.7
Learnable-Fourrer-2222
44.9
31.6
44.3
95.3
31.6
17.7
Fixed-Fourier-MMIPP11/
45.0
32.1
44.2
95.4
31.2
17.1
Excdd-Fourirr+MMLP22222
46.1
32.5
45.8
100.2
32.5
18.4
Axced-Fouriert+MLLP44//
45.5
32.1
45.1
97.2
31.7
17.6
Leamable-Fourier-LLLPP
45.6
32.7
45.2
99.1
32.2
17.1
Faamable-Fourier-MLLL.
46.1
32.7
45.9
98.0
32.6
17.9
46.8
33.4
46.1
100.7
32.4
17.8
We use the same model architecture and hyperparameters of the strongest model, Pixel+Local+ Context, the original paper [20]. and built our experiment based on the public codebase widget captioning Specifically, the screen encoder uses a 6-layer, 8-head Transformer with hidden size of I 128. We train all the models to 100k steps with Adam optimizer and scheduled learning rate detailed the original paper. All the models converged within 12 hours using V100 GPU cores.
All the results are acquired by applying each trained model the dataset, based on the same set of captioning metrics. As shown in Table 3 our method outperforms the benchmark method Embed-4D (#Params=5. 11MM) with a large margin even though our method uses fewer parameters (#Params=5.07MM particularly on BLEU-1, BLEU-2, ROUGE and CIDEr, which clearly advanced the state of the for this task. Interestingly, both Faamaable-Fuurir--MLLPP Fourier+MLP outperform
and Learnable- which indicate that more complex dis- tances needed to modeled in this task than T.2 distances. Compared to Embed-4D,, T-tests (over 3 runs of each model) show the gain of (p 0.05) on BLEU-1, ROUGE, CIDEr and METOER: Learnable- Fouriar MLP 2/2 achieves significance (p 0.05) on BLEU-1, ROUGE and METOER. For the two champion conditions, i.e., Formable-Fourier-MLL..
4/1 is statistically significant
and 2/2, we found on most metrics there no statistical significance between their performance (p > 0.05). Farmable-FourierrMMLPPP with marginal statistical significance (p = 0.042).
outperforms 2/2 only CIDEr
We also included few ablation studies in this experiment. One variant is to fix Fourier features but still include MLP. In this group. i.c., Foredd-Furrir=-MLP. performs the best across all the metrics. Overall, it seems that Forrhebeee- still has advantages over the fixed one on most cases. We then look at Learnable-Fourt but without using MLP. Learnable- Searmable-Fourie-222 seems to perform worse than its counterpart in the other groups on every metric, which indicates that MLP is a crucial component for positional encoding this task. Lastly, although using MLP alone as the encoding function seems competitive in the object detection task, it performs poorly in this experiment.
Fxxed-Forrerr-MLPP. clearly
Discussion
One clear trend that emerges from our experiments is that positional encoding methods that treat an image as a flattened sequence (Embed-11) ID or Sine-1D) do not perform well, even though the model is given a great capacity to learn these positional relations. We also observe that taking multi-dimensional position holistically often performs better than representing each dimension separately and then concatenating these representations. We found it generally beneficial to use the

---

Left
Right
Top
Bottom
0.030
0.10
0.025
0.04
Density
0.020
0.06
0.019
0.02
0.04
0.005
0.2
0.02
11
0.02
40
00
00
100
0.00
:00
0.00
100
20
60
60
Position
Position
Position
Position
Figure 4: Widget position distributions for each dimension in the training set. There are positions rarely occurred in the training set.
multi-layes perceptron (Equation 6 to process the Fourier features for positional encoding before is mixed with content embedding. We obtained mixed results for using MLP alone as the positional encoding function, which performs competitively on the object detection task but poorly on the modeling task that involves sparse spatial structures. From these experiments, it seems not necessary use large random feature dimension to achieve good results.
Table 4: The accuracy each method on widgets with seen and unseen positions.
Method
Seen CIDEr
Unseen CIDEr
Embed-4D
123.4
78.5
Sine-4D
121.3
76.4
Faarnable-FuurerrMMMPP...
123.4
82.2
To understand how different positional encoding methods can generalize unseen positions, analyze test results for the widget captioning task. There are positional values rarely or never seen in the training set (Figure 4) Specifically, 1867 widgets in the test set have positions and 2692 have unseen positions. Table 4shows that our method generalizes to unseen positions significantly better than baselines. There a number of reasons for the proposed positional encoding generalize for unseen positions. First, it treats positions as continuous-valued vectors. As a result, it does not suffer from the difficulty with embedding based approaches where an embedding vector assigned discrete position, which can be not trained or significantly under-trained when position is unseen or rarely seen. Second, the Fourier features capture the relative positional relationships by maintaining the shift-invariant property during learning (Equation 3) which applies to unseen positions well.
One direction that deserves further investigation is how the interaction between positional encoding and content embedding should be taken into account for the design a positional encoding function. Our work investigated positional encoding when it combined with content embedding via addition for all the image tasks. It would be interesting to investigate how our positional encoding performs when it is concatenated with content embedding these tasks.
Although Euclidean distances might be a desirable positional metric for images, tasks such as widget captioning involves sparse spatial structures, and the spatial relations between rectangular objects on the screen can be more complicated. For example, similarity between two bounding boxes can be related their vertical horizontal alignment overlaps (loU), other domain specific factors related to UI layouts. Our positional encoding method outperformed benchmark methods in this task, which showed that it is better equipped to capture these spatial relationships. Yet, it is worth investigating methods that can more directly capture these complex spatial relationships.
6 Conclusion
We present a novel approach for positional encoding based on learnable Fourier features. We evaluate our approach on range of multi-dimensional spatial tasks, including image generation, object detection, image classification, and sparse spatial structure modeling in user interfaces, which show that our positional encoding consistently outperforms the benchmark methods.
10

---

Acknowledgments
We would like thank anonymous reviewers for their insightful comments and constructive feedback that have significantly improved the work.
References
[1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate, 2014. cite oral presentation.
Accepted at ICLR 2015 as
[2] Irwan Bello, Barret Zoph, Ashish Vaswani, Jonathon Shlens, and Quoe V. Le. Attention augmented convolutional networks. In Proceedings of the IEEF/CVF International Conference on Computer Vision (ICCV), October 2019.
[3] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and
Sergey Zagoruyko. End-to-end object detection with transformers. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision ECCV 2020- 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings. Part I, volume 12346 of Lecture Notes in Computer Science, pages 213-229. Springer, 2020.
[4] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. CoRR, abs/1904.10500 2019.
[5] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, David Belanger, Lucy Colwell, and Adrian Weller. Masked language modeling for proteins via linearly scalable long-context transformers, 2020.
[6] Xiangxiang Chu, Bo Zhang, Zhi Tian, Xiaolin Wei, and Huaxia Xia. Do we really need explicit position encodings for vision transformers? CoRR, abs/2102.10882, 2021.
[7] Zihang Dai. Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transoomer--LL Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978-2983 Florence, Italy, July 2019. Association for Computational Linguistics.
[8] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics.
[9] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby, An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[10] Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolu- tional sequence to sequence learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1243-1252. PMLR, 06-11 Aug 2017.
[11) Benjamin Graham, Alaaeldin El-Nouby, Hugo Touvron, Pierre Stock, Armand Joulin, Hervé Jégou, and Matthijs Douze. Levit: a vision transformer convnet's clothing for faster inference. ICCV 2021, abs/2104.01 136. 2021.
[12] Raffay Hamid, Ying Xiao, Alex Gittens, and Dennis DeCoste. Compact random feature maps. In Proceedings of the 31 International Conference on International Conference on Machine Learning- Volume 32, ICML' 14, 2014.
[13] Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention, 2021.

---

[14] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation. 9:1735-80, 12 1997.
[15] Cheng-Zhi Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Noam Shazeer, Curtis Hawthorne, Andrew M. Dai, Matthew D. Hoffman, and Douglas Eck. An improved relative self-attention mechanism for transformer with application to music generation. CoRR, (oss/18990428., 2018.
[16] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In ICLR, 2020.
[17] Quoc Le. Tamas Sarlos, and Alexander Smola. Fastfood: Approximate kernel expansions in loglinear time. 30th International Conference on Machine Learning, ICML. 2013, 2014.
[18] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Comput., 1(4):541-551, December 1989.
[19] Yang Li, Jiacong He, Xin Zhou, Yuan Zhang, and Jason Baldridge. Mapping natural language instructions mobile UI action sequences. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 8 9200,,, Online, July 2020. Association for Computational Linguistics.
[20] Yang Li, Gang Li, Luheng He, Jingjie Zheng, Hong Li, and Zhiwei Guan. Widget captioning: Generating natural language description for mobile user interface elements. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5495-55 10, Online, November 2020. Association for Computational Linguistics.
[21] Yanjun Li, Kai Zhang, Jun Wang, and Sanjiv Kumar. Learning adaptive random features. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):4229 4236, Jul. 2019.
[22] Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pictro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitmick. Microsoft COCO: common objects in context. In David J. Fleet, Tomás Pajdla, Bernt Schiele, and Tinne Tuytelaars, editors, Computer Vision ECCV 2014 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V, volume 8693 of Lecture Notes in Computer Science, pages 740-755. Springer, 2014.
[23] Xuanqing Liu, Hsiang- Fu Yu, I. Dhillon, and Cho-Jui Hsich. Learning to encode position for transformer with continuous dynamical model. In ICML, 2020.
[24] Antoine Liutkus, Ondřej Cifka, Shih-Lun Wu, Umut Simsekli, Yi-Hsuan Yang, and Gael Richard. Relative positional encoding for transformers with linear complexity. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7067-7079. PMLR, 18 24 Jul 2021.
[25] Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches to attention-based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Nat- ural Language Processing, pages 1412-1421, Lisbon, Portugal, September 2015. Association for Computational Linguistics.
[26] Masato Neishi and Naoki Yoshinaga. On relation between position information and sentence length in neural machine translation. In Proceedings of the 23 Conference on Computational Natural Language Learning (CoNLL), pages 228-338, Hong Kong, China, November 2019. Association for Computational Linguistics.
[27] Andrei Nicolicioiu, Iulia Duta, and Marius Leordeanu. Recurrent space-time graph neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. -uché-Buc, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[28) Giambatrista Parascandolo, Heikki Huttunen, and Tuomas Virtanen. Taming the waves: sine as activation function in deep neural networks. 2017.
12

---

[29] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages PMLR.
Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018.
[30] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Ad- vances in Neural Information Processing Systems 20, Proceedings of the Twenty-Firyy Anmual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 1177-1184, 2007.
[31] Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimiza- tion with randomization in learning. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 1313-1320, 2008.
[32] Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jon Shlens. Stand-alone self-attention in vision models. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Bus E. Fox, and R. Gareett, editors, Advances in Neural Information Process- ing Systems, volume 32. Curran Associates, Inc., 2019.
[33] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position rep- resentations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Short Papers), pages 464-468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
[34] Alex Sherstinsky. Fundamentals of recurrent neural network (RNN) and long short-term memory (LSTM) network. CoRR, abs/1 0008.03314 14, 2018.
[35] Vighnesh Leonardo Shiy and Chris Quirk. Novel positional encodings to enable rreebased transformers. In NeurlPS 2019, 2019.
[36] Yitong Sun, Anna Gilbert, and Ambuj Tewari. But how does it work in theory? linear svm with random features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 3383-3392, 2018
[37] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. arXiv preprint arXiv:2012.12877, 2020.
[38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.053 03762, 2017.
[39] Benyou Wang, Lifeng Shang, Christina Lioma, Xin Jiang, Hao Yang, Qun Liu, and Jakob Grue Simonsen. On position embeddings in (bert). International Conference on Learning Representations, 2021.
[40] Benyou Wang, Donghao Zhao, Christina Lioma, Qiuchi Li, Peng Zhang, and Jakob Grue Simon- sen. Encoding word order in complex embeddings. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[41] Xing Wang. Zhaopeng Tu, Longyue Wang, and Shuming Shi. Self-attention with structural position representations. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-ID) EEMNLP-IJCNPP,, pages 1403-1409, Hong Kong, China, November 2019. Association for Computational Linguistics.
[42] Jiyan Yang, Vikas Sindhwani, Haim Avron, and Michael Mahoney. Quasi-monte carlo feature maps for shift-invariant kernels. 3/ International Conference on Machine Learning, ICMI. 2014, 1, 12 2014.
13

---

[43] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bun Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 5753-5763, Curran Associates, Inc., 2019.
14


Reviews:
[{"review_id": "trgRX3S9vzG", "reviewer": "Reviewer_cSb4", "summary": "\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "See Table 8 of Dosovitskiy et.al., equipping with different position embeddings does not produce significantly different results -- this is perhaps due to that the training data and used transformer models in Dosovitskiy et.al. is much larger than in this paper. I am wondering whether the proposed PE also performs better the those PE baselines in image recognition. If it is not, does this mean image generation,  object detection, and widget captioning tasks are more sensitive to the positions of the input? If the authors already did the image recognition, the performance should be reported, otherwise, some discussions may be needed.  So I feel that it may be risky to conclude that the proposed position embedding is generally better than existing ones.\n\nDosovitskiy et.al. AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE. ICLR 2021\n\n\nIt seems that the proposed position encoding is different due to 1)being parameterized by learnable sinusoidal functions 2) being extended to a multi-dimensional case. Note the former may need to be discussed the one in Wang et.al. which proposes learnable sinusoidal PEs. Regarding the latter, one can easily know that Eq. 2 is equivalent to the case when you separately learn learnable  Fourier Features for each dimension (vertical or horizontal dimension) and then concatenate them together. Let me know if I was wrong. \n\nWang et.al. On position embeddings in BERT\n\nWith sin or cosine activations, there are some optimization issues regarding the local minimum, see Parascandolo et.al. It would be better if you could mention this if necessary.\n\nParascandolo et.al. Taming the waves: sine as activation function in deep neural networks \n\nIt may be interesting if you could visualize the learned W_r in eq 2.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Using sine/cosine as an activation function may be problematic during optimization.  This should be mentioned.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "s8vDp0xhyP6", "reviewer": "Reviewer_9tzP", "summary": "This paper motivates and introduces a way to do positional encoding that involves a multidimensional sinusoidal encoding with trainable weights followed by a MLP. The method is simple to implement and is advocated as working well. \nThe balance between the theory and the (very impressive) experiments is good.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I must say that I already reviewed this paper for ICML, and that I was the grumpy reviewer for that paper in that occasion, notably pointing out that some claims were not appropriately justified (novelty on multidimensional sinusoidal encoding) and that the MLP, that seems important, was completely ignored during the discussion.\n\nI was happy to review this paper again because I really hoped that the authors would have fixed these issues, since I believed the contribution is good. And it turns out I am now fully satisfied, because I feel that the authors understood they could not claim to fully understand what happens now in their model (due to the MLP) as they were pretending before. The resulting discussion appears more humble but then way more inspiring and actually more impressive to me. I therefore want to thank the authors for taking the time to work so much on the paper again, notably because of me. But now you got me as a big supporter.\n\n\nI have some comments still:\n\nIntroduction\n* L28: \", which\" reads wrong\n\nBackground\n* L105-107: Actually, there were very recent works for relative PE with linear complexity that could be referenced here. (your approach is still different indeed)\n\n3. Learnable Fourier Features positional encoding\n* I must say that I appreciate how the authors modified their discussion here to explicitly mention that their proposed representation is a generalization of sinusoidal PE\n* In algorithm 1, the title is \"compute the PE\", while there is an \"initialization\" step to compute this randomized Wr. This is still a bit confusing.  I understand that somehow this Wr variable is static, so that it is initialized if it's the first run, and kept as it is otherwise, but there is probably a better way to write this. Maybe as describing your positional encoding as a module ? `Constructor` you get the init. Then in the `forward`: your computation ?\n* Thanks a lot for including this Transformer MD-sine experiment that I was asking for. This looks quite surprising that the MD-sine+mlp behaves so badly. It hence seems that training the frequencies is crucial here. \n* I don't understand the difference between MD-sine and Fourier. Is this the actual frequencies that are picked ? Instead of the regular sampling of the spectrum in MD, you sample in a Gaussian way, that's it ?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no relevant societal impact.\nlimitations of the work are not highlighted by the authors. maybe that could be interesting to know of further research.", "review_text": "", "extra_scores": {"ethical_concerns": "nothing particular", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "rEhbmAHzrgo", "reviewer": "Reviewer_SAzJ", "summary": "Modern architectures like transformers relax how data is presented to a network with respect to spatial (or temporal) relationships by allowing the position to be explicitly encoded as part of the input vector rather than implicitly (e.g. in a lattice or sequence). The first transformer model proposed a hand-crafted fixed distributed position encoding based on sinusoidal waves. More recently models like BERT propose to learn the position encoding directly from the data, but this is expensive. This paper proposes a kind of middle ground: a learnable Fourier feature mapping projected by a small MLP. The inductive bias from the Fourier mapping has the advantage of requiring many fewer learnable parameters than a fully unconstrained data driven approach, and naturally extends beyond positions in a sequence to positions in a lattice/grid, etc (existing approaches are based on concatenated dimension-wise embeddings, so capturing similarity on Lp distances for example isn't _directly_ possible - it can be learned with extra functional layers, but then generalisation becomes more problematic empirically).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n-----------\n\nThis is original to the best of my knowledge (but I'd be first to admit to not having read every paper using/proposing a positional embedding). In terms of related work, it certainly covers the papers I am familiar with. The authors have done a good job (see below) of making it clear how this differs from other works.\n\n\nQuality\n-------\n\nOverall, my impression is that what is proposed is a sound idea (it's certainly intuitive enough), and the experimental results validate it in a number of different scenarios. Obviously it would be nice to see how well it works in a large scale language modelling task, but given the resources required it is understandable this might not be achievable. \n\nThe authors appear to have done a solid job at evaluating their proposed approach, and have performed multiple repeats where possible, although elicitation of this could be improved (see below).\n\nClarity\n-------\n_Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)_\n\nThe authors should be commended for the clarity of the presentation in the early part of the paper (sections 1 & 2). They clearly explained the problem they are trying to address and have given clear (often visual) examples of the shortcomings of the existing approaches. The writing is also self contained - I did not need to refer back to other papers to understand what the point being made is.\n\nSection 3 could be improved a bit: \n\n- Eqn 5 (and the discussion about it) and algorithm 1 are a bit disjoint. Where did $W_p$ go? Why not just say its a two-layer MLP from the outset? Where did $\\phi$ go in the algorithm (it's obvious if you read it in detail, but you can make it easier for the reader)\n- Alg 1 line 2 - help the reader and maybe just add a comment to say its a ReLU or change the Max(0,x) to ReLU(x)?\n- Fig 3. Can you redraw this properly with error bars (or shaded bands) and remove any smoothing (I could be wrong but it looks like the plots might be showing the EMA rather than raw data; the problem with this is that it can remove fluctuations that could ultimately make you draw very different conclusions about performance of different algorithms)\n\nThere are a couple of areas where the writing/presentation could be slightly improved (this is rather nit-picky, but hopefully is helpful):\n\n- Line 137: maybe better to say Fourier feature**s** [...] **are**... **a** Gaussian kernel, ...?\n- Line 142: feature**s** **have**\n- Line 143: are -> have been \n- Line 167: introduce**s**\n- Line 173/4: **an** RNN\n- Line 246: **a** Transformer?\n- Line 263: rest -> other\n- Tab 1 caption: accuracy -> performance\n- Tab 1, 2: reformat according to NeurIPS style (it really does look better!)\n- Line 311: treats -> treat\n- Fig 3, 4, 5. Please make label & caption text bigger\n\nSignificance\n------------\n\nJudging significance is hard, but I can see the potential value in the proposed approach if it works on other problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Whilst technical limitations are covered fairly well, in my view the potential broader societal impacts are insufficiently addressed. The statement in the Broader Impact section reads like the authors are completely disengaged from the current discussion around potential broader (potentially negative) impact. I'd argue that in 2021, for a paper that has real potential for tangible impact in a number of areas, that this is not acceptable. \n\nAt the very least I'd encourage the authors to at least read though some of the guidelines from last year's NeurIPS (e.g. https://medium.com/@GovAI/a-guide-to-writing-the-neurips-impact-statement-4293b723f832 and https://brenthecht.medium.com/suggestions-for-writing-neurips-2020-broader-impacts-statements-121da1b765bf) and give this some more thought.      ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mVZ6dSEf5DX", "reviewer": "Reviewer_gVFH", "summary": "This paper proposes a learnable positional encoding based on Fourier features for capturing not only positions but also complex positional relationships in the vision domain. The experimental results demonstrate the effectiveness of the proposed method.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the effectiveness of the proposed method does not convince by following concerns;\n- Baselines; The proposed method is designed for handling images, and the image classification task is one of the major tasks in computer vision. However, the authors do not demonstrate the effectiveness of the method in the clasification task. Besides, there are several related works that consider improving positional encodings based on Vision Transformer; in detail, Graham et al.[1] introduces attention bias, which lines up with Shaw et al.[2], for providing positional information in each self-attention layer, instead of the input layer. On the other hand, Chu et al.[3] suggests conditional position encoding, which depends on input, by using outputs of depth-wise convolution to the patches.\n- Marginal improvements; Figure 4. shows applying MLP already outperforms the baselines and the improvement from adding learnable Fourier is marginal. So, I concern that the most improvements are from the increased number of parameters by adding MLP. Moreover, Figure 3 (a) also shows marginal improvements compared to Embed-2D, which is the original positional encoding of Reformer. \n- Clarification; The authors claim that complex spatial relationships can be captured by the proposed method, but the explanation and experimental backups are insufficient. \n\nMinor comments\n- Unclear notations; e.g. $\\phi$ in eq. 5\n- missing ref in Checklist \n\n[1]Graham, B., El-Nouby, A., Touvron, H., Stock, P., Joulin, A., Jégou, H., and Douze, M. Levit: a vision transformer in convnet’s clothing for faster inference.arXiv preprint arXiv:2104.01136,3202021\n\n[2]Shaw, P., Uszkoreit, J., and Vaswani, A.  Self-attention with relative position representations.arXiv preprint arXiv:1803.02155, 2018\n\n[3]Chu, X., Tian, Z., Zhang, B., Wang, X., Wei, X., Xia, H., and Shen, C. Conditional positional308encodings for vision transformers.arXiv preprint arXiv:2102.10882, 2021\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think there is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "LNzBRgrGKAz", "reviewer": "Reviewer_xpKV", "summary": "This paper proposes a new form of positional encoding that introduces more inductive bias (based on L2 distance). The method is a combination of learned Fourier features and MLP transform, demonstrating better performance and faster convergence on both vision and language tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The methodology is simple and can replace existing positional encoding methods in place. The authors verify the effectiveness and generality of this new positional encoding on a variety of tasks, including machine translation in NLP, discriminative and generative tasks in CV.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The training curves in Fig 3 & 4 seem to be close to each other, other than the trivial embed-2D. Without the precise numbers, it is hard to determine whether the proposed design brings about significant improvement.\n\nThe increased computational complexity and runtime are also concerned, but not mentioned in the original paper. I would appreciate it if the authors can also provide these statistics.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "2BByYFmn4ZC", "reviewer": "Reviewer_TqtX", "summary": "This paper proposes a new positional encoding (PE) method for transformers. The key idea of this work is to use the Fourier Features technique, which is able to transform the dot product of two vectors into the L2 distance between two positions. By using this technique, the self-attention on PE in transformers, which is essentially dot-product, can be transformed into L2 distance between two positions. Overall, to my understanding, this idea can achieve the effect of relative PE but avoid the problems of relative PE. I think it is really a good idea.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n+ The paper is well-motivated and easy to understand.\n+ To me, the proposed idea, i.e., using the fourier features technique in PE, is very interesting. This idea can solve many problems in previous PE methods such as sinusoidal PE or learnable PE. For example, this PE can naturally work well with the self-attention in transformers, and unlike relative PE, it does not need to change the existing implementation of self-attention.\n+ In experiments, the proposed methods also show superior performance than other methods.\n\nCons:\n\n- The biggest issue of this work is in the experiment section. Although the idea shows some positive results in the included experiments, I think the authors should present more results.\n\nFor example, how is the performance comparison with relative PE? I understand by design, the idea is better than relative PE, but the performance comparison should also be reported.\n\nAlso, on object detection, why did you only show the results in the first 100K steps? I think the final performance should be reported.\n\nHow is the performance of the ImageNet classification? The ImageNet classification is one of the most popular tasks, and I think the performance on it is important.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It seems the authors did not mention the limitations of this work. Please include them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The majority of reviewers agreed that this paper presents an interesting idea related to a relevant application. 
Decision: Accept (Poster)