Attention: Self-Expression Is All You Need
Authors: Rene Vidal
Venue: ICLR 2022 Submitted (2022)
Keywords: Self-attention
sparse representation
subspace clustering

Abstract: Transformer models have achieved significant improvements in performance for various learning tasks in natural language processing and computer vision. Much of their success is attributed to the use of attention layers that capture long-range interactions among data tokens (such as words and image patches) via attention coefficients that are global and adapted to the input data at test time. In this paper we study the principles behind attention and its connections with prior art. Specifically, we show that attention builds upon a long history of prior work on manifold learning and image processing, including methods such as kernel-based regression, non-local means, locally linear embedding, subspace clustering and sparse coding. Notably, we show that self-attention is closely related to the notion of self-expressiveness in subspace clustering, wherein data points to be clustered are expressed as linear combinations of other points with global coefficients that are adapted to the data and capture long-range interactions among data points. We also show that heuristics in sparse self-attention can be studied in a more principled manner using prior literature on sparse coding and sparse subspace clustering. We thus conclude that the key innovations of attention mechanisms relative to prior art are the use of many learnable parameters, and multiple heads and layers.

Under review as a conference paper at ICLR 2022
ATTENTION: SELF-EXPRESSION Is ALL YOU NEED
Anonymous authors
Paper under double-blind review
ABSTRACT
Transformer models have achieved significant improvements in performance for various learning tasks in natural language processing and computer vision. Much of their success is attributed to the use of attention layers that capture long-range interactions among data tokens (such as words and image patches) via attention coefficients that are global and adapted to the input data at test time. In this pa- per we study the principles behind attention and its connections with prior art. Specifically, we show that attention builds upon long history of prior work on manifold learning and image processing, including methods such as kernel- based regression, non-local means, locally linear embedding, subspace clustering and sparse coding. Notably, we show that self-attention is closely related to the notion of siffeexpressieeeess in subspace clustering, wherein data points to be clustered are expressed as linear combinations of all other points with coefficients designed attend to other points in the same group, thus capturing long-range interactions. We also show that heuristics in sparse self-attention can be studied in a more prin- cipled manner using prior literature on sparse coding and sparse subspace cluster- ing. We thus conclude that the key innovations of attention mechanisms relative to prior art are the use of many learnable parameters, and multiple heads and layers.
INTRODUCTION
Attention, i.e., the ability to selectively focus on a subset of sensory observations, while ignoring other irrelevant information, is central component of human perception. For example, only a few words in a sentence may be useful for predicting the next word, or only a small portion of an image may be relevant for recognizing an object. This property of biological systems has inspired the recent development of attention based neural architectures (Bahdanau et al. 2014). such as Transformers [Vaswani et al. 2017). BERT (Devlin et al. 2018). GPT (Radford et al. 2018 2019), RoBERTa (Liu et 20199), and 15 (Rafeel et al.) 2019), which have achieved impressive performance in multiple natural language processing tasks, including text classification (Chaudhari et al. 2019 Galassi et al.)
2020), machine translation (Ott et al. 2018), and question answering (Garg et al. 2020). Attention- based architectures have also led to state-of-the-art results in various computer vision tasks (Khan
et al. 2021), including image classification (Dosovitskiy al. (220)), object detection (Carion et al.
2020
Zhu et al. 2020), and visual question answering (Tan & Bansal 2019 Su et al., 2019).
Much of the success behind attention-based architectures is attributed to their ability capture long- range interactions among data tokens (such as words and image patches) via attention coefficients that are global, learnable and adapted to the input test time. For example, while recurrent neu- ral network architectures in natural language processing predict the next word in a sentence using information about few previous words, self-attention mechanisms make a prediction based on in- teractions among all words. Similarly, while convolutional architectures in computer vision compute local interactions among image patches using weights that do not depend on the input image at test time, vision transformers compute global interactions that are adapted to the input at test time.
In this paper, we show that many of the key ideas behind attention, which we briefly summarize in Section build upon a long history of prior work manifold learning and image processing. In Section we show that the scaled dot product attention mechanism is equivalent to kernel- based regression with the Gaussian kernel (Nadarayal 1964 Watson 1964), recently pointed out in (Chaudhari et al., 2019 Zhang et al., 2021a). and that more general attention mechanisms can be obtained by choosing other kernels. We also show in Section 3 that the non-local means image denoising algorithm (Buades et al., 2005), which can also be understood as a form of dernel-based regression, is the main building block behind the vision transformer (ViT) (Dosovitskiy al.. 2020

---

Under review as a conference paper at ICLR 2022
As consequence, we argue that the key innovation of attention relative to kernel-based regression is not on its ability to capture global long-range interactions that are adapted to the input data (some- thing that non-local means already does), but rather the use of many learnable parameters for defining attention. In contrast, classical kernel methods typically tune only the kernel bandwidth.
In S we establish several connections between masked attention and Locally Linear Embed- ding (LLE) (Roweis & Saul 20000 2003). Specifically, we show that LLE learns a low-dimensional representation of dataset using masked self-attention mechanism where the masks are defined by the nearest neighbors of a data point. The resulting coefficients are not constrained to be nonneg- ative, thus allowing for both positive and negative attention. Moreover, they depend explicitly on multiple data tokens, unlike attention coefficients which depend only on a pair of tokens. We also show that L.LE's training objective can be interpreted as a fill the blanks self-supervised learning objective. However, a key limitation of LLE is that its local neighborhood is pre-specified, so data point cannot attend to any other point. This issue is resolved by eeff-expressiveness, which connects every point to every other point and uses sparse regularization to reveal which points to attend to.
In Section we show that self-attention is closely related the notion of self-expressiveness of BI- hamifar & Vidal (2009 2013); Vidal et al. (2016), wherein the data points to be clustered are ex- pressed as linear combinations of other points with global coefficients that are adapted to the data and capture
interactions among data points. Such self-expressive coefficients are then used to define a data affinity matrix which is used to cluster the data. A first difference between self-attention and self-expressive coefficients is that the latter are not restricted to be non-negative, thus allowing for both positive and negative attention. A second difference is that self-expressive co- efficients are not defined as a function of the tokens parametrized by learnable weights. Instead, the coefficients are learned directly using an unsupervised loss. A third difference is that self-expressive coefficients are typically regularized to be sparse or low-rank. As a consequence, we argue that the key innovation of self-attention relative to seff-expressiveness is neither in its ability to capture global long-range interactions that are adapted to the data nor in the ability to learn such interactions (something that seffsexpressiveesss already does), but rather on the fact that attention mechanisms use multiple sirention-haade in parallel and are stacked into deep architectures.
We conclude with future directions on how to improve self-expressivenes: using self-attention and vice versa. For example, we argue that the use of sparse regularization in (Elhamifar & Vidal 2009] 2013) to automatically seleet the most relevant coefficients is more principled way of handling large number of tokens than restricting attention to arbitrary local neighborhoods, as done e.g., in criss-cross attention (Huang et al. 2019). To achieve this, suggest unrolling the sparse encod- ing mechanism in order to induce sparse attention maps through multiple layers of attention. We conjecture this may not only improve self-attention-based architectures through the of sparse regularizers on the attention coefficients, but also improve subspace clustering methods by using self-attention, as recently proposed in (Zhang et al.) (0021b). This could also allow one to extend sub- space clustering methods to nonlinear manifolds by stacking multiple layers of self self-expressivensss.
2
TRANSFORMERS, ATTENTION AND SELF-ATTENTIC
2.1 TRANSFORMER
Feed Forward
The transformer architecture was originally designed for processing data sequences, e.g., a sequence of words in a sentence. As shown in Figure[] each element of the sequence is first mapped to vector space through a suitable embedding, e.g., a Word2vec embedding of a word. Since the architecture does not depend on the position and order of the input se- quence, a positional encoding is added to the each input embedding. The resulting input tokens are then processed by multi-head attention layer. This layer computes output tokens as linear combinations of input tokens weighted by attention coefficients designed to capture long-range interac- tions among input tokens, such as word associations. The output tokens are then processed by residual connection followed by layer normalization, feed-forward network such as an MLP, and another residual connection and normalization layer. Therefore, the main component of the transformer architecture is the (multi-head) attention layer, which we describe next.
Norr Mult-Head Attention
Positional
Encoding
Inout Embedding
Inputs
Figure/ 1: Transformer encoder architecture Vaswani et al. (2017).
2

---

Under review as a conference paper at ICLR 2022
2.2 ATTENTION
Matsuul
As illustrated in Figure 2 the atlention layer is designed to capture long- range interactions among three types of input tokens: queries. keys and values. It does so by comparing queries to keys to produce set of attention coefficients, which are then used generate linear combinations of the val- ues. Specifically, let us denote the queries by matrix Q = !q...... 9N RdxN,, the keys by matrix K = [ki.... kN2 RdxN=, and the corre- sponding values by matrix = 1i -......, UN. Rd.xM, The attention layer computes an attention coefficient Ci = attn(k,, Q)) E [0, 1] for each key-query pair and returns a linear combination of the values as follows:
SonMaxx
Mask top1)
Scnklo
MorMil
Figure 2: Scaled
dot product attention Vaswani et al. 2017
No
3j
U.Cij or Z = VC, where C = attn K, Q) E [0,,1|
(1)
Intuitively, the attention coefficient Cij measures the importance of key k; for representing query qj and the representation 2j combines the values v; that are most important for Qj. The are many possible choices for the attention mechanism, including additive attention, multiplicative attention and dot product attention. A common choice is scaled dor product attention, which applies a softmax operator to the dot product of keys and queries scaled by the square root their dimension, i.e.:
K QTQ,
cxp(k: q, /
C softmax
Vd E. exp(k, g/VV)
Since the coefficients are non-negative and add up to one, 2j is a convex combination of the values. Let us illustrate the intuition behind attention using the following (overly simplified) examples:
1. Suppose we would like translate sentences from French to English. Let qj be feature embedding for the jith word of a sentence in French, and let k; v, be an embedding for the ith word of the corresponding sentence in English. Ideally, the attention mechanism should be designed such that the coefficient Gjj is large (Cij == 1) only for key-query pairs (i.j) that correspond to the translation of French word i into English word j. in which case the output to French query qj will be its translation into English 2;
2. Suppose we are given an image-caption pair and we would like to find which regions in the image corresponds each word in the caption. Assume also have collection of bounding boxes extracted from the image, c.g., using an object detector. Let the queries be feature embeddings for the words in the caption and the keys and values be CNN features extracted from the bounding boxes. Ideally, the attention mechanism should be designed such that Cıj is large when the box corresponds to word j. That is, the attention mechanism is designed to tell us which regions to pay attention to for each word.
Of course, in order for multilingual word embeddings to align with each other, or for word embed- dings match image features, both features need to be mapped to common latent space through a learnable transformation. We discuss such mappings in the next subsection in the context self- attention, but such mapping also apply here.
2.3 SELF-ATTENTION
Let X [.,,.... NN E DDNN denote a set of data tokens, such as words or image patches. The goal of self-attention is to capture long-range interactions among such tokens. Such interactions are captured by first transforming these tokens into keys, queries and values via learnable coefficient matrices Wx E RdxD We RdxD and Wy E Rdd respectively, as follows:
K = WR X E R Q = =W@x R and V= Wy X E xd
(3)
Then, we can define a set of transformed tokens using attention, e.g.:
= /softmax(K Q/vd)..
(4)
Let us illustrate the intuition behind self-attention using the vision transformer (ViT) proposed in Dosovitskiy et al. 2020). As shown in Figure 2.3 the VIT divides an input image into a collection
3

---

Under review as a conference paper at ICLR 2022
of patches and maps those patches to set of vectors via a learnable linear projection. Each projected patch is augmented with positional encoding for the location of the patch in the image. Since VIT is designed for image classification, an additional (zero) token is added the input of the trans- former. This token is expected to capture class information and learned during train- ing. The transformer encoder processes all these tokens using self-attention. Specifi- cally, new tokens are formed as linear com- binations of patches weighted by attention coefficients that capture relationships among image patches. Moreover, attention coeffi- cients relating the class token to patch tokens are expected to capture which patches to pay attention to in order to classify the image. The output class token is then passed through an MLP head to pro- duce class probabilities. The network parameters (input class token, patch projection, self-attention weights, encoder MLP, MLP head) are learned using a cross-entrops loss for classification.
Class Find Bull
Head
Transformer Encoder
Patch + Position Embredding
00
Eatr icanablc [eloss] enbelking
Linear Projection Flattened Putches
Figure 3: VIT architecture (Dosovitskiy al.
2020
2.4 MASKED ATTENTION AND SPARSE ATTENTION
As discussed in the introduction, much of the success of attention- architectures is attributed to the fact that attention layers capture long-range interactions among data tokens via attention co- efficients that are global and adapted the input data at test time. However, the use of the softmax operator often leads to dense attention maps, whose computation can be both memory and computa- tionally intensive. Moreover, in applications such as document summarization, question answering or visual grounding, the attention maps are expected to be sparse. One approach to addressing this issue is to restrict non zero attention coefficients to certain patterns, such as the criss-cross pattern proposed in (Huang et al.) 2019). In the architecture shown in Figure 2 this is implemented via masks, hence the name masked attention. However, pre-defining local attention maps might miss important long-range interactions. As an alternative, |Mrrinns & Astudillo (2016) propose sub- stitute the softmax operator by sparsemax operator, which directly induces sparse attention maps. However, it is not clear why doing so would automatically lead selecting tokens that are more informative. This motivated He et al. (202I) to propose heuristics for combining attention maps in order to select informative tokens for fine-grained recognition. Overall, rigorous method for inducing sparsity while maintaining the most informative long-range interactions remains elusive.
3 KERNEL REGRESSION, NON-LOCAL MEANS DENOISING AND ATTENTION
We begin with what arguably is one of the carliest incarnations of the idea of aelf-attention, namely kernel regression (Nadaraya 1964 Watson 1964). Interestingly, kernel regression is also at the root of a well-known image denoising algorithm, namely non-local means (Buades et al. 2005). which
show is strongly connected to the vision transformer (ViT) (Dosovitskiy et al. 2020).
3.1 KERNEL REGRESSION
The connection between attention and kernel regression was recently pointed out in Chaudhari et al. (019);; Zhang et al. (202 Kernel regression (Nadaraya 1964 Watson 1964 is non-parametric method for fitting function f: X' + y to samples ((x), j= drawn from X' x >V, which uses a
kernel density estimator to approximate the minimum wwwe--suuaaeee-eeeeeeee Specifically, given kernel : X' x X + [adaaaaaay 1964) and Watson (964) show that one can estimate f(x)) weighted combination of the values of y, i.e.
predictor f(x) = E(y aa:).
N f(x) = Σ a( 2,) = Σ 1=1
<(z, 2;)
yj.
(5)
E
((x,
J=1
Intuitively, the weighting function (xrr, 2r,) encodes the relevance of my for predicting (xx)
4

---

Under review as a conference paper at ICLR 2022
When is a Gaussian kernel, k( (zy) exp(
||
mu-=e 2x
). the expression in equation
reduces to
N
||
N
exp(
x x. yy
f(x)
20r
3)
softmax
(6)
| 1
20
==1 exp(
26
j=1
Therefore, Nadayara- Warson regression is an attention mechanism where the query is = æ, the keys are k; = z.. the values are v, = yj. and the attention function is softmax applied minus the normalized squared distance between query and key. Further assuming that keys and queries are normalized as ||a||| = | so that ||:: æ3112 attention:
2(1 x T xz)) yields scaled dot product
expl
a 20 19
f(x) =
yj
softmax(
j=1 Li=1 expl
Despite this obvious connection, we note that kernel regression with the Gaussian kernel is local attention mechanism that is unable to capture general long-range interactions. This is because the at- tention weights depend upon the distance between the key and the query. which is adapted using only one tunable parameter: a. When is very small, although all pairwise interactions are computed, large interactions occur only in a local neighborhood, which results in a local attention mechanism. On the other hand, when is very large all weights are similar and get f(x) R N Σ yj. which is clearly not an effective attention mechanism. Therefore, the key advantage of attention with respect kernel regression that it incorporates learnable linear transformations for both key and queries. Specifically, if we let = W x and k, = Wæy, we obtain q Kj = x W Way. In order for kernel regression to achieve such a learnable dot product, it would need to use a Gaussian kernel with full covariance matrix E, and learn the resulting dot product which is given by x _ x E-'ny.
More generally, observe that the expression in equation nisms by choosing different kernel function 6. For example, the Gaussian, Laplace and Wasserstein kernels are all members of the exponential family, as they are defined as the exponential of minus a squared distance, i.e., k(q, k) = exp( -distds (q. )) In this case, the resulting attention mechanism attn(q q. k) = softmax( - dist(q q. k)²) is defined based on a notion of similarity (Graves et al. 2014). On the other hand, it is not clear if all existing attention mechanisms (e.g.. additive attention) can be written in terms of a kernel.
used define new attention mecha-
3.2 NON-LOCAL MEANS DENOISING
As the name suggests, image denoising methods aim remove noise in an mage. The most basic image denoising method is based on computing the average intensity of a set of neighboring pixels. Typically, local Gaussian weighted average is used. Specifically, if æ, denotes the 2D coordinates of pixel j and yj denote its intensity or RGB values, the denoised image at pixel x takes the form in equation 5 Since a is typically chosen to small (say 3-11 pixels) and Gaussian weights decay very quickly with the distance ||= æzi- ll. it is customary to restrict the sum in equation 5 to neighborhood æe of size RJ 3o. In this case, the sum becomes a convolution with a Gaussian filter. Therefore, classical denoising is a local attention mechanism with queries and keys denoting pixel locations (i.c., q, = k,- x,) and values denoting image intensities (i.c., v2 = yz).
Non-local means introduces two key modifications to classical image denoising. First, it computes the weighted average of the intensities of all pixels, not just of a local neighborhood of x, as in equation [5] Second, it uses Gaussian kernel based on the intensity value y, rather than the pixel location Zj. This allows the algorithm to be non-local in that it finds other (possibly far away) pixels with similar intensities. Specifically, in its simplest form, non-local means denoises the image
1l- 20
exp(
f(x)
y
(8)
exp(
y/ M.
Therefore, this simplified form of non-local means denoising is self-attention mechanism with queries, keys and values denoting image brightness (i.e., 4; = k, = Dj = y₁).
A slightly more general form of the non-local means algorithm computes a Gaussian kernel not on the intensities y and yy of a single pixel, but on the intensities of patches centered at pixels æ and æ. respectively. This allows the algorithm attend to distant patches that are similar and hence
5

---

Under review as a conference paper at ICLR 2022
useful for denoising. Therefore, non-local means denoising is attention mechanism where the queries and keys are the intensities image patches and the values are the intensities of the central pixel. This connection had been noted in Wang al. (2018), but surprisingly it is not mentioned in Dosovitskiy et al., 2020). Indeed, notice that the steps of non-local means are equivalent to:
1. Extract a set of overlapping patches from the image.
2. Flatten these patches.
3. Apply attention mechanism with the keys and queries being the flattened patches and the values being the intensity of their central pixel.
Therefore, non-local means denoising closely related to the vision transformer, except that (a) there is additional classification token, (b) the projection of patches is fixed the identity rather than learned, (c) no positional encoding is added to the embedded patches, and (d) a single-head head and single-layer self-attention mechanism is used without normalization or fully connected layers.
4 LOCALLY LINEAR EMBEDDING (LLE) AND LOCAL SELF-ATTENTION
In this section, show that LLE learns low-dimensional representation of a dataset by using masked local self self-attention mechanism. Specifically, we show that LLE coefficients can be inter- preted as local attention weights with masks defined by the nearest neighbors. We note that LLE coefficients are not constrained to be nonnegative, thus allowing for both posítive and negative atten- tion, and LLE coefficients depend explicitly on multiple data tokens, unlike additive attention and scaled dot product which depend only on a pair of tokens (except for softmax). Finally, we show that LLE's training objective can be interpreted as a fill the blanks supe-supe learning objective.
4.1 LOCALLY LINEAR EMBEDDING
Let us first recall that LLE aims to learn locally- locally-linear low-dimensional embedding {u,} Rd of a given data set { C RD, where is the data dimension and d D is the embedding dimension. LLE computes this low-dimensional embedding by first expressing each data point æ; as an affine combination of K-nearest neighbors, i.e., by finding coefficients Gjj E such that z ~ EieN, Z,Cij and EiEN, Cj 1, where N2 C. [I....,N] .N is the set of K -nearrsst neighbors of z.. More specifically, LLE finds the coefficients by minimizing the reconstruction error
N
min
Ø - Σ 2. iEN
s.t.
cy=1 vj= N. REN
Once these coefficients have been found, LLE finds a dow-dimensional representation that is centered at the origin, has unit covariance, and minimizes the same reconstruction error, i.e.
N
N
min
yick 12 s.t.
Σセ =0
and
y,u y =I
(10)
VEN,
1=1
4.2 LLE VERSUS LOCAL-ATTENTION
In order show that LLE uses masked local self atff-attention mechanism, observe that the coefficient Gjj in the expression æj Re ΣiEN, 22Cij can be interpreted as an attention weight that measures the contribution of point e; point E,. Specifically, note that the optimization problem in equation 9 can decoupled as optimization problems, one for each zy. and that the optimal coefficients for æy are a function of the query 2; and the keys (ar)ee, i.e., hey,,N, = f(x,, JaN,,, | All other coefficients Jeiy,, are set to zero, thus the nearest neighbors define a local attention
'If jı, .j.j are the indices the K-NN xy, e, = [e Cj.jj..... "r T E R² is its vector attine coefficients and G,- [odd] E I x is its local Gram matrix defined g (x, xx," (x: x,) if
G.
æ; and œy that are K- K-NN of æy, then the optimal solution is C 166

---

Under review as a conference paper at ICLR 2022
mask. Note also that the constraint in equation 9 ensures the weights add up 1 without requiring softmax post-procces processs..... Finally, notice that the training objective in equation Dis fill in the blanks objective, where the nearest neighbors of zj, { are used to predict the missing token æy.
Despite these similarities between LLE and existing attention mechanisms, there are some important differences. First, most existing attention mechanisms compute a score function applied query-key pair and then apply the softmax function so that attention weights are between 0 and 1. In contrast, LLE coefficients are not constrained be nonnegative, thus allowing for both positive and negative attention. Moreover, LLE coefficients depend on both the query and multiple keys. Another difference, perhaps the most important one, is that in most existing attention mechanisms Cij is a parametrized function of the query-key pair whose weights are learned during training. In sharp contrast, L.E learns the values of Gj directly, which makes it more difficult to evaluate the coefficients for new data, as the optimization problem in equation Saaaaionnnnete needs to be solved anew.
single
Despite these differences, we note many of the key ingredients of attention (key, query, value, mask) were already present in the original LLE formulation, albeit for different purposes. In particular, LLE based on the idea that each query attends its nearest neighbors by writing itself as an affine combination of such neighbors. The attention weights thus capture the local geometry of the data manifold and are hence used to find the low-dimensional embedding as per equation I0
5 SUBSPACE CLUSTERING, SELF-EXPRESSIVENESS AND SELF-ATTENTIO
A key limitation of LLE is that its local neighborhood is pre-specified, so a data point cannot attend to any other point. In this section we show that this issue is resolved by self-expressivenss (EI- hamifar & Vidal, 2009: 2013 Vidal et al. 2016), which connects every point to every other point and uses sparse regularization to reveal which points to attend to. Specifically, we show that self- expressiveness based subspace clustering methods such sparse subspace clustering (Elhamifar
& Vidal 2009 2013: Wang & Xu 2013), low-rank subspace clustering (Liu et al.) 2010 Vidal &
Favaro 2014), least squares regression (Lu al. 2012) and extensions (Wang al. 2013 compute
a data affinity using a global masked self-attention mechanism where the queries, keys and values are the data points to be clustered, and the self-expressive coefficients of a data point are designed to attend to other points in the same subspace. We note, however, that self-expressive coefficients are not constrained be nonnegative, thus allowing for both positive and negative attention. We also show that self- eeff-expressive coefficients are global in that they truly depend on multiple data points, unlike most attention mechanisms that depend only on a pair of tokens (except for softmax). Finally, we show that the subspace clustering training objective can be interpreted as a fill in the blanks self- supervised learning objective where each data point is regressed with respect to all other data points.
5.1 SUBSPACE CLUSTERING AND SELF-EXPRESSIVENESS
Subspace clustering refers to the problem of clustering data drawn from a union of subspaces. Self- expressiveness based methods solve this problem by expressing each data point linear combi- nation of all other data points. The resulting self-expressive coefficients reveal information about which points belong to the same subspace, hence they can be used to define suitable data affinity matrix. The clustering of the data is then obtained by applying spectral clustering to such an affinity.
More formally, let X .......; : NN be of points drawn from a union of n subspaces of RD of dimension d < D which we wish to cluster. Assume that the data from each subspace is sufficiently rich so that any points from one group span the subspace associated to that group. Then, each data point xy can be expressed as a linear combination of d other points in its own subspace. That is, for all j -l..., N, there exist at most d non-zero coefficients Cjj E R such that:
3j =
Σ BiSiy or X XC and diag(C) = O, i8
(1I)
where C' E N is the matrix of coefficients. Notice that in the above constraint data points are expressed as linear combinations of each other, hence the name relf-expressiveness.
Since our goal is to use the self exffeexxressive coefficients to define an affinity matrix for clustering the data, ideally the coefficients should have the property that Cij * only if points æ. and æy are in
7

---

Under review as a conference paper at ICLR 2022
the same subspace. Coefficients that satisfy such a property guaranteed to exist since a point can always be expressed in terms of d points in its own subspace. Moreover, if d < N, i.c. the subspaces are dwwddmmesionall and the number of data points is sufficiently large. such coefficients are sparse. This motivates the sparse subspace clustering objective (Hlhamifar & Vidal 2009)
min ||, (o.))
Σ x.cy
Σ lagle
min C:ding(C)
|X - XCI X|1
(12)
where the first term measures how well data point reconstructed in terms of other data points, the second term uses & regularization to encourage sparsity, and X > 0 is a regularization parameter. More generally, one can use other regularizers O and write the objective in terms of the matrix C
min C
X - XCI| + XO(C).
(13)
Once the coefficients have been computed (see next subsection), it is common to select the largest nonzero coefficients to induce additional sparsity and to normalize the columns of C so that they add up to one (Elhamifar & Vidal 2013). Alternatively, once can add an é1-normalization constraints the optimization problem in equation [3] as commonly done in affine subspace clustering (Elhamifar & Vidal 2013 Li et al., 2018 You et al. 2019). Interestingly, it appears that sofmax normalization the coefficients has never used in the subspace clustering literature. Finally, given C, the data is clustered by applying spectral clustering to an affinity matrix that is often constructed by symmetrizing the absolute values of the self-expressive coefficients, i.c., A = C + |
5.2 SELF-EXPRESSIVE COEFFICIENTS FOR DIFFERENT REGULARIZERS
The least squares regression approach eu al. 2012 uses =(C)=||C] and gives closed form solution for C = [XT X + X X VI - where X UEV is the SVD of the data. Therefore, the self-expressive coefficient Cij a (E² (E + - is a weighted dot product of rows of V. When À is large enough we get scaled dot product of the data points
C
X.
(14)
The low-rank subspace clustering approach (Liu et al. 2010 Vidal & Favaro 2014 uses nuclear norm regularizer ((C)= = ||C'|, to induce low-rank coeffcients. The solution can be computed in closed form from the SVD of the data as C = VReLU, V where x (x) max(ι- X, 0). As before, this can be interpreted as a weighted dot product of rows V, except that some weights can be zero to induce low-rank.
The sparse subspace clustering approach (Elhamifar & Vidal, 2009 the E norm (CC) ||C'l1 to induce sparse coefficients. In this case, the coefficients cannot be computed in closed form. However, a common approach is to use the Iterative Shrinkage Thresh- olding Algorithm (ISTA) proposed by (Beek & Teboulle, 2009). which can be written as
2013 Wang & Xu 2013) uses
C++1 ReI.U,((1 ex X)C₁ +eX ReI.U,, (C₁, + ex (X XC,)), (15)
where e > a step size. We note that equation [5] is the point of the departure for the unrolling approach proposed in (Gregor & LeCun 2010).
which connects sparse coding with neural networks. In that approach, the iterates are interpreted activation functions of a neural network and the
Feed Forward
linear transformations (T (--ck x X) and X X as learnable weights.
Nx
XiaG Mutt-Hos Attention
As future research direction, suggest further exploring the connections between sparse subspace clustering and transformers via unrolling, which we extend subspace clustering nonlinear manifolds
conjecture will allow through the use of (deep) multi-layer attention models. More specifically, notice that we can partially re-interpret equation 15 as the update of one attention layer. This is because in equation [5] the term X X XC can be interpreted as applying attention Cj to input data X and then adding (negative) residual connection with the input X. Then, the multiplication by X in in equation 15 and the ReLU nonlinearity can be interpreted as the feedforward layer of the transformer. Of course, the analogy is not perfect because the addition of C₁ is not quite a residual connection.
Positional Encoding
Pnout Embeddiing
Inpute
Figure 4: Towards a sparse transformer?
We have neglected the constraint diag(C) 0 for case of exposition
8

---

Under review as a conference paper at ICLR 2022
5.3 SELF-EXPRESSIVENESS VERSUS
Notice from equation 1 that self-expressiveness can be interpreted as a self-attention mechanism where the query 4j zjj is expressed as a linear combination of all values v; 3; i 1,.... with attention coefficients Cij determined by the queries 1 2; and the keys K2 = Dy However, we note that cefffexxressive coefficients (SEC) are more general than self-attention coefficients.
SEC are not restricted to be nonnegative, allowing for both positive and negative attention.
2. SEC are not restricted to be an explicit function of a single key-query pair. For example, the closed form solution to least squares regression has a term of the form (AI + XX- which makes Cūj function of all key-query pairs. The only case where self-expressive coefficients yield an explicit function of a single key-query pair is when À is large that as per equation [4] which resembles scaled dot product attention.
3. SEC are not defined as function of the tokens parametrized by learnable weights. Instead, the coefficients are learned directly using an unsupervised loss. This is, however, a potential disadvantage of self-expressiveness. as it makes it difficult to compute coefficients at test time. This issue is addressed in (Zhang al. b02 by using learnable coefficients.
4. SEC are typically regularized to be sparse or low-rank. We argue that the use of sparse regularization in (Elhamifar & Vidal, 2009) 2013) to automatically select the most relevant coefficients is more principled way of handling a large number of tokens than restricting attention to arbitrary local neighborhoods, c.g., in criss-cross attention (Huang et al. 2019).
As a consequence, we argue that the key innovation of self-attention relative to self-expressiveness neither in its ability to capture global long-range interactions that are adapted the data in the ability to learn such interactions (something that self-expressivenett already does), but rather on the fact that attention mechanisms have been stacked into deep architectures and with multiple attention- heads in parallel. As suggested in the previous section, further exploring the connections between sparse subspace clustering and transformers via unrolling might lead to (deep) multi-layer subspace clustering models. Alternatively, one may use attention mechanisms to parametrize self-expressive coefficients, as recently suggested in (Zhang al. b021
5.4 SPARSE CODING AND SPARSE ATTENTION
The connections made between self-ex eeff-expressiveness and self-attention also suggest new directions towards improving transformers via sparse encoding. Specifically, recall that in standard sparse cod- ing, data point is expressed sparse linear combination of dictionary atoms A [a [....... aNl with coefficients c by solving the optimization problem
min y Acll3 + A||c||1-
(16)
Reinterpreting the data point y as the query and the dictionary A as the set of keys K, and solving the problem for multiple queries Q leads to attention mechanism of the form
Z VC where C = arg min
|| K + A||C"|1
(17)
C
Since solving sparse coding problem can be costly, we unroll sparse coding iterates and obtain:
Z = VCr where C++1 = (U- K)C₂ + e.' Q), k l, K. (18)
Observe that the update has rather interesting structure. The term K K is dot product self- attention, while the term K" Q is dot product attention. Therefore, the update equation combines standard attention and self-attention to produce a new sparse attention map.
CONCLUSIONS
We have shown that attention builds upon long history of prior work manifold learning and im- age processing, including methods such as kernel-based regression, non-local means, locally linear embedding, subspace clustering and sparse coding. In particular, we showed that many of the key ideas behind attention, such as its ability to capture global long-range interactions that are learned and adapted to the input, had already appeared in the literature. Therefore, the key innovations of attention mechanisms relative to prior art are the use of many learnable parameters, and multiple heads and layers.

---

Under review as a conference paper at ICLR 2022
Ethics Statement This work focuses understanding the principles behind transformers and connecting it to well established topics in machine learning research. The research conducted in the framework of this work raises no ethical issues any violations vis-a-vis the ICLR Code of Ethics.
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: 409.0447, 2014.
A. Beck and M. Teboulle. A fast iterative thinnkage-thresholdding algorithm for linear inverse prob- lems. SIAM Journal on Imaging Sciences, 2(1):183-202, 2009.
Antoni Buades, Bartomeu Coll, and Jean-Michel Morel. A non-local algorithm for image denoising. In IEEE Conference on Computer Vision and Pattern Recognition, 2005.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European Conference on Computer Vision, pp. 213-229. Springer, 2020.
Sneha Chaudhari, Varun Mithal, Gungor Polatkan, and Rohan Ramanath. An attentive survey of attention models. arXiv preprint arXiv:1904. 02874, 2019.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 27977, 2009.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions Pattern Analysis and Machine Intelligence, 35(11))2765-2888 2013.
Andrea Galassi, Marco Lippi, and Paolo Torroni. Attention natural language processing. IEEE Transactions Neural Networks and Learning Systems, 2020.
Siddhant Garg, Thuy Vu, and Alessandro Moschitti. Tanda: Transfer and adapt pre-trained trans-
former models for answer sentence selection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7780-7788, 2020.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv: 1410.5401, 2014.
arXiv preprint
K. Gregor and Y. LeCun. Learning fast approximations of sparse coding. In International Confer- ence on Machine Learning, pp. 399-406. Omnipress, 2010.
Ju He, Jie-Neng Chen, Shuai Liu, Adam Kortylewski, Cheng Yang. Yutong Bai, Changhu Wang, and Alan Yuille. Transfg: transformer architecture for ame-gerined recognition. arXiv preprint arXiv:2103.07976 2021.
Zilong Huang, Xinggang Wang, Lichao Huang, Chang Huang, Yunchao Wei, and Wenyu Liu. Cenet: Criss-cross attention for semantic segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 603-612, 2019.
Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. arXiv preprint arXiv:2101.00 169, 2021.
Chun-Guane MuunGGaag Li, Chong You, and René Vidal. On geometric analysis of affine sparse subspace clustering. IEEE Journal Selected Topics in Signal Processing, 1206):1200-153, 2018.
10

---

Under review as a conference paper at ICLR 2022
Guangean Liu, Zhouchen Lin, and Yingrui Yu. Robust subspace segmentation by low-rank repre-
sentation. In International Conference on Machine Learning, pp. 663-670, 2010.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprini arXiv: 1907. 1692, 2019.
Can-Yi i Lu, Hai Min, Zhong-Qin Qiu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. In European Conference on Computer Vision, pp. 347-360, 2012.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pp. 1614-1623. PMLR, 2016.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. arXiv preprint arXiv: 1806.00187 2018.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training (2018), 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv: 2019.
S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500);2323- 2326, 2000.
S. Roweis and L.. Saul. Think globally, fit locally: Unsupervised learning of low dimensional mani- folds. Journal of Machine Learning Research, 19-1155, 2003.
Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai. VI-bert: Pre-training of generic visual-linguistic representations. arXiv preprint arXiv: / 090800 2019.
Hao Tan and Mohit Bansal. Lxmert: Learning cross-modality encoder representations from trans- formers. arXiv preprint 1XXXv:19080074999 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Neural Information Processing Systems, pp. 1999-6008 2017.
René Vidal and Paolo Favaro. Low rank subspace clustering (LRSC). Pattern Recognition Letters, 43:47-61, 2014.
René Vidal, Yi Ma, and Shankar Sastry. Generalized Principal Component Analysis. Springer Verlag, 2016.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2018.
Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. In International Conference on Machine Learming, pp. 89 97, 2013.
Yu-Xiang Wang. Huan Xu, and Chenlei Leng. Provable subspace clustering: When LRR meets SSC. In Neural Information Processing Systems, 2013.
Geoffrey S Watson. Smooth regression analysis. Sankhya: The Indian Journal of Statistics, Series A, pp. 359-372, 1964.
11

---

Under review as a conference paper at ICLR 2022
Chong You, Chun-Guam Li, Daniel P. Robinson, and René Vidal. Is an affine constraint needed for affine subspace clustering? In IEEE International Conference on Computer Vision, 2019.
Aston Zhang, Zachary C Lipton, Mu Li, and Alexander J Smola. Dive into deep learning. arXiv preprint
2021a.
Shangzhi Zhang, Chong You, René Vidal, and Chun-Guang Li. Learning self- self-expressive network for subspace clustering. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021b.
Xizhou Zhu, Weijic Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai. Deformable detr: Deformable transformers for end-to-end object detection. arXiv preprint arX1::0010004/59, 2020.
12


Reviews:
[{"review_id": "swCV-kTWEPq", "reviewer": "Reviewer_K4hc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strengths:\n\n+    The paper does a literated survey of the prior work that has connection to self-attention. It offers various perspectives on the self-attention module, and it helps us slowing down our steps and really think about what's the real magic in self-attention and how can we improve it by taking inspirations from other problems and areas.\n+    The proposed directions for future work are quite interesting, including using self-attention for manifold clustering, and connecting sparse reconstruction with self-attention.\n+    The paper is easy to follow. \n\nWeaknesses:\n\nThe main concern for me is the contribution of this paper. The main body of the paper is dedicated to showing the relation between self-attention and prior arts.\n-    First of all, the relation between self-attention and kernel regression and non-local mean denoising has already pointed out by previous work, as cited by the authors. \n-    Second of all, the relation between self-attention and locally linear embedding and self-expression in subspace clustering seems not so close to me. For example, self-expression estimates the affinity of the points sampled from the same subspace. But could we assume that different words in a sentence are sampled from a low-dimensional subspace? Despite the similar form (weighted average of data points), self-attention and the prior arts are targeting at different problems, so I think it's not convincing to say that self-attention is somehow \"reinvented\" from previous algorithms.\n-    The paper proposes several conjectures on how self-attention could be improved or be applied to other problems. However, the authors didn't take a step further into any of them. The contribution would be much bigger if the authors could dive deep into one of the ideas to potentially improve self-attention or apply it in other problems. For example, the authors show that self-attention is related to non-local means and also to low-rank subspace clustering. It's well known that non-local means and low-rank subspace clustering both have the effect of removing certain noises in the data. Is it a possible way to explain that transformers are more robust than CNNs, as stated in recent works [1]?\n\n[1] Paul S, Chen P Y. Vision transformers are robust learners[J]. arXiv preprint arXiv:2105.07581, 2021.\n", "summary_of_the_paper": "This paper surveys several lines of prior work which has connection to the self-attention module in transformers. Specifically, the authors show that self-attention has the similar form with the kernel regression and non-local mean algorithm. They also demonstrate that locally linear embedding and self-expression algorithm for subspace clustering have the form of representing one data point by weighted sum of other data points, and thus are connected to the weighted sum of values in self-attention. Based on these observations, the authors argue that the innovation of self-attention is not modeling the long-range relation, which is also proposed in prior work, but the learnable parameters and the multi-head design. The authors also suggest several directions for future work, such as using self-attention for manifold clustering.", "summary_of_the_review": "The paper explains the relation between self-attention and several previous algorithms and its implications, offering different perspectives on the self-attention module. However, the contribution is lacking in both justifying if self-attention and prior arts are functionally similar or just similar in the form, and exploring how the relations explained in the paper can help us better design self-attention or apply it in other areas.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Lq5KkfWvc8C", "reviewer": "Reviewer_vLjt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "This is a review paper to discusses the relationships between the attentions and the traditional (coding) methods, including attention and kernel-based regression, masked attention and locally linear embeding, self-attention and self-expressiveness. \n\nves: \n+ The problem of the principles behind attention seems interesting. \n+ This paper is well-written and is easy to follow.\n+ The authors show some future directions on how to improve self-expressiveness using self-attention and vice versa.\n\nConcerns: \n- The title “attention: self-expression is all you need” seems too over-expression due to the following reason. The self-expression is that “each data point in a union of subspaces can be efficiently reconstructed by a combination of other points in the dataset.” (Elhamifar & Vidal 2009; 2013) This leads to the reconstruction loss in the Eq. (12). However, self-attention is to use itself to choose itself, that is, the calculation formula is defined in the Eq. (4), and it’s loss depends on the different tasks. It is clear that the self-attention does not need the self-expression or the self-expression is one case of the self-attention.\n- This paper discuses the three parts. Could you propose a unified form to cover all the three parts?\n- In the subsection 5.3, the authors note that self-expressive coefficients (SEC) are more general than self-attention coefficients. However, SEC still have some shortcomings.\n1) SEC must result in over-high time and space complexities because it considers self-expressiveness. Thus, the current SEC methods cannot apply into large-scale datasets.\n2) Although SEC are typically regularized to be sparse or low-rank, it is well-known that sparse or low-rank regularization lead to expensive costs. \n- In the subsection 5.4, the authors consider the Eq. (17) instead of the Eq. (4). I have two suggestions. \n1) Could you prove the equivalence between the Eq. (17,18) and (4)?\n2) Could you provide some rough experimental results to verify the effectiveness of the Eq. (18)?\n", "summary_of_the_paper": "This review paper tries to study the principles behind attention and its connections with prior art using the self-expression methods (e.g., kernel-based regression, non-local means, locally linear embedding, subspace clustering). ", "summary_of_the_review": "I recommend this score since this paper is to consider an interesting problem, some suggestions are hard to implement in deep models on large-scale datasets (millions), and there are no experimental results to support the arguments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ht7y8Orn2pr", "reviewer": "Reviewer_Upbz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "In general, this is an interesting paper with good insights. It provides holistic views towards one of the central parts of deep learning, attention, through many excellent learning methods developed before. However, I would not like to recommend acceptance because of the lack of theoretical and practical evidence to support and verify some basic claims as well as substantially ignore the progress within the deep learning community to bridge the attention method with prior arts listed in this paper.\n\nIt would be a successful work for the ICLR blog track but not the ICLR main conference. Many ideas are clearly of merit to inspire further research but not formal and supported enough as scientific work. I sincerely recommend submitting this work to the ICLR blog track this year, if the authors can sufficiently revise the writing style to suit a blog.\n\n## Strengths\n\n1. The paper is well-written, especially for explaining the key ideas of previous works. The intuition behind the connection between attention and prior arts is clear.\n2. The insights provided by this paper are valuable even though not novel enough. Especially for many researchers starting their careers after the booming of deep learning, the discussion sketches a holistic and detailed perspective towards the essence of many previous works and how they are related to attention. This will be of interest to the community.\n\n## Weaknesses\n\n1. It is hard to define the scientific value of this paper because it fails to provide theoretical claims and misses experimental results to verify its implication based on self-expressiveness, i.e., the sparse attention mechanism inspired by the optimization of sparse coding. A solid work requires a systematically organized logic line supported by theorems or precise experiments to verify some ideas. Also, integrating these principled methods into neural networks is not such easy, especially due to the curse of training issues, computation budget, etc.\n2. Although this work itself sufficiently discusses the correlation between attention and classic methods and clearly explains why these classic methods are related to attention or vice versa, it ignores many related works in the community that have essentially similar ideas or contributions. A simple list is as follows.\n\n   For bridging attention with classic methods, \n   - [1] Lu, J., Yao, J., Zhang, J., Zhu, X., Xu, H., Gao, W., Xu, C., Xiang, T., & Zhang, L. (2021). SOFT: Softmax-free Transformer with Linear Complexity. ArXiv, abs/2110.11945.\n   - [2] Xiong, Y., Zeng, Z., Chakraborty, R., Tan, M., Fung, G.M., Li, Y., & Singh, V. (2021). Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention. AAAI.\n   - [3] Geng, Z., Guo, M., Chen, H., Li, X., Wei, K., & Lin, Z. (2021). Is Attention Better Than Matrix Decomposition? ICLR.\n   - [4] Li, X., Zhong, Z., Wu, J., Yang, Y., Lin, Z., & Liu, H. (2019). Expectation-Maximization Attention Networks for Semantic Segmentation. ICCV.\n\n   The framework by Hamburger[3] is strongly correlated with the self-expressiveness in this work.\n\n   Considering the close connection between attention and Graph neural networks, here is a list of GNN papers inspired by classic methods.\n   - [5] Yang, Y., Liu, T., Wang, Y., Zhou, J., Gan, Q., Wei, Z., Zhang, Z., Huang, Z., & Wipf, D.P. (2021). Graph Neural Networks Inspired by Classical Iterative Algorithms. ICML.\n   - [6] Liu, X., Jin, W., Ma, Y., Li, Y., Liu, H., Wang, Y., Yan, M., & Tang, J. (2021). Elastic Graph Neural Networks. ICML.\n   - [7] Zhu, M., Wang, X., Shi, C., Ji, H., & Cui, P. (2021). Interpreting and Unifying Graph Neural Networks with An Optimization Framework. Proceedings of the Web Conference 2021.\n   - [8] Huang, Q., He, H., Singh, A., Lim, S., & Benson, A.R. (2021). Combining Label Propagation and Simple Models Out-performs Graph Neural Networks. ICLR.\n   - [9] Wang, H., & Leskovec, J. (2020). Unifying Graph Convolutional Neural Networks and Label Propagation. ArXiv, abs/2002.06755.\n   - [10] Wilder, B., Ewing, E., Dilkina, B.N., & Tambe, M. (2019). End to end learning and optimization on graphs. NeurIPS.\n\n   Optimization-inspired methods [5,6,7] are strongly related as well.", "summary_of_the_paper": "This paper studies the correlation between the attention mechanism and many prior arts. Heuristically, this paper links the currently hot topic, attention mechanism, with many milestones works in the past decades before the deep learning era, including subspace learning, sparse coding, kernel regression, non-local means, etc. Among these classic methods, many can be formulated as optimization problems. The minimizer to the optimization problem can be treated as the output of attention modules, and the optimization algorithm can be understood as the ``architecture'' of attention. Specifically, this work highlights the potential of sparse coding in designing the sparse attention mechanism when considering the self-expressiveness in subspace learning is essentially profoundly connected to the formulation of self-attention.", "summary_of_the_review": "It would be a successful work for the ICLR blog track but not the ICLR main conference. Many ideas are clearly of merit to inspire further research but not formal and supported enough as scientific work. I sincerely recommend submitting this work to the ICLR blog track this year, if the authors can sufficiently revise the writing style to suit a blog.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper points out connections between the self-attention module in transformers and some prior art, including kernel regression, the non-local mean algorithm, locally linear embeddings, and the self-expression algorithm for subspace clustering. Based on these observations, the authors argue that the innovation of self-attention is not modeling the long-range relation, which is also proposed in prior work, but the learnable parameters and the multi-head design. The authors also suggest several directions for future work, such as using self-attention for manifold clustering.

Reviewers pointed out several weaknesses with this paper: that some connections (e.g. connection to kernel regression) had been pointed out before, that the relation between self-attention and locally linear embedding and self-expression in subspace clustering is a bit nuanced, as pointed out by one of the reviewers, and that while some speculative future directions might be interesting, the paper falls short in actually trying some of them out empirically, or building a proof-of-concept. 

In the discussion period, the authors pointed out that this is a position paper (which unfortunately was not expressed so assertively in their submission), which according to their view liberates them from digging deeper and test empirically some of these connections and speculative directions. According to the authors, a core contribution of their position paper is that "it expresses the opinion that the original attention paper failed to cite and acknowledge that attention mechanisms build upon a series of prior works in sparse coding, subspace clustering, and locally linear embedding." 

There are no specific guidelines to review position papers at ICLR that I know of, but I will base my assessment on the assumption that a good position paper should:
- provide a good historical perspective of a subject
- connect previously unrelated lines of work in non-obvious ways
- inspire the research community to look at new directions.

While a good position paper can be extremely valuable and enlightening, I am not convinced that this particular paper achieves either of the goals above, and therefore it is my opinion that it does not deserve publication at ICLR. 

As pointed out both by the authors and the reviewers, the connection between self-attention and kernel regression and non-local mean denoising is not new, and so it is not an original contribution of this paper. The relation between self-attention and locally linear embedding and self-expression in subspace clustering appears to be new, but this relation is a bit nuanced, as pointed out by one of the reviewers. 

The tone of this position paper is that some of these connections were missing in the original attention paper -- the authors say "attention did not properly acknowledge prior art" in one of their responses (it is not clear if they are referring to Bahdanau et al.'s attention paper or to Vaswani et al.'s transformer paper). However, the historical perspective of how attention mechanisms came to be seems to be missing from this position paper -- attention has been proposed by Bahdanau et al. for machine translation, inspired by the idea of word alignment that has been prevalent in machine translation for decades. Later, in the transformer paper, self-attention was suggested as an alternative to recurrent and convolutional models for machine translation (note that self-attention has been used before the transformer paper, see e.g. [1]). While a theoretical connection with kernel regression etc. exists, this was not related to the original motivation of these works. There are many ways of arriving at the same construction! And given the simplicity of attention mechanisms it doesn't surprise me that connections with other lines of research exist. Had they been noticed, they would probably be a parenthesis in the original papers, because attention is derived there in a much more direct way (this doesn't mean that the connections aren't interesting, but that they are not _essencial_ to the construction). 

In their response, the authors dismissed a constructive suggestion from one of the reviewers which in my opinion would have strengthen this paper -- the connection with graph neural networks. If the point of the paper is to point out past research that connects fundamentally to the idea of attention mechanisms, why leaving this out?

In sum, in my view this paper lacks the rigor, the insight, and the historical perspective that should characterize a strong position paper, and as such I cannot recommend acceptance. I strongly suggest that the authors take into account some of the insightful suggestions given by the reviewers in future iterations of their work. 

[1] Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model. In Empirical Methods in Natural Language Processing, 2016.
Decision: Reject