quadratic dependency(이차 의존성)

• 시퀀스 연산을 제곱으로 필요로 함

Abstract

• Bert 같은 트랜스포머 기반의 모델은 NLP의 딥러닝 모델에서 성공적인 효과를 가져왔다.
• 핵심적인 한계는 full 어텐션 메커니즘으로 인한 특히 메모리의 양에서 sequence 길이에 대한 quadratic dependency였다.
• 이를 해결하고자, 우리는 BIGBIRD를 제시한다
  • sparse attention mechanism
    • quadratic dependency를 linear로 줄인다
• 우리는 BIGBIRD가 sequence functions에 대해서 universal approximator이며, Turing complete해서 quadratic의 속성인 full attention model을 보존함을 입증했다.
• 그 과정에서 우리의 이론적인 분석은 CLS같은 $O(1)$ global tokens를 가지는 것의 이점을 밝힌다.
  • global tokens는 sparse attention mechanism의 부분으로 entire sequence에 들어간다
• 제시하는 sparse attention은 시퀀스의 길이를 $8x$까지 다룰 수 있다(이는 이전에 similar hardware를 사용해서 가능했었다)
• 더 긴 문맥을 다루기위한 수용력의 결과로, BIGBIRD는 NLP task의 다양한 부분(question answering, summarization)에서 성능을 높였다
• 우리는 또한 genomics data에 대한 novel한 application을 제안한다

1 Intro

Transformer

• BERT처럼 Transformers에 의존하는 모델들은 NLP의 많은 분야에서 성공적이고 현대 NLP 연구에 많은 결과를 가져왔다.
• 그 강건함은 Transformer를 wide-scale로 채택되게 했다.
• 모델은 seq2seq model을 translation [91], summarization [66], generation [15], etc. or as a standalone encoders for sentiment analysis [83], POS tagging [65], machine reading comprehension [93], etc. 다음과 같은 분야에서 널리 썼으며, 이는 이전의 시퀀스 모델인 LSTM을 압도한다고 알려져있다.
• Transformers의 핵심 혁신은 self-attention mechanism의 소개이다.
  • 인풋 시퀀스에서 각 토큰을 병렬로 평가할 수 있다
    • LSTM같은 recurrent 뉴럴 네트워크에서 sequential dependency를 제거하면서
    • 이 병렬은 Transformer가 GPUs/TPUs 같은 현대의 SIMD hardware accelerators의 full power를 조절해서 NLP 모델을 전례없는 데이터 사이즈로 훈련할 수 있게 한다.
    • 이러한 large scale data에서 훈련이 가능하게 하는 능력은 BERT와 T5 같은 모델을 나타나게 했다
      • 해당 모델들은 트랜스포머를 large general purpose corpora에서 유지하게 하고, knowledge를 downstream task로 전환한다.
      • pretraining은 low data regime downstream task와 sufficient data로의 task의 향상을 가능하게 했다.
        • 그로 인해 현대의 NLP에서 transformers가 아주 흔한 주된 것이 되도록 하였다.

self-attention mechanism

• self-attention mechanism은 RNNs의 제약을 극복한다
  • 어떻게? 인풋 시퀀스에서 각 토큰이 시컨스의 각 다른 토큰에 independently하게 attend할 수 있게 해서.
  • 해당 방법은 몇 가지의 흥미진진한 영향이 있다
  • 특히 full self-attention은 sequence length에서 quadratic한 computational과 memory requirement가 있다.
  • 우리는 corpus가 크더라도, many applications에서 context를 제공하는 sequence length는 제한적임을 알고 있다.
  • 흔히 쓰이는 현대의 hardware와 model sizes를 사용해서 해당 requirement는 인풋 시퀀스의 길이를 512 토큰으로 번역한다.
    • 이는 더 긴 문맥을 필요로 하는 QA, 문서 분류 등에서 direct applicability를 낮춘다.

      참고 Self-attention의 경우 target token과 neighbor token 간의 inner-product를 통해 계산된다. 따라서, Sequence의 길이가 길어지면 길어질수록 요구되는 연산이 많아지기 때문에 일반적으로 512 token으로 입력 문장의 길이를 제한하고 있다. 따라서, 문서 요약, 문서 분류, Q&A 등과 같이 입력 문장의 길이가 512 token 보다 훨씬 긴 경우 성능이 저하된다는 문제가 존재한다.

self-attention mechanism에 대한 의문

• self-attention과 Transformers가 유용하다는 것을 알지만, 우리의 이론적인 이해는 가장 기본적이다.
  • What aspects of the self-attention model are necessary for its performance?
    • self-attention model이 성능을 위해서 어떠한 면에서 필수적인가?
  • What can we say about the expressivity of Transformers and similar models?
    • Transformers와 비슷한 모델들에 대해서 expressivity를 우리는 어떻게 말할 수 있는가
  • 만일 self-attention mechanism이 RNNs만큼 효율적이었다면 design으로부터 명백하지 않았을 것이다.
    • 예를 들어서 self-attention은 permutation(순열) equivalent(동등한)이기 때문에 sequence order에 obey하지 않는다
      • 해당 고려는 다음을 입증하면서 부분적으로 해결되었다
        • Yun et al.은 transformers는 모든 continuous sequence를 compact domain에서 sequence functions로 포착하기에 충분하다
        • 한편 Pérez et al.은 full transformer가 Turing Complete (i.e. can simulate a full Turing machine)임을 보였다.

          튜링 완전(turing complete)이란 어떤 프로그래밍 언어나 추상 머신이 튜링 머신과 동일한 계산 능력을 가진다는 의미이며 튜링 머신으로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 머신으로 풀 수 있다는 의미.

      • 두 가지의 자연스러운 의문이 생긴다.
        • Can we achieve the empirical benefits of a fully quadratic self-attention scheme using fewer inner-products?
        • 우리가 fewer inner-products를 사용해서 fully quadratic self-attention scheme의 경험적 이점을 얻을 수 있는가?
        • Do these sparse attention mechanisms preserve the expressivity and flexibility of the original network?
        • 이러한 spars ttention mechanisms가 original network의 expressivity와 flexibility를 보존하는가?

본 논문

• 우리는 위 질문을 다루고, 더 긴 문맥을 필요로 하는 multitude task에서 성능을 향상하는 sparse attention mechanism을 제시한다.
• 시스템적으로는 BIGBIRD를 개발한다
  • attention 메커니즘
  • complexity가 토큰의 수에 linear하다(Sec2)
• 우리는 graph sparsification methods에서 영감을 얻어, proposed attention pattern을 형성하기 위해 full-attention이 relaxed되었을 때 Transformers의 expressiveness에 대한 증거가 어디서 break down되었는지 이해한다.
  • 그 이해는 우리가 BIGBIRD를 개발하게 도와주었다
    • 그것은 이론적으로 효율적이고 경험적으로 유용하다

BIGBIRD의 주요 구성 요소

• A set of g global tokens attending on all parts of the sequence.
  • 모든 sequence의 부분에 attending하는 global tokens g의 집합
• All tokens attending to a set of w local neighboring tokens.
  • local neighboring tokens의 집합인 w에 attending 하는 모든 tokens들
• All tokens attending to a set of r random tokens
  • random tokens의 집합인 r에 attending하는 모든 tokens들
• 이를 통해 더 긴 시퀀스 길이에서 좋은 성과 얻는 것이 가능하다(8x)

main contributions

1. BIGBIRD는 full transformer에 대한 모든 알려진 이론적인 속성을 충족한다(Sec. 3).

• 특히 우리는 extra tokens를 추가하는 것이 O(n)-inner products만으로 모든 continuous sequence to sequence functions를 표현하는 것이 가능함을 보였다.
• 더 나아가 우리는 precision 관련된 standard assumptions에서 BIGBIRD가 Turing complete함을 보였다.

2. 경험적으로 우리는 BIGBIRD에 의해서 모델링된 extended context가 많은 NLP task에서 이점을 줌을 보였다.

• 우리는 question answering과 document summarization에서 a number of different datasets로 state of the art results를 달성했다
  • 해당 결과에 대한 요약은 Sec.4에 있다

3. long contexts에서 이점이 있는 attention 기반의 novel application을 소개했다.

• DNA 같은 contextual representations of genomics sequences를 뽑아서
• longer masked LM pretraining을 통해 BIGBIRD는 promoterregion and chromatin profile prediction (Sec. 5)같은 task에서 성능이 향상되었다.

참고실험 결과 transformers의 시간 복잡도 $O(n^{2})$ 을 $O(n)$으로 감소시킴으로써, 512 token보다 8배 긴 문장을 입력 받을 수 있게 된 것 뿐만 아니라 기존 Fully Self-attention의 성능까지 달성하였다. 게다가 문서 요약, Q&A 등과 같이 입력 문장의 길이가 긴 분야에서는 SOTA를 달성하였다.

1.1 Related work

• Transformers의 quadratic dependency를 경감하는데 초점을 둔 흥미로운 시도들이 있었다

1. length 한계를 받아들이고(입력 문장의 길이는 512 token으로 사용하고), method를 그 주위에서 개발한다(sliding window방식을 통해 입력 문장을 여러 block으로 받는다)

• 해당 방법에서 가장 간단한 방법은 sliding window를 적용하는 것이다
• 하지만 대다수의 일반적인 일에서 다음의 일반적인 패러다임을 따른다
  • 다른 몇 메커니즘이 relevant contexts에서 더 적은 subset을 선택하도록 해서 transformer에 적용하고 선택적으로 iterate하게 하기(i.e. call transformer block multiple time with different contexts each time)
  • 가장 유망하게 SpanBERT [42], ORQA [54], REALM [34], RAG [57] 같은 다양한 태스크에서 강한 성능을 성취했다
  • 하지만 이는 이러한 방법들이 중요한 engineering efforts (like back prop through large scale nearest neighbor search)를 요구하고 훈련하기 어렵다는 것을 알아차릴 떄 가치가 있다(어렵다는 한계가 있다)

2. 만일 full attention이 본질적인가를 질문하며, full attention을 필요로 하지 않는 접근법들을 시도하려고 노력했다. -> 그를 통해 memory와 계산 필요를 줄이고자 했다(입력 문장의 길이를 늘리고자 fully Self-attention가 아닌 다른 방식을 통해 성능을 개선)

• 유망하게, Dai et al. [21], Sukhbaatar et al. [82], Rae et al. [74]는 auto-regresive models를 제안했다
  • 이는 left-to-right language modeling 에서 잘 작동하지만 bidirectional context를 필요로 하는 task는 어려워한다
• Child et al. [16]는 O(n√n)의 복잡도를 줄이는 sparse model을 제안
• Kitaev et al. [49]은 nearest neighbors를 계산하기 위해 LSH를 사용해서 O(nlog(n))의 복잡도를 줄이고자 노력했다
• Ye et al. [103]는 binary partitions of the data를 제안했다
  • Qiu et al. [73] 가 block sparsity를 사용해서 복잡도를 줄인 데이터.
• 최근 Longformer [8] 는 계산을 줄이기 위해서 few global mask 와 함께 localized sliding window based mask를 소개했고, BERT를 longer sequence based tasks로 확장했다
• 마침내 우리의 연구는 Extended Transformers Construction [4]의 작업과 관련이 있다
  • 해당 연구는 transformers의 text에서 structure를 encode하고자 고안되었다
  • global tokens 아이디어는 그들의 목표를 달성하고자 extensively하게 사용되었다
  • 우리의 이론적인 연구는 이 모델들에 대해서 정당화를 제공하는 것처럼 보일 수도 있다
  • 대다수의 앞서 언급한 방법들이, heuristic 기반이고 경험적으로 다용도이지 않고, original transformer만큼 강건함을 아는 것이 중요하다(i.e. 같은 architecture는 multiple standard benchmarks에서 SOTA를 달성하지 못했다.)
    • 우리의 모든 비교에 포함한 Longformer가 유일한 예외다(App. E.3)

Longformer
Longformer에서 제안한 attention은 기존의 full-attention의 self-attention 행렬을 특정 패턴에 따라 sparse하게 만들어서 사용한다. 논문에서 사용한 attention 패턴은 다음의 세 가지이다.

App E.3 Relationship to Contemporary Work

Longformer

• Child et al. [16]는 computation을 줄이고자 localized sliding window를 소개했다
• 더 최근의 버전은 Longofrmer[8]에 의해서 독립적으로 소개되었다
  • 해당 버전은 localized sliding windows와 global tokens를 소개한다
• 비록 BIGBIRD가 additional random tokens를 포함하지만 global and local tokens가 realized되는 방법에도 차이점이 있다
  • 특히, random tokens가 없을 떄에도, question answering에서 SoTA를 달성하기 위해 Longformer와 BIGBIRD에는 큰 두가지 차이가 있다
    1. 우리는 relative position encodings와 함께 global-local attention을 사용한다
    • structured inputs를 더 잘 다루기 위해서
    2. Longformer와 달리 우리는 CPC loss를 사용해서 global tokens를 훈련하고, finetuning 동안에 그들의 use를 학습한다

2 BIGBIRD Architecture

참고Bigbird는 Multi-head attention과 feed forward network로 구성되어 있는 Transformer 구조를 기반으로 학습. 다만 Self-attention 부분에서 Fully Self-attention이 아닌 generalized attention mechanism을 사용한다는 것이 차이점

• generalised attention mechanism을 사용한 BIGBIRD model을 묘사한다
  • 그것은 transformer의 각 layer에서 input sequence $X = (x1, ..., xn) ∈ R^{n×d}$를 입력으로 받으며,(X는 d차원으로 Embedding 된 입력 문장)
• generalized attention mechanism은 vertex set(노드 집합)가 [n] ={1, . . . , n}인 directed graph(유향 그래프) D에서 묘사된다

유향 그래프, 방향 그래프(Directed Graph) : 하나의 간선이 하나의 방향만을 표현(화살표로 표현)

• arcs의 집합(directed edges)은 attention 메커니즘이 고려할 inner products의 집합을 표현한다
• N(i)를 D에서 노드 i의 out-neighbor로 정의하면
  • 그러면 generalized attention mechanism 의 i번째 output vector는 다음과 같이 정의된다
    
  • $Q_{h}$,$K_{h}$,$V_{h}$는 각각 Query, Key, Value Vector.
  • σ는 Scoring Function으로 본 논문에서는 Softmax 혹은 Hardmax를 사용.
  • $H$는 Self-attention을 수행할 때 head의 수
    
    이미지 출처
    
• $X_N(i)$: the matrix formed by only stacking {xj : j ∈ N(i)} and not all the inputs.
• 만일 D가 complete digraph라면 우리는 Vaswani et al.의 full quadratic attention mechanism을 recover한다
• 우리의 exposition을 간단히 하고자, 우리는 인접행렬(adjacency matrix) A of the graph D에서 작동할 것이다(비록 underlying graph가 sparse일수도 있을지라도)
  • 더 자세히 설명하자면 A(i, j) = 1에서 $A∈ [0, 1]^{n×n}$이다, 만일 query
    i가 key j에 attend하면 1, 아니면 0을 의미한다고 할 때
    예를 들어서 A가 ones matrix(BERT에서처럼)라면 그것은 quadratic complexity로 이어진다(모든 토큰이 각 다른 토큰에 attend하기 때문이다)
    이런 fully connected graph로서의 self-attention view는 우리에게 존재하는 graph theory를 이용해서 complexity를 줄이게 도와준다
• self-attention의 quadratic complexity를 줄이는 것의 문제는 graph
  sparsification problem으로 이어질 수 있다
  • random graphs가 expanders라고 알려져 있고, spectral properties를 포함해서 다양한 문맥의 수의 complete graphs에서 근사치를 낼 수 있다
• 우리는 attention mechanism을 위한 sparse random graph가 두 개를 필요로 해야 한다고 본다
  1. small average path length between nodes
  2. a notion of locality

1. small average path length between nodes

Complete graph에서 edge들이 특정 확률에 의해 남겨진 random graph를 생각해봅시다. 이때 두 노드의 최단 경로(shortest path)는 node의 개수에 logarithmic하게 비례한다는 것이 밝혀져 있습니다. 즉, random graph의 크기를 키우고 sparse하게 만들어도 shortest path가 기하급수적으로 급격히 증가하는 것이 아니고 매우 천천히 변하게 됩니다. 또한 이러한 random graph가 complete graph의 spectral property를 근사하게 되며 second eigenvalue가 first eigenvalue와 차이가 크기 때문에 해당 그래프 위에서의 random walk mixing time이 매우 빨라진다고 합니다. 본 연구에서는 이러한 성질을 각 query가 r개의 random key를 attend하는 구조로 반영하였습니다.(그림1-a)

• Erdos-Rényi model로 알려진 simplest random graph construction을 고려하자
  • 각 edge는 fixed probability로 independently하게 선택된다
• Θ(˜n)egdes만을 가진 그러한 random graph에서 any two node 사이의 가장 짧은 길은 노드의 수에 있는 logarithmic이다
• 결론적으로 그러한 random graph는 spectrally한 complete graph에 근접하고 그것의 두 번째 고유값(인접 행렬의)은 첫 번째 고유값으로부터 꽤 멀다
  • 이러한 속성은 graph에서 random walks에 대한 rapid mixing time으로 이어진다(그것은 비공식적으로 제안한다, any pair of nodes 사이에서 정보가 빠르게 흐를 수 있다고)
  • 그러므로 우리는 sparse attention을 제안한다 -> 각 쿼리가 r random number of keys에 attends하는(즉, A(i, ·) = 1 for r randomly chosen keys, Fig. 1a)
    

2. a notion of locality

locality
어떤 token의 정보는 대부분 주변 token의 정보에서 얻어지고, 멀리 떨어진 token에서 얻게 되는 정보량은 적다는 것입니다. Graph 이론을 적용해보면 locality를 계산하기 위한 방법으로 clustering coefficient(군집 계수)를 활용할 수 있습니다. 예를 들어, 어떤 그래프가 많은 clique, near-clique을 담고 있다면 clustering coefficient가 높습니다.

• 토큰에 대한 엄청난 양의 정보가 neighboring tokens에 의해서 생겨난다
• 가장 요령있게 Clark et al. [19]는 NLP tasks에서 self-attention 모델을 조사하고, neighboring inner-products가 특히 중요하다고 결론을 내렸다
• locality의 개념(lingustic feaute에서의 proximity(가까움) of tokens)은 또한 transformationalgenerative grammar 같은 다양한 lingustic theories의 basis를 형성한다
• graph theory의 용어에서 clustering coefficient는 locality of connectivity의 measure이고 그래프가 많은 cliques나 near-cliques(subgraphs that are almost fully interconnected)를 포함할 때 높다.
• 간단한 Erdos-Rényi random graphs는 high clustering coefficient를 가지고 있지 않다, 하지만 small world graphs라 알려진 random graphs의 class는 high clustering coefficient를 exhibit한다.
• Watts and Strogatz [94] 에 의해서 소개된 특정한 모델은 우리에게 high relevance이다.
  • 그것이 average shortest path와 notion of locality 사이에 good balance를 주기 때문이다.
  • 그들 모델의 일반적인 과정은 다음과 같다
    • Construct a regular ring lattice, a graph with n nodes each connected to w neighbors, w/2 on each side.

본 연구에서는 각 node(token)이 window size w으로 양옆 단어를 attend 하는 구조를 적용했습니다. 즉, self-attention시 i에 위치한 query는 [i−w/2,i+w/2]의 key들을 attend하게 됩니다.(A(i,i−w/2:i+w/2)=1)

sliding window

• 다시 말해서, 우리는 nodes에서 sliding window로 시작한다
• 그러면 모든 connections들의 random subset(k%)는 random connection으로 교체된다
• 다른 (100-k)% local connections들은 유지된다
• 하지만 그런 random edges를 삭제하는 것은 modern hardware에서 효율적이지 않을 수도 있어서, 우리는 그것을 유지한다
• 요약하자면, context에서 local structures를 포착하기 위해서 BIGBIRD에서 우리는 sliding window attention을 정의해 width w의 self attention 동안에 location i에 있는 query가 i − w/2에서 i + w/2 keys로 들어간다
  • $A(i, i−w/2 : i+w/2) = 1$ (see Fig. 1b).
• 초기의 온전한 체크로서 우리는 basic experiments를 수행했다
  • 이 직관이 BERT같은 모델과 유사한 성능을 얻기에 충분한지 시험하고자.
  • 토큰의 수에 attention을 linear하게 유지하면서
  • 그 결과 우리는, random blocks와 local window가 BERT와 경쟁할 성능을 얻기 위해서는 모든 context에서 포착하기는 불충분함을 발견했다

하지만 위 구조들을 적용한 self-attention으로는 기존 BERT의 성능이 나오지 않았다고 합니다. 그리고 저자들은 많은 실험과 이론 분석을 통해 global token의 중요성을 파악하고 이를 적극 활용했다고 합니다. 본 연구에서는 두 가지 방법으로 적용했습니다.

BigBird-ITC(Internal Transformer Construction): 언어 corpus에 존재하는 token 중 특정 몇개를 global token으로 지정하여 모든 token들에 대해 attention 계산
BigBird-ETC(Extended Transformer Construction): sequence에 g개의 global token을 추가(e.g. [CLS])

global tokens

• BIGBIRD의 마지막 조각은 우리의 이론적인 분석(Sec 3)에서 영감을 받았다
  • 그것은 경험적인 성능에 대해서는 비판적이다
• 더 구체적으로, 우리의 이론은 "global tokens"의 중요성을 이용했다
  • 시퀀스에서 모든 토큰에 들어가는 토큰들, 그리고 들어가는 모든 토큰들(Fig 1c)
  • 이런 global tokens는 다음 두 방법으로 정의될 수 있다
  1. BIGBIRD-ITC(In internal transformer construction (ITC))
  • 우리는 전체 시퀀스를 들어가는 어떤 존재하는 토큰인 "global"을 만든다
  • 구체적으로 우리는 a subset G of indices를 선택한다(with g := |G|)
    • A(i, :) = 1 , A(:, i) = 1 for all i ∈ G.
  2. BIGBIRD-ETC(In extended transformer construction (ETC))
  • CLS 같은 추가적인 "global tokens"를 포함했다
  • 구체적으로 우리는 모든 존재하는 토큰에 attend하는 g global tokens를 추가했다
  • 우리의 언어로, 이는 matrix A에 g rows를 추가해서 새로운 matrix인 $B ∈ [0, 1]^{(N+g)×(N+g)} $를 창조하는 것이다
    • $B(i, :) = 1$, $B(:, i) = 1$ 같이.
    • 모든 $i ∈ {1, 2, . . . g}$에 대해서
    • $B(g + i, g + j) = A(i, j)∀ i, j ∈ {1, . . . , N}$
    • 이는 context를 저장하기 위한 extra location을 추가한다(우리는 실험에서 성능이 향상됨을 볼 것이다)

FIG 1D

• BIGBIRD에 대한 마지막 어텐션 메커니즘은 모든 세 가지의 속성을 가지고 있다(Fig 1d)
  • 쿼리는 r random keys에 attend하고
  • each query attends to w/2 tokens to the left of its location and w/2 to the right of its location
  • g global tokens를 가지고 있다
    • global tokens can be from existing tokens or extra added tokens
    • 실행 과정에 대한 자세한 내용은 어펜딕스 D.

APP D Implementation details

GPU/TPU and Sparsity

blockify the attention pattern

• blockify the attention pattern i.e. we pack sets of query and keys
  together and then define attention on these blocks.

1. fig3에서 처럼 12 query and 12 key vectors to attend to.가 있다고 가정할 때,
2. block size of 2,
3. we split the query matrix into 12/2 = 6 blocks and similarly the key matrix into 12/2 = 6 blocks.
4. the three different building components of BIGBIRD are defined on the block matrix.
5. 특히 세 가지의 구성 요소가 있다

• Random attention:
  • Each query block attends to r random key blocks.
  • r = 1, block size 2
  • 해당 부분은 다음 each query block of size 2 randomly attends to a key block of size 2을 뜻한다
• Window local attention
  • the number of query blocks = the number of key blocks => block window attention
  • Every query block with index j attends to key block with index j − (w − 1)/2 to j + (w − 1)/2, including key block j.
  • w = 3 with block size 2.
    • It means that each query block j (size 2 queries) attends to key block j − 1, j, j + 1
• Global attention:
  remains the same as defined in Sec. 2,
  but we compute it in terms of blocks.
  In Fig. 3c, g = 1 with block size 2.
  For BIGBIRD-ITC this implies that one query and key block, attend to everyone.
  
  gather operation으로 더 빨리 계산 가능
  

3 Theoretical Results about Sparse Attention Mechanism

해당 부분에서는 두 관점에서 sparse attention이 full-attention만큼 powerful함을 보이겠다

1. 우리는 standalone encoder (such as BERT)애서 sparse attention 메커니즘이 사용될 때, 그들이 Yun et al. [104] 스타일에서 sequence to sequence functions에 대한 Universal Approximators임을 입증했다. 우리는 이 속성이 이론적으로 contemporary work Yun et al. [105]에도 explored되었음을 알고 있다
2. [105]와 달리, 우리는 sparse encoder-decoder transformers가 Turing Complete (assuming the same conditions defined in [72])임을 입증했다. 위의 긍정적인 결과를 보완하면서 우리는 또한 sparse-attention 메커니즘으로의 이동이 cost를 발생시킨다는 것을 입증했다 (즉, 공짜 점심은 없다)

Sec. 3.4에서 우리는 lower bounds를 보인다

• by exhibiting a natural task where any sufficiently sparse mechanism will require polynomially more layers.

3.1 Notation

• complete Transformer encoder stack는 independent parameters를 가진 single layer encoder의 repeated application이다

• 우리는 Transformer encoders stack의 class를 generalized encoder(Sec2)를 사용해서 $T_D^{H,m,q}$로 정의한다

  • 그것은 head size가 m인 H-heads,
  • q: the hidden layer size of the output network,
  • the attention layer is defined by the directed graph D로 이루어져있다

• 우리가 제안하는 어텐션 메커니즘과 Vaswani et al. [91], Yun et al.[104]의 가장 큰 차이는 다음과 같다.

  • 우리는 각 시퀀스의 시작에 특별한 토큰을 추가했고 그것을 특별한 vector로 할당했다
    • 우리는 이것을 $x_0$라 명명한다
  • 그러므로 우리의 graph D는 노드(vertex) 집합인 ${0} ∪ [n] = {0, 1, 2, . . . , n}$를 가진다
  • 우리는 이 extra node 그리고 respective vector가 transformer의 마지막 아웃풋 레이어에서 떨어질 것임을 가정한다
  • 다루기 어려운 notation을 피하고자, 우리는 transformer를 mapping sequences로서 다룰 것이다($X ∈ R^{n×d}$를 $R^{n×d}$로)
  • 우리는 또한 transformer가 position embeddings $E ∈ R^{d×n}$를 인풋 레이어에서 matrix X에 추가하는 것을 허용한다

• 마침내 우리는 universal approximation을 잘 입증하기 위해서 function class와 distance measure를 정의해야 한다

  • $F_CD$가 continuous functions $f : [0, 1]^{n×d} → R{n×d}$의 집합이라 명명하자.
    • 그것은 $l_{p} norm$에서 정의된 topology에 대해서 연속적이다
    • 어떠한 $p ≥ 1$에 대해서 $lp$ distance가 $dp(f1, f2) =$임을 상기하자

3.2 Universal Approximators

Definition1

• star-graph S centered at 0은 {0, . . . , n}에서 정의되는 그래프다
• 모든 vertices i에 대한 neighborhood는 i ∈ {1 . . . n}에 대해서 N(i) = {0, i}이고, N(0) = {1, . . . n}이다.

우리의 main theorem은 S를 포함하는 graph에 의해서 정의되는 sparse attention 메커니즘이 universal approximator이라는 것이다

Theorem 1

Theorem을 증명하기 위해서, 우리는 [104]에서 outlined된 standard proof structure를 따를 것이다

Step 1: Approximate FCD by piece-wise constant functions

• f가 bounded domain [0, 1)n×d을 가진 continuous function이기에, 우리는 그것을 suitable piece-wise constant function으로 approximate할 것이다.
• 이것은 region [0,1)에서 discrete set $Gδ$를 얻기 위해서 suitable partition으로서 grid of granularity δ로 성취된다.
• 그러므로 우리는 f : Gδ → R^{n×d}(dp(f, ¯f) ≤3)를 다루고 있음을 가정할 수 있다.

Step 2: Approximate piece-wise constant functions by modified transformers.

• 해당 단계는 self-attention mechanism이 인풋의 a contextual-mapping을 생성하는데 사용되는 것을 증명하는 주요한 단계다.
• 비공식적으로 contextual mapping은 matrix (X, xi)와 열 하나로 이루어진 pair의 unique code다
• 그것의 uniqueness는 Feed forward layers가 각 code를 써서 그것을 unique output column으로 map하는데 사용되도록 허락한다
• 주요한 기술적인 challenge는 contextual mapping을 오로지 sparse attention mechanism만을 사용해서 mapping하는 것이다.
• 이는 [104]에서 "selective" shift operator를 사용해서 행해진다
  • 그것은 특정한 간격에 있는 entries들을 shift up하는 것이다
  • 그들 증거의 핵심은 shift가 정확히 가장 큰 entry에서 가장 작은 entry까지의 범위였다는 사실이었다
• sparse attention mechanism으로 contextual mapping을 만드는 것은 꽤 어려운 일이다.
• 특히, 각 쿼리가 few keys에만 attends하기 떄문에, 충분한 정보가 entire matrix의 contextual embedding을 만들기 위해서 모아지는 것은 명백하지 않다.
• 이걸 피하고자, 우리는 sparse shift operator를 개발했다
  • 그것은 matrices의 entries를 shifts한다(그들이 특정한 범위 안에 있다면)
• shift의 정확한 양은 directed sparse attention graphg D에 의해서 통제된다.
• 두 번째 주요 재료는 additional global token의 사용이다
• operator(연산자)를 선택된 범위의 집합에 신중하게 적용함으로써, 우리는 각 열이 전체 매핑의 고유한 매핑을 포함할 것이라는 것을 보여줄 것이다.
• 그러므로 우리는 여러 layers와 auxiliary(보조) global token을 사용하여 self attention 메커니즘에서 inner-products의 loss을 augment(증가)시킬 수 있다.

Step 3: Approximate modified transformers by original Transformers:

• 마지막 단계는 modified된 transformers를 ReLU와 softmax를 사용하는 original transformer에서 approximate하는 것이다(자세한 사항은 App. A)

A Universal Approximators

3.3 Turing Completeness

• Transformers는 매우 일반적인 class다

• Vaswani et al. [91]는 original paper에서 encoder와 decoder를 둘 다 썼다

• 이전 section이 encoder만을 쓰는 것이 얼마나 powerful한지를 다루었다면, 자연적으로 생기는 다른 질문은 what the additional power of both a decoder along with an encoder is? 다.

• Pérez et al. [72]는 quadratic attention mechanism에 기반을 둔 full transformer가 Turing complete임을 보였다

• 이 결과는 한 unrealistic assumption을 만들게 한다

  • 그것은 모델이 임의의 precision model에서 작동한다는 것이다
  • 물론 이것은 다른 방법으로서 필요하다
    • Transformers가 bounded finite state machines이고 cannot be Turing Complete.

• full attention mechanism이 필수적인지 아닌지 물어보는 것은 당연하다. 또는 sparse attention mechanism은 Turing Machine을 simulate하기 위해서 사용될 수 있는가.

• 우리는 이거이 해당 경우임을 보였다: 우리는 any Turing Machine을 simulate하기 위해서 sparse encoder와 sparse decoder를 사용할 수 있다

• transformer architecture에서 sparse attention mechanism을 사용하기 위해서 우리는 어디에서 각 토큰이 이전의 토큰에 반응하는지 적합한 modification을 정의해야 한다

• 전체 attention mechanism이 한 번에 적용되는 BERT와 달리, full transformers에서 decoder side에 있는 sparse attention mechanism은 token by token으로 쓰인다

• 두 번쨰로 Pérez et al. [72]의 작품은 각 토큰을 tape history의 representation으로서 사용하며, full attention을 correct tape symbol을 움직이거나 회수하기 위해서 사용한다

• Pérez et al. [72]의 대다수의 construction은 sparse attention을 거쳐간다(except for their addressing scheme to point back in history (Lemma B.4 in [72]).) , App. B

B Turing Completeness

B.2 Details of the Simulation

Decoder

3.4 Limitations

• 우리는 O(1)-layers에서 full attention mechanism에 의해 해결될 수 있는 natural task를 증명한다
• 하지만 standard complexity theoretic assumptions에 따라서 이 문제는 O˜(n) edges를 가지는 sparse attention layers에 대해서 Ω( ˜ n)-layers를 필요로 한다

4 Experiments: Natural Language Processing

해당 섹션에서 우리의 목표는 NLP task에서 긴 인풋 시퀀스를 모델링 하는 것의 이점을 우리가 선택한 세 representative task에서 보이는 것이다.

• 우리는 basic masked language modeling(MLM; Devlin et al. 22)에서 시작한다.
  • 더 좋은 contextual representations가 더 긴 contiguous sequences를 이용하면서 학습될 수 있는지를 체크하기 위해서
• 다음으로 우리는 supporting evidence로 QA를 고려한다
  • 더 긴 시퀀스를 다루는 수용력은 우리가 TF-IDF/BM25 같은 crude 시스템을 사용하는 것에 더 많은 증거를 가져오도록 허용할 것이다
• 마지막으로 우리는 long document classification을 다룬다
  • 정보를 discriminating(구별)하는 것이 첫 512 토큰에 위치하지 않을 수도 있다
  • 밑에서 우리는 4096 길이의 시퀀스를 사용한 BIGBIRD의 결과를 요약한다
  • 그러면서 우리는 computational resources, batch size, step size 등을 App.E에 set up 세부사항을 요약한다

App E NLP experiments details

E.1 MLM Pretraining

Pretraining and MLM
우리는 base and large versions of BIGBIRD를 만들고 MLM을 사용해서 유지하고자 [22,63]을 따른다

• 이 task는 마스킹된 a random subset of tokens를 예측하는 것을 포함한다
• pretraining을 위해 four standard data-sets을 사용한다(listed in App. E.1, Tab. 9)
  
  • warm-starting from the public RoBERTa checkpoint
  • 우리는 [8]을 따르면서 bits per character의 면에서 masked out tokens를 예측하는데 성능을 비교한다
  • App. E.1, Tab. 10에 나와있는대로 BIGBIRD와 Longformer 둘다 limited length RoBERTa보다 좋은 성능을 보인다(BIGBIRD-ETC가 최고)
  • 우리는 배치 사이즈 32-64로 합리적인 16GB memory/chip로 모델을 훈련했다
  • 메모리 효율성은 Sec2에 묘사되어있다
    * due to efficient blocking and sparsity structure of the
    sparse attention mechanism

Question Answering (QA)
우리는 다음의 4개 데이터셋을 고려한다

1. 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).
2. 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.
3. 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.
4. WikiHop [95]: Chose correct option from multiple-choice questions (MCQ), by aggregating
   information spread across multiple documents given in the evidences.

• 해당 task들이 competitive하기에, multiple highly engineered systems은 특정한 각 데이터셋(confirming to respective output formats)으로 고안되었다.
• 공정한 비교를 위해 우리는 BIGBIRD 훈련에 몇 additional regularization을 사용했다(App. E.2에 상세히 나와있다)

E.2 Question Answering

• 우리는 base sized model을 사용해서 실험하고 각 데이터셋에 대한 best configuration을 선택했다(Tab2)
  
  expanded global tokens를 가진 BIGBIRD-ETC가 다른 모델들을 능가한다. 그러므로 우리는 이 configuration을 골라서 a large sized model을 훈련한다(hidden test set에서 evaluation에 쓰기위해서)

우리는 BIGBIRD-ETC model을 리더보드의 top-3 entries로부터 비교했다.

• Longformer and BIGBIRD가 둘다 longer context를 사용했을 떄 smaller보다 모델이 능가하기에 중요성을 볼 수 있다
• 또한 BIGBIRD submission이 single model인 반면에 다른 Natural Questions에 대한 top-3 entries는 ensembles임을 볼 수 있다(이는 exact answer phrase selection에서의 약간 낮은 정확성을 설명할 수 있다)

Classification
다양한 길이, 내용의 데이터셋에서 실험한다. 특히 문서 분류와 GLUE task에서.

• BERT를 따라서 우리는 first [CLS] token의 가장 위에 cross entropy loss 를 가진 one layer를 사용했다
• 우리는 BIGBIRD를 사용하는 것의 이점이 훈련 예제에서 더 긴 문서를 가지고 있을 떄 더 중요함을 보였다.
  • 예를 들어서 base sized model을 사용하면 BIGBIRD는 Arxiv dataset에 대해 5% points로 state-of-the-art다.
  • Patents dataset에서는 simple BERT/RoBERTa를 쓰는 것보다는 약간의 상승이 있지만 큰 사이즈의 훈련 데이터가 주어졌을 때, SoTA (which is not BERT based)를 넘어선 향상은 중요하지 않다
• 이 성능 향상이 훨씬 더 작은 IMDb dataset에서는 더 작음을 보아라.

Along with experimental setup detail, we present detailed results in App. E.4 which show competitive performance.

E.4 Classification

4.1 Encoder-Decoder Tasks

encoder-decoder setup을 통해서 full self attention 때문에 quadratic complexity로부터 둘다 어려움을 겪음을 볼 수 있다

• 우리는 인코더의 측면에서만 BIGBIRD의 sparse attention mechanism을 소개하는데 초점을 두고자 한다
• 이는 실제적인 generative applications에서 아웃풋 시퀀스의 길이가 인풋에 비해 작기 때문에 일어난다.
  • 예를 들어서 텍스트 요약에 대해서 우리는 realistic scenarios를 본다(c.f. App. E.5 Tab. 18)
    * median output sequence length is ∼ 200이고 input sequence’s median length is > 3000임을.
    이러한 applications에 대해서 인코더에는 sparse attention을 쓰고 디코더에는 full self attention을 쓰는 것이 효율적이다.

E.5 Summarization

Summarization
문서 요약은 텍스트 문서에 대해서 짧고 정확한 요약을 만들어내는 task다.

우리는 모델을 시험하고자 three long document datasets를 썼다(Tab 18)

• 본 논문에서 우리는 긴 문서의 abstractive summarization에 초점을 둔다
  • longer contextual encoder를 사용하는 것이 성능을 향상해야 한다는.
  • 이유는 두 가지다
    1. 가장 중요한 내용이 긴 문서에서 첫 512토큰에가 아니라, 고르게 분포될 수 있다. -> 이것은 BigPatents dataset [78]에 의해서 고안되었다
    2. longer documents는 richer discourse structure를 나타내고, 요약은 상대적으로 더 abstractive해서 context를 더 관찰하는 것이 도움이 된다.
• 최근에 주목받고 있듯이 generative task에서 pretraining이 도움이 된다
  • 우리는 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.

Tab 4

• long document datasets 에서 BIGBIRD sparse encoder를 full decoder로 훈련하는 결과는 Tab 4에 나와있다
• 우리는 긴 문맥을 모델링 하는 것이 더 좋은 성능향상을 가져옴을 볼 수 있다
  

Tab17

• 우리는 또한 하이퍼파라미터와 함께 더 잘 쓰이는 데이터셋에서의 shorter한 결과도 다음 표에서 보인다.
• using sparse attention does not hamper performance either임을 보였다
  

5 Experiments: Genomics

• genomics data [86, 106, 13]에서 딥러닝을 사용하는 것이 최근 upsurge를 보였다.
  • several biologically-significant tasks(promoter site prediction [71], methylation analysis [55], predicting functional effects of non-coding variant [109], etc.)에서 성능 향상을 보였다
• 이런 방식들은 인풋으로서 DNA sequence fragments를 사용해서, 우리는 BIGBIRD에서 더 긴 인풋 시퀀스를 다루는 것이 많은 기능적인 효과에서 더 이점일 것임을 믿는다(DNA에서의 많은 functional effects가 꽤 non-local해서)
• 더 나아가 NLP에서 영감을 얻어 우리는 DNA fragments로부터 powerful contextual representations를 배운다(MLM pretraining을 abundant unlabeled data를 사용해서)
  • e.g. human reference genome, Saccharomyces Genome Database
• 다음으로 우리는 우리의 긴 input BIGBIRD가 두 downstream task에서 pretraining임을 보인다

Detailed experimental setup for the two tasks are provided in App. F

Pre-training and MLM

• base pairs를 operating 하는 것 대신에, Liang [58]이 연구한대로, 우리는 먼저 DNA를 tokens로 segment해서, context lenght를 상승시킬 것을 제안한다(App. F, Fig. 7)
  
• 특히 우리는 32K사이즈인 DNA sequence를 위해 byte-pair encoding [50] table를 만든다
  • 각 토큰은 평균적으로 8.78 base pairs를 나타낸다
• 우리는 이 토큰들의 contextual representation 을 MLM objective을 사용해서 human reference genome (GRCh37)에서 학습한다
• 그리고 우리는 bits per character (BPC)를 Tab5에 보고한다
  
• 우리는 DNA contextual representation에 기반을 둔 attention이 BPC를 향상하지 않음을 알아차린다, 이는 오히려 긴 문맥을 사용해서 향상된다

Promoter Region Prediction

• promoter는 DNA region으로서 특히 gene의 upstream에 위치해있다
  • transcription initiation의 site이다
• 많은 비법들이 주어진 DNA sequence [99, 59, 11, 98, 71]에서 promoter regions를 알아차리고자 제시되었다
  • 그것이 gene regulation을 이해하는 첫번째 중요한 방법이기 떄문이다
• 그에 상응하는 머신러닝 테스크는 주어진 DNA fragment를 promotor 또는 non-promoter로서 classify하는 것이다
• 우리는 Oubounyt et al. 에 의해서 compile된 dataset을 사용하는데 그것은 Eukaryotic Promoter Database (EPDnew)에 의해서 만들어졌다
• 우리는 위처럼 사전훈련된 BIGBIRD model을 finetuning한다
  • 훈련데이터를 사용하고 테스트데이터에 F1을 보고한다
• 우리는 우리의 결과를 이전에 보고된 best method와 비교한다(Tab6)
  
• 그를 통해 우리는 BIGBIRD가 이전의 최고 정확도보다 5% 상승하며 거의 최고의 정확도임을 본다.

Chromatin-Profile Prediction

• DNA의 Non-coding regions들은 proteins를 위해 code하지 않는다
• single-nucleotide polymorphism과 연관된 대다수의 질병들과 다른 속성들은 non-coding genomic variations [109, 46]와 연관이 있다.
• 그러므로, DNA의 non-coding regions를 이해하는 것은 중요한 태스크다.
• 해당 과정에서 중요한 부분은 Zhou and Troyanskaya에 의해 정의된다
  • 그것은 non-coding genomic sequence로부터 large-scale chromatin-profiling을 예측하는 것이다
  • 이런 취지로 DeepSea [109]는 Encyclopedia of DNA Elements (ENCODE)5
    and Roadmap Epigenomics projects에서의 2.4M non-coding variants의 919 chromatin-profile을 엮었다.
  • 그에 상응하는 ML task는 주어진 DNA의 non-coding region에 대해서 690 transcription factors (TF) binding profiles for 160 different TFs,
    125 DNase I sensitivity (DHS) profiles and 104 histone-mark (HM) profiles를 포함한 919 chromatin-profile를 예측하는 것이다.
• 우리는 DNA fragments의 sequence 대해서 functional effects를 예측하기 위해서 919 binary classifiers를 jointly하게 학습했다
• 베이스라인과 비교한 AUC는 Tab7에 있다
  
• harder task인 HM에서 더 성능 향상을 보였다
• 다른 것보다 longer-range correlations라고 알려진

F Genomics experiments details

F.1 Pretraining

figure 7을 보면, raw DNA 데이터셋에서 masked language modeling data가 어떻게 생성되는지 볼 수 있다. Raw DNA sequnece가 무작위로 분할되어서 50-100개의 문장을 가진 문서를 만든다(이 때 각 문장은 500-1000개의 pairs를 가지고 있다) 그렇기에 각 문서는 25000개에서 1000,000ro의 DNA 연속 가닥을 가지고, 해당 과정을 10번 반복해 각 염색체에 대해서 20개 세트의 문서가 작성된다. 그 다음 평균 8bp의 토큰으로 만들어진 sentencepiece가 문서에 전달된다. 그 후, 사전 훈련을 위해 마스킹된 언어 모델을 사용하고 토큰의 10%를 마스킹했으며 마스킹된 토큰을 예측하는 훈련을 했다

• 여기서 A, T, C, G, N은 sentencepiece [50] tokenization의 결과로 5개의 문자로 나타냄(four for bases - A, T, C, G and one for missing symbol N)
• a byte pair encoding table of size 32k, with each token representing 8.78 base pairs

  BPC(bits-per-character)
  문자를 인코딩하는 데 필요한 평균 비트 수의 양을 정확히 측정한다.
  압축 방법의 성능을 측정한 것이기 때문에 문자 당 비트 수가 적을수록 압축 방법이 더 효과적이다.
  생성 언어 모델을 압축에 사용하고 높은 효율성의 결과가 나오면 정확성이 높다고 나타낸다.
  즉, 모델이 좋으면 문자를 정확하게 예측하여 bit squence가 짧아지기 때문에 문자당 총 비트 수가 낮다.(= BPC가 낮을수록 모델의 성능이 좋다.)

ablation study로서 긴 문맥에서 더 좋은 향상을 가져온다는 것을 입증하고자 다른 길이의 시퀀스로 하여 정확도를 평가한 결과가 fig8에 나와있습니다. 논문에 따르면 긴 문맥은 final accuracy를 높여줄 뿐 아니라, 학습을 빠르게 이끌어주기도 한다고 합니다.

F.2 Promoter Region Prediction

F.3 Chromatin-Profile Prediction

6 Conclusion

BIGBIRD: a sparse attention mechanism that is linear in the number of tokens

• theoretical results 몇 가지를 만족
  • sequence to sequence functions의 universal approximator이며, Turing complete하다
  • 이론적으로 우리는 모델의 expressive powers를 보존하고자 extra global tokens를 사용했다
  • 우리는 sparse attention mechanism으로의 이동이 cost를 초래함을 보이면서 이 결과를 보완했다
• 경험적으로 BIGBIRD는 question answering and long document classification 같은 NLP task에서 state-of-the-art performance를 보인다
• 우리는 더 나아가 DNA를 위해 attention 기반의 contextual language model를 소개하고 그것을 promoter region prediction 같은 down stream tasks를 위해 파인튜닝하고, non-coding variants의 이점을 예측했다.

논문의 좋은 점, 아쉬운 점, 흥미로운 점 등등

• 좋은 점: 42쪽의 분량으로 인해서 어펜딕스가 풍부하다 !!! 그 덕에 궁금한 부분이 있다면 어펜딕스에서 그 어려움을 해결할 수 있다(다만, 수학적인 내용과 기본 지식을 알고 있다는 전제 하에 논문이 작성된 것 같아서 이해가 많이 어려울 수도 있다)
• 아쉬운 점: 내용이 어렵다,,, 예전에 Attention is all you need 논문을 3주 가량 공부했는데 그만큼 시간이 주어지지 못해 이해하지 못한 부분이 많다는 점에서 아쉬움이 남는다
• 흥미로운 점: Transformer가 NLP에 끼친 영향이 어마어마 하다는 것은 알고 있었지만, 정말 그 이상이구나 싶었고, 그로 인한 다양한 연구들이 진행되어왔다는 현행 상황들까지 살펴볼 수 있어서 좋았다 !!!