`Long Sequence Time-series Forecasting(LSTF)`은 output과 input 간의 정확한 `long-range dependency` 관계를 효율적으로 파악하는 모델의 높은 예측 능력을 요구
최근 연구에 따르면 `Transformer`가 예측 능력을 향상시킬 수 있는 잠재력을 가진 것으로 나타남
그러나 Transformer에는 `quadratic time complexity`, `high memory usage`, 인코더-디코더 아키텍처의 내재적 한계점 등 LSTF에 직접 적용하기 어려운 몇 가지 문제점이 존재
인코더-디코더 아키텍처의 step-by-step inference의 속도 문제
Transformer의 이러한 문제점을 해결하기 위해 3가지 특징을 가진 `Informer`라는 이름의 효율적인 LSTF용 Transformer 기반 모델을 설계
$O(L log L)$의 시간 복잡성과 메모리 사용량을 가진 `ProbSaprse` self-attention mechanism이 시퀀스의 dependency alignment에서 비교할만한 성능을 보임
계단식 layer input을 절반으로 줄여 지배적인 attention을 강조하고, 매우 긴 input sequence를 효율적으로 처리
`generative style decoder`는 개념적으로 단순하지만, step-by-step 방식이 아닌 한 번의 forward 연산으로 긴 시계열 시퀀스를 예측하여 추론 속도를 획기적으로 향상
4가지 대규모 데이터셋에 대한 광범위한 실험을 통해 `Informer`가 기존 방법보다 훨씬 뛰어난 성능을 발휘하며 LSTF 문제에 대한 새로운 솔루션을 제공한다는 사실을 입증
1. Introduction
시계열 예측은 센서 네트워크 모니터링, 에너지 및 스마트 그리드 관리, 경제 및 금융, 질병 전파 분석 등 여러 영역에서 중요한 요소
이런 경우에는 과거 행동에 대한 상당한 양의 시계열 데이터를 활용하여 장기적인 예측, 즉 `Long Sequence Time-series Forecasting(LSTF)`을 할 수 있음
그러나 기존 방법들은 대부분 48개의 지점 혹은 그 이하의 예측과 같이 단기적인 문제 설정 하에 설계됨
점점 더 길어지는 시퀀스는 모델의 예측 능력에 부담을 주며, 이러한 추세로 인해 LSTF에 대한 연구가 지연되고 있음
Figure 1은 변전소의 시간당 온도를 단기(12개 지점, 0.5일)와 장기(480개 지점, 20일)까지 `LSTM` 네트워크로 예측한 결과
예측 길이가 48개 지점을 초과하는 경우(Figure 1(b)) 전반적인 성능 격차가 크게 발생하여 예측에 실패
`MSE`가 매우 높아지며 추론 속도는 급격히 떨어짐
LSTF의 주요 과제는 점점 더 길어지는 시퀀스에 대한 예측 능력을 향상시키는 것으로, 이를 위해서 다음이 요구
long-range alignment ability
long-range input과 output에 대한 효율적인 연산
self-attention 메커니즘은 네트워크 신호 이동 경로의 최대 길이를 이론적으로 가장 짧은 O(1)로 줄이고, 반복 구조를 피할 수 있기 때문에 Transformer는 LSTF 문제에 대한 큰 잠재력을 보여줌
그럼에도 불구하고, self-attention 메커니즘은 L-quadratic computation과 L-length inputs/outputs에서의 메모리 소비로 인해 long-range input과 output에 대한 효율적인 연산을 하지 못함
`vanilla Transformer`는 LSTF 문제를 풀 때 3가지의 주요한 문제점이 존재
(1) The quadratic computation of self-attention : self-attention 메커니즘의 `dot-product` 연산은 레이어당 시간 복잡성과 메모리 사용량을 $O(L^2)$로 만듬
(2) The memory bottleneck in stacking layers for long inputs : J개의 인코더/디코더 레이어 스택으로 인해 총 메모리 사용량이 $O(J·L^2)$가 되므로 긴 시퀀스 inputs에 따른 모델의 `확장성(scalability)`을 제한
확장성이란, 데이터의 크기가 증가하더라도 모델이 계속해서 잘 동작하는 능력
(3) The speed plunge in predicting long outpus : vanilla Transformer의 `dynamic decoding`은 step-by-step 추론 속도를 RNN 기반의 모델만큼 느리게 만듬
dynamic decoding이란, RNN과 같은 autoregressive한 step-by-step 방식을 의미
self-attention의 효율성을 개선시키기 위한 선행 연구 존재
`Sparse Transformer`, `LogSparse Transformer`, `Longformer`는 모두 heuristic 방법을 사용하여 (1)번 한계점을 해결하고 self-attention 메커니즘의 복잡성을 $O(L log L)$로 감소
`Reformer`도 `locally-sensitive hashing self-attention`을 통해 $O(L log L)$를 달성했지만, 매우 긴 시퀀스에서만 작동
`Linformer`은 복잡도 $O(L)$을 주장했지만, 실제 긴 시퀀스 input에서는 `project matrix`가 고정될 수 없어 $O(L^2)$로 성능이 저하될 위험이 있음
`Transformer-XL`과 `Compressive Transformer`는 `auxiliary hidden states`를 사용하여 long-range dependency를 파악하는데, 이는 (1)번 한계점을 증폭시키고, efficiency bottleneck 현상을 깨는데 불리하게 작용할 수 있음
모든 선행 연구들은 (1)번 한계점에 초점을 맞추고 있으며, (2), (3)번 한계점은 LST 문제에서 풀리지 않은 채 남아있음
💡 Self-attention Complexity 문제점 : self-attention은 Transformer에서 중요한 역할을 하지만, 두 가지의 문제점이 발생한다. (1) Complexity : self-attention의 complexity($O(T^2 · D)$)는 문장(T)이 길어지면 연산 복잡도가 quadratic하게 증가한다. (2) input에 대한 어떤 `structural bias`도 없어 input이 시퀀스 형태만 된다면 self-attention 계산이 가능하다는 장점이 있지만, 동시에 모든 input 시퀀스에 대하여 모두 self-attention을 계산해야하기 때문에 연산이 비효율적이라는 단점이 있다.
💡 Sparse Transformer : Vanilla Transformer Attention Matrix는 attention score가 계산되는 지점이 적기 때문에 행렬의 값이 대부분 0인 `sparse matrix`이다. 여기서 0에 수렴하는 attention 값들은 attention score가 계속 계산이 가능하지만, 이는 `representation`을 추출하는데 아무런 영향을 끼치지 못하기 때문에 계산량과 메모리 측면에서도 낭비가 발생한다. 따라서 연구자들은 `structural bias`를 부여하여 `Query-Key pair` 개수를 제한한다. 여기서 structural bias란, 모든 query와 key pair 중 어떤 pair만 사용할지를 결정해주는 기준으로 볼 수 있다.
Sparse Attention을 제안하는 연구들의 공통적인 주장은 다음과 같다. (i) 문장이 길어질수록, Attention에 필요한 비용이 크기 때문에 input length에 quadratic하게 증가하는 비용 대신에 최대한 Linear에 가깝게 증가하도록 만드는 것이 목적($O(n^2)$ → $O(n)$) (ii) 적당히 짧은 문장에서는 Transformer가 좋을 수 있어도, 긴 문장에서는 Cost 문제로 인해 Transformer를 적용하기 힘들어 global attention을 통해 long-range dependency를 해소
Sparse Attention의 효과는 먼저 일반적인 512 토큰보다 더 긴 문장을 input으로 활용할 수 있으며, input 문장을 길게 만들면 downstream task에서 사용되는 단서가 많아진다는 점이다. NLP에서는 주로 downstream task로 QA & 문서 요약에서 단서 증폭 효과를 살피기 위하여 이러한 sparse attention을 많이 사용한다. 시계열 예측의 관점에서는 더 긴 시퀀스를 받아서 더 긴 시퀀스를 예측하게 될 수 있다는 효과가 있다.
본 논문의 기여점
긴 시퀀스 시계열 inputs과 outputs 간의 개별적인 long-range dependency를 파악하기 위한 Transformer-like 모델의 잠재적 가치를 검증하는 LSTF 문제에서 예측 능력을 성공적으로 향상시키기 위한 `Informer`를 제안
표준적인 self-attention 메커니즘을 효율적으로 대체하기 위해 dependency alignments에서 $O(L log L)$의 시간 복잡도와 $O(L log L)$의 메모라 사용량을 달성한 `ProbSparse` self-attention 메커니즘을 제안
J-stacking layer에서 지배적인 attention score를 우선시하고, 전체 공간 복잡도를 $O((2-\epsilon)L log L)$로 급격히 감소시켜 긴 시퀀스 input을 수신하는 것을 돕는 `self-attention distilling operation`을 제안
추론 단계에서 누적 오류 확산을 방지하는 동시에 단 한번의 forward 단계만으로 긴 시퀀스 output을 얻을 수 있는 `generative style decoder`를 제안
Informer의 궁극적 목표는 기존의 Transformer을 연산, 메모리, 구조적 측면에서 효율적으로 개선시키면서도 높은 예측 성능을 유지하는 것"
2. Preliminary
고정된 크기의 `window`를 가진 `rolling forecasting` 환경 속에서 input은 시점 $t$에서 $X^t = \left\{x^t_1, ... , x^t_{L_x} | \in \mathbb{R}^{d_x} \right\}$이며, output은 해당 시퀀스에 대한 예측 $y^t = \left\{y^t_1, ... , y^t_{L_y} | y^t_i \in \mathbb{R}^{d_y} \right\}$
LSTF 문제는 이전 연구들보다 output의 길이 $L_y$ 가 더 길고, feature dimension이 단변량에 제한되지 않음($d_y$ ≥ 1)
Encoder-Decoder architecture
인코더-디코더 아키텍처의 모델들은 대부분 `input representations` $X^t$를 `hidden state representations` $H^t = \left\{h^t_1, ... , h^t_{L_h} \right\}$로 `encode`
추론에는 디코더가 이전 hidden state $h^t_k$와 $k$번째 단계에서의 outputs을 통해 새로운 hidden state $h^t_{k+1}$을 계산한 후, $(k+1)$번째 시퀀스 $y^t_{k+1}$을 예측하는 `dynamic decoding`이라는 step-by-step 프로세스 포함
💡 The Uniform Input Representation : `Informer`에서 활용하는 `Uniform Input Representation`은 총 3가지의 파트로 구성된다.
첫 번째는 `scalar`로, 일반적인 단변량 또는 다변량 시계열 데이터의 input 값에 해당한다. Informer에선 차원을 동일하게 맞추기 위해 1D Convolution filter(kernel width=3, stride=1)을 통해 scalar context $x^t_i$를 $d_{model}$의 차원 벡터 $u^t_i$로 `사영(projection)`한다.
두 번째는 `Local time stamp`이다. 이는 기존 `Transformer`에서 사용하는 고정된 `position embedding`을 사용하여 `local context`를 보존한다. 마지막은 `global time stamp`이다. 이는 사용자에 따라 week, month, holiday 등에 해당하는 내용을 포함한다. 각 global time stamp는 제한된 `vocab size`(최대 60개, 즉 분 단위로 가장 세분화)로 `learnable stamp embedding` $SE(pos)$에 의해 구현된다.
이러한 3가지 부분을 합친 `feeding vector`는 다음과 같이 표현된다. 여기서 $\alpha$는 `scalar projection`과 `local/global embeddings` 사이의 크기 균형을 맞추는 계수이다. 시퀀스 input이 정규화되어 있는 경우 $\alpha = 1$을 권장한다.
3. Methodology
Informer는 인코더-디코더 아키텍처를 유지하면서 LSTF 문제를 대상으로 한 모델
💡 Informer의 인코더와 디코더의 input : 인코더의 input은 어떠한 시퀀스의 길이만큼의 시계열 데이터 값인 `scalar embedding`과 앞서 `Uniform Input Representation`에서 확인한 것과 같이 stamp 정보가 포함된 `stamp embedding`이 합해진 형태이다.
디코더의 input의 경우 `start token`이라 표현하는 인코더의 input 시퀀스의 일부를 그대로 가져오고, 예측해야할 부분의 나머지 scalar 값은 0으로 `padding`을 한다. 그러나 해당 시점에 대한 stamp 정보는 그대로 포함된다.
Informer model overview
Informer Encoder
표준 self-attention을 `ProbSparse self-attention`으로 대체
파란색 사다리꼴은 `self-attention distilling operation`을 통해 지배적인 attention을 추출하여 네트워크 크기를 급격하게 감소시킴
`layer stacking replicas`는 robustness를 증가시킴
Informer Decoder
feature map의 `weighted attention composition`을 측정한 후 `generative style`로 output 요소(주황색 계열)를 즉시 예측
Efficient Self-attention Mechanism
표준 self-attention은 튜플 형태의 `query`, `key`, `value`에 기반한 `scaled dot-product` $A(Q,K,V) = Softmax(QK^T/\sqrt{d})V$를 수행
이러한 방식은 모든 query와 key에 적용되므로 `quadratic`한 `dot-product` 계산과, $O(L_QL_K)$의 메모리 사용량을 필요로 하여 예측 성능 향상에 제약
선행 연구들은 self-attention의 확률 분포에 잠재적 `sparsity`가 있다는 것을 발견하여, 모든 $p(k_j|q_i)$ 중 성능에 큰 영향을 끼치는 것만을 활용하는 `selective counting strategies`를 설계
그러나 이러한 `Sparse attention`은 `heuristic` 방법론을 따르고 있으며, `multi-head self attention`에서 각 head 모두 동일한 전략을 활용히여 개선이 힘듬
표준 self-attention의 학습된 attention 패턴에 대한 정성적 평가를 진행
`sparsity self-attention score`는 `long tail distribution`을 형성
몇 개의 dot-product pairs만이 주요한 attention에 기여하고, 다른 것들은 영향력이 낮은 attention에만 기여하고 있어 이들을 구별할 수 있는 방법이 필요
💡 The long tail distribution in self-attention feature map : ETTH_1 데이터셋을 통해 4개의 layer로 구성된 vanilla Transformer를 훈련시켜 self-attention feature map을 조사했을 때, long tail distribution을 형성(파란색 선)하는 것을 확인했다. 여기서는 Head1과 Head7의 attention score를 확인한 결과이다. 이를 통해, 일부 dop-product pairs만이 주요 attention에 기여하며, 다른 것들은 softmax score가 0에 수렴해 무시될 수 있다는 것을 확인할 수 있다.
Query Sparsity Measurement
$i$번째 query의 모든 key에 대한 attention은 확률 $p(k_j | q_i)$로 정의되며, output은 value $v$로 구성
주요 dot-product pairs는 해당 query의 attention 확률 분포가 `균일 분포(uniform distribution)`가 되지 않도록 유도
만약 $p(k_j | q_i)$의 분포가 균일 분포 $q(k_j | q_i) = 1 / L_k$에 가까우면, self-attention은 values $v$의 단순한 합이 되고 이는 inputs에 중복
자연스럽게 query의 attention probability $p$와 균일 분포 $q$ 사이의 `유사도(likeness)`을 이용하여 중요한 query를 확인 가능
long-tail distribution 아래에서 랜덤하게 $U = L_KlnL_Q$개의 dot-product pairs를 선택하고, 나머지를 0으로 채워 $\bar{M}(q_i, K)$를 계산
이후 샘플링된 값들 중 sparse Top-$u$를 선택해 $\bar{Q}$로 지정
$\bar{M}(q_i, K)$의 `max operator`는 0 값에 덜 민감하며, 수치적으로 안정
일반적인 self-attention 메커니즘에서는 queries와 keys의 input length는 동일하며, 이 둘 모두 $L$로 표시($L_Q = L_K = L$)
`ProbSparse self-attention`의 시간 복잡도와 공간 복잡도는 $O(LlnL)$
$U=L_KlnL_Q$에서 $L_K$와 $L_Q$를 $L$로 치환
결론적으로, ProbSparse Self-attention은 $\bar{M}(q_i, K)$를 통해 추출된 Top-$u$개의 queries들만 모든 keys들에 대한 attention을 수행하여 시간 복잡도와 공간 복잡도를 감소
Encoder: Allowing for Processing Longer Sequential Inputs under the Memory Usage Limitation
인코더는 long sequential inputs의 robust한 long-range dependency를 추출하기 위해 설계
input representation 이후 $t$번째 sequence input $X^t$는 matrix $X^t_{en}\in \mathbb{R}^{L_x\times d_model}$로 변환
Self-attention Distilling
💡 The single stack in Informer's encoder (1) horizontal stack은 인코더 복제본 중 개별 스택을 나타냄 (2) 그림에 있는 stack은 전체 input sequence를 입력 값으로 받는 메인 스택으로, 두 번째 스택은 input의 절반을 입력 값으로 받으며, 다음 스택들도 동일하게 반복 (3) 빨간색의 layers는 dot-product matrixes로, 각 layer에 distilling self-attention을 적용시켜 계단식으로 감소 (4) 모든 스택의 feature map을 concatenate하여 인코더의 output으로 활용
`ProbSparse self-attention` 메터니즘의 자연스러운 결과로 인코더의 feature map에는 value $V$의 중복 조합이 존재
`distilling operation`을 사용하여 지배적인 values들에 집중하게 하여 다음 layer에서 `focused self-attention feature map`을 생성하도록 함
attention block의 `$n$-heads weight matrix`를 통해 inputs의 시간 차원을 감소
`dilated convolution`에 영감을 받음
$j$-th layer에서 $(j+1)$-th layer로의 `distilling` 과정은 다음과 같음
$\left [ \cdot \right ]_{AB}$ : attention block
Multi-head ProbSparse self-attention
Conv1D로 시간 차원의 1-D convolutional filters(kernel width=3)
ELU(·) activation function
Max-pooling(stride=2)를 통해 $X^t$에 대한 다운샘플링 및 메모리 사용량을 $O((2-\epsilon)LlongL)$로 감소
`ProbSparse self-attention`에 `Masked multi-head attention`을 적용하여 마스킹되는 dot-products를 $-\infty$로 설정
`Multi-head Attention`에서는 기존 Transformer와 동일한 방식의 encoder-decoder attention 적용
`Fully-connected layer`를 통해 최종 output을 생성
outsize $d_y$는 단변량 예측($d=1$)과 다변량 예측($d>1$)에 따라 달라짐
Generative Inference
`Start token`은 NLP의 `dynamic decoding`에 효율적으로 적용되며, 본 논문은 이를 generative way로 확장
하지만 특정한 토큰을 start token으로 사용하는 경우 학습 데이터에 모델이 과적합될 가능성이 존재
기존에 방법 대신 input 시퀀스에서 긴 시퀀스를 `sampling`하여 $L_{token}$으로 사용
뒤에서의 실험 파트에서의 예시처럼 만약 7일간의 기온(168개의 데이터)을 예측하는 경우 알려진 5일의 데이터를 start token으로 사용하여 `generative-style inference decoder`에 입력
$X_{de} = \left\{X_{5d},X_0 \right\}$의 형태로 입력
$X_0$ : target 시퀀스의 time stamp, 즉 target week의 context
이후 기존 인코더-디코더 아키텍처의 `dynamic decoding`이 아닌 한 번의 `forward` 과정을 통해 디코더가 outputs을 예측
Loss function
예측 값과 실제 값의 차이에 대한 `MSE` 손실 함수 사용
디코더의 outputs에서부터 전체 모델에 걸쳐 역전파 과정을 통해 loss 값이 계산
4. Experiment
Datasets
2개의 LSTF에 대한 real-world datasets과 2개의 public benchmark 데이터셋으로 실험 진행
ETF(Electricity Transformer Temperature)
`electric power long-term deployment`의 중요한 지표
중국의 분리된 두 지역에서 2년 간의 데이터를 수집
LSTF 문제의 `세분성(granularity)`를 확인하기 위해 데이터셋을 $\left\{ETTh_1, ETTh_2 \right\}$와 $ETTn_1$으로 분리
$\left\{ETTh_1, ETTh_2 \right\}$은 1시간마다, $ETTm_1$는 15분마다 측정
"oil tempertature"를 target value로 지정하였으며, 6개의 변수로 구성
train/val/test는 각각 12/4/4 months
ECL(Electricity Consuming Load)
321명의 고객에 대한 전력 소비량 데이터셋
결측값으로 인해 데이터셋을 2년에 대한 1시간 간격으로 전환
"MT_320"을 target value로 지정
train/val/test는 각각 15/3/4 months
Weather
2010년부터 2013년까지 4년 동안 1시간 간격으로 수집된 미국의 1,600개 지점에 대한 local climatological dataset
"wet bulb"를 target value로 지정하였으며, 11개의 변수로 구성
train/val/test는 각각 28/10/10 months
Experimental Details
Baselines
`Informer`와의 비교를 위해 `ARIMA`, `Prophet`, `LSTMa`, `LSTnet`, `DeepAR` 5개의 시계열 예측 모델을 선택
`ProbSparse self-attention`의 성능을 확인하기 위해 ProbSparse self-attention이 아닌 일반적인 표준 self-attention을 적용시킨 `Informer+`와 `Reformer`, `LogSparse Self-attention`을 포함
Hyper-parameter tuning
Adam optimizer
learning rate : 1$e^{-4}$로 시작해 각 에포크마다 2번씩 감소
총 8에포크로, early stopping 적용
batch size는 32
Setup
각 데이터셋에 대한 inputs은 `zero-mean normalizing` 수행
`windows size` $L_y$는 {ETTh, ECL, Weather} 데이터셋에 대해 {1d, 2d, 7d, 14d, 30d, 40d}로 점차 증가
ETTm에 대해선 {6h, 12h, 24h, 72h, 168h}로 증가
Metrics
$MSE = \frac{1}{n}\sum_{i=1}^{n}(y-\hat{y})^2$와 $MAE = \frac{1}{n}\sum_{i=1}^{n}\left|y-\hat{y}\right|$ 사용
Platform
모든 모델은 single Nvidia V100 32GB GPU에서 train 및 test
Results and Analysis
Univariate Time-series Forecasting
모든 데이터셋에서 `Informer`의 성능이 우세(Informer 및 Informer+ 포함)
`LogTrans`와 `Reformer`는 dynamic decoding을 하기 때문에 LSTF 문제에서 성능 저조한 것으로 예상
ProbSparse self-attention을 적용한 Informer가 표준 self-attention을 적용한 Informer+보다 성능이 좋음(32>12)
Multivariate Time-series Forecasting
일부 모델은 다변량 데이터에 적합하지 않으며, 기존에 SOTA 모델은 `LSTnet`
`Informer`의 경우 최종 FCN layer만을 조정하여 간단하게 단변량 시계열 데이터 모델에서 다변량 시계열 데이터 모델로 변경 가능
Informer가 단변량 시계열 데이터뿐만 아니라 다변량 시계열 데이터에서도 가장 좋은 성능을 보임
Ablation Study: How well Informer works?
The performance of ProbSparse self-attention mechanism
위의 단변량 및 다변량 시계열 데이터에 대한 성능은 표준 self-attention을 사용해도 메모리 사용이 가능하게끔 제한한 결과로, 이러한 제한 없이 실험을 진행
메모리 효율성 문제점을 위해 {batch size=8, heads=8, dim=64}로 초기 설정을 했고, 나머지 세팅은 단변량 시계열 데이터 실험과 동일
모든 경우 Informer많이 `Out of Memory(OOM)` 없이 좋은 성능을 보임
The performance of self-attention distilling
ProbSaprse self-attention의 효과를 제거하기 위해 표준 self-attention을 활용한 Informer+를 활용
LSTF 문제에서 long sequence inputs의 이점을 고려할 때 distilling operation은 가치가 있음
특히, longer prediction이 요구되는 경우 가치가 상승
The performance of generative style decoder
Informer$\s$는 generative style decoder 대신 dynamic decoding을 적용
generative style decoder가 예측 성능에 중요하게 작용
여기서 offset의 경우 예측 길이를 얼마나 더 추가했는지에 대한 부분으로, prediction offset의 변화에도 Informer++은 강건한 성능을 보임
Computation Efficiency
training phase에서 Informer는 Transformer-based 방법들 중 가장 좋은 학습 효율성을 보임
testing phase에서는 generative style decoding 방식을 통해 모든 방법들 중 가장 빠른 추론 속도를 보임
시간 복잡도 및 메모리 사용량에 대한 비교
5. Conclusion
이 논문에서는 긴 시퀀스 시계열 예측 문제를 연구하고, 긴 시퀀스를 예측하기 위한 `Informer`를 제안
특히 `vanilla Transformer`의 `quadratic time complexity`와 `quadratic memory usage` 문제를 처리하기 위해 `ProbSaprse` self-attention 메커니즘과 `self-attention distilling operation`을 설계
`generative decoder`는 기존 인코더-디코더 아키텍처의 한계를 완화
실제 데이터에 대한 실험을 통해 LSTF 문제에서 예측 능력을 향상시키는 Informer의 효과를 검증
