수식이 보이지 않을 때는 페이지를 새로고침해주세요🫡
0. Abstract
--- ---[용어]--- ---
🔸LSTF : Long sequence time-series forecasting의 약자로 장기 시계열 예측을 지칭하는 줄임말로 자주 사용된다.
--- --- --- --- ---
[본문]
에너지 소비량 예측과 같은 현실 세계의 여러 문제들은 LSTF 문제에 해당한다. LSTF를 위해선 모델의 높은 예측 능력(예측 수용량)이 요구된다.
최근 연구들을 통해 Transformer의 예측 수용량(prediction capacity)이 증가하고 있으나 여전히 3가지 문제점이 존재한다.
[ Three Problems of Transformer ]
- 1. quadratic time complexity
- 2. high memory usage
- 3. inherent limitation of the encoder-decoder architecture
본 연구진들은 3가지 해결책을 통해 이 3가지 문제점들을 극복하고자 한다.
[ Three distinctive characteristics of Informer ]
- 1. ProbSparse self-attention mechanism
- 2. self-attention distilling
- 3. the generative style decoder
1. Introduction
[본문]
우리는 상당한 양의 과거 데이터를 활용하여 미래를 예측하는, 일명 LSTF를 수행할 수 있다. 그러나 모델에 부담을 주지 않는 short-term prediction이 시계열 예측의 추세가 되고 있는데 이는 LSTF연구에 방해가 된다.
일반적으로 예측 길이가 48 이하인 시계열 예측을 short-term이라 부른다. Figure(a)는 단순히 short-term prediction과 long-term prediction의 차이를 보여주는 것이다. Figure(b)는 주목해야 하는데, 48번 위치를 기점으로 더 긴 시점을 예측할수록 기하급수적으로 MSE 값이 커지고 추론 속도가 느려지고 있다.
위 Figure1 a,b를 통해 알 수 있는 사실은 다음과 같다.
a. LSTF는 더 긴 예측이 가능해야 한다. (long-range alignment ability)
b. long sequence input과 output에 대한 더 효율적인 연산이 가능해야 한다.
2017년 처음 등장한 Transformer은 사실 LSTF 과제에 가장 훌륭한 잠재력을 갖는 모델이다. self-attention 메카니즘을 활용하여 long-range dependency를 탐지하는 능력이 뛰어나고 서로 다른 위치의 정보가 서로를 참조하는 길이를 나타내는 maximum path lenght도 O(1)로 여태껏 등장했던 recurrent, convolution 모델들보다 뛰어나다. (Transformer 포스팅 참고) 그러나 위에서 언급한 b. 능력(계산 효율성)을 만족하지 못한다는 큰 단점이 존재한다. 몇몇 NLP 과제에서는 막대한 비용을 소모하여 large-scale Transformer 모델을 훈련시켰고 큰 성과를 보았지만, 현실세계의 모든 LSTF 과제에 이렇게 값비싼 모델을 사용할 수는 없다.
정리하자면 다음과 같다.
[ Three Problems of Vanilla Transformer ]
- 1. The Quadratic computation of self-attention : Query, Key, Value를 모두 원자 단위로 곱셈연산을 하기 때문에 layer마다 \( \mathcal{O}(L^2) \)만큼의 시간이 소요된다. (vanilla transformer의 self-attention을 나는 편하게 full attention이라 부르겠다.)
- 2. The memory bottleneck in stacking layers for long inputs : Transformer 논문(Vaswani et al. 2017)에서는 encoder를 N개 만큼 stack하는데 본 논문에서는 encoder stack layer의 개수를 J로 표현한다. 그랬을 때 총 \(\mathcal{O}(J\cdot L^2)\)만큼의 메모리가 필요하다.
- 3. The speed plunge in predicting long outputs : 기존의 decoding 방식은 step-by-step 추론을 수행한다. 본 논문에서는 RNN-based model과 같이 재귀적인 성격의 decoding을 Dynamic Decoding이라 칭한다.
Full attention의 계산 효율성을 개선하기 위한 연구들은 많이 이루어져 왔다. The Sparse Transformer, LogSparse Transformer, Longformer, Linformer, Transformer-XL, Compressive Transformer 등이 있다. 이들에 대한 설명은 내가 참고한 논문 리뷰에 자세히 설명되어 있다. 그러나 이런 연구들은 모두 1번 문제점(quadratic computation)만을 해결하려 하고, 해결책 또한 대체로 heuristic한 방법론이기 때문에 정확하지 않다.
Informer는 선행 연구들 중 full attention의 sparsity에 주목한 연구들을 계승하여 full attention과 vanilla transformer를 개선한 모델이다.
2. Preliminary
[본문]
- t-th sequencey \(\mathcal{X}^t\), length of sequence \(L_x\) \[ \mathcal{X}^t = \lbrace x^t_1,\cdots,x^t_{L_x}|x^t_i \in \mathbb{R}^{d_x} \rbrace \text{ at time } t \] - corresponding t-th prediction sequence \(\mathcal{Y}^t\), length of sequence \(L_y\) \[ \mathcal{Y}^t = \lbrace y^t_1,\cdots,y^t_{L_y}|y^t_i \in \mathbb{R}^{d_y} \rbrace \] - Input Representation : sequence transduction problem에서는 토큰 간 상대적 위치만 고려하면 되기에 Transformer에서는 PositionalEmbedding을 통해 local context를 input sequence에 삽입했다. 그러나 time-series forecasting 과제에서는 데이터의 상대적 위치 뿐만 아니라 hourly, weekly, monthly와 같이 global한 문맥도 중요하기 때문에 이를 위한 uniform input representation이 필요하다. 자세한 임베딩 방식은 부록 B를 참고해야 한다.
Appendix B - The Uniform Input Representation
- Scalar
Project Input Sequence \(\mathcal{X}^t\) of which shape is \([L_x,n_x]\) to \(\mathcal{U}^t\) of which shape is \([L_x,d_{model}]\) by Conv1d Layer
(\(L_x\) refers to length of input sequence,
\(n_x\) refers to numbers of features,
\(d_{model}\) refers to the size of model)
- Local Time Stamp
Same as Vanilla Transformer. \[ \operatorname{PE}_{(pos,2j)} = \sin(pos/(2L_x)^{2j/d_{model}}) \] \[ \operatorname{PE}_{(pos,2j+1)} = \cos(pos/(2L_x)^{2j/d_{model}}) \]
- Global Time Stamp
3. Methodology
- Efficient Self-attention Mechanism
[본문]
Transformer Dissection: An Unified Understanding for Transformer’s Attention via the Lens of Kernel(Tsai et al. 2019) 선행 연구에 따르면, i번째 query에 대한 attention을 kernel smoother을 사용하여 확률 함수의 형태로 변형할 수 있다. (let qi, ki, vi stand for the i-th row in Q, K, V respectively.)
--- ---[용어]--- ---
🔸kernel smoother : \( q_ik_j^T \)를 근사하는 kernel 함수
--- --- --- --- ---
\[ \mathcal{A}(\mathbf{q}_i,\mathbf{K},\mathbf{V}) = \sum_j\frac{k(\mathbf{q}_i,\mathbf{k}_j)}{\sum_l k(\mathbf{q}_i,\mathbf{k}_l)} \mathbf{v}_j = \mathbb{E}_{p(\mathbf{k}_j | \mathbf{q}_i)}[\mathbf{v}_j] \] --- --- --------- --- ---
Via the lens of the kernel, we were able to better understand the role of individual components in Transformer’s attention and categorize previous attention variants in a unified formulation.
(Tsai et al. 2019)
아직 커널 함수를 활용해 attention 수식을 변형하는 과정은 이해가 가지 않으나, attention에 대해 확률 분포의 관점으로 접근하려는 의미를 찾을 수 있다.
많은 선행 연구(SparseTransformer, LogSparse Transformer, Longformer, etc)들을 통해 canonical self-attention의 확률 분포가 희소하다는 사실이 밝혀졌고, 전체 \( p(\mathbf{k}_j|\mathbf{q}_i) \) 중 일부만 선택하는 전략들을 선보인 바가 있다.
위의 그림은 선행 연구들의 선택 전략을 시각화한 것들이다. 그러나 이런 연구들은 모두 heuristic한 선택 전략을 갖고 있다는 한계가 있으며 vanilla transformer의 2, 3번 문제점에 대한 해결책은 제시하지 못하고 있다.
이를 해결하기 위해 본 연구자들은 canonical self-attention에 대한 질적 연구를 통해 attention score의 분포가 "long tail distribution" 형태를 보인다는 사실을 발견했다.
위 그림은 Appendix C에 첨부된 것이며, y축 attention score에 해당하는 샘플의 수를 시각화한 것이다. 보다시피 0.2 이상의 확률값을 갖는 샘플은 0에 수렴하고, 0.025 이하의 확률값을 갖는 샘플이 대다수이다. 이것이 의미하는 바는 대다수의 query - key 쌍이 무의미하다는 것이다.
- Query Sparsity Measurement
--- ---[용어]--- ---
🔸The dominant dot-product pairs : input-output dependency에 기여하는 핵심 query-key pair
--- --- --- --- ---
[본문]
그럼 이제 어떻게 유의미한 query-key쌍을 찾을지에 대한 질문이 나온다.
수식1에 따르면 query의 각 행에 대한 attention은 조건부확률 \( p(\mathbf{k}_j | \mathbf{q}_i) \)로 정의된다. 그리고 최종 attention value는 해당 확률값과 value의 곱이다.
본 연구자들이 제안한 방법은 \( p(\mathbf{k}_j | \mathbf{q}_i) \) 분포와 균등분포인 \( q(\mathbf{k}_j | \mathbf{q}_i) = 1/L_k \) 분포를 비교하는 것이다. 아래 그림을 보면, canonical self-attention의 분포에서 무의미한 쿼리(\( \mathbf{q}_i \))과 key들의 연산 결과가 균등 분포를 갖는다는 점을 알 수 있다.
(편의상 앞으로 p 분포와 q 균등분포라고 줄여서 부르겠다.)
즉, i번째 p분포와 q 균등분포가 일치할수록 해당 query는 무의미한 것이고 p분포가 q 균등분포를 따르지 않을수록 dominant dot-product pair의 query라는 것이다.
그럼 왜 p분포가 균등분포를 따르면 안 되느냐?
query와 key의 내적 결과는 시퀀스 내의 각 위치 간 연관성을 나타낸다. 이에 softmax를 취하여 확률값으로 변환하고 value에 내적하게 된다. \[ softmax(\frac{p_iK^T}{\sqrt{d_k}}) = shape[1,L_k] \quad \Rightarrow \quad \mathcal{A}(p_i,K,V) = softmax(\frac{p_iK^T}{\sqrt{d_k}})V = shape[1,d_v]\] 만약 p 분포가 q 균등분포 \( q(\mathbf{k}_j | \mathbf{q}_i) = 1/L_k \)를 따른다면 i번째 query에 대한 attention score는 다음과 같이 정리된다. \[ {A}(q_i,K,V) = \sum_j q(\mathbf{k}_j | \mathbf{q}_i) V = shape[1,d_v] \] 이를 그림으로 보면 아래와 같다. 본 연구는 LSTF 문제를 다루므로 L_k 값이 크고, L_k값이 클수록 \({A}(q_i,K,V)\)의 결과 벡터의 원소들의 값이 모두 작아진다. 이는 곧 attention score가 모두 아주 작은 값, 균등 분포를 갖는다는 의미이다.
논문에서는 이를 다음과 같이 표현하고 있다.
If p(kj |qi) is close to a uniform distribution \(q(k_j |q_i)=1/L_K \), the self-attention becomes a trivial sum of values V and is redundant to the residential input.
요약하자면, p 분포와 q 균등분포의 유사성("likeness")을 중요한 query들을 판별해내는 데에 사용할 수 있다. 그리고 이 유사성은 Kullback-Leibler divergence를 이용해 측정할 수 있다.
\[ KL(q||p) = \ln\sum_{l=1}^{L_K}e^{q_ik_i^T/\sqrt{d}} - \frac{1}{L_K}\sum_{j=1}^{L_K} q_ik_j^T/\sqrt{d} - \ln L_K \] \[ \text{Dropping the constant} \quad \Rightarrow M(q_i,K)=\ln\sum_{l=1}^{L_K}e^{q_ik_i^T/\sqrt{d}} - \frac{1}{L_K}\sum_{j=1}^{L_K} q_ik_j^T/\sqrt{d} \] --- --- --------- --- ---
KL divergence 값이 클수록 두 분포가 다름을 의미하기 때문에 M(q,K)값이 클수록 해당 query가 dominate dot-product pair일 가능성이 높음을 의미한다. (KL divergence 공식의 유도는 아직 이해하지 못했으므로 생략하겠다...)
- ProbSparse Self-attention
[본문]
그래서 ProbSparse Self-attention은 위의 M(q,K)를 통해 중요한 query로 선정된 \(\overline{Q}\)만 갖고 attention을 계산하는 것이다.
\[ \mathcal{A}(Q,K,V)=\operatorname{Softmax}(\frac{\overline{Q}K^T}{\sqrt{d}})V \] --- --- --------- --- ---
\(\overline{Q}\)의 size는 [u,d_q]인데 u값은 \(c\cdot \ln L_Q\)이다. 이는 계산 복잡성과 메모리 사용량을 각각 \(\mathcal{O}(\ln L_Q), \mathcal{O}(L_K\ln L_Q)\)로 만들기 위한 하이퍼 파라미터이다.
그러나 이러한 방식은 모순적으로 계산 효율성을 떨어뜨리는데, 바로 \(\overline{Q}\)를 선택하는 과정에서 이미 \(\mathcal{O}(L_QL_K)\)만큼의 연산이 수행되기 때문이다. 문제점을 해결하기 위해 본 논문의 저자는 Lemma 1(보조정리1)과 Proposition 1(증명1)을 통해 이 \(\overline{Q}\)를 99%이상의 유의구간에 근사시킬 수 있음을 증명한다. 저자가 내세운 방법은 Key 또한 \( U^*=L_K\ln L_Q \)개 만큼 샘플링하여 M(q,K)를 계산하자는 것이다.
관련 내용은 Appendix D를 통해 확인할 수 있으며, 아직 완벽히 이해하지 못했기 때문에 생략하겠다.
의의 : 중요한 건 이런 근사 방법론을 통해 시간 복잡성과 메모리 사용량을 모두 \( \mathcal{O}(L\ln L) \)만큼 줄였다고 한다.
또한
- Encoder: Allowing for Processing Longer Sequential Inputs under the Memory Usage Limitation
[본문]
위 이미지는 논문의 Figure 3와는 조금 다른 구조지만 AAA1 학회에서 저자들이 발표할 때는 이 아키텍쳐 그림을 사용한다.
🔸Embedding
인코더의 입력으로는 앞선 임베딩의 결과값이 전달된다. 이 때, 임베딩 레이어에는 scalar를 임베딩하는 Conv1d layer와 time stamp를 임베딩하는 TemporalEmbedding layer + PositionalEmbedding layer로 구성되어 있다. 구체적인 내용은 포스팅 맨 아래 코드리뷰 ppt를 참고하길 바란다. \[ X_{en}^t \in \mathbb{R}^{L_x \times d_{model}} \]
🔸Multi-head ProbSparse Self-attention
임베딩 데이터를 head별로 나눈다. 데이터의 shape은 다음과 같이 변한다 >> [batch, seq_len, d_model] to [batch, head, seq_len, d_model/head]
이제 head별로 아래 과정을 수행한다.
Key를 랜덤하게 U개 샘플링한 후, 모든 \(\overline{M}(q_i,K) \)를 계산한다.
Top-u 개의 \(\overline{Q}\)를 선정한다. 이 때, Top-u개 query들의 index를 저장해둔다.
\(\mathcal{A}(\overline{Q},K,V)\)을 계산한다.
그러면 각 head별로 [u, d_model/head] shape의 출력물이 나와야 하지만 실은 그렇지 않다.
Appendix E를 참고하면 ProbSparse의 구현은 다음과 같다.
실제 feature map은 Value의 평균값으로 채워진 [seq_len,d_model/head] 행렬에 앞서 저장해둔 index 위치의 행에 ProbSparse self-attention 결과를 대입하는 식으로 구성된다.
최종적으로 [head,seq_len,d_model/head] 결과물이 나오고, 이를 concat하여 [seq_len, d_model] 크기로 만든다.
🔸Self-attention Distilling
기존 encoder의 feature map은 자연스레 중복적인 Value의 조합을 갖게 된다. 저자는 주요한 정보만을 추출하여 다음 layer에 전달하기 위해 distilling 기법을 활용하였다.
kernel_size가 3인 Conv1d layer를 통과시켜 주요한 정보를 추출하고 그 결과를 stride가 2인 Maxpooling을 통과시켜 크기를 절반으로 다운그레이드한다.
🔸Encoder Replicas
이는 Encoder구조를 수평으로 복제하여 추가하고 나중에 그 결과물을 stack하는 구조이다.
이러한 구조는 distilling 작업의 robustness(견고함)을 향상시켜 준다고 한다.
이 때, replicas의 input은 기존 sequence length를 절반씩 줄여가며 대입한다.
출력물의 차원을 맞추기 위해 stack replica 내부의 encoder layer 개수는 하나씩 줄어든다.
- Decoder: Generating Long Sequential Outputs Through One Forward Procedure
[본문]
Informer의 decoder 구조는 Vanilla Transformer와 동일하지만 추론 방식은 step-by-step이 아니라 one forward, 즉 입력을 하면 출력이 한 번에 나오는 방식이다.(decoder 구조는 vanilla transformer와 동일하므로 생략한다.)
\[ X^t_{de}=\operatorname{Concat}(X^t_{token}, X^t_O) \in \mathbb{R}^{(L_{token}+L_y)\times d_{model}} \]
- \(X^t_{token} \in \mathbb{R}^{L_{token}\times d_{model}}\) : \(X^t_{ec}\)에서 [L_x-L_token:L_x]만큼 슬라이싱한 임베딩
- \(X^t_{O} \in \mathbb{R}^{L_{y}\times d_{model}}\) : 실제로 예측해야 하는 시점(placeholder for the target sequence)
🔸Generative Inference
기존에 Start token <sos>과 End token <eos>을 활용한 dynamic decoding 방식은 효율적으로 사용되었다. 저자들은 이 방식을 generative하게 확장했다. 특정 역할을 하는 하나의 토큰 대신 이전 시점들의 샘플 토큰들을 입력하여 한 번의 forward로 예측을 수행하는 것이다.
generative inference에 대한 성능 검증은 Experiment section에서 이어진다.
🔸Loss function
MSE 손실 함수를 사용한다.
4. Experiments
--- ---[용어]--- ---
🔸Ablation Study : 모델의 특정 부분들을 제거하여 해당 부분이 있을 때와 없을 때의 성능 차이를 비교하는 연구
--- --- --- --- ---
[본문]
주요 실험 결과들은 아래와 같다.
- 다변량 예측, 단변량 예측에서 모두 Informer가 LogTransformer, Reformer, LSTMa, LSTMnet보다 우세했다. 그러나 단변량 예측에서 더 큰 차이로 우세한 모습을 보였다.
- Ablation Study결과, ProbSparse self-attention과 distilling과 generative inference 기법 모두 없을 때보다 있는 것이 더 효과적이었다.
특히, 해당 기법들을 사용하지 않았을 때는 out-of-memory(메모리 초과) 상태가 되어 아예 LSTF과제를 해결할 수 없었다.
5. Conclusion
[본문]
본 논문에서는 LSTF과제에서 중요한 long-range dependency를 효율적으로 포착할 수 있는 Informer 모델을 제시했다는 점에서 의의를 가진다.
특히 선행 연구들이 해결하지 못했던 Vanilla Transformer의 메모리 효율과 디코딩 시 느린 속도 문제에 대한 해결책을 획기적으로 제안했다.
+) Code Review
BITAmin 12기 세션 발표를 위해 준비한 코드 리뷰 피피티를 첨부합니다. 논문에서 공식 Github 페이지와 실습 코드도 제공해주고 있어 코드 리뷰하는 데 수월했습니다. 각 Layer별 output의 shape에 초점을 두어 코드 리뷰를 진행했습니다.
논문 읽으며 정리한 파일도 같이 첨부합니다~
References
'논문 리뷰' 카테고리의 다른 글
| [논문리뷰] G-EVAL: NLG Evaluation using GPT-4 with Better Human Alignment (0) | 2024.08.09 |
|---|---|
| [논문리뷰] Text clustering with LLM embeddings (0) | 2024.08.02 |
| [논문코드리뷰] Attention is all you need (code) (0) | 2024.07.01 |
| [논문리뷰] Attention is all you need (0) | 2024.03.04 |
| [논문 겉핥기] BERT: Pre-training of Deep Bidirectional Transformers forLanguage Understanding (0) | 2023.09.24 |
