On the Relationship between Self-Attention and Convolutional Layers
Authors: Jean-Baptiste Cordonnier
Andreas Loukas
Martin Jaggi
Venue:  (2020)
Keywords: self-attention
attention
transformers
convolution
CNN
image
expressivity
capacity

Abstract: Recent trends of incorporating attention mechanisms in vision have led researchers to reconsider the supremacy of convolutional layers as a primary building block. Beyond helping CNNs to handle long-range dependencies, Ramachandran et al. (2019) showed that attention can completely replace convolution and achieve state-of-the-art performance on vision tasks. This raises the question: do learned attention layers operate similarly to convolutional layers? This work provides evidence that attention layers can perform convolution and, indeed, they often learn to do so in practice. Specifically, we prove that a multi-head self-attention layer with sufficient number of heads is at least as expressive as any convolutional layer. Our numerical experiments then show that self-attention layers attend to pixel-grid patterns similarly to CNN layers, corroborating our analysis. Our code is publicly available.

Published as a conference paper at ICLR 2020
ON THE RELATIONSHIP BETWEEN SELF-ATTENTION AND CONVOLUTIONAL LAYERS
Jean-Baptiste Cordonnier, Andreas Loukas & Martin Jaggi École Polytechnique Fédérale de Lausanne (EPFL) ffirst. last 1aasst..as@eeepffff.e @epfl. .ch.....hhh.
ABSTRACT
Recent trends of incorporating attention mechanisms in vision have led re- searchers to reconsider the supremacy of convolutional layers as primary build- ing block. Beyond helping CNNs to handle long-range dependencies, Ramacchnn dran et al.] (2019) showed that attention can completely replace convolution and achieve state-of-the-art performance vision tasks. This raises the question: do learned attention layers operate similarly to convolutional layers? This work pro- vides evidence that attention layers can perform convolution and, indeed, they of- ten learn to do so in practice. Specifically, we prove that a multi-head self-attention layer with sufficient number of heads layer. Our numerical experiments then show that self-attention layers attend to pixel-grid patterns similarly to CNN layers, corroborating our analysis. Our code is publicly available
least as expressive as any convolutional
INTRODUCTION
Recent advances in Natural Language Processing (NLP) largely attributed to the rise of the trans- former (Vaswani et al. 2017). Pre-trained to solve an unsupervised task on large corpora text, transformer-bant architectures, such as GPT-2 (Radford al. 2018). BERT (Devlin et al. 2018) and Transformer-XL. (Dai et 2019), seem to possess the capacity to learn the underlying structure of text and, consequence, learn representations that generalize across tasks. The key differ- ence between transformers and previous methods, such as recurrent neural networks (Hochreiter & Schmidhuber 1997) and convolutional neural networks (CNN), is that the former can simultane- ously attend to every word of their input sequence. This is made possible thanks to the attention mechanism Sachanismm-rrgginallly introduced in Neural Machine Translation to better handle long-range de- pendencies (Bahdanau al. 2015). With self-attention in particular, the similarity of two words in a sequence is captured by an attention score measuring the distance of their representations. The representation of each word is then updated based on those words whose attention score is highest.
Inspired by its capacity to learn meaningful inter deterddependsncess between words, researchers have recently considered utilizing self-attention in vision tasks. Self-attention attention (Hu et al. 2018) or non-local relationships across the image (Wang et al. 2018). More recently. Bello et al. (20T9) augmented CNNs by replacing some convolu- tional layers with self-attention layers, leading to improvements on image classification and object detection tasks. Interestingly, Ramachandran art results are reached when attention and convolutional features are combined, under same com- putation and model size constraints, self-attention-onf architectures also reach competitive image classification accuracy.
first added to CNN
by either using channel-
al. (2019) noticed that, even though state-of-the
These findings raise the question, do self-attention layers process images a similar manner to convolutional layers? From theoretical perspective, one could argue that transfomers have the capacity to simulate any funetion-includiin a CNN. Indeed, Pérez layer attention-batn based architecture with additive positional encodings is Turing complete under some strong theoretical assumptions, such as unbounded precision arithmetic. Unfortunately, universality results do not reveal how machine solves a task, only that it has the capacity to do so. Thus, the question of how self-attention layers actually process images remains open.
Inéez et al. (2019) showed that a multi-
CCode: github. githibb.com/eppmm//ttteeee
Wehsite; wlf.l.ggithiiil .ithhb.. i /aatteentt inn-cnn

---

Published as a conference paper at ICLR 2020
Contributions. In this work, put forth theoretical and empirical evidence that self-attention layers can (and do) learn to behave similar to convolutional layers:
From theoretical perspective, we provide constructive proof showing that self-attention layers can express any convolutional layers.
Specifically, we show that single multi-head self-attention layer using relative positional encoding can be re- re-parametrized to express any convolutional layer.
II. Our experiments show that the first few layers of attention-only architectures (Ramachan- dran et al. 2019) do learn to attend grid-like pattern around each query pixel, similar to our theoretical construction.
Strikingly, this behavior is confirmed both for our quadratic encoding, but also for relative encoding that is learned. Our results seem to suggest that localized convolution is the right inductive bias for the first few layers of image classifying network. We provide an interactive website to explore how self-attention exploits localized position- based attention in lower layers and content- based attention in deeper layers. For reproducibility purposes, our code is publicly available.
BACKGROUND ON ATTENTION MECHANISMS FOR VISION
We here recall the mathematical formulation of self-attention layers and emphasize the role of posi- tional encodings.
2.1 THE MULTI-HEAM SELF-ATTENTION LAYER
Let X T be an input matrix consisting of T tokens in of Din dimensions each. While in
NLP each token corresponds to a word in a sentence, the same formalism can be applied to any sequence of T' discrete objects, e.g. pixels. A self-attention layer maps any query token t e [T]
from D to D dimensions as follows:
Self-Attention X):: := softmax (Ac.) X
(1)
where we refer to the elements of the T T matrix
A XW gry W X
(2)
as attention scores and the softmax outpu attention probabilities. The layer is parametrized by a query matrix Wary E DeD,, a key matrix Wkey E R D2 and a value matrix What e PuxD For simplicity, we exclude any residual connections, batch normalization and constant factors.
key property of the self-attention model described above that it equivariant to reordering, that is, it gives the same output independently of how the T input tokens are shuffled. This is problematic for cases we expect the order of things to matter. To alleviate the limitation, a positional encoding is learned for each token in the sequence (or pixel in an image), and added the representation of the token itself before applying self-attention
A (X P)W W XX + P)T,
(3)
where P E T contains the embedding vectors for each position. More generally, P may be substituted by any function that returns a vector representation of the position.
It has been found beneficial in practice replicate this self- atff-attention mechanism into multiple heads, each being able to focus on different parts of the input by using different query, key and value matrices. In multi-head self-attention, the output of the N₂ heads of output dimension Dj, concatenated and projected to dimension D as follows:
MHSA (X) == concal [Sell-Attemtonn, (X) Wonr + bou kE[N,]
(4)
and two new parameters are introduced: the projection matrix W Wa E Nr Den and a bias term bont E R8 D.v.
lepfml foffml.githee softmax (Ar.), = (x,(A.,x)/ E, exp(At.))
2

---

Published as a conference paper at ICLR 2020
2.2 ATTENTION FOR IMAGES
Convolutional layers are the de facto choice for building neural networks that operate on images.
We recall that, given image tensor X IR xxxD= of width W, height H and D,, channels, the output of a convolutional layer for pixel (i, is given by
Conv (X) iige =
X4+61 W da.i, + b,
(5)
(
where W is the K x K Din x Dour weight tensor
Rav is the bias vector and the set
K
K
x 2
2
2
contains all possible shifts appearing when convolving the image with K K kernel.
In the following, we review how self-attention can adapted from ID sequences to images.
With images, rather than tokens, we have query and key pixels q, & E [W] [H]. Accordingly, the input is tensor of dimension W x Din and each attention score associates a query and key pixel.
To keep the formulas consistent with the ID case, we abuse notation and slice tensors by using a 2D index vector: if p (i,j). write Xp.: and Ap, to mean X, and Auja. respectively. With this notation in place, the multi-head self attention layer output at pixel q can be expressed as follows:
Self-Autention g)
Σ k
softmax (Aq:) X Wont
and accordingly for the multi-heas case.
2.3 POSITIONAL ENCODING FOR IMAGES
There are two types of positional encoding that has been used in transformer- based architectures: the absolute and relative encoding (see also Table 3 in the Appendix).
With absolute encodings, a (fixed or learned) vector Pp.: is assigned to each pixel p. The computa- tion of the attention scores
in eq.
then be decomposed as follows:
abs q.k
(Xq:: Pa ary W
(Xk. PA.))
-x Wary
Key k.: + Xg. War W.
PT. k. + P W X + Pq.. Wan, W Pk::
(7)
where q and & correspond to the query and key pixels, respectively.
The relative positional encoding was introduced by Dai et al. (2019). The main idea is only consider the position difference between the query pixel (pixel we compute the representation of) and the key pixel (pixel we attend) instead of the absolute position of the key pixel:
A Agel
X
Wey X X W q. @ry
W
ay W T5 u." W X o' Wkey rs
In this manner, the attention scores only depend on the shift == k q. Above, the learnable vectors u and v are unique for each head, whereas for every shift 5 the relative positional encoding rs E RDr shared by all layers and heads. Moreover, now the key weights are split into two types: Whey pertain to the input and Wey to the relative position of pixels.
3 SELF- ATTENTIOO AS A CONVOLUTIONAL LAYER
This section derives sufficient conditions such that a multi-head self-attention layer can simulate a convolutional layer. Our main result is the following:
Theorem multi-head self-attention layer with N₁. heads of dimension Dr. output dimen-
sion Dow and relative positional encoding of dimension Dp 2 3 can express any convolutional layer of kernel size /Nn VN, and min Dr, Dent) output channels.
"To simplify notation, we index the first two dimensions of the tensor from -KK/2] to LK/2]-
3

---

Published as a conference paper at ICLR 2020
The theorem is proven constructively by selecting the parameters of the multi-head self-attention layer so that the latter acts like a convolutional layer. In the proposed construction, the attention scores of each self-attention head should attend to different relative shift within the set A {-LK/2].-
]2 of all pixel shifts in a K x K kernel. The exact condition can be found in the statement of Lemma
Then, Lemma 2 shows that the aforementioned condition is satisfied for the relative positional en- coding that refer the quadratic encoding:
(h) = aa (1, 241 -2A
(1))) T6: -1161,,81,00 W Way 0
Weey I
A (h) and (1) determine the center and width of attention of each head, respectively. On the other hand, ā (61, 62) is fixed and expresses the relative shift between query and key pixels.
The learned parameters A (h)
(A) (1)
important to stress that the above encoding not the only one for which the conditions of Lemma [ are satisfied. In fact, in our experiments, the relative encoding learned by the neural network also matched the conditions of the lemma (despite being different from the quadratic en- coding). Nevertheless, the encoding defined above is very efficient in terms of size, only D, 3 dimensions suffice to encode the relative position of pixels, while also reaching similar or better empirical performance (than the learned one).
The theorem covers the general convolution operator as defined in eq. (17). However, machine learning practitioners using differential programming frameworks (Paszke et al. 2017 Abadi al. 2013) might question if the theorem holds for hyper-parameters 2D convolutional layers:
Padding: a multi-head self-attention layer uses by default the "SAME" padding while a convolutional layer would decrease the image size by K pixels. The correct way to alleviate these boundary effects is to pad the imput image with K//2] zeros on each side. In this case, the cropped output MHSA and a convolutional layer are the same.
Stride: strided convolution be operation- with computational optimizations. Theorem [ is defined for stride 1, but fixed pooling layer could be appended the Self-Attention layer to simulate any stride.
convolution followed by fixed pooling
Dilation: multi-head self-attention layer can express any dilated convolution each head can attend a value at any pixel shift and form a (dilated) grid pattern.
Remark for the 1D case. Convolutional layers acting sequences commonly used in the lit- erature for text (Kim 2014), as well as audio (van den Oord et al. 2016) and time series (Franceschi al. 2019). Theorem [ can be straightforwardly extended show that multi-head self-attention with N₁. heads can also simulate ID convolutional layer with kernel of size K = N₁. with min Dr. Dout) output channels using a positional encoding of dimension D, > 2. Since we have not tested empirically if the preceding construction matches the behavior of ID self-attention in practice, we cannot claim that it actually learns convolve an input sequence- that has the capacity to do so.
PROOF OF MAIN THEOREM
The proof follows directly from Lemmas I and stated below:
Lemma 1, Consider a multi-head self-attention layer consisting of N₁. K2 heads, DT 2 D out and let f [Nx] + Ag x be bijective mapping of heads onto shifts. Further, suppose that for every head the following holds:
{1
f otherwise.
softmax (AAmmax(A))) (A
(10)
Then, for any convolutional layer with K x K kernel and Dent output channels, there exists (W(h) (W(h) JNe(Ns) such that MHSA(X) Conv X) for every X XHxD.
4

---

Published as a conference paper at ICLR 2020
Multi-Head Self-Attention Layer
Fy
X
MIIAA(X)
concatonna atte
8
A
pontionn A pepootong
Σ Ner #O
Fihtr matrices
Attention maps pixel
Figure I: Illustration a Multi- Head Self-Attention layer applied to a tensor image X. Each head attends pixel values around shift A (h) and learn filter matrix W(() computed for query pixel at position q.
We show attention maps
vol
Proof. Our first step will be rework the expression of the Multi-Head Self-Attention operator from equation (1) and equation 4 such that the effect of the multiple heads becomes more transparent:
MHSA(X) = bont
Σ
softmax A (h)
)
X w vol
Wour((
1)D, + 1: h:h +1]
(11)
RE(M)]
W())
Note that each head's value matrix W-(A) E Di and each block of the projection matrix W our val
of dimension Dr X Dour are learned. Assuming that Dr 2 Dowts we can replace each pair of matrices by a learned matrix (h)) for each head. We consider one output pixel of the multi-head self-attention
MHSA MHSA(X)q: x)::
Σ
Σ softmax A (1)) XK:
Wh() + bour
(12)
bE[NN]
Due the conditions of the Lemma, for the h-th attention head the attention probability is one when k f(h) and zero otherwise. The layer's output at pixel is thus equal to
MHSA(X)g
Σ AEIN
Xg-)(h), W (h)
bout
(13)
For K = VN. the above can be seen to be equivalent to a convolutional layer expressed in eq. 17 there is a one to one mapping (implied by map f) between the matrices (h(h) for h = [Nx] and the matrices W da for all k2) E [K]2.
Remark about Dr and Dout- It is frequent in transformer-basee architectures to set DA Dow/Nn, N,. hence Dr. < D In that case, (hh can be seen to be of rank D Dr, which does not suffice express every convolutional layer with D channels. Nevertheless, it can be seen that any Dj, out of Denr outputs of MHSA(X) can express the output of any convolutional layer with D2 output channels. To cover both cases, in the statement of the main theorem we assert that the output channels of the convolutional layer should be min Dn., D Dour). In practice, we advise to concatenate heads of dimension Dr = our instead of splitting the Doar dimensions among heads to have exact re- parametrization and no "unused" channels.
Lemma 2. There exists relative encoding scheme {rs E Pr 1887 with D, 3 and parame-
ters W When Wle, u with D, S Dr such that, for every A Ag there exists some vector (conditioned on A) yielding softmax( Ag:)) if k
A and zero, otherwise.
Proof. We show by construction the existence of a D, = 3 dimensional relative encoding scheme yielding the required attention probabilities.
5

---

Published as a conference paper at ICLR 2020
As the attention probabilities independent of the input tensor X, set Whe gry 0 which leaves only the last term of eq. (). Setting Wiey row padding), yields Ay.k v тs where
E IR DDD, to the identity matrix (with appropriate := = k Above, we have assumed that Dp 1 Dk
such that no information from rs is lost.
Now, suppose that we could write:
- -a Al2 +c)
(14)
for some constant c. In the above expression, the maximum attention score over Aq is -ac and is reached for Ag. with ô = A. On the other hand, the coefficient can be used to scale arbitrarily the difference between A and the other attention scores.
In this way, for d A, have
e =[|1--A11
lim softmax softmax(Aqq)e (q.)* = lim a->00
a-000
Ex kr e a(l +1)+))
-all--Ai!
lim 0-1000
E kc
1 lim Exyr / e e-alll q²) Al
and for 8 # A, the equation becomes lima- softmnx Agi)) = O, exactly as needed to satisfy the lemma statement.
What remains to prove that there exist v and (Ta3s for which eq.
14 holds. Expanding the 2, A +c) Now if we
RHS of the equation, we have -a 6 A 1 c) -a (|0| + ||
set v = a (1, 22 1, 1 2 and ra = (18) 5, 52) then
Aq.k 0 T -a 0112 24, 51 -22262) aa(10] - 2(6 A))
8- A =
which matches eq. 14 with - -|| || and the proof concluded.
Remark on the magnitude of a. The exact representation of one pixel requires a (or the matrices Wgry and Wir) be arbitrary large, despite the fact that the attention probabilities of all other pixels converge exponentially to 0 as a grows. Nevertheless, practical implementations always rely on finite precision arithmetic for which constant a suffices satisfy construction. For instance, since the smallest positive float32 32 scalar is approximately 10 setting a 46 would suffice obtain hard attention.
EXPERIMENTS
The aim of this section is to validate the applicability of our theoretical results which state that self-attention can perform convolution- and to examine whether self-attention layers in practice do actually learn to operate like convolutional layers when trained on standard image classification tasks. In particular, we study the relationship between self-attention and convolution with quadratic and learned relative positional encodings. We find that, for both cases, the attention probabilities learned tend respect the conditions of Lemma] supporting our hypothesis.
4.1 IMPLEMENTATION DETAILS
We study fully attentional model consisting of six been shown by Bello et al.] (2019) that combining attention features with convolutional features improves performance on Cifar- 100 and ImageNet, we do not focus on attaining state-of-the-ee performance. Nevertheless, to validate that our model learns a meaningful classifier, we compare to the standard ResNet18 (He et al., 2015) on the CIFAR-10 dataset (Krizhevsky et al.). In all experiments, we a 2 x 2 invertible down-sampling (Jacobsen al.) 2018) on the input to reduce the size of the image. As the size of the attention coefficient tensors (stored during forward) scales quadratically with the size of the input image, full attention cannot be applied to bigger images. The fixed size representation of the input image computed as the average pooling of the last layer representations and given a linear classifier.
self-attention layers. As has already

---

Published as a conference paper at ICLR 2020
0.9
Models
accuracy
of params
# of PLOPS
Tepaaconnoo
ResNet18
0.9.8
11.2M
1.18
SA quadratic emh.
0.938
12.1M
6.2R
SA leamed cmb.
0
12.3M
6.28
leamed emhh content
29.5M
0.7
30
300
150
200
250
300
Esoch
Figure 2: Test accuracy on CIFAR-10.
Table 1: Test accuracy on CIFAR- 10 and model sizes. SA stands for Self-Attention.
Epoch 0
Epoch 50
Epoch 100
Epoch 300
aao
Figure 3:
Centers of attention of each attention head (different colors) at layer 4 during the training with quadratic relative positional encoding. The central black square is the query pixel, whereas solid and dotted circles represent the 50% and 90% percentiles of each Gaussian, respectively.
We used the PyTorch library (Paszke et al. 2017) and based our implementation on PyTorch Trans- formers We release code on Github and weyper-parameten are listed in Table 2 (Appendix).
Remark on accuracy. To verify that our self-attention models perform reasonably well, we dis- play in Figure [ the evolution the test accuracy on CIFAR- 10 over the 300 epochs of training for our self-attention models against small ResNet (Table D. The ResNet is faster to converge, but we cannot ascertain whether this corresponds to an inherent property of the architecture or an artifact of the adopted optimization procedures. Our implementation could be optimized to exploit the locality of Gaussian attention probabilities and reduce significantly the number FLOPS. We observed that learned embeddings with content-based attention harder train probably due their increased number of parameters. We believe that the performance gap can be bridged to match the ResNet performance, but this is not the focus of this work.
4.2 QUADRATIC ENCODING
As first step, we aim to verify that, with the relative position encoding introduced in equation (9) attention layers learn to behave like convolutional layers. We train nine attention heads at each layer kernels used predominantly by the ResNet architecture. The center of
to be on par with the attention of each head is initialized to A (h) (0,0 212).
Figure 3 shows how the initial positions of the heads (different colors) at layer 4 changed during training. We can see that after optimization, the heads attend on specific pixel of the image forming grid around the query pixel. Our intuition that Self- Attention applied to images learns convolutional filters around the queried pixel is confirmed.
Figure 4 displays all attention head at each layer of the model at the end of the training. It can be seen that the first few layers the heads tend focus on local patterns (layers 1 and 2). while deeper layers (layers 3-6) also attend to larger patterns by positioning the center of attention further from the queried pixel position. We also include in the Appendix a plot of the attention positions for higher number of heads (N, 16). Figure 14 displays both local patterns similar to CNN and long range dependencies. Interestingly. attention heads do not overlap and seem to take an arrangement maximizing the coverage of the input space.
wtthhtt.cc///uugggaaaaa///tttttn formers gtttbbb.ccmm/eemm//ttttttttiinnt
7

---

Published as a conference paper at ICLR 2020
Layer
Layer 2
Layer 3
Layer
Layer
Loyer
aho
Figure 4: Centers of attention of each attention head (different colors) for the 6 self-attention layers using quadratie positional encoding. The central black square is the query pixel, whereas solid and dotted circles represent the 50% and 90% percentiles of each Gaussian, respectively.
4.3 LEARNED RELATIVE POSITIONAL ENCODING
We move on to study the positional encoding used in practice by fully-attentional models on images.
We implemented the 2D relative positional encoding scheme used by (Ramachandran et al. 2019 Bello et al. 2019) we learn pp./2 position encoding vector for each row and each column pixel shift. Hence, the relative positional encoding of key pixel at position & with a query pixel at posi- tion q is the concatenation of the row shift embedding ô and the column shift embedding 82 (where = k q). We chose Dp = Dow 400 in the experiment. We differ from their (unpublished) implementation in the following points: (i) do not convolution stem and ResNet bottlenecks for downsampling. but only a 2 x 2 invertible downsampling layer (Jacobsen et al.] (0018) at input, (ii) we use Da Dow instead of Dt. Pn//N, backed by our theory that the effective number of learned filters is min Da, Dowr).
At first, we discard the input data and compute the attention scores solely the last term of eq. (8) The attention probabilities of each head at each layer are displayed on Figure The figure confirms our hypothesis for the first two layers and partially for the third: even when left to learn the positional encoding scheme from randomly initialized vectors, certain self-attention heads (depicted on the left) learn to attend to individual pixels, closely matching the condition of Lemma and thus Theorem 1. At the same time, other heads pay attention to -yyomttllly-ymmmtiii but non-localized patterns, as well as to long-range pixel inter-dependencies.
We move on to a more realistic setting where the attention scores are computed using both positional and content-based attention (i.e., q Th h + q Tr in (Ramachandran et al. 2019)) which corresponds to a full-blown standalone self-attention model.
The attention probabilities of each head at each layer are displayed in Figure 6 We average the attention probabilities over batch of 100 test images to outline the focus of each head and remove the dependency on the input image. Our hypothesis is confirmed for some heads of layer and 3: when left to learn the encoding from the data, certain self-attention heads only exploit position- based attention to attend to distinct pixels at a fixed shift from the query pixel reproducing the receptive field of convolutional kernel. Other heads more content-based attention (see Figures to 10 in Appendix for non-averaged probabilities) leveraging the advantage of Self Self-Attention over CNN which does contradict our theory. In practice, was shown by [ello al. (2019) that combining CNN and self-attention features outperforms each taken separately. Our experiments shows that such combination learned when optimizing an unconstrained iilly-attentional model.
The similarity between convolution and multi-head self-attention is striking when the query pixel is slid over the image: the localized attention patterns visible Figure 6 follow the query pixel. This characteristic behavior materializes when comparing Figure 6 with the attention probabilities at different query pixel (see Figure 7 in Appendix). Attention patterns in layers 2 and 3 are not only localized but stand at constant shift from the query pixel, similarly to convolving the receptive field a convolutional kernel over an image. This phenomenon made evident on our interactive website This tool is designed to explore different components of attention for diverse images with or without content- content-based attention. We believe that it is a useful instrument to further understand how MHSA learns process images.
Tepfm1 gi thub. wechub.o/aattee io/attetiiionccc
8

---

Published as a conference paper at ICLR 2020
layer 1
layer 2
loger 3
layer
lager
layer
Figure 5: Attention probabilities each head (column) at each layer (row) using learned relative positional encoding without content-basee based attention. The central black square the query pixel. We reordered the heads for visualization and zoomed on the 7x7 pixels around the query pixel.
byger
laper
Sayer
Figure 6: Attention probabilities for a model with 6 layers (rows) and 9 heads (columns) using learned relative positional encoding and content-content based attention. Attention maps are aver- aged over 100 test images to display head behavior and remove the dependence on the input content. The black square is the query pixel. More examples are presented in Appendix A

---

Published as a conference paper at ICLR 2020
5 RELATED WORK
In this section, we review the known differences and similarities between CNNs and transformers.
The use of CNN networks for text-at word level (Gehring al., 2017) character level (Kim 2014)-is more seldom than transformers (or RNN). Transformers and convolutional models have been extensively compared empirically on tasks of Natural Language Processing and Neural Ma- chine Translation. It was observed that transformers have competitive advantage over convolu- tional model applied text (Vaswani et al.) 2017). is only recently that Bello et al.j (2019); Ramachandran et al. (2019) used transformers on images and showed that they achieve similar ac- curacy as ResNets. However, their comparison only covers performance and number of parameters and FLOPS but not expressive power.
Beyond performance and computational-com comparisons of transformers and CNN, the study of expressiveness of these architectures has focused on their ability to capture long-term dependencies at.. 2019). Another interesting line of research has demonstrated that transformers are Turing- complete (Dehghani et al., 2018 Pérez al.] (219)), which is an important theoretical result but is not informative for practitioners. To the best of our knowledge, we are the first to show that the class of functions expressed by a layer of self-attention encloses all convolutional filters.
The closest work in bridging the gap between attention and convolution is due to Andreoli (2019). They cast attention and convolution into unified framework leveraging tensor outer- product. In this framework, the receptive field of a convolution is represented by "basis" tensor A E R x xHx W For instance, the receptive field of a classical K K convolutional kernel would be encoded by AA.q. ( q = A} for A E A The author distinguishes this index-based convolution with content-based convolution where A is computed from the value of the input, e.g., using a key/query dot-product attention. Our work moves further and presents sufficient conditions for relative positional encoding injected into the input content (as done in prac- tice) to allow content-based convolution to express any undex-based convolution. We further show experimentally that such behavior is learned in practice.
CONCLUSION
We showed that self-attention layers applied images can express any convolutional layer (given sufficiently many heads) and that fully-attentional models learn to combine local behavior (similar to convolution) and global attention based on input content. More generally, fully-attentional mod- els seem to learn a generalization of CNNs where the kernel pattern is learned at the same time as the filters-simlla to deformable convolutions (Dai et al. 2017; Zampieri 2019). Interesting di- rections for future work include translating existing insights from the rich CNNs literature back to transformers on various data modalities, including images, text and time series.
ACKNOWLEDGMENTS
Jean-Baptiste Cordonnier is thankful to the Swiss Data Science Center (SDSC) for funding this work. Andreas Loukas was supported by the Swiss National Science Foundation (project "Deep Learning for Graph Structured Data", grant number PZ00P2 179981).
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Watten- berg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org.
Jean-Mare Andreoli. Convolution, attention and structure embedding. NeurlPS 2019 workshop on Graph Representation Learning, Dec 13, 2019, Vancouver, BC, Canada, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Irwan Bello, Barret Zoph, Ashish Vaswani, Jonathon Shlens, and Quoc V. Le. Attention Augmented Convolutional Networks. XXiv:1904.09923 [es), April 2019.
Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei. Deformable convolutional networks. CoRR, abs/1 0tts//773..2211 2017.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoc V. Le, and Ruslan Salakhut- dinov. Transformer-X XL: Attentive Language Models Beyond Fixed-Length Context. CoRR, abs/1901.002600 2019.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. CoRR, htss/1807.03819 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre- pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805, 2018.
Jvan-Yves Franceschi, Aymeric Dieuleveut, and Martin Jaggi. Unsupervised scalable representation learning for multivariate time series. In NeurIPS 2019, 2019.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional sequence sequence learning. CoRR, abs/1705.00112,, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CoRR, abs/1512.0033 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780, 1997.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excitation networks. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 7132-7141, 2018.
Jörn-Henrik Jacobsen, Amoll W.M. Smeulders, and Edouard Oyallon. i-revnet: Deep invertible networks. In International Conference on Learning Representations, 2018.
Yoon Kim. Convolutional neural networks for sentence classification. In Proceedings of the
2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1746- 1751, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v1/ D14-1181.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced re- search).
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Vito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
11

---

Published as a conference paper at ICLR 2020
Jorge Pérez, Javier Marinkovic, and Pablo Barceló. On the turing completeness of modern neural network architectures. CoRR, abs/1901.03429, 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. 2018.
Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jonathon Shlens. Stand-alone self-attention in vision models. CoRR, abs/1906.05509, 2019.
Aäron van den Oord, Sander Dicleman, Hciga Zen, Karen Simonyan, Oriol Vinyals, Alexander Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint arXiv:/609.083:
2016.
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.03762, 2017.
Xiaolong Wang, Ross B. Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pp. 7794-7803, 2018.
Zhilin Yang, Zihang Dai, Yiming Yang. Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoe V. Le. Xlnet: Generalized autoregressive pretraining for language understanding. CoRR, abs/1906.08237, 2019.
Luca Zampieri. Geometric deep learning for volumetric computational fluid dynamics. pp. 67, 2019.
12

---

Published as a conference paper at ICLR 2020
APPENDIX
A MORE EXAMPLES WITH CONTENT-BASED ATTENTION
We present more examples attention probabilities computed by self-attention model. Figure 7 shows average attention at different query pixel than Figure Figures too display attention for single images.
Figure 7: Attention probabilities for model with 6 layers (rows) and 9 heads (columns) using learned relative positional encoding and content-content attention. We present the average of 100 test images. The black square the query pixel.
Attention probabilities for model with 6 layers (rows) and 9 heads (columns) using learned relative positional encoding and content-content based attention. The query pixel (black square) is on the frog head.
Figure 8:
13

---

Published as a conference paper at ICLR 2020
Figure 9: Attention probabilities for a model with layers (rows) and heads (columns) using learned relative positional encoding and content-content based attention. The query pixel (black square) is on the horse head.
Attention probabilities for model with layers (rows) and 9 heads (columns) using learned relative positional encoding and content-content based attention. The query pixel (black square) on the building in the background.
Figure 10:
14

---

Published as a conference paper at ICLR 2020
B HYPER-PARAMETERS USED IN OUR EXPERIMENTS
Hyper-parameters
number of layers
6
number heads
9
hidden dimension
400
intermediate dimension
512
invertible pooling width
2
dropout probability
0.1
layer normalization epsilon
10-12
number epochs
300
batch size learning rate
100
0.1
weight decay
0.0001
momentum
0.9
cosine decay
v
linear warm up ratio
0.05
Table 2: Self-attention network parameters
C
POSITIONAL ENCODING REFERENCES
type of positional encoding
Model
relative
sinusoids
learned
quadratic
Vaswani ct 2017
Radford et al.
2018
Devlin et al. (0188)
Dai et al.
20 1
Yang et al.
2019
Bello et al. (019)
Ramachandran al. (0019)
Our work
Table Types of positional encoding used by transformers models applied to text (top) and images (bottom). When multiple encoding types have been tried, we report the one advised by the authors.
D GENERALIZED LEMMA 1
We present generalization of Lemma that replaces the necessity of hard attention (to single pixels) by a milder assumption: the attention probabilities should span the grid receptive field. The conditions of this Lemma are still satisfied by Lemma hence Theorem foolows.
Lemma 3. Consider multi-head self- attentito layer consisting of N 2 K² heads, Dí 2 Deut and let : [H] [W] [HW] be a pixel indexing. Then, for any convolutional layer with x K kernel and Den output channels, there exists (W(h) Jie[NN) and W our such that MHSA(X) = Conv(X) for every X &WWHHD, if and only if. for all q E [H] [W].
span(few(g+A) E HW A Ax)) C (pan((voct(softmmxx
A (1))) [N,]))
q.
the vectorization operator vect(-) flattens matrix into vector
15

---

Published as a conference paper at ICLR 2020
HW
HW
((((tt)
K²
NA
voct/softmart A.
veci(Wa....
vect(W
Eqq
Aq
D Dut
Den Dout
W
W-SA
V-SA
Factorization of the vectorized weight matrices Vroon and V used to compute the output at position q for an input image of dimension H x W. 9 the left: a convolution of kernel 2 x 2, on the right: self-attention with N₂. 5 heads. Din. 2, Dout 3 in both cases.
Figure 1I:
Proof. Our first step will be to rework the expression of the Multi-Head Self-Attention operator from equation (T) and equation 4 such that the effect of the multiple heads becomes more transparent:
MHSA(X) = b +
softmax A (h) X w-(h)
Wone (1h - D)D; + hDn +
(15)
vol
AE(NA]
W
Note that each head's value matrix W-(A) (h) of dimension Dr X Dowr are learned. Assuming that Dú 2 Dowr we can replace each pair of matrices by a learned matrix ( for each head. We consider one output pixel of the multi-head self-attention and drop the bias term for simplicity:
vol E Di.xD, and each block of the projection matrix Wo
MHSA(X)
Σ KE[NA]
Σ
(1) q.k
W(h) -Ex, X
Σ
(1) q.k
w(h)),
(16)
AE(N.)
WMM ER Pn Done
with (h) d. softmax (A (h) )..
A.. We rewrite the output of convolution at pixel g in the same manner:
Conv(X)
Σ W
Σ
Xk: 1 (1- W Wk-qii-
(17)
kE[N]
Woon ER Pin Dout
Equality between equations (6] and 117 holds for any input X if and only if the linear transfor-
mations for each pair of key/query pixels are equal, i.e. Weony = WSS
q. Vq. k. We vectorize the weight matrices into matrices of dimension D Dont x HW as Veoww = [vect (eeetyy 9. ][[[H]][[W]
and SAA [vect WSS ( Hence, to show that Conv MHSA(X) for all X,
must show that Va VSA for all
The matrix Veean has restricted support: only the columns associated with pixel shift A AK in the receptive field of pixel can be non-zero. This leads the factorization V comm E, displayed in Figure 11 where Wroony Doue. and Eg k XWW, HW Given an ordering of the shifts A E Ax indexed by j. set (Wawa)) )..j = vect (octlWa..)) and (Eg)j, = Eu(gtA). On the other hand, we decompose VSA. SA Ag with (WSS)
):,h h = vect vect(W(()) and (Ag)a.i (w)))))
(h)
The proof is concluded by showing that row EEq) C row row(AA) ) is necessary and sufficient condition for the existence of WSA such that any Vrow Wroom Eg can be written SASAA Ag.
Sufficient. Given that row Eg) S row (Aw)) there exists E IR x such that E, = 4 AAg and valid decomposition W/SA Woong which gives W/S Ag = VeORy
Necessary. Assume there exists x E WHW such that x E row Eg) and x & row(A,) and set x' to be a row of Vrauv Then, WASA A, + Veows for any SA and there no possible decomposition.
16

---

Published as a conference paper at ICLR 2020
E GENERALIZED QUADRATIC POSITIONAL ENCODING
We noticed the similarity of the attention probabilities in the quadratic positional encoding (See- tion 3) to isotropic bivariate Gaussian distributions with bounded support:
e -
softmax (Aq:)A
(18)
[ l 9) AIF
Building this observation, we further extended our attention mechanism to non-isotropic Gaus- sian distribution over pixel positions. Each head is parametrized by a center of attention A and a covariance matrix E to obtain the following attention scores,
Ag.k -- 1 A) = 3- -- ATE-'A
(19)
where, once more, 8= k - q. The last term can be discarded because the softmax is shift invariant and we rewrite the attention coefficient as dot product between the head target vector and the relative position encoding ra (consisting of the first and second order combinations of the shift in pixels 8):
1 v= 2 (), - - - Eg
-2 -
ET and rs = (ō1, 62 07, 6162)
Evaluation. We trained our model using this generalized quadratic relative position encoding. We were curious to see if, using the above encoding the self-attention model would learn to attend to non-isotropic groups of pixels- thus forming unseen patterns CNNs. Each head was parametrized by Á E R22 and 1-12 E 2x to ensure that the covariance matrix remained positive semi-definite. We initialized the center of attention to A (N) (0, 212) and Σ 1/2 + (O, 0.01 that initial attention probabilities were close to an isotropic Gaussian. Figure 12 shows that the network did learn non-isotropic attention probability patterns, especially in high layers. Nevertheless, the fact that we do not obtain any performance improvement seems to suggest that attention non-isotropy is not particularly helpful in practice- the quadratic positional encoding suffices.
Layer
Layer 2
Layer
Layer 4
Layer
Layer
Centers of attention of each attention head (different colors) for the 6 self- attf-attention layers using non-isotropic Gaussian parametrization. The central black square is the query pixel, whereas solid and dotted circles represent the 50% and 90% percentiles of each Gaussian, respectively.
Figure 12:
Pruning degenerated heads. Some non-isotropic attention heads attend on "non-intuitive" patches of pixels: either attending a very thin stripe of pixels, when Σ-1 was almost singular, or attending all pixels uniformly, when --1 was close to 0 (i.c. constant attention scores). We asked ourselves, are such attention patterns indeed useful for the model unused? To find out, we pruned all heads having largest eigen-values smaller than 10-5 or condition number (ratio of the biggest and smallest eigen-values) greater than 10a Specifically in model with 6-layer and 9-heads each, we pruned [2, 4, 1, 2, 6, 0] heads from the first to the last layer. This kernel anymore. As shown in yellow on fig. 2 this
these heads degenerated and d
means that these layers cannot express ablation initially hurts a bit the performance, probably due to off biases, but after a few epochs of continued training with smaller learning rate (divided by 10) the accuracy recovers its unprumed value. Hence, without sacrificing performance, we reduce the size of the parameters and the number of FLOPS by a fourth.
F INCREASING THE NUMBER OF HEADS
For completeness, also tested increasing the number of heads of our architecture from 9 to 16.
17

---

Published as a conference paper at ICLR 2020
1.0
0.9
Models
acturacy
params
of
RosNet18
0.938
11.2M
1.1B
0.8
SA quadratic emb.
0.938
12.1M
6.28
quadratic emb. gen.
0.934
12.1M
6.2B
quaddallc
quadratic gen. pruncd
SA quadraticc emb. gen.
leamed emb.
0.918
12.3M
6.2B
SA quadraticc emb, gen, pruned
SA leamed cmb. content
0.871
29.5M
15B
SA isammad cmb.
learned emb. condent-bawed atL
0.4
50
300
150
201
250
500
350
400
Epech
Figure 13: Evolution of test accuracy CIFAR- 10. Pruned model (yellow) is continued training of the non-isotropic model (orange).
Table 4: Number of parameters and accuracy on CIFAR-10 per model. SA stands for Self- Attention.
Centers of attention for 16 attention heads (different colors) for the self-attention layers using quadratic positional encoding. The central black square is the query pixel, whereas solid and dotted circles represent the 50% and 90% percentiles of each Gaussian, respectively.
Figure 14:
Similar to Figure we see that the network distinguishes two main types of attention patterns. Localized heads (i.e., those that attend nearly individual pixels) appear more frequently in the first few layers. The self-attention layer uses these heads to act in manner similar to how convolutional layers do. Heads with less-localized attention become more common at higher layers.
18


Reviews:
[{"review_id": "ryxtiK90Fr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the recent application of attention based Transformer networks for image classification tasks and asks the question as to the similarity of functions learned by these attention networks with the standard convolutional networks. \n\nFirst the paper theoretically proves that a multi head self attention layer (appropriately defined for a 3 dimensional input) can represent a convolutional filter. The proof is based on constructing weights for the attention layers that results in a convolution operation. This construction uses rather crucially the relative positional encodings for the self attention layer. The paper claims that the results can be extended to other forms of positional encodings. \n\nIt looks like the construction is correct as far as I can tell. One caveat is that, It looks like, the weights of the attention layer need to be arbitrarily large (\\alpha in Lemma 2) to exactly represent the convolution layer. I think this is not possible to avoid for exact representation. A comment on this after the results will be nice.\n\nFinally the paper presents experiments on the Cifar10 dataset. The paper shows that the multihead attention units in the lower layers learn to attend on grid like structures on pixels, similar to a Conv filter.  I find the experiments to be nicely complementing the theoretical results, even though they are limited to the Cifar10 dataset.\n\nOverall I think this paper takes a nice step towards understanding the similarities and differences between the Attention and Conv layers, and I suggest acceptance.\n\nMinor:\nFirst sentence in intro raise -> rise.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgXKBVXtr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper shows both theoretically and in practice that self-attention can learn to act as convolutions. The main intuition is that every attention head can learn to attend individually to a given relative offset around each pixel. Given enough heads (K**2) such a layer can imitate a convolution with kernel size (K,K). This leads to the conclusion that self-attention is at least as powerful as CNNs are. This fact has been acknowledged by (at least part of) the community for a while (following a similar intuition) but as far as I know has never been formalized. Hence, although incremental I consider this an important contribution. The derivation of quadratic relative encoding is a nice theoretical construction. Experiments show improvements over learned relative attention, however, experiments are merely conducted on Cifar.\n\nFinally, even though the contributions are somewhat marginal and the experiments are not quite enough to establish the new relative attention mechanism as being superior, I like this paper and consider its contributions valuable. The message of the paper deserves a larger audience and I therefore lean to accept despite some shortcomings.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1eGmNvsFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper claims that 1. multi-head self-attention(MHSA) is at least as powerful as convolutions by showing that a CONV can be cast as a special case of MHSA and 2. that in practice, MHSA often mimic convolutional layers.\n\nThese claims are interesting and timely, given that there has been a fair amount of recent work that have explored the use of self-attention(SA) on image tasks, either by composing SA with convolutions or replacing convolutions altogether with self-attention (examples of each are referenced in the paper). So should these claims be true, they would give theoretical evidence that SA can completely replace convolutions.\n\nHowever, I think that the claims are exaggerated and misleading.\n1. The theory shows an arguably contrived link between self-attention and convolution. Theorem 1 says that a convolution can be seen as a special case of MHSA, and the constructive proof (that chooses SA parameters to derive a convolution) shows a correspondence between the output of each head of MHSA and a D_out by D_in linear transform applied to the D_in features of a single pixel, with attention weight given entirely to this pixel (i.e. hard attention). The derivation relies heavily on the use of a relative encoding scheme that sets W_qry=W_key = 0 (usually referred to as W^Q, W^K in the self-attention literature, the linear maps applied to the queries and keys) i.e. the attention weights do not depend on the key/query values, but only their relative positions. Moreover, the softmax temperature (an interpretation of 1/alpha) is set arbitrarily close to 0 to make the softmax saturate and attain hard-attention. With these two constraints, I am sceptical as to whether you can really say that you are implementing self-attention. In standard practice when MHSA is used, W^Q and W^K are never set to zero, and the scale of the logits for the self-attention weights are controlled by normalising them with sqrt(D_k) (or sqrt(D_k/N_h), depnding on how you choose to deal with multiple heads). Furthermore, the derivation only holds for when stride=1 and padding=“SAME”, such that the spatial dimensions of the input (H & W) remain unchanged. In fact the padding is not really dealt with in the derivation, and it is unclear whether the result can generalise to convolutions with stride > 1, making the claim “MHSA layer … is at least as powerful as any convolutional layer” problematic. Hence although I think the derivation is mathematically correct, I think that the link that the derivation makes between convolutions and MHSA is somewhat contrived and not a useful observation in practice. I expect MHSA with learned W_qry and W_key will behave differently to when they are set to 0, and it would be much more interesting/relevant to see how their behaviour compares with convolutions in this more realistic setting.\n\n2. The heavy dependence of the experiments on the quadratic encoding, the aforementioned contrived form of MHSA that was used to derive the link between convolutions and MHSA, makes the results not very relevant and the claim that \"MHSA often mimic convolutional layers\" rather misleading. It could be more relevant if quadratic encoding can replace standard MHSA parametererisations with learned W_qry and W_key, but I’m not convinced that this is the case. Although Figure 4 suggests that this SA with quadratic encoding gives similar test performance to ResNet18, I think that CIFAR-10 classification is too simple a task to claim that quadratic encoding can replace standard SA with learned W_qry and W_key, and I think results can look very different for harder problems e.g. ImageNet, MSCOCO - explored in Ramachandran et al - made possible because they use local SA as opposed to full SA. Experiments on these problems would be much more interesting and relevant. Note that the experiments using the learned relative positional encoding have “attention scores (are) computed using only the relative positions of the pixels and not the data” (I’m guessing this means W_qry=W_key=0 again). Hence the qualitative similarities between MHSA and convolutions only hold for the rather restricted case where I get the impression that self-attention has been unrealistically constrained only to increase its chance of behaving similarly to convolutions. Also the comparison in Figure 4 and Table 1 is being used to support the claim that self-attention can be as “powerful” as convolutions, but I think this is misleading because both quadratic and learned SA uses full SA, where each pixel attends to all pixels - this means the time & memory complexity of the algorithm is O((HW)^2), whereas for convolutions it is O(HW). So the expressiveness of SA that matches convolutions for this particular problem comes at a significant cost, to the extent that for bigger problems (ImageNet, MSCOCO) full SA is not feasible due to its quadratic memory requirement, whereas convolutions don’t face this problem. I think this should be pointed out more explicitly in the text, and think the claim that “self-attention is at least as powerful as convolutions” should be replaced with a more moderate statement such as “self-attention defines a family of functions that contains convolutions (of stride 1)”\n\nSummary: Although the writing of the paper is clear and the derivation is mathematically correct as far as I can see, the link between self-attention and convolutions in the paper are fairly contrived, hence the contribution of the paper to the field is not so significant in my honest opinion.\n\n********************\nI appreciate the authors' response, and understand that the maths suggests a single head of MHA (in the original form) cannot exactly emulate a general convolution. But empirically, the localised attention patterns do seem to suggest that each head can behave similarly to a restricted form of convolution, where similar weights are given to the receptive field (the local patch) in the neighbourhood each input pixel. Perhaps an analysis of what special case of convolution each head can emulate would be interesting, given the empirically observed similarities in the qualitative behaviour. \n\nWith the more justified nuance of the findings of the paper, and together with the authors' significant efforts to make the evaluation more relevant and thorough, I will increase my score to \"weak accept\".", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the relationship between attention networks such as Transformers and convolutional networks. The paper shows that a special case of attention can be cast as convolution. However this link depends on using relative positional embeddings and generalization to other encodings are not given in the paper. The reviewers found the results correct, but we caution that the writing should better reflect the caveats of the approach.
Decision: Accept (Poster)