Transformer

一、Transformer[2017]

1. 循环神经网络RNN （尤其是 LSTM、GRU 网络）已经牢牢地被确定为序列建模和转导transduction 问题的 state-of-the-art 方法。此后，许多努力继续推动循环语言模型 recurrent language model 和 encoder-decoder 的发展。

   循环模型通常沿输入序列和输出序列的 symbol position 来考虑计算。将 position 和 step 在计算期间对齐 aligning ，这些模型生成一系列 hidden state ${\overrightarrow{\mathbf{h}}}_t$$\mathbf{\vec h}_t$ ，其中 ${\overrightarrow{\mathbf{h}}}_t$$\mathbf{\vec h}_t$ 是前一个hidden state ${\overrightarrow{\mathbf{h}}}_{t-1}$$\mathbf{\vec h}_{t-1}$ 和 $t$$t$ 时刻 input 的函数。这种固有的序列性质 sequential nature 阻止了训练样本内的并行化，而这种样本内的并行化在更长的序列长度下变得至关重要，因为内存约束限制了样本之间的 batching 。最近的工作通过分解factorization 和条件计算 conditional computation 显著提高了计算效率，同时在后者的 case 中（即，条件计算）也提高了模型性能。然而，序列计算sequential computation的基本约束仍然存在。

   注意力机制已经成为各种任务中引人注目的序列建模和转导模型 sequence modeling and transduction model 的组成部分，它允许建模依赖性而无需考虑这些相互依赖的项在 input 序列或 output 序列中的距离。然而，除了少数情况之外，这种注意力机制与RNN 结合使用。

   在论文 《Attention Is All You Need》 中，作者提出了 Transformer，这是一种避免循环 recurrence 的模型架构。Transformer 完全依赖注意力机制来抽取 input 和 output 之间的全局依赖关系。Transformer 可以实现更高的并行化，并且在八个 P100 GPU 上经过短短 12 个小时的训练后就可以在翻译质量方面达到新的 state-of-the-art 。

2. 背景：

   • 减少序列计算这一目标也构成了 Extended Neural GPU、ByteNet、ConvS2S 的基础，它们都使用卷积神经网络作为基础构建块 basic building block ，并行地为所有 input position 和 output position 来计算 hidden representation 。在这些模型中，联系 relate 来自两个任意 input position 或 output position 的信号所需操作的数量，随着 position 之间的距离而增加：对于 ConvS2S 呈线性增加，而对于 ByteNet 则呈对数增加。这使得学习远距离位置之间的依赖性变得更加困难。

     在 Transformer ，这种数量被降低到常数级（$O(1)$$O(1)$），尽管以降低有效分辨率 effective resolution 为代价（由于attention-weighted 加权平均 ），但是我们使用多头注意力 Multi-Head Attention 来抵消这种影响。

   • 自注意力self-attention（有时被称作 intra-attention）是一种将单个序列的不同位置关联起来从而计算序列的 representation 的注意力机制。自注意力已经成功应用于各种任务，包括阅读理解reading comprehension、抽象摘要abstractive summarization、文本蕴含textual entailment、学习任务无关的 sentence representation 。

   • 端到端记忆网络memory network 基于循环注意力机制 recurrent attention mechanism 而不是序列对齐循环 sequence-aligned recurrence，并且已被证明在简单的语言问题和语言建模任务中表现良好。

   然而，据我们所知，Transformer 是第一个完全依赖自注意力来计算其 input 和 output 的 representation 而不使用 sequence-aligned RNN 或卷积的模型。在接下来部分中，我们将描述 Transformer、自注意力的启发，并讨论它相对于 《Neural GPUs learn algorithms》、《Neural machine translation in linear time》、《Structured attention networks》 等模型的优势。

1.1 模型

1.1.1 模型架构

1. 大多数有竞争力的神经序列转导模型 neural sequence transduction model 具有 encoder-decoder 结构。这里，encoder 将 symbol representation 的输入序列 $\mathbf{x}=({\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2,\cdots ,{\overrightarrow{\mathbf{x}}}_n)$$\mathbf x = \left(\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_n\right)$ 映射到 continuous representation 的序列 $\mathbf{z}=({\overrightarrow{\mathbf{z}}}_1,\cdots ,{\overrightarrow{\mathbf{z}}}_n)$$\mathbf z = \left(\mathbf{\vec z}_1,\cdots,\mathbf{\vec z}_n\right)$，其中 $n$$n$ 为输入序列长度，${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为第 $i$$i$ 个输入 symbol representation （one-hot 向量），${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ 为第 $i$$i$ 个 hidden representation 。 给定 $\mathbf{z}$$\mathbf z$ ，decoder 然后生成 symbol 的一个输出序列 $({\overrightarrow{\mathbf{y}}}_1,{\overrightarrow{\mathbf{y}}}_2,\cdots ,{\overrightarrow{\mathbf{y}}}_m)$$\left(\mathbf{\vec y}_1,\mathbf{\vec y}_2,\cdots,\mathbf{\vec y}_m\right)$ ，一次输出一个元素，其中 $m$$m$ 为输出序列长度，${\overrightarrow{\mathbf{y}}}_j$$\mathbf{\vec y}_j$ 为第 $j$$j$ 个输出 symbol representation （one-hot 向量）。在每个 step，模型都是自回归auto-regressive的，在生成下一个输出symbol 时使用所有前面生成的 symbol 作为额外的输入。

   Transformer 遵循这种整体架构，同时为 encoder 和 decoder 使用堆叠的 self-attention的和 point-wise 的全连接层，分别如下图的左半部分和有半部分所示。

   下图中的 attention 的三个输入中，最右侧为 query 而其它两个输入分别为 key,value 。注意，key 的数量和 value 的数量相等。

   

2. Encoder：encoder 由 $N=6$$N = 6$ 个相同的层堆叠而成。每个层有两个子层：第一个子层是多头注意力机制 multi-head self-attention mechanism， 第二个子层是简单的、position-wise 的全连接前馈神经网络。我们在两个子层中的每个子层周围使用残差连接 residual connection ，然后进行 layer normalization 。即，每个子层的输出为：

   $$\text{LayerNorm}(\overrightarrow{\mathbf{x}}+\text{Sublayer}\left(\overrightarrow{\mathbf{x}}\right))$$

   其中：$\text{Sublayer}\left(\overrightarrow{\mathbf{x}}\right)$$\text{Sublayer}\left(\mathbf{\vec x}\right)$ 是子层自己实现的函数。

   为了有助于这些残差连接，模型中的所有子层以及 embedding layer 都会产生维度 $d_{\text{model}}=512$$d_\text{model} = 512$ 的输出。

   注意，图中黄色框内的标注是 Add & Norm ，即 Add 在前、Norm 在后，也就是 LayerNorm 作用在残差连接之后。

3. Decoder：decoder 也是由 $N=6$$N = 6$ 个相同的层堆叠而成。decoder 的每个层包含三个子层，其中有两个子层与 encoder 子层相同，而第三个子层对 encoder stack 的输出执行 multi-head attention 。

   与 encoder 类似，我们在每个子层周围使用残差连接，然后进行 layer normalization 。我们还修改了 decoder stack 中的 self-attention 子层，从而防止它关注后续的 position （即，masked self-attention）。这种 masking 确保对 position $i$$i$ 的预测只能依赖于位置小于 $i$$i$ 的已知输出。

1.1.2 Attention

1. 注意力函数可以描述为：将一个 query 和一组 key-value pair 映射到 output ，其中 query, key, value, output 都是向量。output 被计算为 value 的加权和，其中每个 value 的权重是由一个函数来计算（即，注意力函数），该函数以 query, key 作为输入。

2. Scaled Dot-Product Attention：我们称我们提出的注意力为 Scaled Dot-Product Attention ，如下图所示。输入由三部分组成：维度为 $d_k$$d_k$ 的 query、维度为 $d_k$$d_k$ 的 key、维度为 $d_v$$d_v$ 的 value 。我们将单个 query 和所有的 key 计算内积，然后内积的结果除以 $\sqrt{d_k}$$\sqrt{d_k}$ ，然后对这些内积结果应用 softmax 函数从而获得 value 的权重。

   这里要求 query 向量的维度和 key 向量的维度相同，都是 $d_k$$d_k$ 。

   在实践中，我们同时计算一组 query 的注意力函数，其中将 query 打包到一个矩阵 $\mathbf{Q}$$\mathbf Q$ 中。key 和 value 也被打包到矩阵 $\mathbf{K}$$\mathbf K$ 和 $\mathbf{V}$$\mathbf V$ 中。我们将 output 矩阵计算为：

   $$\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{softmax}\left(\frac{\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}}{\sqrt{d_k}}\right)\mathbf{V}$$

   假设有 $n_q$$n_q$ 个 query、 $n_v$$n_v$ 个 key、 $n_v$$n_v$ 个 value （要求 key 的数量和 value 的数量相同），则：

   $$\mathbf{Q}\in {\mathbb{R}}^{n_q\times d_k},\mathbf{K}\in {\mathbb{R}}^{n_v\times d_k},\mathbf{V}\in {\mathbb{R}}^{n_v\times d_v},\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}\in {\mathbb{R}}^{n_q\times n_v},\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})\in {\mathbb{R}}^{n_q\times d_v}$$

   两种最常见的注意力函数为：加性注意力additive attention、内积注意力dot-product (multiplicative) attention 。

   • 内积注意力与我们的算法相同，除了我们使用了 $1/\sqrt{d_k}$$1/\sqrt{d_k}$ 的缩放因子。

     因为维度越大，则内积中累加和的项越多，内积结果越大。很大的数值会导致 softmax 函数位于饱和区间，梯度几乎为零。

   • 加性注意力通过具有单隐层的前馈神经网络来计算注意力函数。

     additive attention（也称作 Bahdanau Attention ） 的原理为：

     $$\begin{array}{c}{s}_{i,j}={\overrightarrow{\mathbf{w}}}^{\mathrm{\top }}\sigma ({\mathbf{W}}_q{\overrightarrow{\mathbf{q}}}_i+{\mathbf{W}}_k{\overrightarrow{\mathbf{k}}}_j)\\ {\alpha }_{i,j}=\text{softmax}(s_{i,j})=\frac{\exp (s_{i,j})}{\sum _{j^{\prime }}\exp (s_{i,j^{\prime }})}\\ {\overrightarrow{\mathbf{v}}}_i^{\prime }=\sum _{j=1}{\alpha }_{i,j}{\overrightarrow{\mathbf{v}}}_j\end{array}$$

     其中：

     • $\overrightarrow{\mathbf{w}}$$\mathbf {\vec w}$ 为attention 向量，为待学习的参数，$\sigma (\cdot )$$\sigma(\cdot)$ 为非线性函数。
     • ${\overrightarrow{\mathbf{q}}}_i$$\mathbf{\vec q}_i$ 为第 $i$$i$ 个 query，${\overrightarrow{\mathbf{k}}}_j$$\mathbf{\vec k}_j$ 为第 $j$$j$ 个 key，${\overrightarrow{\mathbf{v}}}_j$$\mathbf{\vec v}_j$ 为第 $j$$j$ 个 value 。
     • ${\mathbf{W}}_q$$\mathbf W_q$ 将 query 向量映射到公共空间，${\mathbf{W}}_k$$\mathbf W_k$ 将 key 向量映射到公共空间，因此 query 向量和 key 向量可以为不同的维度。它们都是待学习的权重。
     • ${\alpha }_{i,j}$$\alpha_{i,j}$ 给出第 $i$$i$ 个 query 在各个 position 的注意力权重，position 的数量为 $n_v$$n_v$ 。

   虽然这两种注意力在理论上的复杂度相同，但是内积注意力在实践中更快且更节省内存空间，因为它可以使用高度优化的矩阵乘法代码来实现。

   

3. Multi-Head Attention：与执行单个注意力函数 attention function （具有 $d_{\text{model}}$$d_\text{model}$ 维的 query, key, value ）不同，我们发现将 query, key, value 线性投影 $h$$h$ 次是有益的，其中每次线性投影都是不同的并且将 query, key, value 分别投影到 $d_k,d_k,d_v$$d_k, d_k,d_v$ 维。

   然后，在每个 query, key, value 的投影后的版本上，我们并行执行注意力函数，每个注意力函数产生 $d_v$$d_v$ 维的 output 。这些 output 被拼接起来并再次投影，产生 final output ，如上图右侧所示。

   多头注意力multi-head attention 允许模型在每个position 联合地关注jointly attend 来自不同 representation 子空间的信息。如果只有单个注意力头single attention head，那么平均操作会抑制这一点。

   $$\begin{array}{c}\text{MultiHead}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{Concat}({\overrightarrow{\text{head}}}_1,{\overrightarrow{\text{head}}}_2,\cdots ,{\overrightarrow{\text{head}}}_h){\mathbf{W}}^O\\ {\overrightarrow{\text{head}}}_i=\text{Attention}(\mathbf{Q}{\mathbf{W}}_i^Q,\mathbf{K}{\mathbf{W}}_i^K,\mathbf{V}{\mathbf{W}}_i^V)\end{array}$$

   其中待学习的投影矩阵为：${\mathbf{W}}_i^Q\in {\mathbb{R}}^{d_{\text{model}}\times d_k}$$\mathbf W_i^Q\in \mathbb R^{d_\text{model}\times d_k}$、${\mathbf{W}}_i^K\in {\mathbb{R}}^{d_{\text{model}}\times d_k}$$\mathbf W_i^K\in \mathbb R^{d_\text{model}\times d_k}$、${\mathbf{W}}_i^V\in {\mathbb{R}}^{d_{\text{model}}\times d_v}$$\mathbf W_i^V\in \mathbb R^{d_\text{model}\times d_v}$、${\mathbf{W}}^O\in {\mathbb{R}}^{(h{d}_v)\times d_{\text{model}}}$$\mathbf W^O\in \mathbb R^{(hd_v)\times d_\text{model}}$。

   在这项工作中，我们使用 $h=8$$h=8$ 个注意力头 attention head 。对于其中每个注意力头，我们使用 $d_k=d_v=d_{\text{model}}/h=64$$d_k=d_v=d_\text{model}/h=64$ 。由于每个 head 的维度减小，因此总的计算成本与完整维度的单头注意力single-head attention 相近。

4. 注意力在 Transformer 中的应用：Transformer 以三种不同的方式使用多头注意力：

   • 在 encoder-decoder attention 层中，query 来自于前一个 decoder layer，key 和 value 来自于 encoder 的输出。这允许 decoder 中的每个位置关注 input 序列中的所有位置。这模仿了 sequence-to-sequence 模型中典型的 encoder-decoder attention 注意力机制。
   • encoder 包含自注意力层。在自注意力层中，所有的 query, key, value 都来自于同一个地方（在这个 case 中，就是 encoder 中前一层的输出）。encoder 中的每个位置都可以关注 encoder 上一层中的所有位置。
   • 类似地，decoder 中的自注意力层允许 decoder 中的每个位置关注 decoder 中截至到当前为止（包含当前位置）的所有位置。我们需要防止 decoder 中的信息向左流动，从而保持自回归特性。我们通过在 scaled dot-product attention 内部屏蔽掉 softmax input 的某些 value 来实现这一点（将这些 value 设置为 $-\mathrm{\infty }$$-\infty$ ），这些 value 对应于无效连接illegal connection 。

1.1.3 Position-wise Feed-Forward Networks

1. 除了注意力子层之外，我们的 encoder 和 decoder 中的每一层还包含一个全连接的前馈神经网络，该网络分别且相同地应用于每个位置。该网络包含两个线性变换，中间有一个 ReLU 激活函数：

   $$\text{FFN}(\overrightarrow{\mathbf{x}})=max(\overrightarrow{\mathbf{0}},\overrightarrow{\mathbf{x}}{\mathbf{W}}_1+{\overrightarrow{\mathbf{b}}}_1){\mathbf{W}}_2+{\overrightarrow{\mathbf{b}}}_2$$

   虽然线性变换在不同位置上是共享的（即，相同的参数），但是它们在层与层之间使用不同的参数。

   该层的另一种描述是： kernel size = 1 的两个卷积，其中 input 和 output 的维度为 $d_{\text{model}}=512$$d_\text{model} = 512$，而内层的维度为 $d_{\text{ff}}=2048$$d_\text{ff} = 2048$ 。

   ${\mathbf{W}}_1\in {\mathbb{R}}^{d_{\text{model}}\times d_{\text{ff}}}$$\mathbf W_1\in \mathbb R^{d_\text{model}\times d_\text{ff}}$ ，${\mathbf{W}}_2\in {\mathbb{R}}^{d_{\text{ff}}\times d_{\text{model}}}$$\mathbf W_2\in \mathbb R^{d_\text{ff}\times d_\text{model}}$ 。这里采用膨胀的方式，选择 $d_{\text{ff}}>d_{\text{model}}$$d_\text{ff} \gt d_\text{model}$ 从而使得 representation 维度先增大再减小。

1.1.4 Embeddings and Softmax

1. 与其它序列转导模型类似，我们使用学到的 embedding 将 input token 和 output token 转换为维度 $d_{\text{model}}$$d_\text{model}$ 的向量。我们还使用学到的线性变换和 softmax 函数将 decoder output 转换为 next-token 的预测概率。

   在我们的模型中，我们在两个 embedding layer （输入层）和 pre-softmax 线性变换（输出层）之间（共计三个权重矩阵）共享相同的权重矩阵，类似于 《Using the output embedding to improve language models》。在 embedding 层中，我们将这些权重乘以 $\sqrt{d_{\text{model}}}$$\sqrt{d_\text{model}}$ 。

   这里有两个输入层，分别来自于 encoder input 和 decoder input。而输出层来自于 decoder 。

   三个 embedding 矩阵共享的前提是：input symbol 空间和 output symbol 空间是相同的，例如，输入是中文的文本，输出是中文摘要，那么input symbol 和 output symbol 都是中文单词。否则，encoder 的 embedding 矩阵无法和 decoder 的 两个 embedding 矩阵共享。但是无论如何，decoder 的两个 embedding 矩阵之间可以共享。

   为什么要把 embedding 矩阵乘以 $\sqrt{d_{\text{model}}}$$\sqrt{d_\text{model}}$ ？论文并未说明原因。有一种解释说是放大 embedding 使得它的量级和 positional embedding 的量级相同。可以通过实验来验证。

1.1.5 position embedding

1. 由于我们的模型不包含递归和卷积，为了让模型利用序列的次序 order，我们必须注入一些关于序列中 token 的相对位置或绝对位置的信息。为此，我们在 encoder stack 和 decoder stack 底部的 input embedding 中添加了 positional encoding 。positional encoding 与 embedding 具有相同的维度 $d_{\text{model}}$$d_\text{model}$ ，因此可以将二者相加。

   positional encoding 有很多选择，可以选择固定的也可以选择可学习的。

   • 这里我们选择固定的方式，采用不同频率的正弦函数和余弦函数：

     $$\begin{array}{c}{\overrightarrow{\mathbf{p}}}_j=({\text{PE}}_{(j,1)},{\text{PE}}_{(j,2)},\cdots ,{\text{PE}}_{(j,d_{\text{model}})})\\ {\text{PE}}_{j,2i}=\sin \left(\frac{j}{{10000}^{2i/d_{\text{model}}}}\right),{\text{PE}}_{j,2i+1}=\cos \left(\frac{j}{{10000}^{2i/d_{\text{model}}}}\right)\end{array}$$

     其中：$j$$j$ 表示 position，$i$$i$ 表示维度。即，positional encoding 的每个维度对应于一个正弦曲线，正弦曲线的波长从 $2\pi$$2\pi$ （当维度 $i=0$$i=0$ 时）到 $10000\times 2\pi$$10000\times 2\pi$ （当维度 $2i=d_{\text{model}}$$2i=d_\text{model}$ 时）。

     我们选择这个函数是因为我们假设它可以让模型通过相对位置来轻松地学习关注 attend ，因为对于任意固定的偏移量 $k$$k$，${\overrightarrow{\mathbf{p}}}_{j+k}$$\mathbf{\vec p}_{j+k}$ 可以表示为 ${\overrightarrow{\mathbf{p}}}_j$$\mathbf{\vec p}_j$ 的线性函数。

   • 我们还尝试使用可学习的 positional embedding，发现这两个版本产生了几乎相同的结果。我们选择了正弦版本，因为它可以让模型推断出比训练期间遇到的序列长度更长的序列。

     正弦版本的 positional embedding 可以应用到训练期间 unseen 的位置，而可学习的 positional embedding 无法实现这一功能。

1.1.6 Why Self-Attention

1. 这里我们将自注意力层与循环层、卷积层进行各个方面的比较。这些层通常用于将一个可变长度的 symbol representation 序列 $({\overrightarrow{\mathbf{x}}}_1,\cdots ,{\overrightarrow{\mathbf{x}}}_n)$$(\mathbf{\vec x}_1,\cdots,\mathbf{\vec x}_n)$ 映射到另一个等长序列 $({\overrightarrow{\mathbf{z}}}_1,\cdots ,{\overrightarrow{\mathbf{z}}}_n)$$(\mathbf{\vec z}_1,\cdots,\mathbf{\vec z}_n)$，其中 ${\overrightarrow{\mathbf{x}}}_{,}{\overrightarrow{\mathbf{z}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec x}_,\mathbf{\vec z}_i\in \mathbb R^d$ 。 为了启发我们使用自注意力，我们考虑了三个方面：每层的总计算复杂度、可并行化的计算量（以所需的最少的序列操作数量来衡量）、网络中远程依赖long-range dependency的路径长度。

   学习远程依赖是许多序列转导任务中的关键挑战。影响学习这种依赖的能力的一个关键因素是：前向传播信号和反向传播信号必须在网络中传输的路径长度。input 序列和 output 序列中任意位置组合之间的路径越短，那么就越容易学习远程依赖。因此，我们还比较了由不同类型的层组成的网络中，任意input 位置和 output 位置之间的最大路径长度。

   如下表所示：

   • 自注意力层在所有位置都关联一个 $O(1)$$O(1)$ 数量的序列操作（即具有最大程度的并行化），而循环层需要 $O(n)$$O(n)$ 数量的序列操作（即几乎完全无法并行化）。

     并行化指的是：为了计算指定位置的输出，模型需要依赖已经产生的多少个输出？

   • 在计算复杂度方面，当序列长度 $n$$n$ 小于 representation 维度 $d$$d$ 时（机器翻译中 state-of-the-art 模型常见的 case ），self-attention 层比循环层更快。

     为了提高涉及非常长序列（即 $n$$n$ 非常大）的任务的计算性能，可以将自注意力限制为仅考虑输入序列中的局部区域，这个局部区域是以输出位置对应处为中心、大小为 $r$$r$ 的邻域。这会将最大路径长度增加到 $O(n/r)$$O(n/r)$ ，同时每层的计算复杂度降低到 $O(rnd)$$O(rnd)$。我们计划在未来的工作中进一步研究这种方法。

   • 具有 kernel width $k<n$$k \lt n$ 的单个卷积层无法连接 input position 和 output position 组成的所有的 pair 。如果希望连接所有的 input position 和 output position，则需要堆叠 $O(n/k)$$O(n/k)$ 个卷积层(连续核 contiguous kernel) 或 $O({\log }_k(n))$$O(\log_k(n) )$ 个卷积层（空洞卷积 dilated convolution ），并且增加了网络中任意两个位置之间最长路径的长度。

     卷积层通常比循环层更昂贵 expensive （贵 $k$$k$ 倍）。然而，可分离卷积将计算复杂度显著降低到 $O(k\times n\times d+n\times d^2)$$O(k\times n\times d + n\times d^2)$ 。当 $k=n$$k=n$ 时，可分离卷积的复杂度就等于一个自注意力层和一个point-wise feed-forward layer 的组合（这就是我们在 Transformer 模型中采用的方法）。

   

2. 作为附带的好处，自注意力可以产生更可解释的模型。我们从 Transformer 模型中检查注意力的分布，并在下图中展示和讨论了示例。不仅单个注意力头清晰地学习执行不同的任务，而且许多注意力头似乎还表现出与句子的句法结构syntactic structure和语义结构 semantic structure 有关的行为。

   • 如下图所示为 encoder 六层自注意力层的第五层中，making 这个单词的多头自注意力分布（不同的颜色代表不同的头，颜色的深浅代表注意力大小）。making 这个单词的自注意力分布似乎倾向于构成短语 making ... more difficult 。

     

   • 如下图所示为 encoder 六层自注意力层的第五层中的两个注意力头。上半部分为 head 5 的完全的注意力分布（每个单词），下半部分为单词 its 在 head 5和 head 6 中的注意力分布。

     

   • 如下图所示为 encoder 六层自注意力层的第五层中的两个注意力头。

     

1.1.7 训练

1. Training Data and Batching：

   • 我们在由大约 450 万个 sentence pair 组成的标准 WMT 2014 English-German 数据集上进行了训练。句子使用 byte-pair encoding: BPE （《Massive exploration of neural machine translation architectures》） 进行编码，该编码有一个共享的 source-target vocabulary，词典规模大约 37000 个 token 。

     BPE 算法：

     • 语料库中每个单词表示为字符的拼接，其中 </w> 表示词尾。
     • 将每个单词拆分为字符，并计算字符出现的次数。这些字符添加到词表 vocabulary 。
     • 寻找出现频次最高的 character pair，合并它们并添加到词表。这些合并的 character pair 称作 word-piece 。
     • 重复执行上一步（即，“寻找--合并”），直到词表达到指定的规模。

   • 对于 English-French，我们使用了更大的 WMT 2014 English-French 数据集，该数据集由 3600 万个 sentence pair 组成。这些句子被拆分为 token，并且使用大小为 32k 的 word-piece vocabulary 。

   sentence pair 按照近似的序列长度被 batch 在一起。每个训练 batch 包含一组 sentence pair，大约共计 25k 个 source token 和 25k 个 target token 。

2. 硬件和 schedule：我们在一台配备 8 个 NVIDIA P100 GPU 的机器上训练我们的模型。

   • 对于我们的base model（使用我们在整篇论文中描述的超参数），每个 training step 大约需要 0.4 秒。我们对 base model 进行了总共 100k 步（即 12 小时）。
   • 对于我们的 big model （如下表最后一行所示），每个 training step 大约需要 1.0 秒。我们对 base model 进行了总共 300k 步（即 3.5 天）。

   

3. 优化器：我们使用 Adam optimizer 优化器，其中 ${\beta }_1=0.9,{\beta }_2=0.98,ϵ={10}^{-9}$$\beta_1=0.9,\beta_2=0.98,\epsilon=10^{-9}$ 。我们根据以下公式来调整训练期间的学习率：

   $$\text{lr}=\frac{1}{\sqrt{d_{\text{model}}}}\times min(\frac{1}{\sqrt{\text{step-num}}},\frac{\text{step-num}}{{\text{warmup-steps}}^{1.5}})$$

   即：

   • 在开头的 warmup_steps 训练 step 中线性增加学习率。这里我们使用 warmup_steps = 4000 。
   • 然后根据 step number 的平方根倒数来按比例降低学习率。

   为什么除以 $\sqrt{d_{\text{model}}}$$\sqrt{d_\text{model}}$ ？论文并未给出原因。这样做的效果是：模型越大则学习率越小。

4. 正则化：在训练期间我们使用三种类型的正则化：

   • Residual Dropout：

     • 我们将 dropout 应用于每个子层的 output，然后将其和子层的 input 相加（即残差连接）最后进行 layer normalization 。即：

       $$\text{LayerNorm}(\overrightarrow{\mathbf{x}}+\text{Dropout}\left(\text{Sublayer}\left(\overrightarrow{\mathbf{x}}\right)\right))$$

     • 此外，我们将 dropout 同时应用于 encoder stack 和 decoder encoder 中的 sum embedding，这个 sum embedding 是 embedding 和 positional encoding 相加得到的。

     对于 base model，我们使用 dropout rate 为 $P_{\text{drop}}=0.1$$P_\text{drop} = 0.1$ 。

   • Label Smoothing：在训练期间，我们采用了 ${ϵ}_{\text{ls}}=0.1$$\epsilon_\text{ls} = 0.1$ 的 label smoothing 。这会损害 perplexity 指标，因为模型会变得更加不确定，但是会提高准确率指标和 BLEU 得分。

     语言模型困惑度perplexity 的定义为：

     $$\text{perplexity}(\mathcal{W})=\frac{1}{\sqrt[n]{P(w_1,w_2,\cdots ,w_n)}}$$

     其中 $\mathcal{W}$$\mathcal W$ 为一个序列，$P(\mathcal{W})=P(w_1,w_2,\cdots ,w_n)$$P(\mathcal W) = P(w_1,w_2,\cdots,w_n)$ 为这个序列的概率。

1.2 实验

1.2.1 机器翻译

1. 配置（所有超参数是在对验证集进行实验之后再选择的）：

   • base model 使用单个模型，该模型是通过平均最后 5 个 checkpoint 获得的，其中 checkpoint 是以 10 分钟的间隔写入的。 big model 也是会用单个模型，但是它平均了最后 20 个 checkpoint 。

     checkpoint 平均指的是参数值取平均（而不是输出结果取平均）。

   • 我们使用 beam size = 4 和 length penalty $\alpha =0.6$$\alpha = 0.6$ 的 beam search 。

     在解码器的每个位置始终生成 beam size 个候选，直到出现结束标记。$\alpha$$\alpha$ 用于惩罚较短的生成序列：

     $$\text{score}(w_1,\cdots ,w_n)=\frac{1}{n^{\alpha }}\times \text{perplexity}(\mathcal{W})$$

     其中 $n$$n$ 为序列 $\mathcal{W}=(w_1,\cdots ,w_n)$$\mathcal W=(w_1,\cdots,w_n)$ 的长度。$n$$n$ 越大则修正后的困惑度越小。

   • 我们将推断期间的最大输出长度设置为 input length + 50 ，但是在可能的情况下输出会提前结束。

2. 下表总结了我们的结果，并将我们的翻译质量和训练成本，与文献中的其它模型架构进行了比较。我们通过将训练时间、使用的 GPU 数量、以及每个 GPU 的单精度浮点运算能力的估计值相乘，从而估计用于训练模型的浮点运算的数量。对于 K80, K40, M40, P100，我们取它们的单精度浮点运算能力分别为 2.8, 3.7, 6.0, 9.5 TFLOPS 。

   • WMT 2014 English-to-German 翻译任务：big transformer model 比先前报告的最佳模型（包括 ensemble 模型）在 BLEU 指标上高出 2.0 以上，达到了一个新的 state-of-the-art 的 BLEU 得分 28.4 。big transformer model 在 8 个 P100 GPU 上训练耗时 3.5 天。

     甚至我们的 base model 也超越了所有先前发布的模型和 ensembles ，并且 base model 的训练成本仅仅是任何其它有竞争力的模型的一小部分。

     bilingual evaluation understudy: BLEU 评估机器翻译质量。其思想是：机器翻译结果越接近专业人工翻译的结果，则越好。

     $$\text{BLEU}=\text{BP}\times \exp (\sum _{n=1}^N{w}_n\times \log p_n)$$

     其中：

     • BP 为句子简短惩罚Brevity Penalty，迫使机器翻译的长度与参考翻译的长度接近。

       $$\begin{array}{c}\text{BP}=\{\begin{array}{ll}1& \text{if }c>r\\ \exp (1-r/c)& \text{else}\end{array}\end{array}$$

       其中 $c$$c$ 为机器翻译的长度，$r$$r$ 为参考翻译的长度。

     • $N$$N$ 代表机器翻译和参考翻译之间的 n-gram 匹配最大的 n 值。通常 1-gram 匹配结果代表有多少个单词被独立地翻译出来，而 2-gram 以上的匹配结果代表翻译的流畅度。通常 $N$$N$ 最大为 4 。

     • $w_n$$w_n$ 代表 n-gram 匹配结果的权重，通常选择 $w_n=\frac{1}{N}$$w_n = \frac {1}{N}$ 。

     • $p_n$$p_n$ 衡量机器翻译和参考翻译之间 n-gram 匹配结果，即 n-gram precision：

       $$p_n=\frac{\sum _{\mathcal{C}\in \text{Candidates}}\sum _{{\text{gram}}_n\in \mathcal{C}}\text{count-clip}({\text{gram}}_n)}{\sum _{{\mathcal{C}}^{\prime }\in \text{Candidates}}\sum _{{\text{gram}}_n^{\prime }\in {\mathcal{C}}^{\prime }}\text{count}({\text{gram}}_n^{\prime })}$$

       其中：

       • $\text{Candidates}$$\text{Candidates}$ 表示翻译的所有句子的集合，$\mathcal{C}$$\mathcal C$ 表示某个翻译的句子，${\text{gram}}_n$$\text{gram}_n$ 表示某个 n-gram 项。

       • $\text{count}(\cdot )$$\text{count}(\cdot)$ 表示某个 n-gram 项在所有翻译结果中出现的次数。

       • $\text{count-clip}(\cdot )$$\text{count-clip}(\cdot)$ 表示某个 n-gram 项在所有翻译结果中出现的截断次数：

         $$\text{count-clip}({\text{gram}}_n)=min(\text{count}({\text{gram}}_n),\text{ground-truth}({\text{gram}}_n))$$

         而 $\text{ground-truth}({\text{gram}}_n)$$\text{ground-truth}(\text{gram}_n)$ 为 n-gram 项在参考译文中出现的次数。因此这里的“截断”指的是被 ground-truth频次所截断。

   • WMT 2014 English-to-French 翻译任务：big transformer model 达到了 41.0 的 BLEU 得分，优于先前发布的所有单一模型，训练成本小于先前 state-of-the-art 模型的 1/4 。

     注意：为 English-to-French 而训练的Transformer big model 使用 dropout rate 为 $P_{\text{drop}}=0.1$$P_\text{drop} = 0.1$ ，而不是 0.3 。

     41.0 对不上？从下表结果来看应该是 41.8 。

   

1.2.2 模型变体

1. 为了评估 Transformer 不同组件的重要性，我们以不同的方式改变了我们的 base model，并衡量了验证集（newstest2013 ）上 English-to-German 翻译性能的变化。我们使用了上一节中描述的 beam search，但是没有使用 checkpoint 平均。实验结果如下表所示。

   • 在 (A) 行中，我们改变了注意力头的数量以及注意力 key, value 的维度，并保持计算量不变。可以看到，虽然单头注意力要比最佳配置差 0.9 BLEU，但是如果 head 数量过多效果也会下降。

   • 在 (B) 行中，我们观察到降低注意力 key 的维度 $d_k$$d_k$ 会损害模型质量。这表明确定 compatibility function 并不容易确定，采用比内积更复杂的 compatibility function 可能是有益的。

     compatibility function 就是计算未归一化注意力分的函数 $s_{i,j}={\overrightarrow{\mathbf{q}}}_i{\overrightarrow{\mathbf{k}}}_j^{\mathrm{\top }}$$s_{i,j} = \mathbf{\vec q}_i \mathbf{\vec k}_j^\top$。

     此外，降低 $d_k$$d_k$ 降低了模型容量（模型参数从 65M 降低到 60M 和 58M）。

   • 在 (C) 行中，我们观察到，正如预期的那样，更大的模型更好。

   • 在 (D) 行中，我们观察到，dropout 和 label smoothing 有助于缓解过拟合，但是需要选取合适的 dropout rate 和 label smoothing rate 。

   • 在 (E) 行中，我们用可学习的 positional embedding 代替固定的正弦 positional encoding ，并观察到与 base model 几乎相同的结果。

   

1.2.3 English Constituency Parsing

1. 为了评估 Transformer 是否可以泛化到其它任务，我们对英语成分分析 English constituency parsing 任务进行了实验。这项任务提出了特定的挑战：output 受到强烈的结构性约束，并且明显比 input 更长。此外，RNN sequence-to-sequence model 无法在小数据领域获得 state-of-the-art 结果。

2. 我们在Penn Treebank 的 Wall Street Journal: WSJ 部分（大约 40k 个训练句子）上训练了一个 $d_{\text{model}}=1024$$d_\text{model} = 1024$ 的 4 层 transformer 。对于该任务，我们使用 16k token 的词典 vocabulary。

   我们还在半监督环境中训练了相同配置的 transformer ，使用来自大约 1700 万个句子的更大的 high-confidence 和 BerkleyParser 的数据集。对于该任务，我们使用 32k token 的词典。

   我们仅在 Section 22 验证集上进行了少量实验来选择以下超参数：dropout （attention 和 residual 上的 dropout）、学习率、beam size 。所有其它超参数保持与 English-to-German base translation model 相同。在推断期间，我们将最大输出长度增加到 input length + 300 。对于 WSJ only 和半监督任务，我们都使用 beam size = 21 和 $\alpha =0.3$$\alpha = 0.3$ 。

   实验结果如下表所示，可以看到：

   • 尽管缺乏对特定任务的调优，但是我们的模型表现得非常好，比除了 Recurrent Neural Network Grammar 之外的所有先前报告的模型得到了更好的结果。
   • 与 RNN sequence-to-sequence model 相比，即使仅在具有 40k 个句子的 WSJ 训练集上进行训练，Transformer 的性能也超越了 Berkeley- Parser 。

   

二、Universal Transformer[2018]

1. 像 Transformer 这样的 parallel-in-time 架构解决了RNN 的一个重要缺陷：RNN 固有的序列计算sequential computation 阻止了输入序列中各元素的并行化。同时 Transformer 也解决了序列较长时梯度消失的问题。Transformer 模型完全依靠自注意力机制。这种机制不仅可以直接并行化，而且由于每个symbol 的 representation 也直接访问到所有其他symbol 的 representation ，这导致了整个序列中有效的全局感受野 global receptive field 。

   然而，值得注意的是，Transformer 具有固定数量的层，放弃了RNN 对学习迭代式转换 iterative transformation或递归式转换recursive transformation的归纳偏置 inductive bias。我们的实验表明：这种归纳偏置可能对一些算法和语言理解任务至关重要，Transformer 不能很好地泛化到训练期间没有遇到的输入长度。

   在论文 《Universal Transformer》 中，作者介绍了Universal Transformer: UT，这是一个parallel-in-time 的递归的自注意力序列模型，它可以作为Transformer 模型的泛化，在广泛的具有挑战性的sequence-to-sequence 任务上产生提升的理论能力和改进的结果。 Universal Transformer结合了像Transformer这样的前馈序列模型的并行能力 parallelizability 和全局感受野、以及RNN的循环归纳偏置，这似乎更适合一系列的算法和自然语言理解的sequence-to-sequence 问题。顾名思义，与标准的 Transformer 相比，在某些假设下，Universal Transformer 可以被证明是图灵完备的。

   在每个recurrent step中，Universal Transformer 使用自注意力机制并行地refine 序列中所有 symbol 的 representation ，然后跟着一个深度可分离卷积depth-wise separable convolution 或 position-wise fully-connected layer （在所有position 和time-step 中共享），如下图所示。作者还添加了一个动态的逐位置停机机制 per-position halting mechanism ，允许模型动态选择每个symbol 所需的refinement step 数量，并首次表明这样的条件计算机制conditional computation mechanism 事实上可以提高几个较小的结构化的算法和语言推理任务的准确性（尽管它在机器翻译任务上的结果略有下降）。

   论文强有力的实验结果表明：Universal Transformer 在广泛的任务中的表现优于 Transformer 和LSTM 。

   

2. 相关工作：

   • 当运行一个fixed 数量的 step 时，Universal Transformer 相当于一个跨所有层共享参数的 multi-layer Transformer 。这在一定程度上类似于Recursive Transformer ，它在不同的深度上共享了self-attention layer 的权重。

     另一种可能更 informative 的描述，Universal Transformer 的方式是：作为一个并行的 RNN block （每个symbol 一个RNN block ，共享参数）来同时演化每个symbol 的 hidden state （通过在每个 step 关注前一个 step 的hidden state 序列来产生）。这样，它与 Neural GPU 和 Neural Turing Machine 等架构有关。因此，Universal Transformer 保留了原始 feed-forward Transformer 模型有吸引力的计算效率，但增加了RNN的recurrent inductive bias。此外，利用动态停机机制，Universal Transformer 可以根据输入数据自动选择 processing step 的数量。

   • Universal Transformer 和其他序列模型之间的联系从架构上看是显而易见的： 如果我们将recurrent step 限制为一个，它将是一个Transformer。

     但是，考虑 Universal Transformer 和 RNN 以及其他网络之间的关系更为有趣，在这些网络中，递归发生在时间维度上。表面上看，这些模型似乎密切相关，因为它们也是递归的。但有一个关键的区别：

     • 像RNN这样的time-recurrent模型不能在递归步骤中访问所有的记忆 memory （只能访问最近的一个记忆）。这使得它们在计算上更类似于自动机automata，因为在递归部分唯一可用的记忆是一个固定尺寸的状态向量fixed-size state vector。
     • 另一方面，Universal Transformer 可以关注整个previous layer，允许它在recurrent step 中访问所有的记忆。

   • 给定足够的内存，Universal Transformer 在计算上是通用的，即它可以模拟任何图灵机Turing machine，从而解决了标准Transformer模型的一个缺陷。

     除了在理论上有吸引力外，我们的结果表明：这种增加的表达性也导致了在几个具有挑战性的序列建模任务上的准确性的提高。这缩小了在机器翻译等大规模任务上与Neural Turing Machine或Neural GPU等模型之间的差距。

     为了说明这一点，我们可以将 Universal Transformer 简化为一个 Neural GPU。忽略decoder 并将 self-attention 模块（即带有残差连接的self-attention）简化为恒等映射，并且假设转移函数是卷积。如果我们将循环step的总数 $T$$T$ 设定为输入长度，我们得到的正是一个Neural GPU。

     Universal Transformer 和 Neural Turing Machine 之间也存在类似的关系。Neural Turing Machine 每个 step 的single read/write 操作可以由 Universal Transformer 的全局的、并行的representation revision来表达。

   • 另一个相关的模型架构是端到端记忆网络Memory Network 。然而，与端到端记忆网络相比，Universal Transformer 使用的 memory 对应于与其输入或输出的individual position 对齐的状态。此外，Universal Transformer 遵循 encoder-decoder 的配置，在大规模 sequence-to-sequence 的任务中实现了有竞争力的性能。

3. Universal Transformer将以下关键属性结合到一个模型中：

   • Weight sharing：我们用一种简单的权重共享形式来扩展Transformer ，从而在inductive bias 和模型表达力之间取得了有效的平衡。

     由于权重共享，所以 Universal Transformer 的模型大小要远远小于标准的 Transformer 。

   • Conditional computation：我们为Universal Transformer 配备了动态停机能力。与固定深度的 Universal Transformer 相比，它显示了更强的结果。

2.1 模型

1. Universal Transformer 是基于常用的encoder-decoder 架构，它的encoder 和decoder都是通过将一个 RNN 分别应用于输入和输出序列的每个位置的 representation 来操作的，如下图所示。然而，与常规 RNN 不同，Universal Transformer 不是在序列中的 position 上递归（沿着宽度方向），而是在每个 position 的 depth 上递归（沿着高度方向）。

   在每个 recurrent time-step，每个位置的 representation 在两个 sub-step 中被并行地修改：

   • 首先，使用自注意力机制在序列中的所有位置上交换信息，从而为每个位置生成一个 vector representation ，该 representation 是由前一个time step的所有其他位置的representation 融合而来。
   • 然后，在每个位置独立地对自注意力机制的输出应用一个转移函数（跨position 和 time 共享）。

   由于递归可以应用任何次数，这意味着Universal Transformer 可以有可变的深度（per-symbol processing step 的数量）。相比之下，Transformer 和 stacked RNN 只有固定的深度。

   

   更完整的架构如下图所示：

   

2.1.1 Encoder

1. 给定一个长度为 $m$$m$ 的输入序列，我们定义 ${\mathbf{H}}^{(0)}\in {\mathbb{R}}^{m\times d}$$\mathbf H^{(0)} \in \mathbb R^{m\times d}$ 为 embedding 矩阵，它的第 $i$$i$ 行表示输入序列位置 $i$$i$ 的 symbol 的 $d$$d$ 维 embedding 向量 ${\overrightarrow{\mathbf{h}}}_i^{(0)}\in {\mathbb{R}}^d,0\le i<m$$\mathbf{\vec h}_i^{(0)}\in \mathbb R^d, 0\le i\lt m$ 。 然后 Universal Transformer 通过应用Transformer的多头内积自注意力机制 multi-headed dot-product self-attention mechanism ，在 step $t$$t$ 为所有 $m$$m$ 个位置并行地迭代计算 representation ${\mathbf{H}}^{(t)}$$\mathbf H^{(t)}$，然后是一个转移函数transition function 。我们还在这些功能块function block周围添加了残差连接，并应用了 dropout 和layer normalization 。

2. 更具体地说，我们使用缩放的内积注意力：

   $$\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{softmax}\left(\frac{\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}}{\sqrt{d}}\right)\mathbf{V}$$

   其中 $\mathbf{Q}\in {\mathbb{R}}^{m\times d},\mathbf{K}\in {\mathbb{R}}^{m\times d},\mathbf{V}\in {\mathbb{R}}^{m\times d},\mathbf{Q}{\mathbf{K}}^{\mathrm{\top }}\in {\mathbb{R}}^{m\times m},\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})\in {\mathbb{R}}^{m\times d}$$\mathbf Q\in \mathbb R^{m \times d}, \mathbf K\in \mathbb R^{m \times d}, \mathbf V\in \mathbb R^{m \times d}, \mathbf Q\mathbf K^\top\in \mathbb R^{m\times m}, \text{Attention}(\mathbf Q, \mathbf K, \mathbf V)\in \mathbb R^{m\times d}$ 。

   我们使用有 $k$$k$ 个头的多头自注意力版本：

   $$\begin{array}{c}\text{MultiHeadSelfAttn}({\mathbf{H}}^{(t)})=\text{Concat}({\overrightarrow{\text{head}}}_1,{\overrightarrow{\text{head}}}_2,\cdots ,{\overrightarrow{\text{head}}}_k){\mathbf{W}}^O\\ {\overrightarrow{\text{head}}}_i=\text{Attention}({\mathbf{H}}^{(t)}{\mathbf{W}}_i^Q,{\mathbf{H}}^{(t)}{\mathbf{W}}_i^K,{\mathbf{H}}^{(t)}{\mathbf{W}}_i^V)\end{array}$$

   其中：${\mathbf{W}}^Q\in {\mathbb{R}}^{d\times (d/k)},{\mathbf{W}}^K\in {\mathbb{R}}^{d\times (d/k)},{\mathbf{W}}^V\in {\mathbb{R}}^{d\times (d/k)},{\mathbf{W}}^O\in {\mathbb{R}}^{d\times d}$$\mathbf W^Q\in \mathbb R^{d \times (d/k)}, \mathbf W^{K}\in \mathbb R^{d \times (d/k)}, \mathbf W^V\in \mathbb R^{d\times (d/k)}, \mathbf W^O\in \mathbb R^{d\times d}$ 。

3. 在 step $t$$t$ ， Universal Transformer 然后计算所有 $m$$m$ 个输入位置的修正的 representation ${\mathbf{H}}^{(t)}\in {\mathbb{R}}^{m\times d}$$\mathbf H^{(t)}\in \mathbb R^{m\times d}$，即：

   $$\begin{array}{c}{\mathbf{H}}^{(t)}=\text{LayerNorm}({\mathbf{A}}^{(t)}+\text{Transition}\left({\mathbf{A}}^{(t)}\right))\\ {\mathbf{A}}^{(t)}=\text{LayerNorm}(({\mathbf{H}}^{(t-1)}+{\mathbf{P}}^{(t)})+\text{MultiHeadSelfAttn}({\mathbf{H}}^{(t-1)}+{\mathbf{P}}^{(t)}))\end{array}$$

   LayerNorm 作用在残差连接之后，而不是之前。

   其中：

   • Transition 为转移函数。根据任务，我们使用两种不同的转移函数之一：要么是可分离的卷积、要么是前馈神经网络（由两个线性投影以及中间的的单个 Relu 激活函数组成，逐位置应用）。

   • ${\mathbf{P}}^{(t)}\in {\mathbb{R}}^{m\times d}$$\mathbf P^{(t)}\in \mathbb R^{m\times d}$ 为固定的、常量的、二维的（位置维度、时间维度）的 coordinate embedding，通过计算正弦的 position embedding 向量获得：

     $$\begin{array}{c}{\mathbf{p}}_i^{(t)}=(p_{i,1}^{(t)},\cdots ,p_{i,d}^{(t)})\in {\mathbb{R}}^d\\ p_{i,2j}^{(t)}=\sin \left(\frac{i}{{10000}^{2j/d}}\right)+\sin \left(\frac{t}{{10000}^{2j/d}}\right)\\ p_{i,2j+1}^{(t)}=\cos \left(\frac{i}{{10000}^{2j/d}}\right)+\cos \left(\frac{t}{{10000}^{2j/d}}\right)\end{array}$$

     $i$$i$ 给出了位置维度的信息，$t$$t$ 给出了时间维度的信息。

   经过 $T$$T$ 个 step （每个 step 并行地更新输入序列的所有位置），Universal Transformer encoder 的 final output 是 ${\mathbf{H}}^{(T)}\in {\mathbb{R}}^{m\times d}$$\mathbf H^{(T)}\in \mathbb R^{m \times d}$ 。

2.1.2 Decoder

1. decoder 与 encoder 的基本递归结构相同。然而，在self-attention 函数之后，decoder 额外还使用多头内积注意力函数来关注 encoder 的 final representation ${\mathbf{H}}^{(T)}$$\mathbf H^{(T)}$，但query $\mathbf{Q}$$\mathbf Q$ 是从 decoder representation 投影得到，而 key $\mathbf{K}$$\mathbf K$ 和 value $\mathbf{V}$$\mathbf V$ 是从 encoder final representation 投影得到。

   是否可以对 decoder 和 encoder 应用不同的 $T$$T$ ？理论上并没有约束强制要求 decoder 和 encoder 迭代相同的次数。

2. 像 Transformer 模型一样，Universal Transformer 是自回归的。

   • 在生成阶段，Universal Transformer 一次产生一个 symbol 的输出，其中 decoder 仅仅依赖已经产生的输出位置。
   • 在训练阶段，decoder 的目标输出就是输入左移一个位置。

   最后，per-symbol target distribution 是通过应用线性变换 $\mathbf{O}\in {\mathbb{R}}^{d\times |\mathcal{V}|}$$\mathbf O \in \mathbb R^{d\times |\mathcal V|}$ 从 final decoder state 映射到 output vocabulary $\mathcal{V}$$\mathcal V$ ，然后通过 softmax 进行按行的归一化：

   $$p(y_{\text{pos}}\mid y_{[1:\text{pos}-1]},{\mathbf{H}}_{\text{encoder}}^{(T)})=\text{softmax}\left({\mathbf{H}}_{\text{decoder}}^{(T)}\mathbf{O}\right)\in {\mathbb{R}}^{n\times |\mathcal{V}|}$$

   其中：$n$$n$ 为输出序列的长度。

   这里我们用 ${\mathbf{H}}_{\text{encoder}},{\mathbf{H}}_{\text{decoder}}$$\mathbf H_\text{encoder}, \mathbf H_\text{decoder}$ 来区分 encoder 和 decoder 的最后一层的 representation 。$y_{[1:\text{pos}-1]},{\mathbf{H}}_{\text{encoder}}^{(T)}$$y_{[1:\text{pos}-1]},\mathbf H^{(T)}_\text{encoder}$ 都是 decoder 的输入。

3. 为了从模型中生成：

   • 首先， encoder 要对输入序列运行一次前向传播。
   • 然后重复运行decoder 从而消耗所有已经生成的symbol ，同时为下一个输出位置的symbol 生成一个额外的分布。然后，我们通常对最高概率的symbol 进行采样从而作为next symbol （用于decoder 的下一轮 RNN 迭代）。

   如果是训练期间，那么 decoder 每一轮迭代都使用 decoder 的目标输出右移一位作为 decoder input 。但是在推断期间，decoder 的目标输出不存在，因此需要用到 decoder 在每一轮的输出。

2.1.3 动态停机

1. 在序列处理系统中，某些 symbol 通常比其他 symbol 更 ambiguous 。因此，将更多的处理资源分配给这些更ambiguous 的 symbol 是合理的。Adaptive Computation Time: ACT 是一种机制，用于动态调节标准 RNN 中处理每个 input symbol 所需的计算步（称为 ponder time ），它基于模型在每个step 预测的标量停机概率 halting probability 。

   受此启发，Universal Transformer 为每个位置（即每个 per-symbol self-attentive RNN）添加了一个动态 ACT 停机机制。一旦某个 symbol 的 recurrent block 停机，它的状态就被简单地复制到下一步，直到所有的block 都停机，或者我们达到最大的 step 数量 $T$$T$ 。然后，encoder 的final output 是以这种方式产生的最后一层 representation 。

2.2 实验

2.2.1 BABI 问答

1. bAbi question answering 数据集：由 20 个不同的任务组成，其目标是在给定一些英文句子的前提下回答一个问题，这些给定的句子编码了潜在的 multiple supporting facts 。

   这么做的目的是：通过要求对每个故事中呈现的语言事实进行某种类型的推理，来衡量各种形式的语言理解 language understanding 。

2. 为了对输入进行编码，与《Tracking the world state with recurrent entity networks》类似：

   • 首先，我们通过应用一个学到的乘性的 positional mask 到每个单词的 embedding ，并 sum 聚合所有单词的 embedding ，从而编码故事中的每个 fact 。

     因为每个 fact 包含多个单词，所以需要对 word embedding 进行聚合从而得到 fact emebdding 。

   • 然后，我们以同样的方式嵌入问题，然后用这些 fact embedding 和 question embedding 馈入 Universal Transformer。

3. 模型可以在每个任务上单独训练（train single）或在所有任务上联合训练（train joint）。下表总结了我们的结果。我们用不同的初始化运行了 10次，并根据验证集上的表现挑选出最佳模型。

   可以看到：Universal Transformer和带有动态停机的Universal Transformer 在所有任务中的平均误差和失败任务数方面都取得了SOTA 的结果。

   括号中的指标代表失败任务数，如 (10/20) 表示在 20 个任务中失败了 10 个。任务失败指的是错误率大于 5% 。

   

4. 为了更好地理解模型的工作，我们分析了这项任务的注意力分布和平均ACT ponder time 。下图为注意力权重在不同 step 上的可视化，左侧不同的颜色条表示不同 head 的注意力权重（一共4个head），即，列代表 head 、行代表句子。

   • 一个 supportive fact 的问题：

     

   • 两个 supportive fact 的问题：

     

     

   • 三个 supportive fact 的问题：

     

     

     

     

     

   结论：

   • 首先，我们观察到注意力分布开始时非常均匀，但在后面的step 中，围绕着回答每个问题所需的正确的supporting fact，注意力分布逐渐变得尖锐，这确实非常类似于人类如何解决这个任务。

   • 其次，通过动态停机我们观察到：需要三个supporting fact 的任务的所有位置的平均 ponder time（即per-symbol recurrent processing chain 的深度（$3.8\pm 2.2$$3.8 \pm 2.2$）高于只需要两个supporting fact 的任务（$3.1\pm 1.1$$3.1 \pm 1.1$），而这又高于只需要一个supporting fact 的任务（$2.3\pm 0.8$$2.3 \pm 0.8$）。这表明，该模型根据回答问题所需的supporting fact 的数量来调整processing step的数量。

   • 最后，我们观察到：在只需要一个supporting fact 的任务中，不同位置的 ponder time 直方图与需要两个/三个supporting fact 的任务相比更加均匀。

     同样，在需要两个supporting fact 的任务与需要三个supporting fact 的任务也是如此。特别是对于需要三个 supporting fact 的任务，许多位置已经在第1步或第 2 步停机了，只有少数位置需要更多的step （如下图所示）。这一点特别有意思，因为在这种情况下，故事的长度确实要高得多，有更多不相关的fact ，而模型似乎成功地学会了以这种方式忽略这些fact 。

   

2.2.2 主谓一致

1. 主谓一致Subject-Verb Aggrement任务：使用语言建模的 training setup 来解决这个任务，即next word prediction 的目标，然后在测试时计算目标动词的 ranking accuracy 。该任务是衡量模型在自然语言句子中捕捉层级结构hierarchical structure的能力的一个代理。

   attractors 用于增加难度，它表示与主语相反数量opposite number 的中间名词intervening noun 的个数（旨在混淆模型）。如：给定句子 The keys __ to the cabinet ，训练期间的目标动词是 are，但是测试期间我们要求 are 的排名比 is 更高。

   

2.2.3 LAMBADA 语言建模

1. LAMBADA 任务：是一项语言建模任务，在给定前面 4 到 5 个句子的条件下预测一个缺失的目标词。

   该数据集是专门设计的，当显示完整的上下文时，人类能够准确地预测目标词，但当只显示出现该词的目标句时，则人类无法预测目标词。因此，它超越了语言建模，并测试了模型在预测目标词时纳入更长上下文的能力。

   该任务在两种情况下被评估：

   • 语言建模（标准设置，更具挑战性）：模型只是在训练数据上进行next-word prediction 的训练，并在测试时对目标词进行评估。

   • 和阅读理解：目标句子（减去最后一个词）被用作 query ，用于从上下文句子中选择目标词（即，检索式的方法）。

     请注意，目标词在81% 的时间里出现在上下文中，这使得这种设置更加简单。然而，在其余19% 的情况下，这个任务是不可能完成的（因为目标词不存在上下文中）。

2. 实验结果：Universal Transformer 在语言建模和阅读理解设置中都取得了SOTA 结果。

   我们 fixed Universal Transformer 结果使用了6个step （即，$T=6$$T=6$ ）。然而，带有动态停机的最佳 Universal Transformer 的平均step 数为 $8.2\pm 2.1$$8.2 \pm 2.1$ 。

   为了看看动态停机是否仅仅因为采取了更多的step 而做得更好，我们训练了两个 fixed Universal Transformer ，分别用 $T=8$$T=8$ 和 $T=9$$T=9$（见最后两行）。有趣的是，与 $T=6$$T=6$ 的模型相比，这两个模型取得了更好的结果，但并没有超过动态停机的 Universal Transformer 的表现。

   这使我们相信：动态停机可以作为模型的一个有用的正则器，通过激励一些input symbol 以较小的 step 数量，同时允许其他input symbol 以更多的计算。

   

2.2.4 算术任务

1. 我们在三个算术任务上训练 Universal Transformer ，即 Copy 、Reverse 和（整数）加法，都是在由十进制符号（0 ~ 9）组成的字符串上。在所有的实验中，我们在长度为40 的序列上训练模型，在长度为400的序列上进行评估。 我们使用从randomized offset 开始的位置来训练 Universal Transformer （训练样本需要选择从哪里开始切分，因为输入语料库可以视为一个超长的文本），以进一步鼓励模型学习position-relative 的转换。

   结果如下表所示， Universal Transformer 在所有三个任务上的表现都远远超过了 LSTM 和常规的 Transformer。

   

2.2.5 Learnung To Execute: LTE

1. 作为另一种 sequence-to-sequence learning 问题，我们评估表明模型学习执行计算机程序的能力的任务。这些任务包括程序评估program evaluation 任务（编程、控制和加法），以及记忆memorization 任务（copy、double 和reverse）。

   结果如下表所示， Universal Transformer 在所有任务上的表现都远远超过了 LSTM 和常规的 Transformer。

   

2.2.6 机器翻译

1. 我们使用与 Transformer报告中相同的设置在 WMT2014 英德翻译任务上训练 Universal Transformer ，以评估其在大规模 sequence-to-sequence 任务上的性能。结果总结如下。采用前馈神经网络（而不是可分离卷积）作为转移函数且没有动态停机的 Universal Transformer 比 Transformer 提高了 0.9 BLEU 。

   根据作者在引言部分的介绍，如果采用动态停机，则会导致 Universal Transformer 的效果更差。

   

三、Transformer-XL[2019]

1. 尽管 RNN 适应性很广，但是，由于梯度消失和爆炸导致 RNN 很难优化。在LSTM 中引入门控和梯度裁剪技术可能不足以完全解决这一问题。从经验上看，以前的工作发现：LSTM语言模型平均使用200个context words，表明有进一步改进的空间。

   另一方面，注意力机制中的长距离 word pairs 之间的直接联系可能会有助于优化，并学习长期依赖性。最近 《Character-level language modeling with deeper self-attention》 设计了一套辅助损失来训练深度 Transformer 网络从而用于 character-level 语言建模。该方法存在两个问题：

   • 尽管取得了成功，但该模型的训练是在几百个字符的分离的固定长度的 segment 上进行的，没有跨segment 的信息流。 由于固定的上下文长度，该模型无法捕捉到超出预定义上下文长度的任何长期依赖关系。
   • 此外，固定长度的 segment 是通过选择连续的符号块 symbol chunk来创建的，没有考虑句子或任何其他语义边界。因此，该模型缺乏必要的上下文信息从而无法很好地预测前几个symbol ，导致低效的优化和较差的性能。我们把这个问题称为上下文碎片化 context fragmentation 。

   为了解决上述固定长度上下文的局限性，论文 《Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context》提出了一个新的架构，叫做 Transformer-XL（意为 extra long）。论文将递归的概念引入 deep self-attention network。具体而言，论文不是为每个新的segment 从头开始计算 hidden state，而是复用在previous segments 中获得的 hidden state。复用的 hidden state 用于 current segment 的 memory ，在前后 segment 之间建立了一个递归连接 recurrent connection 。因此，建立非常长期的依赖关系的模型成为可能，因为信息可以通过递归连接 recurrent connection 来传播。同时，从前一个segment 传递信息也可以解决上下文碎片化的问题。

   RNN 是在 position 之间构建递归，Universal Transformer 是在 depth 之间构建递归，Transformer-XL 是在 segment 之间构建递归。

   通常一个 segment 代表一个样本，因此这也是样本之间构建递归。

   更重要的是，论文展示了使用相对位置编码 relative positional encoding 而不是绝对位置编码 absolute positional encoding 的必要性，以便在不引起时间混乱的情况下实现状态重用 state reuse。因此，作为一个额外的技术贡献，论文引入了一个简单但更有效的相对位置编码公式，该公式可以泛化到比训练期间看到的长度更长的序列。

   Transformer-XL 在五个数据集上获得了强有力的结果，这些数据集从word-level 语言建模到 character-level 语言建模。Transformer-XL 还能够生成相对连贯的、数千个 token 的长篇文章。

   坤文的主要技术贡献包括：

   • 在纯粹的自注意力模型 self-attention model 中引入递归的概念。
   • 推导出一个新颖的位置编码方案。

   这两种技术构成了一套完整的解决方案，因为其中任何一个单独的技术都不能解决固定长度上下文的问题。Transformer-XL 是第一个在word-level 语言建模到 character-level 语言建模上取得比 RNN 更好结果的自注意力模型。

2. 相关工作：为了捕获语言建模中的长距离上下文，一系列工作直接将更宽上下文的 representation 作为 additional input 输入到网络中。现有的工作有人工定义 context representation 的，也有依靠从数据中学到的document-level topic 。

   例如，可以把非常长上下文的 sum word embedding 作为额外的输入。

   更广泛地说，在通用序列建模中，如何捕获长期依赖性一直是一个长期研究问题。从这个角度来看，由于 LSTM 的普适性，人们在缓解梯度消失问题上做了很多努力来有助于优化，包括更好的初始化、辅助损失、增强的记忆结构memory structure、以及其他的修改RNN内部结构的方法。与他们不同的是，我们的工作是基于 Transformer 架构的，并表明语言建模作为一个现实世界的任务，受益于学习长期依赖性的能力。

3.1 模型

1. 给定一个 token 序列 $\mathbf{x}=(x_1,\cdots ,x_T)$$\mathbf x = (x_1,\cdots,x_T)$，语言建模 language modeling 的任务是估计联合概率 $P(\mathbf{x})$$P(\mathbf x)$ 。这个联合概率通常被自回归地分解为：

   $$P(\mathbf{x})=\prod _{t}P(x_t\mid {\mathbf{x}}_{<t})$$

   其中 ${\mathbf{x}}_{<t}$$\mathbf x_{\lt t}$ 为序列截止到时刻 $t$$t$ （不包含）的上下文 ${\mathbf{x}}_{<t}=(x_1,\cdots ,x_{t-1})$$\mathbf x_{\lt t} = (x_1,\cdots,x_{t-1})$ 。

   在这项工作中，我们坚持采用标准的神经网络方法来建模条件概率。具体而言：

   • 一个神经网络将上下文 ${\mathbf{x}}_{<t}$$\mathbf x_{\lt t}$ 编码到一个固定维度的隐状态 hidden state 中。
   • 然后将隐状态（一个向量）与每个单词的 word embedding相乘，从而得到一组logit 。
   • 将这组 logit 馈入 softmax 函数，从而得到关于 next token 的离散概率分布。

3.1.1 普通的 Transformer

1. 为了将 Transformer 或 self-attention 应用于语言建模，核心问题是如何训练Transformer 从而将一个任意长的上下文有效地编码为固定尺寸的representation 。

   理想的方法是用一个无条件的 Transformer 来处理整个上下文序列，但是由于资源有限，这通常是不可行的。

   一个可行但粗糙的近似方法是：将整个语料库分割成规模可控的较短的 segment，只在每个 segment内训练模型，忽略之前 segment的所有上下文信息。我们称之为普通的 Transformer 模型，并在下图 (a) 中可视化。在这种训练范式下，信息在前向传播和反向传播过程中都不会跨 segment 流动。

   使用固定长度的上下文有两个关键限制：

   • 首先，最大依赖长度被segment 长度所限。在 character-level 语言建模中，segment 长度为几百。
   • 其次，简单地将一个序列分割成固定长度的segment 将导致上下文碎片化问题。

   在评估过程的每一步，普通的 Transformer 模型也会消耗相同长度的segment （与训练 segment 长度相同），但仅在 segment 的最后一个位置做一个预测。然后在下一步，该segment 只向右移动了一个位置，而新的 segment 必须从头开始计算，如图 (b) 所示。这个过程确保了每个预测都利用了最长的上下文，同时也缓解了训练中遇到的上下文碎片化问题。然而，这种评估过程是非常昂贵的。我们将表明：我们提出的架构能够大幅提高评估速度。

   注意：训练阶段和评估阶段有两个地方不一致：

   • segment 移动的步长不一致：训练期间右移 $L$$L$ 个位置（ $L$$L$ 等于 segment 长度），验证期间右移一个位置。
   • 预测位置不一致：训练期间对 segment 的每个位置进行预测，而验证期间仅对 segment 的最后一个位置进行预测。这是为了和 segment 移动步长相匹配，使得每个位置仅进行一次预测。

   之所以训练期间 segment 移动步长更大，个人猜测是为了降低训练样本量。假设 segment 长度固定为 $L$$L$ ，如果移动步长为 $L$$L$ ，则每个训练 epoch 中每个 token 会出现一次；如果移动步长为 1，则每个训练 epoch 中每个 token 会出现 $L$$L$ 次。

   

3.1.2 Segment-Level Recurrence

1. 为了解决使用固定长度上下文的局限性，我们建议在 Transformer 架构中引入一个递归机制。在训练过程中，固定前一个segment 计算好的hidden state 序列，并在处理 next segment 时作为扩展上下文extended context 来重用，如下图 (a) 所示（图中的绿色路径表示扩展上下文）。

   尽管反向传播仍然保持在一个 segment 内，但这个额外的输入（即，前一个 segment 的hidden state 序列 ）允许网络利用历史信息，导致了对长期依赖性的建模能力，并避免了上下文碎片化。

   注意：

   • 在训练过程中，前一个 segment 的 hidden state 序列被冻住，不再更新它们的状态（前向传播）以及梯度（反向传播）。
   • 对于前一个 segment ，需要考虑每一层的 hidden state 序列（而不仅仅是最后一层）。

   

2. 具体而言，假设长度为 $L$$L$ 的连续的两个 segment 为：

   $${\mathbf{x}}_{\tau }=(x_{\tau ,1},\cdots ,x_{\tau ,L}),{\mathbf{x}}_{\tau +1}=(x_{\tau +1,1},\cdots ,x_{\tau +1,L})$$

   记 ${\mathbf{x}}_{\tau }$$\mathbf x_\tau$ 的第 $n$$n$ 层 hidden state 序列为： ${\mathbf{H}}_{\tau }^{(n)}={({\overrightarrow{\mathbf{h}}}_{\tau ,1}^{(n)},\cdots ,{\overrightarrow{\mathbf{h}}}_{\tau ,L}^{(n)})}^{\mathrm{\top }}\in {\mathbb{R}}^{L\times d}$$\mathbf H_\tau^{(n)} = \left(\mathbf{\vec h}_{\tau,1}^{(n)},\cdots,\mathbf{\vec h}_{\tau,L}^{(n)}\right)^\top\in \mathbb R^{L\times d}$，其中第 $i$$i$ 行表示位置 $i$$i$ 的 hidden state ${\overrightarrow{\mathbf{h}}}_{\tau ,i}^{(n)}\in {\mathbb{R}}^d$$\mathbf{\vec h}_{\tau,i}^{(n)}\in \mathbb R^d$ ，$d$$d$ 为 hidden state 维度。那么 ${\mathbf{x}}_{\tau +1}$$\mathbf x_{\tau+1}$ 第 $n$$n$ 层 hidden state 序列的计算过程为：

   • 拼接第 $n-1$$n-1$ 层的上下文：${\tilde{\mathbf{H}}}_{\tau +1}^{(n-1)}=\text{SG}\left({\mathbf{H}}_{\tau }^{(n-1)}\right)\circ {\mathbf{H}}_{\tau +1}^{(n-1)}$$\tilde{\mathbf H}^{(n-1)}_{\tau+1} = \text{SG}\left(\mathbf H_\tau^{(n-1)}\right)\circ \mathbf H_{\tau+1}^{(n-1)}$ ，其中： $\text{SG}(\cdot )$$\text{SG}(\cdot)$ 表示 stop-gradient，$\circ$$\circ$ 表示沿着序列长度的维度拼接两个 hidden state 序列。

   • 生成 query, key, value ：

     $$\begin{array}{c}{\mathbf{Q}}_{\tau +1}^{(n)}={\mathbf{H}}_{\tau +1}^{(n-1)}{\mathbf{W}}_q^{\mathrm{\top }}\\ {\mathbf{K}}_{\tau +1}^{(n)}={\tilde{\mathbf{H}}}_{\tau +1}^{(n-1)}{\mathbf{W}}_k^{\mathrm{\top }}\\ {\mathbf{V}}_{\tau +1}^{(n)}={\tilde{\mathbf{H}}}_{\tau +1}^{(n-1)}{\mathbf{W}}_v^{\mathrm{\top }}\end{array}$$

     注意：query 用当前 segment 的上下文，而key/value 用扩展的上下文。这是因为我们只需要计算当前 segment 的 representation，这对应于 query 的形状。

   • 计算第 $n$$n$ 层的 hidden state 序列：${\mathbf{H}}_{\tau +1}^{(n)}=\text{Transformer-Layer}({\mathbf{Q}}_{\tau +1}^{(n)},{\mathbf{K}}_{\tau +1}^{(n)},{\mathbf{V}}_{\tau +1}^{(n)})$$\mathbf H^{(n)}_{\tau+1} = \text{Transformer-Layer}\left(\mathbf Q^{(n)}_{\tau+1},\mathbf K^{(n)}_{\tau+1},\mathbf V^{(n)}_{\tau+1}\right)$。

   与标准的 Transformer 相比，关键的区别在于：key ${\mathbf{K}}_{\tau +1}^{(n)}$$\mathbf K^{(n)}_{\tau+1}$ 和 value ${\mathbf{V}}_{\tau +1}^{(n)}$$\mathbf V^{(n)}_{\tau+1}$ 是根据扩展上下文 ${\tilde{\mathbf{H}}}_{\tau +1}^{(n-1)}$$\tilde{\mathbf H}^{(n-1)}_{\tau+1}$ 来计算的，而 ${\mathbf{H}}_{\tau }^{(n-1)}$$\mathbf H_\tau^{(n-1)}$ 是从前一个 segment 缓存的。我们通过上图 (a) 中的绿色路径来强调这一特殊设计。由于这种递归机制应用于语料库的每两个连续的 segment ，因此它在hidden state中创造了一个segment-level 的递归。因此，有效利用的上下文可以远远超过两个segment 。

   这对于 batch 的组织是一个挑战，要求前后两个样本之间是连续的，并且不能随机选择样本。

3. 请注意，连续两个 segment 之间，${\mathbf{H}}_{\tau +1}^{(n)}$$\mathbf H_{\tau+1}^{(n)}$ 和 ${\mathbf{H}}_{\tau }^{(n-1)}$$\mathbf H_\tau^{(n-1)}$之间的递归依赖关系对每一层都右移了一位（整体右移一位），这与传统的RNN 语言模型中的同层递归不同。因此，最大可能的依赖长度与网络层数、segment 长度呈线性增长，即 $O(N\times L)$$O(N\times L)$，如上图 (b) 中的阴影区域所示，这里 $N$$N$ 为网络层数、$L$$L$ 为 segment 长度。

   ${\overrightarrow{\mathbf{h}}}_{\tau +1,i}^{(n)}$$\mathbf{\vec h}_{\tau+1,i}^{(n)}$ 依赖于 $\{{\overrightarrow{\mathbf{h}}}_{\tau ,i+1}^{(n-1)},\cdots ,{\overrightarrow{\mathbf{h}}}_{\tau ,L}^{(n-1)},{\overrightarrow{\mathbf{h}}}_{\tau +1,1}^{(n-1)},\cdots {\overrightarrow{\mathbf{h}}}_{\tau +1,i}^{(n-1)}\}$$\left\{\mathbf{\vec h}_{\tau,i+1}^{(n-1)},\cdots,\mathbf{\vec h}_{\tau,L}^{(n-1)},\mathbf{\vec h}_{\tau+1,1}^{(n-1)},\cdots\mathbf{\vec h}_{\tau+1,i}^{(n-1)}\right\}$ ，即第 $n-1$$n-1$ 层中：序列 ${\mathbf{x}}_{\tau }$$\mathbf x_{\tau}$ 的位置 $i+1$$i+1$ 到位置 $L$$L$ 、以及序列 ${\mathbf{x}}_{\tau +1}$$\mathbf x_{\tau+1}$ 中的位置 $1$$1$ 到位置 $i$$i$ ，一共 $L$$L$ 个位置。

   对于同层递归，则 ${\overrightarrow{\mathbf{h}}}_{\tau +1,i}^{(n)}$$\mathbf{\vec h}_{\tau+1,i}^{(n)}$ 依赖于 $\{{\overrightarrow{\mathbf{h}}}_{\tau ,1}^{(n-1)},\cdots ,{\overrightarrow{\mathbf{h}}}_{\tau ,i}^{(n-1)},{\overrightarrow{\mathbf{h}}}_{\tau +1,1}^{(n-1)},\cdots {\overrightarrow{\mathbf{h}}}_{\tau +1,i}^{(n-1)}\}$$\left\{\mathbf{\vec h}_{\tau,1}^{(n-1)},\cdots,\mathbf{\vec h}_{\tau,i}^{(n-1)},\mathbf{\vec h}_{\tau+1,1}^{(n-1)},\cdots\mathbf{\vec h}_{\tau+1,i}^{(n-1)}\right\}$ 。

4. segment-Level 递归类似于截断的 BPTT （用于训练 RNN 语言模型）。然而，与截断的BPTT不同的是：我们的方法缓存了hidden state 的一个序列，而不仅仅是最后一个 hidden state ，并且应该与相对位置编码技术一起应用。

   注意，segment-Level 递归对于每一层，都需要缓存 hidden state 的一个序列。

5. 除了实现超长上下文和解决上下文碎片化问题，递归方案带来的另一个好处是评估速度明显加快。具体而言，在评估过程中，先前的segment 的 representation 可以被重用，而不是像普通 Transformer 那样从头开始计算。在我们对enwiki8的实验中，Transformer-XL在评估过程中比普通 Transformer 模型快 1800 多倍。

6. 最后，请注意，递归方案不仅限于前面一个segment。理论上，我们可以在GPU内存允许的范围内缓存尽可能多的 previous segments，并在处理当前 segment 时复用所有这些 segment 作为额外的上下文。因此，我们可以缓存一个长度为 $M$$M$ 的 old hidden state 序列，跨越（可能）多个 segment ，并将它们称为 memory ${\mathbf{M}}_{\tau }^{(n)}\in {\mathbb{R}}^{M\times d}$$\mathbf M_\tau^{(n)}\in \mathbb R^{M\times d}$ 。

   总的上下文长度为 $L+M$$L+M$ 。

   在我们的实验中，我们在训练时将 $M$$M$ 设置为等于segment 长度 $L$$L$ ，在评估时将 $M$$M$ 设为 $L$$L$ 的若干倍。

   segment 长度 $L$$L$ 用于划分 segment，上下文长度 $M$$M$ 用于建模上下文，二者的作用不同。

   这里在训练期间和评估期间采用不同的上下文长度，会不会影响评估效果？毕竟训练数据分布和测试数据分布人为地导致了不一致（总的上下文长度不一致）。

3.1.3 Relative Positional Encoding

1. 为了重用前面 segment 的 hidden state ，有一个关键的技术挑战我们还没有解决：如何保持位置信息的一致性？

   在标准的 Transformer 中，序列顺序的信息是由一组位置编码positional encoding 来提供的，表示为 $\mathbf{U}\in {\mathbb{R}}^{L_{max}\times d}$$\mathbf U\in \mathbb R^{L_\max\times d}$，其中第 $i$$i$ 行 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 对应于segment 内第 $i$$i$ 个绝对位置，$L_{max}$$L_\max$ 定义了最大可能的建模长度。如果我们简单地将这种位置编码应用于我们的递归机制，那么 hidden state 序列的计算方式为：

   $$\begin{array}{c}{\mathbf{H}}_{\tau +1}=f({\mathbf{H}}_{\tau },{\mathbf{E}}_{{\mathbf{x}}_{\tau +1}}+{\mathbf{U}}_{1:L})\\ {\mathbf{H}}_{\tau }=f({\mathbf{H}}_{\tau -1},{\mathbf{E}}_{{\mathbf{x}}_{\tau }}+{\mathbf{U}}_{1:L})\end{array}$$

   其中：

   • ${\mathbf{E}}_{{\mathbf{x}}_{\tau }}\in {\mathbb{R}}^{L\times d}$$\mathbf E_{\mathbf x_\tau}\in \mathbb R^{L\times d}$ 为 segment ${\mathbf{x}}_{\tau }$$\mathbf x_\tau$ 的 word embedding，$f(\cdot )$$f(\cdot)$ 为一个变换函数，${\mathbf{U}}_{1:L}$$\mathbf U_{1:L}$ 为 $\mathbf{U}$$\mathbf U$ 的前 $L$$L$ 行组成的矩阵。
   • ${\mathbf{H}}_{\tau }$$\mathbf H_\tau$ 作为计算 ${\mathbf{H}}_{\tau +1}$$\mathbf H_{\tau+1}$ 的扩展上下文，${\mathbf{E}}_{{\mathbf{x}}_{\tau +1}}+{\mathbf{U}}_{1:L}$$\mathbf E_{\mathbf x_{\tau+1}} + \mathbf U_{1:L}$ 作为计算 ${\mathbf{H}}_{\tau +1}$$\mathbf H_{\tau+1}$ 的 input 。

   $L_{max}\ge L$$L_\max \ge L$ ，这是因为可能需要在测试期间泛化到 unseen 的序列长度。

   注意，${\mathbf{E}}_{{\mathbf{x}}_{\tau }}$$\mathbf E_{\mathbf x_\tau}$ 和 ${\mathbf{E}}_{{\mathbf{x}}_{\tau +1}}$$\mathbf E_{\mathbf x_{\tau+1}}$都与相同的位置编码 ${\mathbf{U}}_{1:L}$$\mathbf U_{1:L}$ 相关。因此，该模型没有信息来区分任何 $x_{\tau ,j}$$x_{\tau,j}$ 和 $x_{\tau +1,j}$$x_{\tau+1,j}$之间的位置差异，$1\le j\le L$$1\le j\le L$，从而导致了纯粹的性能损失。

   为解决这个问题，基本的想法是相对位置编码。从概念上讲，位置编码给了模型一个关于如何收集信息的时间线索或 "bias"，也就是说，关注attend 哪个地方。以相对的方式来定义时间bias 是更直观和更可泛化的。例如，当一个query 向量 ${\overrightarrow{\mathbf{q}}}_{\tau ,i}$$\mathbf{\vec q} _{\tau,i}$关注 key 向量 ${\left\{{\overrightarrow{\mathbf{k}}}_{\tau ,j}\right\}}_{j\le i}$$\left\{\mathbf{\vec k}_{\tau,j}\right\}_{j\le i}$时，它不需要知道每个key 向量的绝对位置来识别segment 的时间顺序，只要知道每个key 向量 ${\overrightarrow{\mathbf{k}}}_{\tau ,j}$$\mathbf{\vec k}_{\tau,j}$ 与 ${\overrightarrow{\mathbf{q}}}_{\tau ,i}$$\mathbf{\vec q}_{\tau,i}$ 之间的相对距离（即 $i-j$$i-j$ ）就足够了。

   实际上，人们可以创建一组相对位置编码 $\mathbf{R}\in {\mathbb{R}}^{L_{max}\times d}$$\mathbf R\in \mathbb R^{L_\max\times d}$ ，其中第 $i$$i$ 行 ${\overrightarrow{\mathbf{r}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec r}_i\in \mathbb R^d$ 表示两个位置之间的相对距离为 $i$$i$ 。通过将相对距离动态地注入到 attention score，query 向量可以很容易地根据不同距离区分出 $x_{\tau ,j}$$x_{\tau,j}$ 和 $x_{\tau +1,j}$$x_{\tau+1,j}$ 的 representation，使状态重用机制变得可行。同时，我们不会丢失任何时间信息，因为绝对位置可以从相对距离中递归恢复。

2. 此前，相对位置编码的想法已经在机器翻译和音乐生成任务中得到了探索。在这里，我们提供了一种不同的编码形式，它不仅与绝对位置编码有一一对应关系，而且在经验上也具有更好的泛化性。

   • 首先，在标准的 Transformer中，同一个 segment 中的注意力得分可以分解为：

     $$\begin{array}{c}{a}_{i,j}^{\text{abs}}={\left({\mathbf{W}}_q({\overrightarrow{\mathbf{e}}}_{x_i}+{\overrightarrow{\mathbf{u}}}_i)\right)}^{\mathrm{\top }}\left({\mathbf{W}}_k({\overrightarrow{\mathbf{e}}}_{x_j}+{\overrightarrow{\mathbf{u}}}_j)\right)=\\ \underset{(a)}{\underbrace{{\overrightarrow{\mathbf{e}}}_{x_i}^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_k{\overrightarrow{\mathbf{e}}}_{x_j}}}+\underset{(b)}{\underbrace{{\overrightarrow{\mathbf{e}}}_{x_i}^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_k{\overrightarrow{\mathbf{u}}}_j}}+\underset{(c)}{\underbrace{{\overrightarrow{\mathbf{u}}}_i^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_k{\overrightarrow{\mathbf{e}}}_{x_j}}}+\underset{(d)}{\underbrace{{\overrightarrow{\mathbf{u}}}_i^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_k{\overrightarrow{\mathbf{u}}}_j}}\end{array}$$

     其中：${\overrightarrow{\mathbf{e}}}_{x_i}$$\mathbf{\vec e}_{x_i}$ 为 $x_i$$x_i$ 的 embedding 向量，${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 为位置 $i$$i$ 的 positional embedding ，${\mathbf{W}}_q$$\mathbf W_q$ 为 query 的投影矩阵，${\mathbf{W}}_k$$\mathbf W_k$ 为 key 的投影矩阵。

   • 然后，按照仅依赖于相对位置信息的思路，我们建议重写上述四项为：

     $$a_{i,j}^{\text{rel}}=\underset{(a)}{\underbrace{{\overrightarrow{\mathbf{e}}}_{x_i}^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_{k,E}{\overrightarrow{\mathbf{e}}}_{x_j}}}+\underset{(b)}{\underbrace{{\overrightarrow{\mathbf{e}}}_{x_i}^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_{k,R}{\overrightarrow{\mathbf{r}}}_{i-j}}}+\underset{(c)}{\underbrace{{\overrightarrow{\mathbf{u}}}^{\mathrm{\top }}{\mathbf{W}}_{k,E}{\overrightarrow{\mathbf{e}}}_{x_j}}}+\underset{(d)}{\underbrace{{\overrightarrow{\mathbf{v}}}^{\mathrm{\top }}{\mathbf{W}}_{k,R}{\overrightarrow{\mathbf{r}}}_{i-j}}}$$

     一种更简单直接的改写方式为：$a_{i,j}^{\text{rel}}={\left({\mathbf{W}}_q({\overrightarrow{\mathbf{e}}}_{x_i}+{\overrightarrow{\mathbf{r}}}_{i-j})\right)}^{\mathrm{\top }}\left({\mathbf{W}}_k({\overrightarrow{\mathbf{e}}}_{x_j}+{\overrightarrow{\mathbf{r}}}_{j-i})\right)$$a_{i,j}^{\text{rel}} = \left(\mathbf W_q\left(\mathbf{\vec e}_{x_i}+\mathbf{\vec r}_{i-j}\right)\right)^\top\left(\mathbf W_k\left(\mathbf{\vec e}_{x_j}+\mathbf{\vec r}_{j-i}\right)\right)$ 。可以通过实验来验证效果。

     • 第一个改变是用相对位置编码 ${\overrightarrow{\mathbf{r}}}_{i-j}$$\mathbf{\vec r}_{i-j}$ 来取代 (b) 和 (d) 中的绝对位置编码 ${\overrightarrow{\mathbf{u}}}_j$$\mathbf{\vec u}_j$。这实质上反映了一个先验，即只有相对距离才是最重要的。注意，$\mathbf{R}$$\mathbf R$是一个正弦编码矩阵，没有可学习的参数。

       实际上，绝对位置在一些任务中也同样重要，例如：句子里的第一个位置和最后一个位置都比较重要，可能包含特殊的语义。

     • 其次，我们引入一个可训练的参数 $\overrightarrow{\mathbf{u}}\in {\mathbb{R}}^d$$\mathbf{\vec u}\in \mathbb R^d$ 来取代 (c) 中的 ${\left({\mathbf{W}}_q{\overrightarrow{\mathbf{u}}}_i\right)}^{\mathrm{\top }}$$\left(\mathbf W_q \mathbf{\vec u}_i\right)^\top$。在这种情况下，由于 query 向量对所有的 query position 都是相同的，因此这表明无论 query position 如何，对不同的单词的 attentive bias 应该保持不变。

       类似地，我们引入一个可训练的参数 $\overrightarrow{\mathbf{v}}\in {\mathbb{R}}^d$$\mathbf{\vec v}\in \mathbb R^d$ 来取代 (d) 中的 ${\left({\mathbf{W}}_q{\overrightarrow{\mathbf{u}}}_i\right)}^{\mathrm{\top }}$$\left(\mathbf W_q \mathbf{\vec u}_i\right)^\top$。这表明无论 query position 如何，对不同相对位置的 attentive bias 应该保持不变。

       在绝对位置编码中，query 的位置、key 的位置都很重要，因此需要两个 positional embedding ${\overrightarrow{\mathbf{u}}}_i,{\overrightarrow{\mathbf{u}}}_j$$\mathbf{\vec u}_i,\mathbf{\vec u}_j$。

       在绝对位置编码中，只有 query 和 key 的相对位置的编码才重要，因此只有一个 positional embedding ${\overrightarrow{\mathbf{r}}}_{i,j}$$\mathbf{\vec r}_{i,j}$ 。

     • 最后，我们特意将两个权重矩阵 ${\mathbf{W}}_{k,E}$$\mathbf W_{k,E}$ 和 ${\mathbf{W}}_{k,R}$$\mathbf W_{k,R}$ 分开，分别产生 content-based 和 location-based 的 key 向量。

       $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 和 $\overrightarrow{\mathbf{v}}$$\mathbf{\vec v}$ 也分别对应于 content-based 和 location-based 的 attentive bias 向量。

3. 在相对位置编码中，每一项都有直观的含义：

   • ${\overrightarrow{\mathbf{e}}}_{x_i}^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_{k,E}{\overrightarrow{\mathbf{e}}}_{x_j}$$\mathbf{\vec e}_{x_i}^\top\mathbf W_q^\top\mathbf W_{k,E}\mathbf{\vec e}_{x_j}$ ： 表示基于内容的寻址 addressing。
   • ${\overrightarrow{\mathbf{e}}}_{x_i}^{\mathrm{\top }}{\mathbf{W}}_q^{\mathrm{\top }}{\mathbf{W}}_{k,R}{\overrightarrow{\mathbf{r}}}_{i-j}$$\mathbf{\vec e}_{x_i}^\top\mathbf W_{q}^\top\mathbf W_{k,R}\mathbf{\vec r}_{i-j}$ ：捕获内容相关的 positional bias 。
   • ${\overrightarrow{\mathbf{u}}}^{\mathrm{\top }}{\mathbf{W}}_{k,E}{\overrightarrow{\mathbf{e}}}_{x_j}$$\mathbf{\vec u}^\top\mathbf W_{k,E}\mathbf{\vec e}_{x_j}$：捕获全局的 content bias 。
   • ${\overrightarrow{\mathbf{v}}}^{\mathrm{\top }}{\mathbf{W}}_{k,R}{\overrightarrow{\mathbf{r}}}_{i-j}$$\mathbf{\vec v}^\top\mathbf W_{k,R}\mathbf{\vec r}_{i-j}$：捕获全局的 positional bias 。

   相比之下，《Self-attention with relative position representations》 仅考虑了 (a), (b) 两项，放弃了 (c), (d) 两个 bias 项。此外，《Self-attention with relative position representations》 将 ${\mathbf{W}}_k\mathbf{R}$$\mathbf W_k \mathbf R$ 合并为单个矩阵可训练的矩阵 $\hat{\mathbf{R}}$$\hat{\mathbf R}$ ，这放弃了原始的正弦波位置编码中的 inductive bias 。相比之下，我们的 relative positional embedding $\mathbf{R}$$\mathbf R$ 采用正弦波公式，从而可以在评估期间泛化到训练期间更长的序列上。

4. 将segment-level 递归与我们提出的 relative positional embedding 相结合，我们最终得到了Transformer-XL架构。

   注意，为了计算所有的 pair $(i,j)$$(i,j)$ 的 ${\mathbf{W}}_{k,R}{\overrightarrow{\mathbf{r}}}_{i-j}$$\mathbf W_{k,R}\mathbf{\vec r}_{i-j}$ ，其计算代价为 $O(L^2)$$O(L^2)$ 。我们在论文附录中展示了一个简单的计算过程，它将成本降低到 $O(L)$$O(L)$ 。

   但是为了计算 $a_{i,j}^{\text{rel}}$$a_{i,j}^{\text{rel}}$ ，仍然需要 $O(L^2)$$O(L^2)$ 的计算复杂度。