데이터와 AI / NOTE 28

순환 신경망과 Attention

RNN & Attention

시계열, RNN·LSTM·GRU와 어텐션 표현을 살펴봅니다.

♫ 이 문서 듣기

개념에서 수식으로

먼저 이해할 내용

시간에 따라 이어지는 데이터에서는 현재 입력만으로 의미를 정하기 어려울 수 있다. 이 글은 이전 상태를 다음 계산에 전달하는 RNN에서 출발해, 어떤 과거 정보를 유지하고 어느 위치를 참고할지 정하는 Attention으로 확장한다.

기호를 먼저 읽기

xₜ, yₜ
시점 t의 입력과 출력
hₜ, cₜ
중간 상태와 문맥 또는 기억 상태; 구간별 정의를 구별
iₜ, fₜ, oₜ
입력·유지·출력 비중을 조절하는 게이트
같은 위치의 성분끼리 곱하는 연산
Q, K, V
질의·비교 기준·실제로 모을 값
αₜ,ₜ′
출력 시점 t가 입력 위치 t′를 참고하는 비중

이 글의 흐름

독립 샘플과 순서 데이터의 차이를 확인하고, 상태 갱신과 기울기 전달을 읽는다. 이후 게이트와 가중합을 이용한 선택적 정보 전달, Attention의 행렬 표현, 계산량을 줄이는 구조를 살펴본다.

주제와 표기

RNN (Recurrent Neural Network)

IID Data (Independent, Identically, Distributed)

독립 샘플과 순서 데이터는 다른 가정을 갖는다

IID 식은 각 샘플이 독립이라는 조건에서 결합확률을 개별 확률의 곱으로 적는다. 시계열에서는 앞뒤 값의 관계를 다루므로 이 가정을 그대로 두지 않는다. 원문은 시간·언어·음성·영상 등의 순서 자료를 이러한 차이의 사례로 제시한다.

x1,x2,,xN
xnP[x]
P[x1,x2,,xn]=P[x1]P[x2]P[xn]
Fully - Connected Net, CNN

Sequence Modeling

Wanted:Probabilityoversequences,xP[x1,x2,,xT]

Non IID Data

Time series
Language
Audio/Speech
Video
RNN

Feedforward Net

현재 입력만 쓰는 경우와 이전 상태도 쓰는 경우를 비교한다

순방향 식의 hₜ는 xₜ로 계산된다. RNN 식에서는 여기에 hₜ₋₁의 항이 더해진다. 따라서 같은 현재 입력이라도 이전 상태가 다르면 출력이 달라질 수 있으며, h는 지나온 정보를 다음 단계로 전달하는 역할을 한다.

원본 도해
yt=ϕ[Wyhht+by]
ht=ϕ[Whxxt+bh]

Vanilla RNN: Unfolding Computational Graph

ht=RNN[ht1,xt]
원본 도해
yt=ϕ[Wyhht+by]
ht=ϕ[Whxxt+Whhht1+bh]

Hidden Markov Model

원본 도해

Many to Many: Encoder-Decoder

입력 순서를 중간 표현에 담아 출력 순서로 옮긴다

Encoder는 입력의 정보를 표현으로 만들고 Decoder는 그 표현을 참고해 출력한다. 문맥 cₜ가 여러 h의 가중합이면 출력 시점마다 다른 입력 위치를 더 참고할 수 있다. α는 참고 비중이며 z 점수를 지수화하고 합으로 나누어 구성한다.

원본 도해
원본 도해

Seq-to-Seq Learning

Context vector
Ct=tαt,tht
αt,t : amount of attention yt should pay to ht
α_ (t, t^′) = ^z_ (t, t^′)/(Underoverscript[∑, l = 1, arg3] ^z_ (t, l))
원본 도해

Aligment Model

st1
FF Net zt,t
ht
Scores how well the inputs around position t^′ and the output at position t match

Vanilla RNN: Gradient Flow

여러 단계의 미분이 반복해서 곱해진다

현재 출력의 오차가 오래전 상태에 미치는 영향을 계산하려면 여러 단계의 미분을 거쳐야 한다. 원문의 행렬과 활성화 미분이 반복되는 식은 이 전달 구조를 보여준다. 특이값에 대한 설명은 반복 곱의 확대·축소를 이해하기 위한 조건으로 읽고, 모든 비선형 상태에서 한 값만으로 전체 동작이 결정된다고 보지 않는다.

원본 도해
Gradient of h1 involves multiplies of may W
Exploding gradients when largest singular value > 1
Vanishing gradients when largest singular value < 1
계속 작아지는 값이 문제가 있어 LSTM
원본 도해
y=ϕ[Wx]
computeJx!
Jxi=jJyjyjxi=j(Jyj)(ϕj)(Wji)
(Jx)=(WT)(ϕ100ϕk)(Jy)
Backprop from y to x involves a multiplication by W

Attention in Encoder and Decoder

Encoder

Attention이 참고할 수 있는 범위를 구별한다

Encoder의 자기참조, Decoder의 자기참조, Encoder-Decoder 사이의 참조는 입력 출처가 다르다. Decoder의 마스크는 현재 출력에서 아직 주어지지 않은 미래 정보를 보지 못하게 하는 조건이다. 같은 가중합이어도 어느 위치를 허용하는지에 따라 의미가 달라진다.

Contains self - attention layers
Each position in the encoder can attend to all positions in the previous layer of the encoder

Decoder

Contains self - attention layers
The input of the decoder is masked, which avoids the decoder to see the future . (each position is the decoder can attend to all positions in the decoder up to and including that position)
Need to prevent leftward flow in the decoder to preserve the auto - regressive property

Encoder-decoder attention

Queries come from the previous decoder layer and keys/values come from the output of the encoder
Allow every position in the decoder attend over all positions in the input sequence
Mimics the encoder - decoder attention in seq2seq learning

Hidden vector

양방향 상태와 게이트 구조로 확장한다

앞에서 읽은 상태와 뒤에서 읽은 상태를 모으면 두 방향의 정보를 함께 표현할 수 있다. LSTM은 별도의 기억 갱신을 사용하는 구조로 이어진다. 여기의 결합은 출력 형태에 관한 것이며, 미래 정보가 허용되는 문제인지와도 구별해 읽는다.

ht=(htht)

Long Short Term Memory (LSTM)

ht=LSTM[ht1,xt]

Permutation-Equivariant Attention Modules (SAB & ISAB)

MAB (multihead attention block)

집합 Attention은 순서 변화에 맞는 출력을 만든다

MAB는 Attention 결과에 입력을 더하고 정규화한 뒤 성분별 네트워크로 처리한다. SAB는 같은 집합을 질의와 참조로 사용한다. ISAB는 적은 수의 유도점을 거쳐 정보를 모으는 구조이므로, 어느 집합이 질의이고 어느 집합이 참조인지 따라간다.

Given X, Y∈RN×D
MAB[X,Y]=LayerNorm[H+rFF[H]]
H=LayerNorm[X+Multihead[X,Y,Y;w]]

SAB (set attention block)

SAB[X]=MAB[X,X]

ISAB (induced set attention block)

With inducing points I∈RM×D (trainable parameters, M<<N)
ISABM[X]=MAB[X,H]
where H = MAB[I,X]

Gates ∈ [0,1]

LSTM Cell Updates

기억의 유지와 새 정보 입력을 따로 조절한다

cₜ=fₜ⊙cₜ₋₁+iₜ⊙gₜ는 이전 기억을 남기는 부분과 새 후보를 넣는 부분의 합이다. 출력 게이트 oₜ는 기억에서 외부로 전달할 비중을 조절한다. 0~1 사이의 게이트는 각 성분의 통과량으로 읽는다.

이 구간에는 일반적인 함수 이름과 별개로 ArcTan이 직접 적혀 있다. 원문의 식을 유지하면서 기억·게이트의 구조를 설명하며, 이 표기를 확인하지 않고 다른 활성화 함수와 같다고 치환하지 않는다.

⊙ Hadamard product, element - wise product
ht=otArcTan[Ct]
ct=ftct1+itgt
gt=ArcTan[Wgxxt+Wghht1+bg]
it=sigmoid[Wixxt+Wihht1+bi]
ot=sigmoid[Woxxt+Wohht1+bo]
ft=sigmoid[Wfxxt+Wfhht1+bf]

LSTM: Gradient Flow

기억 경로의 미분을 별도로 본다

앞의 c 상태에서 다음 c 상태로 직접 이어지는 항에는 fₜ가 성분별로 곱해져 있다. 따라서 단순 RNN의 반복 행렬곱과 다른 직접 경로를 볼 수 있다. 이는 계산 그래프의 한 경로에 대한 설명이며 전체 미분의 다른 경로가 모두 사라진다는 뜻은 아니다.

원본 도해
ct=ftct1+itgt
ht=otArcTan[ct]
Backprop from ctto ct1 involves only elementwise multiplication by ft (no matrix multiplication by W, in contrast to the case of vanilla RNN)

Gated Recurrent Unit (GRU)

GRU는 이전 상태와 새 후보의 비중을 정한다

원문은 zₜ로 새 후보의 비중을, 1−zₜ로 이전 상태의 비중을 정한다. rₜ는 후보를 만들 때 이전 상태를 얼마나 사용할지 조절한다. 두 게이트는 모두 0~1의 값이지만 서로 다른 위치에서 다른 역할을 한다.

ht=GRU[xt,ht1]

Two gates : update gate zt and reset gate rt
ht=(1zt)ht1+ztgt
gt=ArcTan[Wgxxt+Wgh(rtht1)+bg]
zt=sigmoid[Wzxxt+Wzhht1+bz]
rt=sigmoid[Wrxxt+Wrhht1+br]

Generative RNN

다음 값의 확률을 곱해 순서 전체를 평가한다

각 단계에서 다음 입력의 조건부 확률을 모델링하고, 이를 곱하면 전체 순서의 우도가 된다. 음의 로그를 취하면 단계별 손실의 합으로 바뀐다. 이 과정에서 시간 첨자가 곱과 합의 범위를 정한다.

Parameterize p[xt+1yt], where

yt=σ[Wyht+by]

Likelihood

p[x1:T+1]=t=1Tp[xt+1yt]

Loss function

J=t=1Tlog[p[xt+1yt]]

VAE

GAN

Generating Sequence

원본 도해

Training RNNs for sequence Prediction

입력 순서에 조건을 둔 출력 순서를 학습한다

출력 yₜ는 입력뿐 아니라 이전 출력의 조건도 포함할 수 있다. 전체 조건부 확률을 시간별 곱으로 나눈 뒤, 로그우도를 크게 만드는 계수를 학습한다. 여러 샘플의 합과 한 샘플 내부 시간의 합을 구별해서 읽는다.

Inputsequence(x1,x2,,xT)
Outputsequence(y1,y2,,yT)
P[y1,y2,,yTx1,x2,,xT]
=P[yTy1:T1,x1:T]P[yT1y1:T2,x1:T]P[y1x1:T]
=t=1TP[ytht]: RNN

Training

수식
θML=argmaxθ(Xn,yn)Dlog[p[Ynxn;θ]]
=argmaxθ(Xn,yn)Dtlog[p[Ytny1:t1n,xn;θ]]
=argmaxθ(Xn,yn)Dtlog[p[Ytnhtn;θ]]
where
htn = {{{f[Xn], if t = 1}, {f[ht1n,yt1n], otherwise}}
Prediction of token yt requires either the true previous token yt1 or an estimate y^t1 coming from model itself

Teacher-Forcing

학습 때의 입력과 추론 때의 입력을 구별한다

Teacher Forcing은 학습 중 이전 정답을 다음 단계에 넣는다. 추론 때에는 모델이 만든 이전 출력을 다시 입력해야 할 수 있다. 따라서 학습에서 본 조건과 실제 출력 누적 과정에서의 조건이 같지 않을 수 있다는 점이 이 구간의 핵심이다.

Training : The model receives the ground truth output yt (instead of the generated one y^t) as input in the next time step xt+1

TF

원본 도해

Without TF

원본 도해
Inference (test) : Open loop mode with network outputs fed back as inputs
Inputs that the model will see during training time could be quite different from that it will see at test time

Attention in RNN-Encoder-Decoder

고정된 문맥과 시점별 문맥을 비교한다

Encoder의 마지막 상태 하나를 사용하는 방식에서는 입력 정보가 고정 길이 c로 모인다. Attention 방식에서는 출력 시점마다 여러 Encoder 상태의 가중합 cₜ를 다시 계산한다. 두 식을 비교할 때 c에 시간 첨자가 생기는 의미를 먼저 읽는다.

Computes the conditional probability
p[y1:Tyx1:Tx]=t=1Typ[ytc,y1:t1]=t=1Tyg[yt1,st,c]
where st is the hidden state of the decoder, c is the fixed - dimensional representation of the input sequence (x1, …, xTx), given by the last hidden state of the encoder
ht=f[xt,ht1]
c=q[h1,,hTx]=hTx
Compute the probability over the target sequence
p[y1:Tyx1:Tx]=t=1Typ[ytc,y1:t1]=t=1Tyg[yt1,st,ct]
where st is the hidden state of the decoder, computed by
st=f[xt1,yt1,ct]
and ct is the context vector, computed by a weighted sum of encoder hidden states {ht}

참고할 위치의 점수와 비중을 구한다

출력 상태와 입력 위치의 표현을 비교해 z 점수를 만들고, 지수값을 전체 합으로 나누어 α를 얻는다. α를 각 h에 곱해 더한 것이 cₜ이다. 점수·정규화된 비중·최종 문맥은 같은 값이 아니라 순서대로 계산되는 세 단계이다.

ct=t=1Txαt,tht
Note that in the previous model, we have c1 = hTx and ct = 0 for t = 2, …, Ty
원본 도해
context vector
ct=t=1Txαt,tht
Aligment Model
st1
FF Net zt,t
ht
α_ (t, t^′) = ^z_ (t, t^′)/(Underoverscript[∑, l = 1, arg3] ^z_ (t, l))

Visual Attention

영상의 여러 위치를 문장 생성에 연결한다

CNN의 특징 지도를 L개 위치의 D차원 벡터로 읽는다. Decoder는 단어를 만들 때마다 이 위치들 중 어떤 정보를 더 참고할지 정한다. 따라서 위치의 개수 L과 각 위치의 특징 개수 D는 서로 다른 차원이다.

Capsulize
Learning words - image alignment
Input : Raw image
14×14 Feature Map
Convolutional Feature Extraction
RNN with attention over the image (LSTM)
Word by word generation
Output : A sequence of C words from vocabulary of size K, {y1, …, yc}, yiRK

Encoder

Use a CNN to extract a set of D - dimensional feature vectors, referred to as annotation vectors
a=[a1,,aL]RL×D
which contains the output L1×L2×D (L = L1×L2) of a lower convolutional layer (before max pooling)

Decoder

Use a RNN with attention modules to produce a caption generating one word every time step conditioned on a context vector, the provious hidden state, and the previously generated words

Tranformer models

순환 상태 대신 위치 사이의 참조를 계산한다

Transformer 구간은 Attention, 위치 정보, 순방향 네트워크의 결합으로 정리되어 있다. 먼저 각 위치가 다른 위치를 얼마나 참고할지 계산하고, 그 결과를 다음 변환에 전달한다. 원문의 구조 설명을 다른 최신 모델의 구성까지 포함하는 주장으로 확대하지 않는다.

Self - Attention - based models

RNN

Sequential computations (autoregressive models in decoders) are expensive and are not easy to be parallelized

CNN (ByteNet, ConvS2S)

Need a lot of layers to catch long - term dependencies

Vanilla Transformer

Trnsformer=encoder+decoder
Encoderordecoder=attention+positionalencoding+feedforwardnet

Self-Attention: A sequence-to-sequence operation

출력은 입력값들의 가중합이다

yᵢ=∑Wᵢⱼxⱼ는 i번째 출력이 여러 입력 xⱼ를 모은 값이라는 뜻이다. 가중치 Wᵢⱼ는 입력 사이의 점수를 지수화하고 합으로 나누어 얻는다. 따라서 결과의 의미는 입력값뿐 아니라 참고 비중을 어떻게 정하는지에 달려 있다.

Inputseq(x1,,xT)
Self Attention
Outputseq(y1,,yT)
yi=jWijxj
Wij=exiTxjlexiTxl

Query, Key, Value

질의·비교 기준·모을 값을 나눈다

Query는 무엇을 찾는지, Key는 어느 입력이 관련되는지 비교할 기준, Value는 실제로 모을 정보에 해당한다. 같은 입력에서 만들어져도 서로 다른 투영을 거칠 수 있다. 이를 세 역할로 분리하면 QKᵀ를 계산한 뒤 V를 곱하는 순서가 이해된다.

Query:xi,WQ
Key:x1,,xT,Wk
Value:x1,,xT,Wv
Wgj=eqTkjjeqTkj

Scaled Dot-Product Attention

행렬곱의 차원을 따라 Attention을 읽는다

QKᵀ로 위치 간 점수를 만들고 √D_k로 크기를 조절한 뒤 Softmax로 비중을 만든다. 그 비중 행렬에 V를 곱하면 각 위치에 모인 정보가 된다. Q와 K의 비교 차원, V의 출력 차원은 같은 역할이 아니다.

Attention(Q,K,V)=softmax[QKTDk]VRN×Dv
Queries:QRN×Dk,qiR1×Dk
Keys:KRN×Dk,kiR1×Dk
Values:VRN×Dv,viR1×Dv
For example, attention on a query qi is calculated as
n=1Nexp[qiknT/Dk]j=1Nexp[qikjT/Dk]vn
softmax[(qiknTDk)n[N]]
Self - attention : Queries, keys, and values are from the same sequence

Multi-Head Attention

여러 표현에서 계산한 결과를 다시 모은다

각 head는 Q·K·V를 서로 다른 투영으로 바꾼 뒤 Attention을 수행한다. 결과들을 연결하고 Wᴼ로 다시 출력 차원에 맞춘다. 원문 투영행렬 목록의 마지막 기호는 출력 투영과의 대응을 확인하며 읽는다.

Allows the model to jointly attend to information from different representation subspaces at different positions
MultiHead[Q,K,V]=Concat[head1,,headh]WO
headi=Attention[QWiQ,KWiK,VWiV]
where linear projections are done via parameters matrices
WiQRDmodel×Dk
WiKRDmodel×Dk
WiVRDmodel×Dv
WiQRhDv×Dmodel
where h = 8 is the number of parallel attention layers

Position-wise Feedforward Networks

위치별 변환과 위치 정보의 역할을 구별한다

순방향 네트워크는 각 위치에 같은 형태의 변환을 적용한다. 위치 부호화는 입력이 몇 번째 위치에 있는지 구별할 정보를 더한다. 사인·코사인 식의 pos는 위치이고 i는 성분 번호이며, 분모의 지수 범위는 원문 표기를 확인해야 한다.

Applied to each position separately and identically
Linear transformations are the same across different positions, but different parameters are used from layer to layer
FF net with signle hidden layer
FFN[x]=max[0,xW1+b1]W2+b2
where x∈R512 and the number of hidden units is 2048

Positional Encoding

Inject some information about the relative or absolute position of the tokens in the sequence
Add positional encodings to the input embeddings
PEpos,2i=sin[pos100002iDmodel]
PEpos,2i+1=cos[pos100002iDmodel]
where pos is position and i is the dimension

Reformer: Efficient Transformer

Transformer models

참고할 쌍의 수와 저장할 중간값을 줄인다

모든 위치 쌍을 비교하면 길이에 따라 비교 수가 커진다. 원문은 LSH, 가역층, 분할 계산을 서로 다른 비용 절감 방법으로 제시한다. 계산 시간과 중간값 메모리를 줄이는 방법을 같은 하나의 효과로 보지 않는다.

Training large transformer models are prohibitively costly, especially on long sequences
The dot - product attention requires O (T^2) complexity, where T is the length of the sequence

Reformer models

LSH (Locality Sensitive Hashing) attention : Replaces the dot - product attention, reducing the complexity form O (T^2) to O (T log T)
Reversible layers : Reduce memory space (storing activations only once in the training process instead of L times, where L is the number of layers)
Chunking

Locality Sensitive Hashing (LSH)

비슷한 입력을 같은 그룹에서 만날 가능성과 연결한다

LSH 식은 입력의 유사성과 같은 해시값을 갖는 확률을 연결한다. 여러 해시를 사용하면 그룹화 방식과 충돌 확률도 달라진다. 구체적인 확률식은 원문의 해시 구성과 분포 조건 안에서 읽는다.

Project the data into a low - dimensional Hamming space such that each hash function hm[xi] for m = 1, …, M, satisfies the local sensitivity hassing property
P[h[xi]=h[xj]]=Sij
where P[h[xi]=h[xj]] is the probability of collision and Sij represent the similarity between xi and xj
LSH is a data - independent method and the hash functions hm[] (for m = 1, …, M)
consist of random projections followed by rounding :
hm[xi]=sdn[WmTxi+bm]
For random weight vector wm (drawn from p - stalbe distribution), the probability of collision was proven to be
P[h[xi]=h[xj]](11πcos1[xiTxj|xi||xj|])M
In practice, LSH requires muliple hash tables with long binary codes . The large value of M decreases the collision probability

Reversible Network

앞 단계 값을 뺄셈으로 되찾는 구조를 살핀다

순방향 식은 z₁=x₁+F(x₂), z₂=x₂+G(z₁)이다. 이 구조를 이해하면 어떤 출력과 함수값을 이용해 이전 값을 되찾으려는지 알 수 있다. 다만 원문 역방향 두 줄에는 변수와 함수 인수의 대응이 어긋나 보이므로, 이를 검증된 복원식으로 설명하지 않고 순방향 정의와 함께 확인하도록 둔다.

Allow the activations at any given layer to be recovered from the activations at the followinglayer, using only the model parameters
A normal residual layer performs a function x|→y that operates on a single input and produce a single output and has the form z = x + F[x]
A reversible layer works on a paris of inputs/outputs
(x1,x2)(z1,z2)
where (x1, x2) are a partition of units in a layer, and follows the equations
z1=x1+F[x2]
z2=x2+G[z1]
A layer can be reversed by subtracting the residuals
x2=z2G[z2]
x2=z1F[x2]
원본 도해
원본 도해

정리하면

순서 모델의 핵심은 과거 정보를 어떻게 보존하고 선택하는지이다. 같은 h나 c라는 기호도 구간에 따라 상태 또는 문맥으로 정의되므로, 먼저 각 식의 입력과 출력을 확인한다.