# Why self-attention is Natural for Sequence-to-Sequence Problems? A
Perspective from Symmetries

Chao Ma, Lexing Ying
Department of Mathematics
Stanford University
Stanford, CA 94305, USA
{chaoma<EMAIL_ADDRESS>
###### Abstract

In this paper, we show that structures similar to self-attention are natural
to learn many sequence-to-sequence problems from the perspective of symmetry.
Inspired by language processing applications, we study the orthogonal
equivariance of seq2seq functions with knowledge, which are functions taking
two inputs—an input sequence and a “knowledge”—and outputting another
sequence. The knowledge consists of a set of vectors in the same embedding
space as the input sequence, containing the information of the language used
to process the input sequence. We show that orthogonal equivariance in the
embedding space is natural for seq2seq functions with knowledge, and under
such equivariance the function must take the form close to the self-attention.
This shows that network structures similar to self-attention are the right
structures to represent the target function of many seq2seq problems. The
representation can be further refined if a “finite information principle” is
considered, or a permutation equivariance holds for the elements of the input
sequence.

##  1 Introduction

Neural network models using self-attention, such as Transformers Vaswani et
al. (2017), have become the new benchmark in the fields such as natural
language processing and protein folding. Though, the design of self-attention
is largely heuristic, and theoretical understanding of its success is still
lacking. In this paper, we provide a perspective for this problem from the
symmetries of sequence-to-sequence (seq2seq) learning problems. By identifying
and studying appropriate symmetries for seq2seq problems of practical
interest, we demonstrate that structures like self-attention are natural for
representing these problems.

Symmetries in the learning problems can inspire the invention of simple and
efficient neural network structures. This is because symmetries reduce the
complexity of the problems, and a network with matching symmetries can learn
the problems more efficiently. For instance, convolutional neural networks
(CNNs) have seen great success on vision problems, with the translation
invariance/equivariance of the problems being one of the main reasons. This is
not only observed in practice, but also justified theoretically Li et al.
(2020b). Many other symmetries have been studied and exploited in the design
of neural network models. Examples include permutation equivariance Zaheer et
al. (2017) and rotational invariance Kim et al. (2020); Chidester et al.
(2019), with various applications in learning physical problems. See Section
2.1 for more related works.

In this work, we start from studying the symmetry of seq2seq functions in the
embedding space, the space in which each element of the input and output
sequences lie. For a language processing problem, for example, words or tokens
are usually vectorized by a one-hot embedding using a dictionary. In this
process, the order of words in the dictionary should not influence the meaning
of input and output sentences. Thus, if a permutation is applied on the
dimensions of the embedding space, the input and output sequences should
experience the same permutation, without other changes. This implies a
permutation equivariance in the embedding space. In our analysis, we consider
equivariance under orthogonal group, which is slightly larger than the
permutation group. We show that if a function $f$ is orthogonal equivariant in
the embedding space, then its output can be expressed as linear combinations
of the elements of the input sequence, with the coefficients only depending on
the inner products of these elements. Concretely, let $X\in\mathbb{R}^{d\times
n}$ denote an input sequence with length $n$ in the embedding space
$\mathbb{R}^{d}$. If $f(QX)=Qf(X)$ holds for any orthogonal
$Q\in\mathbb{R}^{d\times d}$, then there exists a function $g$ such that

$f(X)=Xg(X^{T}X).\vspace{-1mm}$

However, the symmetry on the embedding space is actually more complicated than
a simple orthogonal equivariance. In Section 3.2, we show that the target
function for a simple seq2seq problem is not orthogonal equivariant, because
the target function works in a fixed embedding. To accurately catch the
symmetry in the embedding space, we propose to study seq2seq functions with
knowledge, which are functions with two inputs, $f(X,Z)$, where
$X\in\mathbb{R}^{d\times n}$ is the input sequence and
$Z\in\mathbb{R}^{d\times k}$ is another input representing our “knowledge” of
the language. The knowledge lies in the same embedding space as $X$, and is
used to extract information from $X$. With this additional input, the symmetry
in the embedding space can be formulated as an orthogonal equivariance of
$f(X,Z)$, i.e. $f(QX,QZ)=Qf(X,Z)$ for any inputs and orthogonal matrix $Q$.
Intuitively understood, in a language application, as long as the knowledge is
always in the same embedding as the input sequence, the meaning of the output
sequence will not change with the embedding. Based on the earlier theoretical
result for simple orthogonal equivariant functions, if a seq2seq function with
knowledge is orthogonal equivariant, then it must have the form

$f(X,Z)=Xg_{1}(X^{T}X,Z^{T}X,Z^{T}Z)+Zg_{2}(X^{T}X,Z^{T}X,Z^{T}Z)$

If $Z$ is understood as a parameter matrix to be learned, the following subset
of this representation,

$f(X,Z)=Xg(X^{T}Z),$

is close to a self-attention used in practice, with $Z$ being the
concatenation of query and key parameters. This reveals one possible reason
behind the success of self-attention based models on language problems.

Based on the results from orthogonal equivariance, we further study the
permutation equivariance on the elements of the input sequence. Under this
symmetry, we show that seq2seq functions with knowledge have a further reduced
form which only involves four different nonlinear functions. Finally,
discussions are made on the possible forms of $g$ (or $g_{1}$ and $g_{2}$) in
the formulations mentioned above. Based on the assumption that these functions
are described by a finite amount of information (although their output sizes
need to change with respect to the sequence length $n$), we reason that
quadratic forms with a nonlinearity used in usual self-attentions is one of
the simplest choice of $g$. We also discuss practical considerations that add
the complexity of the models used in application compared with theoretical
forms.

##  2 Background and related work

###  2.1 Neural networks and symmetries

Implementing symmetries in neural networks can help the models learn certain
problems more efficiently. A well-known example is the success of
convolutional neural networks (CNNs) on image problems due to their
(approximate) translation invariance LeCun et al. (1989). Many types of
symmetries have been explored in the design of neural networks, such as
permutation equivariance and invariance Zaheer et al. (2017); Guttenberg et
al. (2016); Rahme et al. (2021); Qi et al. (2017a; b), rotational equivariance
and invariance Thomas et al. (2018); Shuaibi et al. (2021); Fuchs et al.
(2020); Kim et al. (2020), and more Satorras et al. (2021); Wang et al.
(2020b); Ling et al. (2016a); Ravanbakhsh et al. (2017). Some works deal with
multiple symmetries. In Villar et al. (2021), the forms of functions with
various symmetries are studied. These networks see many applications in
physical problems, where symmetries are intrinsic in the problems to learn.
Examples include fluid dynamics Wang et al. (2020a); Ling et al. (2016b); Li
et al. (2020a); Mattheakis et al. (2019), molecular dynamics Anderson et al.
(2019); Schütt et al. (2021); Zhang et al. (2018), quantum mechanics Luo et
al. (2021a; b); Vieijra et al. (2020), etc. Theoretical studies have also been
conducted to show the benefit of preserving symmetry during learning Bietti et
al. (2021); Elesedy & Zaidi (2021); Li et al. (2020b); Mei et al. (2021).

###  2.2 self-attention

self-attention Vaswani et al. (2017); Parikh et al. (2016); Paulus et al.
(2017); Lin et al. (2017); Shaw et al. (2018) is a type of attention mechanism
Bahdanau et al. (2014); Luong et al. (2015) that attends different elements in
a same input sequence. It is the building block of a series of large language
models (e.g. Devlin et al. (2018); Brown et al. (2020); Raffel et al. (2020)),
and is under extensive research. See Bommasani et al. (2021); Niu et al.
(2021) for reviews.

As a preparation for later studies, we briefly summarize the structure of
(multihead) self-attention. A self-attention is a seq2seq operator which takes
a sequence of vectors as the input, and another sequence of vectors (of the
same size) as the output. Let $X\in\mathbb{R}^{d\times n}$ be the input
sequence with length $n$. A self-attention computes the output using three
parameter matrices: the query parameters $W_{Q}\in\mathbb{R}^{d_{1}\times d}$,
the key parameters $W_{K}\in\mathbb{R}^{d_{1}\times d}$, and the value
parameters $W_{V}\in\mathbb{R}^{d\times d}$. Given the input $X$, a “query”
and a “key” is computed for every column of $X$ by multiplying with $W_{Q}$
and $W_{K}$, i.e. we compute $Q(X)=W_{Q}X\in\mathbb{R}^{d_{1}\times n}$ and
$K(X)=W_{K}X\in\mathbb{R}^{d_{1}\times n}$. Then, an attention matrix is
obtained by computing the inner product of all pairs of queries and keys:

$A(X)=Q(X)^{T}K(X)=X^{T}W_{Q}^{T}W_{K}X\in\mathbb{R}^{n\times n}.$

Next, a weight matrix is computed by applying softmax over rows of $A$, and
the output of the attention is obtained by a linear combination of the
“values”, $W_{V}X$, using rows in the weight matrix as coefficients. In
practice, $A(X)$ is usually scaled by a factor of $1/\sqrt{d_{1}}$, and a
residual connection is added, thus we have

$Attn(X)=X+W_{V}X\mathcal{S}_{r}\left(\frac{1}{\sqrt{d_{1}}}X^{T}W_{Q}^{T}W_{K}X\right)^{T}$
(1)

where $\mathcal{S}_{r}(\cdot)$ computes the softmax of an input matrix over
rows.

######  Remark 1.

In this paper we use $X\in\mathbb{R}^{d\times n}$ to denote sequences with
length $n$ in the space $\mathbb{R}^{d}$. Each column of $X$ is an element of
the sequence. In many works the same sequence is represented by an $n\times d$
matrix. The two representations are intrinsically equivalent.

The self-attention mechanism described above consists of one “head”, in the
sense that we have one query, key and value for each element of $X$. Similar
to the way that we add more neurons to a layer of a fully connected neural
network, we can add more heads to a self-attention, which gives a multihead
attention. For a multihead attention with $m$ heads, we have $m$ different
query, key, and value matrices, denoted by $W_{Q}^{(i)}$, $W_{K}^{(i)}$, and
$W_{V}^{(i)}$. $W_{Q}^{(i)}$ and $W_{K}^{(i)}$ are still $d_{1}\times d$
matrices, while $W_{V}^{(i)}$ are $d_{2}\times d$ matrices. Besides, in order
to still use the residual connection, an output parameter matrix
$W_{out}^{(i)}\in\mathbb{R}^{d\times d_{2}}$ is added for each head to
transform the value vectors in $\mathbb{R}^{d_{2}}$ into vectors in
$\mathbb{R}^{d}$. With these parameters, each head is similar to a single-head
self-attention:

$head_{i}(X)=W_{V}^{(i)}X\mathcal{S}_{r}\left(\frac{1}{\sqrt{d_{1}}}X^{T}(W_{Q}^{(i)})^{T}W_{K}^{(i)}X\right)^{T},$

and the output of the multihead attention is

$\displaystyle Attn_{m}(X)$
$\displaystyle=X+\sum\limits_{i=1}^{m}W_{out}^{(i)}head_{i}(X)$
$\displaystyle=X+\sum\limits_{i=1}^{n}W_{out}^{(i)}W_{V}^{(i)}X\mathcal{S}_{r}\left(\frac{1}{\sqrt{d_{1}}}X^{T}(W_{Q}^{(i)})^{T}W_{K}^{(i)}X\right)^{T}.$

######  Remark 2.

In a practical model like a Transformer, a fully-connected layer is sometimes
added after multihead attentions. The fully-connected layer is applied to each
element of the output sequence.

##  3 Orthogonal equivariance in the embedding space

In this section, we focus on the orthogonal equivariance in the embedding
space. We show that functions with such equivariance enjoy a representation
which takes a similar but more general form as self-attention. We start from a
theoretical characterization for simple seq2seq functions with orthogonal
equivariance (Proposition 1). Then, we introduce and study a class of
functions called seq2seq function with knowledge, whose form is inspired by
typical seq2seq learning problems.

###  3.1 Simple orthogonal equivariant functions

We first consider orthogonal equivariant functions given by the following
definition:

######  Definition 1.

Let $\mathcal{X}=\bigcup_{n=1}^{\infty}\mathbb{R}^{d\times n}$ be the space of
all sequences in $\mathbb{R}^{d}$. Let $f:\mathcal{X}\rightarrow\mathcal{X}$
be a sequence to sequence function. $f$ is called orthogonal equivariant in
the embedding space if for any $X\in\mathcal{X}$ and orthogonal matrix
$Q\in\mathbb{R}^{d\times d}$, there is $f(QX)=Qf(X)$.

For orthogonal equivariant functions, the following proposition shows that any
column of the output must be a linear combination of the the columns of $X$,
with the coefficients depending only on the inner products between $X$’s
columns.

######  Proposition 1.

Let $f:\mathcal{X}\rightarrow\mathcal{X}$ be orthogonal equivariant in the
embedding space given by Definition 1. Then, there exists a function $g$
taking $X^{T}X$ as input and producing a matrix with appropriate shape as
output, such that for all $X\in\mathcal{X}$, we have

$f(X)=Xg(X^{T}X).$

Proposition 1 shows that orthogonal equivariant seq2seq functions always
represent a linear combination of the elements of their input sequence $X$,
with the coefficients being orthogonal invariant. We give the proof in
Appendix A. A similar result has appeared in Villar et al. (2021) and played
an important role for physics applications.

###  3.2 Orthogonal equivariance with “knowledge”

Proposition 1 treats seq2seq functions that are strictly orthogonal
equivariant in the embedding space. For many practical language problems or
other seq2seq learning problems, the embedding indeed has some flexibility
over orthogonal transformations–the information is encoded only in the
relative positions between vectors in the embedding space, and an orthogonal
transformation of those vectors does not change the “meaning” of the sequence,
hence the “answer” of the transformed input sequence should be the transformed
original answer.

However, this intuitive symmetry does not mean that the target function is
orthogonal equivariant. As an example, consider a seq2seq function $f$ that
takes an arithmetic expression as the input and outputs the result of the
expression, e.g $f(``2+1")=``3"$, $f(``2-1")=``1"$. The tokens used in the
input and output sequences include single digit numbers $0-9$ and arithmetic
operators. These tokens can be cast into vectors by an one-hot embedding. To
be simple, suppose we only use operators “+” and “-”. Then, the embedding
space has $12$ dimensions. One possible embedding is

$``+"\rightarrow\bm{e}_{1},\ \ ``-"\rightarrow\bm{e}_{2},\ \
``0"\rightarrow\bm{e}_{3},\ \
``1"\rightarrow\bm{e}_{4},\cdots``9"\rightarrow\bm{e}_{12},$

where $\bm{e}_{i}$ is the $i$-th unit vector in the standard orthonormal basis
of $\mathbb{R}^{12}$. Under this embedding, $f(``2+1")=``3"$ can be written as

$f([\bm{e}_{5},\bm{e}_{1},\bm{e}_{4}])=[\bm{e}_{6}].$

Now, let $Q_{12}\in\mathbb{R}^{12\times 12}$ be a linear transformation that
swaps the first and second entries of any vector in $\mathbb{R}^{12}$. Then,
$Q_{12}$ is orthogonal. If $f$ is orthogonal equivariant, we will have

$f([\bm{e}_{5},\bm{e}_{2},\bm{e}_{4}])=f(Q[\bm{e}_{5},\bm{e}_{1},\bm{e}_{4}])=[Q\bm{e}_{6}]=[\bm{e}_{6}].$

This means $f(``2-1")=``3"$, which is obviously not what we expect.

To summarize, the target function is not orthogonal equivariant because it
works in a fixed embedding and cannot deal with sequences from different
embeddings. The intuitive symmetry we discussed earlier can be understood as
the symmetry in an equivalent class of target functions. Let $f$ be a seq2seq
function in a certain embedding, if an orthogonal transformation $Q$ is
applied to this embedding, then there exists another function $f_{Q}$ that
satisfies

$f_{Q}(QX)=Qf(X).$

$f_{Q}$ does the same thing as $f$ in a different embedding. Collecting
$f_{Q}$ for all orthogonal transformations $Q$, the set $\\{f_{Q}\\}$ is an
equivalence class of $f$ in all embeddings (obtained by orthogonal
transformations).

The discussion above points out that the target function is aware of the
embedding it works in. Intuitively, this is because the function contains some
knowledge used to process the input sequence, and the knowledge depends on the
embedding. Motivated by this point of view, we propose to study functions
which take the “knowledge” as an explicit input. Like the input sequence, the
knowledge also consists of vectors in the embedding space, showing its
embedding dependence. The knowledge is used to extract information from the
input sequence. Concretely, we consider functions
$f:\mathcal{X}\times\mathbb{R}^{d\times k}\rightarrow\mathcal{X}$ taking two
inputs, $X\in\mathcal{X}$ and $Z\in\mathbb{R}^{d\times k}$, with $X$ being the
original input sequence, and $Z$ being the knowledge. With this additional
knowledge input, the function $f$ can be orthogonal equivariant—changing the
embedding transforms $X$ and $Z$ simultaneously, and the true “meaning” of
what $f$ does is not changed. In other words, the equivalent class
$\\{f_{Q}\\}$ is parameterized by the knowledge input such that
$f_{Q}(\cdot)=f(\cdot,QZ)$.

From now on, we study orthogonal equivariant functions with knowledge, whose
definition is given below:

######  Definition 2.

Let $f:\mathcal{X}\times\mathbb{R}^{d\times k}\rightarrow\mathcal{X}$ be a
seq2seq function with knowledge. For any $Z\in\mathbb{R}^{d\times k}$, $f$ is
called orthogonal equivariant with knowledge $Z$ if for any $X\in\mathcal{X}$
and orthogonal matrix $Q\in\mathbb{R}^{d\times d}$, there is
$f(QX,QZ)=Qf(X,Z)$.

As a corollary of Proposition 1, we have the following proposition
characterizing the formulation of functions satisfying Definition 2.

######  Proposition 2.

Let $Z\in\mathbb{R}^{d\times k}$, and $f:\mathcal{X}\times\mathbb{R}^{d\times
k}\rightarrow\mathcal{X}$ be a function that is orthogonal equivariant with
knowledge $Z$. Then, there exist two functions $g_{1}$ and $g_{2}$ independent
of $Z$, taking $X^{T}X,Z^{T}X,Z^{T}Z$ as inputs, and producing matrices with
appropriate shapes as outputs, such that for all $X\in\mathcal{X}$, we have

$f(X,Z)=Xg_{1}(X^{T}X,Z^{T}X,Z^{T}Z)+Zg_{2}(X^{T}X,Z^{T}X,Z^{T}Z).$ (2)

###### Proof.

Let $\tilde{X}=[X,Z]\in\mathbb{R}^{d\times(n+k)}$. Viewed as a function of
$\tilde{X}$, $f$ satisfies $f(Q\tilde{X})=Qf(\tilde{X})$ for any orthogonal
matrix $Q\in\mathbb{R}^{d\times d}$. Hence, by Proposition 1, there exists a
function $g$ depending on $\tilde{X}^{T}\tilde{X}$, such that

$f(\tilde{X})=\tilde{X}g(\tilde{X}^{T}\tilde{X}).$

By the definition of $\tilde{X}$, $g$ can be written as a function of
$X^{T}X$, $Z^{T}X$ and $Z^{T}Z$, i.e.
$g(\tilde{X}^{T}\tilde{X})=g(X^{T}X,Z^{T}X,Z^{T}Z)$. Noticing that $\tilde{X}$
has $n+k$ columns, $g$ must have $n+k$ rows. Letting

$g(X^{T}X,Z^{T}X,Z^{T}Z)=\left[\begin{array}[]{c}g_{1}(X^{T}X,Z^{T}X,Z^{T}Z)\\\
g_{2}(X^{T}X,Z^{T}X,Z^{T}Z)\end{array}\right]$

with $g_{1}$ taking the first $n$ rows and $g_{2}$ taking the next $k$ rows,
we have

$f(X,Z)=Xg_{1}(X^{T}X,Z^{T}X,Z^{T}Z)+Zg_{2}(X^{T}X,Z^{T}X,Z^{T}Z).$

∎

In practice, the knowledge $Z$ in a function $f(X,Z)$ studied above can be
treated as a parameter matrix learned during the training process. We note
that the self-attention in equation 1 takes a similar form. In the self-
attention, the product of $X$ with the attention matrix has the form
$Xg(Z^{T}X)$, with $Z=[W_{Q}^{T},W_{K}^{T}]$, and $g$ being the composition of
a quadratic function and a softmax operation:

$g(Y)=\mathcal{S}_{r}\left(\frac{1}{\sqrt{d_{1}}}Y^{T}\left[\begin{array}[]{cc}0&I\\\
0&0\end{array}\right]Y\right).$

Indeed, similar as our understanding of $Z$, the query and key parameters in
the self-attention are usually understood as knowledge of the language used to
extract information from the input sequence. These parameters are naturally
embedding dependent. Certainly, the self-attention used in practice contains
more components than merely a $Xg(Z^{T}X)$ form. For example, as shown in
equation 1, a linear transformation in the embedding space is applied by
$W_{V}$, and a residual connection is added. in Section 5, we discuss some
practical considerations that may cause additional complication of the model
in practice.

Coming back to the formulation 2, if $Z$ is understood as a parameter matrix,
it is fixed after training. Then, among the three inputs of $g_{1}$ and
$g_{2}$, $Z^{T}Z$ is a constant, and $X^{T}X$ is an identity matrix under one-
hot embedding. Hence, $Z^{T}X$ is the most informative input. Moreover, since
$Z$ is a constant matrix, the linear combination of its columns,
$Zg_{2}(X^{T}X,Z^{T}X,Z^{T}Z)$ becomes less important than the linear
combination of $X$’s columns, $Xg_{1}(X^{T}X,Z^{T}X,Z^{T}Z)$. Extracting the
most meaningful parts in the formulation 2, we obtain a simpler form
$f(X,Z)=Xg_{1}(Z^{T}X)$. This coincides with what appears in the self-
attention.

###  3.3 Finite information and the representation of coefficients

In formulation 2 or the simplified formulation $f(X,Z)=Xg_{1}(Z^{T}X)$, the
coefficient functions $g_{1}$, $g_{2}$ can be quite arbitrary. They can have
very complicated dependence with their inputs. For example, for a function
$f(X,Z)=Xg(Z^{T}X)$ whose output has the same length as the input, when
$X\in\mathbb{R}^{d\times n}$, we have $g(Z^{T}X)\in\mathbb{R}^{n\times n}$. In
the most general case, $g$ can have a different formulation
$g_{n}:\mathbb{R}^{k\times n}\rightarrow\mathbb{R}^{n\times n}$ for each $n$.
Because $n$ can be arbitrarily large, the description of $g$ requires infinite
amount of information. However, if these functions can be described and
implemented by machine learning models, they must contain only a finite amount
of information. In other words, the functions cannot get infinitely
complicated when the sizes of their inputs become large. In this section,
based on this finite information principle, we discuss possible forms of the
$g$’s.

For the convenience of the discussion, we focus on the form
$f(X,Z)=Xg(Z^{T}X)$ and assume that the output of $f$ has the same length as
its input. Hence, for any input $X\in\mathbb{R}^{d\times n}$, we have
$g(Z^{T}X)\in\mathbb{R}^{n\times n}$. In this case, we put our discussion on
$g$ under the following more specific statement of the finite information
principle:

######  Assumption 1.

(Finite information principle) $g$ is represented by a parameterized model
with a finite number of parameters not depending on $n$.

This assumption concerns only one aspect of the broader idea of “finite
information”. But it is the only aspect that we can quantify easily.

Now, we consider parameterized representations for $g$. Given Assumption 1,
one of the simplest parameterizations is the composition of a nonlinear
function and a quadratic forms, such as $\sigma(X^{T}ZAZ^{T}X)$ for some
matrix $A\in\mathbb{R}^{k\times k}$. To see this, denote
$Y=Z^{T}X\in\mathbb{R}^{k\times n}$ and consider $g$ represented by a
composition of an elementwise nonlinear function and a sum of matrix products
involving $Y$, i.e.

$g(Y)=\sigma\left(\sum\limits_{i=1}^{N}W_{i,0}\prod\limits_{j=1}^{K_{i}}\tilde{Y}W_{i,j}\right),$
(3)

where $\tilde{Y}$ is either $Y$ or $Y^{T}$, and $N$ can be infinity. In the
formulation above, $W_{i,j}$ are parameters. By the finite information
principle, the dimensions of $W_{ij}$ in equation 3 should not depend on $n$.
Then, it is easy to show that we always have $K_{i}\geq 2$ in equation 3,
because terms with $K_{i}=0$ or $1$ cannot have shape $n\times n$ without
$n$-dependent parameter matrices. Hence, there is no constant or linear terms
in the sum of matrix products, and thus the simplest terms are quadratic
terms. In its simplest form, without higher order terms, we have
$g(Y)=\sigma(Y^{T}WY)$ for some $W\in\mathbb{R}^{k\times k}$, in which case
the output always has the shape $n\times n$ for any $n$. Note that the self-
attention matrix used in practice is very close to this form. If $Z$ is the
concatenation of the query and key matrices, i.e. $Z=[W_{Q}^{T},W_{K}^{T}]$,
then by taking $A=\left[\begin{array}[]{cc}0&I\\\ 0&0\end{array}\right]$ we
have

$X^{T}ZAZ^{T}X=X^{T}W_{Q}^{T}W_{K}X.$

The only difference is that the softmax operation is not elementwise.

#### A perspective from kernels

Another perspective to create $g$ with finite amount of information is from
the kernels. Viewing the input $Y\in\mathbb{R}^{k\times n}$ as $n$ vectors in
$\mathbb{R}^{k}$, $g$ maps the $n$ vectors into an $n\times n$ matrix,
characterizing the relations between these vectors. This can naturally be
achieved by a kernel function
$K(\cdot,\cdot):\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$.
Denote $Y=[\bm{y}_{1},...,\bm{y}_{n}]$, then we can let
$g(Y)=(K(\bm{y}_{i},\bm{y}_{j}))_{n\times n}$. When $K$ is an inner product
kernel $K(\mathbf{x},\bm{y})=\sigma(\mathbf{x}^{T}\bm{y})$, which is widely
used in traditional machine learning models such as the support vector
machine, $g$ takes a similar quadratic form (with an elementwise nonlinearity)
as in the discussion above, i.e. $g(Y)=\sigma(Y^{T}Y)$. Besides, there are
more kernels to choose. For instance, a radio basis function (RBF) kernel
$K(\mathbf{x},\bm{y})=f(\|\mathbf{x}-\bm{y}\|)$ can produce a $g$ defined by
$g_{ij}(Y)=f(\|\bm{y}_{i}-\bm{y}_{j}\|)$. These representations of
coefficients may see benefits in some special applications. Actually, self-
attention using kernels has already been studied in previous works such as
Rymarczyk et al. (2021); Chen et al. (2021)

##  4 Permutation equivariance for sequence elements

in this section, we consider another symmetry—the permutation equivariance for
the elements of the sequence. With this permutation equivariance, the form 2
can be further restricted. In a seq2seq problem such as a language problem,
though, the order of the input is usually important. Hence, permutation
equivariance on the order of the sequence should not be expected. However, in
practice some parts of the problems or models may have permutation
equivariance. For example, when self-attention based models are used to learn
seq2seq problems, a position encoding is usually added to the input sequence
before fed into the model Vaswani et al. (2017). In this case, the order
information is included in the input sequence and the function implemented by
the model can be permutation equivariant.

For any sequence $X\in\mathbb{R}^{d\times n}$, we call $n$ the length of $X$,
denoted by $l(X)$. We consider the following definition of permutation
equivariance:

######  Definition 3.

Let $f:\mathcal{X}\times\mathbb{R}^{d\times k}\rightarrow\mathcal{X}$ be a
seq2seq function with knowledge. Assume $l(f(X,Z))=l(X)$ always holds. For any
$Z\in\mathbb{R}^{d\times k}$, $f$ is called elementwise permutation
equivariant with knowledge $Z$ if for any permutation matrix
$P\in\mathbb{R}^{l(X)\times l(X)}$, we have $f(XP,Z)=f(X,Z)P$.

Based on the discussions in previous sections, we focus on functions with the
form $f(X,Z)=Xg(Z^{T}X)$. Given the additional permutation equivariance in
Definition 3, we have the following proposition that further narrows down the
form of the functions. The proof of the proposition is given in Appendix B.

######  Proposition 3.

Let $f$ be a function with form $f(X,Z)=Xg(Z^{T}X)$. Assume $f$ is elementwise
permutation equivariant with knowledge $Z$. Then, for any specific $n$, there
exist functions $\rho_{1}$, $\rho_{2}$, $\psi_{1}$, $\psi_{2}$, such that for
any $X\in\mathbb{R}^{d\times n}$ with full column rank, we have

$\displaystyle g_{ii}(Z^{T}X)$
$\displaystyle=\rho_{1}\big{(}\mathbf{x}_{i},Z,\sum\limits_{k=1,\ k\neq
i}^{n}\psi_{1}(\mathbf{x}_{k};\mathbf{x}_{i},Z)\big{)}$ $\displaystyle
g_{ij}(Z^{T}X)$
$\displaystyle=\rho_{2}\big{(}\mathbf{x}_{i},\mathbf{x}_{j},Z,\sum\limits_{k=1,\
k\neq i,j}^{n}\psi_{2}(\mathbf{x}_{k};\mathbf{x}_{i},\mathbf{x}_{j},Z)\big{)}$

for $i,j=1,2,...,n$ and $j\neq i$. Here, $g_{ij}$ are the $(i,j)$-th component
function of $g$, i.e. $g=(g_{ij})_{n\times n}$.

######  Remark 3.

For a self-attention layer used in practice, $Z=[W_{Q},W_{K}]$, in which case
we have

$g_{ij}(Z^{T}X)=\frac{e^{\mathbf{x}_{i}^{T}W_{Q}^{T}W_{K}\mathbf{x}_{j}}}{\sum_{k=1}^{n}e^{\mathbf{x}_{i}^{T}W_{Q}^{T}W_{K}\mathbf{x}_{k}}}.$

Using the form in Proposotion 3, this $g$ can be obtained by taking

$\displaystyle\psi_{2}(\mathbf{x};\bm{y},\bm{z},Z)$
$\displaystyle=e^{\bm{y}^{T}W_{Q}^{T}W_{K}\mathbf{x}},\quad\rho_{2}(\mathbf{x},\bm{y},Z,\psi)=\frac{e^{\mathbf{x}^{T}W_{Q}^{T}W_{K}\bm{y}}}{e^{\mathbf{x}^{T}W_{Q}^{T}W_{K}\bm{y}}+\psi},$

and taking

$\psi_{1}(\mathbf{x};\bm{y},Z)=\psi_{2}(\mathbf{x},\bm{y},\bm{y},Z),\ \ \
\rho_{1}(\mathbf{x},Z,\psi)=\rho_{2}(\mathbf{x},\mathbf{x},Z,\psi).$

##  5 Practical considerations

In previous sections, we revealed the natural forms of seq2seq functions that
satisfy specific symmetries that are reasonable for many practical problems.
Therefore, the structures identified can be taken into consideration when
designing neural network models to learn these problems, as approaches to
improve the efficiency of learning. The self-attention, although designed
without utilizing these connections between symmetries and structures, has
structures that coincides with the forms we identified. This may partially
explain the success of self-attention based models.

Usually, the models used in practice have to be more complicated than that
given by the theory, to address practical issues that are not caught in the
simplified setting of the theory. For CNNs, for example, convolution layers
are stacked to extract features hierarchically, and normalization layers are
added to help training. In the following, we discuss several considerations
when the theories built in the previous sections are used in practical
applications.

#### The evolution of embeddings

In our analysis for orthogonal equivariant functions, we assume the output and
the input of the functions are in the same embedding. In practice this might
not be true. For example, for a translation problem the input and the output
sequences are in two different languages, and hence they may not share one
embedding. In this case, we need to implement a mechanism to change the
embedding of the output sequence. The simplest way is to apply an elementwise
linear transformation to the output, i.e. for a function $f$ with form
$f(X,Z)=Xg(Z^{T}X)$, we can build a new function $\tilde{f}$ by multiplying a
matrix on the left of the output of $f$:

$\tilde{f}(X,Z,W)=WXg(Z^{T}X).$ (4)

A more flexible way is to apply a general elementwise nonlinear transformation
to the output, which can be achieved for example by a two-layer neural
network, as used in many self-attention based models:

$\tilde{f}(X,Z,U,V)=V\sigma\big{(}UXg(Z^{T}X)\big{)},$ (5)

where $U$, $V$ are parameter matrices, and $\sigma$ is an elementwise
nonlinear activation function.

#### Higher capacity

In the application of neural networks, higher capacity of the model is desired
in many cases. Giving the model more flexibility compared to the theoretical
formulation can help improve the performance of the model, as long as the
flexibility does not impair the training efficiency. Based on the structures
in equation 4 or 5, more flexibility can be added to the model by considering
a “multihead” version of such functions. For example, a multihead version for
4 with $m$ heads can be

$\tilde{f}_{m}(X,Z,W)=\sum\limits_{i=1}^{m}W_{i}Xg_{i}(Z_{i}^{T}X),$ (6)

where $Z_{1},...,Z_{m}$ and $W_{1},...,W_{m}$ are different matrices, and
$Z=[Z_{1},...,Z_{m}]$, $W=[W_{1},...,W_{m}]$, and $g_{1},...,g_{m}$ are
different functions. This structure is similar to the multihead self-
attention.

#### Compositions and hierarchical feature extraction

A very successful way to increase the capacity of a model and improve the
performance of learning is to stack several modules compositionally to form a
deep model. A deep model with many layers can extract the information from its
input hierarchically. This is the intuitive reason behind the success of deep
neural networks. For sequence to sequence applications, we can also stack
structures like 6 into a deep model. For example, a model with $L$ layers can
be

$\displaystyle h^{(0)}=X;\ \ \ \
h^{(l)}=\sum\limits_{i=1}^{m}W_{i}^{(l)}h^{(l-1)}g((Z^{(l)}_{i})^{T}h^{(l-1)},),1\leq
l\leq L;\ \ \ \ f(X,Z,W)=h^{(L)},$

where $Z$ and $W$ include all $Z_{i}^{(l)}$ and $W_{i}^{(l)}$ parameters,
respectively. This structure looks similar to the successful large language
models used in practice. One difference is that a residual link is added on
each layer of those models to help the training. Another difference is that
elementwise fully connected layers are added after some self-attentions, which
can be understood as stacking structures in equation 5.

##  6 Summary

In this paper, we study the representations of sequence-to-sequence functions
with certain symmetries, and show that such functions have forms similar to
the self-attention. Hence, self-attention seems to be the natural structure to
learn many seq2seq problems. Moreover, except the inner product based
attention mechanism widely used nowadays, our study reveals more possibilities
that may be picked in the design of attention mechanisms, such as higher-order
matrix products or the RBF kernels. These forms arise from the discussion on
the finite information principle. As a limitation, our discussion on the forms
of $g$ in Section 3.3 started from a simple general form 3. More general
discussions and more precise characterizations of the finite information
principle is left as an important future work.

## References

  * Anderson et al. (2019) Brandon Anderson, Truong Son Hy, and Risi Kondor.  Cormorant: Covariant molecular neural networks.  _Advances in neural information processing systems_ , 32, 2019.
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ , 2014.
  * Bietti et al. (2021) Alberto Bietti, Luca Venturi, and Joan Bruna.  On the sample complexity of learning with geometric stability.  _arXiv preprint arXiv:2106.07148_ , 2021.
  * Bommasani et al. (2021) Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chen et al. (2021) Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang.  Skyformer: Remodel self-attention with gaussian kernel and nyström method.  _ArXiv_ , abs/2111.00035, 2021.
  * Chidester et al. (2019) Benjamin Chidester, Tianming Zhou, Minh N Do, and Jian Ma.  Rotation equivariant and invariant neural networks for microscopy image analysis.  _Bioinformatics_ , 35(14):i530–i537, 2019.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Elesedy & Zaidi (2021) Bryn Elesedy and Sheheryar Zaidi.  Provably strict generalisation benefit for equivariant models.  In _International Conference on Machine Learning_ , pp. 2959–2969. PMLR, 2021.
  * Fuchs et al. (2020) Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling.  Se (3)-transformers: 3d roto-translation equivariant attention networks.  _Advances in Neural Information Processing Systems_ , 33:1970–1981, 2020.
  * Guttenberg et al. (2016) Nicholas Guttenberg, Nathaniel Virgo, Olaf Witkowski, Hidetoshi Aoki, and Ryota Kanai.  Permutation-equivariant neural networks applied to dynamics prediction.  _arXiv preprint arXiv:1612.04530_ , 2016.
  * Kim et al. (2020) Jinpyo Kim, Wooekun Jung, Hyungmo Kim, and Jaejin Lee.  Cycnn: A rotation invariant cnn using polar mapping and cylindrical convolution layers.  _arXiv preprint arXiv:2007.10588_ , 2020.
  * LeCun et al. (1989) Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural computation_ , 1(4):541–551, 1989.
  * Li et al. (2020a) Yunfei Li, Juntao Chang, Chen Kong, and Ziao Wang.  Flow field reconstruction and prediction of the supersonic cascade channel based on a symmetry neural network under complex and variable conditions.  _AIP Advances_ , 10(6):065116, 2020a.
  * Li et al. (2020b) Zhiyuan Li, Yi Zhang, and Sanjeev Arora.  Why are convolutional nets more sample-efficient than fully-connected nets?  _arXiv preprint arXiv:2010.08515_ , 2020b.
  * Lin et al. (2017) Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio.  A structured self-attentive sentence embedding.  _arXiv preprint arXiv:1703.03130_ , 2017.
  * Ling et al. (2016a) Julia Ling, Reese Jones, and Jeremy Templeton.  Machine learning strategies for systems with invariance properties.  _Journal of Computational Physics_ , 318:22–35, 2016a.
  * Ling et al. (2016b) Julia Ling, Andrew Kurzawski, and Jeremy Templeton.  Reynolds averaged turbulence modelling using deep neural networks with embedded invariance.  _Journal of Fluid Mechanics_ , 807:155–166, 2016b.
  * Luo et al. (2021a) Di Luo, Giuseppe Carleo, Bryan K Clark, and James Stokes.  Gauge equivariant neural networks for quantum lattice gauge theories.  _Physical review letters_ , 127(27):276402, 2021a.
  * Luo et al. (2021b) Di Luo, Zhuo Chen, Kaiwen Hu, Zhizhen Zhao, Vera Mikyoung Hur, and Bryan K Clark.  Gauge invariant autoregressive neural networks for quantum lattice models.  _arXiv preprint arXiv:2101.07243_ , 2021b.
  * Luong et al. (2015) Minh-Thang Luong, Hieu Pham, and Christopher D Manning.  Effective approaches to attention-based neural machine translation.  _arXiv preprint arXiv:1508.04025_ , 2015.
  * Mattheakis et al. (2019) Marios Mattheakis, Pavlos Protopapas, David Sondak, Marco Di Giovanni, and Efthimios Kaxiras.  Physical symmetries embedded in neural networks.  _arXiv preprint arXiv:1904.08991_ , 2019.
  * Mei et al. (2021) Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Learning with invariances in random features and kernel models.  In _Conference on Learning Theory_ , pp. 3351–3418. PMLR, 2021\.
  * Niu et al. (2021) Zhaoyang Niu, Guoqiang Zhong, and Hui Yu.  A review on the attention mechanism of deep learning.  _Neurocomputing_ , 452:48–62, 2021.
  * Parikh et al. (2016) Ankur P Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit.  A decomposable attention model for natural language inference.  _arXiv preprint arXiv:1606.01933_ , 2016.
  * Paulus et al. (2017) Romain Paulus, Caiming Xiong, and Richard Socher.  A deep reinforced model for abstractive summarization.  _arXiv preprint arXiv:1705.04304_ , 2017.
  * Procesi (2006) Claudio Procesi.  _Lie groups: an approach through invariants and representations_.  Springer Science & Business Media, 2006.
  * Qi et al. (2017a) Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 652–660, 2017a.
  * Qi et al. (2017b) Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  _Advances in neural information processing systems_ , 30, 2017b.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21(140):1–67, 2020.
  * Rahme et al. (2021) Jad Rahme, Samy Jelassi, Joan Bruna, and S Matthew Weinberg.  A permutation-equivariant neural network architecture for auction design.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 5664–5672, 2021.
  * Ravanbakhsh et al. (2017) Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos.  Equivariance through parameter-sharing.  In _International conference on machine learning_ , pp. 2892–2901. PMLR, 2017.
  * Rymarczyk et al. (2021) Dawid Rymarczyk, Adriana Borowa, Jacek Tabor, and Bartosz Zieliński.  Kernel self-attention for weakly-supervised image classification using deep multiple instance learning.  _2021 IEEE Winter Conference on Applications of Computer Vision (WACV)_ , pp. 1720–1729, 2021.
  * Satorras et al. (2021) Vıctor Garcia Satorras, Emiel Hoogeboom, and Max Welling.  E (n) equivariant graph neural networks.  In _International conference on machine learning_ , pp. 9323–9332. PMLR, 2021.
  * Schütt et al. (2021) Kristof Schütt, Oliver Unke, and Michael Gastegger.  Equivariant message passing for the prediction of tensorial properties and molecular spectra.  In _International Conference on Machine Learning_ , pp. 9377–9388. PMLR, 2021.
  * Shaw et al. (2018) Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani.  Self-attention with relative position representations.  _arXiv preprint arXiv:1803.02155_ , 2018.
  * Shuaibi et al. (2021) Muhammed Shuaibi, Adeesh Kolluru, Abhishek Das, Aditya Grover, Anuroop Sriram, Zachary Ulissi, and C Lawrence Zitnick.  Rotation invariant graph neural networks using spin convolutions.  _arXiv preprint arXiv:2106.09575_ , 2021.
  * Thomas et al. (2018) Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley.  Tensor field networks: Rotation-and translation-equivariant neural networks for 3d point clouds.  _arXiv preprint arXiv:1802.08219_ , 2018.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Vieijra et al. (2020) Tom Vieijra, Corneel Casert, Jannes Nys, Wesley De Neve, Jutho Haegeman, Jan Ryckebusch, and Frank Verstraete.  Restricted boltzmann machines for quantum states with non-abelian or anyonic symmetries.  _Physical review letters_ , 124(9):097201, 2020\.
  * Villar et al. (2021) Soledad Villar, David W Hogg, Kate Storey-Fisher, Weichi Yao, and Ben Blum-Smith.  Scalars are universal: Equivariant machine learning, structured like classical physics.  _Advances in Neural Information Processing Systems_ , 34:28848–28863, 2021.
  * Wang et al. (2020a) Rui Wang, Karthik Kashinath, Mustafa Mustafa, Adrian Albert, and Rose Yu.  Towards physics-informed deep learning for turbulent flow prediction.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 1457–1466, 2020a.
  * Wang et al. (2020b) Rui Wang, Robin Walters, and Rose Yu.  Incorporating symmetry into deep dynamics models for improved generalization.  _arXiv preprint arXiv:2002.03061_ , 2020b.
  * Weyl (1946) Hermann Weyl.  _The classical groups: their invariants and representations_.  Number 1. Princeton university press, 1946.
  * Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  _Advances in neural information processing systems_ , 30, 2017.
  * Zhang et al. (2018) Linfeng Zhang, Jiequn Han, Han Wang, Roberto Car, and EJPRL Weinan.  Deep potential molecular dynamics: a scalable model with the accuracy of quantum mechanics.  _Physical review letters_ , 120(14):143001, 2018\.

##  Appendix A Proof of Proposition 1

###### Proof.

Consider
$X=[\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}]\in\mathbb{R}^{d\times
n}\subset\mathcal{X}$. We first show that the columns of $f(X)$ lie in the
span of $\mathbf{x}_{1},...,\mathbf{x}_{n}$. Without loss of generality, we
assume $f(X)$ has only one column, i.e. $f(X)\in\mathbb{R}^{d}$. Let
$V=\textrm{span}(\mathbf{x}_{1},...,\mathbf{x}_{n})$. Then, there exist
$\bm{v}\in V$ and $\bm{u}\in V^{\perp}$, such that $f(X)=\bm{v}+\bm{u}$. Let
$Q_{\bm{u}}$ be the Householder transformation

$Q_{\bm{u}}=I-\frac{2}{\|\bm{u}\|^{2}}\bm{u}\bm{u}^{T}.$

Then, $Q_{\bm{u}}$ is an orthogonal matrix. By its definition, we have
$Q_{\bm{u}}\bm{u}=-\bm{u}$, and $Q_{\bm{u}}\bm{w}=\bm{w}$ for any
$\bm{w}\perp\bm{u}$, which implies $Q_{\bm{u}}\bm{v}=\bm{v}$ and
$Q_{\bm{u}}\mathbf{x}_{i}=\mathbf{x}_{i}$ for all $i=1,2,...,n$. Since $f$ is
orthogonal equivariant, we have

$f(Q_{\bm{u}}X)=Q_{\bm{u}}f(X)=Q_{\bm{u}}(\bm{v}+\bm{u})=\bm{v}-\bm{u}.$

On the other hand, since $Q_{\bm{u}}X=X$, we must have

$f(Q_{\bm{u}}X)=f(X)=\bm{v}+\bm{u}.$

Therefore, we have $\bm{u}=0$, and $f(X)=\bm{v}\in V$.

Next, we show that the coefficient of the linear combinations can be taken as
orthogonal invariant functions. By the analysis above, there exists a function
$g$ of input $X$, such that

$f(X)=Xg(X).$

The size of $g$’s output depends on $X$ and $f(X)$. Because $f$ is orthogonal
equivariant, for any orthogonal matrix $Q\in\mathbb{R}^{d\times d}$ we have

$QXg(QX)=f(QX)=Qf(X)=QXg(X),$

which means $Xg(QX)=Xg(X)$. Obviously, we can choose $g$ to satisfy
$g(QX)=g(X)$ for any orthogonal $Q$.

Finally, we invoke the first fundamental theorem of invariant theory for the
orthogonal group Weyl (1946); Procesi (2006), which states that $g$ only
depends on $X$ via $X^{T}X$. This completes the proof. ∎

##  Appendix B Proof of Proposition 3

###### Proof.

With an abuse of notations, we use $g(X,Z)$ to denote the output of $g$ given
inputs $X$ and $Z$, despite that $g$ only depends on $Z^{T}X$. Since $X$ has
full column rank, we have $X^{\dagger}X=I$. Hence, $g(X,Z)=X^{\dagger}f(X,Z)$.
By Definition 3, for any permutation matrix $P\in\mathbb{R}^{n\times n}$, we
have

$g(XP,Z)=P^{T}X^{\dagger}f(XP,Z)=P^{T}X^{\dagger}f(X,Z)P=P^{T}g(X,Z)P.$ (7)

Therefore, applying any permutation on $X$ leads to the same permutation on
the rows and column of $g(X,Z)$. Recall that the $(i,j)$-th entry of $g$ is
given by the function $g_{ij}$. Denote the output of $g_{ij}$ given input $X$
and $Z$ by $g_{ij}(\mathbf{x}_{1},...,\mathbf{x}_{n},Z)$. We then study the
forms of $g_{ij}$ using equation 7.

First, consider a permutation $P_{1i}$ that swaps $\mathbf{x}_{1}$ and
$\mathbf{x}_{i}$. By equation 7, we have $g(XP_{1i},Z)_{11}=g(X,Z)_{ii}$,
which means

$g_{ii}(\mathbf{x}_{1},\cdots,\mathbf{x}_{i},\cdots,\mathbf{x}_{n},Z)=g_{11}(\mathbf{x}_{i},\cdots,\mathbf{x}_{1},\cdots,\mathbf{x}_{n},Z).$

Hence, all $g_{ii}$ can be generated by $g_{11}$ with a swap permutation of
its inputs. For $g_{11}$, if we apply a permutation that is identity on $1$,
the output of $g_{11}$ does not change although the order of inputs is
changed. This means $g_{11}$ is permutation invariant with the inputs
$\mathbf{x}_{2},...,\mathbf{x}_{n}$. By Theorem 2 in Zaheer et al. (2017),
viewed as a function of $\mathbf{x}_{2},...,\mathbf{x}_{n}$, $g_{11}$ has the
form $\rho(\sum_{k=2}^{n}\psi(\mathbf{x}_{k}))$ for some functions $\rho$ and
$\psi$. Considering the inputs $\mathbf{x}_{1}$ and $Z$, the functions $\rho$
and $\psi$ above depend on $\mathbf{x}_{1}$ and $Z$. Therefore, there exist
functions $\rho_{1}$ and $\psi_{1}$, such that

$g_{11}(X,Z)=\rho_{1}(\mathbf{x}_{1},Z,\sum_{k=2}^{n}\psi_{1}(\mathbf{x}_{k};\mathbf{x}_{1},Z)).$

By the relation between $g_{11}$ and $g_{ii}$, we have

$g_{ii}(X,Z)=\rho_{1}(\mathbf{x}_{i},Z,\sum_{k\neq
i}\psi_{1}(\mathbf{x}_{k};\mathbf{x}_{i},Z)).$

for any $i=1,2,...,n$.

Next, we consider $g_{ij}$ with $i\neq j$. Without loss of generality, assume
$i<j$. Let $P_{1i,2j}$ be a permutation that swaps $\mathbf{x}_{1}$ with
$\mathbf{x}_{i}$, and $\mathbf{x}_{2}$ with $\mathbf{x}_{j}$. By the
permutation equivariance, we have

$g_{ij}(\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{i},\cdots,\mathbf{x}_{j},\cdots,\mathbf{x}_{n},Z)=g_{12}(\mathbf{x}_{i},\mathbf{x}_{j},\cdots,\mathbf{x}_{1},\cdots,\mathbf{x}_{2},\cdots,\mathbf{x}_{n},Z),$

which means any $g_{ij}$ with $i\neq j$ can be generated by $g_{12}$. Focusing
on $g_{12}$, similar to the arguments for $g_{11}$, it is easy to show that
$g_{12}$ is permutation invariant with inputs
$\mathbf{x}_{3},...,\mathbf{x}_{n}$. Therefore, there exist functions
$\rho_{2}$ and $\psi_{2}$, such that

$g_{12}(X,Z)=\rho_{2}(\mathbf{x}_{1},\mathbf{x}_{2},Z,\sum_{k=3}^{\infty}\psi_{2}(\mathbf{x}_{k};\mathbf{x}_{1},\mathbf{x}_{2},Z)).$

Hence,

$g_{ij}(X,Z)=\rho_{2}(\mathbf{x}_{i},\mathbf{x}_{j},Z,\sum_{k\neq
i,j}\psi_{2}(\mathbf{x}_{k};\mathbf{x}_{i},\mathbf{x}_{j},Z)).$

∎


# Influence of hydrogen radicals treatment on layers and solar cells made of
solution-processed amorphous silicon

Torsten Bronger  Forschungszentrum Jülich GmbH, Institut für Energie und
Klimaforschung (IEK-5), Jülich, 52425 (Germany)  Jan Wördenweber
Forschungszentrum Jülich GmbH, Institut für Energie und Klimaforschung
(IEK-5), Jülich, 52425 (Germany)  Paul Wöbkenberg  Evonik Industries AG Paul-
Baumann Str. 1, Marl, 45772 (Germany)  Stefan Muthmann  Forschungszentrum
Jülich GmbH, Institut für Energie und Klimaforschung (IEK-5), Jülich, 52425
(Germany)  Odo Wunnicke  Evonik Industries AG Paul-Baumann Str. 1, Marl, 45772
(Germany)  Reinhard Carius  Forschungszentrum Jülich GmbH, Institut für
Energie und Klimaforschung (IEK-5), Jülich, 52425 (Germany)

###### Abstract

Solution-processed amorphous silicon is a promising material for semiconductor
devices. Unfortunately, its manufacturing leaves a high density of defects in
the layer, which can be reduced by a treatment with hydrogen radicals. Here,
we present an optimized hydrogen treatment, which is used for best performing
solar cells made of solution-processed amorphous silicon. We examine the
amount and the nature of hydrogen incorporation using infrared absorption and
hydrogen effusion. The hydrogen treatment not only increases hydrogen content
significantly, it also enlarges the fraction of hydrogen in a bonding
configuration which is known to be advantageous for electronic properties,
albeit only close to the surface. Using electron spin resonance and and
photothermal deflection spectroscopy spectra, we confirm a reduction of defect
density. Regarding the electrical properties, the ratio of photo and dark
conductivity is increased by almost two decades. This leads to a greatly
enhanced performance of solar cell devices which use the material as the
absorber layer. In particular, the efficiency jumps by a factor of three.

solar cells; polysilan; passivation

Since the work of ShimodaShimoda  _et al._ (2006), solution-processed
amorphous silicon made of cyclopentasilane (CPS) and neopentasilane (NPS)
precursors has gained interest for the application in semiconductor devices,
in particular solar cells. Recently, solar cells based on this material
reached an efficiency of 3.5 % Bronger  _et al._ (2014). However, immediately
after the conversion of the polymer into a silicon layer, layer quality is
poor.Masuda  _et al._ (2012) Thus, a treatment with hydrogen radicals is
applied to bring hydrogen back into the layer.Masuda  _et al._ (2012); Bronger
_et al._ (2014); Sontheimer  _et al._ (2014) Since this is a crucial step in
the processing, it is worth having a close look at it.

For details of layer and stack preparation, including the doping of the
material, see the experimental section in Ref. Bronger  _et al._ , 2014.

For the hydrogen radicals treatment, the sample is mounted on a holder in a
vacuum chamber (approx. $4\cdot 10^{-7}$ mbar). It is tempered for one hour at
370 ℃, so that the heat is homogeneously distributed and the surface water
film evaporated. Then, 30 sccm of hydrogen gas (chamber pressure is then at
0.1 mbar) pass the layer. At the same time, a tantalum filament at 1350 ℃ with
a distance of 6.8 mm to the sample decomposes the hydrogen. The sample is
heated with the same power as in the tempering step, however the filament
would have an additional thermal impact, which we have not measured. This
passivation step takes 2 hours, after which the sample is thermalized to room
temperature and transferred out of the chamber into ambient atmosphere.

A dip of the sample in hydroflouric acid (10 %) ca. 3 minutes before the
transfer into vacuum does not improve layer or cell performance. However, it
is very important to check the chamber wall for deposits. We observed black
discoloration on the wall after a couple of hydrogen treatment runs, which
negatively affected passivation effectiveness.

Figure 1: Spectrum of Raman scattering of intrinsic NPS and state-of-the-art PECVD material. The amorphous silicon peaks are normalized to 1. Table 1: Electrical and optical properties of NPS material at room temperature. The optical gap is the energy at which the absorption coefficient equals $10^{-4}\,\mathrm{cm}^{-1}$, as determined by the PDS technique. Typical values for state-of-the-art PECVD material are shown for comparison. | before | after | PECVD
---|---|---|---
| hydrogen treatment | reference
Raman peak shift (cm-1) | $-6.8$ | $-2.7$ |  00.0
Raman peak width (cm-1) | $75.3$ | $72.2$ | $70.8$
optical gap (eV) | 1.95 | 1.99 | 1.98
optical band tail width (meV) | 86 | 78 | 61
absorption at 1.2 eV (cm-1) | 24 | 7.0 | 4
hydrogen content (%) | 6.9 | 8.4 | 17
micro structure factor (%) | 64 | 52 | 22
dark conductivity (S/cm) | $2.2\cdot 10^{-10}$ | $3.3\cdot 10^{-11}$ | $1.4\cdot 10^{-10}$
photo conductivity (S/cm) | $2.2\cdot 10^{-7\phantom{0}}$ | $2.5\cdot 10^{-6\phantom{0}}$ | $3.4\cdot 10^{-5\phantom{0}}$
photo/dark conductivity ratio | $1.0\cdot 10^{3}$ | $7.7\cdot 10^{4}$ | $2.4\cdot 10^{5}$

The Raman specra are measured with an excitation wavelength of 488 nm. Our in-
house design is capable of a resolution of $0.5\,\mathrm{cm}^{-1}$. Moreover,
we used a widened laser spot of $50\times 1\,\text{\textmu m}$ in size in
order to be able to average over layer inhomogeneities.

Fig. 1 shows the Raman scattering spectrum of intrinsic layers fabricated of
NPS. The dominating peak is that of amorphous silicon with no measurable
crystalline volume fraction. In contrast to PECVD material, the peak is
slightly shifted towards smaller wavenumbers, and broadened. Tab. 1 quantifies
these differences. These two deviations from the PECVD reference spectrum are
largely compensated by the treatment with hydrogen radicals, as visualized in
Fig. 1 and shown in Tab. 1. The residual difference is plotted in blue in Fig.
1.

One may deduce from these results that the hydrogen treatment reduces the
stress. This is backed by the peeling-off of very thick layers. Thus, we know
that it suffers from tensile stress. However, this explanation is put in
question by crack formation and propagation being independent of the hydrogen
treatment. Moreover, the mechanism of stress reduction is unclear. An
alternative explanation for the shift would be a peak at 460 cm-1 which
vanishes or is strongly suppressed after the treatment, but also here, the
mechanism would be unclear. Future substrate curvature measurements as an
estimate for the layer tension may provide further insight.

The residual difference between hydrogen-treated NPS material and PECVD
material (blue in Fig. 1) can be easily explained by an enhanced longitudinal
optical (LO) phonon absorption at 380 cm-1 in NPS. Generally, this indicates
increased disorder in the microstructure.Gerbi  _et al._ (2003)

Figure 2: The absorption coefficient versus photon energy of intrinsic layers
of NPS and PECVD material as measured with the PDS technique. The thickness of
the NPS sample is approximately 134 nm, while that of the PECVD sample is 200
nm.

For the absorption measurements, we use a photothermal deflection spectroscopy
(PDS) in-house design. A cuvette filled with carbon tetrachloride takes the
sample. Our monochromator after a hydrogen lamp allows an output bandwidth of
10 meV, however, the data points are spaced by 20 meV. The integral
irradiation power on the sample is approx. 1 µW.

Fig. 2 depicts the absorption spectrum of an intrinsic NPS layer, measured
with the PDS technique. NPS exhibits a strongly enhanced absorption in the
critical domain below 2 eV. The optical tail width, which we define as the
maximal slope of the curve in semi-logarithmic axes, is substantially higher
than in the PECVD case. The same is true for the absorption at 1.2 eV.
Similarly to the Raman results, the hydrogen treatment diminishes the
differences between the NPS layer and the reference layer. Tab. 1 confirms
this observation quantitatively. Additionally, it gives the value of the
optical gap for all cases. Again, the hydrogen treatment brings this value
closer to the PECVD reference.

The hydrogen treatment saturates the dangling bonds, thus the absoption at 1.2
eV is reduced. This is confirmed strongly by the very good correlation of PDS
and ESR results (see Fig. 3). Furthermore, the decrease in tail width is
interpreted as less disorder in microstructure, which matches nicely the lower
LO phonon absorption in Raman scattering. This also leads to the increased
optical gap as defined in Tab. 1.

Figure 3: Dependency of spin density on optical absorption at 1.2 eV. Samples
before the hydrogen treatment (red triangles) as well as after (red discs) are
included. The gray corridor is taken from Ref. Wyrsch  _et al._ , 1991 and
bases on a comprehensive results compilation.

Conventional continuous wave electron spin resonance (ESR) measurements are
performed with a commercial X-band ($\nu=9.3$ GHz) Bruker Elexsys E500
spectrometer in a cylindrical mode resonator at room temperature, microwave
power of $4\cdot 10^{-5}$ W, magnetic field modulation amplitude of 5 G, and
modulation frequency of 100 kHz. A calibrated sputtered amorphous silicon
sample with a spin density of $2\cdot 10^{15}\,\mathrm{cm}^{-3}$ and g-value
of 2.00565 was used as a reference standard.

Fig. 3 combines the results of PDS and ESR measurements. The optical
absorption at 1.2 eV is proportional to the defect density as measured with
ESR,Jackson and Amer (1982); Wyrsch  _et al._ (1991) and indeed this
dependency is reproduced by NPS samples with high accuracy over 2.5 orders of
magnitude. Ref. Wyrsch  _et al._ , 1991 reports a proportionality factor in
the range 1.2–$2.5\cdot 10^{16}\,\mathrm{cm}^{-2}$, which is shaded in gray in
Fig. 3. Obviously, the NPS samples both before and after the hydrogen
treatment stay in this range.

Figure 4: Infrared absorption spectrum of intrinsic NPS (230 nm) and PECVD
(700 nm) layers, deposited on silicon wafer substrate. The dashed line denotes
material before the hydrogen treatment. This plot is taken from the
supplementary information of Ref. Bronger  _et al._ , 2014.

For the infrared absorption measurements, we deposited the NPS layer on
double-side polished silicon wafer. The measurement data itself is collected
by an FTIR spectrometer (Nicolet 5700) with a glow bar as light source. We
substracted the absorption spectrum of a piece of uncovered silicon wafer, and
substracted an additional, manually tweaked spline baseline.

Fig. 4 shows infrared absorption spectrum of an NPS layer. There are two peaks
of interest here, one at approx. 2000 cm-1 and the other at approx. 2080 cm-1.
Both are identified with Si–H oscillation modes, however of hydrogen in
different bonding configurations. In particular, the 2080 peak is related to
bonds at (inner) surfaces,Cardona (1983) which is not able to actually
passivate dangling bonds in the bulk. In contrast, the 2000 peak is considered
“good” hydrogen in the sense of decreasing bulk defect density.
Quantitatively, this is expressed by the microstructure factor (MSF).Mahan
_et al._ (1987) Generally speaking, a smaller MSF indicates a better material.

As one can see in Tab. 1, in NPS layers, the MSF is significantly higher than
in PECVD reference layers. One can also see that the hydrogen treatment
ameliorates this situation to some extent. Fig. 4 shows that this is achieved
by increasing the bulk hydrogen while leaving the hydrogen at inner surfaces
constant. Accordingly, the integral hydrogen content raises by 20 %. However,
the content of passivating hydrogen is still much lower than in PECVD
material.

Figure 5: Hydrogen effusion diagram of an intrinsic NPS layer before and after the hydrogen treatment. Table 2: Solar cell properties at room temperature. Typical values for state-of-the-art PECVD material are shown for comparison. | effective cell | efficiency |  $I_{sc}$ in | $V_{oc}$ | fill factor | series resistance
---|---|---|---|---|---|---
| area in mm2 | in % | mA cm-2 | in mV | in % | in Ohm
before H treatment | 3.2 | 0.68 | 4.4 | 497 | 31.1 | 2,400
after H treatment | 3.2 | 2.0 | 7.4 | 628 | 42.7 |  0,910
best NPS cellBronger  _et al._ (2014) | 3.2 | 3.5 | 9.0 | 730 | 53.8 |  0,550
PECVDBronger  _et al._ (2014) | 3.2 | 5.9 | 9.8 | 892 | 67.5 |  0,450

These findings are accompanied by hydrogen effusion measurements that are
presented in Fig. 5. Hydrogen effusion is measured in the setup described in
Ref. Beyer and Einsele, 2011, a so-called open system with a turbomolecular
pump. The base pressure is approx. $10^{-10}$ mbar and the heating rate 20
℃/min. NPS layers emit most hydrogen at 600 ℃. After the hydrogen treatment,
there is an additional emission at 400 ℃. Note that absolute peak heights bear
a high uncertainty in such measurements. In particular, the fact that the
original peak at 600 ℃ is still visible but slightly smaller after the
hydrogen treatment need not be a real effect. However, the temperature axis is
accurate enough, and the peak separation large enough, to state that the
incorporated hydrogen is located and/or bonded differently from the hydrogen
that was already in the material.

IR absorption and effusion measurements give complementary information about
how the hydrogen is incorporated into the layer. On the one hand, IR
absorption clearly shows that virtually the complete additional hydrogen is
passivating dangling bonds, which certainly is an encouraging result. On the
other hand, effusion suggests that this hydrogen does not reach the innerst
parts of the layer. Instead, it gets stuck close to the surface. Note that
“surface” includes here also inner surfaces of cracks and tunnels and
structures of enhanced hydrogen diffusion.

For determining the electrical conductivity, we evaporated two silver pad
contacts at a distance of 0.5 mm on the sample. Then, we heat it in vacuum at
420 K for 30 minutes in order to evaporate most of the surface water film. The
measurement itself is performed at room temperature using a Keithley 617
electrometer. We measure the electrical current at voltages between $-100$ and
$+100$ V in order to detect non-ohmic behavior. For photoconductivity
measurements, a xenon halogen lamp in conjunction with an infrared filter
(Schott KG 7) provides the illumination.

Tab. 1 includes the results of photo and dark conductivity measurements. They
exhibit the most drastic change by hydrogen treatment. The dark conductivity
decreases, which is advantageous for the use in some types of devices. But
much more importantly, the photo conductivity and the photo/dark ratio
increase, the latter by a factor of almost 100. All of these changes make the
material more suitable as an absorber material in solar cells.

The defects and band tail states as discussed in the preceding paragraphs are
detrimental for electronic transport under illumination. Defects are
recombination centres for charge carriers,Abeles  _et al._ (1982) and band
tail states are traps for them.Tiedje (1982) This explains the greatly
increased photoconductivity after the hydrogen treatment. For dark
conductivity, however, the Fermi level moves away from the mobility edge if
less deep defects are present, so that the charge carrier balance is
fulfilled. This causes a lower carrier concentration in the extended states
above the mobility edge, and therefore, decreases dark conductivity.

Figure 6: Characteristic IV curve before and after the hydrogen treatment. For
comparison, we included the curve of our best cell device as published in Ref.
Bronger  _et al._ , 2014, and a PECVD reference.

We measure characteristic IV curves using a Keithley 238 source measure unit
in a sun simulator with AM 1.5 spectrum (class A), with a data point spacing
of 10 mV. During the measurement, we keep the sample at room temperature $\pm
1$ ℃.

Tab. 2 and Fig. 6 show the influence of the hydrogen treatment on solar cell
devices. Because the best cell published in Ref. Bronger  _et al._ , 2014 was
not measured before passivation, we present a comparison of a less efficient
production run. Nevertheless, the best cell results are included for
comparison, as are PECVD reference cell results. Note that the latter are
adapted to the smaller thickness of the NPS layers. The details of this
adaption can be found in Ref. Bronger  _et al._ , 2014.

The hydrogen treatment significantly improves the cell characteristics in any
respect. Most prominently, the series resistance (measured as the inverse
slope at the $V_{oc}$ point) drops by a factor of 2.6. $I_{sc}$, $V_{oc}$, and
fill factor are increased by 68 %, 26 %, and 35 % respectively, and the
efficiency, which is a combination of these quantities, is tripled.

Note that the massive improvement in cell performance is attributed to the
hydrogen treatment alone, and thus is orthogonal to all other conceivable
optimization techniques (e. g. light trapping, thickness optimization,
conversion optimization, interface improvements).

A lack of electronic and optical quality in comparison to PECVD material
remains. Both the density of defects and the widths of the band tails need to
be reduced to allow higher fill factor and open-circuit voltage. Moreover,
only surface-near regions are passivated so far, which needs to be extended
into the bulk.

## References

  * Shimoda  _et al._ (2006) T. Shimoda, Y. Matsuki, M. Furusawa, T. Aoki, I. Yudasaka, H. Tanaka, H. Iwasawa, D. Wang, M. Miyasaka, and Y. Takeuchi, Nature 440, 783 (2006).
  * Bronger  _et al._ (2014) T. Bronger, P. H. Wöbkenberg, J. Wördenweber, S. Muthmann, U. W. Paetzold, V. Smirnov, S. Traut, Ü. Dagkaldiran, S. Wieber, M. Cölle, _et al._ , Advanced Energy Materials (2014).
  * Dersch  _et al._ (1981) H. Dersch, J. Stuke, and J. Beichler, Applied Physics Letters 38, 456 (1981).
  * Masuda  _et al._ (2012) T. Masuda, N. Sotani, H. Hamada, Y. Matsuki, and T. Shimoda, Applied Physics Letters 100, 253908 (2012).
  * Sontheimer  _et al._ (2014) T. Sontheimer, D. Amkreutz, K. Schulz, P. H. Wöbkenberg, C. Guenther, V. Bakumov, J. Erz, C. Mader, S. Traut, F. Ruske, _et al._ , Advanced Materials Interfaces 1 (2014).
  * Kluth  _et al._ (1999) O. Kluth, B. Rech, L. Houben, S. Wieder, G. Schöpe, C. Beneking, H. Wagner, A. Löffl, and H. Schock, Thin Solid Films 351, 247 (1999).
  * Beyer and Einsele (2011) W. Beyer and F. Einsele, “Hydrogen effusion experiments,” in  _Advanced Characterization Techniques for Thin Film Solar Cells_ (Wiley, 2011) Chap. 17.
  * Wyrsch  _et al._ (1991) N. Wyrsch, F. Finger, T. McMahon, and M. Vanecek, Journal of non-crystalline solids 137, 347 (1991).
  * Jackson and Amer (1982) W. B. Jackson and N. M. Amer, Physical Review B 25, 5559 (1982).
  * Cardona (1983) M. Cardona, physica status solidi (b) 118, 463 (1983).
  * Mahan  _et al._ (1987) A. Mahan, P. Raboisson, D. Williamson, and R. Tsu, Solar Cells 21, 117 (1987).
  * Gerbi  _et al._ (2003) J. Gerbi, P. Voyles, M. Treacy, J. Gibson, and J. Abelson, Applied physics letters 82, 3665 (2003).
  * Abeles  _et al._ (1982) B. Abeles, G. Cody, Y. Goldstein, T. Tiedje, and C. Wronski, Thin Solid Films 90, 441 (1982).
  * Tiedje (1982) T. Tiedje, Applied Physics Letters 40, 627 (1982).