【Transformer】SOFT: Softmax-free Transformer with Linear Complexity

This article is included in NeurIPS 2021

Thesis link ：https://arxiv.org/pdf/2110.11945.pdf
Code link ：https://github.com/fudan-zvg/SOFT

One 、 background

be based on self-attention Of transformer Although it has achieved good results , But the amount of computation and memory are the square of the input resolution .

The author believes that this calculation limitation comes from the softmax self-attention.

General self-attention They are all standardized in Computing token The inner product of the feature is calculated , Keep this softmax The operation challenges the later linearization operation .

therefore , The author of this paper puts forward softmax-free transformer, SOFT, stay self-attention Removed from softmax, Use Gaussian kernel function instead of inner product , It can be approximated by low rank matrix decomposition self-attention matrix .

Two 、 Method

2.1 Softmax-free self-attention formulation

Input is X, To carry out attention , First, we need to get Q, K, V：

self-attention The calculation of is as follows ：

$\alpha$ For calculating self-attention map The process of , By nonlinear function $\beta$ and relation function $\gamma$ form ：

The general form is as follows ：

To simplify the calculation , The author uses the following method to replace ：

In order to maintain attention matrix The symmetry of , The author set Q and K The mapping function of , therefore , In this paper, the self-attention matrix as follows ：

2.2 Realize low rank normalization through matrix decomposition

In order to reduce the amount of calculation , The author refers to Nystrom[38] To achieve low rank matrix approximation , You don't have to calculate all self-attention.

Standardized self-attention matrix $\hat{S}$ as follows ：

3、 ... and 、 effect

SOFT Its variants are as follows ：