[논문 리뷰] Big Bird: Transformers for Longer Sequences, 2020
https://arxiv.org/pdf/2007.14062.pdf
Abstract
BERT와 같은 transformer-based model은 NLP 분야에서 가장 좋은 성능을 내는 model 중 하나이다.
하지만 이 model의 가장 큰 단점은 full-attention mechanism을 사용하기 때문에, sequence length에 대한 한계점이 존재한다는 것이다.
따라서 이 논문에서 제안한 BIGBIRD model은 sparse attention을 제안하여 quadratic dependency를 linear하게 줄일 수 있도록 하였다.
BIGBIRD는 기존 model들과 동일한 하드웨어를 사용하였을 때 8배 정도 긴 sequences를 처리할 수 있다고 한다.
Introduction
기존 transformer model은 self-attention 구조를 이용하여 RNN에서의 sequential dependency를 제거하면서 parallel하게 input sequence를 연산할 수 있다는 점은 다른 model들과 비교하였을 때 outperformance를 낼 수 있도록 하였다.
하지만 sequence length의 제곱에 비례하는 computational, memory requirement 때문에 corpus가 길어지면 application이 매우 제한적이게 된다. 보통의 경우 512 token들을 input으로 다룰 수 있다.
이 논문의 contribution은 다음과 같다.
1. BIGBIRD는 full transformer의 이론적 특성을 모두 만족한다.
추가적인 token들을 추가함으로써 O(n)의 inner-product를 달성할 수 있다.
2. BIGBIRD는 QA, summarization task에서 SOTA의 성능을 낸다.
BIGBIRD Archictecture
X : Input Sequence
Directed Graph D에 대해
vertex set : token [n] = {1,...,n}
edge set : set of inner products that the attention mechanism will consider
N(i) : node i 의 out-neighbors
만약 Graph D가 complete digraph인 경우에, full quadratic attention mechanism으로 recover 할 수 있다.
여기서 exposition을 간단히 하기위해 graph D의 인접행렬 A를 이용하여 계산을 진행하는데,
BERT와 같이 full-attention을 사용하는 경우에는 A의 모든 값이 1로 채워져 있다. 때문에 모든 칸들이 서로 연결되어 있기 때문에 quadratic한 복잡도가 만들어진다.
self-attention을 fully connected graph로 생각하는 idea는 complexity를 줄일 때 graph theory를 적용할 수 있음을 의미한다.
이제 self-attention의 quadratic complexity를 graph sparsification problem으로 볼 수 있다는 것이다.
random graph을 사용하면 특성 성질에 의해 complete graph로 근사할 수 있기 때문에, attention mechanism으로 만들어진 sparse random graph에서도 full attention의 성질을 나타낼 수 있도록 하는 방법을 제시한다.
(1) Small average path length between nodes
Erdos-Renyi model로 edge가 선택될 확률이 고정된 확률값에 의해 결정되는 가장 간단한 random graph를 생각해보자
그 중 가장 짧은 path는 node의 개수에 logarithmic하기 때문에, graph의 node(token)이 많아지더라도 shortest path가 천천히 늘어난다는 것을 확인할 수 있습니다.
이는 또한 두번째 eigenvalue와 첫번째 eigenvalue가 멀리 떨어져 있기 때문에
graph 사이를 random하게 walks할 수 있는 mixing time을 빠르게 만들 수 있고, 결국 어떤 node pair든 상관없이 node 사이의 정보가 빠르게 흐를 수 있다는 것을 의미한다.
Big BIRD에서는 attention시에 하나의 query q가 r개의 random key를 가지고 연산하는 것으로 제안하였다.
(2) Notion of locality
대부분의 NLP task와 computational biology data에서 발생하는 특징 중 하나인 Locality of Reference에 대해 살펴보자
이 현상은 어떤 token에 대해 정보를 얻으려 할 때 대부분의 정보가 neighbor token에서 얻어진다는 것이다.
이러한 현상은 neighboring inner-product가 매주 중요한 영향을 미친다고 한다.
여기서 그래프 이론을 적용시켜 보자면 connectivity의 locality를 측정하는 지표인 'clustering coefficient'를 이용할 수 있다.
coefficient가 높다면 그래프는 많은 clique나 near-clique(거의 대부분이 서로 연결되어 있는 subgraph)를 가지고 있다는 것을 의미한다.
위에서 사용했던 Erdos-Renyi random graph는 낮은 coefficient를 가지고 있지만, small world graph로 아렬진 class of random graph에서는 높은 coefficient를 가지고 있다.
BIGBIRD에서는 해당 token과 양 옆 w/2개씩의 attention을 계산하여 적용시킬 수 있다.
위에서 언급한 방법들을 모두 사용하여 간단한 실험을 해본 결과 기존 BERT의 성능을 내지 못했다고 한다.
여러 실험을 거친 후, 'global token'(fig 1.c)이 중요하다는 것을 파악한 후 아래 언급할 두가지 방법으로 활용할 것을 제안하였다.
- BIGBIRD-ITC(Internal Transformer Construction)
sequence에 있는 단어들 중 일부를 'global token'으로 정의하여 다른 모든 sequence와 attention을 수행할 수 있도록 한다.
- BIGBIRD-ETC(Extended Transformer Construction)
g개의 [CLS]와 같은 token을 sequence에 추가하고, 이를 global token으로 사용하여 attention을 계산한다.
BIGBIRD의 최종 attention mechanism은 세가지의 properties들로 구성되어 있다.
- r개의 random key와 query 사이의 attention 수행
- 양 옆 w/2개의 key와 query 사이의 attention 수행
- g개의 global token을 이용하여 attention 수행
Conclusion
이 논문에서는 token의 수에 따른 linear attention mechanism을 제시하였다.
또한 추가적인 global token이 model의 power에 큰 영향을 미친다는 것을 파악할 수 있었다.
이 모델은 QA, long document classification과 같은 NLP task에서 SOTA의 성능을 내었다.