A Survey of Transformers - 中

본 포스트는 arXiv에 2021년 1월에 업로드된 'A Survey of Transformers'의 내용을 요약, 정리하였습니다.
이전 포스팅(A Survey of Transformers - 上)에서 이어지는 내용입니다.

A Survey of Transformers

2. Architectural modification : Self-Attention

2.2 Linearized Attention

Self-attention에서의 계산식은 $(QK^T)V$입니다. 이는 sequence length(T)의 제곱인 $O(T^2)$의 계산 복잡도를 가지는 것이 단점이라고 할 수 있습니다. 이 단점을 해결하기 위해 attention의 계산 복잡도를 $O(T)$로 낮추기 위한 다양한 시도가 있었습니다. 

$QK^T$의 식을 $Q^{'}K^{'T}$로 분리 가능하다면, $Q^{'}K^{'T}V$는 $Q^{'}(K^{'T}V)$의 순서로 연산할 수 있고, 이를 통해 $O(T)$의 계산 복잡도가 가능해집니다.

Linearized attention은 matrix $exp(QK^T)$를 $\phi(Q)\phi(K)^T$($\phi$ : feature map)로 대체하고, 위의 그림 (b)처럼 $\phi(Q)(\phi(K)^TV)$의 연산 과정을 거칩니다.

Linearized attentnion을 적용하면 기존 vanila attention 공식인

$z_i = \sum_j\cfrac{sim(q_i,k_j)}{\sum_{j'}sim(q_i,k_{j'})}v_j$을 $z_i = \cfrac{\phi(q_i)\sum_j\phi(k_j) \otimes v_j}{\phi(q_i)\sum_{j'}\phi(k_{j'})^T}$ ($\otimes$ : outer product)로 변경할 수 있습니다.

이 방법에는 두 가지의 중요한 요소가 포함되어 있습니다.

2.2.1. Feature map $\phi(\cdot)$

Feature map을 사용하는 목적은 dot product 연산을 근사화 하려는 것이 아닌, standard Transformer와 동등한 결과를 얻기 위해 경험적으로 사용합니다.

Linear Transformer는 간단한 feature map인 $\phi_i(x) = elu(x_i)+1$를 사용합니다. Performer는 Transformer의 scoring function을 근사화 하기 위해 random feature map을 사용합니다. 그 밖에도 다양한 feature map이 사용되고 있습니다.

2.2.2. Aggregation rule

$\phi(k_j) \otimes v_j$는 간단한 연산을 통해 이루어집니다. 여러 연구에서도 이러한 aggregation 방식이 사용되었지만, 새로운 관계들이 추가될 때 기존의 관계를 선택적으로 삭제한다면 더 효율적일 것이라는 접근으로 다양한 연구가 진행되었습니다.

2.3 Query Prototyping and Memory Compression

Sparse attention과 kernel function을 기반으로 한 linearized attention 이외에 attention의 복잡도를 줄일 수 있는 방법은, query prototyping과 memory compression 방법을 사용해 query의 개수 또는 key-value쌍의 개수를 줄이는 것입니다.

2.3.1. Attention with Prototype Queries

Clustered Attention은 query들을 몇 개의 clueter로 구분하고, centroid cluster를 query로 하여 key vectory와 attention을 연산합니다. 특정 cluster에 속한 query들은 동일한 attention 분포를 가지게 됩니다.

Informer는 query들로 부터 prototype을 선택하기 위해 query sparsity measurement를 사용합니다. 이 지표는 쿨백-라이블러 발산을 변형해 query의 attention 분포와 이산 균등분포 사이 분산을 계산합니다.

2.3.2. Attention with Compressed Key-Value Memory

Memory Compressed Attention(MCA)은 strided convolution을 사용해 key와 value의 개수를 줄이는 방식을 사용합니다. 이 방법을 사용하면, local attention이 아닌 global context를 반영한 attention을 vanila transformer와 동일한 계산 비용으로 얻을 수 있다는 장점이 있습니다.

Set Transformer와 Luna는 external node를 활용해 입력 정보들을 추상화하고, 더 압축된 메모리 공간에 정보를 표현합니다. 그 밖에 Linformer, Poolingformer 등 다양한 architecture에서 key와 value를 작은 메모리 공간에 추상화하는 방법을 사용합니다.

2.4 Low-rank Self-Attention

몇가지 분석에서 self-attention matrix $A \in R^{T \times T}$가 항상은 아니지만, 자주 low-rank의 특징을 가진다는 것이 발견되었습니다. 이 특성을 활용해 두 가지 방식을 적용할 수 있는데, 하나는 , 다른 하나는 self-attention matrix가 low-rank approximation에 의해 대체될 수 있다는 것입니다.

2.4.1 Low-rank Parameterization

Attention matrix의 rank가 sequence length보다 작다는 것은($D_K > T$), overfitting의 가능성이 증가합니다. 그렇기 때문에 Attention matrix의 rank($D_K$)에 한계를 두어 low-rank attention module로 분해합니다.

이를 통해 긴 범위의 상호작용을 표현할 수 있고, 지역적인 의존성은 band attention을 사용해 표현합니다.