Relative Positional Encoding for Transformers with Linear Complexity

A Liutkus, O Cífka, S Wu, U Şimşekli, Y Yang, G Richard

ICML2021 long talk

[Inria & Telecom Paris & Research Center for IT Innovation]

https://readpaper.com/paper/3163721282

https://readpaper.com/paper/3168215316

https://hub.fastgit.org/aliutkus/spe

Recent advances in Transformer models allow for unprecedented sequence lengths, due to linear space and time complexity. In the meantime, relative positional encoding (RPE) was proposed as beneficial for classical Transformers and consists in exploiting lags instead of absolute positions for inference. Still, RPE is not available for the recent linear-variants of the Transformer, because it requires the explicit computation of the attention matrix, which is precisely what is avoided by such methods. In this paper, we bridge this gap and present Stochastic Positional Encoding as a way to generate PE that can be used as a replacement to the classical additive (sinusoidal) PE and provably behaves like RPE. The main theoretical contribution is to make a connection between positional encoding and cross-covariance structures of correlated Gaussian processes. We illustrate the performance of our approach on the Long-Range Arena benchmark and on music generation.

https://weibo.com/1402400261/KghhtlkRm

摘要：由于线性空间和时间复杂性，Transformer模型的最新进展允许前所未有的序列长度。同时，相对位置编码（RPE）被认为有利于经典Transformer，并且包括利用相对位置而不是绝对位置进行推理。尽管如此，RPE对于Transformer的最新线性变体仍然不可用，因为它需要注意矩阵的显式计算，而这正是此类方法所避免的。在本文中，我们弥合了这一差距，并提出了随机位置编码作为生成PE的一种方法，该方法可替代经典的加法（正弦）PE，并可证明其行为类似于RPE。主要的理论贡献是在相关高斯过程的位置编码和互协方差结构之间建立联系。我们将说明我们的方法在Long-Range Arena基准测试和音乐生成方面的性能。

1.引言

1.1. 线性复杂度Transformer

Transformer模型（Vaswani et al.，2017）是一种新型的神经网络，在许多应用领域迅速成为最先进的，包括自然语言处理（He et al.，2020）、图像处理（Dosovitskiy et al.，2020）、音频处理（Huang et al.，2018；Pham et al.，2020）或生物信息学（AlQuraishi，2019）等等。

Transformer的核心、新颖部件是注意层。它从个输入值计算个输出值，所有输入值都是任意维的向量。遵循经典的非参数回归原则（Nadaraya，1964；Watson，1964），它包含一个简单的加权和：

其中每个注意系数均为——收集在M×N矩阵中——表示值在计算输出中的重要性。

Transformer的主要贡献之一是计算这些系数的原始方法。D维特征向量和附属于输入和输出序列的所有项，分别称为键和查询。将它们收集在N×D和M×D矩阵和中，我们得到softmax点积注意如下：

其中函数exp是按元素应用的。（2）中的右侧是Tsai等人（2019）和Choromanski等人（2020）提出的推广，其中是一个核函数。参数涉及如何从原始序列中获得键、值和查询，通常是通过时间分布的全连接层。（编者注：应该是指用于QKV变换的线性层）

原始的Transformer架构（Vaswani et al.，2017）明确计算注意矩阵，导致复杂性，从而不能扩展到很长的序列长度。虽然这在序列长度仅为几百左右时不一定是个问题，就像在某些语言处理任务中一样，但对于非常大的信号（如高分辨率图像或音频），这是禁止的。

针对这一扩展问题，最近研究了几种允许长序列的方法：

•    注意聚类(Attention clustering)方案对元素进行分组，通过定期注意计算项目之间的依赖关系。这可以通过在序列中使用简单的邻近规则来实现，从而形成分块策略（Dai等人，2019年），或者通过对键和值进行聚类（Roy等人，2020年）。簇间依赖关系要么被忽略，要么通过在内存中创造的固定长度上下文向量进行总结（Wu等人，2020）。

•    假设注意力矩阵稀疏。在这种情况下，只有少数为非零（Child等人，2019年）。

•    假设具有特定（低秩）结构，并可分解为两个较小矩阵的乘积。一个典型的例子是 Linformer（Wang等人，2020b），它仅限于固定长度的输入。在这方面，另一个最近的研究方向是：

其中是应用于每个键和查询的非线性特征映射，并且，（Shen等人，2020年；Katharopoulos等人，2020年）。

•    当公式（2）中的是正（半）定核时(positive (semi)defifinite kernel)，Performer（Choromanski et al.，2020）利用复现核Hilbert空间表明，即使不是低秩，也可以使用随机平均地方便地实现公式（3）中的：

其中是从一个分布中提取的，该分布取决于。

一个简单的例子是，其中，对于某些，有。

每当使用像（3）或（4）这样的高效方案时，就可以在不计算注意系数的情况下获得输出，如（10）。（注释1：最近的LambdaNet works（Bello，2020）使用了一种稍微相关的策略，它将键值信息封装为所谓的lambda函数，以便在查询时应用，因此也避免了计算完全注意矩阵。）

1.2. 位置编码

在Transformer网络中，输出被计算为所有输入值的线性组合，由注意系数加权。在序列建模中，合理的假设是，除了这些位置的内容外，实际位置和也应在计算中发挥作用；否则，序列的任何排列都将导致相同的输出。采取了两种核心方法来纳入位置信息：

•    原始Transformer（Vaswani等人，2017年）将该信息添加到网络输入中，即在第一个注意层之前。这可以等效地理解为对键、值和查询的augmenting：

，，    

其中表示间在位置处的位置编码（PE；Sukhbatar等人，2015）。查询和值项同理。Vaswani等人提出了一种基于三角函数的确定性方案，该方案与可训练嵌入一样有效。

•    作为注意域中位置编码的一个示例，Shaw等人（2018年）提出了相对位置编码（RPE），其是基于在时间维度上的相对滞后要比绝对位置编码（APE）更重要。其如下：

现在充当基于查询选择的时间延迟的个不同编码。这一变化被认为在许多应用领域带来了重要的性能提升，并从那时起得到了广泛的应用。

虽然在注意域中记录位置编码有利于提高性能（Shaw等人，2018；Dai等人，2019；Tsai等人，2019），但我们只知道需要计算或群集(clustered)注意方案的实现，这些方案将精细分解为更小的注意矩阵，并计算它们。这与（3）和（4）形成了鲜明的对比，后者从不计算注意力矩阵。

我们的贡献可以总结如下：

•    我们建议将随机位置编码（Stochastic Positional Encoding ，SPE）作为键域中的一般PE方案，该方案强制实施在注意域中设计的特定注意模式。这使得我们可以使用RPE，而无需显示计算注意力。据我们所知，这是第一个与Transformer（例如Choromanski et al.（2020）和Katharopoulos et al.（2020））兼容的RPE策略。

•    我们研究SPE对Long-Range Arena基准测试（Tay等人，2021年）和两项音乐生成任务性能的影响。由于RPE目前仅限于短序列，我们相信这是第一次研究其在长期预测方面的优势。我们的结果显示了更好的验证损失和外推能力。

•    我们在我们的配套网站2上提供了额外的资源，包括PyTorch和JAX/Flax的SPE的Python实现（https://cifkao.github.io/spe/）。

2.    随机位置编码

索引集和符号。

我们假设输入/输出序列的索引分布为，其中是索引集。对于常规采样的序列，有。当然也有其它的情况，例如非常规采样的时间序列（）或图像（）。

在任何情况下，考虑中的输入/输出位置的特定列表都被写为：（花体字）和（花体字），其大小分别为N和M（的情况称为自注意）。因此，相应的键和值被索引为和，查询为。为了方便起见，我们为M×N注意矩阵的条目编写了。我们使用粗体大写字母表示矩阵，粗体小写字母表示向量（编者注：在在译文中不显示），并使用类似NumPy的表示法：如果是矩阵，则和分别代表其第行和第列。

假设。

在本文的剩余部分中，我们将寻求一个注意矩阵A，由以下公式给出：

其中是位置核。定义，这可以用矩阵形式写成：

这可以被理解为D维注意力模板被查询和键共同激活。原始RPE（7）可以看作是一种特殊情况，其中一些条目保持不变。

作为协方差的位置注意。

SPE的关键思想是将注意力核视为协方差：

--

其中，Qd（m）和Kd（n）是两个实随机变体和零均值随机变体，将在其协方差函数与Pd匹配的单一条件下进行选择。语义上，它们应该分别理解为（随机）编码查询的位置m和键的位置n。当与点积注意力相乘时，它们平均产生所需的注意力模板Pd（m，n）。中心直觉是，实际的位置编码没有他们的点积重要。

在下面的内容中，我们将在互协方差Pd（m，n）上施加特定的结构，这将反过来允许我们设计随机过程Qd={Qd（m）}m∈M和Kd={Kd（n）}n∈使（11）成立。这种结构的核心优点是允许Pd被分解。现在假设我们构造{qd（m），Kd（n）} d的分布，我们可以从它们中取样（我们将在第2.1节中看到），并考虑它们对于给定m和n的R独立实现，它们聚集在m×r和n×r矩阵qd和Kd中：

对于大R，根据大数定律，我们得到：

这导致（9）中的A由以下公式给出：

这里，一个重要的观察结果是，对于大R，由于独立性，交叉项QdK>d0=d可以忽略不计，前提是过程的平均值被选择为零。最后，选择查询和关键点如下：

我们从（15-17）中看到，我们回到了通常的乘法方案（2），其中A=exp（bQbK>/√R） ，其中查询/键现在具有维度R，并且可以在（10）中用于直接获得输出，而无需计算A。

该过程在算法1中进行了总结：我们提供了一种方法（16-17）来实现键域中的PE，从而在注意域中实施所需的模型（8），由注意核Pd参数化。有趣的是，这是在不计算注意矩阵的情况下完成的，符合O（N）变换。我们接下来讨论的剩余挑战是生成Qd和Kd（13）。

2.1.绘制随机位置编码

考察（11），我们注意到我们的目标是从具有规定互协方差结构的D对中心随机过程Qd，Kd D中抽取样本。为此目的，使用高斯过程是合理的（Williams&Rasmussen，2006），对于已知的平均值和协方差，高斯过程具有最大熵。这种分布在联合克里金法文献（Matheron，1963；Genton&Kleiber，2015）中的地球物理学中经常遇到，科学家通常会处理相关随机场。我们设置的特殊曲折是：我们有一个生成问题，如Voˇrechovsk'y（2008年）；然而，与它们的设置相反，我们对每个输出的边际协方差函数并不直接感兴趣，只要期望的互协方差结构成立。

SPE最直接的应用出现在我们选择Pd（m，n）=Pd（m）时− n） ，即静止位置核，在Shaw et al.（2018）中作为选择相对注意而被创造，并归结为对互协方差矩阵Pd强制执行Toeplitz结构≡ [Pd（m]− n） ]m，n介于Qd和Kd之间。

我们提出了两种SPE变体来处理这个重要的特殊情况，如图2所示。第一个变体产生周期协方差函数。当注意力不应随着大的相对位置而消失时，这可能是有益的，如交通预测（Xue&Salim，2020年）或如我们所示，在音乐生成中。第二变体生成消失协方差函数；一个最近被证明是有用的概念（Wang等人，2021年），并且在我们的一些实验中显著地产生较小的验证损失。

变体一。

相对和周期性注意（sineSPE）。在我们的第一种方法中，我们考虑Pd是周期性的情况，得到方便的治疗。我们假设：

K在哪里∈ N是正弦分量和fd的数量∈ [01]K，θd∈ [−ππ]K和λd∈ RK分别收集其K频率、相位和权重。通过使用矩阵表示法，我们可以将（18）改写为：

where–v≡ vbp/2cp∈ R2K表示向量v的两次上采样版本∈ RK，b·c表示楼层操作，对于索引集I，Ω（I，a，b）是一个大小为| I |×2K的矩阵，带有条目（基于0的索引）：

可以证明，如果θd=0和M=N，我们回到正定义Toeplitz矩阵的（唯一的）Vandermonde分解3（Yang等人，2016），这在我们的上下文中归结为假设∀τ、 Pd（0）≥ Pd（τ）。由于这并不总是可取的，我们保留了更一般的（19）。此时，我们可以轻松构建Qd和Kd。我们用单位方差的独立同分布（i.i.d.）高斯项绘制2K×R矩阵Zd，并定义：

很容易检查这种构造是否导致（13）。它的参数是{fd，θd，∧d}d，通常可以通过随机梯度下降（SGD）进行训练。

变体二。相对（消失）注意与定期抽样（convSPE）。

由于其周期结构，变体I生成的协方差函数是非方差函数。然而，我们的框架足够灵活，允许协方差结构消失，这可能更理想，取决于应用（Wang et al.，2021）。

与变体I相反，在变体I中，我们对Pd施加了特定的结构，我们现在将采用间接方法，其中Pd将根据我们的算法构造隐式定义。在这种情况下，我们假设信号是定期采样的（例如文本、图像、音频），我们将利用高斯随机矩阵的结构和卷积运算的基本特性。

为了便于记谱，我们假设自注意，即M=N。让{ΦQd，ΦKd}d表示一组过滤器，这些过滤器最终将从训练数据中学习。这些滤波器的大小和尺寸可根据输入数据选择（即，可以是向量、矩阵、张量）。然后，我们提出以下程序，通过卷积产生Toeplitz Pd：

•我们首先绘制具有i.i.d.标准高斯输入的M×R随机矩阵Zd。对于多维信号，Zd收集R个随机向量、矩阵、立方体等。

•通过将Zd与各自的过滤器ΦQd和ΦKd卷积，获得所需的Qd和Kd：

哪里∗表示具有适当尺寸的卷积（例如1D、2D或3D）。如附录所示，使用卷积和有限滤波器可确保协方差消失。由于Zd项的独立性，对于较大的R，乘积ZdZ>d/R将趋向于单位矩阵。考虑到（22）中的卷积运算可以等价地表示为由各个滤波器构造的三角Toeplitz矩阵的乘法，可以证明，如R→ ∞, 1R QdK>d趋向于两个三角Toeplitz矩阵的乘积。因此，通过使用三角Toeplitz矩阵的性质（参见Kucerovsky et al.2016，定理2.4），我们得出如下结论：→ ∞, 我们的构造产生了所需的Toeplitz矩阵Pd。该方法由滤波器{ΦQd，ΦKd}d参数化，该滤波器将通过SGD从训练数据中学习。

注意模式的多样性P（m）− n） 可直接获得的结果取决于核大小，这是信号处理的经典结果（Vetterli et al.，2014）。在VGGNet中级联几个卷积（Simonyan&Zisserman，2014）可能是一种增强卷积SPE变体表达能力的便捷方法。

从更一般的角度来看，（22）中的两个操作可以理解为通过过滤白噪声来产生PE，这是我们为PE引入的核心思想。可以使用其他经典信号处理技术，例如使用无限脉冲响应滤波器。这些考虑接近于（Engel等人，2020年）中提出的想法。

总之，两种拟议结构（20-21）和（22）之间的核心区别在于RPE的行为超过了最大相对位置，通过（20-21）的频率fd和（22）的滤波器尺寸隐含地定义。当正弦结构导致周期性RPE时，滤波结构导致RPE消失，这在中称为单调（Wang et al.，2021）。根据应用情况，两者都可能是所需的选项。

2.2.门控SPE

尽管我们提出的RPE和泛化（9）是处理位置信息的新颖而有效的策略，但考虑到不考虑位置因素的注意力系数也可能是有益的，只需通过hqm，kni。作为一种通用的选通机制，我们建议通过选通参数δd来权衡位置注意和非位置注意∈ [0 1]:

该选通方案可以通过以下方式简单地通过增加上述生成的Qd和Kd来实现：

d在哪里∈ （24）和（25）中的RR相同，具有i.i.d.标准高斯项。在实践中，我们可以在网络上共享一些SPE参数，尤其是跨层共享，以大大减少计算时间和内存使用。在我们的实现中，共享意味着在实现PE到（16-17）之前，为每个磁头生成一个单独的Q和K实例，在该实例上应用分层选通。如图2所示。

3.实验

3.1. Long-Range Arena

实验装置。

我们在Long-Range Arena（LRA；Tay等人，2021年）中评估了所提出的方法，该Long-Range Arena是高效Transformer的基准，包括序列分类任务，重点是远程依赖性。我们使用此基准测试中的以下任务：•ListOps：解析和评估分层表达式。一个较长的变体（Nangia&Bowman，2018）；

•文本：IMDB语料库上的电影评论情绪分析（Maas等人，2011年）；

•检索：关于NLP（AAN）语料库的文章相似性分类（Radev等人，2013年）；

•图像：CIFAR10数据集上的对象识别（Krizhevsky，2009），表示为像素序列。由于序列长度较大，因此任务具有挑战性，通过选择字符/像素级表示故意增加序列长度。有关这些任务的概述，请参见附录。我们不包括Pathfinder（合成图像分类任务），因为我们无法重现Tay等人在这项任务中的结果，即使是通过与作者的通信。

我们在两种有效的Transformer模型上评估SPE（选通变体）：softmax执行器（Choromanski et al.，2020）和线性Transformer（Katharopoulos et al.，2020），使用ReLU特征映射，即在（3）中选择φ（·）=max（0，·）元素。4应该注意的是，ReLU特征映射并不近似于softmax核，SPE的设计目标（见假设8）。尽管如此，在实践中可以将SPE与任何特征映射一起使用，这使得我们可以将线性TransformerReu作为一个有趣的测试来概括替代核。我们采用Tay等人的配置，仅更改PE和批量大小/学习率，以允许在有限的硬件上进行具有类似结果的训练。所有其他超参数保持与原始LRA相同。值得注意的是，图像模型与其他模型不同，它们采用单层网络，仅使用第一个位置进行预测，极大地限制了它们从相对位置信息中获益的能力。

由于我们观察到不同运行之间的一些变化，我们对每个模型进行了3次训练和评估（卷积SPE的执行者除外，其计算成本更高），并报告结果的平均值和标准偏差。

基准测试结果如表1所示。基线线性Transformer（APE）实现的精度与Tay等人报告的精度相似或超过，这是对我们实验装置的明确验证。

讨论ListOps的结果总体较差，准确率约为17%。这符合Tay等人（2021年）的观点，他认为“基于核的模型[例如，执行者、线性Transformer]在层次结构数据上可能没有那么有效”，留下了改进的余地。我们还假设这主要是由于该任务的训练数据存在一些已知问题，不幸的是，在撰写本文时这些问题尚未得到解决。5

关于SPE的性能，我们首先注意到sineSPE变体在三项任务上产生了最佳结果，这是一项巨大的成就，并验证了我们的方法，特别是考虑到该评估基准的难度。虽然它在列表操作和文本方面仅略优于APE，但值得一提的是，sineSPE与线性TransformerReLU的结合使精度提高了∼与Tay等人（2021年）获得的最佳结果相比，检索率为3%。

关于convSPE，其在LRA中的表现不如后面第3.2节中报告的音乐生成实验那么显著。这一减轻的结果似乎与Wang等人（2021年）的讨论相矛盾，后者将注意力的消失视为PE的一个理想属性。相反，我们根据经验观察到，我们的非消失正弦版本sineSPE在这些特定任务中表现得更好。

最后，考虑到这些模型利用相对位置的能力有限，APE在图像上的优越结果并不意外。相反，SPE在这项任务上相对良好的性能实际上是显著的，特别是考虑到这项任务的基线系统使用可学习的APE。

正如我们将在稍后的音乐生成实验中看到的那样，我们提出的SPE在某些任务中显然产生了显著的改进。在LRA中，我们注意到它并没有明显和系统地提高性能。这引起了有趣的考虑：

（i） 蒙特卡罗估计的方差可能有问题。我们对Performer中的随机特征图的优雅公式充满热情，这是一个强烈的灵感。尽管如此，我们必须承认他们的计算依赖于蒙特卡罗估计（15）。我们怀疑估计量的方差可能在大维度的最终性能中发挥作用，这为探索方差缩减估计方法而不是简单的蒙特卡罗方法开辟了方向。

（ii）LRA任务可能不会受益于强（R）PE计划。LRA旨在比较Transformer架构，填补该领域的空白，并作为事实上的标准，证明我们的选择是合理的。然而，尽管PE在许多情况下都很重要，但不知道在LRA任务中是否如此。我们认为有空间进行这样的专门比较，这将安排在我们未来的工作中，可能导致新的长期任务，其中PE至关重要。

3.2.流行钢琴音乐一代

在我们的音乐生成实验（本小节和第3.3节）中，音乐被表示为符号序列（标记），Performer（Choromanski等人，2020）被用作自回归语言模型，该模型预测了给定过去上下文的下一个标记的概率分布。在测试时，通过对下一个标记进行迭代采样来生成一个新的序列，这在文本生成中很常见。

实验装置。

我们在一个由1747首流行钢琴曲目组成的数据集上训练Performer进行音乐生成，每层24层8个头，使用最新提出的改进MIDI衍生格式进行编码（REMI；Huang&Yang，2020）。这些序列由韵律符号组成：小节、次拍和节奏，它们代表音乐的计时；和音符标记：和弦、音高、持续时间和音量，用于描述音乐内容（更多详细信息，请参见附录）。我们拿出5%的歌曲作为验证集。

我们训练序列长度N=2048的模型，对应于∼一分钟的音乐。我们的模型之间唯一的区别是PE策略。我们考虑基线猿，以及SPE：正弦或卷积，有或没有门控，导致5种不同的模型。

结果和讨论。

对于定性评估，我们首先在图1中显示了每个PE模型的一种注意模式：APE和（门控）sineSPE/convSPE，作为所选（层、头部）20多个从头开始的epoch的平均值。更多类似图见附录。有趣的是，我们注意到，对于早期层次，猿的注意力并没有超出训练序列的长度。SPE变体中未发现这种行为，它们始终注意所有位置。建议模型的另一个显著特征（仅在附录中显示）是，第2.2节中所述的选通在视觉上完全禁用某些层/头的PE，在这种情况下，注意力是全局的。

由于文献表明RPE提高了泛化性能（Shaw等人，2018年；Zhou等人，2019年；Rosendahl等人，2019年），我们在图3中显示了通过教师强制（Williams&Zipser，1989年）计算的验证交叉熵，作为目标标记位置的函数。这些值将表明，对于验证集中的轨迹，模型在给定前面标记的特定位置预测标记的效果如何。我们注意到，所有SPE变体，尤其是convSPE，在超过2048的令牌位置上的表现都比APE好得多。这表明SPE继承了RPE的这一著名优势（Huang et al.，2018），同时适用于更长的序列。

最近，Wang等人（2021年）定义了PE评估指标，表明平移不变性和单调性是理想的属性。前者规定两个任意τ-偏移位置嵌入的距离应相同，而后者规定相邻位置应分配比远处更近的位置嵌入。按照他们相同的单词探测方法，我们在图4中报告了这些指标。正如所料，SPE变体在翻译不变性方面大大优于APE。然而，在我们的音乐应用程序中，单调性似乎不是一个非常相关的标准，在比较图3和图4中的分数时可以看出这一点。音乐建模似乎可以从非消失的注意力模式中获益。在任何情况下，SPE分数在各个位置上都非常稳定，与APE相反，APE在训练时间之外会迅速下降。

3.3.沟槽延伸

在这个实验中，我们评估了groove延续任务的执行者。在每个示例都有统一风格（“groove”）的数据集上进行训练后，我们用一个短提示（2小节音乐片段）初始化模型，并让它生成一个延续。然后，我们观察生成的延续是否与提示的样式匹配。

实验装置。

模型（24层Performer，8个注意头）在伴奏数据集上进行训练，该数据集包括2761种不同音乐风格的5522个样本，采用Cıfka等人（2020）采用的基于标记的格式进行编码，详情见附录。在本实验中，所有基于SPE的模型都使用选通。不同于以前的实验，它利用长的训练序列，我们考虑训练序列长度n＝512，对应于2至10巴。在测试时，用训练期间未出现的样式的2个条提示模型，并对新标记进行采样，以完成长度为1024（即训练长度的两倍）的序列。

我们使用两种音乐风格相似性度量——Cıfka等人（2019；2020）提出的时间音高和开始持续时间——来量化生成的延续与提示的相似性。当听生成的音乐时，我们会在感知上注意到质量随时间的变化。出于这个原因，我们将每个生成的样本分成四个持续时间相同的连续块，并对它们进行独立评估。结果如图5所示。

讨论

我们清楚地看到，SPE在这两个指标上都大大优于APE。虽然在序列开始时，APE显然能够生成接近所需风格的样式，但这种相似性随着时间的推移会大大降低。sineSPE和convSPE在这方面都更稳定，证实了第3.2节的结果，即SPE在训练序列长度之外的推断更好。这与我们的非正式感知评估相吻合

该实验表明，利用局部邻域是处理长序列的一种稳健方法。这可能与远程Transformer的使用相矛盾，但我们强调此处使用了选通，使一些头部能够独立于位置利用长期注意力。尽管由于Tay等人（2021年）的原因，此处未将其包括在内，但与局部注意力计划（如Dai等人，2019年；Hofster等人，2020年）的进一步比较可能会很有趣，这表明它们明显较低，至少在LRA环境中是如此。

4.相关工作

本文注意PE（Sukhbatar et al.，2015），将其作为嵌入每个令牌位置的一种方式，作为其功能的一部分。这一想法是许多后续突破性研究的核心内容（Gehring等人，2017年；Vaswani等人，2017年），也是许多调查的实际主题。

基于Vaswani等人（2017年）的正弦信号的绝对位置编码（APE）是Transformer类结构中最广泛使用的编码。然而，（5）中的PE q（n）和k（n）也可以像在BERT中一样进行训练（Devlin等人，2019；Liu等人，2019）。虽然原始Transformer仅包括输入层的PE，但可能包括所有层（Dehghani等人，2019年；Lan等人，2020年）。

相对位置编码（RPE；Shaw等人，2018）是利用相对位置的一种方法。它具有O（N2D）空间复杂性，在Huang等人（2018年）中将其降低为O（N2）；他等人（2020年）。Raffel等人（2020年）建议考虑对数距离。介绍了RPE的几种变体（Huang等人，2020年；Wang等人，2021年）。他们都在注意域中应用习得的RPE。RPE也考虑使用固定嵌入函数（Pham等人，2020年），Kim等人（2020年）使用掩蔽RPE来促进局部注意。

键域与注意域。

在关键领域进行PE引入了位置内容交叉术语，在Ke等人（2020年）中，这些术语被认为是嘈杂且不有益的，并被无限制的注意力所取代，即在注意力领域进行PE。这在He等人（2020年）中也被称为分散注意力，在Tsai等人（2019年）中已经通过可分离的内容-位置-注意力核提出。所有这些研究都需要A的显式计算和存储。

对于结构化输入，考虑了非整数位置。针对APE（Shiv&Quirk，2019；Xiao et al.，2019；Ma et al.，2019）和RPE（Omote et al.，2019），提出了基于树的PE。Bose等人（2019）发现了任意多边形内机器人的位置编码。

PE的动力学模型。

Bahdanaau等人（2016年）引入了对机器翻译的注意，Ke等人（2020年）回顾性地将机器翻译理解为使用递归神经网络（RNN）进行PE。Chen等人（2018）认为编码器RNN的隐藏状态包含足够的位置信息，可以跳过显式PE。Neishi&Yoshinaga（2019）基于这一观点，但首次明确描述了这一想法。他们的贡献是用RNN代替（5）中的添加剂PE。同样，Liu等人（2020年）使用（神经）常微分方程生成PE。

卷积上下文。

我们的convSPE变体涉及卷积随机噪声。首先，这可能与Mohamed等人（2019年）有关，他们使用卷积神经网络进行查询和键计算。其次，Xu等人（2020年）最近强调了卷积和平稳过程之间的联系。

乘法PE。

不同层次的内容-位置交互在（Tsai等人，2019年）中正式化。针对RPE（Huang等人，2020年）和APE（Dai等人，2019年）提出了乘法策略。后者在Tsai等人（2019年）中得到推广。所有这些都需要注意矩阵的显式计算。Wang等人（2020a）提出了一个方案，该方案接近我们的正弦变体，但没有随机部分，这是从（14）到（15）的关键。

一些作者强调了APE和RPE的局限性。在Wang&Chen（2020）中，表现最好的模型利用了绝对位置和相对位置。在Irie et al.（2019）和Tsai et al.（2019）中，发现在基于Transformer的架构的因果解码器部分中完全去除APE会导致可比/更好的性能。在将PE合并到原始输入信号中（并因此通过值项传播）或仅在查询和键上重新使用PE（如我们所做的）之间，哪一个最好也不清楚。蔡等人（2019年）支持我们的选择。

5.结论

我们提出了一种新的基于随机噪声滤波的随机位置编码（SPE）。正如我们所展示的，该程序概括了相对PE，是实施任何规定的（但经过训练的）互协方差结构的原则性手段，我们证明了这应该是点积注意的中心问题。在我们的实验中，我们表明，与经典（正弦）PE相比，SPE在大型Transformer模型（Choromanski et al.，2020；Katharopoulos et al.，2020）的性能方面带来了有趣的增益。这是意料之中的，因为RPE（Shaw等人，2018年）通常被认为是有益的。然而，到目前为止，还没有将其用于长序列的方法，这是本文的核心贡献。我们研究的自然未来方向是（i）信号相关PE，将输入序列作为SPE的额外输入，（ii）利用相对和绝对位置的非平稳PE，（iii）将我们的方法扩展到任意注意核，例如，通过（4）中的（随机）映射隐式定义。事实上，这里介绍的SPE理论上只适用于点积注意核，但我们在表1中给出的结果表明，这是一个概括，提出了一个有趣的研究问题。

介绍

本文件包含由于篇幅限制而无法纳入本文件的其他信息。它的结构如下。在附录A中，我们提供了一些进一步的理论发展。在附录B中，我们详细介绍了Long-Range Arena上的实验装置。在附录C中，我们详细介绍了我们的音乐生成实验。最后，我们在附录D中提供了其他结果。

我们的源代码位于：

https://github.com/aliutkus/spe/

另见配套网站：

https://cifkao.github.io/spe/

A.理论

A.1。卷积SPE导致注意力消失

在主要文献中，我们声称卷积变体导致注意力消失。我们很快就在这里证明了这一说法。为了便于记谱，证明是在1D的情况下给出的，但很容易扩展到更高的维度。核心思想如图6所示。卷积SPE产量：

其中Zd是高斯白噪声过程，即e[Zd（m，r）Zd（m0，r）]=δmm0。为了便于记法（所有实现都是独立的），省略对r的依赖，我们可以计算位置注意：

其中，只有（p，τ）值使得n−p=m−τ保持不变，所有其他交叉项E[Zd（m）Zd（m0=m）]由于Zd的白度而消失。过滤器被视为[0:P]之外的0值。可以看出，只要| m− n |>P，我们得到Pd（m，n）=0，因为φKd（P+（m− n） ）=0。

A.2。复杂性

在本节中，我们将详细介绍所提出的SPE方法带来的额外复杂性。

•正弦SPE首先需要计算调制矩阵Ω 对于每个特征尺寸d=1。D、 具有O（2NK）复杂度。然后，该矩阵必须与形状为2K×R的噪声矩阵Zd相乘，从而导致总体复杂度为O（DRNK2）。由于K在我们的实验中通常非常小，所以SineSPE在时间和空间复杂性方面都可以被视为非常轻。

•卷积SPE涉及为每个d和r绘制长度为N的新噪声信号zd，：，r，并使用长度为P的滤波器φQd和φKd对其进行卷积。在1D的情况下，这导致总体时间复杂度为O（DRNP），可以用O（DRN log N）代替

当在频域中操作卷积时，这对于长滤波器是有利的。在更高的维度中，例如2D，这在原始域中变成O（DRN1N2P1P2），在频域中变成O（DRN1N2 log N1 log N2），其中（N1，N2）和（P1，P2）分别是噪声和滤波器的形状。

•选通的瓶颈是随机噪声d的产生，其复杂性为O（DR）。

请注意，这种复杂性当然必须乘以所考虑的头部数量，在我们的实验中最多为8个。

可以看出，正弦和卷积变体的复杂性相似，这取决于滤波器的长度P和正弦的数量K。不过，其他方面也在起作用。首先，卷积型需要生成大小为N的噪声，而正弦型需要更小的2K大噪声矩阵。第二，在我们的实验中，只需要极少量的正弦波，而卷积版本需要更长的上下文，因此我们在实践中通常有2kp。最后，尽管这在不久的将来可能会改变，但像PyTorch这样的深度学习框架不容易在频域中集成卷积。

样本噪声共享。

实际上，不需要为每个示例重新绘制SPE。减少该方法内存和计算占用的最直接的技巧是在每个小批量中的所有示例之间共享Q和K，就像我们在所有实验中所做的那样。除了使用大批量训练的网络外，当SPE用作drop时，这可以显著节省内存。

B.实验装置：Long-Range Arena

表2给出了Long-Range Arena（Tay等人，2021年）任务的概述。在本文中，我们不包括Pathfinder（合成图像分类任务）或其更难的变体Pathfinder-X，因为我们无法重现Tay等人在该任务中的结果。Tay等人对所有数据集进行了详细描述，并可从官方LRA存储库获得。7

在所有LRA实验中，我们都采用了带R的选通SPE∈ {32, 64}. 对于正弦（周期性）SPE，我们始终使用K=10；对于卷积SPE，我们始终使用长度为128的滤波器。对于卷积SPE，我们在所有层上共享Q和K（但在注意头上不共享）；对于正弦SPE，Q和K对于每个层和头部都是唯一的；在这两种情况下，都采用了层特定的选通。基线实验采用了与Tay等人相同的绝对位置编码（图像的可学习APE和剩余任务的正弦APE）。在采用SPE的模型中，APE被删除。

主要文件中给出的模型参数数量如表3所示。我们可以看到，基于SPE的模型的参数最多比基线多3.1%。在图像列中，基于SPE的模型的数量大约减少了50%，这是因为该任务的基线采用了可学习的APE。

我们使用来自官方LRA存储库的代码，包括作者的Transformer实现，根据需要进行修改以合并SPE。我们保持LRA作者提供的相同训练配置，但减少批量大小（图像从256到96，其余从32到8）和学习速率，以适应16GB的GPU内存。我们修改过的代码和配置文件可以在源代码存储库中找到。

B.1。资源利用

LRA模型的典型训练时间如表4所示。请注意，由于在某些运行中比在其他运行中更频繁地进行评估（这可能会很耗时），因此不同模型或任务之间的时间可能不具有可比性。

总训练时间为1405小时（总共189次），其中273小时（61次）用于尝试使用Performer softmax、Linear Transformer ReLU和vanilla Transformer再现Tay等人（2021年）的结果。其中一些初步实验分布在1–3个特斯拉V100 GPU上，每个GPU内存为32 GB。最终的模型都是在一个具有16GB内存的特斯拉V100或P100GPU上训练的。

[if !supportLists]C. [endif]实验设置：音乐生成

我们的音乐Performer使用pytorch fast transformers包实现，8根据需要进行修改，以纳入SPE。我们的代码库中提供了修改后的代码和配置文件。

所有模型都有24层，模型尺寸为512，8个注意头和2048个前馈单元，相当于∼8000万个可训练参数。在使用SPE的模型中，Q和K在所有层之间共享（但不在注意头之间）；层特定选通用于使用选通SPE训练的模型。

模型使用Adam优化器进行训练。我们通过线性预热，然后是余弦衰减来安排学习速率。可以在提供的配置文件中找到hyperparameters的完整详细信息。

C.1。流行钢琴音乐一代

训练数据。

我们使用的流行钢琴MIDI数据源于Xiao et al.（2021）中提供的数据集，该数据集在GitHub上开源。9该数据集包含1747首不同日本、韩国和西方流行歌曲的纯钢琴表演，总持续时间为∼100小时。所有歌曲都是4/4时间签名，即每小节四拍（测量）。我们留下5%（87首歌曲）作为验证集。

根据萧等人（2021年）的说法，钢琴表演最初是以MP3（音频）格式从互联网上收集的。Xiao等人进一步采用了Onsets and Frames钢琴转录（Hawthorne等人，2018）、madmom节拍跟踪工具（B¨ock等人，2016）和基于chorder规则的和弦检测10，将音频转录成MIDI格式，并包含节奏、节拍和和弦信息。

数据表示。

这里采用的表示法与Huang&Yang（2020）改进的MIDI派生（REMI）编码基本相同，只是使用了一组扩展的和弦标记（如下所述）。REMI将一首钢琴曲编码为一个由两种类型（韵律和音符）的标记组成的序列。韵律符号为：

•酒吧：标志着音乐酒吧的开始。

•子节拍：标记酒吧内的音乐计时。一个小节被分成16个子节拍，相当于4个节拍。这种符号计时为序列模型建模音乐提供了一个明确的时间网格。

•节奏：确定演奏乐曲的速度（以每分钟的节拍或bpm为单位），每小节不同。节奏标记的范围为[32224]bpm，量化的步长为3 bpm。

注释标记为：

•音高：标记播放的音符。88个音高对应钢琴上的每个键。

•持续时间：表示播放的音符的长度，范围为1/2到16次拍，以1/2次拍为单位。

•音量（或速度）：表示音符的音量。总共考虑了24个音量级别。

•和弦：在伴奏和弦上标记更改。每个和弦都由其根音符和音质来描述，例如C-Maj7、e-min。数据集中总共有133个不同的和弦标记。

请注意，演奏的单个音符由一个连续的三重音符（音高、持续时间、音量）表示。上述标记构成了一个大小不同的词汇表∼340用于我们的REMI编码。平均来说，我们需要一个包含5300个标记的序列来表示一首歌。

训练和推理。

在每个训练阶段，我们从每个样本中随机裁剪出长度为2048的片段，并将整个片段的音高偏移−随机6到6个半音（音乐中称为转置）作为数据增强。我们使用批量大小=4，并将APE的学习率设置为0.0001，所有SPE模型的学习率设置为0.0002。对于sineSPE，我们选择sines的数量K=5；对于convSPE，对于选通和非选通变体，卷积滤波器大小分别设置为128和512。

每个模型的详细资源使用情况如表5所示。

在推断过程中，我们采用核取样（Holtzman et al.，2019），p=0.9，softmax温度t=1.2。没有对生成序列的语法正确性进行后处理。

表6列出了在此任务中训练的模型的验证损失。在这个指标上，我们的convSPE变体在经过训练的位置内和外推上都表现最佳。

C.2。沟槽延伸

训练数据。

Groove2Groove MIDI数据集11由盒带软件（BIAB）生成的伴奏组成。12我们仅使用Groove2Groove MIDI数据集的训练部分，并执行自定义训练/验证/测试分割，以便每个部分包含一组独特的BIAB样式（训练为2761，验证和测试为50）. 存储库中包含下载、预处理和拆分数据集所需的代码。

我们将每个伴奏转换为三重奏，包括贝司、鼓和另一个随机选择的伴奏曲目（如钢琴、吉他）。然后，我们通过在开始时跳过测量值、丢弃一些仪器和转置（音高偏移）来执行随机数据增强−5到+5个半音）。所有随机化都在每个时期重新进行。

数据表示。

我们使用了类似于Cıfka等人（2020）提出的表示法，但适用于多轨道（多仪器）设置。具体地说，我们将一段音乐编码为以下类型的事件标记序列，每个事件标记具有两个整数参数：

•音符（音轨、音高）：以给定音高（0–127）开始一个新音符。

•音符结束（音轨、音高）：在给定音高（0–127）结束音符。

•时间偏移（节拍，偏移）：将当前时间提前给定的节拍数，然后设置节拍内的偏移量，以从开始（0–11）开始的节拍数表示。最大可能换档为（2，0）。

曲目编号范围为1到3，其中1始终为低音，2始终为鼓。然后，该模型的词汇表由794个标记组成（3×128个注释、3×128个注释、24个时间偏移和2个序列开始/结束标记）。

与第C.1节中描述的表示法的主要区别在于更紧凑的计时编码，没有音乐动态的表示法（为简单起见），以及对多首曲目的支持（最初不是由Cıfka等人提出的，2020年，但此处由Donahue等人提出，2019年）。训练和推理。

在训练期间，如上所述对每个示例进行预处理和编码，并将得到的令牌序列截断为512的长度。我们对每个模型进行总共24个阶段的训练。

在测试时，我们以0.6的最高软温度取样。为了确保生成的序列能够正确解码，我们不允许使用会导致无效序列（即虚假注释、向后时间偏移）的采样令牌。

各种训练细节。

超参数调谐主要在初步实验中进行(∼100次）；这些主要是在数据集的其他变体上进行的，并且具有不同的序列长度（从256到20K）；这包括由于在训练期间或训练后发现错误而丢弃的实验。学习率介于0.0001和0.0008之间，批量大小介于1和24之间。对于SPE，我们考虑了门控和非门控变体，它们在内存中的实现数量尽可能多（介于16和64之间）。模型选择基于验证损失和非正式感知评估。对于长度为512的最后一组模型，只进行了最小程度的进一步学习率调整，这似乎对它不太敏感，我们选择将初始学习率保持在0.0004，这在所有情况下都表现良好。

主文档中包括的模型——APE、sineSPE和convSPE——都使用10个批量，分别在大约3小时、5小时和6小时内完成训练，使用9.7 GB、14.4 GB和14.8 GB的GPU内存。包括所有初步实验在内的总训练时间为852小时。

评价指标。

我们使用Cıfka等人（2019；2020）提出的客观指标来衡量生成的延续和从中提取提示的文件之间的风格相似性。给定两段音乐，每个指标以称为风格配置文件的直方图收集这两段音乐的音乐事件统计信息，然后计算它们之间的余弦相似性。

此处使用的两个指标，即开始持续时间和时间间隔，在构建样式配置文件时使用的事件类型上有所不同：

•开始持续时间剖面定义为2D柱状图，将音符开始位置与音符持续时间关联起来。更准确地说，对于一段音乐中的所有音符，它记录了形式的元组

（开始（a）模块4，结束（a）− 开始（a））∈ [0, 4) × [0, 2),

其中start（a）和end（a）是指a的开始时间和偏移时间（以拍为单位）。表达式start（a）mod 4表示音符开始相对于当前条的位置，因为数据集中的所有示例都在一个4拍表中。这些元组收集在24×12柱状图中（24表示开始时间，12表示持续时间）。

•时间-音高曲线也以2D柱状图的形式获得，这一次捕获音符之间的时间差和音高差（间隔）。它认为元组具有以下形式

其中a，b是一对音符，而音高（·）表示一个音符的音高作为其MIDI音符编号（来自C的半音数量）−1） 。直方图有24×41个单元（24个用于0到4拍之间的时间间隔，41个单元用于0到4拍之间的间隔）−20和20个半音）。

在这两种情况下，二维直方图在计算余弦相似性之前被展平为向量。

D.其他结果

D.1。注意力可视化：音乐生成

在本节中，我们将展示流行钢琴音乐生成模型产生的注意力模式。

学习位置模板。

我们在执行者的所有层上共享SPE模块，但不在注意头上共享，从而产生512个已学习的位置核Pd（每个头的头数×关键尺寸）。在图7中，我们为sineSPE和convSPE显示了16个随机挑选的结果模板Pd，并使用选通进行了训练。这两个变体的详细信息如下：

•sineSPE：我们设置sines的数量K=5。

•convSPE：我们使用大小为128的过滤器。

根据定义，所有可视化都用方程Pd=QdK>d绘制，我们永远不需要对线性Transformer进行显式计算。从图7中，我们可以观察到sineSPE学习利用广泛的频率范围，并且convSPE在与滤波器相对应的小查询键偏移内有效大小如预期。

全神贯注。

虽然在线性Transformer中没有计算完全注意矩阵A，但我们仍然可以通过将查询和键乘以A=exp（QK>/√D） （对于APE，其中D是每个头部的关键尺寸），或A=exp（bQbK>/√R） （对于SPE）；然后对as规范化应用行softmax操作。

在这里，我们展示了第1、3、12、20和24（最后一个）中的（softmax ed）注意矩阵图8-12显示了所有五个模型在流行钢琴音乐生成方面的层次。这些层次是从每个模型的一个随机从无到有的音乐生成中计算出来的。为了检验模型的外推能力，我们让它们生成一个长度为3072的序列，而训练序列长度仅为2048。注意矩阵为l由于因果掩蔽，每个像素的颜色通过图中的min{1，amn 0.4/0.020.4}进行调整，以获得更好的可视化效果，其中amn∈ [0,1]是软最大ed注意分数。

图8揭示了APE的一个主要缺点：标记的注意力超出位置2048（训练序列长度）似乎将注意力集中在早期的2 048左右，而不是注意全局或局部。这种行为在我们的任何SPE模型中都没有发现。这可能解释了APE对长序列的泛化能力差的原因，这是由于位置2 048后验证损失的显著增加（参见主要论文中的图3和此处的表6）。

接下来，比较图9和图10，很明显，门控SPE使模型可以自由关闭某些头部的PE以获得全局注意力（见图9），而非门控sineSPE（图10）的注意力基本上保持周期性，这可能并不总是可取的。convSPE也可以这样说（图11和图12）门控的CurpSe能比中间层更远地看中间层。

D.2.注意力可视化：CIFAR10

图13显示了从LRA CIFAR10任务中训练的模型中提取的注意图。注意，这些是单层网络，分类是通过在像素值序列中预先添加一个特殊的CLS标记，并使用第一个位置的输出作为前馈分类器的输入来完成的。因此，只有在这个位置的注意图单个位置（我们在这里显示的位置）很重要。（因此，该模型实际上不使用自注意，而是使用单个查询和多个键的注意。这消除了相对位置和绝对位置之间的区别，这可能解释了为什么可训练APE在这项任务上比SPE表现更好。）

D.3.所需PE性能的评估

我们使用相同的单词探测和Wang等人（2021年）介绍的相关度量来比较APE和SPE的翻译不变性和单调性。这项工作中提到的其他属性，即对称性和方向平衡，在这里不进行评估，因为在我们的例子中注意力是单向的。模特们还接受了流行钢琴音乐的训练。

根据第一层中每个头部的注意矩阵计算指标，在所有可能的相同标记序列（即，由重复的相同标记组成的序列；有∼其中340个用于我们的REMI词汇表）。为了消除应用带因果掩蔽的行softmax对平移不变性属性的影响，我们计算了非规范化注意矩阵的度量，即A=exp（QK>/√D） 对于APE，A=exp（bQbK>/√R） 对于SPE。我们考虑了查询位置和查询键偏移量的各种组合，以检查当我们外推到更长的序列时，PE属性是否保持一致，以及研究它们在局部和长期注意广度中的行为。

我们在表7中报告了每个模型中表现最好（即得分最低）的负责人的得分。从表中，我们可以注意到，在外推的情况下，APE的PE特性通常会急剧恶化。相反，未分级SPE模型的分数，即我们在每一层强制合并位置信息的模型，在整个位置上保持显著一致。这里的评估为SPE的外推能力提供了额外的证据。

D.4。实现数量R的影响

在主要文档中，我们讨论了当R增长到无穷大时，SPE如何渐近地导致期望的互协方差结构。在本节中，我们实证研究了该参数在实践中对绩效的影响。首先要强调的是，每个训练批次都会产生一组新的噪声Zd实现，这样网络就可以平均看到正确的注意模式。

然而，我们可能想知道实现的数量R是如何影响训练和测试性能的。人们确实可以注意到，在训练和推理过程中，R的设置可能完全不同，因为它对模型的实际参数/结构的形状没有影响。因此，我们进行了一项消融研究，在该研究中，我们在训练时使用不同的Rtrain值，得到一个经过训练的模型，然后使用可能不同的Rtest值评估其性能。结果如图14所示。

我们可以注意到，对于相同的Rtrain，使用Rtest=Rtrain（以粗体突出显示）获得的结果始终接近最佳结果，相反，选择Rtest=Rtrain通常会导致较差的结果。换句话说，使用相同的R进行训练和测试似乎有利于始终保持良好的绩效。

另一个值得注意的事实是，更高的R似乎并不意味着更好的性能，即使Rtest=Rtrain。相反，convSPE在R=4时达到了目前为止的最高精度。这个意想不到的结果似乎与它意味着更嘈杂的注意力模式这一事实相矛盾。需要进一步的研究来解释这一现象，但我们推测，注意模式中的额外噪声会增加训练模型的鲁棒性，从而有助于推广。