Positional Encoding

Absolute Positional Encoding

Relative Positional Encoding

ALiBi

RoPE

NoPE

Read for some math?

A self-attention operator $A_s$ is permutation equivariant while an attention operator with learned query $A_Q$ is permutation invariant.

See more

credits

Consider an image or feature map $\mathbf{X}\in {\mathbb{R}}^{d\times n}$, where $n$ denotes the spatial dimension

and $d$ denotes the number of features. Let $\pi$ denote a permutation of $n$ elements. A transformation

$T:{\mathbb{R}}^{d\times n}\to {\mathbb{R}}^{d\times n}$ is called a spatial permutation if $T(\mathbf{X})=\mathbf{X}{P}_{\pi }$,

where $P_{\pi }\in {\mathbb{R}}^{n\times n}$ denotes the permutation matrix associated with $\pi$, defined as

$P_{\pi }=[{\mathbf{e}}_{\pi (1)},{\mathbf{e}}_{\pi (2)},\cdots {\mathbf{e}}_{\pi (n)}]$ with ${\mathbf{e}}_i$ being

a one-hot vector of length $n$ and $i$-th element as 1.

An operator $A:{\mathbb{R}}^{d\times n}\to {\mathbb{R}}^{d\times n}$ is spatial permutation equivariant if

$T_{\pi }(A(\mathbf{X}))=A(T_{\pi }(\mathbf{X}))$ for any $\mathbf{X}$ and any spatial permutation $T_{\pi }$.

In addition, an operator $A:{\mathbb{R}}^{d\times n}\to {\mathbb{R}}^{d\times n}$ is spatially invariant if

$A(T_{\pi }(\mathbf{X}))=A(\mathbf{X})$ for any $\mathbf{X}$ and any spatial permutation $T_{\pi }$.

A self-attention operator $A_s$ is permutation equivariant while an attention operator with learned query $A_\mathbf{Q}$ is permutation invariant. In particular, denote by $X$ the input matrix and by $T$ any spatial permutation, we have $$A_s(T_{\pi }(\mathbf{X}))=T_{\pi }(A_s(\mathbf{X})),$$

and

$$A_{\mathbf{Q}}(T_{\pi }(\mathbf{X}))=A_{\mathbf{Q}}(\mathbf{X}).$$

When applying a spatial permutation $T_{\pi }$ to the input $\mathbf{X}$

of a self-attetnion operator $A_s$, we have

$$\begin{array}{rl}{A}_s(T_{\pi }(\mathbf{X}))& ={\mathbf{W}}_v{T}_{\pi }(\mathbf{X})\cdot \text{softmax}\left(({\mathbf{W}}_k{T}_{\pi }(\mathbf{X}){)}^T\cdot {\mathbf{W}}_v{T}_{\pi }(\mathbf{X})\right)\\ & ={\mathbf{W}}_v\mathbf{X}{P}_{\pi }\cdot \text{softmax}\left(({\mathbf{W}}_k\mathbf{X}{P}_{\pi }{)}^T\cdot {\mathbf{W}}_q\mathbf{X}{P}_{\pi }\right)\\ & ={\mathbf{W}}_v\mathbf{X}{P}_{\pi }\cdot \text{softmax}\left(P_{\pi }^T({\mathbf{W}}_k\mathbf{X}{)}^T\cdot {\mathbf{W}}_q\mathbf{X}{P}_{\pi }\right)\\ & ={\mathbf{W}}_v\mathbf{X}{P}_{\pi }{P}_{\pi }^T\cdot \text{softmax}\left(({\mathbf{W}}_k\mathbf{X}{)}^T\cdot {\mathbf{W}}_q\mathbf{X}\right)P_{\pi }\\ & ={\mathbf{W}}_v\mathbf{X}\cdot \text{softmax}\left(({\mathbf{W}}_k\mathbf{X}{)}^T\cdot {\mathbf{W}}_q\mathbf{X}\right)P_{\pi }\\ & =T_{\pi }(A_s(\mathbf{X})).\end{array}$$

Note that $P_{\pi }^T{P}_{\pi }=\mathbf{I}$ since $P_{\pi }$ is an orthogonal matrix. It is also easy to verify that

$$\text{softmax}(P_{\pi }^T\mathbf{M}{P}_{\pi })=P_{\pi }^T\text{softmax}(\mathbf{M})P_{\pi }$$

for any matrix $\mathbf{M}$. Hence $A_s$ is spatial permutation equivariant.

Similarly, when applying $T_{\pi }$ to the input of an attention operator $A_Q$ with a learned query $\mathbf{Q}$,

which is independent of the input $\mathbf{X}$, we have

$$\begin{array}{rl}{A}_Q(T_{\pi }(\mathbf{X}))& ={\mathbf{W}}_v{T}_{\pi }(\mathbf{X})\cdot \text{softmax}\left(({\mathbf{W}}_k{T}_{\pi }(\mathbf{X}){)}^T\cdot \mathbf{Q}\right)\\ & ={\mathbf{W}}_v\mathbf{X}(P_{\pi }{P}_{\pi }^T)\cdot \text{softmax}\left(({\mathbf{W}}_k\mathbf{X}{)}^T\cdot \mathbf{Q}\right)\\ & ={\mathbf{W}}_v\mathbf{X}\cdot \text{softmax}\left(({\mathbf{W}}_k\mathbf{X}{)}^T\cdot \mathbf{Q}\right)\\ & =A_Q(\mathbf{X}).\end{array}$$

Hence $A_Q$ is spatial permutation invariant.

readme

• 位置编码一篇质量高的综述