Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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. 

First 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. 

It 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.

Finally 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.

Overall I think this paper takes a nice step towards understanding the similarities and differences between the Attention and Conv layers, and I suggest acceptance.

Minor:
First sentence in intro raise -> rise.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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.

These 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.

However, I think that the claims are exaggerated and misleading.
1. 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.

2. 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)”

Summary: 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.

********************
I 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. 

With 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".
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.

Finally, 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.
review_title: Official Blind Review #1

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)