Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper tries to analyse the Transformer, widely applied building block of a neural network component, to improve understanding of the internals of the model. The analysis starts showing that the transformer blocks generate permutation equivalent maps and then shows that the transformer can approximate any permutation equivalent map in a compact domain with arbitrary precision. Three key steps are developed and used to prove the universal approximation of arbitrary permutation equivalent map: 1) quantization of input via feed-forward layers, 2) contextual mapping via attention layers, and 3) value mapping via feed-forward layers. By introducing positional embeddings, the paper relaxes the restriction on permutation equivalence and proves that the Transformer is a universal approximator of any sequence to sequence function.

Overall, the paper presents an interesting analysis of the Transformer providing some practical implications, with a caveat for some clarifications on the experiments. The structure of the manuscript could be improved.

One of the natural question after reading this paper is whether the claims made in section 5 are what actually happens inside of the Transformer because we often observe the attention layers of the first few stacks of Transformer blocks do something. Since the claims lead us to have a universal approximator of seq-2-seq functions, it would be great if there is an experiment based on an alternative model structure based on the claims. For example, one can design a new Transformer architecture with stacks of feed-forward layers, followed by stacks of self-attention layer, followed by other stacks of feed-forward layers. Which may reduce the number of model parameters while preserving a similar level of performance.

Here are a few minor comments on the structure of the manuscript. It seems a bit unnatural to have a section with a proof sketch (section 4). Will it be better if it follows theorem 2. Also, the title of section 5 seems not very informative (proof sketch of proposition 4). You may consider rewriting these sections to improve readability. The definition of contextual mapping and the following lemma seem also one of the major contribution of this paper since the other proof techniques are somewhat familiar with the existing method on universal approximation theory. It would be good to have these result in the early part of the manuscript instead of having it in the end.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: CONTRIBUTIONS:

C1. Transformers (without positional encodings and without layer normalization), with 2 attention heads of dimension 1 and feed-forward layers (FFN) with 4 hidden nodes, are universal approximators of continuous permutation-equivariant functions f of compact support, relative to any Lp metric (1 <= p < \infty). (Thm. 2, p. 3). (Without positional encodings, a function f computed by a Transformer is permutation equivariant: f(P(X)) = P(f(X)) for any permutation P of the columns of X, which are the vector encodings of the input tokens.)

C2. For transformers with trainable positional encodings, the same result holds without the restriction to permutation equivariance (Thm. 3, p. 4)

C3. The notion of ‘contextual mapping’ is introduced (Def. 5.1, p. 6); this notion is central to the proofs of the theorems in C1-C2. Such a mapping q takes any two vectors L, L’ in a finite subset of a real vector space and maps them to a vector space such that all elements (in R) of q(L) and q(L’) are distinct. (In the permutation-equivariant context, L’ must not be a permutation of L.)

RATING: Weak accept

REASONS FOR RATING (SUMMARY). ‘Accept’ because the results seem important. ‘Weak’ because the explanation for the crux of the key result is inaccessible. It relies crucially on the notion of C3, the utility of which for understanding how real Transformers work is questionable.

REVIEW

Sec. 4 does a good job of sketching the key proof. But Sec. 5 falls down at a crucial point, Lemma 6.


What I can glean from the paper (Sec 5.0) is that the idea of the proof is this: (1) use the continuity of f to approximate it with a piecewise constant function c, which takes a fixed value within each hypercube of a discretization of the compact support of f; (2) use a FFN g to map f’s input space to a discrete subset, a regular finite grid G defining the corners of the hypercube discretization; (3) use modified Transformer attention layers to create a contextual mapping k of G; (4) use a FFN h on R to map each (unique) real number in the vector outputs of k to the correct output value so that h([k(g(X))]_i) = [c(X)]_i; (5) approximate the modified Transformer attention layers of k with standard Transformer attention layers. (The modified attention layers replace softmax with argmax and replace ReLU with a (varying) piecewise-linear activation functions “with at most 3 pieces, at least one of which is constant” [Step 2, p. 4.])

The paper should focus on steps (3) and (5), the only parts of the proof that pertain to what is special about the Transformer: attention. These should be explained fully and clearly in the main text. To make room for this, the rest, concerning FFN approximation and discretization, can be reduced to a paragraph each in the main text, since they are standard, not particular to Transformers.

My attempts to understand the proofs of (3) and (5) from the Appendix were not successful. To illustrate the kind of difficulty I had in several places: in the proof of Lemma 9 on p. 12, the conclusion is “Thus, given any \bar{g} \in \bar{\cal{T}}^{2,1,1}, there exists a function g \in \cal{T}^{2,1,4} arbitrarily close to \bar{g}, by appropriately choosing the parameters to be large enough.” (“2,1,4” means a Transformer attention layer with 2 heads of dimension 1 followed by a FFN with 4 hidden units) But how do the numbers {2,1,1} and {2,1,4} relate to the equations internal to this proof? I can see some possible connections, but the authors should spell this out very clearly rather than making the reader work to fill in the gap. It should be clear how the ATTENTION MECHANISM is crucial for the proof by understanding just how that mechanism does the work needed in steps (3) and (5) above.

Given the time-consuming but ultimately unsuccessful attempt to understand the first few pages of the 11-page Appendix, I did not attempt to absorb the remaining pages.

It is clear that the notion of contextual mapping plays an important role in their proof of the universal approximation theorem, but does it play any role in the operation of Transformers in practice? Spraying the points of a grid G in the Transformer’s input space into a collection of vectors in which the same real number never appears twice is a nice step in an approximation proof, because it reduces the problem to mapping a set of unique real numbers to another set of real numbers (the elements of the output vectors). But does an actual trained Transformer in practice do anything resembling this? It seems implausible on the face of it, but perhaps there is a theoretical argument, or empirical evidence, that makes it plausible. Thus, for understanding how real Transformers actually do their work, the value of the notion of contextual mapping, and therefore the discussion at the end of the paper of alternatives to attention for achieving it, appears questionable to me. The subtitle of Sec. 5, “Demystifying Transformers”, is not clearly justified.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 
This paper discusses the universal approximation capability of the Transformer, under certain assumptions, analyze the role of different components of the Transformer (e.g., self-attention layer for contextual mapping), and propose the use of some other layers that can also provide contextual mapping.

Overall speaking, the problem studied by this paper is very important. The transformer has been used extensively in many applications today, however, deep theoretical understanding of it is not sufficient. Universal approximation capability is a very important theoretical property of deep learning, and advances on the universal approximation of the Transformer is important for the deep learning community. Therefore, I think people will be willing to see the results in this paper. 

While saying so, this paper has some limitations, which could be further improved. 

1)	The paper studies a variant of the Transformer, where the layer norm is removed. However, according to practical experiences, the layer norm plays a critical role in the Transformer. As a result, there is gap between this paper and practical situations, and the value of the paper becomes not very clear.

2)	The paper lacks experimental verifications. It would be better to design some toy experiments with different types of target functions to see whether the Transformer can well approximate them, and see the contribution of different components of the Transformer

3)	The discussions on contextual mapping are not solid enough. First, it seems that contextual mapping is kind of sufficient condition for the proof, however, it is unclear whether it is a necessary condition. Consequently, things are not clear regarding”

a.	If all the structures (self-attention, bilinear projection, depth-wise separable convolutions) are all sufficient conditions, why self-attention is better than the other two, and why the mix of them can generate even better results?

b.	If they are not necessary conditions, we cannot say one should choose them since other structures may be equally good even if they do not satisfy contextual mapping conditions.

4)	The experimental study in the paper is not very comprehensive. Given that the Transform has been used in many NLP scenarios, experiments on more datasets and more tasks are expected.


**I read the author rebuttal. Some of my concerns still remain, and I would like to keep the current rating (which is positive).
review_title: Official Blind Review #1

Meta-review: The paper provides a proof that Transformer networks (a popular deep learning model) are universal approximators for sequence-to-sequence functions. The theorem relies on the idea of contextual mappings (Definition 3.1), which models the attention layers. The results provide an important starting point for understanding a very widely used architecture.

As with many theoretical papers, the reviewers provided several suggestions as to which are important parts to be presented in the main paper. The authors were very responsive during the discussion period, updating the structure of the paper significantly. This shows nice evidence supporting the need for a long discussion period for ICLR. One reviewer upgraded their score (to 8), which is not reflected in the system.

This is an excellent paper, providing much needed theoretical analysis of a popular neural architecture. Clear accept.


Decision: Accept (Poster)