李宏毅机器学习第十五周 Self-attention mechanism summary

week15 Self-attention mechanism summary

摘要

本文首先介绍了多种提高self-attention机制运行效率的方法。由于self-attention中矩阵运算的复杂度呈O(N²)，限制了使用该种机制的神经网络。本文讨论了从多个角度逐渐迭代的优化方法。之后本文进一步的解析了题为Linear Complexity Self-Attention With 3 rd Order Polynomials的论文。该论文使用多项式形式推导出了一种特定形式的线性复杂度的自注意力机制计算方法，且提出了两种新颖的神经网络模块，Ploy-NL、Ploy-SA。两个模块分别应用非局部块与自注意力块，并实现了线性复杂度。

Abstract

First, This airticle introduces a variety of methods to improve the efficiency of the self-attention mechanism. Due to the complexity of matrix operations in self-attention, which is O(N²), the neural networks using this mechanism are limited. This article discusses several optimization approaches that are gradually iterative from multiple perspectives. This airticle then analyzes a paper titled Linear Complexity Self-Attention With 3 rd Order Polynomials. This paper deduces a specific form of self-attention mechanism calculation method of linear complexity using polynomial form, and propose two novel neural network modules, Ploy-NL and Ploy-SA. The two modules apply non-local blocks and self-attention blocks respectively, and achieve linear complexity.

一、李宏毅机器学习

提高self-attention效率的方法

self-attention中的计算较为复杂。假定序列长度为n，则单个序列对应的key和query向量长度均为n，而$AttentionMatrix=key\times query$，最后和value做带权重的求和。显然上述的计算过程是与输入序列的长度n成正比的，即O(n²)，因此以下介绍几种可以用于降低计算复杂度的方法。

但需要指出的是，transformer模型并不仅由self-attention计算组成，其还包括了位置编码、残差计算、归一化、全连接层等。这些计算在序列长度较小时会占据计算量的主要部分，尤其是全连接层。然而当序列长度较大时，self-attention部分的运算占据计算量的主要部分，此时针对self-attention的计算进行优化才能取得较为明显的效果。特别在影像处理部分，对于较小尺寸的影像，由于其输入序列是按照像素进行编码的，因此其序列长度仍旧是一个相对其他任务较大的数量级。

1. local attention/truncated attention

首先想到的优化思路是减小矩阵运算的规模。在一些领域的计算中，序列可能并不与全局相关，因此提取局部信息可能在提高模型的运行效率的同时提高模型的运行效果。local attention或truncated attention就是基于上述思路，其在计算时仅考虑下图中浅蓝色部分的注意力，而将其他位置置零。这虽然能有效地提高模型的运行效率，但由于这种计算方法考虑的全局信息过少，导致其实际上与CNN无异，从而使得模型的运行效果并不理想。

2. stride attention

为了区别于CNN，提出了stride attention方法。该方法在计算注意力时考虑不相邻的序列，例如向前数三个位置的序列。向前数几位是一个由设计者根据模型处理问题所决定的超参。左侧为向前数三个，右侧为两个。

3. global attention

上面的两种方法均是提取局部信息的，而该方法侧重于提取全局信息。该方法首先选择或添加特殊的token用于提取全局信息，下图右上角显示了从序列中选择token用于提取全局信息的方法，注意力矩阵计算如左侧浅红色部分。右下角显示了添加新的token的方法。

由于multi-head self-attention，可以在不同的头选择不同的注意力机制。下图显示了一些应用多种注意力机制的样例。其中big bird除了上述方法，还应用了random attention。

上述的注意力机制均是基于人为设计，但能否设计一种数据驱动的注意力机制？如下图，对于较小的数据值可以置零，以下介绍如何快速的提取较小的注意力参数。

4. Clustering

在Reformer、Rourting Transformer中，均使用了Clustering方法。该方法首先对query向量序列与key向量序列进行聚类。首先，确定各个vector所属的类别，将相近的vector归在一个类内，聚类过程可以使用多种方式加速。其次计算在同一类的vector之间的注意力矩阵

5. Learnable Patterns

标题中的方法是在sinkhorn sorting network中提出。首先，用另一个神经网络处理输入序列，其输出是与输入序列等长的向量组。文中还提出了一种可微分的将低维数据映射至高维的方法。从而可以将前文中提到的网络的输出结果转换成注意力矩阵的权重矩阵的同时，随着训练过程的推进不断迭代。此外，该方法为了进一步降低计算量，对于一个较长的输入序列，可以使多个向量共用一个神经网络中的向量。

对该方法的一种可行改进方法是其计算权重矩阵的神经网络直接输出注意力矩阵。

6. part attention matrix proposed by Linformer

Linformer中认为并没有必要计算full attention matrix，因为在矩阵中部分元素是其他元素的线性组合或由其他元素的直接决定。因此Linformer提出了部分注意力矩阵，即仅计算注意力矩阵中的一部分

首先，确定key向量序列中确定最具有代表性的N个key向量，选择value向量序列中N个key向量对应的value向量。其次，计算N个key向量与所有query向量序列的注意力矩阵，最后和选中的value向量序列做weighted sum得到输出。

上述过程仅对key、value序列进行处理，但对于部分任务，可以对query矩阵进行相同的操作。由于这种操作会改变输出序列的长度，因此需要根据问题确定。

上文中仅给出了部分注意力矩阵的计算方式，以下介绍如何筛选key向量。

compressed attention提出将序列输入卷积层筛选，输出即为筛选结果

而linformer中提出，将整个序列乘以N*K大小的矩阵，从而输出长度为K的key向量序列。其生成序列是N个向量的线性组合。

7. computation simplism

下图中的论文实现了上述计算简单化

8. synthesizer

该文提出了另一种生成注意力的方式，其由下图中左侧的作为注意力矩阵，但该矩阵并不由q&k产生。该矩阵是网络参数的一部分。该过程使用另一种方式实现了注意力机制，且该方法不会使得效果更差

进一步的能否抛弃注意力机制进行相关任务呢？下图中的论文给出了多种方向，其仅使用MLP处理

summary

下图总结了今天学习的用于优化注意力机制的多种方法，下图右侧为展示表。表中，纵轴为运行效果，横轴为速度，而圆圈的大小表示memory的使用量

二、文献阅读

1. 题目

题目：Linear Complexity Self-Attention With 3 rd Order Polynomials

作者：Francesca Babiloni; Ioannis Marras; Jiankang Deng; Filippos Kokkinos; Matteo Maggioni; Grigorios Chrysos

期刊： IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 11, pp. 12726-12737, 1 Nov. 2023

2. abstract

注：self-attention(SA), non-local(NL)

该文首先通过多项式框架彻底分析了多种方法，即自注意力机制与非局部块，确定了自注意力可被表达为三阶多项式的特例。其次，在此框架内，设计了能够以相同数据模式接入非局部与自注意力块的多项式模块，该类模块能够将将其复杂度从$O(n^2)$降低至$O(n)$。文中提出的模块是Poly-NL和Poly-SA，其可在各种CV任务中取得更好效果的同时保持线性复杂度。

This paper first thoroughly analyzes various methods, i.e. self-attention mechanism and non-local blocks. Through a polynomial framework, they identify a special case in which self-attention can be expressed as a third-order polynomial. Second, within this framework, polynomial modules that can access non-local and self-attention blocks in the same data pattern are designed, which can reduce their complexity from $O(n^2)$ to $O(n)$. The module propose in this paper are Poly-NL and Poly-SA, which can achieve better results in various CV tasks while maintaining linear complexity.

3. 网络架构

该部分详见下文Poly-NL Layer和 Poly-SA Layer，下文中包括公式推导、图像展示。在下文中已经提供了足够的说明，且这两部分是该文提出的主要的具有创新性的网络结构，故不在此处赘述。

4. 文献解读

4.1 Introduction

该文建立了全新的多项式展开与自注意力/非局部块的联系，并在此基础上设计了用于捕获块内相同相关性的算子以减低运算成本。该文则提出了Poly-NL(该文之前的工作)的扩展——Poly-SA。在多个ViT模型的任务中，该模块能够作为低复杂度的替代方案。文中还以可视化的方式直观的说明了模块内部的工作原理。

4.2 创新点

4.2.1 CAPTURING HIGH-ORDER INTERACTIONS IN NEURAL NETWORKS

上文中提到该文建立了多项式展开与神经网络之间的联系，本部分进行说明

该文通过逐阶建立描述对应阶的相关作用的公式，根据公式析取有限子集，从而限定参数范围。依照这种方法可以将神经网络中复杂的张量替换为规模较小的矩阵

Polynomials for Neural Networks

向量表示为小写字母（例如 x），矩阵表示为大写字母（例如 $X$）

矩阵 $X\in R^{I_1\times I_2}$ 的位置 (i, j) 处的元素可以表示为$x(i,j)$

张量用花体字母（例如 $\mathcal{X}$）标识

Hadamard products记作$\odot$

双点积定义为第一个张良的最后两个索引和第二个张量的前两个索引的张量收缩，用$\bullet$表示，具体来说

对于两个张量
$$\begin{gathered} \mathcal{W}\in R^{I_1\times I_2\cdots \times I_{N-1}\times I_N} \\ \mathcal{X}\in R^{I_{N-1}\times I_N} \end{gathered}$$
其双点积
$$\mathcal{Y}=\mathcal{W}\bullet \mathcal{X}\in R^{I_1\cdots \times I_{N-2}}$$
上式可表示为
$$y_{(i_1,\dots ,i_{N-2})}=\sum _{i_n=1}^{I_N}\sum _{i_{n-1=1}}^{I_{N-1}}w(i_1,\dots ,i_{N-2},i_{n-1},i_n)x(i_{n-1},i_n)$$

曾有作者[2]采用多项式表达神经网络层，每个输出元素通过多项式函数依赖于每个输入元素，定义如下
$$\text{Y}=P(\text{X})=\sum _{d=1}^D{\mathcal{W}}^{[d]}\prod _{j=1}^d\bullet \text{X}+{\text{W}}^{[0]}\text{\hspace{1em}(1)}$$
其中X和Y是大小为$I_1\times I_2$的输入和输出矩阵，P是D阶多项式。${\mathcal{W}}^{[d]}\in {\text{R}}^{I_1\times I_2\times {\prod }_j=1^d(I_1\times I_2)}$是可学习的张量参数，与特定阶数$d\in 1,\dots ,D$相关。${\text{W}}^{[0]}$是可学习的偏差矩阵。张量参数${\mathcal{W}}^{[d]}$的大小随着多项式的阶数d呈指数增加

Higher Order Interactions

首先描述特征图$\mathcal{X}\in {\text{R}}^{H\times W\times C}$的高阶交互项，考虑其折叠$\text{X}\in {\text{R}}^{N\times C}$，向量化空间维度为$N=HW$。二阶块的一般方程可通过分离(1)式中的二阶项$D=2$获得， 具体如下
$$\text{Y}=(({\mathcal{W}}^{[2]}\bullet \text{X})\bullet X)\text{\hspace{1em}(2)}$$
其中${\text{W}}^{[2]}$是六阶张量，维度为${\text{R}}^{N\times C\times N\times C\times N\times C}$

(1)式可作为线性层的推广，其element-wise公式如下
$$y_{(a,b)}=\sum _{c,e}^N\sum _{d,f}^C{w}_{2_{(a,b,c,d,e,f)}}{x}_{(c,d)}{x}_{(e,f)}\text{\hspace{1em}(3)}$$
将上述过程推广至三阶依赖关系。假设 d ∈ { 0 , 1 , 2 } d\in \{0,1,2\} d∈{0,1,2}的${\mathcal{W}}^{[d]}=0$，则可以分离三阶项D=3，从而有
$$\text{Y}=((({\mathcal{W}}^{[3]}\bullet \text{X})\bullet \text{X})\bullet \text{X})\text{\hspace{1em}(4)}$$
其中${\mathcal{W}}^{[3]}$是八阶张量，维度为${\text{R}}^{N\times C\times N\times C\times N\times C\times N\times C}$

相应的有
$$y_{(a,b)}=\sum _{c,e,g}^N\sum _{d,f,h}^C{w}_{3_{(}a,b,c,d,e,f,g,h)}{x}_{(c,d)}{x}_{(e,f)}{x}_{(g,h)}\text{\hspace{1em}(5)}$$
上式描述了所有可能三阶相互作用

在经过上述推导后，可利用张量${\mathcal{W}}^{[3]}$的特定结构，仅选择$x_{(c,d)}{x}_{(e,f)}{x}_{(g,h)}$的所有有限子集

在实际操作中，使用神经网络中常用的高效算子将交互张量替换为较小尺寸的矩阵

4.2.2 Poly-NL Layer

非局部块是一个可学习层，用于提取输入中的远程依赖关系

其对N个空间位置和C个通道的折叠特征图$\mathbf{X}\in {\text{R}}^{N\times C}$进行操作，并输出相同维度的矩阵Z
$$\mathbf{Z}=\mathbf{Y}+\mathbf{X}=f(\mathbf{X})g(\mathbf{X})+\mathbf{X}\text{\hspace{1em}(6)}$$
f用于计算没对空间位置的相似度，g用于计算输入的表示

在$g(\mathbf{X})$是线性编码且$f(\mathbf{X})$是点积的情况下，非局部块可定义为
$${\mathbf{Y}}^{NL}=(\mathbf{X}{\mathbf{W}}_{\theta }{\mathbf{W}}_{\varphi }^T{\mathbf{X}}^T)(\mathbf{X}{\mathbf{W}}_g)=\mathbf{X}{\mathbf{W}}_f{\mathbf{X}}^T\mathbf{X}{\mathbf{W}}_g\text{\hspace{1em}(7)}$$
其中${\mathbf{W}}_{\theta }{\mathbf{W}}_{\varphi }{\mathbf{W}}_g$是维度为$C\times C$的可学习参数

上式写作element-wise形式为
$$y_{(a,b)}^{NL}=\sum _e^N\sum _{d,f,h}^C{w}_{f_{(d,f)}}{w}_{g_{(h,b)}}{x}_{(e,f)}{x}_{(e,h)}\text{\hspace{1em}(8)}$$
其中标量$w_{f_{(d,f)}},w_{g_{(h,b)}}$可以用于辨识矩阵$W_f,W_g$在给定索引d,f,h,b处的元素

上述非局部块的复杂度为$O(N^2)$，因此该文提出了Poly-NL模块。

该模块接受输入矩阵$\mathbf{X}\in R^{N\times C}$并输出相同维度的Z矩阵，Z计算公式如下
$$\mathbf{Z}=\alpha \mathbf{X}+\beta {\mathbf{Y}}^{Poly-NL}$$
其中$\alpha ,\beta$是可学习参数，而Poly-NL模块计算公式如下
$${\mathbf{Y}}^{Plo{y}_{N}L}=(\Psi (\mathbf{X}{\mathbf{W}}_1\odot \mathbf{X}{\mathbf{W}}_2)\odot \mathbf{X}){\mathbf{W}}_3\text{\hspace{1em}(9)}$$

其中，$\Psi$是均值池化后空间位置上的扩充函数，${\mathbf{W}}_1,{\mathbf{W}}_2,{\mathbf{W}}_3$均是可学习矩阵，$\odot$表示element-wise乘法

空间相互作用集在Poly-NL公式中如下式
$$y_{(a,b)}^{Poly-NL}=\sum _{d,f,h}^C\sum _e^N{w}_{1_{(h,d)}}^{\prime }{w}_{2_{(f,d)}}{w}_{3_{(d,b)}}{x}_{(a,d)}{x}_{(e,f)}{x}_{(e,h)}\text{\hspace{1em}(10)}$$
其中$w_{1_{(h,d)}}^{\prime }$式矩阵${\mathbf{W}}_1^{\prime }={\mathbf{W}}_1/N$的参数

Poly-NL不需要显式计算任何成对函数，因此可以被视为非局部块的线性复杂性替代方案。所提出的模块图如下图所示。

下图左侧展示了该模块作为非局部自注意力块，右侧展示了该模块作为三阶多项式模块

4.2.3 Poly-SA Layer

上文中针对非局部块提出了能将其降低为线性复杂度的模块，现从transformer的角度出发讨论，并提出针对空域transformer中自注意力部分的的Poly-SA

自注意力块的输出Y为
$$\mathbf{Y}=\sigma (\mathbf{Q}{\mathbf{K}}^T/\sqrt{C_q})\mathbf{V}\text{\hspace{1em}(11)}$$
自注意力块将N个标签和C个通道的特征图$\mathbf{X}\in {\text{R}}^{N\times C}$作为输入。输入通过可学习参数${\mathbf{W}}_k\in R^{C\times C_q},{\mathbf{W}}_q\in R^{C\times C_q},{\mathbf{W}}_v\in R^{C\times C_q}$投影到键 $\mathbf{K}=\mathbf{X}{\mathbf{W}}_k$、查询 $\mathbf{Q}=\mathbf{X}{\mathbf{W}}_q$ 和值 $\mathbf{V}=\mathbf{X}{\mathbf{W}}_v$ 中。在标准的自注意力层中，键和查询用于计算注意力矩阵，并使用softmax归一化函数$\sigma$来获得值的权重。

$\sigma (\mathbf{Q}{\mathbf{K}}^T/\sqrt{C_q})\in {\text{R}}^{N\times N}$保持了由非对称性softmax注意力内核计算的表示每对可能的空间位置之间的相似性

上式element-wise形式如下
$$y_{(a,b)}=\sum _e^N\sigma (\sum _{d,f,g}^C{w}_{q_{(f,g)}}{w}_{k_{(d,g)}}{x}_{(a,d)}{x}_{(e,f)})\sum _h^C{x}_{(e,h)}{w}_{v_{(h,b)}}\text{\hspace{1em}(12)}$$
分两步构建有线性复杂度的自注意力

首先，通过核化观察(11)中的注意力机制，考虑到文献中相关内容以及广义自注意力
$${\mathbf{Y}}^{SA}=\mathbf{AV}=(\varphi (\mathbf{Q})\varphi (\mathbf{K}{)}^T)\mathbf{V}\text{\hspace{1em}(13)}$$
上式中以通用相似度矩阵替换传统自注意力softmax注意力矩阵

将A视为Q和K中的行的线性点积，该函数通过函数$\varphi$映射，从而生成正相似性度量。

用矩阵乘法降低上式的复杂度
$${\mathbf{Y}}^{SA}=\varphi (\mathbf{Q})(\varphi (\mathbf{K}{)}^T\mathbf{V})=\varphi (\mathbf{Q})\mathbf{B}\text{\hspace{1em}(14)}$$
其中B矩阵描述频道间特征

用上述方法可以获得线性复杂度，但相应的失去了空间适应性。因为上式用额外通道混合块替换了空间混合层。

从而引申出了第二步，估计每个通道重要性，并使用此信息重新调整输入
$${\mathbf{Y}}^{Poly-SA}=\varphi (\mathbf{Q})Diag(\mathbf{B})\text{\hspace{1em}(15)}$$
该层在保持了动态性的同时降低了额外计算。

与(9)类似，只能通过均值池化和element-wise乘法计算
$${\mathbf{Y}}^{Poly-SA}=\varphi (\mathbf{Q})\odot \Psi (\varphi (\mathbf{K})\odot \mathbf{V})\text{\hspace{1em}(16)}$$
其中若$\varphi$是标识函数，从而相似度计算内核是线性复杂度

在上述假设下，element-wise形式如下
$$y_{(a,b)}^{Ploy-SA}=\sum _e^N\sum _d^C\sum _{h,f}^C{w}_{k_{(d,b)}}{w}_{q_{(f,b)}}{w}_{v_{(h,b)}}{x}_{(e,f)}{x}_{(a,d)}\text{\hspace{1em}(17)}$$
上式可视为N和C的线性复杂度的三阶多项式块

为了弥补空间自适应性，引入两个新参数向量${\mathbf{p}}_1\in {\mathbf{R}}^N,\mathbf{p}2\in {\mathbf{R}}^N$ ，。最后，为了避免训练期间的收敛问题，用sigma归一化函数封装动态权重的值。总之，Poly-SA 的方程式为
$${\mathbf{Y}}^{Poly-SA}=\mathbf{Q}\odot {\mathbf{p}}_1\sigma ({\mathbf{p}}_2^T(\mathbf{K}\odot \mathbf{V}))\text{\hspace{1em}(18)}$$

4.3 实验过程

4.3.1 Poly-NL for Cnns

在三个不同的任务上评估了所提出的Poly-NL：COCO上的对象检测和实例分割、ImageNet上的图像分类以及 WIDER FACE 数据集上的人脸检测，提供的经验证据表明，Poly-NL 优于之前提出的 CNN 非局部块，同时保持效率和性能之间的最佳权衡。

Efficiency

从效率角度，评估了TESA、NL、LatentGNN、EA和 Poly-NL的性能。此外，为了强调非局部交互的影响，还包括了无注意力机制的CONV。测试环境为RTX2080GPU

下图描述了不同大小的输入矩阵 X 的各种非局部块的复杂性开销，其中b和c展示空间位置数量，a展示通道数量。a和b展示了运行时间，c展示了GPU内存峰值。

Classification

使用ImageNet数据集在大规模图像分类上评估方法，数据预处理为将1.28 M训练图像分为1000个类

在Res4阶段插入非本地模块来修改 ResNet-50 架构，然后使用8个 GPU 从头开始训练90个 epoch，使用批量大小为 256 和具有初始值的SGD优化器学习率为 0.1 和权重衰减

将该网络与[3]的原始非局部块、LatentGNN、TESA、the Efficient Attention（EA）[4]比较。

对于 LatentGNN 块，使用 2 个潜在内核，潜在维度等于 100，通道缩减因子为 8。

对于 TESA，使用通道缩减因子 2。

对于 EA，使用通道缩减因子 8、头数 1 和 softmax 归一化。

对于 Poly-NL，通过将块放置在卷积瓶颈层和卷积扩展层之间来使用通道缩减因子 4。

定量结果报告在下表a

Poly-NL 在 Top-5 精度上实现了最佳性能，并且在 Top-1 上，显着优于除 TESA之外的所有其他非局部神经网络，但 TESA 的计算要求非常高。

Instance Segmentation

使用在MS-COCO 2017数据集上训练的[5]的Mask R-CNN基线，其中包含 118 k 图像作为训练集，5 k 作为验证集，20 k 作为测试集。

使用在ImageNet上预训练的ResNet-50架构作为主干。

使用 8 个 Tesla V-100 GPU 进行训练，每个GPU2个图像（有效批量大小 16），在训练期间使用随机水平翻转作为增强。使用权重衰减为 0.0001、动量为 0.90、初始学习率为 0.02 的 SGD 求解器。所有模型都经过 26 个时期的训练，学习率步骤在第 16 和 22 时期以 gamma 0.1 执行。在所有实验中，报告了边界框和分割掩模的平均精度 AP、AP50 和 AP75 的标准指标。

将该网络与[3]的原始非局部块、LatentGNN、EA和TESA进行比较。结果如上表b

与性能最佳的方法 TESA相比，Poly-NL 在 $A{P}_{mask}$ 中表现出相同的性能，但在 $A{P}_{box}$ 中表现出稍低的精度。然而，在给定分辨率下，Ploy-NL的计算速度比 TESA 快近 10 倍。

2nd and 3rd Order Methods

简要讨论注意力多项式框架与可以构建为二阶多项式块的神经网络流行构建块之间的联系

为了强调更高级别交互的重要性，在下表(a) 中对 COCO 上的实例分割进行了消融。

参数与上节Instance Segmentation中一致，并通过在 Res4 阶段添加一个额外的块来修改 ResNet-50 主干网，并消除各种可能的选择。考虑 SE[6] 和 GC[7] 块，以及为了进行（9）中定义的修改将 ($\mathbf{X}{\mathbf{W}}_1\odot \mathbf{X}{\mathbf{W}}_2$) 替换为仅包括$\mathbf{X}{\mathbf{W}}_1$ (二阶) 。

这一变化使块接近SE。在这项任务中，非局部模式至关重要，用二阶方法代替 Poly-NL 会导致性能下降。从下表(a) 中可以看出，二阶结果与 SE 相当，但低于 Poly-NL。此外，与 GC 相比，Poly-NL 保持了更好的性能。

此外，展示了如何联合使用二阶和三阶交互来构建更具辨别力的特征。二阶块存在很多可能的选择，二阶块和三阶块的最佳可能组合留待将来的工作。

在这里，为了简单起见，选择等价于[76]中引入的ProdPoly块的公式$\mathbf{X}{\mathbf{W}}_p\ast \mathbf{X}$。参数设置遵循Classification。从上表(b) 的结果可以看出，二阶和三阶交互作用的引入使得两个模型比基线模型提高了性能，但它们的组合实现了最佳结果。

4.3.2 Poly-SA for Transformers

讨论了标准自注意力在效率方面的差异，并展示了其在两种不同计算机视觉任务上的应用。

Efficiency

将Poly-SA 的时间复杂度效率与标准多头自注意力SA [8]、高效变体 XCA [9] 和 LA [10] 进行比较。

作为时间复杂度的衡量标准，报告GPU上的运行时间以及每秒的浮点操作数，两者均表示为输入大小的函数。与Poly-NL for Cnns类似，通过报告大小相当的线性层（No-SA）的复杂性来定义这种情况下的绝对复杂性下限。

在这种情况下，XCA、LA 和 Poly-SA 相对于输入大小保持线性趋势，而标准 SA 机制则以二次方方式扩展其复杂性。

如图下图©和(b) 所示，Poly-SA 通过避免访问互协方差对角线之外的影响因素而优于其他有效变体，并保持与 No-SA（没有注意机制的基线线性层）相同的复杂性。

通过分析 GPU 上的运行时间作为通道数量的函数来展示我们方法的可扩展性。如下图(a)所示，虽然 XCA 和 LA 仅在 C< N 时优于标准 SA，但即使对于大量通道，Poly-SA 的性能仍然接近 No-SA 下限。

Classification

在一组不同的最先进的Vision Transformer上评估Poly-SA模块

在ImageNet数据集上使用了大规模分类任务，其中包含130万张训练图像、5万张验证图像和1K个对象类。

考虑了两种著名的无下采样层的各向同性架构和三种分层视觉转换器架构。作为各向同性网络，考虑了传统ViT（即 DeiT）和XCiT架构。作为分层网络，在4级Transformer中选择了Swin架构和MetaFormer架构，考虑了3级Transformer CvT。

对于每个网络，用 Poly-SA 块替换所有自注意力（或交叉协方差自注意力），而其余架构保持不变。使用公开的代码来复制原始的训练设置。

对于CvT，卷积投影VK的步长等于 1。对于DeiT和Swin Transformers，使用 3x3 深度卷积作为投影层将头部内容混合在一起。在Metaformer架构中，SA仅在最后两个阶段使用。仅在变体的最后两个阶段实现 Poly-SA。

上表报告了架构大小、注意力块的类型、架构的参数计数以及用于计算注意力块的 FLOPS。此外，还报告了所有评估方法在 Top1 精度方面的性能。

从表中可以明显看出，Poly-SA 降低了复杂性，而不会大幅影响所有五种架构的性能。它节省了高达 58% 的浮点运算，性能下降不到 2%，在评估的架构中显示出一致的结果。

接下来，使用 CIFAR-100 的小规模数据集和 ImageNet 的大规模数据集评估分类任务方法。选择最先进的架构XCiT作为基线比较。遵循DeiT中的训练设置，并使用AdamW优化器训练了400个epoch。为 XCiT设置了四种不同的网络大小，并用Poly-SA替换了原始的XCA块，保持其余架构不变。四个规模设置为：“Nano”大小（与 12 层 128 个通道和 4 个注意力头相关），“Tiny”大小（与 12 层 192 个通道和 4 个注意力头相关），“Small”（12 层 384 个通道和 8 个注意力头 ），“Medium”（24 层 512 个通道和 8 个注意力头）

在对CIFAR-100数据集进行的实验中，层数固定为6，通道数为：Nano=128、Tiny=192、Small=384 和 Medium=512。

CIFAR-100和ImageNet的结果分别报告在下表(b)和下表(a)中。从结果中可以看出，Poly-SA仍然保持与XCA相当的性能，并且在不同数据集和网络规模上表现出一致的性能。

4.4 结论

该文将非局部块转换为输入空间位置之间乘法交互形式的三阶多项式，并分别提出了非局部层的实例Poly-NL、自注意力的实例Poly-SA，两个模块在线性复杂度的情况下能与修改前版本保持相近的效率。

小结

本文首先介绍了多种提高self-attention机制运行效率的方法。由于self-attention中矩阵运算的复杂度呈O(N²)，限制了使用该种机制的神经网络。本文讨论了从多个角度逐渐迭代的优化方法。之后本文进一步的解析了题为Linear Complexity Self-Attention With 3 rd Order Polynomials的论文。该论文使用多项式形式推导出了一种特定形式的线性复杂度的自注意力机制计算方法，且提出了两种新颖的神经网络模块，Ploy-NL、Ploy-SA。两个模块分别应用非局部块与自注意力块，并实现了线性复杂度。

1. local attention:局部注意力或称截短注意力，该机制仅考虑在query-key矩阵对角线附近的注意力权重，这实际上限制了注意力机制，使得其与CNN无异。
2. stride attention:其按照步幅stride确定计算自注意力的方式
3. global attention:该方法侧重于提取全局信息，首先选择或者添加特殊token用于提取全局信息，计算该token所在的行列的注意力参数
4. Clustering:该方法对query、key向量序列进行聚类操作，计算横纵坐标对应向量属于同一类的注意力参数
5. Learnable Patterns:该方法用另一个神经网络处理输入序列，从而生成一个用于决定是否计算对应元素的0-1矩阵。
6. Linformer:该框架改变了计算注意力的方式，从而实现了注意力矩阵计算的线性复杂度，本文还彻底的对该部分内容进行了书面推导。
7. synthesizer:其源论文提出了这种基于神经网络直接计算注意力矩阵的方法

参考文献

[1] F. Babiloni et al., “Linear Complexity Self-Attention With 3 rd Order Polynomials,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 11, pp. 12726-12737, 1 Nov. 2023, doi: 10.1109/TPAMI.2022.3231971.

[2] G. G. Chrysos, S. Moschoglou, G. Bouritsas, J. Deng, Y. Panagakis, and S. P. Zafeiriou, “Deep polynomial neural networks,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 8, pp. 4021–4034, Aug. 2022.

[3] X. Wang, R. Girshick, A. Gupta, and K. He, “Non-local neural networks,” in Proc. IEEEConf. Comput. Vis. Pattern Recognit., 2018, pp. 7794–7803.

[4]Z. Shen,M. Zhang, H. Zhao,S.Yi, andH. Li, “Efficient attention: Attention with linear complexities,” in Proc. IEEE/CVFWinter Conf. Appl. Comput. Vis., 2021, pp. 3531–3539.

[5]K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-CNN,” in Proc. IEEE Int. Conf. Comput. Vis., 2017, pp. 2961–2969.

[6] J. Hu, L. Shen, and G. Sun, “Squeeze-and-excitation networks,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., 2018, pp. 7132–7141.

[7] Y. Cao, J. Xu, S. Lin, F.Wei, and H. Hu, “GcNet: Non-local networks meet squeeze-excitation networks and beyond,” in Proc. IEEE/CVF Int. Conf. Comput. Vis. Workshops, 2019, pp. 1971–1980.

[8]A. Vaswaniet al., “Attention is all you need,” Adv. Neural Inf. Process. Syst., vol. 30, 2017.

[9]A. Ali et al., “XCIT: Cross-covariance image transformers,” Adv. Neural Inf. Process. Syst., vol. 34, pp. 20 014–20 027, 2021.

[10]A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, “Transformers are RNNs: Fast autoregressive transformers with linear attention,” in Proc. Int. Conf. Mach. Learn., 2020, pp. 5156–5165.