NL-040, Transformer-XL: Attentive Language ModelsBeyond a Fixed-Length Context (2019-ACL)

0. Abstract

• Transformers은 longer-term dependency에 대한 문제점이 있다.
• 왜냐하면 매번 고정 된 길이에 해당하는 context로 LM을 수행하기 때문
• 실제로 BERT에서 feature extraction 할 때, 512가 최대 길이..
• Transformer-XL은 새로운 구조로 fixed length에 의존적인 것을 해결하려고 한다.
• 방법은 segment-level recurrence와 relative positional encoding을 이용한다.
• 이 논문의 방법은 longer-term dependency을 해결할 뿐 아니라 context fragmentation 문제를 해결한다
• 그 결과 Transformer-XL은 RNN보다 80%이상 길고 vanilla Transformer보다 450% 긴 dependency을 가지고 짧고 긴 모든 문장에 대해 좋은 성능을 낸다
• 속도는 vanilla Transformer보다 1800배정도 빠르다
• bpc/PPL 측정으로 wiki8, text 8, WikiText-103, One Billion Word, Penn Treebank에서 SOTA을 달성한다

1. Introduction

• LM은 long-term dependency가 요구되는 중요한 문제이다. (unsupervised pretraining와 같은)
• Neural networks로 long-term dependency in sequential data를 처리하기는 쉽지 않았다.
• RNN을 사용하여 sequential data를 처리하는 게 일반적이지만, RNN은 gradient vanishing and explosion에 관한 문제점이 있다.
• LSTM gate에서는 gradient clipping의 기술들을 써서 해결을 하나 충분치 않을 수 있다.
• 실제로 LSTM 계열은 이전 연구들에서 200개의 context words을 평균적으로 사용한다고 알려져 있다. (처음 안 사실!!)
• Attention 메커니즘은 이를 해결하는 기술이다. (대표적으로 Bahadanau와 Vaswani 방법 등이 있음)
• 최근에는 character-level Transformer 가 발표되었고 이는 LSTM보다 좋은 성능을 보인다. (읽어 봐야 겠...)
• 하지만 이 방법은 수백개의 characters을 fixed-length segment로 분리하여 수행하는 방식이다.
• 따라서 fixed-length보다 긴 것의 dependency는 처리할 수 없다
• 어떤 심볼을 이용한 문장 단위로 끊는 것이 아니라 fixed-length로 그냥 segment를 가져가는 것이기 때문에 the model lacks necessary contextual information needed to well predict the first few symbols, leading to inefficient optimization and inferior performance. 
• 모델이 처음 몇 개의 symbol을 예측을 잘못한다? (+불충분한 optimization)
• 이러한 두 번째 문제를 context fragmenetation이라고 한다
• 위 문제들을 해결하기 위해 Transformer-XL(extra long)을 제안한다.
• 개념은 deep self-attention network이다.
• 각 new segment에서의 hidden state을 매번 새롭게 게산하는 대신, previous segments에서 얻은 hidden states을 재사용한다.
• 재사용된 hidden states은 current segment의 memory의 역할을 하는 개념이다. 
• 즉 segments 사이의 recurrent connection을 담당하는 것
• 그 결과 very long term dependency을 해결할 수 있고 이전 segment읭 정보를 전달함으로써 context fragmentation의 문제를 해결할 수 있다.
• 어케보면 느낌이 이미지에서의 DenseNet과 비슷하기도 하다
• 또 중요한 부분은 relative positional encodings을 사용해야 한다는 점이다.
• 생각해보면, 현재의 state에서의 첫 번째라는 개념은 현재 segment에서 첫 번째라는 개념인데 previous segment을 가져오기 때문에 절대 position의 개념이 상대적으로 되야한다는 것
• 따라서 이 논문에서 주장하는 하나의 contribution은 간단한 relative positional encoding을 사용하여 이를 통해 attention lengths을 일반화 했다는 것
• Transformer-XL은 word-level, character level language modeling의 5개 데이터세트에서 SOTA이다.
• 100M tokens에 대해서 학습하였고 자연스러운 문장들을 생성할 수 있다. (Appendix E)
• Transformer-XL은 최초의 self-attentive model로써 character-level, word-level LM의 RNN 모델들 보다 좋다.
• 이 논문을 일게 된 이유는 다음 포스팅 계획인 XLNet 때문인데, XLNet으로써 Transformer-XL의 효과에 입증을 더했다고 생각이 된다.
• 실제로 Transformer-XL은 ICLR(?)였나에 reject이 되었는데(ㄷㄷ..) 그 이유 중 하나는 application, general 하게 실제로 잘 적용이 되는지를 못보였기 때문이라고 들었다.

2. Related Work

• LM 모델링들에 대한 연구들과 이를 통한 encoding을 하는 것들.. + long-term dependency을 해결하려는 RNN 변형의 연구들을 소개하고 있다.

3. Model

• Tokens의 corpus인 가 있다고 하자.
• 인 joint probability을 auto-regressively하게 찾는 것이다.
• 즉 을 fixed size hidden state로 encode하여 word embedding에 곱하여 logits을 얻는 것이다.
• 즉 auto-regressively하게 이전 step에서 현재 step의 word을 예측하는 (일반적인?) LM 방식으로 하는 것이다.
• 단 previous 연구에서는 t-step에서 이전 fixed step만 사용했다고 하면, 여기서는 이전 모든 step을 이용한다는 차이점이 다른점이라고 보면 될 것 같다.

3.1 Vanilla Transformer Language Models

• Transformer or self-attention을 LM에 적용하기 위한 중요한 문제는 임의의 긴 context을 fixed size representation을 효과적으로 하는 문제이다.
• 만약 무한한 memory와 계산이 가능하다면, 간단한 해결법으로는 전체의 context sequencec을 unconditional Transformer decoder(마치 feed-forward neural network 처럼)을 통과하여 학습하면 되지만 (Unconditional Transformer 처럼), 실제로는 불가능하다.
• context2vec처럼 전체의 context를 한꺼번에 학습하면 이론적으론 된다는 거 같음
• 하지만 실제로 context가 엄청 길게 되면, computing이 못 받쳐주니까 안됨
• 현실적으로 가능한 approximation은 전체의 corpus을 split하여 짧은 segment을 만들어서 이용하는 것이다.
• 즉 model은 each segment 사이에서 학습을 하게 되지만, 이는 previous segment로부터 contextual information을 전부 무시하게 되는 방법이다.
• 예를 들면)
• "오늘 아침을 굶었다. 그래서 점심을 허겁지겁 먹었다. 그랬더니 배탈이 났다. 따라서 오후 반차를 쓰고 집에 일찍 갔다."
• 라는 4개의 문장으로 이루어진 context가 있다고 하자.
• 이 때, computing이 최대 2개의 문장만을(원래는 fixed length) 처리할 수 있다고 하자.
• 그러면 "오늘 아침을 굶었다. 그래서 점심을 허겁지겁 먹었다." , "그래서 점심을 허겁지겁 먹었다. 그랬더니 배탈이 났다." 와  "그랬더니 배탈이 났다. 따라서 오후 반차를 쓰고 집에 일찍 갔다." 로 총 3개로 segment로 나눠서 학습을 하게 된다.
• 하지만 이러면, 3번째 segment을 학습할 때 아침을 굶고 점심을 빨리 먹은 내용을 모르고 학습을 진행하게 되는 것과 같은 단점이 생긴다.
• 이러한 방법을 vanilla model이라고 하고 다음의 그림과 같다.
• 
• 이 학습 방법은 절대 flow가 forward or backward pass가 동시에 일어나지 않는다.
• 이 말은 Language modeling(Transformer decoder)에서 auto-regressively하게 진행되니까 당연한 듯?
• 이러한 방법은 두 가지 문제점이 있다.
1. 가장 최대의 dependency length의 길이의 가능성은 segment length가 upper bound가 된다. (few hundred on character-level)
• 그래서 self-attention 기법은 RNN에 비해서 vanishing gradient problem에 영향을 적게 받지만, vanilla model은 optimization의 장점을 풀로 살릴 수 없다.
2. 문장(or semantic boundaries)에 관하여 padding을 사용할 수 있지만, 이는 실제로 긴 text을 효율성을 올리기 위해(computing이 가능하도록 하기 위해?) fixed-length segment 로 나누는 것이다.
• 그러나 이렇게(simply chunking) 문장을 fixed-length로 segment하는 것은 context fragmentation problem을 일으킨다.
• 위의 예시를 생각해보면, 특정 symbol으로 segment을 나누는 것이 아닌 fixed-length로 단지 나누어서 학습하는 것이기 때문에 previous segment에서의 정보를 가져다 쓰지 않는 학습 방법때문에 생기는 문제
• vanilla 모델은 같은 길이를 가지는 segment을 학습할 뿐 아니라 evaluation을 할 때, last position만을 예측하는 형태이다.
• Next step에서는 segment을 one position만큼 오른쪽으로 shift해서 다시 process을 진행하는 식이다.
• 그림은 다음과 같다.
• 
• 이것은 가장 긴 가능한 context을 이용하여 학습한 것을 이용하여 prediction을 하는 것이고 context fragmentation을 상기시킨다.
• 그러나 이러한 evaluation은 매우 expensive하다. (왜냐하면 매 step마다 token prediction을 할 때, 계산을 해야하므로)
• 여기서 제안한 방법의 구조는 evaluation speed을 개선한다.
• 예를 들어)
• 위에서 든 예시처럼 4개의 문장이 있다고 하자. ("오늘 아침을 굶었다. 그래서 점심을 허겁지겁 먹었다." , "그래서 점심을 허겁지겁 먹었다. 그랬더니 배탈이 났다." 와  "그랬더니 배탈이 났다. 따라서 오후 반차를 쓰고 집에 일찍 갔다." )
• 처리할 수 있는 fixed length가 4단어라고 하면, evaluation할 때 "그래서 점심을 허겁지겁 먹었다"문장의 step 에서 "먹었다"라는 단어를 예측할 때, "그래서 점심을 허겁지겁"이 입력이 되어서 "먹었다"를 예측하게 되는 것이다.
• 다음 step에서는 "점심을 허겁지겁 먹었다."가 입력이고 "그랬더니"을 예측해야한다.
• 이렇게 매 step에서 token을 예측할 때, 새롭게 계속 계산을 해야한다는 점이다. ("점심을 허겁지겁"사이의 관계는 이미 계산했지만 또 해야한다는 점이다)

3.2 Segment-Level Recurrence with State Reuse

• Recurrence mechanism을 Transformer 구조에 적용을 제안한다.
• 
• Previous segment에서 계산된 hidden state sequence을 fixed and cached라 하고 모델이 next new segment을 계산하는데 재사용 된다.
• Gradient는 segment 사이에 여전히 남아있지만 additional input은 네트워크가 longer-term dependency와 context fragmentation을 피하게 해준다.
• 수식적을 봐보면
• 두 개의 연속적인 길이 L을 가지는 segment을 다음과 같이 표기하자.
• , 
• (번째 segment 을 위한) n번째 layer의 hidden state sequence는 로 표기한다. (d는 hidden dimension)
• (next segment 을 위한) n번째 layer의 hidden state는 다음과 같이 계산된다.
• 
• SG는 여기서 stop-gradient을 의미하는 것이라고 한다.
• 는 concatenation을 의미한다고 한다.
• W는 model parameters 라고 한다.
• standard Transformer과 가장 크게 다른 점은  와 은  을 condition을 가지기 때문에 previous segment의 cached인 을 이용한다는 것이다.
• 추가설명을 해보자면, 원래 Transformer에선 previous layer에서의 hidden 값들에 matrix 3개를 곱해서 Q,K,V을 구한다. 이를 통하여 self-attention을 통하여 현재 layer의 hidden값을 구하게 된다.
• 하지만 여기서는 Q,K,V을 구할 때, Q는 똑같이 하지만, K, V는 현재 step의 previous layer 뿐만 아니라 이전 step의 previous layer의 값까지 사용하는 것이다. (그림보면 회색 박스에 해당하는 hidden vectors들을 concat 한다는 것)
• 의문점은 왜 Q는 previous step을 사용하지 않았는가? 인가
• 이것이 반복되면 두 개의 연속된 segment을 뛰어넘는다. (즉 계산할 때는 layer가 깊어질수록 receptive field가 넓어지면서 바로 직전뿐 아니라 훨씬 이전의 segment의 정보도 가져오게 된다)
• Conventional RNN-LM과는 다르다.
• RNN-LM은 이전 정보들이 계속 누적되어서 다음 state로 넘어가는 식임
• 결국 가능한 최대 dependency length 계산 복잡도는 O(N x L)이 되는 것이다. (Figure 2.b 참고, TCN에서 receptive field 개념하고 비슷)
• 여기서 말하길 truncate BPTT와 비슷하다고 함.
• 하지만 BPTT와 다른 점은 위에서 말햇듯이 sequence of hidden state의 last 값을 계속해서 가져가는 것이 아니라 relative positional encoding을 추구하여 caches 값들을 가져가는 것
• Extra long context을 처리할 수 있는 것외에 또다른 장점은 faster evaluation이다.
• 특별히 evaluation하는 동안 vanilla model과 다르게 이전 segment에서 계산된 값들을 재사용할 수 있다.
• 실험에서 Transformer-XL은 vanilla model보다 1800+배 빠르다고 한다.
• 이론상으로는 current segment의 processing할 때, GPU 메모리가 허락하는한 수 많은 previous segments의 cache을 사용할 수 있다.
• 그래서 여기서는 pre-defined된 길이-M old hidden state을 참조하여 cache을 구성한다.
• 즉 memory 만큼 필요하게 되는 것 (M개 이전 것 까지(정확히는 M-1개의 이전 step과 현재 step에 해당하는 previous hidden layer값) 참고해야 하고 각 hidden vector dimmension은 d이기 때문에 M x d 만큼 필요)
• 여기서 M을 학습시에는 segment length와 똑같이 두고, evaluation은 몇 배 곱해서 (ex. 2M, 3M 등) 큰 숫자를 사용한다고 한다.
• 그림에서 M=4로 segment length로 같이 두기 때문에 현재 cell 값을 구할 때, 이전 3개의 cell에서 가져다 쓴다는 개념이다. 하지만 evaluation을 할 때, 더 이전의 cell까지 사용한다는 말

3.3 Relative Positional Encodings

• How can we keep the positional information coherent when we reuse the states?
• Standard Transformer에서 과정을 리마인드 해보자
• positional encodings: 
• : i번째 absolute position에 해당하는 encoding (여기서 말하는 absolute란 것은 하나의 segement에서의 말임)
• : 모델이 수용할 수 있는 최대 길이
• Standard Transformer때 썼던 개념을 여기서 제안한 recurrence 모델에 단순히 적용해보면 다음과 같을 것이다.
• 
• 는 sequence 의 word embedding이다.
• 즉 모델에 word가 들어가서, word embedding을 하고 이 값에 position encoding을 더한다.
• 그 값들을 이용하여 f(=transformation function)을 통과하여 self-attention을 하는 과정이다.
• 하지만 여기서 와 은 같은 positional encoding 을 가지게 된다.
• 즉 모델은 어떤 j(1~L)에 대해서도 와  구분할 수 없게 되는 문제점이 생긴다.
• 다시 말하면, 두 개의 segment(, +1) 에서 j번째에 해당하는 word는 같은 positional encoding을 가지게 된다는 것.
• standard Transformer에서는 segment끼리 상호작용 할 일이 없어서 상관 없었지만, 여기서는 cached 개념으로 메모리를 가져오기 때문에 relative encoding을 해야한다는 것이다.
• 이러한 실패를 해결하기 위해서 relative positional information을 hidden state에서 encode 하자는 것이다.
• 즉 처음에 embedding을 주는 것이 아니라, each layer의 attention score에 정보를 주는 개념
• 예를 들어, query 와 key  사이를 attention을 해야할 때 each key vector의 absolute 위치는 알필요가 없다.
• 단지 알아야 하는 것은, 와 사이의 i-j의 상대적인 거리만 알면 된다
• 실제로  (는 relative distance of i between two positions)을 구할 수 있다.
• 이렇게 하면 , 에서 query vector가 representation을 구별할 수 있다.
• 이해하기로는) self-attention을 할 때마다, Q,K,V을 이용해서 서로를 attention하는 hidden layer input에서 positional encoding을 하겠다는 것이다.
• 즉 맨 처음에만 positional encoding을 하지 않고 이렇게 each layer에서 해주면 relative encoding의 개념이 되고 Q,K가 서로가 얼만큼 떨어져 있는지를 알 수 가 있다는 것!
• 수식적으로 absolute positional encoidng과 relative positional encoding을 살펴보자
• Abs positional encoding 에서 attention score은 다음과 같은 전개를 가지게 된다.
• 
• 
• 여기서 몇가지를 바꾸어서 relative positional encoding을 만든다.
• 
• 기본적으로 U들을 R로 바꾸는 작업들이다.
1. (b)와 (d)에서의 key vector을 구할 때, Uj term을 R로 바꾸는 것이다. 
• R은 relative 파트를 의미하는 것이고 R을 기존에 BERT, Transformer에서 쓰던 식으로 sinusoid encoding matrix을 사용한다.
2. (c)와 (d)에 Ui term이 남아있는데 이것도 1번처럼 생각하면 R0이 되는 것이다.
• 즉 query i-th을 기준으로 key j-th와의 관계를 찾는 것에서 i-th positional encoding은 어떤 query vector가 들어와도 똑같다는 것이다.
• 여기서 두 개의 Ui를 같은 것으로 치환하지 않고 (c)에서 는 로 (d)에서는 로 치환을 하여 training parameter을 만든다. (E, R에 곱해지는 것이라 다르게 설정한 것 같지만, 개념적으로는 같은 parameter로 치환해도 되지 않을까? 실험을 둘 다 했을 것 같기는 한데...)
3. 마지막으로 W matrix을 으로 나누어서 처리한다.
• 이렇게 바뀐 term (a), (b), (c), (d)을 논문에서는 다음과 같이 설명한다.
• (a): represents context-based addressing
• (b): captures a content-dependent positional bias
• (c): governs a global content bias
• (d) encodes a global positional bias
• 수식을 보고있으면 위의 설명과 비슷한 느낌이 들긴 함 (뭐.. 끼어 맞추기식 설명?)
• 이전의 연구들 중에 비슷한 방식을 소개하는데
• Shaw(2018)에서는 (a)와 (b) term을 사용한 연구가 있었다.
• 여기서 또한, W_k*R 대신 trainable matrix R을 사용하였다고 한다.
• 여기서는 R은 sinusoid로 non-trainable이고 W_k을 학습하는 것이니 조금 다르다.
• R을 sinusoid을 쓰면 좋은점은, 어떤 특정한 길이에 대해 모델이 학습하는 식이 아니니까 evaluation 때, longer times에 대해서도 일반화된 R을 써서 처리할 수 있다는 점!
• 최종 Transformer-XL 과정은 다음과 같이 된다.
• 논문에서는 N-layer + single attention head로 수식을 설명한다.
• 
• q,k,v을 3.2에서 설명했듯이 구하고
• Attention score또한 3.3에서 설명햇듯이 구하고
• 이 두개를 이용해서 Masked-softrmax을 통해 a을 구한다.
• 그 뒤에는 LayerNorm + Positionwise-Feed-Forward을 통과시키는데 이 부분은 기존 Transformer하고 똑같은 부분이다.
• 으로 초기 입력(word embedding)이 h0이라고 생각하면 된다.
• Attention score 구할 때, Appendix B에서 말하는 식으로 하면 cost가 sequence length에 quadratic 비례로 증가에서 선형 증가로 바꿀 수 있다고 하는 것 같다.

4. Experiments

4.1 Main Results

• word-level과 character-level 모델링을 SoTA 시스템과 비교를 하였다.
• 데이터는 WikiText-103, enwik8, text8, One Billion Word, Penn treebank을 포함하였다.
• 자세한 내용은 생략하교 결과 표를 확인해 보자.
• 
• WikiText-103에서 attention length을 384로 학습하고 evaluation할 때는 1600의 길이를 가지고 adopted softmax을 적용하였다.
• enwik8에서는 기존 Transformer의 layer와 파라미터수를 같거나 적게 사용하면서 더 좋은 성능을 냈다고 표현하고 있다. 이 때는 attention length을 784을 가지고 학습하였고 evaluation은 3800 길이를 가진다.
• Task에 따라 attention length은 어떻게 설정한 것인지에 대해서는 설명이 안나와있다. (아마 task가 얼마나 더 longer dependency을 가지냐에 따라 적절히 설정해줬을 것 같다)
• text8은 enwik8과 비슷한 task이다.
• One Billion Word은 sentence가 shuffling이 되어있기 때문에 long term dependency 문제만이 아니다. 하지만 Transformer-XL은 여기서도 SOTA 급이기 때문에 generalizable modeling to short sequences에 대한 장점도 있다.
• 
• 여기서도 SoTA이다.

4.2 Ablation Study

• Transformer-XL은 the recurrence mechanism과 new positional encoding 두 가지 기술이 들어간 것이므로 이 두개에 대해 ablation실험을 하였다.  
• recurrence mechanism은 long-term dependency가 필요한 WikiText-103 데이터에서 실험을 하였고 Table 6이 그 결과이다.
• 
• “Full” and “half” losses refer to applying a cross entropy loss to all or the recent half positions in the segment. (정확히 무슨 말인지?)
• 여기서 half losses가 학습 시에 very short attention length을 가지고 학습하기 때문에 generation에 better이라고 하다.
• Table 6에서는 recurrence mechanism 뿐 아니라 encoding scheme도 중요함을 보여준다.
• 학습 시에 BP 학습을 위해 attention length을 128을 이용했지만, test time에서는 640으로 늘릴 수 있다.
• 두 번째는 context fragmentation에 관한 실험이다.
• 이것또한 recurrence 방법이 해결해 줄 수 있음을 보인다.
• long term dependency가 필요없는 (영향이 없도록) One Billion Word dataset으로 실험을 한다.
• 
• 표 7 결과를 보면, long term dependency가 필요 없어도 recurrence 메커니즘이 성능을 올려준다.
• 그 이유는 context fragmentation 문제를 해결하기 때문이라고 하고 다른 encoding과 비교를 해봐도 여기서 사용한 relative encoding이 더 좋은 성능을 도출함을 보여준다.

4.3 Relative Effective Context Length

• Khandelwal이 sequence model의 Effective Context Length(ECL) 을 evaluate 하는 방법을 제안했었다.
• ECL은 context span이 threshold 보다 더 큰 gain을 도출할 수 있는 longest length을 말한다.
• 즉 모델이 적절한 성능을 낼 수 있는 최대 context 길이의 개념인 듯?
• 그러나 만약 모델이 shorter context에 최적화가 되어있다면, 모델끼리 ECL을 비교하는게 적절하지 않다고 한다.
• 따라서 이 논문에서는 Relative Effective Context Length(RECL)을 제시한다.
• 자세한건 Appendix. C에있다고 하니 참고..
• best short context model에서의 상대적인 성능 향상으로부터 측정된 long context의 gain으로 부터 연산이 되는 식?
• RECL은 parameter r을 가지고 있고 이는 top-r의 hard examples의 비교라고 한다.
• 
• 결과를 보면 Transformer-XL이 더 많은 RECL을 가진다.
• 즉 이는 recurrence mechanism과 positional encodings이 longer RECL을 가지게 해준다.

4.4 Generated Text

• WikiText-103에서만 중간 사이즈로 학습한 결과라고 한다. (Appendix. E)
• 
• 영어라 퀄리티가 어떤지 확 느낌은 없으나 나름 일관성이 있다고 한다.
• 따로 성능 평가나 그런 것을 하지는 않은 듯. 단지 생성에도 쓸 수 있다 이정도?

4.5 Evaluation Speed

• 
• Attention Length가 3800일 때, 1875배나 빨라짐..

5. Conclusions

• Transformer-XL은 PPL로 좋은 성능을 보여주고 RNN보다 longer-term dependency을 가지게 해준다.
• 또한 evaluation speed가 매우 빨라지고 일관성 있는 text articles을 생성할 수 있다.
• 이 논문은 text generation / unsupervised feature learning / image and speech modeling에서 적용되길 기대된다고 함.

Reference

• https://arxiv.org/pdf/1901.02860.pdf
• https://www.youtube.com/watch?v=lSTljZy8ag4