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. edu
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-dimeniional
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://gitte /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 V
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--oorrrr+MMMM 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/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-MM.PP11/
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 Faamaabl--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-MLP.. 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, (bss/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 9210,,, 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": "zTrWBJe-Cfe", "reviewer": "Reviewer_ZKdD", "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).\n\nImprovements provided by the proposed positional embedding are demonstrated \n- for tasks with 2D positions in an image: \n  - Reformer model for image generation task on ImageNet 64x64 dataset \n  - DETR model for object detection task on COCO 2017 detection dataset (faster convergence also observed for DETR experiments)\n- for widget captioning task in graphical user interfaces with 4D positions representing bounding box (also better generalization to unseen positions is observed)", "questions": "", "limitations": "", "rating": 6, "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": "**Originality**\n\nAuthors 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).\nOriginal 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.\n\n**Quality** \n\nProposed 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.\n\n- 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: \n  - (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$.\n  - (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).\n  - (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).\n  - Thanks for additional analysis on the inner product of embeddings in Appendix.\n- Generalization study.\n  - 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?\n  - 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).\n- 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.\n- How was $gamma$ hyper-parameter chosen for different tasks (1 for image generation and 100 for widget captioning)?\n- For DETR experiments in Fig. 4 why did authors stop at 100k updates? Seems models are not fully converged yet.\n- 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).\n- 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?\n- 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? \n\n**Clarity**\n\nThe 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.\n\n- line 28 \"which a position\" -> \"where a position\"\n- line 163 \"are initialized\" -> \"is initialized\"\n- 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)\n- 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).\n- 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.\n- 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? \n- Fig. 2b - what is the matrix $W_r$ used here? Some random matrix from normal distribution?\n- 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)?\n- Appendix line 67 \"(Figure 2\" -> \"Figure 2\" - remove bracket, line 91 \"forLearned\" -> \"for Learned\"\n- Appendix Fig 3, 4 recheck $\\gamma$ in captions\n- line 275 \"We\" -> \"we\"\n- Table 1 last column the bold value is wrong, another row should be bold.\n\n**Significance**\n\nPositional 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "gPEusIaTrke", "reviewer": "Reviewer_xZYh", "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.", "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": "[Originality]\n- 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.\n\n[Quality]\n- The proposal is well ablated and compared with various baselines in the experiments.\n- Extensive experiments on various types of vision tasks and transformer models demonstrate the proposal's generality.\n\n[Clarity]\n- The motivation of the paper is well illustrated with several figures. \n- The description of the method is well written and its implementation details are well-summarized in the algorithm box.\n\n[Significance]\n- 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.\n\n[Suggestion]\n- 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.\n- 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "YJrH9wHaPPW", "reviewer": "Reviewer_HjX3", "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.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "three"}, "extra_text": {}}, {"review_id": "2elIyUI5tMr", "reviewer": "Reviewer_aPhY", "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. ", "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": "**Strengths**:\n\nThe 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. \n\n**Weaknesses:** \n\nWhile the proposed approach seems promising, the following points either need further justification or clarification:\n\n**1- Distance function:**\n- 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.\n\n- 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.\n\n- 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?\n\n\n**2- Capacity of embedding function:**\n\n- 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?\n\n**3- clarity:**\n\nIn 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.\n\n- 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. \n\n- Are W1, B1, W2, B2 mentioned in Algorithm 1 part of W_p? If so, it should be clarified.\n\n- 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?\n\n**4- correctness:**\n\n- 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 \ncomponents (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?\n\n- 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "**Regarding checklist:**\n\n- The code is not provided, while authors have answered Yes.\n\n- I did not see any section on the limitation of the proposed approach, while authors have answered Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "There is no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}]

Author rebuttal:

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)