Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work constructs an optimization problem whose approximate solution results in a general form of attention. The optimization objective is derived from three assumptions: 1. the prior of the attention distribution has a support of the memory bank; 2. the likelihood of the query vector in the attention mechanism is roughly conforming to an isotropic Gaussian centered at the difference between the mean of the attention distribution and the mean of a prior distribution; 3. the standard deviation of the isotropic Gaussian is large. Then the mean of the posterior of the attention distribution is a general form of attention, with the dot attention scores reweighted by the prior probabilities. Under this framework, when the prior is a uniform distribution, dot attention is recovered; when the prior is defined by positions and word masks, the attention used in T5 is recovered.
main_review: Strengths:
1. The math is elegant. Under the three simple assumptions, a general form of attention happens to be the mean of the posterior.
2. The general form of attention makes sense intuitively: T5 can be understood as one special case when position information is used, and there are also other works that can be viewed as special cases such as applying a content selector before attention (https://arxiv.org/pdf/1808.10792.pdf).

Weaknesses:
1. My main concern is the lack of intuition. While general attention follows from an optimization problem derived from the three assumptions, this formalism doesn't provide any more justification. In fact, I think directly proposing the general attention is more intuitive than going through all the math, especially considering that we are not treating the attention variable as a random variable or use its distribution in any sense (such as by marginalizing it, rather than simply using its mean under this work's formalism).
2. I don't think it's reasonable to assume the standard deviation of the isotropic Gaussian to be large ($\alpha$ being small under this paper's notation). There are situations where we use a high $\alpha$. For example, there are cases when we use a low "temperature" in attention to get more spiky or even one-hot distributions (such as in Gumbel-softmax https://arxiv.org/pdf/1611.01144.pdf). While this paper argues that the prior distribution reduces the support of the attention from tens of thousands of words to several dozens, I don't think "the inference of p(k) should strongly anchor around this prior information" (L237): no matter how large $\alpha$ is, the optimal solution of Eq. 6 always has the same support as the prior, so using whatever $\alpha$ is always anchoring around this prior information if we just want to have the same support.

Suggestions:
1. I think maybe it'd be more clear to get rid of the superscript $^{(k)}$ and simply mention that only a single step is considered in the case of predicting a sequence.
2. The motivating example is on a continuous case while the focus of the rest of the paper is on a discrete case. I think maybe you don't really need this motivating example.
3. The discussion section mentioned that the proposed approach might generalize to continuous cases. I think this paper would be stronger if you can make that work (and the motivating example would make more sense). 

Overall, this paper is well-written and the math is elegant. However, the intuition and motivation of the objective function are not very clear and I am not convinced that having this objective function provides a principled justification for attention. Therefore, I am leaning towards rejecting this paper unless I missed anything.

==== Post Rebuttal ====

My concern about the assumption $\alpha$ being small has been resolved: it makes sense that in practice (transformers) $\alpha=\frac{1}{\sqrt{d}}$ is small. 

Besides, it's interesting to see the extra experiment that shows optimizing 6) has a similar BLEU score as using $\alpha z^{(k)}$, and that $\alpha z^{(k)}$ is close to the optimal solution.

Therefore, I'm increasing my score to 6. That being said, I think this paper still can be further improved: for example, the BLEU score in the added experiment is quite low (I'd suggest using a smaller translation dataset such as IWSLT14 De-En), and I think it would be much more convincing if you can just use a trained transformer (with normal attention), and show that optimizing 6) gets a similar BLEU score. Lastly, I think this paper would be much stronger if you can add some experiments with a continuous version.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper introduces a novel interpretation of the attention algorithm and corresponding theoretical discussions. The paper suggests that the "(weighted) attention algorithm" can be interpreted as an approximate solution of a density estimation problem, where we have a noisy observation of a mean and a reference distribution (or "preference distribution" in the paper). 

In the proposed interpretation, the density estimation solves a proximal-type optimization problem. The penalty function is a reverse KL to a reference distribution, and the objective function is an L2-norm between the model's mean and the observed mean. Here, the authors emphasize treating the observed mean as a sum of the reference's mean and a noisy observation of a mean-shift.
Since the optimization problem satisfies the strong duality, the optimization can be solved by its dual; however, it is still challenging to obtain its analytical solutions. Thus, in the dual problem, the authors introduce to approximate a term, a cumulant generating function of a reference distribution, by its second-order Taylor polynomial. The authors show that the closed-form solution of the resulting approximate problem is the dot-product attention, weighted by a reference distribution.

Furthermore, the authors show that the proposed interpretation includes a well-known T5 transformer as a special case. Assume we aim at solving the proposed optimization problem to estimate a density of a categorical distribution, where the distribution is on a set of M vectors (i.e., M keys). Given some context information, a set of networks predicts a preference distribution and a query, which is the mean-shift. The weight on the L2-norm in the optimization problem is the inverse of the temperature parameter. Then the T5 transformer's attention can be obtained by the expected value of keys under the analytical solution of the approximate dual problem. Thus, the authors demonstrate that the closed-form solution of the approximate dual problem is a generalized attention algorithm. Under the proposed framework, the design of preference distributions is flexible; for example, one can choose different types of context information depending on tasks.

In experiments, the authors discuss how much the deviation of the approximate dual's solution from the ground truth depends on \alpha.
main_review: Overall I enjoy reading the paper and believe the paper will be an essential contribution to the ML community. However, the paper should improve the quality and clarify.  
  
(Originality & Significance)  
I found that the proposed framework can provide a significant contribution to the ML community. For example, the authors can check if reducing the approximation errors improves the performance of the attention mechanisms. In the proposed framework, the authors take two levels of approximations. The first is to take the second-order Taylor polynomial of the cumulant generating function (CGF) in the dual problem. The second is the approximation from Eq 17 to Eq 18. If we focus on the latter, we notice that one can directly plug Eq. 17 into Eq. 14 without using Eq. 18. The solution contains the covariance of the keys, and the resulting attention naturally takes into account the correlations between keys. It would be exciting to see if the attention with the covariance terms will improve the performance.   

Similarly, the authors can discuss the approximation errors of the second-order Taylor polynomial. It would be very interesting to see if the exact solution or higher-order polynomial will improve attention algorithms.


(Quality & Clarity)  
The abstract and introduction section doesn't provide enough information about the paper and potential discussions. For example, it is difficult to guess what "a certain type of optimization" the authors refer to and in what context the authors introduce the generalization of the attention.

It is challenging to clarify how the proposed framework is supposed to look. I highly rely on the reference, G. Rioux et al., '20. I believe that the paper should be improved. For example, one may include 1) the motivation of solving the dual instead of the primal, or 2) what conditions described in the proposed method provide strong duality.

While Section 3-4 provides example cases in attention mechanisms, it isn't easy to draw a connection from the descriptions to the proposed framework.

In my understanding, the connection of the proposed framework to the principle of maximum entropy is invalid. There must be a historical reason for naming "maximum entropy on the mean (MEM)." Still, it would be nice to clarify the difference between the MEM and maximum entropy principle. I also found that G. Rioux et al., '20. also clarifies that MEM is different from the principle of maximum entropy (see Sec 3.1 in their paper)  
  
   
  
(Minor comments)
- In Eq 17, a \alpha → 0, isn't \Sigma^{-1} z the only one left?
limitations_and_societal_impact: (Limitations)  
In my understanding, Theorem 2 is incomplete, while it is supposed to be the major contribution of the paper. In Theorem 2, the approximation error depends on the remainders of the Taylor approximation of the cumulant generating function (CGF) of the preference distribution. In understanding, the characteristics of the CGF's higher-order Taylor terms are not trivial, except the normal distributions. Therefore, I consider it essential to specify the conditions of the remainders and how small \alpha should be to validate the approximation. One may only consider some common choices of preference distributions, such as the categorical or normal distributions. Note that the authors mention that in Lines 306-307, the approximations have implicitly assumed that the bounded moments of the preference distributions. However, I consider that Theorem 2 specify such conditions. Moreover, as far as I know, the behaviors of cumulants differ from moments in higher-order, so it is important to describe if preference distributions have bounded cumulants instead of bounded moments.

While the paper provides a novel interpretation of the attention algorithms, the discussion about testing the hypothesis (= the proposed framework) is limited. As I mentioned in the "Originality & Significance," one way to (indirectly) test if the proposed framework is generalized attention is to analyze if reducing the approximation errors improves the performance in a set of toy examples. I believe that providing such discussions will enormously improve the significance of the paper.
  
  
  
(Societal Impact)  
N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper casts attention as a solver for an inference task that consists in estimating the mean of an unknown distribution given two information: an unreliable estimate and a prior distribution. The authors start by explaining this inference task and showing how this setup encompasses several real-life examples (translation, image captioning, filling the blanks). Then, they derive a convex optimization problem from this task and solve it by looking  at its Fenchel dual. Finally, the authors show that the solution obtained from this problem yields a generalized attention that is implicitly used in T5 Transformer.
main_review: As mentioned to the AC, I would like to first signal that I am not familiar at all with attention and NLP tasks. Therefore, it is very hard for me to assess whether the model proposed in Section 4 by the authors is valid or not.  

Originality: The paper is definitely original and looks at a question that raises a lot of interest. The techniques used are classic in convex optimization but they are used in a novel way. I am not aware of any work modelling attention as a solution of a convex optimization problem. The related has the merit to cite other works that mathematically model attention. 

Quality: The paper seems technically sound on the optimization side. I also appreciate the fact that the authors bring the weaknesses and limitations of their approach. I would like to raise some points: 

1) The problem formulation (6) assumes that p is in the support of u^k (otherwise the KL divergence is not well defined). However, how do you enforce this fact? It does not seem obvious to me that you are enforcing this constraint in (6). 

2) Is it realistic in the case of language to assume that the noise in (5) is a Gaussian random variable? The whole analysis in Section 5 seems to rely on that.

3) What is the choice of the prior that you would make when applying your method in practice? For instance in a translation task?

4) Do you think that it is possible to numerically compare the Transformer T5 with a vanilla Transformer? How does your model differ from the vanilla attention?

Clarity: I think that the paper is very well written and I appreciate the efforts of the author to explain in detail their motivation (Section 3) and the setup they propose (Section 4) by taking concrete examples.  

Significance: I cannot really assess the significance of the paper as I am not an expert in NLP. I however believe that the authors should do more experiments on real-life NLP tasks and compare it to a vanilla transformer. This would help to assess the validity of their model and maybe figure out some limitations of their approach.
limitations_and_societal_impact: The authors dedicated a whole paragraph regarding the limitations of this paper which is definitely an advantage of the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a new perspective on the attention mechanism. More precisely, the paper claims that an attention module can be seen as estimating the distribution solving a specific optimization problem. This problem follows the assumption that many deep learning models use a module updating a global guess with local information. The problem consists in minimizing both the discrepancy between an adjusted value of the mean and the mean of the estimated distribution, and between a prior distribution and the estimated distribution. Using some approximation, the solution corresponds to a generalized form of the dot-product attention.
main_review: Although the perspective provided seems at first glance artificial, it is original, sound, and seems indeed related to attention. The paper is globally well-written. To my mind, some points (how does this perspective apply in practice, some points to clarify) are worth being adressed before recommending acceptance. 

Pros:
- To the best of my knowledge, the paper indeed provides a new, nice perspective on attention.
- The paper provides insightful links between their formulation of attention and classical deep learning architectures.

Cons:
- The perspective proposed by the paper is potentially insightful but the authors does not bring out whether their perspective really applies in practice: would real, learned attention mechanisms indeed provide a good approximation to the optimization problem (6)?
- Conversely, the paper could benefit from an example where solving the optimization problem can effectively replace a learned attention mechanism.
- It is not clear to me whether this perspective really applies in transformers (see below). This may be due to a misunderstanding from my side though.

Questions and remarks:
- l21-22: what is ``"poorly understood" in attention?
- Section 2: There are works related to attention that could be worth citing in Section $2$, see non-local means [1], and attention as a kernel smoothing [2] which also proposes a generalized attention mechanism. 
- Section 4: previous work learn a template from the whole data set for computing the attention weights in linear time, e.g, [3][4]: would this improve the estimation of $p^{(k)}$ in your perspective? 
- l114: early explanation/intuition on $f_{prev}$ and $f_{evd}$ could be useful.
- l120: inconsistency in fonts for the Real symbol.
- l134:  could you elaborate on this problem? Why would we want to solve it in the context of deep learning?
- l174: in BERT, the attention weights are computed with keys and queries matrices, and not with values and queries as suggested by Figure 2c. Moreover, the attention output is added to the input feature map which is different from what Figure 2c seems to suggest. What is your view on these two potential differences?
- Figure 3: if $\alpha$ is small, it seems that the estimate of $\hat{h}^{(k)}$ goes away from $\mu^{(k)} + z^{(k)}$, making the evidence term $z^{(k)}$ potentially useless?

---------

[1] Buades et al. : Non-local Means Denoising, IPOL 2011

[2] Tsai et al. : Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel, EMNLP 2019

[3] Mialon et al. : A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention, ICLR 2021

[4] Kolouri et al. : Wasserstein Embedding for Graph Learning, ICLR 2021
limitations_and_societal_impact: See above (Cons) for the limitations of the paper from my point of view. 
I think the authors correctly address the potential negative societal impact.
review_title: null

Meta-review: This paper received an overall score of 6 and is therefore borderline.

All reviewers agreed that it's a very promising paper that could shed some light on attention models. 

However, in the current state, we believe the paper isn't ready for publication yet:

- The writing would benefit from some polishing. 
- Section 3 "Motivating example" feels disconnected from the rest of the paper. We would personally remove it since it appears in Theorem 1.
- Section 4, Figure 1 and Figure 2 were difficult to follow. Some effort needs to be spent on clarity.
- Reading the paper, we are left with the feeling "so what?". Although a variational perspective of attention is interesting, we already know empirically that attention works. Coming up with benefits that only this new view brings is very important. To that end, the experiments that the authors posted in the rebuttal are promising.
- Reviewer ZmJe mentioned issues with Theorem 2

Overall, we agree with reviewer ZmJe 

> In conclusion, the authors respond to most of my concerns. Unfortunately, however, such modifications require major revision, and thus I will keep my current score. On the contrary, I strongly believe that the revised version will be a significant contribution to the ML community.

We therefore believe that the ideas described in the paper are not yet clear enough to obtain the impact that they deserve. Polishing the paper and adding more experiments will greatly increase the impact of this paper and the authors will eventually benefit from it.
Decision: Reject