[논문 리뷰] Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting

이 글은 아래의 논문을 참고하여 리뷰한 것이다.

Informer" target="_blank" rel="noopener" data-mce-href="http://Informer">http://Informer

Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting

 

Abstract

최근 Transformer를 기반으로 long sequence의 시계열을 예측하는 새로운 모델들이 많이 제안되고 있다. 그러나 여전히 Transformer를 long sequence time-series forecasting(LSTF)문제에 적용하는 데에 quadratic time complexity(이차원적 시간 복잡성), high memory usage(고용량 메모리 사용), 내재적 인코더-디코더 아키텍처의 한계(inherent limitation of the encoder-decoder architecture) 등의 치명적인 문제점들이 존재한다. 위 논문에서는 이러한 문제들을 해결하기 위해 시계열 데이터에 대한 연산 complexity를 낮추면서 효과적이고 빠르게 예측을 수행할 수 있도록 하는 방법론을 적용한다.

 

1) ProbSparse Self-Attention mechanism

2) Self-Attention distilling

3) Generative Style Encoder

 

1. Introduction

◈ Short Sequence Forecasting   VS.   Long Sequence Forecasting

 

 

(a) : Short Sequence Forecasting 과 Long Sequence Forecasting 간의 차이점 

(b) : 예측 Sequence Length에 따른 MSE와 예측 속도 비교

• Length가 48이상인 구간에서 MSE가 급격히 증가
• 마찬가지로 예측 속도 역시 가파르게 낮아짐, length가 길어질수록 추론 속도가 느려짐

 

◈ LSTF의 주요 Challenge

• Long Sequence에 대한 예측 Capacity를 향상시키는 것
  1. Long-range Alignment Ability (길이가 긴 범위에 대한 정렬 능력)
  2. Efficient Operations on Long Sequence input/ouput (긴 시퀀스 데이터의 입출력에 대한 효율적 처리)

 

최근 Transformer는 1번 과제에 대해서는 RNN이나 CNN등의 모델들보다 우수한 결과를 보이고 있다. Transformer 모델은 Attention Mechanism을 사용하는 구조로, 일반적으로 RNN이나 CNN보다 long-range를 잘 포착한다.

 

그러나 Self-Attention Mechanism도 2번 과제에 대해서는 만족스럽지 못한 결과를 보인다. 이는 L - length를 가진 input/output에 대해 L-quadratic $(L^2)$한 연산과 메모리 사용 때문.

 

 

★ LSTM을 수행하기위한 Transformer 활용 방안

• long-range dependency 장점 유지
• self-attention mechanism의 연산, 메모리, 속도 효율 개선
• prediction capacity 향상

 

기존의 Transformer 모델을 연산, 메모리, 구조적 측면에서 효율적으로 향상시키면서 높은 예측 성능을 발휘하게끔 할 방법이 있을까?

◈ Transformer의 한계점

1. The quadratic computation of self-attention
   • Vanilla Transformer의 self-attention에서 각 layer의 내적 연산의 시간 복잡도가 $O(L^2)$
2. The memory bottleneck in stacking layers for long inputs
   • $J$개의 encoder/decoder layer에 대해 시간 복잡도는 $O(J \times L^2)$를 따르고, 이는 long sequence에 따른 모델의 확장성의 한계점으로 작용함
3. The speed plunge in predicting long outputs
   • Vanilla Transformer의 dynamic decoding 방식은 step-by-step decoding을 수행하므로, 느린 속도를 보임 

 

◈ 선행연구와 그 한계점

 

1) Sparse Transformer, LogSparse Transformer, Longformer

• 휴리스틱한 방법론을 바탕으로 self-attention mechanism의 복잡도를 $O(LlogL)$로 줄인 모델
• 1번의 한계점만 보완

2) Reformer

• 복잡도를 $O(LlogL)$로 줄이고, 메모리 효율 개선
• 극단적으로 긴 sequence에만 특화

3) Linformer

• 선형복잡도 $O(L)$을 가지는 attention 기법 제안
• 여기서 쓰이는 projection matrix는 현실의 long sequence에 대한 확장성을 갖기 힘듦

 

따라서 전반적인 선행연구들도 위 세 가지 한계점 중 1번 한계점에 대해서만 보완을 하고 있을 뿐, 나머지 두 한계점에 대한 대안은 뚜렷하지 않다고 볼 수 있다.

 

 

★ Informer의 해결책

1. Transformer 모델을 기반으로 하여 LSTF 문제에서 long-range dependency를 잘 학습시킴과 동시에 prediction capacity를 향상시킨 모델
2. ProbSparse Self-Attention Mechanism을 제안하여 시간복잡도를 $O(LlogL)$로 줄임
3. Self-Attention distilling을 제안함으로써 주요 feature를 추출하기 위한 stacking layer의 총 공간 복잡도를 $O((2-\epsilon)LlogL)$로 감소시켜 long sequence 입력을 받아들이기 용이하게 함
4. Generative Style Decoder를 제안함으로써 오직 하나의 forward step만으로 long sequence 출력을 얻을 수 있도록 함

 

2. Preliminary 

⊙ LSTF 문제 정의

• Input: $X_t$ = $\left\{x_{1}^{t}, x_{2}^{t},...,x_{Lx}^{t} | x_{i}^{t} \in R^{dx}\right\}$
• Output: $Y_t$ = $\left\{y_{1}^{t}, y_{2}^{t},...,y_{Ly}^{t} | y_{i}^{t} \in R^{dy}\right\}$

⊙ Input Representation

• Uniform input representation
• Global positional context와 Local temporal context를 잘 반영
• Scalar는 input $x_{i}^{t}$를 $d_{model}$ 차원으로 projection 시킨 값
• Local Time Stamp는 일반적인 Transformer의 Positional 방식으로 fixed 값 사용
• Global Time Stamp는 학습 가능한 embedding 사용

 

 

3. Methodolgy

◈ Informer의 Encoder와 Decoder 구성

 

Part 1. Efficient Self Attention Mechanism

▶ Vanilla Transformer의 Attention Mechanism

$$ A(Q,K,V) = Softmax(\frac{QK^T}{\sqrt{d}})V$$

 

▶ 위 수식을 $i$번째 행 벡터 단위로 쪼개 본다면, $i$번재 query에 대한 attention은 다음과 같이 정의

$$A(Q,K,V) = \sum_{j}^{}\frac{k(q_i, k_j)}{\sum_{l}^{}k(q_i, k_l)}v_j = E_{p(k_j|q_i)}[v_j]$$

 

• Quadratic한 횟수의 내적 연산과 $O(L_qL_k)$만큼의 메모리 사용 필요

 

◈ Informer의 새로운 Selective Strategy

 

 

 

> 'Sparsity'한 self-attention은 long-tailed 분포를 띔

> 이는 소수의 내적 값들만이 주요 어텐션에 기여하고 나머지 내적 값들은 영향력이 낮은 어텐션을 생성한다는 것

 

 

핵심 아이디어: 어떻게 유의미한 dot-product pair를 구분할 것인가?

▶Query Sparsity Measurement

• 유의미한 query(i) - key(j) pair들의 분포는 균등분포로부터 상이함
• 만약 $p(k_j | q_i)$의 분포가 균등분포인 $q(k_j | q_i) = \frac{1} {L_k}$에 근사한다면, self-attention score로 value $V$를 가중합 할 때 낮은 영향력을 주고, 불필요한 query로 인식된다. 따라서 p분포와 q분포의 유사도로 중요한 query를 구분할 수 있다.

 

◎ p- 분포 와 q- 분포의 유사도는 Kullback-Leibler divergence로 계산

$$KL(q||p) = ln\sum_{l=1}^{L_k}e^{q_ik_j/\sqrt{d}}-\frac{1}{L_k}\sum_{j=1}^{L_k}\frac{q_ik_j^{T}}{\sqrt{d}}-lnL_k$$

 

◎ KL-div 식을 바탕으로, $i$번째 query에 대한 sparsity 정도 측정 방법 정의

$$M(q_i, K) = ln\sum_{j=1}^{L_k}e^{q_ik_j/\sqrt{d}}-\frac{1}{L_k}\sum_{j=1}^{L_k}\frac{q_ik_j^{T}}{\sqrt{d}}$$

 

만약 $i$번째 query의 $M(q_i, K)$값이 크다면, 그 attention probability $p$는 다양한 확률 값을 갖게 되므로 유의미한 dot-product pair가 될 확률이 커진다.

 

 

 

◈ ProbSparse Self-Attention이란? 

앞선 측정지표를 바탕으로 유의미한 top-u개의 query만 택하여 attention을 계산

$$ A(Q,K,V) = Softmax(\frac{\overline{Q}K^T}{\sqrt{d}})V$$

• 여기서, $\overline{Q}$는 sparse matrix(희소행렬)이며, Top-$u$개의 query만으로 구성 
• $u$는 하이퍼 파라미터인 sample factor $c$와 $lnL_q$의 곱인 $u = c \times lnL_q$
• 오직 $O(lnL_q)$만큼의 query에 대해서만 내적 연산 수행, $O(L_klnL_q)$만큼의 메모리 소요

 

위 논문에서는 $M(q_i, K)$값을 효율적으로 계산하기 위해 다음과 같은 식을 사용. 

$$ M(q_i, K) = \max_{j}\left(\frac{q_i k_j}{\sqrt{d}}\right) - \frac{1}{L_k} \sum_{j=1}^{L_k} \frac{q_i k_j^T}{\sqrt{d}} $$

 

[개인적인 해석] : $max$ operator를 사용한 것은 분포 차이를 극대로 하는 값을 기준 삼아 유의미한 query를 더욱 잘 선정하기 위함이 아닌가 생각함

 

▶여기서 잠깐! 그렇다면 key $j$에 관한 max 값은 어떻게 구하지?

• Prob. 모든 key $j$들에 대해 내적을 구하는 것은 $O(L_{k}L_{q})$만큼의 quadratic한 연산을 해결하지 못함
• Sol.  Key를 sampling 하여 query 중요도 $M(q_i, K)$을 구하는 데 사용

$M$ 계산에 사용되는 Sample의 수는 $U* = c\times lnL_k$ 개

 

위와 같이 query의 중요도 계산을 마치고 이를 기준으로 top-$u$개 query를 선택하면, 이들과 모든 key set에 대해 attention을 구한다. 이렇게 구하고 나면 attention의 결과는 크기 $u \times L_k$ 인 matrix가 나온다. 

 

 

Part 2. Encoder: Allowing for Processing Longer Sequential Inputs under the Memory Usage
Limitation

 

1.  seq_len = $L = L_q = L_k = L_v = 96$
2.  $d_{model} = 512$
3.  no. of heads = $h = 8$  
4.  no. of variables = 7
5.  no. of stamp types = 4

 

◈ Encoder Embedding

• Scalar Embedding과 Stamp Embedding을 더하여 최종 Embedding 구성

 

◈ Self Attention distilling

• ProbSparse self-attention 후, convolution과 max-pooling을 통해 distilling 수행
• Attention output으로 부터 주요한 정보만을 추출하여 다음 layer에 전달할 정보를 구성하기 위함

▶Multi head self-attention

• 각 head별 query, key, value는 $d' = d/8$ 차원을 갖도록 projection됨 ($d' = 64$)
• Top-$u$개의 index를 저장해주었다가 다시 [$L_q, d'$] 차원으로 맞춤
• Head 개수($h$) 별로 다양하게 뽑은 후 concatenate 시킴 : [$h, L_q, d'$] 차원

▶1D Conv. & Max Pooling → Distilling

• [$h, L_q, d'$] 차원을 다시 projection하여 [$L_q, d_{model}$]차원으로 변환
• 변환된 행렬을 1D Convolution과 Max-pooling을 이용해 절반 크기로 줄이는 과정을 반복

$$ X_{t}^{j+1} = \text{MaxPool}\left( \text{ELU}\left( \text{Conv1d}\left( \left[ X_{t}^{j} \right]_{AB} \right) \right) \right)$$

 

이렇게 하면 총 메모리 사용량을 $O((2-\epsilon)LlogL)$로 감소시키는 효과! $\epsilon$은 매우 작은 양수

 

 

◈ Stacking Layer Replicas

• Robustness 향상을 위해서 원래 input의 절반의 길이만큼만 다음 input으로 받는 복제된 encoder 추가 구성
• 각 encoder 별로 생성되는 output feature map의 dimension을 맞추기 위해 오른쪽 그림처럼 self-attention distilling layer 수를 하나씩 점진적으로 감소
• 여러 개의 stack encoder를 거친 output들은 concatenate 되어 최종적으로 encoder의 hidden representation을 구성
• 최근 시점 기준으로 input sequence를 절반씩 잘라서 사용

 

 

Part 3. Decoder: Generating Long Sequential Outputs Through One Forward Procedure

• One forward procedure로 Generative Inference를 수행하는 decoder 구성
• Attention을 통해 출력된 결과는 Fully-Connected Layer를 통해 최종 output 예측
• Loss는 MSE 사용

 

4. Experiment Results

 

1. Informer 모델이 대부분 Case에서 우수한 성능을 보임
2. RNN이나 CNN 기반의 모델보다 더 나은 결과를 보임
3. 다변량 예측에서는 단변량과 달리 성능 차이의 폭이 작음. 이는 feature 수가 많다는 점, 그래서 prediction capacity가 증가할 수 있다는 점과 연관이 있는 것으로 보임