text: 稀疏Transformer（Sparse Transformer）
  自Transformer[2]被提出以来，它依靠强大的效果得到了广泛的关注。Transformer最被诟病的一个问题是它的时间复杂度和输入序列的长度成二次方的关系，假设序列的长度是  ，Transformer的复杂度则高达  。Transformer的这个复杂度对于文本数据来说还并不算太高，但是对于由数万个像素组成的图像来说，它的复杂度就非常庞大了。目前解决Transformer的复杂度过高，提升Transformer的运行效率，从而将Transformer应用到更多领域，成为了一个主流的研究方向。本文要介绍的稀疏Transformer（Sparse Transformer）[2]使用稀疏自注意替代传统了Transformer的密集注意力，将Transformer的复杂度降低到  ，下面我们就来介绍稀疏 Transformer的详细内容。稀疏Transformer的提出动机是基于一个在CIFAR-10数据集上，使用一个128层自注意力模型，对注意力模式可视化后得到的。如图1到图4所示，它是一个基于自回归的图像生成模型，图中白色区域是注意力机制的高权值位置，黑色区域是被掩码掉的像素。图1是比较浅层的注意力节点的可视化，它的高权值点集中在当前预测点的附近，也就是说浅层的注意力更关注当前像素周边的纹理信息。图2是第19层自注意力权值的可视化，从图中可以看出，高亮区域接近当前像素点的之前若干个时间片的若干个像素，也就是说这个自注意力更关注当前预测像素的同行的信息。图3是第20层自注意力权值的可视化，它的高亮区域是当前预测像素的同一列，此时自注意力更关注同列信息。图4是稍微偏后一些的自注意力可视化（36层），从中可以看出自注意力更关注的是图像的全局信息。从图1到图4的可视化结果来看，Transformer的注意力机制呈现了和卷积模型类似的归纳偏置，即浅层的网络倾向于提取纹理信息，深层的网络倾向于提取语义信息。我们知道，卷积网络的一个重要特征是稀疏性，那么我们能否将稀疏性引入Transformer中呢，这也就是稀疏Transformer的提出思想。像GPT这样的自回归模型，它们使用的是之前所有时间片的内容来预测当前时间片的结果。普通的Transformer需要为当前时间片之前所有像素计算一个权值，所以普通Transformer的自注意力机制的时间复杂度是  ，在作者的CIFAR-10的实验中，  。图5是一个普通的Transformer以自回归的方式生成大小为  图像的注意力（左）以及连接矩阵（右）的示例。在生成一个图像时，它总共需要计算的权值数量是  ，当我们要预测一个更大的图像时，这个量级的计算量还是非常庞大的。因为Transformer的自注意力在进行图像生成时，注意力矩阵与注意力所处的网络深度呈现了明显相关的稀疏性。那么我们能否提前就人工设置好自注意力计算矩阵的稀疏性呢？这样我们一是能够引入网络结构的归纳偏置，二是能够减轻模型的计算量，提升计算速度。下面我们就来介绍Sparse Transformer是如何实现这个目标的。我们知道，普通的自注意力的计算方式可以表示为：  ，该计算方式复杂度最高的地方是  的计算，达到了  。而稀疏Transformer的核心是只让设置好的像素点参与自注意力的计算（注意这里不是只取设置好的位置上的像素点，因为这样并不能降低模型复杂度）。为了实现这个目的，我们这里引入了一个名为连接模式（Connectivity Pattern）的变量，它表示为  。其中  表示在预测第  个时间片的索引（Indicing），它是一个由  和  组成的二维矩阵，位置为  表示该位置的像素点参与自注意力的计算。如图5的注意力计算矩阵，它对应的是  ，其中深色部分的值是  ，浅色部分的值是  。在稀疏Transformer的自注意力计算中，连接模式只作用在  和  的计算，它的计算过程如式(1)到式(3)。    其中  ，  以及  分别是计算Query，Key，Value三个向量用到的权值矩阵。稀疏Transformer减轻计算量的方式通过让连接模式作用到  上，从而减轻  的复杂度。如式(3)，对于第  个时间片的输入，我们首先使用Key和Value的权值矩阵乘以输入特征，得到  和  。然后再将连接模式  作用到  和  上，得到稀疏的特征  和  。然后再使用稀疏特征得到第  个时间片结果  ，如式(2)。最后再将  个时间片的结果合并起来，得到最终的结果  ，如式(1)。我们这里已经定义好了稀疏自注意力机制的通用计算方式，接下来我们要做的是将第1节观察到的不同深度的不同稀疏模式有效地融合到这个计算方式中。对于每个自注意力的计算，我们可以使用若干个不同的注意力核。在作者的论文中，注意力核的个数是  ，当然也可以扩展到更高的维度。跨步注意力（Stride Attention）由两种形式的连接模式组成，一种是如图2所示的行注意力的模式，另一种是如图3所示的列注意力的模式。假设步长是  ，行注意力核指的是在连接模式中，当前时间片的前  个时间片的的值是  ，其余的值是  。列注意力核指的是连接模式中每隔  个时间片值为  ，其余值为  。行注意力核的表达式如式(4)。对于图片生成这样的任务来说，  一般为图像的宽或者高，在作者的CIFAR-10实验中，  ，也就是说行注意力核的复杂度是  。  列注意力核的表达式如式(5)，同理，它的复杂度也是  。  行注意力核，列注意力核以及它们的连接矩阵的形式如图6所示。它的生成目标是一个  的图像，当预测第  个时间片的像素时，行注意力核的值为  的位置是第  个像素，列注意力核的值为  的位置是第  个像素。固定注意力（Fixed Attention）也是由行注意力和列注意力组成，它的行注意力核是当前预测像素所在行的全部像素，如式(6)。例如图7.(a)中，当前预测的时间片 以及步长  ，那么  的值需要满足  ，也就是说  的值可以是  。固定注意力的行注意力核的最大长度是  ，因此它的复杂度是  。  固定注意力的列注意力核表示为式(7)，其中  ，  是一个超参数。在式(7)中，我们发现其中并没有变量  ，这也就意味着固定注意力的列注意力核关注的位置与  无关。图7.(b)展示的是 ，  ，以及  的情况，此时我们可以得到  ，也就是  可以取的值满足：  且  ，因此可以推出  的值可能为  ，也就是图7.(b)中的浅蓝色区域。固定注意力的列注意力又被叫做滑窗注意力（Sliding Window Attention）。超参数  的作用相当于卷积窗口的大小。在作者的实验中，一组效果比较好的参数是  以及  。列注意力核的关注的像素数约为  ，因此它的复杂度也是  。 上面我们介绍了多种不同形式的注意力核，那么下面我们将介绍如何将这些不同形式的注意力核融入到网络中的，在论文中作者介绍了三种融合的方式：其中组不同的注意力核会并行计算，然后在特征维度进行特征拼接。实验结果表明这种方式是最好的融合策略。 在上面的多种不同形式的注意力核，作者对其进行了GPU加速。作者发现多层的Transformer非常难训练，为了解决这个问题，作者首先使用了在ResNet v2[3]中提出的激活前置（Pre-Activation）的残差模块。一个  层的网络可以表示为式(11)。  其中embed是可学习的嵌入层，表示为式(12)。  其中  的值为  或  ，这取决于输入的模块中的数据，  是数据的维度，  是分解注意力的维度。  是序列中第  个元素的one-hot编码，  是  在第  维特征上的one-hot编码。 由一个注意力模块和一个前馈神经网络组成，表示为式(13)。  其中归一化策略是LN，  。  是GELU激活函数。梯度检查点（Gradient Checkpointing）是一个以时间换空间的一个策略，它的思想和可逆残差以及可逆Transformer非常像。即在反向传播的过程中，我们不是保存所有节点的参数值，而是只保留部分关键节点的值，然后通过这些关键节点反向推出其他节点的值。这样虽然引入了额外的节点参数的计算工作，但是大大节约了显存，从而使得训练更长的序列成为可能。Sparse Transformer使用了混合精度训练的策略来进一步加速，这里指的是使用单精度浮点数存储网络权重，使用半精度浮点数计算网络的激活和梯度。在梯度计算的过程中，这里使用了动态损失缩放来避免损失下溢的问题，并在跨GPU取均值是使用半精度传递梯度。我们这里介绍了一个应用于图像生成的Transformer架构：稀疏Transformer。稀疏Transformer最大的特点是提出了多种不同类型的稀疏注意力核，将自注意力的时间复杂度从  下降至  。稀疏Transformer的稀疏卷积核是基于Transformer在图像生成实验中的对注意力权值的可视化得到的，可以非常好的应用到类似的场景中，但是对于Transformer更常见的NLP应用场景，现在的稀疏Transformer的效果则有限了，除非我们设计出更适合这些场景的稀疏注意力核。[1] Child, Rewon, et al. &#34;Generating long sequences with sparse transformers.&#34; arXiv preprint arXiv:1904.10509 (2019).[2] Vaswani, Ashish, et al. &#34;Attention is all you need.&#34; Advances in neural information processing systems 30 (2017).[3] He, Kaiming, et al. &#34;Identity mappings in deep residual networks.&#34; European conference on computer vision. Springer, Cham, 2016.