Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: In this paper, the authors treat a particular Transformer, "dot-product attention", as  an RKBS kernel called "exponentiated query-key kernel". The explicit form of feature maps and Bach space are given. Moreover, authors term a binary kernel learning problems within the framework of regularized empirical risk minimization. The problem and the correponding representer theorem is new due to its extension to Banach space. A new approximation theorem is also proved and  some experiements are done. 
Pros:
The idea of understanding how Transformers work with the help of non-mercer binary kernel  is interesting.
As for the theoretical side, authors provide representer theorem to binary kernel learning for Banach space rather than Hilbert space. 

Cons:
The experiment is insufficient because only one dataset is studied.
I think the proof is just a generalization of kernel learning problems on RKBS, without too much difficulty.
review_title: My review of paper "Transformers are Deep Infinite-Dimensional Non-Mercer Binary Kernel Machines"

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper aims at providing a mathematical structure for explaining the mechanism behind the attention block characteristic to transformers. The focus of the paper is on the scaled dot-product attention, reviewed in Eq. (1). In my understanding, the whole mechanism can be seen as an instance of the set kernel. The inputs are bags of items, where an item is denoted with $s_j$. The items are embedded into some feature space via matrix multiplication $W^V s_j$. The set kernel representation of a bag is obtained by weighted averaging of item embeddings, where the item-specific weight is the output of an exponential family model. The latter model is obtained by combining embeddings of items and corresponding context vectors, denoted with $t_i$ (see Eq. 1 for more details).

The paper in itself does not explain this mechanism as a whole but focuses on the un-normalized exponential family model that provides importance weights in the set kernel embedding. In particular, the main focus of the work is to find a bilinear form and, thus, a mathematical structure that could give rise to non-symmetric similarity function defining the un-normalized importance weights in the set kernel described above. More formally, the work seeks a kernel function
$$
k(t,s) = \exp(\frac{(W^Qt)^{\top}(W^Ks)}{\sqrt{d}}) \ ,
$$
where $d$ is the rank of W-matrices.

This is achieved by introducing the so called reproducing kernel Banach space (Sections 3 and 4). Following this, the paper introduces a form of regularized risk minimization problem in reproducing kernel Banach spaces. I fail to see a direct link to transformers and backpropagation used in training of such models. The conclusion is that transformers learn a kernel or similarity function that can be assigned to a reproducing kernel Banach space. I disagree with this because the whole attention mechanism is a set kernel, with the supplied bilinear form amounting to importance weights only. The section 5 concludes with a representer theorem and regularized risk minimization problem in reproducing kernel Banach spaces. Again, this is a completely disconnected part of the paper from the introduction and provided motivation.

#### clarity
I find the paper clear in most parts and have not had problems following the main arguments. Related work on learning with similarity measures, indefinite symmetric kernels, and general similarity functions seems to be well covered.

#### quality
I think this paper should really be focusing on learning in reproducing kernel Banach spaces with non-symmetric similarity measures. It is difficult to tell how much novelty it brings compared to relevant related work and how useful it would be in practice. If the authors decide to take this direction, then there should be a detailed experiments section where trade-offs between effectiveness and computational complexity are carefully studied. 

It is unclear to me why this work would be associated with attention models and transformers. The story just does not hold and it does not explain the scaled dot-product attention. At the moment, it just seems as an unfinished work that is unnecessarily associated with attention and transformers.

review_title: ICLR 2021 Conference Paper2896 AnonReviewer1

final_score: rating: 7: Good paper, accept
review_content: The paper aims at making a link between kernels in RKBS (indefinite and asymmetric kernels) and the dot-product attention of Transformers. The paper contains several contributions on top of this link : it provides a novel kernel machine that can deal with data from 2 distinct input domains and a cross domain output, it show that Transformer can learn such kernels, and it also give hints on what make Transformer efficient.

The paper manages to present different backgrounds (transformers and exotic kernels) to mix them in a quite clear manner. Notations from two worlds are respected such that, as far as I can say, people from each side can catch things quickly. 
From the transformer's perspective, being able to plug any well designed kernel in place of the dot-product attention can have some interesting practical application. The observation that the efficiency of transformer could be linked to the infinite feature map brought be some kernel shapes is appealing but quite weak. 
From the kernel machine's perspective, the proposed kernel machine in RKBS is elegant and comes with solid theoretical proofs. It might have been a paper by itself. 
The choice of content in paper/in supplementary seems good to me.

I vote for accepting the paper, as I find the idea interesting, I can see some applications and the theoretical part seems correct to me. My main concern is about section 6, which contains only one experiment. It illustrates the fact that one can change the kernel in transformers, but not much more. 
I also have difficulties to see how section 5.2 is done in practice, as I find the description of implementation details do not consider those aspects : I would be happy to have more details on the algorithms

- Details :  
* section 6 : I suggest the order of kernels be the same in table and in text, it would be easier to follow. 
* section 5.2 : I think this reference (https://doi.org/10.1016/j.patcog.2017.06.003) introduces Nystrom for RKKS a couple of years earlier. 
review_title: a two-fold contribution - transformers and kernel machines. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Review: This paper demonstrates that transformer models with dot-product attention-based scores are inherently
learning feature representations in reproducing kernel Banach spaces. Under some mild regularity conditions,
the authors demonstrate that the regularized empirical minimization solutions are unique, (i.e. linear independence
assumptions in the two reproducing kernel Banach spaces corresponding to the targets and the sources) and that
using two-layer neural network with appropriate number of hidden layer units can achieve universal approximation
property.
 
Overall reasons for score:
I am leaning toward arguing for acceptance. The paper establishes a connection between a fairly recent method a classical method. It would have been nice to see more experimental results (see below).

+Positives: 

+ The paper for the most part is clearly written and establishes a connection between the recent method and the classical
method. I have skimmed through most of the proofs and they seem to be correct.
 

Concerns: 

- The experimental section is fairly limited since the majority of the paper focuses on more theoretical aspects of transformers.
In particular, it would be interesting to see the authors expand upon whether exponentiated dot products are better on
more datasets.
 
- The theoretical contributions in this paper are interesting but mainly pieces together results.

Minor comments: 

* Proposition 1 has typos in Equation 7a and 7b. (q_l)^n -> (q_l)^{p_l} and (k_l)^n -> (k_l)^{p_l}

review_title: Transformer models are non-mercer binary kernel machines on reproducing kernel Banach spaces

Meta-review: Reviewers have different views on the paper and after going through the reviews, replies and the papers, we believe that
there is room for improvement here. 

While the part related to  indefinite symmetric kernels, and general similarity functions seems to be well covered, as
well as the part on Transformers, the relation with learning in RKBS and Transformer is far from being clear and Reviewer 4 makes a strong point on this. For instance, 

* what is the goal of the section 5 and Definition 1 . Indeed it is not clear here if the point of the authors is to learn the kernel parameters in equation 9 or to learn to predict the output of a transformer. If it is the latter, the connection with the first part is unclear.

* In Equation 11, I can understand that x and y are the sequences t and s but what is z_ij and how it is obtained? So again, the learning problem drops in without justification and it is not explained how it can be solved. The theoretical results involving the representer theorem is nice though.

* The experiment does not seem very related to the learning problem in Equation 11 introduced by the authors.it seems to me that they are just trying different kernels on top of the dot product.

Decision: Reject