Big Bird: Transformers for Longer Sequences

Big Bird: Transformers for Longer Sequences

Big Bird：面向更长序列的 Transformer

Manzil Zaheer Guru Guruganesh Avinava Dubey Affiliation: Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Affiliation: Anirudh Ravula, Qifan Wang, Li Yang, Amr Ahmed Affiliation: Google Research Affiliation: {manzilz, gurug, avinavadubey}@google.com

Abstract

摘要

O(1)

O(1)

1 Introduction

1 引言

Models based on Transformers [91], such as BERT [22, 63], are wildly successful for a wide variety of Natural Language Processing (NLP) tasks and consequently are mainstay of modern NLP research. Their versatility and robustness are the primary drivers behind the wide-scale adoption of Transformers. The model is easily adapted for a diverse range of sequence based tasks - as a seq2seq model for translation [91], summarization [66], generation [15], etc. or as a standalone encoders for sentiment analysis [83], POS tagging [65], machine reading comprehension [93], etc. - and it is known to vastly outperform previous sequence models like LSTM [37]. The key innovation in Transformers is the introduction of a self-attention mechanism, which can be evaluated in parallel for each token of the input sequence, eliminating the sequential dependency in recurrent neural networks, like LSTM. This parallelism enables Transformers to leverage the full power of modern SIMD hardware accelerators like GPUs/TPUs, thereby facilitating training of NLP models on datasets of unprecedented size. This ability to train on large scale data has led to surfacing of models like BERT [22] and T5 [75], which pretrain transformers on large general purpose corpora and transfer the knowledge to down-stream task. The pretraining has led to significant improvement in low data regime downstream tasks [51] as well as tasks with sufficient data [101] and thus have been a major force behind the ubiquity of transformers in contemporary NLP.

以 Transformer [91] 为基础的模型，如 BERT [22, 63]，在广泛 NLP 任务上极为成功，已成为现代 NLP 研究的主流。其通用性与稳健性是大规模采用的主要动力。模型易于适配多样的序列任务——作为翻译 [91]、摘要 [66]、生成 [15] 等的 seq2seq，或作为情感分析 [83]、词性标注 [65]、机器阅读理解 [93] 等的独立编码器——并显著优于 LSTM [37] 等既往序列模型。Transformer 的关键创新是自注意力：可对输入序列每个 token 并行计算，消除 LSTM 一类 RNN 的序列依赖。该并行性使 Transformer 能充分发挥 GPU/TPU 等现代 SIMD 加速器的能力，从而在前所未有规模的数据集上训练 NLP 模型。大规模训练催生了 BERT [22] 与 T5 [75] 等模型：在通用语料上预训练 Transformer，再把知识迁移到下游任务。预训练既提升低数据下游任务 [51]，也提升数据充足的任务 [101]，是 Transformer 在当代 NLP 中无处不在的重要原因。

The self-attention mechanism overcomes constraints of RNNs (namely the sequential nature of RNN) by allowing each token in the input sequence to attend independently to every other token in the sequence. This design choice has several interesting repercussions. In particular, the full self-attention have computational and memory requirement that is quadratic in the sequence length. We note that while the corpus can be large, the sequence length, which provides the context in many applications is very limited. Using commonly available current hardware and model sizes, this requirement translates to roughly being able to handle input sequences of length 512 tokens. This reduces its direct applicability to tasks that require larger context, like QA [60], document classification, etc.

自注意力克服 RNN 的序列性约束：输入序列中每个 token 可独立关注序列中每一个其他 token。这一设计选择带来若干后果。尤其是，全自注意力的计算与显存需求相对序列长度二次。我们注意到：语料可以很大，但许多应用提供上下文的序列长度非常有限。按常见硬件与模型规模，这大约只能处理 512 token 的输入。从而难以直接用于需要更长上下文的任务，如问答 [60]、文档分类等。

However, while we know that self-attention and Transformers are useful, our theoretical understanding is rudimentary. What aspects of the self-attention model are necessary for its performance? What can we say about the expressivity of Transformers and similar models? Apriori, it was not even clear from the design if the proposed self-attention mechanism was as effective as RNNs. For example, the self-attention does not even obey sequence order as it is permutation equivariant. This concern has been partially resolved, as Yun et al. 2019 showed that transformers are expressive enough to capture all continuous sequence to sequence functions with a compact domain. Meanwhile, Pérez et al. 2019 showed that the full transformer is Turing Complete (i.e. can simulate a full Turing machine). Two natural questions arise: Can we achieve the empirical benefits of a fully quadratic self-attention scheme using fewer inner-products? Do these sparse attention mechanisms preserve the expressivity and flexibility of the original network?

我们知道自注意力与 Transformer 有用，但理论理解仍粗糙。自注意力模型的哪些方面对其表现必要？Transformer 及类似模型的表达力如何？从设计上看，先验上甚至不清楚所提自注意力是否与 RNN 一样有效。例如，自注意力对置换等变，并不服从序列顺序。这一担忧已部分消解：Yun 等人 2019 表明 Transformer 足以刻画紧致定义域上所有连续序列到序列函数；Pérez 等人 2019 表明完整 Transformer 图灵完备（可模拟完整图灵机）。自然产生两个问题：能否用更少的内积获得全二次自注意力方案的经验收益？这些稀疏注意力机制是否保留原网络的表达力与灵活性？

In this paper, we address both the above questions and produce a sparse attention mechanism that improves performance on a multitude of tasks that require long contexts. We systematically develop BigBird, an attention mechanism whose complexity is linear in the number of tokens (Section 2). We take inspiration from graph sparsification methods and understand where the proof for expressiveness of Transformers breaks down when full-attention is relaxed to form the proposed attention pattern. This understanding helped us develop BigBird, which is theoretically as expressive and also empirically useful. In particular, our BigBird consists of three main part:

本文同时回答上述问题，并提出一种在众多需要长上下文的任务上提升表现的稀疏注意力机制。我们系统发展 BigBird：复杂度对 token 数线性的注意力机制（第 2 节）。我们从图稀疏化方法汲取灵感，并理解当全注意力放松为所提注意力模式时，Transformer 表达力证明在何处失效。这一理解帮助我们发展出理论上同样有表达力、经验上也有用的 BigBird。具体而言，BigBird 主要由三部分构成：

g

g

w

w

r

r

This leads to a high performing attention mechanism scaling to much longer sequence lengths (8x).

由此得到可扩展到更长序列长度（8 倍）的高性能注意力机制。

To summarize, our main contributions are:

总结一下，我们的主要 贡献 是：

O(n)

O(n)

Empirically, we show that the extended context modelled by BigBird benefits variety of NLP tasks. We achieve state of the art results for question answering and document summarization on a number of different datasets. Summary of these results are presented in Section 4.

经验上，我们表明 BigBird 建模的扩展上下文有益于多种 NLP 任务。我们在若干不同数据集的问答与文档摘要上取得 当时最优 结果。结果摘要见第 4 节。

Lastly, we introduce a novel application of attention based models where long contexts are beneficial: extracting contextual representations of genomics sequences like DNA. With longer masked LM pretraining, BigBird improves performance on downstream tasks such as promoter-region and chromatin profile prediction (Section 5).

最后，我们引入注意力模型在长上下文有益的新应用：提取 DNA 等基因组序列的上下文化表示。借助更长的掩码语言模型预训练，BigBird 提升启动子区域与染色质图谱预测等下游任务表现（第 5 节）。

1.1 Related Work

1.1 相关工作

There have been a number of interesting attempts, that were aimed at alleviating the quadratic dependency of Transformers, which can broadly categorized into two directions. First line of work embraces the length limitation and develops method around it. Simplest methods in this category just employ sliding window [93], but in general most work fits in the following general paradigm: using some other mechanism select a smaller subset of relevant contexts to feed in the transformer and optionally iterate, i.e. call transformer block multiple time with different contexts each time. Most prominently, SpanBERT [42], ORQA [54], REALM [34], RAG [57] have achieved strong performance for different tasks. However, it is worth noting that these methods often require significant engineering efforts (like back prop through large scale nearest neighbor search) and are hard to train.

缓解 Transformer 二次依赖已有许多有趣尝试，大致可分两个方向。第一类接受长度限制并在其周围发展方法。最简单的是只用滑动窗口 [93]，但多数工作符合如下范式：用其他机制选出更小的相关上下文子集送入 Transformer，并可选地迭代——即用不同上下文多次调用 Transformer 块。最突出的是 SpanBERT [42]、ORQA [54]、REALM [34]、RAG [57] 在不同任务上取得强表现。不过这些方法往往需要显著工程投入（如对大规模近邻搜索反向传播），且难以训练。

O(n\sqrt{n})

O(n\sqrt{n})

(a) Random attention

(a) 随机注意力

2 BigBird Architecture

2 BigBird 架构

{\bm{X}}=({\bm{x}}_{1},...,{\bm{x}}_{n})\in\mathbb{R}^{n\times d}

{\bm{X}}=({\bm{x}}_{1},...,{\bm{x}}_{n})\in\mathbb{R}^{n\times d}

\vskip-5.69054pt\small\textsc{Attn}_{D}({\bm{X}})_{i}={\bm{x}}_{i}+\sum_{h=1}^{H}\sigma\left(Q_{h}({\bm{x}}_{i})K_{h}({\bm{X}}_{N(i)})^{T}\right)\cdot V_{h}({\bm{X}}_{N(i)}) \tag{AT}

Q_{h},K_{h}:\mathbb{R}^{d}\to\mathbb{R}^{m}

Q_{h},K_{h}:\mathbb{R}^{d}\to\mathbb{R}^{m}

\tilde{\Theta}(n)

\tilde{\Theta}(n)

n

n

Model MLM SQuAD MNLI BERT-base 64.2 88.5 83.4 Random (R) 60.1 83.0 80.2 Window (W) 58.3 76.4 73.1 R + W 62.7 85.1 80.5 Table 1: Building block comparison @512

Model	MLM	SQuAD	MNLI
BERT-base	64.2	88.5	83.4
Random (R)	60.1	83.0	80.2
Window (W)	58.3	76.4	73.1
R + W	62.7	85.1	80.5

Model MLM SQuAD MNLI BERT-base 64.2 88.5 83.4 Random (R) 60.1 83.0 80.2 Window (W) 58.3 76.4 73.1 R + W 62.7 85.1 80.5 表 1：构件比较 @512

Model	MLM	SQuAD	MNLI
BERT-base	64.2	88.5	83.4
Random (R)	60.1	83.0	80.2
Window (W)	58.3	76.4	73.1
R + W	62.7	85.1	80.5

k

k

The final piece of BigBird is inspired from our theoretical analysis (Section 3), which is critical for empirical performance. More specifically, our theory utilizes the importance of “global tokens” (tokens that attend to all tokens in the sequence and to whom all tokens attend to (see Figure 1(c)). These global tokens can be defined in two ways:

BigBird 的最后一块来自我们的理论分析（第 3 节），对经验表现至关重要。更具体地，理论利用了「全局 token」的重要性：它们关注序列中所有 token，且所有 token 也关注它们（见图 1(c)）。全局 token 可用两种方式定义：

G

G

g

g

r

r

r=2

r=2

3 Theoretical Results about Sparse Attention Mechanism

3 稀疏注意力机制的理论结果

In this section, we will show that that sparse attention mechanisms are as powerful and expressive as full-attention mechanisms in two respects. First, we show that when sparse attention mechanisms are used in a standalone encoder (such as BERT), they are Universal Approximators of sequence to sequence functions in the style of Yun et al. 2019. We note that this property was also explored theoretically in contemporary work Yun et al. 2020. Second, unlike [105], we further show that sparse encoder-decoder transformers are Turing Complete (assuming the same conditions defined in [72]). Complementing the above positive results, we also show that moving to a sparse-attention mechanism incurs a cost, i.e. there is no free lunch. In Section 3.4, we show lower bounds by exhibiting a natural task where any sufficiently sparse mechanism will require polynomially more layers.

本节将表明，稀疏注意力机制在两方面与全注意力机制同样强大且有表达力。第一，当稀疏注意力用于独立编码器（如 BERT）时，它们按 Yun 等人 2019 的风格是序列到序列函数的通用逼近器。我们注意到当代工作 Yun 等人 2020 也从理论上探讨了该性质。第二，与 [105] 不同，我们进一步证明稀疏编码器-解码器 Transformer 在 [72] 所定义的相同条件下图灵完备。补充上述正面结果的同时，我们也表明转向稀疏注意力有代价，即没有免费午餐。在第 3.4 节，我们展示自然任务上的下界：任何足够稀疏的机制都需要多项式更多层。

3.1 Notation

3.1 记号

\mathcal{T}_{D}^{H,m,q}

\mathcal{T}_{D}^{H,m,q}

{\bm{x}}_{0}

{\bm{x}}_{0}

\mathcal{F}_{CD}

\mathcal{F}_{CD}

3.2 Universal Approximators

3.2 通用逼近器

S

S

S

S

1<p<\infty

1<p<\infty

To prove the theorem, we will follow the standard proof structure outlined in [104].

为证明该定理，我们遵循 [104] 概述的标准证明结构。

\mathcal{F}_{CD}

\mathcal{F}_{CD}

({\bm{X}},{\bm{x}}_{i})

({\bm{X}},{\bm{x}}_{i})

The main technical challenge is computing the contextual mapping using only sparse attention mechanism. This was done in [104] using a “selective” shift operator which shift up entries that are in a specific interval. Key to their proof was the fact that the shift, was exactly the range of the largest entry to the smallest entry.

主要技术挑战是仅用稀疏注意力计算上下文映射。[104] 用「选择性」移位算子完成：把落在特定区间的条目上移。其证明关键在于：移位恰好是从最大条目到最小条目的范围。

D

D

Step 3: Approximate modified transformers by original Transformers : The final step is to approximate the modified transformers by the original transformer which uses ReLU and softmax.

步骤 3：用原始 Transformer 逼近修改后的 Transformer ：最后一步是用采用 ReLU 与 softmax 的原始 Transformer 逼近修改后的 Transformer。

We provide the full details in Appendix A.

完整细节见附录 A。

3.3 Turing Completeness

3.3 图灵完备性

Transformers are a very general class. In the original paper of Vaswani et al. 2017, they were used in both an encoder and a decoder. While the previous section outlined how powerful just the encoders were, another natural question is to ask what the additional power of both a decoder along with an encoder is? Pérez et al. 2019 showed that the full transformer based on a quadratic attention mechanism is Turing Complete. This result makes one unrealistic assumption, which is that the model works on arbitrary precision model. Of course, this is necessary as otherwise, Transformers are bounded finite state machines and cannot be Turing Complete.

Transformer 是非常一般的类。在 Vaswani 等人 2017 原文中，它们同时用于编码器与解码器。上一节概述了仅编码器有多强大；另一个自然问题是：解码器与编码器一起额外带来什么能力？Pérez 等人 2019 表明基于二次注意力的完整 Transformer 图灵完备。该结果做了一个不现实的假设：模型在任意精度模型上工作。当然这是必要的，否则 Transformer 是有界有限状态机，不可能图灵完备。

It is natural to ask if the full attention mechanism is necessary. Or can a sparse attention mechanism also be used to simulate any Turing Machine? We show that this is indeed the case: we can use a sparse encoder and sparse decoder to simulate any Turing Machine.

自然要问：全注意力是否必要？稀疏注意力是否也可用于模拟任意图灵机？我们表明确实如此：可用稀疏编码器与稀疏解码器模拟任意图灵机。

To use the sparse attention mechanism in the transformer architecture, we need to define a suitable modification where each token only reacts to previous tokens. Unlike the case for BERT, where the entire attention mechanism is applied once, in full transformers, the sparse attention mechanism at decoder side is used token by token. Secondly the work of Pérez et al. 2019, uses each token as a representation of the tape history and uses the full attention to move and retrieve the correct tape symbol. Most of the construction of Pérez et al. 2019 goes through for sparse attentions, except for their addressing scheme to point back in history (Lemma B.4 in [72]). We show how to simulate this using a sparse attention mechanism and defer the details to Appendix B.

要在 Transformer 架构中使用稀疏注意力，需定义合适修改，使每个 token 只对先前 token 反应。与 BERT 一次性施加整段注意力不同，在完整 Transformer 中，解码器侧稀疏注意力逐 token 使用。其次，Pérez 等人 2019 用每个 token 表示纸带历史，并用全注意力移动与检索正确纸带符号。Pérez 等人 2019 的构造大部分对稀疏注意力成立，除了其指向历史的寻址方案（[72] 中引理 B.4）。我们说明如何用稀疏注意力模拟它，细节推迟到附录 B。

3.4 Limitations

3.4 局限

O(1)

O(1)

n

n

Finding vectors that are furthest apart boils down to minimize inner product search in case of unit vectors. For a full-attention mechanism with appropriate query and keys, this task is very easy as we can evaluate all pair-wise inner products.

找相距最远的向量在单位向量情形归结为最小化内积搜索。对带合适查询与键的全注意力机制，该任务很容易，因为可评估所有成对内积。

n

n

g\in\mathcal{T}^{H=1,m=2d,q=0}

g\in\mathcal{T}^{H=1,m=2d,q=0}

We give a formal proof of this fact in Appendix C.

我们在附录 C 给出该事实的形式证明。

4 Experiments: Natural Language Processing

4 实验：自然语言处理

In this section our goal is to showcase benefits of modeling longer input sequence for NLP tasks, for which we select three representative tasks. We begin with basic masked language modeling (MLM; Devlin et al. 2018) to check if better contextual representations can be learnt by utilizing longer contiguous sequences. Next, we consider QA with supporting evidence, for which capability to handle longer sequence would allow us to retrieve more evidence using crude systems like TF-IDF/BM25. Finally, we tackle long document classification where discriminating information may not be located in first 512 tokens. Below we summarize the results for BigBird using sequence length 4096[^1], while we defer all other setup details including computational resources, batch size, step size, to Appendix E.

本节目标是展示为 NLP 任务建模更长输入序列的收益，为此选取三项代表性任务。先从基础掩码语言建模（MLM；Devlin 等人 2018）入手，检验利用更长连续序列能否学到更好的上下文化表示。接着考虑带支持证据的问答：处理更长序列的能力使我们能用 TF-IDF/BM25 等粗系统检索更多证据。最后做长文档分类，其中判别信息可能不在前 512 token。下文汇总 BigBird 使用序列长度 4096[^1] 的结果；包括计算资源、batch size、步数等设置细节推迟到附录 E。

16GB

预训练与 MLM 我们遵循 [22, 63] 创建 base 与 large 版 BigBird，并用 MLM 目标预训练。该任务预测被掩码掉的随机 token 子集。我们用四个标准预训练数据集（列于第 E.1 节表 10），从公开 RoBERTa 检查点热启动[^2]。按 [8]，以每字符比特数比较对被掩码 token 的预测表现。如第 E.1 节表 10 所示，BigBird 与 Longformer 均优于长度受限的 RoBERTa，其中 BigBird-etc 最好。注意我们在合理的每芯片 16GB 显存、batch size 32-64 上训练。显存效率来自第 2 节所述稀疏注意力的高效分块与稀疏结构。

Model HotpotQA NaturalQ TriviaQA WikiHop Ans Sup Joint LA SA Full MCQ RoBERTa 73.5 83.4 63.5 - - 74.3 72.4 Longformer 74.3 84.4 64.4 - - 75.2 75.0 BigBird-itc 75.7 86.8 67.7 70.8 53.3 79.5 75.9 BigBird-etc 75.5 87.1 67.8 73.9 54.9 78.7 75.9 Table 2: QA Dev results using Base size models. We report accuracy for WikiHop and F1 for HotpotQA, Natural Questions, and TriviaQA.

Model		HotpotQA		NaturalQ		TriviaQA		WikiHop
	Ans	Sup	Joint		LA	SA		Full		MCQ
RoBERTa		73.5	83.4	63.5		-	-		74.3		72.4
Longformer		74.3	84.4	64.4		-	-		75.2		75.0
BigBird-itc		75.7	86.8	67.7		70.8	53.3		79.5		75.9
BigBird-etc		75.5	87.1	67.8		73.9	54.9		78.7		75.9

Model HotpotQA NaturalQ TriviaQA WikiHop Ans Sup Joint LA SA Full MCQ RoBERTa 73.5 83.4 63.5 - - 74.3 72.4 Longformer 74.3 84.4 64.4 - - 75.2 75.0 BigBird-itc 75.7 86.8 67.7 70.8 53.3 79.5 75.9 BigBird-etc 75.5 87.1 67.8 73.9 54.9 78.7 75.9 表 2：Base 规模模型的问答开发集结果。WikiHop 报准确率；HotpotQA、Natural Questions、TriviaQA 报 F1。

Model		HotpotQA		NaturalQ		TriviaQA		WikiHop
	Ans	Sup	Joint		LA	SA		Full		MCQ
RoBERTa		73.5	83.4	63.5		-	-		74.3		72.4
Longformer		74.3	84.4	64.4		-	-		75.2		75.0
BigBird-itc		75.7	86.8	67.7		70.8	53.3		79.5		75.9
BigBird-etc		75.5	87.1	67.8		73.9	54.9		78.7		75.9

Model HotpotQA NaturalQ TriviaQA WikiHop Ans Sup Joint LA SA Full Verified MCQ HGN [26] 82.2 88.5 74.2 - - - - - GSAN 81.6 88.7 73.9 - - - - - ReflectionNet [32] - - - 77.1 64.1 - - - RikiNet-v2 [61] - - - 76.1 61.3 - - - Fusion-in-Decoder [39] - - - - - 84.4 90.3 - SpanBERT [42] - - - - - 79.1 86.6 - MRC-GCN [87] - - - - - - - 78.3 MultiHop [14] - - - - - - - 76.5 Longformer [8] 81.2 88.3 73.2 - - 77.3 85.3 81.9 BigBird-etc 81.2 89.1 73.6 77.8 57.9 84.5 92.4 82.3 Table 3: Fine-tuning results on Test set for QA tasks. The Test results (F1 for HotpotQA, Natural Questions, TriviaQA, and Accuracy for WikiHop) have been picked from their respective leaderboard. For each task the top-3 leaders were picked not including BigBird-etc. For Natural Questions Long Answer (LA), TriviaQA, and WikiHop, BigBird-ETC is the new state-of-the-art . On HotpotQA we are third in the leaderboard by F1 and second by Exact Match (EM).

Model	HotpotQA		NaturalQ		TriviaQA		WikiHop
Ans	Sup	Joint		LA	SA		Full	Verified		MCQ
HGN [26]	82.2	88.5	74.2		-	-		-	-		-
GSAN	81.6	88.7	73.9		-	-		-	-		-
ReflectionNet [32]	-	-	-		77.1	64.1		-	-		-
RikiNet-v2 [61]	-	-	-		76.1	61.3		-	-		-
Fusion-in-Decoder [39]	-	-	-		-	-		84.4	90.3		-
SpanBERT [42]	-	-	-		-	-		79.1	86.6		-
MRC-GCN [87]	-	-	-		-	-		-	-		78.3
MultiHop [14]	-	-	-		-	-		-	-		76.5
Longformer [8]	81.2	88.3	73.2		-	-		77.3	85.3		81.9
BigBird-etc	81.2	89.1	73.6		77.8	57.9		84.5	92.4		82.3

| Model | HotpotQA | | NaturalQ | | TriviaQA | | WikiHop |---|---|---|---|---|---|---|---|---|---|---|---| | Ans | Sup | Joint | | LA | SA | | Full | Verified | | MCQ | HGN [26] | 82.2 | 88.5 | 74.2 | | - | - | | - | - | | - | | GSAN | 81.6 | 88.7 | 73.9 | | - | - | | - | - | | - | | ReflectionNet [32] | - | - | - | | 77.1 | 64.1 | | - | - | | - | | RikiNet-v2 [61] | - | - | - | | 76.1 | 61.3 | | - | - | | - | | Fusion-in-Decoder [39] | - | - | - | | - | - | | 84.4 | 90.3 | | - | | SpanBERT [42] | - | - | - | | - | - | | 79.1 | 86.6 | | - | | MRC-GCN [87] | - | - | - | | - | - | | - | - | | 78.3 | | MultiHop [14] | - | - | - | | - | - | | - | - | | 76.5 | | Longformer [8] | 81.2 | 88.3 | 73.2 | | - | - | | 77.3 | 85.3 | | 81.9 | | BigBird-etc | 81.2 | 89.1 | 73.6 | | 77.8 | 57.9 | | 84.5 | 92.4 | | 82.3 | 表 3：问答任务测试集微调结果。测试结果取自各排行榜；每项取不含 BigBird-etc 的前三。Natural Questions 长答案、TriviaQA 与 WikiHop 上 BigBird-ETC 为新的当时最优；HotpotQA 按 F1 第三、按 EM 第二。

Question Answering (QA) We considered following four challenging datasets:

问答（QA） 我们考虑以下四个具有挑战性的数据集：

Natural Questions [52]: For the given question, find a short span of answer (SA) from the given evidences as well highlight the paragraph from the given evidences containing information about the correct answer (LA).

Natural Questions [52]：给定问题，从给定证据中找出简短答案跨度（SA），并标出包含正确答案信息的证据段落（LA）。

HotpotQA-distractor [100]: Similar to natural questions, it requires finding the answer (Ans) as well as the supporting facts (Sup) over different documents needed for multi-hop reasoning from the given evidences.

HotpotQA-distractor [100]：类似 Natural Questions，需从给定证据中找出答案（Ans）以及多跳推理所需、分布在不同文档上的支持事实（Sup）。

TriviaQA-wiki [41]: We need to provide an answer for the given question using provided Wikipedia evidence, however, the answer might not be present in the given evidence. On a smaller verified subset of question, the given evidence is guaranteed to contain the answer. Nevertheless, we model the answer as span selection problem in this case as well.

TriviaQA-wiki [41]：利用所提供的维基证据回答给定问题；答案未必出现在证据中。在更小的 verified 问题子集上，证据保证包含答案。尽管如此，我们仍把答案建模为跨度选择问题。

WikiHop [95]: Chose correct option from multiple-choice questions (MCQ), by aggregating information spread across multiple documents given in the evidences.

WikiHop [95]：通过聚合证据中分布在多文档上的信息，从多项选择题（MCQ）中选出正确选项。

As these tasks are very competitive, multiple highly engineered systems have been designed specific each dataset confirming to respective output formats. For a fair comparison, we had to use some additional regularization for training BigBird, details of which are provided in Section E.2 along with exact architecture description. We experiment using the base sized model and select the best configuration on the development set for each dataset (as reported in Table 2). We can see that BigBird-etc, with expanded global tokens consistently outperforms all other models. Thus, we chose this configuration to train a large sized model to be used for evaluation on the hidden test set.

这些任务竞争激烈，已有多套高度工程化的系统分别针对各数据集与输出格式。为公平比较，训练 BigBird 时需使用一些额外正则，细节与精确架构描述见第 E.2 节。我们用 base 规模模型实验，并在各数据集开发集上选最佳配置（见表 2）。可见带扩展全局 token 的 BigBird-etc 持续优于所有其他模型。因此我们选该配置训练 large 规模模型，用于隐藏测试集评估。

In Table 3, we compare BigBird-etc model to top-3 entries from the leaderboard excluding BigBird. One can clearly see the importance of using longer context as both Longformer and BigBird outperform models with smaller contexts. Also, it is worth noting that BigBird submission is a single model, whereas the other top-3 entries for Natural Questions are ensembles, which might explain the slightly lower accuracy in exact answer phrase selection.

在表 3 中，我们把 BigBird-etc 与排行榜上除 BigBird 外的前三名比较。可清楚看到使用更长上下文的重要性：Longformer 与 BigBird 均超过较短上下文的模型。另需注意 BigBird 提交是单模型，而 Natural Questions 其他前三多为集成，这或许解释了精确答案短语选择上略低的准确率。

\bm{5\%}

\bm{5\%}

Model Arxiv PubMed BigPatent R-1 R-2 R-L R-1 R-2 R-L R-1 R-2 R-L Prior Art SumBasic [68] 29.47 6.95 26.30 37.15 11.36 33.43 27.44 7.08 23.66 LexRank [25] 33.85 10.73 28.99 39.19 13.89 34.59 35.57 10.47 29.03 LSA [97] 29.91 7.42 25.67 33.89 9.93 29.70 - - - Attn-Seq2Seq [85] 29.30 6.00 25.56 31.55 8.52 27.38 28.74 7.87 24.66 Pntr-Gen-Seq2Seq [77] 32.06 9.04 25.16 35.86 10.22 29.69 33.14 11.63 28.55 Long-Doc-Seq2Seq [20] 35.80 11.05 31.80 38.93 15.37 35.21 - - - Sent-CLF [81] 34.01 8.71 30.41 45.01 19.91 41.16 36.20 10.99 31.83 Sent-PTR [81] 42.32 15.63 38.06 43.30 17.92 39.47 34.21 10.78 30.07 Extr-Abst-TLM [81] 41.62 14.69 38.03 42.13 16.27 39.21 38.65 12.31 34.09 Dancer [31] 42.70 16.54 38.44 44.09 17.69 40.27 - - - Base Transformer 28.52 6.70 25.58 31.71 8.32 29.42 39.66 20.94 31.20 + RoBERTa [76] 31.98 8.13 29.53 35.77 13.85 33.32 41.11 22.10 32.58 + Pegasus [107] 34.81 10.16 30.14 39.98 15.15 35.89 43.55 20.43 31.80 BigBird-RoBERTa 41.22 16.43 36.96 43.70 19.32 39.99 55.69 37.27 45.56 Large Pegasus (Reported) [107] 44.21 16.95 38.83 45.97 20.15 41.34 52.29 33.08 41.75 Pegasus (Re-eval) 43.85 16.83 39.17 44.53 19.30 40.70 52.25 33.04 41.80 BigBird-Pegasus 46.63 19.02 41.77 46.32 20.65 42.33 60.64 42.46 50.01 Table 4: Summarization ROUGE score for long documents.

Model	Arxiv	PubMed	BigPatent
	R-1	R-2	R-L	R-1	R-2	R-L	R-1	R-2	R-L
Prior Art	SumBasic [68]	29.47	6.95	26.30	37.15	11.36	33.43	27.44	7.08	23.66
	LexRank [25]	33.85	10.73	28.99	39.19	13.89	34.59	35.57	10.47	29.03
	LSA [97]	29.91	7.42	25.67	33.89	9.93	29.70	-	-	-
	Attn-Seq2Seq [85]	29.30	6.00	25.56	31.55	8.52	27.38	28.74	7.87	24.66
	Pntr-Gen-Seq2Seq [77]	32.06	9.04	25.16	35.86	10.22	29.69	33.14	11.63	28.55
	Long-Doc-Seq2Seq [20]	35.80	11.05	31.80	38.93	15.37	35.21	-	-	-
	Sent-CLF [81]	34.01	8.71	30.41	45.01	19.91	41.16	36.20	10.99	31.83
	Sent-PTR [81]	42.32	15.63	38.06	43.30	17.92	39.47	34.21	10.78	30.07
	Extr-Abst-TLM [81]	41.62	14.69	38.03	42.13	16.27	39.21	38.65	12.31	34.09
	Dancer [31]	42.70	16.54	38.44	44.09	17.69	40.27	-	-	-
Base	Transformer	28.52	6.70	25.58	31.71	8.32	29.42	39.66	20.94	31.20
	+ RoBERTa [76]	31.98	8.13	29.53	35.77	13.85	33.32	41.11	22.10	32.58
	+ Pegasus [107]	34.81	10.16	30.14	39.98	15.15	35.89	43.55	20.43	31.80
	BigBird-RoBERTa	41.22	16.43	36.96	43.70	19.32	39.99	55.69	37.27	45.56
Large	Pegasus (Reported) [107]	44.21	16.95	38.83	45.97	20.15	41.34	52.29	33.08	41.75
	Pegasus (Re-eval)	43.85	16.83	39.17	44.53	19.30	40.70	52.25	33.04	41.80
	BigBird-Pegasus	46.63	19.02	41.77	46.32	20.65	42.33	60.64	42.46	50.01

| Model | Arxiv | PubMed | BigPatent |---|---|---|---|---|---|---|---|---|---|---| R-1 | R-2 | R-L | R-1 | R-2 | R-L | R-1 | R-2 | R-L | Prior Art | SumBasic [68] | 29.47 | 6.95 | 26.30 | 37.15 | 11.36 | 33.43 | 27.44 | 7.08 | 23.66 | LexRank [25] | 33.85 | 10.73 | 28.99 | 39.19 | 13.89 | 34.59 | 35.57 | 10.47 | 29.03 | LSA [97] | 29.91 | 7.42 | 25.67 | 33.89 | 9.93 | 29.70 | - | - | - | Attn-Seq2Seq [85] | 29.30 | 6.00 | 25.56 | 31.55 | 8.52 | 27.38 | 28.74 | 7.87 | 24.66 | Pntr-Gen-Seq2Seq [77] | 32.06 | 9.04 | 25.16 | 35.86 | 10.22 | 29.69 | 33.14 | 11.63 | 28.55 | Long-Doc-Seq2Seq [20] | 35.80 | 11.05 | 31.80 | 38.93 | 15.37 | 35.21 | - | - | - | Sent-CLF [81] | 34.01 | 8.71 | 30.41 | 45.01 | 19.91 | 41.16 | 36.20 | 10.99 | 31.83 | Sent-PTR [81] | 42.32 | 15.63 | 38.06 | 43.30 | 17.92 | 39.47 | 34.21 | 10.78 | 30.07 | Extr-Abst-TLM [81] | 41.62 | 14.69 | 38.03 | 42.13 | 16.27 | 39.21 | 38.65 | 12.31 | 34.09 | Dancer [31] | 42.70 | 16.54 | 38.44 | 44.09 | 17.69 | 40.27 | - | - | - | | Base | Transformer | 28.52 | 6.70 | 25.58 | 31.71 | 8.32 | 29.42 | 39.66 | 20.94 | 31.20 | + RoBERTa [76] | 31.98 | 8.13 | 29.53 | 35.77 | 13.85 | 33.32 | 41.11 | 22.10 | 32.58 | + Pegasus [107] | 34.81 | 10.16 | 30.14 | 39.98 | 15.15 | 35.89 | 43.55 | 20.43 | 31.80 | BigBird-RoBERTa | 41.22 | 16.43 | 36.96 | 43.70 | 19.32 | 39.99 | 55.69 | 37.27 | 45.56 | | Large | Pegasus (Reported) [107] | 44.21 | 16.95 | 38.83 | 45.97 | 20.15 | 41.34 | 52.29 | 33.08 | 41.75 | Pegasus (Re-eval) | 43.85 | 16.83 | 39.17 | 44.53 | 19.30 | 40.70 | 52.25 | 33.04 | 41.80 | BigBird-Pegasus | 46.63 | 19.02 | 41.77 | 46.32 | 20.65 | 42.33 | 60.64 | 42.46 | 50.01 | 表 4：长文档摘要的 ROUGE 分数。

4.1 Encoder-Decoder Tasks

4.1 编码器-解码器任务

\sim 200

\sim 200

Summarization Document summarization is a task of creating a short and accurate summary of a text document. We used three long document datasets for testing our model details of which are mention in Table 18. In this paper we focus on abstractive summarization of long documents where using a longer contextual encoder should improve performance. The reasons are two fold: First, the salient content can be evenly distributed in the long document, not just in first 512 tokens, and this is by design in the BigPatents dataset [78]. Second, longer documents exhibit a richer discourse structure and summaries are considerably more abstractive, thereby observing more context helps. As has been pointed out recently [76, 107], pretraining helps in generative tasks, we warm start from our general purpose MLM pretraining on base-sized models as well as utilizing state-of-the-art summarization specific pretraining from Pegasus [107] on large-sized models. The results of training BigBird sparse encoder along with full decoder on these long document datasets are presented in Table 4. We can clearly see modeling longer context brings significant improvement. Along with hyperparameters, we also present results on shorter but more widespread datasets in Section E.5, which show that using sparse attention does not hamper performance either.

摘要 文档摘要旨在生成短而准确的文本摘要。我们用三个长文档数据集测试模型，细节见表 18。本文聚焦长文档抽象摘要：更长上下文编码器应能提升表现，原因有二。其一，显著内容可均匀分布在长文档中，而非仅在前 512 token，这在 BigPatents 数据集 [78] 中是刻意设计。其二，更长文档展现更丰富的篇章结构，摘要也明显更抽象，因此观察更多上下文有帮助。如近期所指出 [76, 107]，预训练有益于生成任务；我们从 base 规模的通用 MLM 预训练热启动，并在 large 规模上利用 Pegasus [107] 的摘要专用预训练。在这些长文档数据集上，用 BigBird 稀疏编码器配全解码器训练的结果见表 4。可清楚看到建模更长上下文带来显著提升。连同超参，第 E.5 节也给出更短但更常见数据集上的结果，表明使用稀疏注意力并不损害表现。

5 Experiments: Genomics

5 实验：基因组学

There has been a recent upsurge in using deep learning for genomics data [86, 106, 13], which has resulted in improved performance on several biologically-significant tasks such as promoter site prediction [71], methylation analysis [55], predicting functional effects of non-coding variant [109], etc. These approaches consume DNA sequence fragments as inputs, and therefore we believe longer input sequence handling capability of BigBird would be beneficial as many functional effects in DNA are highly non-local [12]. Furthermore, taking inspiration from NLP, we learn powerful contextual representations for DNA fragments utilizing abundant unlabeled data (e.g. human reference genome, Saccharomyces Genome Database) via MLM pretraining. Next, we showcase that our long input BigBird along with the proposed pretraining significantly improves performances in two downstream tasks. Detailed experimental setup for the two tasks are provided in Appendix F.

近期深度学习用于基因组数据显著升温 [86, 106, 13]，并在启动子位点预测 [71]、甲基化分析 [55]、非编码变异功能效应预测 [109] 等多项生物学重要任务上提升表现。这些方法以 DNA 序列片段为输入，因此我们相信 BigBird 处理更长输入的能力会有益——DNA 中许多功能效应高度非局部 [12]。进一步，受 NLP 启发，我们利用充足的无标注数据（如人类参考基因组、酿酒酵母基因组数据库）经 MLM 预训练学习 DNA 片段的强上下文化表示。接下来展示：长输入 BigBird 配合所提预训练，在两项下游任务上显著提升表现。两项任务的详细实验设置见附录 F。

Model BPC SRILM [58] 1.57 BERT (sqln. 512) 1.23 BigBird (sqln. 4096) 1.12 Table 5: MLM BPC

Model	BPC
SRILM [58]	1.57
BERT (sqln. 512)	1.23
BigBird (sqln. 4096)	1.12

Model BPC SRILM [58] 1.57 BERT (sqln. 512) 1.23 BigBird (sqln. 4096) 1.12 表 5：MLM 的 BPC

Model	BPC
SRILM [58]	1.57
BERT (sqln. 512)	1.23
BigBird (sqln. 4096)	1.12

Pre-training and MLM As explored in Liang 2012, instead of operating on base pairs, we propose to first segment DNA into tokens so as to further increase the context length (Appendix F, Figure 7). In particular, we build a byte-pair encoding [50] table for the DNA sequence of size 32K, with each token representing 8.78 base pairs on average. We learn contextual representation of these token on the human reference genome (GRCh37)[^3] using MLM objective. We then report the bits per character (BPC) on a held-out set in Table 5. We find that attention based contextual representation of DNA does improve BPC, which is further improved by using longer context.

预训练与 MLM 如 Liang 2012 所探索，我们建议先不在碱基对上直接操作，而是把 DNA 切成 token，以进一步增大上下文长度（附录 F，图 7）。具体地，为 DNA 序列构建大小 32K 的 byte-pair encoding [50] 表，每个 token 平均代表 8.78 个碱基对。我们在人类参考基因组（GRCh37）[^3] 上用 MLM 目标学习这些 token 的上下文化表示，并在表 5 报告留出集上的每字符比特数（BPC）。我们发现基于注意力的 DNA 上下文化表示确实改善 BPC，使用更长上下文可进一步改善。

Model F1 CNNProm [90] 69.7 DeePromoter [71] 95.6 BigBird 99.9 Table 6: Comparison.

Model	F1
CNNProm [90]	69.7
DeePromoter [71]	95.6
BigBird	99.9

Model F1 CNNProm [90] 69.7 DeePromoter [71] 95.6 BigBird 99.9 表 6：比较。

Model	F1
CNNProm [90]	69.7
DeePromoter [71]	95.6
BigBird	99.9

5\%

5\%

Model TF HM DHS gkm-SVM [30] 89.6 - - DeepSea [109] 95.8 85.6 92.3 BigBird 96.1 88.7 92.1 Table 7: Chromatin-Profile Prediction

Model	TF	HM	DHS
gkm-SVM [30]	89.6	-	-
DeepSea [109]	95.8	85.6	92.3
BigBird	96.1	88.7	92.1

Model TF HM DHS gkm-SVM [30] 89.6 - - DeepSea [109] 95.8 85.6 92.3 BigBird 96.1 88.7 92.1 表 7：染色质图谱预测

Model	TF	HM	DHS
gkm-SVM [30]	89.6	-	-
DeepSea [109]	95.8	85.6	92.3
BigBird	96.1	88.7	92.1

690

690

6 Conclusion

6 结论

We propose BigBird: a sparse attention mechanism that is linear in the number of tokens. BigBird satisfies a number of theoretical results: it is a universal approximator of sequence to sequence functions and is also Turing complete. Theoretically, we use the power of extra global tokens preserve the expressive powers of the model. We complement these results by showing that moving to sparse attention mechanism do incur a cost. Empirically, BigBird gives state-of-the-art performance on a number of NLP tasks such as question answering and long document classification. We further introduce attention based contextual language model for DNA and fine-tune it for down stream tasks such as promoter region prediction and predicting effects of non-coding variants.

我们提出 BigBird：对 token 数线性的稀疏注意力机制。BigBird 满足若干理论结果：它是序列到序列函数的通用逼近器，且图灵完备。理论上，我们利用额外全局 token 的力量保留模型表达力。我们补充表明：转向稀疏注意力确有代价。经验上，BigBird 在问答与长文档分类等多项 NLP 任务上给出 当时最优 表现。我们进一步为 DNA 引入基于注意力的上下文化语言模型，并微调用于启动子区域预测与非编码变异效应预测等下游任务。

References

参考文献

Big Bird: Transformers for Longer Sequences - Appendix

Abboud et al. [2014] A. Abboud, V. V. Williams, and O. Weimann. Consequences of faster alignment of sequences. In International Colloquium on Automata, Languages, and Programming , pages 39–51. Springer, 2014. Abboud et al. [2015] A. Abboud, A. Backurs, and V. V. Williams. Tight hardness results for lcs and other sequence similarity measures. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 59–78. IEEE, 2015. Abreu et al. [2019] J. Abreu, L. Fred, D. Macêdo, and C. Zanchettin. Hierarchical attentional hybrid neural networks for document classification. In International Conference on Artificial Neural Networks , pages 396–402. Springer, 2019. Ainslie et al. [2020] J. Ainslie, S. Ontanon, C. Alberti, P. Pham, A. Ravula, and S. Sanghai. Etc: Encoding long and structured data in transformers. arXiv preprint arXiv:2004.08483 , 2020. Alberti et al. [2019] C. Alberti, K. Lee, and M. Collins. A bert baseline for the natural questions. arXiv preprint arXiv:1901.08634 , 2019. Alt et al. [2019] J. Alt, R. Ducatez, and A. Knowles. Extremal eigenvalues of critical erd \ \backslash h { { o } } sr \ \backslash ’enyi graphs. arXiv preprint arXiv:1905.03243 , 2019. Backurs and Indyk [2015] A. Backurs and P. Indyk. Edit distance cannot be computed in strongly subquadratic time (unless seth is false). In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 51–58, 2015. Beltagy et al. [2020] I. Beltagy, M. E. Peters, and A. Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150 , 2020. Benaych-Georges et al. [2019] F. Benaych-Georges, C. Bordenave, A. Knowles, et al. Largest eigenvalues of sparse inhomogeneous erdős–rényi graphs. Annals of Probability , 47(3):1653–1676, 2019. Benaych-Georges et al. [2020] F. Benaych-Georges, C. Bordenave, A. Knowles, et al. Spectral radii of sparse random matrices. In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques , volume 56, pages 2141–2161. Institut Henri Poincaré, 2020.

Bharanikumar et al. [2018] R. Bharanikumar, K. A. R. Premkumar, and A. Palaniappan. Promoterpredict: sequence-based modelling of escherichia coli σ \sigma 70 promoter strength yields logarithmic dependence between promoter strength and sequence. PeerJ , 6:e5862, 2018. Buldyrev et al. [1995] S. Buldyrev, A. Goldberger, S. Havlin, R. Mantegna, M. Matsa, C.-K. Peng, M. Simons, and H. Stanley. Long-range correlation properties of coding and noncoding dna sequences: Genbank analysis. Physical Review E , 51(5):5084, 1995. Busia et al. [2019] A. Busia, G. E. Dahl, C. Fannjiang, D. H. Alexander, E. Dorfman, R. Poplin, C. Y. McLean, P.-C. Chang, and M. DePristo. A deep learning approach to pattern recognition for short dna sequences. BioRxiv , page 353474, 2019. Chen et al. [2019a] J. Chen, S.-t. Lin, and G. Durrett. Multi-hop question answering via reasoning chains. arXiv preprint arXiv:1910.02610 , 2019a. Chen et al. [2019b] Y.-C. Chen, Z. Gan, Y. Cheng, J. Liu, and J. Liu. Distilling the knowledge of bert for text generation. arXiv preprint arXiv:1911.03829 , 2019b. Child et al. [2019] R. Child, S. Gray, A. Radford, and I. Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509 , 2019. Chung and Lu [2002] F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceedings of the National Academy of Sciences , 99(25):15879–15882, 2002. Clark and Gardner [2017] C. Clark and M. Gardner. Simple and effective multi-paragraph reading comprehension. arXiv preprint arXiv:1710.10723 , 2017. Clark et al. [2019] K. Clark, U. Khandelwal, O. Levy, and C. D. Manning. What does bert look at? an analysis of bert’s attention. arXiv preprint arXiv:1906.04341 , 2019. Cohan et al. [2018] A. Cohan, F. Dernoncourt, D. S. Kim, T. Bui, S. Kim, W. Chang, and N. Goharian. A discourse-aware attention model for abstractive summarization of long documents. arXiv preprint arXiv:1804.05685 , 2018.

Gidiotis and Tsoumakas [2020] A. Gidiotis and G. Tsoumakas. A divide-and-conquer approach to the summarization of academic articles. arXiv preprint arXiv:2004.06190 , 2020. Gong [2020 (accessed June 3, 2020] M. Gong. ReflectionNet , 2020 (accessed June 3, 2020). URL https://www.microsoft.com/en-us/research/people/migon/ . Gray et al. [2017] S. Gray, A. Radford, and D. P. Kingma. Gpu kernels for block-sparse weights. arXiv preprint arXiv:1711.09224 , 3, 2017. Guu et al. [2020] K. Guu, K. Lee, Z. Tung, P. Pasupat, and M.-W. Chang. Realm: Retrieval-augmented language model pre-training. arXiv preprint arXiv:2002.08909 , 2020. He et al. [2019] J. He, L. Wang, L. Liu, J. Feng, and H. Wu. Long document classification from local word glimpses via recurrent attention learning. IEEE Access , 7:40707-40718, 2019. Hermann et al. [2015] K. M. Hermann, T. Kocisky, E. Grefenstette, L. Espeholt, W. Kay, M. Suleyman, and P. Blunsom. Teaching machines to read and comprehend. In Advances in neural information processing systems , pages 1693-1701, 2015. Hochreiter and Schmidhuber [1997] S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation , 9(8):1735-1780, 1997. Hoory et al. [2006] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society , 43(4):439-561, 2006. Izacard and Grave [2020] G. Izacard and E. Grave. Leveraging passage retrieval with generative models for open domain question answering. arXiv preprint arXiv:2007.01282 , 2020. Jiang et al. [2019] Y. Jiang, J. Petrak, X. Song, K. Bontcheva, and D. Maynard. Team bertha von suttner at semeval-2019 task 4: Hyperpartisan news detection using elmo sentence representation convolutional network. In Proceedings of the 13th International Workshop on Semantic Evaluation , pages 840-844, 2019.

Liu et al. [2020] D. Liu, Y. Gong, J. Fu, Y. Yan, J. Chen, D. Jiang, J. Lv, and N. Duan. Rikinet: Reading wikipedia pages for natural question answering. arXiv preprint arXiv:2004.14560 , 2020. Liu and Lapata [2019] Y. Liu and M. Lapata. Text summarization with pretrained encoders. arXiv preprint arXiv:1908.08345 , 2019. Liu et al. [2019] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692 , 2019. Maas et al. [2011] A. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies , pages 142-150, 2011. Martin et al. [2019] L. Martin, B. Muller, P. J. O. Suárez, Y. Dupont, L. Romary, É. V. de la Clergerie, D. Seddah, and B. Sagot. Camembert: a tasty french language model. arXiv preprint arXiv:1911.03894 , 2019. Miller [2019] D. Miller. Leveraging bert for extractive text summarization on lectures. arXiv preprint arXiv:1906.04165 , 2019. Narayan et al. [2018] S. Narayan, S. B. Cohen, and M. Lapata. Don’t give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization. arXiv preprint arXiv:1808.08745 , 2018. Nenkova and Vanderwende [2005] A. Nenkova and L. Vanderwende. The impact of frequency on summarization. Microsoft Research, Redmond, Washington, Tech. Rep. MSR-TR-2005 , 101, 2005. Olson et al. [2019] M. L. Olson, L. Zhang, and C.-N. Yu. Adapting pretrained language models for long document classification. OpenReview , 2019. Oord et al. [2018] A. v. d. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748 , 2018.

Oubounyt et al. [2019] M. Oubounyt, Z. Louadi, H. Tayara, and K. T. Chong. Deepromoter: Robust promoter predictor using deep learning. Frontiers in genetics , 10, 2019. Pérez et al. [2019] J. Pérez, J. Marinković, and P. Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv:1901.03429 , 2019. Qiu et al. [2019] J. Qiu, H. Ma, O. Levy, S. W.-t. Yih, S. Wang, and J. Tang. Blockwise self-attention for long document understanding. arXiv preprint arXiv:1911.02972 , 2019. Rae et al. [2019] J. W. Rae, A. Potapenko, S. M. Jayakumar, and T. P. Lillicrap. Compressive transformers for long-range sequence modelling. arXiv preprint arXiv:1911.05507 , 2019. Raffel et al. [2019] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683 , 2019. Rothe et al. [2019] S. Rothe, S. Narayan, and A. Severyn. Leveraging pre-trained checkpoints for sequence generation tasks. arXiv preprint arXiv:1907.12461 , 2019. See et al. [2017] A. See, P. J. Liu, and C. D. Manning. Get to the point: Summarization with pointer-generator networks. arXiv preprint arXiv:1704.04368 , 2017. Sharma et al. [2019] E. Sharma, C. Li, and L. Wang. Bigpatent: A large-scale dataset for abstractive and coherent summarization. arXiv preprint arXiv:1906.03741 , 2019. Shaw et al. [2018] P. Shaw, J. Uszkoreit, and A. Vaswani. Self-attention with relative position representations. arXiv preprint arXiv:1803.02155 , 2018. Spielman and Teng [2011] D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs. SIAM Journal on Computing , 40(4):981-1025, 2011.

Subramanian et al. [2019] S. Subramanian, R. Li, J. Pilault, and C. Pal. On extractive and abstractive neural document summarization with transformer language models. arXiv preprint arXiv:1909.03186 , 2019. Sukhbaatar et al. [2019] S. Sukhbaatar, E. Grave, P. Bojanowski, and A. Joulin. Adaptive attention span in transformers. arXiv preprint arXiv:1905.07799 , 2019. Sun et al. [2019] C. Sun, L. Huang, and X. Qiu. Utilizing bert for aspect-based sentiment analysis via constructing auxiliary sentence. arXiv preprint arXiv:1903.09588 , 2019. Sussman [2017 (accessed June 3, 2020] D. Sussman. Lecture Notes for Boston University MA 882 Spring 2017 , 2017 (accessed June 3, 2020). URL http://math.bu.edu/people/sussman/MA882_2017/2017-01-26-Lecture-2.html . Sutskever et al. [2014] I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems , pages 3104-3112, 2014. Tampuu et al. [2019] A. Tampuu, Z. Bzhalava, J. Dillner, and R. Vicente. Viraminer: Deep learning on raw dna sequences for identifying viral genomes in human samples. PloS one , 14(9), 2019. Tang et al. [2020] Z. Tang, Y. Shen, X. Ma, W. Xu, J. Yu, and W. Lu. Multi-hop reading comprehension across documents with path-based graph convolutional network. arXiv:2006.06478 , 2020. Thongtan and Phienthrakul [2019] T. Thongtan and T. Phienthrakul. Sentiment classification using document embeddings trained with cosine similarity. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: Student Research Workshop , pages 407-414, 2019. Trinh and Le [2018] T. H. Trinh and Q. V. Le. A simple method for commonsense reasoning. arXiv preprint arXiv:1806.02847 , 2018. Umarov and Solovyev [2017] R. K. Umarov and V. V. Solovyev. Recognition of prokaryotic and eukaryotic promoters using convolutional deep learning neural networks. PloS one , 12(2), 2017.

Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in neural information processing systems , pages 5998-6008, 2017. Wang et al. [2018] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07461 , 2018. Wang et al. [2019] Z. Wang, P. Ng, X. Ma, R. Nallapati, and B. Xiang. Multi-passage bert: A globally normalized bert model for open-domain question answering. arXiv preprint arXiv:1908.08167 , 2019. Watts and Strogatz [1998] D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’networks. nature , 393(6684):440-442, 1998. Welbl et al. [2018] J. Welbl, P. Stenetorp, and S. Riedel. Constructing datasets for multi-hop reading comprehension across documents. Transactions of the Association for Computational Linguistics , 6:287-302, 2018. Williams [2005] R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science , 348(2-3):357-365, 2005. Wiseman et al. [2017] S. Wiseman, S. M. Shieber, and A. M. Rush. Challenges in data-to-document generation. arXiv preprint arXiv:1707.08052 , 2017. Xiao et al. [2019] X. Xiao, Z.-C. Xu, W.-R. Qiu, P. Wang, H.-T. Ge, and K.-C. Chou. ipsw (2l)-pseknc: A two-layer predictor for identifying promoters and their strength by hybrid features via pseudo k-tuple nucleotide composition. Genomics , 111(6):1785-1793, 2019. Yang et al. [2017] Y. Yang, R. Zhang, S. Singh, and J. Ma. Exploiting sequence-based features for predicting enhancer-promoter interactions. Bioinformatics , 33(14):i252-i260, 2017. Yang et al. [2018] Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv:1809.09600 , 2018.

Appendix A Universal Approximators

附录 A 通用逼近器

A.1 Notation

A.1 记号

\operatorname{Enc}

\operatorname{Enc}

{\bm{X}}

{\bm{X}}

O

O

i

\operatorname{Enc}({\bm{X}})

\displaystyle{\bm{z}}_{i}=O({\bm{a}}_{i})+{\bm{a}}_{i}\qquad\text{where}\qquad{\bm{a}}_{i}=\textsc{Attn}({\bm{X}})_{i}+{\bm{x}}_{i} \tag{1}

O

O

Q,K,V:\mathbb{R}^{d}\to\mathbb{R}^{m}

Q,K,V:\mathbb{R}^{d}\to\mathbb{R}^{m}

\displaystyle\textsc{Attn}_{D}({\bm{X}})_{i} \\ \displaystyle=\sum_{h=1}^{H}\sigma\left(({\bm{x}}_{i}W_{Q}^{h})({\bm{X}}_{N(i)}W_{K}^{h})^{T}\right)\cdot({\bm{X}}_{N(i)}W_{V}^{h}) \tag{AT}

N(i)

N(i)

Lastly, we define the output fully connected network as follows:

最后，输出全连接网络定义为：

\displaystyle O({\bm{a}}_{i}) \\ \displaystyle=\operatorname{ReLU}\left({\bm{a}}_{i}W_{1}+b_{1}\right)W_{2}\cdot+b_{2} \tag{FF}

W_{1}\in\mathbb{R}^{d\times q}

W_{1}\in\mathbb{R}^{d\times q}

[a,b)_{\delta}=\{a,a+\delta,\dots,a+\lfloor\frac{b-a}{\delta}\rfloor\cdot\delta\}

[a,b)_{\delta}=\{a,a+\delta,\dots,a+\lfloor\frac{b-a}{\delta}\rfloor\cdot\delta\}

A.2 Proof

A.2 证明

In this section, we will present the full proof of theorem 1. The proof will contain three parts. The first and the third part will largely follow standard techniques. The main innovation lies is in the second part.

本节给出定理 1 的完整证明。证明分三部分：第一、第三部分大体沿用标准技术；主要创新在第二部分。

\mathcal{F}_{CD}

\mathcal{F}_{CD}

f\in\mathcal{F}_{CD}

f\in\mathcal{F}_{CD}

\bar{f}(X)=\sum_{P\in\mathbb{G}_{\delta}}f(P)\cdot\mathbf{1}\left[\|\operatorname{ReLU}(X-P)\|_{\infty}\leq\delta\right]

E

E

E=\begin{bmatrix}0&0&0&\dots&0\\delta^{-d}&\delta^{-d}&\delta^{-d}&\dots&\delta^{-d}\\delta^{-2d}&\delta^{-2d}&\delta^{-2d}&\dots&\delta^{-2d}\\vdots\\delta^{-(n-1)d}&\delta^{-(n-1)d}&\delta^{-(n-1)d}&\dots&\delta^{-(n-1)d}\\end{bmatrix}

g(X)=f(X-E)

g(X)=f(X-E)

\mathbf{G}^{E}_{\delta}:=[0,1]_{\delta}^{d}\times[\delta^{-d},\delta^{-d}+1]_{\delta}^{d}\times\dots\times[\delta^{-(n-1)d},\delta^{-(n-1)d}+1]_{\delta}^{d}.

\bar{f}:\mathbf{G}^{E}_{\delta}\to\mathbb{R}^{n\times d}

\bar{f}:\mathbf{G}^{E}_{\delta}\to\mathbb{R}^{n\times d}

\bar{f}(X)=\sum_{P\in\mathbf{G}^{E}_{\delta}}f(P-E)\cdot\mathbf{1}\left[\|\operatorname{ReLU}(X-P)\|_{\infty}\leq\delta\right].

0

X\in\mathbb{R}^{(n+1)\times(d+1)}

(X,x_{i})

(X,x_{i})

q:\mathbf{G}^{E}_{\delta}\to\mathbb{R}^{n}

q:\mathbf{G}^{E}_{\delta}\to\mathbb{R}^{n}

P\in\mathbf{G}^{E}_{\delta}

P\in\mathbf{G}^{E}_{\delta}

P,P^{\prime}\in\mathbf{G}^{E}_{\delta}

P,P^{\prime}\in\mathbf{G}^{E}_{\delta}

The key technical novelty of the proof is computing a contextual mapping using only the sparse attention mechanism. We create a “selective shift” operator which only shifts entries of a vector that lie in a certain range. We will use this shift operator strategically to ensure that we attain a contextual mapping at the end of the process. The lemma below, which is based on parts of the proof of Lemma 6 of [104], states that we can implement a suitable “selective” shift operator using a sparse attention mechanism.

证明的关键技术新颖之处在于：只用稀疏注意力机制计算上下文映射。我们构造「选择性移位」算子，只移动落在某范围内的向量分量；再策略性地使用该算子，最终得到上下文映射。下述引理基于 [104] 引理 6 证明的部分内容，说明可用稀疏注意力实现合适的「选择性」移位算子。

\psi:\mathbb{R}^{(n+1)\times(d+1)}\times\mathbb{R}^{2}\to\mathbb{R}^{(n+1)\times 1}

\psi:\mathbb{R}^{(n+1)\times(d+1)}\times\mathbb{R}^{2}\to\mathbb{R}^{(n+1)\times 1}

\psi_{u}(Z;b_{1},b_{2}){i}=\begin{cases}(\max{j\in N(i)}u^{T}Z_{j}-\min_{j\in N(i)}u^{T}Z_{j})e_{1}&\text{ if }b_{1}\leq u^{T}Z_{j}\leq b_{2}\0&\text{ else. }\end{cases}

e_{1}\in R^{d+1}

e_{1}\in R^{d+1}

Proof. Consider the function , which can be implemented by a sparse attention mechanism :

证明。 考虑可由稀疏注意力机制实现的函数：

\tilde{\psi}(X,b)_{i}=\sigma_{H}\Big[(u^{T}\cdot X_{i})^{T}\cdot(u^{T}X_{N(i)}-b1_{N(i)}^{T})e^{(1)}(u^{T}X_{N(i)})\Big]

X

X

D

D

\tilde{\psi}(Z;b){i}=\begin{cases}(\max{j\in N(i)}u^{T}Z_{j})e_{1}&\text{ if }u^{T}Z_{j}>b\(\min_{j\in N(i)}u^{T}Z_{j})e_{1}&\text{ if }u^{T}Z_{j}<b\\end{cases}

\tilde{\psi}(Z;b_{Q})-\tilde{\psi}(Z;b_{Q^{\prime}})

\tilde{\psi}(Z;b_{Q})-\tilde{\psi}(Z;b_{Q^{\prime}})

\psi(Z;b_{1},b_{2}){i}=\begin{cases}(\max{j\in N(i)}u^{T}Z_{j}-\min_{j\in N(i)}u^{T}Z_{j})e_{1}&\text{ if }b_{1}\leq u^{T}Z_{j}\leq b_{2}\0&\text{ else }\end{cases}

∎

The following lemma, which is the heart of the proof, uses the above selective shift operators to construct contextual mappings.

下述引理是证明的核心：用上述选择性移位算子构造上下文映射。

g_{c}:\mathbb{R}^{(n+1)\times(d+1)}\to\mathbb{R}^{(n+1)}

g_{c}:\mathbb{R}^{(n+1)\times(d+1)}\to\mathbb{R}^{(n+1)}

u\in\mathbb{R}^{d+1}=[1,\delta^{-1},\delta^{-2},\dots,\delta^{-d+1},\delta^{-nd}]

u\in\mathbb{R}^{d+1}=[1,\delta^{-1},\delta^{-2},\dots,\delta^{-d+1},\delta^{-nd}]

1,\dots,n

1,\dots,n

i\in\{0,1,\dots,n\}

i\in\{0,1,\dots,n\}

\displaystyle\delta^{-(i-1)d} \\ \displaystyle\leq\left\langle u,X_{i}\right\rangle\leq\delta^{-id}-\delta\qquad\text{ for all }i\in[n] \\ \displaystyle\delta^{-(n+1)d} \\ \displaystyle=\left\langle u,X_{0}\right\rangle

l_{i}

l_{i}

i\in\{1,\dots,n\}

i\in\{1,\dots,n\}

X\leftarrow X+\delta^{-d}\psi\left(X,v-\delta/2,v+\delta/2\right)

v\in[\delta^{-id}),\delta^{-(i+1)d})_{\delta}

v\in[\delta^{-id}),\delta^{-(i+1)d})_{\delta}

X\leftarrow X+\delta^{-nd}\cdot\psi\left(X,v-\delta/2,v+\delta/2\right)

v\in[S_{i},T_{i})_{\delta}

v\in[S_{i},T_{i})_{\delta}

i

i

k\in\{0,1,\dots,n\}

k\in\{0,1,\dots,n\}

\displaystyle T_{k} \\ \displaystyle=(\delta^{-(n+1)d}+1)^{k}\cdot\delta^{-nd}-\sum_{t=2}^{k}(\delta^{-(n+1)d}+1)^{k-t}(2\delta^{-nd-d}+\delta^{-nd}+1)\delta^{-td} \\ \displaystyle\qquad-(\delta^{-(n+1)d}+1)^{k-1}(\delta^{-nd-d}+\delta^{-nd})\delta^{-d}-\delta^{-(k+1)d} \tag{UP}

\displaystyle S_{k} \\ \displaystyle=(\delta^{-(n+1)d}+1)^{k}\cdot\delta^{-nd}-\sum_{t=2}^{k}(\delta^{-(n+1)d}+1)^{k-t}(2\delta^{-nd-d}+\delta^{-nd}+1)\delta^{-(t-1)d} \\ \displaystyle\qquad-(\delta^{-(n+1)d}+1)^{k-1}(\delta^{-nd-d}+\delta^{-nd})-\delta^{-kd} \tag{LP}

k

k

S_{k}<\tilde{f}^{k}_{0}<T_{k}

k\in\{0,1,\dots,n\}

T_{k-1}\leq f_{k}<S_{k}

k^{th}

k

k=0

k=0

k=1

k=1

[\delta^{-(k-1)d},\delta^{-kd})_{\delta}

[\delta^{-(k-1)d},\delta^{-kd})_{\delta}

\displaystyle l_{k}+1<l_{k+2}\dots<l_{n}<f_{1}<f_{2}<\dots<\tilde{f}_{0}^{k-1}<f_{k} \tag{2}

[S_{k-1},T_{k-1})_{\delta}

[S_{k-1},T_{k-1})_{\delta}

\displaystyle\tilde{f}_{0}^{k} \\ \displaystyle=\delta^{-nd}\cdot(f_{k}-l_{k+1})+\tilde{f}_{0}^{k-1} \\ \displaystyle=\delta^{-nd}\cdot(\delta^{-d}(\tilde{f}_{0}^{k-1}-l_{k})+l_{k}-l_{k+1})+\tilde{f}_{0}^{k-1} \\ \displaystyle=\delta^{-(n+1)d}\cdot(\tilde{f}_{0}^{k-1}-l_{k})+\delta^{-nd}(l_{k}-l_{k+1})+\tilde{f}_{0}^{k-1} \\ \displaystyle=(\delta^{-(n+1)d}+1)\tilde{f}_{0}^{k-1}-(\delta^{-nd-d}+\delta^{-nd})l_{k}-l_{k+1} \\ \displaystyle=(\delta^{-(n+1)d}+1)^{k}\cdot\tilde{f}_{0}^{0}-\sum_{t=2}^{k}(\delta^{-(n+1)d}+1)^{k-t}(2\delta^{-nd-d}+\delta^{-nd}+1)l_{t} \\ \displaystyle\qquad-(\delta^{-(n+1)d}+1)^{k-1}(\delta^{-nd-d}+\delta^{-nd})l_{1}-l_{k+1}

\tilde{f}_{0}^{0}=\delta^{-nd}

\tilde{f}_{0}^{0}=\delta^{-nd}

S_{k}\leq\tilde{f}_{0}^{k}<T_{k}

S_{k}\leq\tilde{f}_{0}^{k}<T_{k}

n

n

\bar{f}

\bar{f}

g_{c}

g_{c}

g_{v}^{tkn}(g_{c}(L)_{j})=f(L)_{j}

\sigma_{H}

\sigma_{H}

g\in\bar{\mathcal{T}}^{2,1,1}

g\in\bar{\mathcal{T}}^{2,1,1}

Combining the above lemma with the Lemma 3, we get our main result:

把上述引理与引理 3 合在一起，得到主结果：

1\leq p\leq\infty

1\leq p\leq\infty

Since the sparsity graph associated with BigBird contains a star network, we know that it can express any continuous function from a compact domain.

由于 BigBird 对应的稀疏图含星形网络，可知它能表达紧致定义域上的任意连续函数。

Contemporary work on Universal Approximability of Sparse Transformers We would like to note that, contemporary work done by Yun et al. 2020, also parallelly explored the ability of sparse transformers with linear connections to capture sequence-to-sequence functions on the compact domain.

关于稀疏 Transformer 通用逼近性的同期工作 顺带指出：Yun 等人 2020 的同期工作也并行探讨了带线性连接的稀疏 Transformer 在紧致定义域上刻画序列到序列函数的能力。

Appendix B Turing Completeness

附录 B 图灵完备性

In this section, we will extend our results to the setting of Pérez et al. 2019. Our exposition will largely use their proof structure but we will make a few changes. We repeat some of the lemmas with the amendments to make the exposition self-contained.

本节把结果推广到 Pérez 等人 2019 的设定。叙述大体沿用他们的证明结构，但会做若干改动。我们重述部分引理并写明修正，以使论证自洽。

B.1 Notation

B.1 记号

({\bm{K}}^{\textbf{e}}\in\mathbb{R}^{n\times m},{\bm{V}}^{\textbf{e}}\in\mathbb{R}^{n\times d})

({\bm{K}}^{\textbf{e}}\in\mathbb{R}^{n\times m},{\bm{V}}^{\textbf{e}}\in\mathbb{R}^{n\times d})

{\bm{Y}}_{j}

{\bm{Y}}_{j}

({\bm{p}}_{1},...,{\bm{p}}_{j})

({\bm{p}}_{1},...,{\bm{p}}_{j})

O

O

i

\operatorname{Dec}({\bm{Y}}_{j};{\bm{K}}^{\textbf{e}},{\bm{V}}^{\textbf{e}})

\displaystyle{\bm{z}}_{i} \\ \displaystyle=O({\bm{a}}_{i})+{\bm{a}}_{i} \\ \displaystyle{\bm{a}}_{i} \\ \displaystyle=\textsc{CrossAttn}({\bm{p}}_{i},{\bm{K}}^{\textbf{e}},{\bm{V}}^{\textbf{e}})+{\bm{p}}_{i} \\ \displaystyle{\bm{p}}_{i} \\ \displaystyle=\textsc{Attn}_{D}({\bm{Y}}_{j})_{i}+{\bm{y}}_{i} \tag{3}

\textsc{Attn}_{D}

\textsc{Attn}_{D}

\displaystyle\textsc{CrossAttn}({\bm{Y}}_{j})_{i} \\ \displaystyle=\sum_{h=1}^{H}\sigma\left(({\bm{y}}_{i}W_{Q}^{h})({\bm{K}}^{(e)}W_{K}^{h})^{T}\right)\cdot({\bm{V}}^{(e)}W_{V}^{h}) \tag{6}

W_{Q}^{h},W_{K}^{h},W_{V}^{h}\in\mathbb{R}^{d\times m}

h=1,\ldots H

M=(Q,\Sigma,\delta,q_{init},F)

M=(Q,\Sigma,\delta,q_{init},F)

\displaystyle q^{(j)} \\ \displaystyle:\text{ state of Turing machine }M\text{ at time }j. \\ \displaystyle s^{(j)} \\ \displaystyle:\text{ symbol under the head of }M\text{ at time }j. \\ \displaystyle v^{(j)} \\ \displaystyle:\text{ symbol written by }M\text{ at time }j. \\ \displaystyle m^{(j)} \\ \displaystyle:\text{ head direction in the transition of }M\text{ at time }j.

s\in\Sigma

s\in\Sigma

\begin{array}[]{rcllr}{\bm{v}}&=&[&{\bm{q}}{1},{\bm{s}}{1},x_{1},\&&&{\bm{q}}{2},{\bm{s}}{2},x_{2},x_{3},x_{4},x_{5},x_{6},\&&&{\bm{s}}{3},x{7},{\bm{s}}{4},\&&&x{8},x_{9},x_{10},x_{11},x_{12},x_{13},x_{14},x_{15},x_{16}&]\end{array}

{\bm{q}}_{i}\in\mathbb{Q}^{|Q|}

{\bm{q}}_{i}\in\mathbb{Q}^{|Q|}

B.2 Details of the Simulation

B.2 模拟细节

In this section, we give more details on the architecture of the encoder and decoder needed to implement our simulation strategy.

本节更细致地给出实现模拟策略所需的编码器与解码器架构。

Figure 2: Mapping between transformer step and original Turing machine step.

图 2：Transformer 步与原图灵机步之间的对应。

M

M

O(n)

O(n)

{\bm{K}}^{(e)}

{\bm{K}}^{(e)}

D

D

\displaystyle\left(\frac{j(j+1)}{2}+k,\frac{k(k+1)}{2}\right)\text{ and } \\ \displaystyle\left(\frac{j(j+1)}{2}+k,\frac{j(j+1)}{2}+k\right)\text{ if }k>1\text{ else }\left(\frac{j(j+1)}{2}+1,\frac{j(j+1)}{2}\right).

This graph can be seen as a special case of BigBird where first type of edges are realizations of random and second type of edges correspond to locality. Also note that this graph satisfies the left-to-right constraint of decoder, i.e. no node attends to a node in the future.

该图可看作 BigBird 的特例：第一类边是随机边的实现，第二类边对应局部性。同时注意该图满足解码器的从左到右约束，即任何节点都不关注未来节点。

\operatorname{pos}_{\operatorname{Dec}}:\mathbb{N}\to\mathbb{Q}^{d}

\operatorname{pos}_{\operatorname{Dec}}:\mathbb{N}\to\mathbb{Q}^{d}

\begin{array}[]{rcllr}\operatorname{pos}_{\operatorname{Dec}}(i)&=&[&0,\ldots,0,\&&&0,\ldots,0,\&&&0,\ldots,0,\&&&1,g(i)+1,\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},h(i),0,0,0,0&]\end{array}

g(i)=\left\lfloor\frac{-1+\sqrt{1+8i}}{2}\right\rfloor

g(i)=\left\lfloor\frac{-1+\sqrt{1+8i}}{2}\right\rfloor

{\bm{y}}_{1},{\bm{y}}_{2},\ldots

{\bm{y}}_{1},{\bm{y}}_{2},\ldots

\begin{array}[]{rcllr}{{\bm{y}}}{i}&=&[&\llbracket\ q^{g(i)}\ \rrbracket,\llbracket\ s^{g(i)}\ \rrbracket,c^{g(i)},\&&&0,\ldots,0,\&&&{\bm{0}}{s},0,\llbracket\ w^{(i)}\ \rrbracket,\&&&0,0,0,0,0,u_{1}^{(i)},u_{2}^{(i)},u_{3}^{(i)},u_{4}^{(i)}&]\end{array}

i

i

We consider as the starting vector for the decoder the vector

我们取解码器起始向量为

\begin{array}[]{rcllr}{{\bm{y}}}{1}&=&[&\llbracket\ q{\text{init}}\ \rrbracket,\llbracket\ #\ \rrbracket,0,\&&&0,\ldots,0,\&&&0,\ldots,0,\&&&0,\ldots,0&]\end{array}

c^{(0)}=0

c^{(0)}=0

{\bm{y}}_{1},\ldots,{\bm{y}}_{r}

{\bm{y}}_{1},\ldots,{\bm{y}}_{r}

{\bm{y}}_{1}+\operatorname{pos}_{\operatorname{Dec}}(1),\ {\bm{y}}_{2}+\operatorname{pos}_{\operatorname{Dec}}(2),\ \ldots,\ {\bm{y}}_{r}+\operatorname{pos}_{\operatorname{Dec}}(r).

\overline{{\bm{y}}}_{i}

\overline{{\bm{y}}}_{i}

\begin{array}[]{rcllr}\overline{{\bm{y}}}{i}&=&[&\llbracket\ q^{g(i)}\ \rrbracket,\llbracket\ s^{g(i)}\ \rrbracket,c^{g(i)},\&&&0,\ldots,0,\&&&{\bm{0}}{s},0,\llbracket\ w^{(i)}\ \rrbracket,\&&&1,g(i)+1,\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},h(i),u_{1}^{(i)},u_{2}^{(i)},u_{3}^{(i)},u_{4}^{(i)}&]\end{array}

M

M

{\bm{p}}^{1}_{i}

{\bm{p}}^{1}_{i}

\begin{array}[]{rcllr}\textsc{CrossAttn}({\bm{p}}^{1}{i},{\bm{K}}^{\textbf{e}},{\bm{V}}^{\textbf{e}})&=&[&0,\ldots,0,\&&&0,\ldots,0,\&&&\llbracket\ \alpha^{g(i)+1}\ \rrbracket,\beta^{g(i)+1},{\bm{0}}{s},\&&&0,\ldots,0&]\end{array}

\alpha

\alpha

\begin{array}[]{rcllr}{\bm{a}}^{1}{i}&=&&\textsc{CrossAttn}({\bm{p}}^{1}{i},{\bm{K}}^{\textbf{e}},{\bm{V}}^{\textbf{e}})+{\bm{p}}^{1}{i}\&=&[&\llbracket\ q^{g(i)}\ \rrbracket,\llbracket\ s^{g(i)}\ \rrbracket,c^{g(i)},\&&&0,\ldots,0,\&&&\llbracket\ \alpha^{g(i)+1}\ \rrbracket,\beta^{g(i)+1},\llbracket\ w^{(i)}\ \rrbracket,\&&&1,g(i)+1,\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},h(i),u{1}^{(i)},u_{2}^{(i)},u_{3}^{(i)},u_{4}^{(i)}&]\end{array} \tag{7}

O_{1}(\cdot)

O_{1}(\cdot)

O_{1}:\mathbb{Q}^{d}\to\mathbb{Q}^{d}

O_{1}:\mathbb{Q}^{d}\to\mathbb{Q}^{d}

\begin{array}[]{rcllr}O_{1}({\bm{a}}^{1}_{i})&=&[&0,\ldots,0,\&&&\llbracket\ q^{g(i)+1}\ \rrbracket,\llbracket\ v^{g(i)}\ \rrbracket,m^{g(i)},0,0,0,0\&&&0,\ldots,0,\&&&0,\ldots,0&]\end{array}

O_{1}(\cdot)

O_{1}(\cdot)

Thus, finally the output of the first decoder layer is

于是第一解码层的最终输出为

\begin{array}[]{rcllr}{\bm{z}}^{1}{i}=O{1}({\bm{a}}^{1}{i})+{\bm{a}}^{1}{i}&=&[&\llbracket\ q^{g(i)}\ \rrbracket,\llbracket\ s^{g(i)}\ \rrbracket,c^{g(i)},\&&&\llbracket\ q^{g(i)+1}\ \rrbracket,\llbracket\ v^{g(i)}\ \rrbracket,m^{g(i)},0,0,0,0,\&&&\llbracket\ \alpha^{g(i)+1}\ \rrbracket,\beta^{g(i)+1},\llbracket\ w^{(i)}\ \rrbracket,\&&&1,g(i)+1,\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},h(i),u_{1}^{(i)},u_{2}^{(i)},u_{3}^{(i)},u_{4}^{(i)}&]\end{array}

{\bm{a}}_{i}^{2}={\bm{p}}_{i}^{2}={\bm{z}}_{i}^{1}

{\bm{a}}_{i}^{2}={\bm{p}}_{i}^{2}={\bm{z}}_{i}^{1}

\begin{array}[]{rcllr}{\bm{z}}^{2}{i}\ =\ O{2}({\bm{a}}^{2}{i})+{\bm{a}}^{2}{i}&=&[&\llbracket\ q^{g(i)}\ \rrbracket,\llbracket\ s^{g(i)}\ \rrbracket,c^{g(i)},\&&&\llbracket\ q^{g(i)+1}\ \rrbracket,\llbracket\ v^{g(i)}\ \rrbracket,c^{g(i)+1},\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},\frac{c^{g(i)+1}}{g(i)+1},\frac{c^{g(i)}}{g(i)+1},\&&&\llbracket\ \alpha^{g(i)+1}\ \rrbracket,\beta^{g(i)+1},\llbracket\ w^{(i)}\ \rrbracket,\&&&1,g(i)+1,\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},h(i),u_{1}^{(i)},u_{2}^{(i)},u_{3}^{(i)},u_{4}^{(i)}&]\end{array}

{\bm{a}}_{i}^{3}={\bm{p}}_{i}^{3}={\bm{z}}_{i}^{2}

{\bm{a}}_{i}^{3}={\bm{p}}_{i}^{3}={\bm{z}}_{i}^{2}

O([{\bm{x}},{\bm{y}},{\bm{z}},b]))=\begin{cases}[{\bm{0}},{\bm{0}},{\bm{0}},0]&\text{if }b=1,\[{\bm{0}},{\bm{z}}-{\bm{y}},-{\bm{z}},0]&\text{if }b=0.\end{cases}

h(i)

h(i)

\begin{array}[]{rcllr}{\bm{z}}^{3}{i}\ =\ O{3}({\bm{a}}^{3}{i})+{\bm{a}}^{3}{i}&=&[&0,\ldots,0,\&&&\llbracket\ \hat{q}^{(i)}\ \rrbracket,\llbracket\ \hat{v}^{(i)}\ \rrbracket,\hat{c}^{(i)},\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},\frac{c^{g(i)+1}}{g(i)+1},\hat{u}{4}^{(i)},\&&&\llbracket\ \hat{\alpha}^{(i)}\ \rrbracket,\hat{\beta}^{(i)},{\bm{0}}{s},\&&&1,\hat{u}{1}^{(i)},\hat{u}{2}^{(i)},\hat{u}_{3}^{(i)},h(i),0,0,0,0&]\end{array}

h(i)

h(i)

• We copy the input state and head position as is for intermediate nodes. We do not need to transition to next Turing machine states in these nodes.

• 对中间节点，原样复制输入状态与磁头位置。这些节点上不需要转移到下一图灵机状态。

\hat{q}^{(i)}=\begin{cases}q^{g(i)+1}&\text{if }h(i)=1\\ q^{g(i)}&\text{if }h(i)=0\end{cases}

\hat{q}^{(i)}=\begin{cases}q^{g(i)+1}&\text{若 }h(i)=1\\ q^{g(i)}&\text{若 }h(i)=0\end{cases}

\alpha

\alpha

\hat{\alpha}^{(i)}=\begin{cases}\alpha^{g(i)+1}&\text{if }h(i)=1\\ s^{g(i)}&\text{if }h(i)=0\end{cases}

\hat{\alpha}^{(i)}=\begin{cases}\alpha^{g(i)+1}&\text{若 }h(i)=1\\ s^{g(i)}&\text{若 }h(i)=0\end{cases}

w

w

\hat{u}_{1}^{(i)}=\begin{cases}g(i)+1&\text{if }h(i)=1\\ u_{1}^{(i)}&\text{if }h(i)=0\end{cases}

$\hat{u}_{1}^{(i)}=\begin{cases}g(i)+1&\text{if }h(i)=1\\ u_{1}^{(i)}&\text{if }h(i)=0\end{cases}$ ,		$\hat{u}_{2}^{(i)}=\begin{cases}\frac{1}{(g(i)+1)}&\text{if }h(i)=1\\ u_{2}^{(i)}&\text{if }h(i)=0\end{cases}$ ,
$\hat{u}_{3}^{(i)}=\begin{cases}\frac{1}{(g(i)+1)^{2}}&\text{if }h(i)=1\\ u_{3}^{(i)}&\text{if }h(i)=0\end{cases}$ ,		$\hat{u}_{4}^{(i)}=\begin{cases}\frac{c^{g(i)}}{g(i)+1}&\text{if }h(i)=1\\ u_{4}^{(i)}&\text{if }h(i)=0\end{cases}$ .

\hat{u}_{1}^{(i)}=\begin{cases}g(i)+1&\text{若 }h(i)=1\\ u_{1}^{(i)}&\text{若 }h(i)=0\end{cases}

$\hat{u}_{1}^{(i)}=\begin{cases}g(i)+1&\text{若 }h(i)=1\\ u_{1}^{(i)}&\text{若 }h(i)=0\end{cases}$ ，		$\hat{u}_{2}^{(i)}=\begin{cases}\frac{1}{(g(i)+1)}&\text{若 }h(i)=1\\ u_{2}^{(i)}&\text{若 }h(i)=0\end{cases}$ ，
$\hat{u}_{3}^{(i)}=\begin{cases}\frac{1}{(g(i)+1)^{2}}&\text{若 }h(i)=1\\ u_{3}^{(i)}&\text{若 }h(i)=0\end{cases}$ ，		$\hat{u}_{4}^{(i)}=\begin{cases}\frac{c^{g(i)}}{g(i)+1}&\text{若 }h(i)=1\\ u_{4}^{(i)}&\text{若 }h(i)=0\end{cases}$ 。

g(i+1)=g(i)

h(i)=0

\begin{array}[]{rcllr}{\bm{z}}^{3}{i}&=&[&0,\ldots,0,\&&&\llbracket\ {q}^{g(i+1)}\ \rrbracket,\llbracket\ \hat{v}^{(i)}\ \rrbracket,{c}^{g(i+1)},\frac{1}{g(i)+1},\frac{1}{(g(i)+1)^{2}},\frac{c^{g(i)+1}}{g(i)+1},\hat{u}{4}^{(i)},\&&&\llbracket\ \hat{\alpha}^{(i)}\ \rrbracket,\hat{\beta}^{(i)},{\bm{0}}{s},\&&&1,\hat{u}{1}^{(i)},\hat{u}{2}^{(i)},\hat{u}{3}^{(i)},h(i),0,0,0,0&]\end{array}

c^{g(i)+1}

c^{g(i)+1}

\forall i

i

\begin{array}[]{rcllr}Q_{4}({\bm{z}}^{3}_{i})&=&[&0,\ldots,0\&&&0,\ldots,0,\&&&0,\ldots,0,\&&&0,\frac{c^{g(i)+1}}{g(i)+1},\frac{1}{g(i)+1},\frac{1}{3(g(i)+1)^{2}},0,0,0,0,0&]\\end{array}

\begin{array}[]{rcllr}K_{4}({\bm{z}}^{3}{i})&=&[&0,\ldots,0\&&&0,\ldots,0,\&&&0,\ldots,0,\&&&0,\hat{u}{2}^{(i)},\hat{u}{4}^{(i)},\hat{u}{3}^{(i)},0,0,0,0,0&]\V_{4}({\bm{z}}^{3}{i})&=&[&0,\ldots,0,\&&&0,\ldots,0,\&&&{\bm{0}}{s},0,\llbracket\ \hat{v}^{(i)}\ \rrbracket,\&&&0,0,0,0,0,\hat{u}{1}^{(i)},\hat{u}{2}^{(i)},\hat{u}{3}^{(i)},\hat{u}{4}^{(i)}&]\end{array}

It is clear that the three functions are linear transformations and thus they can be defined by feed-forward networks. Notice that the query vector is always formed using current time step position embedding, whereas key and value vectors are formed using copied over entries for intermediate nodes and using current entries only for compute node.

显然这三个函数都是线性变换，因而可由前馈网络定义。注意：query 向量总由当前时间步的位置嵌入构成；而 key 与 value 在中间节点上用复制过来的条目，在计算节点上才用当前条目。

v^{l(j+1)}

v^{l(j+1)}

m(t)=\argmin_{m\in\{0,...,t\}}\chi_{t}^{j}=\argmin_{m\in\{0,...,t\}}|\langle Q_{4}({\bm{z}}_{j}^{3}),K_{4}({\bm{z}}_{m}^{3})\rangle|

m(j)

m(j)

D

D

w^{(j(j+1)/2+k+1)}=\hat{v}^{m(k-1)}

u

u

\begin{array}[]{rcllr}{\bm{p}}^{4}{i}&=&&\textsc{Attn}{D}({\bm{Z}}{i}^{3})+{\bm{z}}^{3}{i}\&=&[&0,\ldots,0,\&&&\llbracket\ q^{g(i+1)}\ \rrbracket,\llbracket\ \hat{v}^{(i)}\ \rrbracket,c^{g(i+1)},0,\frac{c^{g(i)+1}}{g(i)+1},\hat{u}{4}^{(i)},\&&&\llbracket\ \hat{\alpha}^{(i)}\ \rrbracket,\hat{\beta}^{(i)},\llbracket\ w^{(i+1)}\ \rrbracket,\&&&1,\hat{u}{1}^{(i)},\hat{u}{2}^{(i)},\hat{u}{3}^{(i)},h(i),{u}{1}^{(i+1)},{u}{2}^{(i+1)},{u}{3}^{(i+1)},{u}{4}^{(i+1)}&]\end{array} \tag{8}

{\bm{z}}_{i}^{4}={\bm{a}}_{i}^{4}={\bm{p}}_{i}^{4}

{\bm{z}}_{i}^{4}={\bm{a}}_{i}^{4}={\bm{p}}_{i}^{4}

F(\cdot)

F(\cdot)

F:\mathbb{Q}^{d}\to\mathbb{Q}^{d}

F:\mathbb{Q}^{d}\to\mathbb{Q}^{d}

\begin{array}[]{rcllr}F({\bm{z}}^{4}{r})&=&[&\llbracket\ q^{g(r+1)}\ \rrbracket,\llbracket\ s^{g(r+1))}\ \rrbracket,c^{g(r+1)},\&&&0,\ldots,0,\&&&{\bm{0}}{s},0,\llbracket\ w^{(r+1)}\ \rrbracket,\&&&0,0,0,0,0,{u}{1}^{(r+1)},{u}{2}^{(r+1)},{u}{3}^{(r+1)},{u}{4}^{(r+1)}]\&=&&{\bm{y}}_{r+1}\end{array}

w,u_{1},u_{2},u_{3}

w,u_{1},u_{2},u_{3}

Appendix C Limitations

附录 C 局限

O(1)

O(1)

n

n

n

n

Finding vectors that are furthest apart boils down to minimizing inner product search in case of unit vectors. For a full-attention mechanism with appropriate query and keys, this task is very easy as we can evaluate all pair-wise inner products.

找相距最远的向量在单位向量情形归结为最小化内积搜索。对带合适查询与键的全注意力，该任务很容易，因为可评估所有成对内积。

n

n

\epsilon>0

\epsilon>0

g\in\mathcal{T}_{D}^{H=O(d),m=O(d),q=O(d)}

D

g\in\mathcal{T}^{H=1,m=2d,q=0}

g\in\mathcal{T}^{H=1,m=2d,q=0}

Proof. We will break this proof into two parts:

证明。 我们将证明拆成两部分：

O(1)

O(1)

u_{i}

u_{i}

x_{i}:=E(u_{i})=[u_{i};0] \tag{9}

Step 2 Construct query, key, value functions as follows:

步骤 2 构造查询、键、值函数如下：

\displaystyle Q([a;b]) \\ \displaystyle=-a \\ \displaystyle K([a;b]) \\ \displaystyle=a \\ \displaystyle V([a;b]) \\ \displaystyle=[0;a]

\mathrm{Attn}(Q(x_{i}),K(X),V(X)=[0;u_{\argmax_{j}\langle-u_{i},u_{j}\rangle}]

\mathrm{Attn}(Q(x_{i}),K(X),V(X)=[0;u_{\argmax_{j}\langle-u_{i},u_{j}\rangle}]

a_{i}=\mathrm{Attn}(Q(x_{i}),K(X),V(X))+x_{i}=[u_{i};u_{\argmax_{j}\langle-u_{i},u_{j}\rangle}]=[u_{i};u_{i^{*}}] \tag{11}

O(a_{i})=0

O(a_{i})=0

O(n)

O(n)

\tilde{\Omega}(n^{1-\epsilon})

\tilde{\Omega}(n^{1-\epsilon})

g\in\mathcal{T}_{D}^{H=O(d),m=O(d),q=O(d)}

l

\displaystyle a_{i} \\ \displaystyle=\textsc{Attn}_{D}(Q(x_{i}),K(X_{N(i)}),V(X_{N(i)})+x_{i} \\ \displaystyle x_{i} \\ \displaystyle=O(a_{i})+a_{i}

\mathrm{Attn}_{D}

\mathrm{Attn}_{D}

\tilde{O}(nd^{3})

\tilde{O}(nd^{3})

\tilde{O}(nld^{3})

\tilde{O}(nld^{3})

l=O(n^{1-\epsilon})

\epsilon>0

Appendix D Implementation details

附录 D 实现细节

We optimize the code for modern hardware. Hardware accelerators like GPUs and TPUs truly shine on coalesced memory operations which load blocks of contiguous bytes at once. Thus, its not very efficient to have small sporadic look-ups caused by a sliding window or random element queries. We alleviate this by “blockifying” the lookups.

我们针对现代硬件优化代码。GPU 与 TPU 等硬件加速器真正擅长合并内存操作——一次加载连续字节块。因此，由滑动窗口或随机元素查询引起的零星小查找并不高效。我们通过把查找「分块化」来缓解。

(a) Random Attention

(a) 随机注意力

A

A

12

12

=2

=2

r

r

j

j

g=1

g=1

The resulting overall attention matrix is shown in Figure 3(d). Unfortunately, simply trying to compute this attention score as multiplying arbitrary pairs of query and key vectors would require use of gather operation, which is inefficient. Upon closer examination of window and global attention, we observe that we can compute these attention scores without using a gather operation.

所得整体注意力矩阵见图 3(d)。不幸的是，若简单把任意查询-键向量对相乘来算注意力分数，需要 gather 操作，效率低。仔细考察窗口与全局注意力后，我们观察到可不使用 gather 计算这些注意力分数。

(a) Full all pair attention can be obtained by direct matrix multiplication between the query and key matrix. Groupings just shown for guidance.

(a) 完整成对注意力可由查询与键矩阵直接矩阵乘得到。分组仅为示意。

Figure 4: Idea behind fast sparse attention computation in BigBird.

图 4：BigBird 快速稀疏注意力计算的思路示意。

O(n^{2}d)

O(n^{2}d)

A_{jst}=\sum_{u}Q^{\prime}_{jsu}K^{\prime}_{jtu},\qquad j=0,1,...,\lceil n/b\rceil \tag{13}

A

\lceil n/b\rfloor\times b\times b

K^{\prime\prime}

\lceil n/b\rceil\times(g+w+r)b\times d

w

w

Figure 6: Overview of BigBird attention computation. Structured block sparsity helps in compactly packing our operations of sparse attention, thereby making our method efficient on GPU/TPU. On the left, we depict the transformed dense query and key tensors. The query tensor is obtained by simply blocking and reshaping while the final key tensor by concatenating three transformations: The first green columns, corresponding to global attention, is fixed. The middle blue columns correspond to window local attention and can be obtained by appropriately rolling as illustrated in Figure 5. For the final orange columns, corresponding to random attentions, we need to use computationally inefficient gather operation. Dense multiplication between the query and key tensors efficiently calculates the sparse attention pattern (except the first row-block, which is computed by direct multiplication), using the ideas illustrated in Figure 4. The resultant matrix on the right is same as that shown in Figure 3(d).

图 6：BigBird 注意力计算总览。结构化块稀疏有助于紧凑打包稀疏注意力运算，从而使我们的方法在 GPU/TPU 上高效。左侧描绘变换后的稠密查询与键张量。查询张量由简单分块与重塑得到；最终键张量由三种变换拼接：对应全局注意力的首组绿色列固定；中间蓝色列对应窗口局部注意力，可按图 5 适当滚动得到；对应随机注意力的末组橙色列需用计算上低效的 gather。查询与键张量的稠密乘法高效算出稀疏注意力模式（除第一行块由直接乘法计算外），思路见图 4。右侧所得矩阵与图 3(d) 相同。

Appendix E NLP experiments details

附录 E NLP 实验细节

E.1 MLM Pretraining

E.1 MLM 预训练

4096

4096

Similar to the norm, we trained a large version of model as well, which has 24 layers with 16 heads and hidden dimension of 1024. Following the observation from RoBERTa, we pretrain on a larger batch size of 2048 for this size. For BigBird-itc the block length was kept same as base size, but for BigBird-etc the block length was almost doubled to 169. All the remaining parameters were the same.

与惯例类似，我们也训练了大模型：24 层、16 头、隐维 1024。沿用 RoBERTa 的观察，该规模用更大的批大小 2048 预训练。BigBird-itc 的块长与 base 相同；BigBird-etc 的块长几乎加倍到 168。

b

Parameter	BigBird-itc	BigBird-etc
Block length, $b$	$64$	84
$\#$ of global token, $g$	$2\times b$	$256$
Window length, $w$	$3\times b$	$3\times b$
$\#$ of random token, $r$	$3\times b$	$0$
Max. sequence length	$4096$	$4096$
$\#$ of heads	$12$	$12$
$\#$ of hidden layers	$12$	$12$
Hidden layer size	$768$	$768$
Batch size	$256$	$256$
Loss	MLM	MLM
Activation layer	gelu	gelu
Dropout prob	$0.1$	$0.1$
Attention dropout prob	$0.1$	$0.1$
Optimizer	Adam	Adam
Learning rate	$10^{-4}$	$10^{-4}$
Compute resources	$8\times 8$ TPUv3	$8\times 8$ TPUv3

b

参数	BigBird-itc	BigBird-etc
块长 $b$	$64$	84
全局 token 数 $g$	$2\times b$	$256$
窗口长 $w$	$3\times b$	$3\times b$
随机 token 数 $r$	$3\times b$	$0$
最大序列长	$4096$	$4096$
头数	$12$	$12$
$\#$ of hidden layers	$12$	$12$
Hidden layer size	$768$	$768$
批大小	$256$	$256$
Loss	MLM	MLM
Activation layer	gelu	gelu
Dropout prob	$0.1$	$0.1$
注意力 Dropout prob	$0.1$	$0.1$
Optimizer	Adam	Adam
Learning rate	$10^{-4}$	$10^{-4}$
Compute resources	$8\times 8$ TPUv3	$8\times 8$ TPUv3

\#

Dataset	$\#$ tokens	Avg. doc len.
Books [110]	$1.0$ B	$37$ K
CC-News [34]	$7.4$ B	$561$
Stories [89]	$7.7$ B	$8.2$ K
Wikipedia	$3.1$ B	$592$

Model	Base	Large
RoBERTa (sqln: 512)	1.846	1.496
Longformer (sqln: 4096)	1.705	1.358
BigBird-itc (sqln: 4096)	1.678	1.456
BigBird-etc (sqln: 4096)	1.611	1.274

\#

数据集	$\#$ token 数	平均文档长
Books [110]	$1.0$ B	$37$ K
CC-News [34]	$7.4$ B	$561$
Stories [89]	$7.7$ B	$8.2$ K
Wikipedia	$3.1$ B	$592$

模型	Base	Large
RoBERTa (sqln: 512)	1.846	1.496
Longformer (sqln: 4096)	1.705	1.358
BigBird-itc (sqln: 4096)	1.678	1.456
BigBird-etc (sqln: 4096)	1.611	1.274

90447

	Instances
Dataset	Training	Dev	Median	Max
HotpotQA-distractor [100]	$90447$	$7405$	$1227$	$3560$
Natural Questions [52]	$307373$	$7830$	$3258$	$77962$
TriviaQA [41]	$61888$	$7993$	4900	32755
WikiHop [95]	$43738$	$5129$	$1541$	$20337$

90447

	样本数
数据集	训练	开发	中位	最大
HotpotQA-distractor [100]	$90447$	$7405$	$1227$	$3560$
Natural Questions [52]	$307373$	$7830$	$3258$	$77962$
TriviaQA [41]	$61888$	$7993$	4900	32755
WikiHop [95]	$43738$	$5129$	$1541$	$20337$

\#

Parameter		HotpotQA		NaturalQ		TriviaQA		WikiHop
Global token location		itc	etc		itc	etc		itc	etc	itc	etc
$\#$ of global token, $g$		$128$	$256$		$128$	$230$		$128$	$320$	$128$	$430$
Window length, $w$		$192$	$252$		$192$	$252$		$192$	$252$	$192$	$252$
$\#$ of random token, $r$		$192$	$0$		$192$	$0$		$192$	$0$	$192$	$0$
Max. sequence length		$4096$	$4096$		$4096$	$4096$		$4096$	$4096$	$4096$	$4096$
$\#$ of heads		$12$	$12$		$12$	$12$		$12$	$12$	$12$	$12$
$\#$ of hidden layers		$12$	$12$		$12$	$12$		$12$	$12$	$12$	$12$
Hidden layer size		$768$	$768$		$768$	$768$		$768$	$768$	$768$	$768$
Batch size		$32$	$32$		$128$	$128$		$32$	$32$	$64$	$64$
Loss		cross-entropy		cross-entropy		cross-entropy		cross-entropy
	golden spans		golden spans		noisy spans [18]		ans choices
Compute resources		$4\times 2$ TPUv3		$4\times 8$ TPUv3		$4\times 2$ TPUv3		$4\times 4$ TPUv3

g

\#

Parameter	HotpotQA	NaturalQ	TriviaQA	WikiHop
Global token location	etc	etc	etc	etc
$\#$ of global token, $g$	$256$	$230$	$320$	$430$
Window length, $w$	$507$	$507$	$507$	$507$
$\#$ of random token, $r$	$0$	$0$	$0$	$0$
Max. sequence length	$4096$	$4096$	$4096$	$4096$
$\#$ of heads	$16$	$16$	$16$	$16$
$\#$ of hidden layers	$24$	$24$	$24$	$24$
Hidden layer size	$1024$	$1024$	$1024$	$1024$
Batch size	$32$	$64$	$32$	$64$
Loss	cross-entropy	cross-entropy	cross-entropy	cross-entropy
Num epochs	$\{5,9\}$	$\{3,5\}$	$\{3,5\}$	$\{5,10\}$
Optimizer	Adam	Adam	Adam	LAMB
Learning rate	$3\times 10^{-5}$	$\{5,10\}\times 10^{-5}$	$\{3,5\}\times 10^{-5}$	$\{2,5\}\times 10^{-5}$
Compute resources	$4\times 4$ TPUv3	$4\times 8$ TPUv3	$4\times 4$ TPUv3	$4\times 8$ TPUv3

g

E.2 Question Answering

E.2 问答

The detailed statistics of the four datasets used are given in Table 11. All the hyperparameters for BigBird, used for creating Table 2 are shown in Table 12 and those submitted to get Table 3 are shown in Table 13. We use two types of regularization in training:

四个数据集的详细统计见表 11。用于得到表 2 的 BigBird 超参见表 12，用于得到表 3 的见表 13。训练中使用两类正则：

• We used a variant of contrastive predictive coding [70] as a dual encoder model.

• 使用对比预测编码 [70] 的一种变体作为双编码器模型。

• We use position embedding for itc and relative position encoding [79] for etc.

• itc 用位置嵌入，etc 用相对位置编码 [79]。

Next, we will mention the dataset/task specific part of the model.

下面说明各数据集/任务特有的模型部分。

128

128

128

Natural Questions 此处数据同样是问题加支持证据，但证据是单篇可能很长的文档而非多段。大体沿用 [5] 的设定。对长于 4096 的文档，用步长 2048 的滑动窗口。开头用 CLS，后接问题与文档。分别预测长答案与短答案跨度；相关超参见表。

128

TriviaQA 数据由问答对与作为「嘈杂」支持证据的维基文章组成。称之为嘈杂，是因为给定文章未必含答案；且答案实体未标注到合适跨度，而是用模糊字符串匹配找到的所有出现都被当作正跨度。我们沿用常见设定做跨度抽取，并对长文滑动窗口。

79

79

It is worthwhile to note that explicitly designed attention connection in etc works slightly better, the random connection based itc is pretty competative.

值得注意：etc 中显式设计的注意力连接略好，但基于随机连接的 itc 也相当有竞争力。

E.3 Relationship to Contemporary Work

E.3 与同期工作的关系

Longformer Child et al. 2019 introduced localized sliding window to reduce computation. A more recent version, which includes localized sliding windows and global tokens was introduced independently by Longofrmer[8]. Although BigBird contains additional random tokens, there are also differences in the way global and local tokens are realized. In particular even when there is no random token, as used to get SoTA in question answering, there are two key differences between Longformer and BigBird-etc (see [4]):

Longformer Child 等人 2019 引入局部滑动窗口以降低计算。更近的、同时包含局部滑动窗口与全局 token 的版本由 Longformer [8] 独立提出。尽管 BigBird 还含额外随机 token，全局与局部 token 的实现方式也有差别。

We use global-local attention with relative position encodings enables it to better handle structured inputs

我们用带相对位置编码的全局-局部注意力，以便更好处理结构化输入

Unlike Longformer, we train the global tokens using CPC loss and learn their use during finetuning.

与 Longformer 不同，我们用 CPC 损失训练全局 token，并在微调时学习其用法。

E.4 Classification

E.4 分类

We try two types of classification task.

我们尝试两类分类任务。

1\times 10^{-5}

1\times 10^{-5}

95.0\pm 0.2

Model	IMDb [64]	Yelp-5 [108]	Arxiv [35]	Patents [53]	Hyperpartisan [47]
# Examples	25000	650000	30043	1890093	645
# Classes	2	5	11	663	2
Excess fraction	0.14	0.04	1.00	0.90	0.53
SoTA	[88] 97.4	[3] 73.28	[69] 87.96	[69] 69.01	[40] 90.6
RoBERTa	$95.0\pm 0.2$	71.75	87.42	67.07	$87.8\pm 0.8$
BigBird	$95.2\pm 0.2$	72.16	92.31	69.30	$\mathbf{92.2\pm 1.7}$

95.0\pm 0.2

模型	IMDb [64]	Yelp-5 [108]	Arxiv [35]	Patents [53]	Hyperpartisan [47]
# 样本数	25000	650000	30043	1890093	645
# 类别数	2	5	11	663	2
超长比例	0.14	0.04	1.00	0.90	0.53
SoTA	[88] 97.4	[3] 73.28	[69] 87.96	[69] 69.01	[40] 90.6
RoBERTa	$95.0\pm 0.2$	71.75	87.42	67.07	$87.8\pm 0.8$
BigBird	$95.2\pm 0.2$	72.16	92.31	69.30	$\mathbf{92.2\pm 1.7}$

System MNLI-(m/mm) QQP QNLI SST-2 CoLA STS-B MRPC RTE 392k 363k 108k 67k 8.5k 5.7k 3.5k 2.5k BERT 84.6/83.4 71.2 90.5 93.5 52.1 85.8 88.9 66.4 XLNet 86.8/- 91.4 91.7 94.7 60.2 89.5 88.2 74.0 RoBERTa 87.6/- 91.9 92.8 94.8 63.6 91.2 90.2 78.7 BigBird 87.5/87.3 88.6 92.2 94.6 58.5 87.8 91.5 75.0 Table 16: GLUE Dev results on base sized models. Number of training examples is reported below each task. MCC score is reported for CoLA, F1 score is reported for MRPC, Spearman correlation is reported for STS-B, and accuracy scores are reported for the other tasks.

System	MNLI-(m/mm)	QQP	QNLI	SST-2	CoLA	STS-B	MRPC	RTE
	392k	363k	108k	67k	8.5k	5.7k	3.5k	2.5k
BERT	84.6/83.4	71.2	90.5	93.5	52.1	85.8	88.9	66.4
XLNet	86.8/-	91.4	91.7	94.7	60.2	89.5	88.2	74.0
RoBERTa	87.6/-	91.9	92.8	94.8	63.6	91.2	90.2	78.7
BigBird	87.5/87.3	88.6	92.2	94.6	58.5	87.8	91.5	75.0

系统 MNLI-(m/mm) QQP QNLI SST-2 CoLA STS-B MRPC RTE 392k 363k 108k 67k 8.5k 5.7k 3.5k 2.5k BERT 84.6/83.4 71.2 90.5 93.5 52.1 85.8 88.9 66.4 XLNet 86.8/- 91.4 91.7 94.7 60.2 89.5 88.2 74.0 RoBERTa 87.6/- 91.9 92.8 94.8 63.6 91.2 90.2 78.7 BigBird 87.5/87.3 88.6 92.2 94.6 58.5 87.8 91.5 75.0 Table 16: GLUE Dev results on base sized models. Number of training examples is reported below each task. MCC score is reported for CoLA, F1 score is reported for MRPC, Spearman correlation is reported for STS-B, and accuracy scores are reported for the other tasks.

系统	MNLI-(m/mm)	QQP	QNLI	SST-2	CoLA	STS-B	MRPC	RTE
	392k	363k	108k	67k	8.5k	5.7k	3.5k	2.5k
BERT	84.6/83.4	71.2	90.5	93.5	52.1	85.8	88.9	66.4
XLNet	86.8/-	91.4	91.7	94.7	60.2	89.5	88.2	74.0
RoBERTa	87.6/-	91.9	92.8	94.8	63.6	91.2	90.2	78.7
BigBird	87.5/87.3	88.6	92.2	94.6	58.5	87.8	91.5	75.0

\bm{5\%}

文档分类 我们在长度与内容各异的数据集上实验，见表 15。具体包括情感分析（IMDb [64]、Yelp-5 [108]）与主题划分（Arxiv [35]、Patents [53]、Hyperpartisan [47]）。沿用 BERT，在第一个 [CLS] token 上接一层交叉熵损失。对超长文档做截断或滑动。结果表明：在超长比例高的数据集上，长上下文带来更大收益。

b=64,g=2\times b,w=3\times b,r=3\times b

b=64,g=2\times b,w=3\times b,r=3\times b

E.5 Summarization

E.5 摘要

As discussed in Section 4.1, given the small length of output sequence, we used sparse BigBird attention only for encoder, while keeping the full attention for decoder. The number of hidden layers, number of heads, and hidden dimension is same for encoder and decoder. The hyperparameters are detailed in Table 17. We summarize our result in Table 20. In all experiments, we use a learning rate warmup over the first 10,000 steps, and square root decay of the learning rate.

如第 4.1 节所述，因输出序列较短，我们只在编码器使用稀疏 BigBird 注意力，解码器保持全注意力。编码器与解码器的隐层层数、头数与隐维相同。超详见表 17。结果汇总于表 20。

b

Parameter	Base: BigBird-RoBERTa		Large: BigBird-Pegasus
Block length, $b$		$64$		$64$
Global token location		itc		itc
$\#$ of global token, $g$		$2\times b$		$2\times b$
Window length, $w$		$3\times b$		$3\times b$
$\#$ of random token, $r$		$3\times b$		$3\times b$
Max. encoder sequence length		BBC-XSUM: .1024		1024
	CNN/DM: .2048		2048
	Others: .3072		3072
Max. decoder sequence length		BBC-XSUM: 10.64		64
	CNN/DM: 1.128		128
	Others: 1.256		256
Beam size		5		5
Length penalty		BBC-XSUM: 100.7		0.7
	Others: 100.8		0.8
$\#$ of heads		$12$		$16$
$\#$ of hidden layers		$12$		$16$
Hidden layer size		$768$		$1024$
Batch size		$128$		$128$
Loss		teacher forced		teacher forced
	cross-entropy		cross-entropy
Activation layer		gelu		gelu
Dropout prob		$0.1$		$0.1$
Attention dropout prob		$0.1$		$0.1$
Optimizer		Adam		Adafactor
Learning rate		$1\times 10^{-5}$		$1\times 10^{-4}$
Compute resources		$4\times 4$ TPUv3		$4\times 8$ TPUv3

b

参数	Base: BigBird-RoBERTa		Large: BigBird-Pegasus
块长 $b$		$64$		$64$
全局 token 位置		itc		itc
全局 token 数 $g$		$2\times b$		$2\times b$
窗口长 $w$		$3\times b$		$3\times b$
随机 token 数 $r$		$3\times b$		$3\times b$
Max. encoder sequence length		BBC-XSUM: .1024		1024
	CNN/DM: .2048		2048
	Others: .3072		3072
Max. decoder sequence length		BBC-XSUM: 10.64		64
	CNN/DM: 1.128		128
	Others: 1.256		256
束宽		5		5
长度惩罚		BBC-XSUM: 100.7		0.7
	Others: 100.8		0.8
$\#$ of heads		$12$		$16$
$\#$ of hidden layers		$12$		$16$
Hidden layer size		$768$		$1024$
批大小		$128$		$128$
Loss		teacher forced		teacher forced
	cross-entropy		cross-entropy
Activation layer		gelu		gelu
Dropout prob		$0.1$		$0.1$
Attention dropout prob		$0.1$		$0.1$
Optimizer		Adam		Adafactor
学习率		$1\times 10^{-5}$		$1\times 10^{-4}$
Compute resources		$4\times 4$ TPUv3		$4\times 8$ TPUv3

Instances Input Length Output Length Dataset Training Dev Test Median 90%-ile Median 90%-ile Arxiv [20] 20303764366440615114405171352 PubMed [20] 1199246633665827156101212318 BigPatent [78] 1207222670686707230827693123197 Table 18: Statistics of datasets used for summarization.

	Instances		Input Length	Output Length
Dataset	Training	Dev	Test	Median	90%-ile	Median	90%-ile
Arxiv [20]	203037	6436	6440	6151	14405	171	352
PubMed [20]	119924	6633	6658	2715	6101	212	318
BigPatent [78]	1207222	67068	67072	3082	7693	123	197

样本数 输入长度 输出长度 数据集 训练 开发 测试 中位 90 分位 中位 90 分位 Arxiv [20] 20303764366440615114405171352 PubMed [20] 1199246633665827156101212318 BigPatent [78] 1207222670686707230827693123197 Table 18: Statistics of datasets used for summarization.

	样本数		输入长度	输出长度
数据集	训练	开发	测试	中位	90 分位	中位	90 分位
Arxiv [20]	203037	6436	6440	6151	14405	171	352
PubMed [20]	119924	6633	6658	2715	6101	212	318
BigPatent [78]	1207222	67068	67072	3082	7693	123	197

Following success of several recent works [76, 63], we warm start our encoder-decoder BigBird transformer model with pretrained weights and the weights between encoder and decoder are shared. In particular, the query/key/value matrix of self-attention and all the feedforward layers are shared between encoder and decoder. The only variable that is initialized randomly is the encoder-decoder attention. For base sized model, we utilize our MLM pretrained model on 4096 sequence length from Section E.1, which is in turn initialized using the public RoBERTa checkpoint. For the large size model, we lift weight from the state-of-the-art Pegasus model [107], which is pretrained using an objective designed for summarization task.

沿用若干近期工作 [76, 63] 的成功经验，我们用预训练权重热启动编码器-解码器 BigBird Transformer，并在编码器与解码器之间共享权重。具体地，自注意力的 query/key/value 矩阵与全部前馈层在编码器与解码器间共享。唯一独立的变量是交叉注意力参数。

To check if sparse attention causes significant degradation as compared to full attention, we further experiment on two shorter but popular datasets, where full attention can be used without significantly truncating the document. The statistics of these two datasets are in Table 19. We see that our performance is competitive, which shows that sparse attention can achieve similar performance to a full attention models.

为检查稀疏注意力相对全注意力是否显著变差，我们还在两个较短但流行的数据集上实验——那里用全注意力不必大幅截断文档。两数据集统计见表 19。可见性能有竞争力，说明稀疏化并未带来明显损失。

Instances Input Length Output Length Dataset Training Dev Test Median 90%-ile Median 90%-ile BBC XSum [67] 20404411332113343599202532 CNN/DailyMail [36] 287113133681149077714395993 Table 19: Shorter summarization dataset statistics.

	Instances		Input Length	Output Length
Dataset	Training	Dev	Test	Median	90%-ile	Median	90%-ile
BBC XSum [67]	204044	11332	11334	359	920	25	32
CNN/DailyMail [36]	287113	13368	11490	777	1439	59	93

样本数 输入长度 输出长度 数据集 训练 开发 测试 中位 90 分位 中位 90 分位 BBC XSum [67] 20404411332113343599202532 CNN/DailyMail [36] 287113133681149077714395993 Table 19: Shorter summarization dataset statistics.

	样本数		输入长度	输出长度
数据集	训练	开发	测试	中位	90 分位	中位	90 分位
BBC XSum [67]	204044	11332	11334	359	920	25	32
CNN/DailyMail [36]	287113	13368	11490	777	1439	59	93

16.30

Model		BBC XSum		CNN/DailyMail
	R-1	R-2	R-L		R1	R2	R-L
Prior Art	Lead		$16.30$	$1.61$	$11.95$		$39.60$	$17.70$	$36.20$
PtGen [77]		$29.70$	$9.21$	$23.24$		$39.53$	$17.28$	$36.38$
ConvS2S [28]		$31.89$	$11.54$	$25.75$		$-$	$-$	$-$
MMN [48]		$32.00$	$12.10$	$26.00$		$-$	$-$	$-$
Bottom-Up [29]		$-$	$-$	$-$		$41.22$	$18.68$	$38.34$
TransLM [45]		$-$	$-$	$-$		$39.65$	$17.74$	$36.85$
UniLM [23]		$-$	$-$	$-$		$43.47$	$20.30$	$40.63$
Extr-Abst-BERT [62]		38.81	16.50	31.27		42.13	19.60	39.18
BART [56]		45.14	22.27	37.25		44.16	21.28	40.90
Base	Transformer [91]		29.61	9.47	23.17		34.89	13.13	32.12
+ RoBERTa [76]		39.92	17.33	32.63		39.44	18.69	36.80
+ Pegasus [107]		39.79	16.58	31.70		41.79	18.81	38.93
BigBird-RoBERTa		39.52	17.22	32.30		39.25	18.46	36.61
Large	Pegasus (Reported) [107]		47.60	24.83	39.64		44.16	21.56	41.30
Pegasus (Re-eval)		47.37	24.31	39.23		44.15	21.56	41.05
BigBird-Pegasus		47.12	24.05	38.80		43.84	21.11	40.74

16.30

Appendix F Genomics experiments details

附录 F 基因组实验细节

In this section we provide details of the experimental setup for BigBird on genomics data.

本节给出 BigBird 在基因组数据上的实验设定细节。

F.1 Pretraining

F.1 预训练

\mathcal{D}

\mathcal{D}

D=\emptyset

D=\emptyset

C

C

450K

450K

10\%

图 7：由原始 DNA 数据生成掩码语言模型数据的示意。GRCh37 原始 DNA 序列在随机位置切开，做成含 50-100 句、每句 500-1000 碱基对（bp）的文档，因而每篇文档是连续 25000-100000 bp 的 DNA 链。该过程重复以覆盖基因组。

Next we run sentencepiece [50] tokenization on the resulting documents. In particular, using 5 characters as the building blocks (four for bases - A, T, C, G and one for missing symbol N), we construct a byte pair encoding table of size 32k, with each token representing 8.78 base pairs on average.

接着对所得文档跑 sentencepiece [50] 分词。具体地，以 5 个字符为构建块（四种碱基 A、T、C、G 与缺失符号 N），构造大小 32k 的 BPE 表，每个 token 平均代表 8.78 个碱基对。

Using the above constructed documents, we construct a dataset for two pretraining tasks following Devlin et al. 2018:

用上述文档，按 Devlin 等人 2018 构造两个预训练任务的数据集：

• Masked Language Model (MLM): In order to train a deep bidirectional representation, BERT training introduces the MLM task, where we simply mask out 15% of the input tokens at random, and then predict those masked tokens. We can simply replace such masked out of the tokens with a [MASK] placeholder, but it leads to a distribution mis-match for downstream tasks which will not have such placeholders. To mitigate with this issue, out of the 15% of the tokens selected for masking: - 80% of the tokens are actually replaced with the token [MASK]. - 10% of the time tokens are replaced with a random token. - 10% of the time tokens are left unchanged, but are still predicted at output. We run this entire sequence through the BigBird transformer encoder and then predict corresponding to the masked positions, based on the context provided by the other non-masked tokens in the sequence.

• 掩码语言模型（MLM） ： 为训练深层双向表示，BERT 训练引入 MLM：随机掩掉 15% 输入 token 再预测它们。可直接用 [MASK] 占位替换，但这会造成微调时分布不匹配；因此沿用 BERT：80% 换成 [MASK]，10% 换成随机 token，10% 保持不变。

• Next Sentence Prediction (NSP): In order to understand relationship between two sequences, BERT training introduces the NSP task, where we predict if a given pair of sequences are contiguous or not. During training the model gets as input pairs of sequences separated by [SEP] token along with a [CLS] token at the start. Overall the input pattern is: [CLS] sequence A [SEP] sequence B [SEP]. For 50% of the time the second sequence comes from true sequence after the first one. Remaining 50% of the time it is a a random sequence from the full dataset. The model is then required to predict this relationship using the output corresponding to the [CLS] token, which is fed into a simple binary classification layer.

• 下一句预测（NSP） ： 为理解两序列关系，BERT 训练引入 NSP：预测给定序列对是否相邻。训练时输入由 [SEP] 分隔的序列对，开头加 [CLS]。整体输入打包方式与 NLP 设定一致。

Figure 8: BigBird accuracy with context length.

图 8：BigBird 准确率随上下文长度变化。

The sequence of steps is visually elaborated in Figure 9. The model is trained with both MLM and NSP together. Training hyperparameter is provided in second columns of Table 21. In all experiments we use a learning rate warmup over the first 10,000 steps, and linear decay of the learning rate.

步骤序列见图 9 的示意。模型同时用 MLM 与 NSP 训练。训练超参见表 21 第二列。所有实验在前 10,000 步做学习率预热，之后线性衰减。

We additionally performed a simple ablation study to validate the hypothesis, that similar to NLP, having a larger context improves performance. We use MLM task described above to test how BigBird performed with sequences of different length. Accuracy on MLM task with increasing sequence length is shown in Figure 8. Not only longer context improves final accuracy, it also leads to faster learning, as we have now more opportunities for masking.

我们还做了一个简单消融，验证「与 NLP 类似，更大上下文能提升表现」的假设。用上述 MLM 任务测试 BigBird 在不同序列长度上的表现。随序列长度增加的 MLM 准确率见图 8：更长上下文不仅提升准确率，也表明基因组建模同样受益于长程依赖。

690

图 9：由 GRCh37 原始 DNA 预测给定非编码区域染色质谱时所用 DNA 片段的示意。我们在给定非编码区域前后各取 8000 bp 作为上下文。含两侧上下文的完整 DNA 片段再分词，形成输入序列。

F.2 Promoter Region Prediction

F.2 启动子区域预测

The promoter region plays an important role in transcription initiation and thus its recognition is an important area of interest in the field of bioinformatics. Following Oubounyt et al. 2019, we use datasets from Eukaryotic Promoter Database (EPDnew) [24], which contains 29,597 promoter region in the human genome. Around the transcription start site (TSS), we extract a sequence of 8000 bp (-5000 +3000 bp) from the human reference genome GRCh37. Since EPDnew uses newer GRCh38, we convert to GRCh37 coordinates using LiftOver [44].

启动子区域在转录起始中起重要作用，其识别是生物信息学的重要议题。沿用 Oubounyt 等人 2019，我们使用真核启动子数据库（EPDnew）[24] 的数据，其中含人类基因组中 29,597 个启动子区域。在转录起始位点周围截取固定窗口作为正例。

Following Oubounyt et al. 2019 for each promoter region example, a negative example (non-promoter sequences) with the same size of the positive one is constructed as follow: The positive sequence is divided into 20 subsequences. Then, 12 subsequences are picked randomly and substituted randomly. The remaining 8 subsequences are conserved. This process is illustrated in Figure 1 of [71]. Applying this process to the positive set results in new non-promoter sequences with conserved parts from promoter sequences (the unchanged subsequences, 8 subsequences out of 20). These parameters enable generating a negative set that has 32 and 40% of its sequences containing conserved portions of promoter sequences.

沿用 Oubounyt 等人 2019：对每个启动子正例，构造等长负例（非启动子序列）如下：把正序列分成 20 个子序列；随机挑 12 段做随机替换，其余 8 段保留。该过程保证负例与正例局部统计相近但破坏启动子结构。

We prefix and append each example with [CLS] and [SEP] token respectively. The output corresponding to the [CLS] token from BigBird transformer encoder is fed to a simple binary classification layer. We fine-tune the pretrained BigBird from Section F.1 using hyper-parameters described in Table 21. We note that high performance is not surprising due to the overlap in the nature of negative example generation and MLM pretraining.

每个样本前后分别加 [CLS] 与 [SEP]。BigBird Transformer 编码器在 [CLS] 上的输出送入简单二分类层。用第 F.1 节预训练的 BigBird，按表 21 超参微调。高性能并不令人意外，因为任务相对容易且上下文充足。

F.3 Chromatin-Profile Prediction

F.3 染色质谱预测

The first step of sequence-based algorithmic framework for predicting non-coding effects is to build a model to predict, large scale chromatic profile [109].

基于序列预测非编码效应的算法框架，第一步往往是建立预测大规模染色质谱的模型 [109]。

b

Parameter	Pretraining		Promoter Region	Chromatin-Profile
Block length, $b$	$64$		$64$	$64$
Global token location	itc		itc	itc
$\#$ of global token, $g$	$2\times b$		$2\times b$	$2\times b$
Window length, $w$	$3\times b$		$3\times b$	$3\times b$
$\#$ of random token, $r$	$3\times b$		$3\times b$	$3\times b$
Max. Sequence Length	$4096$		$4096$	$4096$
$\#$ of heads	$12$		$12$	$12$
$\#$ of hidden layers	$12$		$12$	$12$
Hidden layer size	$768$		$768$	$768$
Batch Size	$256$		$256$	$256$
Vocab Size	$32000$		$32000$	$32000$
Loss	MLM+NSP		BCE	919 x +ve upweighted
		BCE
Dropout prob	$0.1$		$0.1$	$0.1$
Optimizer	Adam		Adam	Adam
Learning rate	$0.0001$		$0.0001$	$0.0001$
$\#$ of steps	$1000000$		711	500000
Compute Resources	$8\times 8$ TPUv3		$8\times 8$ TPUv3	$8\times 8$ TPUv3

b=64

In this paper, we use the dataset provided in Zhou and Troyanskaya 2015[^8], to train BigBird to predict the chromatic profile.

本文使用 Zhou 与 Troyanskaya 2015 提供的数据集，训练 BigBird 预测染色质谱。

Each training sample consists of a 8,000-bp sequence from the human GRCh37 reference genome centered on each 200-bp bin and is paired with a label vector for 919 chromatin features. As before, we prefix and append each example with [CLS] and [SEP] token respectively. The output corresponding to the [CLS] token from BigBird transformer encoder is fed to a linear layer with 919 heads. Thus we jointly predict the 919 independent binary classification problems. We fine-tune the pretrained BigBird from Section F.1 using hyper-parameters described in Table 21. As the data is highly imbalanced data (way more negative examples than positive examples), we upweighted loss function for positive examples by factor of 8.

每个训练样本是人类 GRCh37 参考基因组上以每个 200-bp bin 为中心的 8,000-bp 序列，并配有 919 个染色质特征的标签向量。同样在样本前后加 [CLS] 与 [SEP]。BigBird 编码器在 [CLS] 上的输出送入多标签分类头。

We used training and testing split provided by Zhou and Troyanskaya 2015 using chromosomes and strictly non-overlapping. Chromosome 8 and 9 were excluded from training to test chromatin feature prediction performances, and the rest of the autosomes were used for training and validation. 4,000 samples on chromosome 7 spanning the genomic coordinates 30,508,751-35,296,850 were used as the validation set.

训练/测试划分沿用 Zhou 与 Troyanskaya 2015：按染色体且严格不重叠。8、9 号染色体排除出训练以测试染色质特征预测；其余常染色体用于训练与验证。7 号染色体上跨越指定基因组坐标的 4,000 个样本用作额外检查。

As the predicted probability for each sequence in DeepSea Zhou and Troyanskaya 2015 was computed as the ensemble average of the probability predictions for the forward and complementary sequence pairs, we also predict using an ensemble of two BigBird model trained independently.

由于 DeepSea（Zhou 与 Troyanskaya 2015）对每条序列的预测概率取正链与互补链概率的集成平均，我们也用两个独立训练的 BigBird 做集成预测。

Big Bird: Transformers for Longer Sequences

Big Bird：面向更长序列的 Transformer

Abstract

摘要

1 Introduction

1 引言

1.1 Related Work

1.1 相关工作

2 BigBird Architecture

2 BigBird 架构

3 Theoretical Results about Sparse Attention Mechanism

3 稀疏注意力机制的理论结果

3.1 Notation

3.1 记号

3.2 Universal Approximators

3.2 通用逼近器

Definition 1.

定义 1。

Theorem 1.

定理 1。

3.3 Turing Completeness

3.3 图灵完备性

3.4 Limitations

3.4 局限

Proposition 1.

命题 1。

4 Experiments: Natural Language Processing

4 实验：自然语言处理

Pretraining and MLM

预训练与 MLM

Question Answering (QA)

问答（QA）

Classification

分类

4.1 Encoder-Decoder Tasks

4.1 编码器–解码器任务

Summarization

摘要

5 Experiments: Genomics

5 实验：基因组学

Pre-training and MLM

预训练与 MLM

Promoter Region Prediction

启动子区域预测

Chromatin-Profile Prediction

染色质图谱预测

6 Conclusion

6 结论

References

参考文献

Appendix A Universal Approximators

附录 A 通用逼近器

A.1 Notation

A.1 记号

A.2 Proof

A.2 证明

A.2.1 Approximate FCD\mathcal{F}_{CD}FCD​ by piece-wise constant functions

A.2.1 用分段常函数逼近 FCD\mathcal{F}_{CD}FCD​

Lemma 1(Lemma 8 [104]).

引理 1（引理 8 [104]）。

A.2.2 Contextual Mappings and Sparse Attention Mechanisms

A.2.2 上下文映射与稀疏注意力机制

Definition 2(Defn 3.1 [104]).

定义 2（定义 3.1 [104]）。

Lemma 2.

引理 2。

Proof.

证明。

Lemma 3.

引理 3。

Proof.

证明。

Base case

基础情形

Inductive Step

归纳步骤

Lemma 4(Lemma 7 [104]).

引理 4（引理 7 [104]）。

A.2.3 Approximating modified Transformers by Transformers

A.2.3 用 Transformer 逼近改性 Transformer

A.2.1 Approximate $\mathcal{F}_{CD}$ by piece-wise constant functions

A.2.1 用分段常函数逼近 $\mathcal{F}_{CD}$

Part 1: The full attention mechanism can solve the problem in $O(1)$ layer

第 1 部分：全注意力机制可用 $O(1)$ 层求解该问题

Part 2: Every Sparse Attention Mechanism will need $\tilde{\Omega}(n^{1-\epsilon})$ layers

第 2 部分：每个稀疏注意力机制都需要 $\tilde{\Omega}(n^{1-\epsilon})$ 层