Beyond efficient transformer for long sequence time-series forecasting

안녕하세요.😊

이번 게시글은 제가 informer에 대해 공부한 내용을 기록한 것입니다. 고려대학교 DSBA 연구실 김수빈님의 자료를 참고하여 작성했습니다.

Overview

[그림 1] informer architecture

Informer 논문에서는 Transformer를 기반으로 long sequence의 시계열 예측을 수행하는 새로운 모델을 제안했습니다.

해당 논문은 시계열 데이터에 대하여 연산 complexity를 낮추면서도 효과적이고 빠르게 예측을 수행할 수 있도록 하는 방법론을 적용했습니다. 다음의 세 가지 방법론을 사용했습니다.

1. ProbSparse self-attention mechanism
2. Self-attention distilling
3. Generative style decoder

논문은 1, 2번을 통해 현실적으로 연산 complexity를 낮췄고, 3번 방법을 통해 error accumulation 방법을 해결했습니다.

Introduction

[그림 2] attention architecture

과거 시계열 예측을 위한 딥러닝 모델의 종류는 크게 세 가지가 있습니다.

1. RNN-based model
2. CNN-based model
3. Attention-based model

이 중 attention-based model은 필요한 정보를 집중해서 보는 Attention 구조를 사용했습니다. Attention 구조를 활용한 Transformer 기반의 모델이 여러 task에서 RNN-based model보다 좋은 성능을 보이고 있습니다. Transformer 기반 모델은 self-attention을 바탕으로 long range dependency를 학습하기 용이하다는 장점이 있습니다. 

• long-term dependency: 장기 의존성 문제란 입력과 출력층의 거리가 멀어질 수록 연관 관계가 줄어드는 문제를 말합니다.

[그림 3] short sequence forecasting vs long sequence forecasting

그림 (a)를 보면 단기 시계열 예측이란 짧은 기간의 미래를 예측하는 것을 말합니다. 반면 장기 시계열 예측은 상대적으로 먼 미래를 예측하는 것입니다. 그림 (b)에서 LSTM을 사용해 장기시계열 예측한 결과입니다. Sequence length가 길어질 수록 MSE 값은 급격하게 증가하고 추론 속도는 급격하게 느려집니다. 

이처럼 Long Sequence time-series forecasting (LSTF)의 주요 challenge는 long sequence (input/target)에 대한 prediction capacity를 향상 시키는 것입니다.

LSTF 문제 해결을 위한 prediction capacity 향상을 위해 필요한 것은 다음과 같습니다.

• (a) long range alignment ability
  • 장기간 정렬 능력이란 멀리 떨어진 미래 시점을 예측하는 능력을 말합니다. 모델이 우수한 장기간 정렬 능력을 가지고 있다면 시계열 데이터의 패턴과 추세를 잘 학습할 수 있습니다. 따라서 훈련 데이터의 범위를 넘어서는 기간을 일반화 할 수 있으며 더 긴 범위를 정확히 예측할 수 있게 됩니다.
• (b) efficient operations on long sequence input/output: 효율적인 연산

Transformer의 경우 self - attention 메커니즘 덕분에 (a) 문제를 어느 정도 해결했습니다. 하지만 self-attention 메커니즘으로 인해 $L^2$한 연산과 메모리 사용이 불가피합니다. 연산량과 메모리 사용량이 이차함수에 가까워져 길이가 길어질 수록 bottleneck 현상이 발생하게 됩니다.

Related works

Self-attention은 다음과 같은 문제점을 가지고 있습니다.

• Complexity: self-attention 메커니즘은 input sequence의 길이가 길어지면 bottleneck 현상이 발생합니다.
• Structual Prior: Input에 대한 어떤 structural bias도 없습니다. 이는 모든 input sequence에 대해 self-attention을 수행하기 때문에 과거 정보를 더욱 잘 반영할 수 있다는 장점도 있지만 모든 정보를 살펴봐야 하기 때문에 비효율적인 연산이라는 단점도 존재합니다.

위와 같은 문제점을 해결하기 위해 해당 논문에서는 Sparse Attention을 제안했습니다. Sparse attention이란 Attention에 Sparsity Bias를 추가하여 complexity를 감소시키는 방법론입니다.

Self-attention의 Sparsity

[그림 3] Sparsity

위 그림은 self-attention 결과를 나타낸 것입니다. Self-attention이 끝난 후 attention score로 행렬을 만들어보면 it 같은 경우 특정 단어에만 집중하고 대부분의 단어와는 크게 상관이 없는 것으로 나타납니다. 하얀색이 높은 attention score이고, 검은색이 낮은 attention score입니다.

이처럼 query, key간에 attention score가 높게 잡히는 것은 소수이고, 대부분의 score 값이 0에 수렴합니다. 특히 attention이 학습된 후에는 결과적으로 주목해야 하는 대상만 유효하게 사용이 되고, 다른 0에 수렴하는 attention score는 representation하는데 아무런 영향을 주지 못합니다. 따라서 Attention 후에 볼 대상만 보게 된다면 모든 대상을 보는 것이 아니라, 모든 query, key pair 중에서 어떤 pair 만을 계산할지 정해줄 수 있다면(Structural bias를 부여) 효율적인 연산이 가능할 것입니다.

Sparse Attention

Sparse Attention을 통해 비용 및 dependency를 감소시키면 512 token보다 더 긴 문당을 input으로 활용할 수 있습니다. 시계열의 관점에서는 더 긴 sequence를 받아서 더 긴 sequence를 예측할 수 있게 됩니다.

Paper review

해당 논문의 목표는 기존 Transformer 모델을 연산, 메모리, 구조적 측면에서 효율적이게 향상시키면서도 높은 예측 성능을 유지하는 것입니다.

 Transformer의 한계점

Self-attention 측면

1. Self-attention의 quadratic한 연산량 $O(L^2)$
2. 긴 input 길이에 대한 stacking layer 구조는 memory bottleneck을 발생시킴

Decoder 측면

1. Step-by-step deconding 방식의 느린 inference 속도

Informer의 해결책

1. Transformer 모델을 기반으로 하여 LSTF 문제에서 ling-range dependency를 잘 학습하게 하고 동시에 prediction capacity를 향상시킨 informer 모델을 제안
2. ProbSparse self-attention mechanism을 제안하여 시간 복잡도와 메모리 사용량을 줄임
3. Self-attention distilling operation을 제안함으로써 주요 feature를 추출하기 위한 stacking layer의 총 공간 복잡도를 감소시켜 long sequence input을 받아들이는데 용이하게 함
4. 오직 하나의 forward step만으로 long sequence output을 얻을 수 있도록 하는 generative style decoder를 제안함 이를 통해 inference 속도를 개선하고 accumulative error를 방지하고자 함

Preliminary

LSTF 문제 정의

• LSTF 문제는 output length의 길이가 선행연구(~48)들 보다 길 때로 정의합니다.

Encoder-Decoder architecture

• Informer는 순차적 예측이 아닌 한번의 forward step으로 예측을 진행합니다.

Input representation

[그림 4] Input representation of Informer

Informer는 input data를 효과적으로 학습하기 위해 여러 embedding 단계를 거칩니다. 특히 시계열 데이터인만큼 시간 정보를 충분히 학습할 수 있게 global time stamp와 local time stamp를 구합니다.

 

Informer의 encoder input과 decoder input 구성

[그림 5] encoder, decoder of informer

informer encoder input: [input series((seq_ len))]

informer decoder input: concat[start_token series((label_ len)), zero_padding series((pred_ len))]

• Input sequence length of informer encoder ((seq_ len)) : 96
• Start token length of informer ((label_ len)) : 48
• Prediction sequence length ((pred_ len)) : 24

encoder input data의 경우 스칼라에 앞서 설명한 time stamp 값을 더해 입력으로 사용합니다. 반면 decoder의 input data의 경우 scalar 값에 stamp를 더하는 것은 encoder와 동일하지만 예측할 부분의 scalar를 0으로 패딩해 사용합니다. 위 그림의 경우 96 step의 encoder input이 주어졌을 때, input의 절반을 그대로 decoder의 입력으로 사용하고 예측할 부분은 0으로 패딩해 예측합니다. 

Methodology

ProbSparse Attention

Vanilla transformer의 scaled dot-product attention은 quadratic한 횟수의 dot-product 연산과 $O(L_qL_k)$만큼의 메모리 사용을 필요로합니다. 이는 prediction capacity 향상에 제약을 줍니다.

선행 연구들은 $p(k_i|q_i)$ 들 중에서 performance에 유의미한 영향을 끼치지 않는 것을 제외하는 "selective", 특정 확률만을 계산, counting startegies를 고안 또는, attention score를 근사하는 kernel function을 고안했습니다.

Efficient self-attention mechanism

[그림 6] Sparsity attention distribution

"Sparsity"한 self-attention은 꼬리가 긴 분포를 가집니다. 이는 소수의 dot-product pairs 만이 주요 attention에 기여하고 다른 dot-product pairs는 trivial attention, 즉 영향력이 낮은 attention을 생성합니다.

[그림 7] query-key feature map

그럼 어떻게 유의미한 dot-product pair를 구분해낼 수 있을까요?

Dominant dot-product paris, 유의미한 query_key pairs의 분포는 uniform 분포로부터 상이합니다. 그림 7에서 볼 수 있듯이 어떤 query가 다른 key와 활발하게 상호작용한다면 다양한 확률 값을 가질 것이고, 아니면 uniform한 확률 값을 가질 것입니다.

만약 $p(k_i|q_i)$ 의 분포가 uniform 분포인 $q(k_j|q_i) = 1/L_k$에 근사한다면 self-attention socre로 value V를 가중합할 때 상대적으로 불필요한 query로 작용할 것입니다.

따라서 p분포와 q분포의 유사도는 중요한 query를 구분해 내는 지표로 사용할 수 있습니다.

ProbSparse self-attention이란?

[그림 8] ProbSpase self-attention

ProbSparse self-attention이란 sparsity 측정 지표를 통해 유의미한 query를 top-$u$개만 선택하여 attention을 계산하는 방법입니다.

• $\bar{Q}$는 sparse matrix를 의미하며, 오직 Top-$u$개의 query 만으로 구성됩니다.
• ProbSparse self-attention은 오직 top-$u$개 만큼의 query에 대해서만 dot-product 연산을 수행하기 때문에 더 적은 memory를 사용합니다.
• Multi-head 관점에서 보면, 각 head 별로 각기 다른 query-key 쌍을 생성하게 되기 때문에 sammpling으로 인한 심각한 정보 손실을 방지할 수 있는 효과를 가집니다.

ProbSparse self-attention 구현

• step1: query 중요도 계산

[그림 9] step 1

• step2: 중요도를 기준으로 top-$u$개 query 선택

[그림 10] step 2

• step3: top-$u$ 개의 query와 모든 key set에 대해 attention을 구함

[그림 11] step 3

ProbSparse self-attention 정리

• 타 Sparse Attention 방법론 대비, 보다 효율적이며 실질적으로 유의미한 query로만 attention을 계산하는 방법론을 제안함
• Attention을 확률 분포의 관점에서 접근함
• Query 중요도 $\bar{M}(q_i, K)$ 계산을 위해 필요한 연산과, 이를 통해 뽑힌 top-$u$개의 query를 기반으로 self-attention을 수행하는 연산이 모두 $O(LlogL)$의 복잡도를 갖게 됨

Encoder

[그림 12] encoder

encoder는 메모리 사용량 한계 내에서 더 긴 sequential한 input을 받기 위해 다음과 같은 방법론을 사용했습니다.

• Encoder embedding 구성
• Self-attention distilling
• Stacked Encoder

Encoder embedding은 scalar embedding과 stamp embedding을 더하여 최종 embedding을 구성합니다. 서로 다른 차원을 가진 input data를 모델에 넣기 위해 512차원으로 변환합니다.

[그림 13] self-attention distilling

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

[그림 14] self-attention 1

Multi-head self-attention의 관점에서 각 head 별 query, key, value는 64 dimension을 갖도록 projection됩니다. 따라서 query[96,64]와 key[96,64]에 대해 ProbSparse Attention을 수행합니다.

[그림 15] self-attention 2

top-$u$개의 query vector와 value vector를 곱해 output vector를 구하게 됩니다. 이 때, 차원의 크기는 행렬 곱 연산으로 인해 top-$u$개의 크기와 동일합니다.

[그림 16] concatenate

key를 sampling해서 query 중요도를 계산하는데 사용하다보면 각 head 별로 output vector의 크기가 달라질 수 있습니다. Multi-head attention의 결과를 concatnate 하기 위해서는 동일한 크기로 맞춰줘야 하는데 이를 위해 Top-$u$ 개의 index를 저장해 두었다가 [$L_q$(96), 64($d'$)] 차원으로 맞춥니다.

본 논문에서는 8개의 Multi-head self-attention layer를 사용했습니다. 8개 head에 대한 Multi-head self-attention 결과, 총 [8, 96, 64]의 output이 출력됩니다. 기존 transformer처럼 concatenate된 output을 projection하여 $d_model$의 차원으로 맞춰주기 때문에 [96,512(8*64)]라는 최종 output이 생성됩니다.

이후 그림 13에서 볼 수 있듯이 1-D convolution과 1-D Max-polling 과정인 distilling을 거쳐 input의 절반 길이인 [48,512]를 갖도록 합니다.

[그림 17] self-attention distilling

이렇게 여러 번의 distilling 과정을 거쳐 input data의 사이즈가 작아진다면 총 메모리 사용량을 감소시키는 효과가 있습니다. 이는 J개의 stacking layer에 대한 memory bottleneck 문제를 해결할 수 있다는 것을 의미합니다.

Stacking layer replicas, $\approx$Multi Encoder

[그림 18] Multi-Encoder

Informer도 Transformer의 구조를 차용했기 때문에 여러 encoder를 가지고 있습니다. 제가 이해한 바로는 encoder의 입력이 다른 인코더의 입력으로 사용되는 것이 아니라 여러 encoder가 병렬적으로 만들어져 여러 feature map을 생성합니다.

이런 encoder 구조는 다음과 같은 특징을 가지고 있습니다.

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

Decoder

[그림 19] Decoder

Decoder는 다음과 같이 구성됩니다.

• One forward procedure로 generative inference를 수행할 수 있는 decoder를 구성합니다. Dynamin decoding 방식에 비해 빠른 추론 속도와 error accumulation을 방지할 수 있습니다.
• Masked self-attention은 encoder처럼 ProbSparse self-attention을 수행하고, Encoder-decoder attention은 Vanilla Transformer와 동일한 attention을 사용합니다. 그림 19에서 볼 수 있듯이 decoder의 input 중 절반은 encoder의 input 중 최근 데이터를 기준으로 절반을 사용합니다. 이후 예측해야할 부분은 cheating 문제를 방지하기 위해 scalar 값을 0으로 padding한 후 학습합니다.
• Attention을 통해 출력된 output은 Fully Connected layer를 거쳐 최종 output을 예측합니다.
• Loss는 true 값과 훈련 과정에서 예측한 prediction 값 간의 차이인 MSE Loss를 사용합니다.

이상으로 제가 공부한 내용에 대한 기록을 마무리 짓겠습니다. 항상 좋은 자료를 제공해주시는 DSBA 연구원님들께 무한한 감사를 표합니다!

 

피드백 환영입니다.😊

 

 

 

 

 

http://dsba.korea.ac.kr/seminar/?mod=document&uid=1823 

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

https://ai.googleblog.com/2017/08/transformer-novel-neural-network.html

Transformer: A Novel Neural Network Architecture for Language Understanding

https://arxiv.org/abs/2012.07436

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