FourierFormer: Transformer Meets Generalized Fourier Integral Theorem
Authors: Tan Minh Nguyen
Minh Pham
Tam Minh Nguyen
Khai Nguyen
Stanley Osher
Nhat Ho
Venue: NeurIPS 2022 Accept (2022)
Keywords: transformers
fourier integral
nonparametric kernel regression

Abstract: Multi-head attention empowers the recent success of transformers, the state-of-the-art models that have achieved remarkable success in sequence modeling and beyond. These attention mechanisms compute the pairwise dot products between the queries and keys, which results from the use of unnormalized Gaussian kernels with the assumption that the queries follow a mixture of Gaussian distribution. There is no guarantee that this assumption is valid in practice. In response, we first interpret attention in transformers as a nonparametric kernel regression. We then propose the FourierFormer, a new class of transformers in which the dot-product kernels are replaced by the novel generalized Fourier integral kernels. Different from the dot-product kernels, where we need to choose a good covariance matrix to capture the dependency of the features of data, the generalized Fourier integral kernels can automatically capture such dependency and remove the need to tune the covariance matrix. We theoretically prove that our proposed Fourier integral kernels can efficiently approximate any key and query distributions. Compared to the conventional transformers with dot-product attention, FourierFormers attain better accuracy and reduce the redundancy between attention heads. We empirically corroborate the advantages of FourierFormers over the baseline transformers in a variety of practical applications including language modeling and image classification.

FourierFormer: Transformer Meets Generalized Fourier Integral Theorem
Tan M. Nguyen' Department of Mathematics University of California, Los Angeles
Minh Pham"
Department of Mathematics
University of California, Los Angeles minhroseducla. edu
tanmguyen88@uclla edu
Tam Nguyen Department of ECE
Khai Nguyen
Department of Statistics and Data Sciences University of Texas at Austin khainbeutexas edu
Rice University aguyemminhtaam@5500gaa com
Stanley J. Osher** Department of Mathematics University of California, Los Angeles sj o @math. ucla. edu
Nhat Ho T*
Department of Statisties and Data Sciences University of Texas at Austin minhnhat@utexas.c
Abstract
Multi-head attention empowers the recent success of transformers, the state-of-the art models that have achieved remarkable success in sequence modeling and beyond. These attention mechanisms compute the pairwise dot products between the queries and keys, which results from the use of unnormalized Gaussian kernels with the assumption that the queries follow mixture of Gaussian distribution. There is no guarantee that this assumption is valid in practice. In response, first interpret attention in transformers as a nonparametric kernel regression. We then propose the FourierFormer, are replaced by the novel generalized Fourier integral kernels. Different from the dot-product kernels, where need choose good covariance matrix capture the dependency of the features of data, the generalized Fourier integral kernels can automatically capture such dependency and remove the need tune the covariance matrix. We theoretically prove that our proposed Fourier integral kernels can effi- ciently approximate any key and query distributions. Compared to the conventional transformers with dot-product attention, FourierFormers attain better accuracy and reduce the redundancy between attention heads. We empirically corroborate the advantages of FourierFormers over the baseline transformers in variety of practical applications including language modeling and image classification.
class of transformers in which the dot-product kernels
1 Introduction
Transformers [83] are powerful neural networks that have achieved tremendous success in many areas of machine learning [40, 76, 36] and become the state-of-the-ant model on wide range of applications across different data modalities, from language [23, 1, 18, 13, 62, 4, 8, 21] to images [24, 43, 78, 63, 59, 27], videos [3, 44], point clouds [97, 31], and protein sequence [65, 34). In addition to their excellent performance on supervised learning tasks, transformers can also effectively transfer the learned knowledge from pretraining task new tasks with limited or no supervision [60, 61, 23, 94, 42]. At the core of transformers is the dot-product self-attention, which
CCo-first authors. Co-last authors. Please correspond taamnguyen89@uuclcee
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

mainly accounts for the success of transformer models [14, 56, 41]. This dot-product self-attention learn self-alignment between tokens in an imput sequence by estimating the relative importance of a given token with respect to all other tokens. It then transform each token into a weighted average of other tokens where the weight is proportional to importance score
the feature representations between each pair of tokens. The importance scores in self-attention enable token to attend to other tokens in the sequence, thus capturing the contextual representation [6, 83, 38).
1.1 Self-Attention
[=1.... _N]" E Nx of N feature vectors, self-attention computes the output sequence H from X as follows:
Given an input sequence X
Step 1: Projecting the input sequence into different subspaces. The input sequence X is transformed into the query matrix Q the key matrix K, and the value matrix V via three linear transformations
Q = XW
Qi K XW K XW
where We, WK E DxDs and Wv E D.xD, are the weight matrices. We denote Q := 41
AN
K = k, ky]", and V := [v v where the vectors qs kj V, for .N are the query. key, and value vectors, respectively.
Step 2: Computing the output as weighted average. The output sequence H [h1," hx]
then given by
[QK] /VD)V= AV, AV,
= softmax
(1)
where the softmax function is applied to each row of the matrix (QK qt ,, Eqn. (I) be written in the vector form compute the output vector h, as follows
(QKT)/VZ I/VD. For each query vector
h; Σ softmax (a (TTk//D)
Σ Vg
The matrix A NNN and its component dij for i, j 1, ,N NN are the attention matrix and attention scores, respectively. The self-attention computed by equations (1) and (2) is called the dot- product attention or softmax attention. our paper, we refer transformer that uses this attention as the baseline transformer with the dot- dot-product attention or the dot-product transformer. The structure of the attention matrix A after training governs the ability of the self-attention to capture contextual representation for each token.
Multi-head Attention Each output sequence H forms attention head. Multi-head attention concatenates multiple heads to compute the final output. Let H be the number of heads and WO IR DDD.HDD be the projection matrix for the output. The multi-head attention is defined as
MultiHead (fQ, K, (
Concat(H,,..... "....,H))W"" Wo
The capacity of the attention mechanism and its ability to learn diverse syntactic and semantic relationships determine the success of transformers [77, 84, 17, 85, 32]. However, equations (1) and (2) implies that the dot-product attention assumes the features (gil...., (.D) in qi as well as the features (kj1,..., ).D) in ky. are independent. Thus, the dot- dot-product attention fail to capture the correlations between these features, limiting its representation capacity and inhibit the performance of transformers on practical tasks where there is no guarantee that independent features can learned from complex data. One solution to capture correlations between features q, and k, is to introduce covariance matrices into the formulation of the dot-product attention with the cost of significantly increasing of the computational complexity. Also, choosing good covariance matrices is difficult.
1.2 Contribution
In this paper, we first establish a correspondence between self-attention and nonparametric kernel regression. Under this new perspective of self-attention, we explain the limitation of the dot-product self-attention that it may fail capture correlations between the features in the query and key vectors. We then leverage the generalized Fourier integral theorems, which can automatically capture these correlations, and derive the generalized Fourier integral estimators for the nonparametric regression problem. Using this new density estimator, we propose the FourierFormeer, novel class of transformers that can capture correlations between features the query and key vectors of self-attention. In summary, our contribution is three-fold:

---

1. We derive the formula of self-attention from solving a nonparametric kernel regression problem, thus providing a nonparametric regression interpretation to study and further develop self-attention.
2. We develop the generalized Fourier integral estimators for the nonparametrie regression problem and provide theoretical guarantees for these estimator.
3. We propose the FourierFormer whose attentions use the generalized Fourier integral es- timators to capture more efficiently correlations between features in the query and key vectors.
Finally, we empirically show that the FourierFormer attains significantly better accuracy than the baseline transformer with the dot-product attention on variety of tasks including the WikiText language modeling and ImageNet image classsification. We also demonstrate in our experiments that FourierFormer helps reduce the redundancy between attention heads.
Organization We structure this paper as follows: In Section 2, we present the correspondence between self-attention and nonparametrie kernel regression. In Section 3. we discuss the generalized Fourier integral estimators and define the FourierFormer. We validate and empirically analyze the advantages of FourierFormer in Section 4. We discuss related works in Section 5. The paper ends with concluding remarks. Technical proofs and more experimental details are provided in the Appendix.
Notation For any N E N, we denote [N] 21, NN. For any D 2 1, J., (R.P) denotes the space real-valued functions on TR." that are integrable. For any two sequences {ax N21, (bv N211 we denote a O(bx) to mean that ON S Cby for all N 2 1 where C is some universal constant.
2 A Nonparametric Regression Interpretation of Self-attention
In this section, we establish the connection between self-attention and nonparametric kernel regression. In particular, we derive the self-attention in equation (2) as nonparametric kernel regression in which the key vectors kj and value vectors V, are training inputs and training targets, respectively, while the query vectors qi and the output vectors h, form a set of new inputs and their corresponding targets that need to be estimated, respectively, for i, j 1, .N. In general, we can view the training set (k;, vj} for j E [N] to come from the following nonparametric regression model:
V, f(k,)) + Ejz
where $1,..., N are independent noises such that B(e,) = O. Furthermore, we consider a random design setting where the key vectors k1, ....... admits as density function. By an abuse of notation, we also denote p as the joint density where the key and value vectors (V1, ......... (Vv, are i.i.d. samples from. Here, f is true but unknown function and we would like to estimate it.
... KN are i.i.d. samples from the distribution that
estimate the function f is based Nadaraya- Watson's 's nonparametric kernel regression approach [50]. In particular, from the nonpara- metric regression model (3), we have E [ k f(k,) for all j E [N]. Therefore, it sufficient to estimate the conditional distribution of the value vectors given the key vectors. Given the density function p of the key vectors and the joint density p of the key and value vectors, for any pair of vectors (v. k) generate from model (3) we have
Nadaraya-Watson estimator Our approach
= / v p(v(k)dv = =
v VVV.pl,v p(v,
[v|k]
dv.
(4)
p(k)
R
The formulation (4) of the conditional expectation indicates that long as we can estimate the joint density function p(v, k) and the marginal density function p(v), we are able to obtain an estimation for the conditional expectation and thus for the function f. This approach is widely known as Nadaraya-Watsee Watson's 's nonparametric kernel regression approach.
Kernel density estimator To estimate p(v, k) and p(k),, we employ the kernel density estimation approach [66, 57]. In particular, by using the isotropic Gaussian kernel with bandwidth a, we have the following estimators of p(v, k) and pkk):
N Σ j=1
po(v,
1 N
Σ (o v,)po(k (k- k,), 1=1
(k)
Po (k k2),
(5)
3

---

where (Po()) (.) is the isotropic multivariate Gaussian density function with diagonal covariance matrix I'In- Given the kernel density estimators (5), we obtain the following estimation of the function f:
EN (k) / V.PolV,k) dv= V.EY=1 2 PolV Vy)go k;)) (k)
dv
JRD
Ex=1 Po kj)
Ei Pa (k - -ki) J (o vy)dv Ex1 UjPo (k (kj))
(6)
Eo iPo kj)
Σラ Po (k: kj)
Connection between Self-Attention and nonparametrie regression By plugging the query vectors q: into the function fo in equation (6), obtain that
(q)) = Σ N V, exp (- 11 k2112/202)
Ej exp
(ap(-1 qq - k5112/202)
Σ N Vj exp |- (1lq: [|k,]1?) /202 exp (q:k:] /0²)
Σ exp |- (11q:11 2 + || |2 exp (qikk /02)
we further assume that the keys k are normalized, which usually done in practice to stabilize the training of transformers [71], the value of (q:) in equation (6) then becomes
Σj Vyexp (aik) 102) Σ exp [q:kk]/11 /02)
fo(q))
Σ softmax q k k3//²²)
(8)
When we choose 0² vD where D is the dimension of qi and kj. equation (8) matches equa- tion (2) of self-attention, namely, (q:) h,, Thus, we have shown that self-attention performs nonparametric regression using isotropic Gaussian kernels.
Remark The assumption that k; is normalized is to recover the pairwise dot-product attention in transformers. In general, this assumption is not necessary. In fact, the isotropic Gaussian kernel in equation (7) is more desirable than the dot-product kernel in equation (8) of the pairwise dot dot-product attention since the former is Lipschitz while the later is not Lipschitz [37]. The Lipschitz constraint helps improve the robustness of the model [16, 81, 2] and stabilize the model training [48].
Limitation of Self-Attention From our nonparametric regression interpretation, self-attention is derived from the use of isotropic Gaussian kernels for kernel density estimation and nonparametric regression estimation, which may fail to capture the complex correlations between D features in qi and k; [88, 33]. Using multivariate Gaussian kernels with dense covariance matrices can help capture such correlations; however, choosing good covariance matrices is challenging and inefficient [87, 73, 11]. In the following section, we discuss the Fourier integral estimator and its use as kernel for computing self-attention in order to overcome these limitations.
3 FourierFormer: Transformer via Generalized Fourier Integral Theorem
In the following, we introduce generalized integral theorems that are able to capture the complex interactions among the features of the queries and keys. We then apply these theorems to density estimation and nonparametric regression problems. We also establish the convergence rates of these estimators. Given these density estimators, we introduce a novel family of transformers, named FourierFormer, that integrates the generalized Fourier integral theorem into the dot-product attention step of the standard transformer.
3.1 Generalized Fourier Integral Theorems and Their Applications
The Fourier integral theorem is a beautiful result in mathematics [92, 7] and has been recently used in nonparametric mode clustering, deconvolution problem, and generative modeling [33]. It is combination of Fourier transform and Fourier inverse transform. In particular, for any function

---

E LR)), the Fourier integral theorem is given by
{ / cos(s"
p(k) (2x) JRO
(k (k-yy)p(gu) y))ply
sin R(h;; -yi)) ply)dy,
lim
II ==1
TO R
JRD
(ky Uj)
where k (k1, KD) y (y1 ........ yD),
($1,...,..) and R is the radius. The de- tailed derivation of Equation (9) is in Appendix B.3. Equation (9) suggests that PR()) == " SRD 11 sin(R(y, -1,1 ply)dy can be used as estimator of the function p. (Dソ-
I
Benefits of the Fourier integral over Gaussian kernel There are two important benefits of the estimator PR: (i) can automatically preserve the correlated structure lying within p even when p is very complex and high dimensional function. It is in stark contrast to the standard kernel estimator built based on multivariate Gaussian kernel where we need to choose good covariance matrix in the multivariate Gaussian kernel guarantee such estimator work well. We note that the standard soft-max Transformer is constructed based on the multivariate Gaussian kernel, the issue of choosing good covariance matrix in dot-product transformer is inevitable; (ii) The product of sinc kernels in the estimator Pæ does not decay to a point mass when R - 30. It is in stark difference from the multivariate Gaussian kernel estimator, which converges goes to O. It indicates that is a non-trivial estimator of the function p. Finally, detailed illustrations of these benefits of the Fourier integral over Gaussian kernel in density estimation and nonparametric just
point mass when the covariance matrix
regression problems, which we have just shown to have connection to the self-attention in transformer, can be found in Section in [33].
Generalized Fourier integral estimator Borrowing the above benefits of Fourier integral estimator PR. in the paper would like to consider generalization of that estimator, named generalized Fourier integral estimator, which is given by:
RD
D
sin (R(y, - k2))
(k)
ply)dy
(10)
AD
R(yj - k2)
JRD
j=1
where A f2 sin(s)
dz and
RR
R given function. When okk) k for all
h E R.,, the generalized Fourier integral estimator pi becomes the Fourier integral estimator pn- Under appropriate conditions on the function & (see Theorem in Section 3.1.1 and Theorem 3 in Appendix C.1), the estimator P converges to the true function p, namely,
RD
D II J=1
sin( - kg)) -k,)) R(y; - k;)
p(k) = lim (k) lim 10+00
p(y)dy.
(1I)
AD
RD
We name the above limit as generalized Fourier integral theorem. Furthermore, the estimator Pi also inherits similar aforementioned benefits of the Fourier integral estimator PR. Therefore, we will use the generalized Fourier integral theorem as building block for constructing density estimators and nonparametric regression estimators, which are crucial to develop the FourierFormer Section 3.2.
3.1.1 Density Estimation via Generalized Fourier Integral Thcorems
We first apply the generalized Fourier integral theorem to the density estimation problem. To ease the presentation, we assume that k1, kgg ... ky TR. are i.i.d. samples from distribution admitting density function p where D 2 is the dimension. Inspired by the generalized Fourier integral theorem, obtain the following generalized Fourier density estimator ph of p follows:
RD
D EII à 1=1
N
[ii((((k, kig)) R(ky kigj)
( = NAD
(12)
where = fg sin(z) dz and k; (kar.... .., kD) for all i E [N]. To quantify the error between the generalized Fourier density estimator ph and the true density p. utilize mean integrated
5

---

squared enrors (MISE) [91], which is given by:
MISE(PN.R: = [ JRD (PN 2
(13)
We start with the following bound on the MISE between P., and p.
Theorem Assume that Jg (2s)n(2)/22z² for all j E [m] and Ja (=(sin(2)/=)112 de < 0o for some m E Then, there exist universal constants C and C' depending on and A such that
C Rm+I + C²R N
MISE(PN 6 N.R. S
Proof of Theorem is in Appendix D.I. A few comments are in order. First, by choosing R balance the bias and variance the bound of MISE Theorem 1, we have the optimal as R O(N1/ID+m+)) With that choice of R, the MISE rate of PN.R O(N((x+))
Second, when ((=) z' for / 2 4 and E R, the assumptions in Theorem 1 are satisfied when 1. Under this case, the MISE rate of PR is O(N-2(D++2). However, these assumptions do not satisfy when ((2) = and E {1, 2, 3), which due to the limitation of the current proof technique of Theorem that is based on Taylor expansion of the estimator Pr.Rt
To address the limitation the Taylor expansion technique, we utilize the Plancherel theorem in Fourier analysis to establish the MISE rate of Px when d(z) = z and E (1,2,3)- The details of the theoretical analyses for such setting are in Appendix C.
3.2 FourierFormer: Transformers with Fourier Attentions
Motivated by the preservation of the correlated structure of the function from the generalized Fourier integral theorem as well as the theoretical guarantees of density estimators, in this section we adapt the nonparametric regression interpretation of self-attention in Section 2 and propose the generalized Fourier nonparametric regression estimator in Section 3.2.1. We also establish the convergence properties that estimator. Then, based on generalized Fourier nonparametric regression estimator, we develop the Fourier Attention and its corresponding FourierFormer in Section 3.2.2.
3.2.1 Nonparametric Regression via Generalized Fourier Integral Theorem
We now discuss an application of the generalized Fourier integral theorems the nonparametric regression setting (3), namely, we assume that (V1,k1)... kı)........ (VN. kx) are i.i.d samples from the following nonparametric regression model:
f(k)) + Ejz
where E1...., N are independent noises such that E(e,) = and the key vectors k1, ..,..., ky are i.i.d. samples from p. Given the generalized Fourier density estimator (12), following the argument in -attron
Section 2, the Nadaraya- Watson estimator of the function f based on the generalized Fourier density estimator is given by:
N -
sin Ri kky))) li(k; kens)
N V Φ
fN.R(k) =
(14)
sin(J((k, k,,))
Rick
Krss
The main difference between the generalized Fourier nonparametric regression estimator JN.R in equation (14) and the estimator for in equation (6) is that the estimator fN. utilizes the generalized Fourier density estimator to estimate the conditional distribution of the value vectors given the key vectors instead of the isotropic Gaussian kernel density estimator as in fo. As we highlighted in Section 3, important benefit of the generalized Fourier density estimator is that it can capture the complex dependencies the features of the value vectors and the key vectors while the Gaussian kernel needs have good covariance matrix to do that, which is computationally expensive in practice.
We now have the following result establishing the mean square (MSE) of fN.R when D, 1.

---

Theorem Assume that fR sin(z)
2 for all 1 S m and J3 o sin(z) |2|5 < 0o
for any m +1 j S 2m + 2 for some m E N. Then, for any TR., when D. there exist universal constants C1, C2 C3 C4 such that the following holds:
B [K) {(k))) S
C1 R2(m++1)
(f(k) + (2))R))
( (FP(K))(R)).
N
where J(R) 1 p²]
Ca T
Cast (og(N
Here, the outer expectation is taken with
N
respect to the key vectors bi....,ke kN and the noises , EEN.
Proof of Theorem 2 in Appendix D.3. A few comments with Theorem are order. First, by choosing R to balance the bias and variance in the bound of the MSE of the nonparametric generalized Fourier estimator /N. R. we have the optimal radius
R (N (m=+++))) ). With that choice of the optimal radius R. the rate of fN.R is ON D13(+11) ). Second, when d(2) = a for 2 6, the assumption on the function of Theorem 2 is satisfied with m 1. Under this case, the rate of fN,R R
becomes ON Di+). In Appendix C, we also provide the rate of fN.R when o(2) = for some I s 5, which includes the original Fourier integral theorem.
3.2.2 FourierFormer
Given the generalized Fourier nonparametric regression estimator fN. n in equation (14), by plugging the query values :1....:9N 9N into that function, obtain the following definition of the Fourier attention:
Definition (Fourier Attention) A Fourier attention a multi-head attention that does nonpara- metric regression using the generalized Fourier nonparametric regression estimator JNN R. The output h, of the Fourier attention is then computed
ΣN V;
sin sin ((ng((g))ks))))) R( kz,))
h; = fN.R(q.)
Vie [N].
(15)
ΣN 11 j=1
sim Rim( k,,))
Rio:; kmzz)
Given the Fourier Attention in Definition I, we then give the definition of FourierFormer follows.
Definition (FourierFormer) A FourierFormer is a transformer that uses Fourier attention to capture dependency between tokens the imput sequence and the correlation between features in each token.
Remark (The Nonnegativity of the Fourier Kernel) The density estimation via generalized Fourier integral theorem in Section 3.1.1 does not require the generalized Fourier density esti- mator to nonnegative. However, empirically, we observe that negative density estimator can cause instability in training the FourierFormer. Thus, in FourierFormer, nonnegative function to enforce the density estimator to be nonnegative. In particular, we choose e to be power functions of the form δ(z) 2mm, where is positive integer. Note that when 1 and m = 2, the kernels in our generalized Fourier integral estimators are the well-known Fejer-de la Vallee Poussin and Jackson-de la Vallee Poussin kernels [20].
choose the function & to be
3.3
An Efficient Implementation of the Fourier Attention
The Fourier kernel is implemented efficiently in the C++CUUDA extension developed by Pytorch [58]. The idea is similar to the function cdist [58], which computes the p-norm distance between each pair of the two collections of row vectors. our case, we aim compute kernel functions that represent Fourier attention in Definition 1. The core of this implementation is the following Fourier metric function dy:
sin sin(Riquun k2a)) d Lg k2) = II
R(qua kza)
We directly implement dy as a torch. autograd Function [58] in which we provide an efficient way to compute forward and backward function (dy and gradient of d,). While the implementation
7

---

Table 1. Perplexity (PPL) on WikiText- 103 of FourierFormerr compared to the baselines. FourierForm- ers achieve much better PPL than the baselines.
Method
Valid PPT.
Test PPI.
Baseline dot-product (small)
33.15
34.29
FourierFormer (small)
31.86
32.85
Baseline dot-product (medium)
27.90
29.60
FourierForrer (medium)
26.51
28.01
of the forward function is straight forward, the backward function is more tricky since we need to optimize the code to compute the gradient of d w.r.f to variables q. k, and all at once. We can develop the backward function with highly parallel computation by exploiting GPU architecture and utilizing the reduction technique. The computational time comparable to function cdist; thus, our FourierFormer implementation is computationally time-efficient.
4 Experimental Results
In this section, we numerically justify the advantage of FourierFormer over the baseline dot-product transformer on two large-scale tasks: language modeling on WikiText-103 [46] (Section 4.1) and image classification on ImageNet [22, 67] (Section 4.2), time series classification
the UEA benchmark [5] (Section 4.3), and reinforcement learning on the D4RL Benchmark [29] (Section 4.4), and the machine translation on the IWSLT" 14 De-En [10] (Section 4.5). We aim to show that: (i) FourierFormer achieves better accuracy than the baseline transformer on a variety of practical tasks with different data modalities, and (ii) FourierFormer helps reduce head redundancy compared to the baseline transformer (Section 4.6).
Throughout the section, we compare FourierFormers with the baseline dot-product transformers of the same configuration. all experiments, we made the constant R Fourier attention (see equation (16) to be learnable scalar and set choose the function ((x) = x (see Remark 2). All of our results are averaged over runs with different seeds. The details on the models and training are provided in Appendix A. Moreover, additional experiments results are provided in Appendix E. Our PyTorch code with documentation can found at
Forree//rrrrirrrrrrr.rr.. NeurlPS.
4.1 Language Modeling on WikiText-103
We report the validation and test perplexity (PPL) of FourierFormer versus the bascline transformer with the dot-product attention in Table 1. FourierFormers attain much better PPL than the base- lines in both small and medium configurations. For the small configuration, the improvements of FourierFormer over the baseline are 1.29 PPL in validation and 1.44 PPL in test. For the medium configuration, these improvements are 1.39 PPL in validation and 1.59 PPL in test. These results suggest that the advantage of FourierFormer over the baseline dot-product transformer grows with the model's ' size. This meets our expectation because larger models has larger query and key di- mensions, e.g. the language model with medium configuration in this experiment has the query and key dimension of 256 versus 128 as in the language model with small configuration. Since the advantage of FourierFormer results from the property that FourierFormer can capture correlation between features in query and key vectors, the larger the query and key dimensions are, the more advantage FourierFormer has.
4.2 Image Classification on ImageNet
In the Imagenet classification task, we illustrates the benefits of Fourierformers different data modalities. We summarize our models' results in Table 2. Same in the language modeling experi- ment, for this image classification task, the Deit model equipped with FourierFormer significantly outperforms the baseline Deit dot-product transformer [79] in both top-1 and top-5 accuracy. This result suggests that the advantage FourierFormer over the baseline dot-product transformer holds across different data modalities.
4.3
UEA Time Series Classification
To evaluate Fourierformers on temporal sequences, we compare the accuracy of the our models and the baseline softmax transformers trained 10 datasets in the the UEA Time Series Classification Archive benchmark [5]. We summarize our results in Table 3. We observe show that Fourierformers outperforms softmax baselines in 7 out of 10 tasks and yields significantly better accuracy than the softmax transformer on average, showing the our models benefits when trained on temporal data.
8

---

Table 2. Top-1 1 and lop-S accuracy (%) of FourierFormer Deit vs. the baseline Deit with dot-product
attention. FourierFormer Deit outperforms the baseline in both top-1 and top-5 accuracy.
Mathod
Top-1 Ace
Top-5 Acc
Baseline DeiT
72.23
91.13
FourieFFrmmer DeiT
73.25
91.66
Table 3. The FourierFormer the baseline softmax transformer the UEA Time Series Classification Archive benchmark [5]. The FourierFormer outperforms the baseline. We also include the reported results from [95] and [93] (in parentheses) in addition
reproduced results. The experiment setups configurations for the baseline and our FourierFormer are the same as [93] (for the PEMS-SE, SellRegulationSCPP. UWaveGestureLibran datasets) and [95] (for other tasks).
Dataset/Model
Baseline softma
FourierFormer
ETHANOLCONCE CONCENTRATION
32.08 (33.70)
36.12
FACEDETECTION
68.70 (68.10)
68.71
HANDWRITING
32,08 (30,50)
31.68
HEARTBEAT
75.77 (77.60)
76.42
JAPANESEVOWELS
99.46 (99.40)
99.37
PEMS-SF
82.66 (82.10)
86.70
SELFREGULATIONSCP!!
91.46 (92.50)
91.70
SELFREGUL ATIONSCP2
54.72 (53,90)
55.37
SPOKENARABICDIGN
99.33 (99,30)
99.00
UWAVEGESTURELIDRARY
84.45 (85.60)
86.66
ACCURACY
72.07 (72.27)
73.17
Table 4. The decision FourierFormer vs. the baseline decision transformer [12] the continuous control tasks from D4RL benchmark [29]. The decision FourierFormer yields significantly better results than the baseline decision transformer on out of tasks and average across tasks, Each experiment result is averaged over 5 runs with different random seeds. also include the reported results from [93] (in parentheses) in addition to our reproduced results.
Environment/Mdel
Baseline decision transformer
Decision FourierFormer
MEDIUM-EXFEE
HALFCHEETAH
91.03 (83.80)
92,27
HOPPER
110.30 (104.40)
111.10
WALKER
108.70 (107.70)
108.90
MEDIUM- SERHUMM-RPLAY
HALFCHEETAR
35.31 (34.6)
38.47
HOPPER
85.61 (79.70)
89,70
WALKER
66.11 (62.90)
63.19
MEDIUM
HALFCHEETAH
42.28 (42.40)
42.38
HOPPER
61.47 (64.20)
64.77
WALKER
68.68 (70.60)
70.42
AvG REWARD
74.39 (72.20)
75.69
4.4 Reinforcement learning on the D4RL benchmark
We also examine the performance of our Fourierformers in reinforcement learning. In Table 4, we verify the advantage of decision FourierFormer over the baseline decision transformer [12] on the continuous control tasks from the D4RL. benchmark [29]. The decision FourierFormer is the decision transformer with the Fourier attention instead of the softmax attention. On this benchmark, decision FourierFormer significantly outperforms the baseline decision transformer on 8 out of 9 tasks and average across tasks. Each experiment result averaged over 5 runs with different random seeds. We follow the architecture and training configuration from [93].
4.5 Machine Translation on IWSLT" 14 De-En
We demonstrate the performance of Fourierformer on the IWSLT' 14 De-En [10] neural machine trans- lation task, which has different inputs' the sequence lengths. Table shows that the FourierFormer achieves better BLUE scores than the softmax baseline.
4.6 FourierFormer Helps Reducing Head Redundancy
To study the diversity between attention heads, given the model trained for the WikiText- language modeling task, we compute the average L2 distance between heads in each layer. We show the layer-average mean and variance of distances between heads in Table 6. Results in Table 6 shows

---

Table S. The FourierFormer vs, the baseline softmax transformer on the IWSLT" 14 De-En machine translation benchmark [10]. The FourierFormer outperforms the bascline.
Method
BLEU score
Baseline sofinax
34.42
FourierFormer
34.68
Table 6. Layer-average mean and standard deviation of L2 distances between heads of FourierFormer versus the baseline transformer with dot-product attention trained for the Wiki'Text-10% language modeling task. FourierFormer has greater L2 distance between hcads than the baseline and thus captures more diverse attention pattern..
Method
Mean
Variance
Baseline dot-product
6.20 1. 2.30
2.30
FourierFormer
7.45 + 2.50
7.37 2.44
that FourierFormer obtains greater La distance between attention heads than the baseline transformer with the dot-proe not-product attention and thus helps reduce the head redundancy. Note that we use the small configuration as specified in Section 4. I for both models.
Related Work
Interpretation of Attention Mechanism in Transformers Recent works have tried to gain an understanding of transformer's attention from different perspectives. [80] considers attention as applying kernel smoother over the inputs. Extending this kernel approach, [35, 15, 52, 89, 54] linearize the softmax kernel in dot-product attention and propose family of efficient transformers with linear computational and memory complexity. [9] then shows that these linear transformers are comparable to Cetrov-Galerkin projection [64], suggesting that the softmax normalization in the dot-product attention is sufficient but not necessary. Other works provide an understanding of attention in transformers via ordinary/partial differential equation include [45, 69]. In addition, [51, 75, 30, 96, 53] relate attentions in transformers to a Gaussian mixture models. Several works also connect the attention mechanism to graph-structured learning and message passing in graphical models 190, 72, 39]. Our work focuses on deriving the connection between self-attention and nonparametric kernel regression and exploring better regression estimator, such as the generalized Fourier nonparametric regression estimator, to improve the performance transformers.
Redundancy in Transformers [19, 47, 25] show that neurons and attention heads in the pre- veetrrined transformer are redundant and can be removed when applied on downstream task. By studying the contextualized embeddings in pre- pre-trained networks, it has been demonstrated that the learned representations from these redundant models are highly anisotropic [49, 26). Furthermore, [70, 74, 86, 68] employ knowledge distillation and sparse approximation to enhance the efficiency of transformers. Our FourierFormer is complementary to these methods and can be combined with them.
Concluding Remarks
In this paper, we establish the correspondence between the nonparametric kernel regression and the self-attention in transformer. We then develop the generalized Fourier integral estimators and propose the FourierFormer, novel class of transformers that use the generalized Fourier integral estimators to construct their attentions for efficiently capturing the correlations between features in the query and key vectors. We theoretically prove the approximation guarantees of the generalized Fourier integral estimators and empirically validate the advantage of FourierFormer over the baseline transformer with the dot-product attention in terms of accuracy and head redundancy reduction. It is interesting to incorporate robust. kernels into the nonparametric regression framework of FourierFormer to enhance the robustness of the model under data perturbation and adversarial attacks. limitation of FourierFormer is that it still has the same quadratic computational and memory complexity as the baseline transformer with the dot-product attention. We leave the development of the linear version of FourierFormer that achieves linear computational and memory complexity as future work. It is worth noting that there no potential negative societal impacts of FourierFormer.
A Acknowledgements
This material is based on research sponsored by the AFOSR MURI 1199550018-1051111 the ONR grant N00014-20-1-2000 the MURI N00014-20-1-2781 and the NSF under Grant# 2030859 to the Computing Research Association for the CIFellows Project (CIF2020-UCIAA-3) NH acknowledges support from the NSF IFML 2019844 and the NSF AI Institute for Foundations of Machine Learning.
10

---

References
[1] Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 3159-3166, 2019.
[2] Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pages 291-301 PMLR, 2019.
[3] Anurag Amab, Mostafa Dehghami, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid. Vivit: A video vision transformer. In 2021 IEEE/CVF International Conference Computer Vision (ICCV), pages 6816-6826, 2021.
[4] Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. In International Conference on Learning Representations, 2019.
[5] Anthony Bagnall, Hoang Anh Dau, Jason Lines, Michael Flymn, James Large, Aaron Bostrom, Paul Southam, and Eamonn Keogh. The uea multivariate time series classification archive, 2018. arXiv preprint 1xXiv:8111.000 2018.
[6] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: 1409.0473, 2014.
[7] S. Bochner. Lectures on Fourier Integrals. Princeton University Press, 1959.
[8] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[9] Shuhao Cao. Choose a transformer: Fourier or galerkin. Advances in Neural Information Processing Systems, 34, 2021.
[10] Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico. Report on the 1thh iwslt evaluation campaign, iwslt 2014. Proceedings of the International Workshop on Spoken Language Translation, Hanoi, Vietnam, volume 57, 2014.
[11] J.E. Chacón and T. Duong. Multivariate Kernel Smoothing and its Applications. CRC Press, 2018.
[12] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling, Advances in neural information processing systems, 14:15004-15097,
2021.
[13] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 10509, 2019.
[14] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 1724-1734, Doha, Qatar, October 2014. Association for Computational Linguistics.
[15] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song. Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
[16] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pages 854-863, PMLR, 2017.

---

[17] Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? an analysis of BERT's attention. In Proceedings of the 2019 ACL Workshop BlackboxNIP: Analyzing and Interpreting Neural Networks for NLP, pages 276-286, Florence, Italy, August 2019, Association for Computational Linguisties.
[18] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe V Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.02860 2019.
[19] Fahim Dalvi, Hassan Sajjad, Nadir Durrani, and Yonatan Belinkov. Analyzing redundancy in pretrained transformer models. arXiv preprint arXiv:2004.04010 2020.
[20] Kathryn Bullock Davis, Mean square error properties of density estimates. The Annals of Statistics, 3(4):1025-10300 1975.
[21] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. In International Conference Learning Representations, 2019.
[22] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pages 248-255. Icce, 2009.
[23] 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.
[24] 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.
[25] Nadir Durrani, Hassan Sajjad, Fahim Dalvi, and Yonatan Belinkov. Analyzing individual neurons in pre-trained language models. arXiv preprint arXiv:2010.02695, 2020.
[26] Kawin Ethayarajh. How contextual are contextualized word representations? comparing the geometry of bert, elmo, and gpt-2 embeddings. arXiv preprint arXiv:1909.00512, 2019.
[27] Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li, Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer. Multiscale vision transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6824-6835, 2021.
[28] Fan. On the optimal rates of convergence for nomparametric deconvolution problems. Annals of Statistics, 19(3): 1257-11222 1991.
[29] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint trXiv:2004.07219. 2020.
[30] Prasad Gabbur, Manjot Bilkhu, and Javier Movellan. Probabilistic attention for interactive segmentation. Advances in Neural Information Processing Systems, 34, 2021.
[31] Meng-Hao Guo, Jun- MuonXiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu. Pct: Point cloud transformer. Computational Visual Media, 1(2):187-199 2021.
[32] John Hewitt and Percy Liang. Designing and interpreting probes with control tasks. In Proceed- ings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLA) pages 2733-2743, Hong Kong, China, November 2019. Association for Computational Linguistics.
[33] N. Ho and S.G. Walker. Multivariate smoothing via the Fourier integral theorem and Fourier kemel.. Arxiv preprint Arxiv:2012.14482, 2021.
12

---

[34] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger. Kathryn Tunyasuvunakool, Russ Bates, Augustin Zídek. Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-88) 2021.
[35] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156-5165. PMLR, 2020.
[36] Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. ACM Computing Surveys (CSUR), 2021.
[37] Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention In International Conference on Machine Learning, pages 5571- PMLR, 2021.
[38] Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. Structured attention networks. arXiv preprint arXiv: 1ww..10028.0.... 2017.
[39] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létoumeau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34, 2021.
[40] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. survey of transformers. arXiv preprint arXiv:2106. 0455444444 2021.
[41] Zhouhan Lin, Minwei Feng, Cícero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding. CoRR, abs/ 100.01033,,,30, 2017.
[42] Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1907: 1169, 2019.
[43] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10012-10022, 2021.
[44] Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu. Video swin transformer. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2022.
[45] Yiping Lu, Zhuohan Li, Di He, Zhiqing Sun, Bin Dong, Tao Qin, Liwei Wang, and Tie- Yan Liu. Understanding and improving transformer from a multi-particle dynamic system point of view. arXiv preprint arXiv: 0226022 2019.
[46] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[47] Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[48] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 2018.
[49] Jiaqi Mu and Pramod Viswanath. All-but-the-op:: Simple and effective postprocessing for word representations. In International Conference on Learning Representations, 2018.
[50] E.A. Nadaraya. On estimating regression. Theory of Probability and its Applications, 9:141-142,
1964.
[51] Tam M Nguyen, Tan M Nguyen, Dung D Le, Duy-Khuong Nguyen, Viet-Anh Tran, Richard G Baraniuk, Nhat Ho, and Stanley Osher. Improving transformers with probabilistic attention keys. In International Conference Machine Learning, pages 16595-16621. PMLR, 2022.
13

---

[52] Tan M Nguyen, Richard Baraniuk, Robert Kirby, Stanley Osher, and Bao Wang. Momentum transformer: Closing the performance gap between self-attention and its linearization. In Mathematical and Scientific Machine Learning, pages 189-204. PMLR, 2022.
[53] Tan M Nguyen, Tam Nguyen, Hai Do, Khai Nguyen, Vishwanath Saragadam, Minh Pham, Duy Khuong Nguyen, Nhat Ho, and Stanley J Osher. Improving transformer with an admixture of attention heads. In Advances in neural information processing systems, 2022.
[54] Tan M Nguyen, Vai Suliafu, Stanley Osher, Long Chen, and Bao Wang. Fmmformer: Efficient and flexible transformer via decomposed near-field and far-field attention. In Advances in neural information processing systems, volume 34, pages 29449-29466 2021.
[55] Kishore Papineni, Salim Roukos, Todd Ward, and Wei Wiigiing Zhu. Bleu: a method for automatic evaluation of machine translation. pages 311-318, 2002.
[56] Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model for natural language inference. In Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, pages 2249-2255, Austin, Texas, November 2016. Association for Computational Linguistics.
[57] E. Parzen. On estimation of a probability density function and mode. Annals of Mathematical Statistics, 33:1065-1076, 1962.
[58] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32. pages 8024 8035. Curran Associates, Inc., 2019.
[59] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning. pages 8748 8763. PMLR, 2021.
[60] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. OpenAl report, 2018
[61] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 188):9 2019.
[62] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140): 66, 2020.
[63] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pages 8821-8831, PMLR, 2021.
[64] IN Reddy, An introduction to the finite element method, volume 1221. McGraw-Hill New York, 2004.
[65] Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C L'arrence Zitnick, Jerry Ma, et al. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences. Proceedings of the National Academy of Sciences, 118(15), 2021.
[66] M. Rosenblatt. Remarks some nonparametric estimates of density function. Annals of Mathematical Statistics, 27:832-837, 887, 1956.
[67] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211-255) 2015.
14

---

[68] Hassan Sajjad, Fahim Dalvi, Nadir Durrani, and Preslav Nakov. Poor man's bert: Smaller and faster transformer models. arXiv e-prints, pages arXiv-2004, 2020.
[69] Michael E Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transform- ers with doubly stochastic attention. In International Conference on Artificial Intelligence and Statistics, pages 3515-3530. PMLR, 2022.
[70] Victor Sanh, Lysandre Debut, Julien Chaumond. and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:191000110,, 2019.
[71] Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers secretly fast weight programmers. In International Conference on Machine Learning, pages 9355-9366. PMLR, 2021.
[72] 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 2 (Short Papers), pages 464 468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
[73] J.G. Staniswalis, K. Messer, and D.R. Finston. Kernel estimators for multivariate regression. Journal of Nonparametric Statistics, 1:103-121, 1993.
[74] Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for bert model compression. arXiv preprint arXiv:1908. 0930000099355000 2019.
[75] Binh Tang and David S. Matteson. Probabilistic transformer for time series analysis. In
A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[76] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. arXiv preprint arXiv:2009.06732. 2020.
[77] Ian Tenney, Dipanjan Das, and Ellie Pavlick. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4593-4601, Florence, Italy, July 2019, Association for Computational Linguistics.
[78] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pages 10347-10357. PMLR, 2021.
[79] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pages 10347-10357. PMLR, 2021.
Massa, Alexandre Sablayrolles, and
[80] Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: An unified understanding for transformer's s attention via the lens of kernel. In Proceedings of the 2019 Conference on Empirical Methods Natural Language Processing and the 9th International Joint Conference on Natural Language Process- ing (EMNLP-IJCNLP), pages 4344-4353, Hong Kong, China, November 2019, Association for Computational Linguistics.
[81] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. Advances in neural information processing systems, 31, 2018
[82] A. Tsybakov. Introduction Nonparametric Estimation. Springer, 2009.
[83] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages
2017.
15

---

[84] Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in a transformer language model. Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpret- ing Neural Networks for NLP, pages 63-76, Florence, Italy, August 2019. Association for Computational Linguisties.
[85] Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing mullti-head self-attention. Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5797-5808, Florence, Italy, July 2019, Association for Computational Linguistics.
[86] Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi- self-attention: Specialized heads do the heavy lifting, the rest can be pruned. arXiv preprint arXiv:1905.0941 2019.
[87] M.P. Wand. Error analysis for general multivariate kernel estimators. Journal of Nonparametric Statistics, 2:1-15, 1992.
[88] M.P. Wand and M.C. Jones. Comparison of smoothing parameterizzatons in bivariate kernel density estimation. Journal of the American Statistical Association, 88:520-528, 1993.
[89] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attentin with linear complexity. arXiv preprint arXiv:2006.04768. 2020.
[90] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7794-7803, 2018
[91] L. Wasserman. All of Nonparametric Statisties. Springer, 2006.
[92] N. Wiener. The Fourier Integral and Certain of its Applications. Cambridge University Press, 1933.
[93] Haixu Wu, Jialong Wu, Jichui Xu, Jianmin Wang, and Mingsheng Long. Flowformer: Lineariz- ing transformers with conservation flows. In International Conference on Machine Learning, 2022.
[94] Zhilin Yang, Zihang Dai, Yiming Yang. Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint arXiv:1906.088: 08237, 2019.
[95] George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Fickhoff. A wransoormr-bbaet framework for multivariate time series representation learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 21 14 242244 2021.
[96] Shaolei Zhang and Yang Feng. Modeling concentrated cross-attention for neural machine translation with Gaussian mixture model. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 1401-1411, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
[97] Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 16259- 16268, 2021.
16

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
17


Reviews:
[{"review_id": "iP8DN9c-dUc", "reviewer": "Reviewer_Ky7B", "summary": "The authors demonstrate the FourierFormer, a new class of transformers in which the novel generalized Fourier integral kernels replace the dot-product kernels. The FourierFormer can capture correlations between query features and key self-attention vectors. The authors empirically corroborate the advantages of FourierFormers over the baseline transformers in various practical applications, including language modeling and image classification.", "questions": "In the paper, the authors say ‘However, equations (1) and (2) imply that the dot-product attention assumes the features (qi1, . . . , qiD) in qi, as well as the features (kj1, . . . , qjD) in kj , are independent’. This description also implies that v is not included in the consideration of the correlation. However, even it's straightforward to consider q, k as independent variables and v as dependent variables, in my opinion, q, k, and v don’t have a clear statistical relationship in Transformer, partially due to its poor interpretability. Hence, according to the author's idea, v may also be part of considering the correlation.", "limitations": "Although the authors have given detailed proof mathematically, due to the poor interpretability of the Transformer itself, I still need to see more experimental results to agree with their point of view. The current experimental results are insufficient and not persuasive.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe ideas that the authors put forward are novel, and the mathematical arguments are complete and ingenious.\nWeaknesses: \nThe experiments in this paper are insufficient and, therefore, not convincing enough to demonstrate the effectiveness of the FourierFormer. The experiment only involves two basic tasks based on WikiText-103 and ImageNet.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MI88u5xmumB", "reviewer": "Reviewer_XT54", "summary": "This paper proposes an alternative to softmax attention using the sinc function. The authors were well-motivated using the sinc function from the Fourier integral estimator and provided theoretical support for approximation error. They have done experiments on two datasets showing improvement over softmax attention.", "questions": "1. What is the connection and differences between the proposed sinc function-based attention and the Fnet [1], which uses Fourier transform instead of softmax attention?\n2. Eq. 6. is derived upon considering only $\\mathbf{v}$ and $\\mathbf{k}$. How is it justified to replace $\\mathbf{k}$ with $\\mathbf{q}$ in line 119?\n3. What was the rationale and practical reason to consider $\\mathbf{k}_j$ s are i.i.d? In practice, when they went through an MLP, the channels became dependent on each other.\n\n[1] Lee-Thorp, James, et al. \"Fnet: Mixing tokens with Fourier transforms.\" arXiv preprint arXiv:2105.03824 (2021).\n", "limitations": "Authors have not adequately commented on the known limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is a pleasant read and clear to understand.\n2. The established connection between non-parametric kernel density estimator and self-attention.\n3. The authors have provided well-motivated intuition for their proposed approach.\n4. Related work has been moderately covered.\n5. The evaluation is convincing to show the benefit of sinc-based attention.\n\nWeaknesses:\n1. The authors only experimented with one choice of $\\phi$. It would be great to see what other suitable candidate of $\\phi$ is possible.\n2. How do they determine the value of $R$? Is it dataset-specific?\n3. There are no quantitative results on the runtime of the proposed attention mechanism.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IyfSls5q_P_", "reviewer": "Reviewer_MHeF", "summary": "In this paper, the authors provide a new perspective to interpret the self-attention mechanism in Transformers. In particular, with the assumption that the query and key vectors are normalized, the self-attention mechanism coincides with the well-known Nonparametric Kernel Regression with kernel density estimation. Motivated by this, the authors instead use the Generalized Fourier Integral Theorem to build more powerful estimators for capturing the interaction between features in different dimensions. Experiments on some benchmarks are conducted.", "questions": "See the issues in the Strength And Weaknesses. If the authors could address these issues, I would like to increase my scores accordingly.", "limitations": "No negative societal impact", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n- The interpretation of seeing the self-attention mechanism as using the isotropic Gaussian kernels for kernel density estimation and nonparametric regression estimation seems to be novel, which provides a new perspective to the community to understand the behavior of self-attention.\n- The motivation seems to be reasonable to use the generalized Fourier Integral Theorem to capture the feature interaction instead of using the multivariate Gaussian kernels with proper covariance matrices.\n- The theoretical analysis is thorough, including approximation error of the generalized Fourier density estimator (Theorem 1) and the generalized Fourier nonparametric regression estimator (Theorem 2). \n\n**Weaknesses**\n- **Regarding the background**: the authors should consider adding a preliminary section to introduce the background knowledge on the nonparametric kernel regression, kernel density estimation, and the generalized Fourier Integral theorem, which could help the readers easily follow the derivation of Section 2 and understand the motivation to use the Fourier Integral theorem as a guide to developing a new self-attention mechanism.\n- **Regarding the experimental evaluation**: the issues are three-fold. 1) since the authors provide an analysis of the approximation error between estimators and true functions (Theorem 1 and 2), it is informative to provide an empirical evaluation of these quantities on real data as further verification. 2)  The experiments should be more comprehensive and general. For both the language modeling task and image classification task, the model size is limited and the baselines are restrictive. 3) Since the FourierFormer need customized operators for implementation, the authors should also provide the memory/time cost profiling compared to popular Transformer architectures. Based on these issues, the efficiency and effectiveness of the FourierFormer are doubtful.\n\n-------After Rebuttal-------\nThank authors for the detailed response. Most of my concerns have been addressed. I have updated my scores to 6.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3uW8ovaX2zR", "reviewer": "Reviewer_WPHc", "summary": "This paper proposes the FourierFormer, in which the dot-product kernels are replaced by the generalized Fourier integral kernels. Unlike the dot-product kernels, where we need to choose a good covariance matrix to capture the dependency of the features of data, the generalized Fourier integral kernels can automatically capture such dependency and remove the need to tune the covariance matrix. This paper theoretically prove that the proposed Fourier integral kernels can efficiently approximate key and query distributions and verify this point through experiments on two transformer-based tasks.", "questions": "1. In line 144, the subsection title is “(Generalized) Fourier Integral Theorems”. Why do authors bracket the word “generalized” ？\n", "limitations": "The paper didn't address the limitation and potential negative societal impact of the work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1.This paper introduces a new angle to interpret transformer and its key module. This work provides a nonparametric regression interpretation to study self-attention in transformers and formulate self-attention from the viewpoint of kernel regression.\n2.This work adopts the generalized Fourier integral estimators to replace the traditional dot-product self-attention and provide theoretical guarantees for the estimator.\n3.Overall, the paper is well organized and technically sound. The experimental results on multiple transformer-based tasks verify the efficiency of the proposed Fourier Former.\n\nWeaknesses\n1.The derivation process and the presentation need to be improved. Some important symbol annotations or explanation is missing during the algorithm description, which make readers hard to follow the derivation process. For example, in the equation (9), some important symbol annotations are missing, e.g. ‘s’, ‘R’. It is difficult for readers to catch up the derivation, and the derivation of p(k) is crucial to the following interpretation.\n2.Some pitfalls in the paper: a) in line 100, “are i.i.d samples from.” ; b) in equation (6) one of /psi is written as /phi; c)line 185, the C’ in text are in wrong format.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept