[Paper Review] Informer: Beyond Efficient Transformer for Long Sequence Time Series Forcasting

Informer는 AAAI-21 Outstanding Paper Award에 선정된 논문으로 장기 시계열 예측에서 좋은 성능을 보인 논문입니다. 회사에서 informer로 시계열 예측을 하는 리서치 업무가 있었기 때문에 본 논문을 리뷰해보겠습니다.
본 리뷰는 DSBA 연구실 리뷰의 도움을 굉장히 많이 받았습니다.

1. Overview

• Informer는 Transformer기반으로 한 Long Sequence의 시계열 예측을 수행하는 모델입니다.
• Attention의 연산 복잡도를 낮추고 효과적이고 빠르게 예측을 수행할 수 있도록 하는 방법론을 제안했습니다.
  • ProbSparse self-Attention Mechanism
  • Self-Attention Distilling
  • Generative style Decoder

2. Introduction

2.1 시계열 예측을 위한 딥러닝 모델 종류 및 특징

1. RNN Based Models
   • 시계열 데이터에 적용된 딥러닝 모델 중 가장 고전적인 접근 방법입니다.
   • 내부적으로 순환이 되는 구조를 지닌 RNN은 이전 시점의 정보를 현재 시점 정보 계산에 활용할 수 있다는 장점이 있습니다.
   • 현재 시점으로부터 멀리 떨어진 과거 시점 정보의 영향력이 약해지는 장기 의존성 문제가 있습니다.
2. CNN Based Models
   • CV분야에서 사용된 CNN 기반 모델이 시계열 데이터 모델링에도 응용됩니다.
   • 시간 순서에 따라 filter를 적용함으로써 과거와 현재 정보의 관계를 파악합니다.
   • Filter 단위로 local한 dependency를 파악하기 때문에 장기 의존성 문제가 역시 있습니다.
3. Attention Based Models
   • Trnasformer는 서로 다른 시점의 정보들 간의 관계를 바탕으로 score를 부여하여 활용하고자 합니다.
   • 현재, Transformer 기반의 모델들이 RNN 기반의 모델 성능을 뛰어넘고 있습니다.
   • Transformer 기반 모델은 self attention을 바탕으로 각 시점 정보 간의 관계를 모델링하는데, CNN, RNN 대비 장기 의존성을 학습하기 용이하다는 장점이 있습니다.

2.2 시계열 예측과 관련된 연구의 대표적인 문제

1. Long sequence time-series forecasting(LSTF)의 major challenge
   • 장기 시계열에 대한 예측 안정성을 향상시키는 것은 굉장히 도전적인 과제입니다.
2. LSTF의 예측 성능을 향상시키기 위해 필요한 것
   • input과 output간의 정확한 장기 의존성의 결합을 효율적으로 포착하여야 합니다.
   • 긴 시퀀스의 입력과 출력에 대한 효율적인 연산이 가능해야 합니다.

2.3 Transformer의 장점 및 한계점

1. Transformer 구조는 일반적으로 RNN 대비 장기의존성을 잘 포착할 수 있습니다.
2. 하지만 self-attention mechanism은 L-length를 가진 input, output에 대해 $O(L^2)$의 계산 복잡도와 메모리 사용이 불가피합니다.

2.4 Informer의 목표

informer는 Transformer의 장기의존성을 잘 포착하는 장점을 유지하면서 연산, 메모리, 속도 측면의 효율성을 개선하는 것을 목표로 합니다.

3. Related Work

3.1 Self-attention의 복잡도 문제

1. self-attention의 복잡도는 $O(T^2 \cdot D)$로 sequence가 길어지면 Bottleneck 현상이 발생합니다.
2. Structural Prior : Input에 대한 어떤 Structural Bias도 없습니다. 즉, sequence 형태의 input이기만 하면 self-attention 계산이 가능하다는 것인데 이는 장점일수도 있지만 비효율적입니다.

3.2 이를 해소하기 위한 발전

1. Sparse Attention
   • self-attention은 학습 뒤에는 볼 대상만 보게 됩니다. 그렇다면 structural bias를 부여하여 query-key 개수를 제한해보자는 아이디어입니다.
2. Sparse Attention의 공통 주장
   • Computational Cost : 문장이 길어질수록 attention에 필요한 비용이 큽니다.
   • input length에 quadratic하게 증가하는 비용 대신, linear하게 증가하도록 만드는 것이 목적입니다.
   • Long range dependency : 긴 sequence에는 cost문제로 인해 transformer를 적용하기 힘듭니다.
3. Sparse Attention의 효과
   • Cost, Dependency를 감소시키면 더 긴 sequence를 input으로 활용할 수 있습니다.
   • 즉, 시계열 관점에서는 더 긴 sequence를 받아서 더 긴 sequence를 예측할 수 있습니다.

4. Informer

4.1 Informer의 해결방안

1. Transformer 모델을 기반
   • LSTF 문제에서 long range dependency를 잘 학습하게 하고 동시에 prediction capadity를 향상시킵니다.
2. ProbSparse self-attention mechanism을 제안
   • 시간 복잡도와 메모리 사용량을 $O(LlogL)$로 줄입니다.
3. self-attention distilling operation을 제안
   • stacking layer의 총 공간 복잡도를 $O((2-\varepsilon)LlogL)$로 감소시켜 long sequence input을 받아들이는 데 용이하게 합니다.
4. Generative style decoder를 제안
   • step-by-step inference 과정에서 발생할 수 있는 cumulative error를 방지하고자 합니다.

4.2 Preliminary

1. LSTF Problem 정의
   • input: $X_t= { x_1^t,…,x_{L_x}^t \mid x_i^t \in \mathbb{R}^{d_x} } $
   • Ouput: $Y_t= { y_1^t,…,y_{L_y}^t \mid y_i^t \in \mathbb{R}^{d_y} } $
   • LSTF 문제는 output length의 길이인 $L_y$가 선행 연구(~48)들 보다 길 때로 정의합니다.
2. Encoder-Decoder Architecture
   • 일반적으로 encoder-decoder 구조는 encoder를 통해 input을 받아 encoder output을 생성한 후, decoder에서 예측된 output을 순차적으로 받아 decodeing을 수행합니다.
   • 하지만 informer에서는 cumulative error를 방지하기 위해 순차적 예측이 아닌 한번의 forward step으로 예측을 진행합니다.
3. Input Representation
   • Informer의 input은 global position context정보와 local temporal context 정보를 잘 반영할 수 있도록 하는 것이 목표입니다.
   • 먼저, Scalar는 input $x_i^t$을 $d_{model}$ 차원으로 사영시킨 값입니다.
   • Local Time Stamp는 일반적인 transformer의 Positional Encoding 방식으로 고정된 값을 사용합니다.
   • Global Time Stamp는 학습 가능한 embedding을 사용합니다. 즉, 사용자가 주단위, 월단위, 휴일정보등의 정보를 추가해줄 수 있습니다.
   • 최종 input은 다음과 같습니다.

   $\begin{align} X_{feed[i]}^t=\alpha u_i^t+PE_{(L_x \times (t-1)+i)}+\sum_{p}[SE_{(L_x \times (t-1)+i)}]_p \end{align}$

4.3 Informer의 Encoder input, Decoder input 구성

1. Encoder input은 input series인 $X_{en}$으로 구성됩니다.
2. Decoder input은 start token series와 zero padding series의 concat $X_{de}={X_{token}, X_0}$ 으로 구성됩니다.

4.4 Methodology

ProbSparse Attention

Vanilla transformer의 scaled dot-product attention은 $A(Q, K, V)=Softmax({QK^T \over \sqrt{d}})V$입니다. 이 수식을 $i$번째 행 벡터로 자세히 쪼개어 본다면, $i$번째 query에 대한 attention은 kernel smoother를 활용하여 다음과 같이 정의할 수 있습니다. (여기서 kernel smoother는 query와 key의 내적을 근사하는 하나의 함수)
$\begin{align} A(q_i, K, V)=\sum_j{k(q_i, k_j) \over \sum_l{k(q_i, k_l)}}v_j=\mathbb{E}_{p(k_j|q_i)}[v_j] \end{align}$ $\begin{align} where\; p(k_j|q_i)={k(q_i, k_j) \over \sum_l{k(q_i, k_l)}}, k(q_i, k_j): asymmetric\; exp\; kernel\; exp({q_ik_j^T \over \sqrt{d}}) \end{align}$

Vanilla transformer의 방법은 quadratic한 횟수의 내적 연산과 $O(L_Q L_K)$만큼의 메모리 사용을 필요로 합니다. 선행 연구들은 성능에 유의미한 영향을 끼치지 않는 것을 제외하는 selective counting 전략을 고안합니다. 하지만 선행 연구는 query나 key를 선택할 때 잠재된 어떠한 실질적 의미 또는 역할을 고려하는 것이 아닌 단순히 random하게 또는 일정 window 구간으로 한정하는 방식 등의 전략을 사용하는 한계가 있다고 논문에서는 말하고 있습니다.

1. 제안 배경
   • Sparsity한 self-attention은 꼬리가 긴 분포를 가집니다.
   • 이는 소수의 dot-product pairs만이 주요 attention에 기여한다는 것을 의미합니다.
2. 어떻게 유의미한 dot-product pair를 구분할 것인가?
   • 유의미한 query($i$)-key(모든 $j$) pairs의 분포는 uniform 분포와 상이합니다.
   • 만약 $p(k_j \mid q_i)$ 의 분포가 uniform분포인 $q(k_j \mid q_i)=1/L_K$ 에 근사하다면, self-attention score로 value V 가중합에 trivial한 영향을 주게 되고 상대적으로 불필요한 query로 작용하게 됩니다.
   • 따라서 $p$분포와 $q$분포의 유사도는 중요한 query를 구분해 내는 지표로 사용할 수 있습니다.
3. 유사도는 어떻게 구할 것인가?

   • $p$분포 (관측된 attention 분포)와 $q$분포 (uniform 분포)의 유사도는 Kullback-Leibler divergence로 계산합니다. KL div의 상수항을 제거하여 다음과 같이 $i$번째 query에 대한 sparsity 정도 측정 방법인 $M(q_i, K)$를 정의합니다. $\begin{align} M(q_i, K)=ln\sum_{l=1}^{L_K}e^{q_ik_l^T \over \sqrt{d}}-{1 \over L_K} \sum_{j=1}^{L_K}{q_ik_j^T \over \sqrt{d}} \end{align}$

   • 즉, $i$번째 query가 큰 $M(q_i, K)$값을 가지게 된다면 그 attention 확률 $p$는 보다 다양한 확률 값을 가지게 될 것이고 유의미한 dot-product pair를 가질 가능성이 더 높습니다.
   • 앞서 sparsity 측정 지표를 바탕으로 유의미한 query를 top-u개만 선택하여 attention을 계산합니다. $\begin{align} A(Q,K,V)=Softmax({\bar{Q}K^T \over \sqrt{d}})V \end{align}$ 여기서 $\bar{Q}$는 측정지표인 $M(q_i, K)$값을 기준으로 하여 top-u개의 query만으로 구성된 sparse matrix입니다.

결국 ProbSparse self-attention은 오직 $O(lnL_Q)$만큼의 query에 대해서만 dot-product 연산을 수행하게 되며, $O(L_KlnL_Q)$만큼의 memory를 사용하게 됩니다. Multi-head 관점에서 보면, 각 head별로 각기 다른 query-key 쌍을 생성하게 되기 때문에 sampling으로 인한 심각한 정보 손실을 방지할 수 있는 효과를 가집니다.
하지만, 결국 top-u개의 유의미한 query를 잘 추출하기 위해서는 $M(q_i, K)$값을 모두 하나씩 계산해보아야 합니다. 이는 $O(L_KlnL_Q)$ 연산을 하기 위해서 $O(L_QL_K)$만큼의 quadradic한 연산이 필수적이게 되는 것입니다. 그래서 본 논문에서는 효율적으로 query sparsity 정도인 $M(q_i, K)$를 측정할 수 있는 emprical approximation 방법론을 제안합니다.

$\begin{align} \bar{M}(q_i, K)=max_j{q_ik_j^T \over \sqrt{d}}-{1 \over L_K} \sum_{j=1}^{L_K}{q_ik_j^T \over \sqrt{d}} \end{align}$

Encoder

Informer의 encoder embedding은 scalar embedding과 stamp embedding을 더하여 구성하게 됩니다. 그 이후, embedding vector는 ProbSparse self-attention을 거친 후 Conv와 Max-pooling을 통해 distilling을 수행합니다. 이는 attention output에서 주요한 정보만을 추출하여 다음 layer에 전달할 정보를 구성하기 위함입니다.

Decoder

decoder의 masked self-attention은 encoder와 같이 probsparse self-attention을 적용하였고, encoder-decoder attention은 vanilla transformer와 동일한 attention을 사용했습니다. attention을 통해 출력된 output은 generative하게 출력되기 위해 FC-layer를 거쳐 최종 output을 예측하게 됩니다.

정리

본 논문은 transformer를 이용한 장기 시계열 예측 모델로 기존 모델들보다 성능향상을 크게 향상시켰다는 점에서 큰 의의가 있습니다. 하지만 시계열 데이터의 feature를 추출하는 과정에서 많은 분석이 없다는 점에서 한계가 있다고 생각됩니다.