10. Sequence Modeling: Recurrent and Recursive Nets

RNN이란 Recurrent Neural Network로 순차적(Sequential) 데이터를 처리하는데 특화된 신경망이다. 이는 Width, Height에 따라 손쉽게 확장되는 Convolution과 비슷하게 RNN의 경우는 Data의 길이에 따라 손쉽게 확장 가능하며 가변 길이 데이터도 처리 가능하다.

RNN과 Parameter Sharing

일반 Multilayer 모델에 Sequential Data를 적용시에는 각 sequence마다 다른 Parameter를 적용해야 하며 이는 다음과 같은 문제를 야기한다.

• Train 때 학습하지 못한 길이의 데이터에 대해서는 일반화가 불가
• 시간의 서로 다른 지점에서 statistical strength를 공유 불가능

하지만 RNN은 Parameter Sharing을 통해 다양한 길이의 데이터의 형태에 일반화가 가능하다.

• 모든 입력 위치에서 같은 parameter를 적용하기 때문에 다양한 길이에 일반화 가능
• 서로 다른 지점에서 같은 Feature를 뽑아내기 때문에 statistical strength 공유가 가능

근데 Statistical Strength란 무엇일까?

→ 특정 정보가 순차열 안의 여러 지점에서 출현하는 경우 statistical strength를 사용가능한데, 예를 들어 “I went to Seoul in 2009”와 “In 2022, I went to Seoul”이라는 문장에서 내가 서울에 간 때를 알아내야 할 경우 모델은 2009의 위치가 어디든 이에 대한 정보를 뽑아내야 한다. 이때 사용하는것이 statistical strength이다.

RNN과 1D Conv

지금까지 본 RNN의 특징은 parameter Sharing을 통해 가변 길이 데이터를 처리할 수 있는 모델이다.

하지만 이는 Conv도 가능하다. 그렇다면 RNN이 1차원 데이터에 적용하는 것처럼 1차원에 적용할 수 있는 1D Convolution과 RNN의 다른 점은 무엇일까?

Convolution의 각 출력은 입력의 인접 성분들의 입력으로 이루어진 함수를 만들어준다. 그 반면, RNN의 출력은 이전 출력이 입력으로 들어오는 함수로 1D-Conv와는 달리 점화식과 같은 방식이라 볼 수 있다.

Unfolding Computational Graphs

RNN을 계산그래프로 표현하기 위해선 Cycle과 Unfolding이라는 개념을 사용해 표현한다.

이때 Cycle이란 위 그림에서 보이는 것처럼 표현하며, 변수의 현재값이 미래값에 영향을 끼치는 것을 의미한다. 그리고 Unfolding이란 Cycle과 같은 재귀적, 순환적 계산을 펼쳐 반복적인 구조를 가진 계산 그래프의 형태를 얻는것을 말한다.

위 그림은 unfold를 한 그래프와 그 그래프의 각 시점의 상태 $s^{(t)}$를나타내는 수식이다.

$s^{(t)}$는 $t$가 속한 집합이 $\tau$개로 유한한 경우 $\tau-1$번 적용해 그래프를 오른쪽과 같이 unfold 가능하다. 이때 좌식 $s^{(t)}=f(s^{(t-1)};\theta)$와 같이 이전 상태가 이번 상태를 나타내기 위해 인자로 들어오는 점화식으로 표현되는 것을 확인할 수 있다.

이때 위와 같이 state $s$가 아닌 hidden unit $h$로 생각할 수 도 있다. 이는 아래와 같이 표현할 수 있다.

$$
h^{(t)}=f(h^{(t-1)};x^{(t)};\theta) = g^{(t)}(x^{(t)}, ..., x^{(1)})
$$

$h$는 hidden unit으로 $t$시점까지의 정보를 lossy하게 요약해 저장하고 있다. 이때 Lossy란 $t$까지의 모든 입력 정보를 전부 저장할 필요 없이 Task에 필요한 충분한 정보만을 저장한다는 의미이다.

이때 $h^{(t)}=f(h^{(t-1)};x^{(t)};\theta)$ 와 같이 표현시 많은 이 점을 얻을 수 있는데 이는 단순히 하나의 함수 $f$를 여러번 적용한 것으로 생각할 수 있는 반면 $h^{(t)} = g^{(t)}(x^{(t)}, ..., x^{(1)})$와 같이 표현하는 경우 매 시점 $t$마다 새로운 함수를 적용해주어야 하여 많은 샘플이 학습에 필요하고, 다양한 길이에도 일반화가 가능하며, 메모리상으로도 문제가 있다.

여담으로 Task에 필요한 정보가 가장 많은 Task의 경우 다시 Input을 복원하는 Task인데, 이는 14장 Auto Encoder 파트에서 다시 알아보기로 하자.

Recurrent Neural Networks

RNN 구조의 주요 패턴들은 다음과 같이 크게 3가지가 있다.

1. 각 Time step 마다 하나의 출력, Hidden Unit 사이 Recurrent Connection 존재

2. 각 time step 마다 하나의 출력, 한 time step의 출력과 그 다음 time step의 hidden unit에만 recurrent connection이 존재

3. hidden unit 사이에 recurrent connection이 존재, 전체 순차열을 입력 받아 하나의 출력

일반적으로 1번 패턴이 가장 많이 사용되며 이후 나오는 패턴도 대부분 1번 패턴을 따른다.

1번 패턴

위 그림에 해당하는 feed forward 공식을 만들어보자. 위 그림에서 hyperbolic tangent 함수를 activation function으로, 출력은 이산적이고, $y^{(t)}$와 비교 전 softmax를 취한다고 가정하자.

이 경우 다음과 같이 공식이 만들어진다.

• $a^{(t)} = b+Wh^{(t-1)}+Ux^{(t)}$.
• $h^{(t)} = \tanh(a^{(t)})$.
• $o^{(t)}=c+Vh^{(t)}$.
• $\hat y^{(t)} = softmax(o^{(t)})$.

이때 $b, c$는 bias, $U$는 input to hidden 가중치, $V$는 hidden to output 가중치, $W$는 hidden to hidden 가중치를 의미

이때 총 손실은 다음과 같이 모든 time step에서의 loss의 총 합이 된다.

$$
L({x^{(1)}, ..., x^{(\tau)}}, {y^{(1)}, ..., y^{(\tau)}} = \sum_t L^{(t)}\\
= -\sum_t \log p_{model}(y^{(t)}|{x^{(1)}, ...,x^{(t)}})
$$

이때 이 손실의 기울기를 계산하기 위해서는 Feed Forward 과정과 Back-Prop 과정이 필요하다.

이때 Feed Forward의 시간 복잡도는 이전 time step의 계산이 끝나야 이번 time step의 계산을 할 수 있기 때문에 병렬화가 불가능해 $O(\tau)$가 소요된다.

Back-Prop 과정에는 Feed forward의 모든 계산 과정을 저장했다가 Back-Prop 시 사용해야 하므로, 공간복잡도가 $O(\tau)$이다.

이렇게 Unfold가 된 그래프에 대한 역전파를 BPTT(Back-Propagation through time)라 부른다.

Teacher Forcing and Networks with Output Recurrence

2번 그림

이전에 본 2번 그림의 방식처럼 output을 다음 time step의 hidden unit과 recurrent connection을 만든 경우, 이때 다음 time step에서 사용할 과거 정보들을 직전 output unit이 가지고 있어야 하는데 output unit들은 hidden unit에서 이번 time step의 목표값과 부합되는 정보만 가져가려 하기 때문에 hidden unit에 비해 표현력이 약한것은 당연하다.

하지만 위 방식은 분명히 output으로 나와야하는 값을 우리가 데이터로 가지고 있기 때문에 이전처럼 이전 hidden unit이 출력되기를 기다릴 필요가 없이 이상적인 값을 train set에서 가져와 이를 다음 time step의 입력으로 넣어주어 병렬화하여 학습을 최적화 시킬 수 있다는 장점이 존재하게 된다.

이러한 방식을 Teacher Forcing이라 부른다.

Teacher Forcing

위 그림은 Teacher Forcing을 통해 학습을 최적화 시킨 그림이다.

즉, Teacher Forcing이란 모델의 출력을 input으로 주는 구조에서 출력 대신 목표값을 input으로 주는 것을 의미한다. 이렇게 한다면 BPTT를 회피해 학습을 병렬화하여 학습 시간을 단축 할 수 있다.

이 방식을 이용한다면 아래와 같은 수식을 만족하게 된다.

$$
\log p(y^{(1)}, y^{(2)}|x^{(1)}, x^{(2)}) = \log p(y^{(2)}|y^{(1)}x^{(1)}, x^{(2)}) + \log p(y^{(1)}|x^{(1)}, x^{(2)})
$$

하지만 이 방식에도 단점이 존재한다.

1. output unit에 다음 time step에 필요한 모든 정보가 들어가도록 강제
2. test time시 출력을 입력으로 주게되는데 이는 학습때의 입력과 다른 분포일 수 있음

이때 2번 방식의 해결책으로 2가지가 있는데 1) output label 둘 다로 훈련시키는 방식과 2) output과 label 중 매 입력마다 무작위로 입력으로 주며 학습하는 방식이 존재한다.

Computing and Gradient in a Recurrent Neural Network

위 그림과 같은 RNN의 기울기 계산은 6장에서 본 Back-Prop 방식과 크게 다르지 않다.

1번 패턴

위 그림을 기준으로 각 노드에서의 기울기를 구해보도록 하자.

먼저 전체 loss에서 각 time step의 loss의 기울기는 단순 합이기 때문에 다음과 같다.

$$
\frac{\partial L}{\partial L^{(t)}}=1
$$

이때 loss는 softmax의 negative likelihood라 가정하면, 각 출력 $O^{(t)}$에서의 기울기는 다음과 같다.

$$
(\nabla_{o^{(t)}} L)_i = \frac{\partial L}{\partial o^{(t)}_i} = \frac{\partial L}{\partial L^{(T)}} \frac{\partial L^{(t)}}{\partial o^{(t)}_i} = \hat y^{(t)}_i - 1_{i,y^{(t)}}
$$

단순 softmax 미분

이제 hidden unit $h^{(t)}$의 기울기를 구해보도록 하자.

이때 $t=\tau$를 제외하고 hidden unit은 2곳에서 기울기가 역전파된다.

1. $o^{(t)}$로부터 역전파
2. $$
   \nabla_{h^{(t)}}L = V^\top \nabla_{o^{(t)}} L
   $$
3. $h^{(t+1)}$로부터 역전파 $(t \neq \tau)$이때 $diag(1-h^{(t+1)})^2)$은 tanh의 jacobian이다. $(\frac{d}{dx}\tanh(x)=1-\tanh(x)^2)$.
4. $$
   \nabla_{h^{(t)}} L = ({\frac{\partial h^{(t+1)}}{\partial h^{(t)}}})^\top(\nabla_{h^{(t+1)}} L) = W^\top(\nabla_{h^{(t+1)}} L) diag(1 - (h^{(t+1)})^2)
   $$

즉, 전체 기울기는 다음과 같다.

$$
\nabla_{h^{(t)}} L = W^\top(\nabla_{h^{(t+1)}} L) diag(1 - (h^{(t+1)})^2) + V^\top \nabla_{o^{(t)}} L
$$

그외 요소들의 기울기는 다음과 같다.

단순 미분이므로 생략

Recurrent Networks as Directed Graphical Models

RNN의 경우 이론적으로 거의 모든 종류의 Loss Function을 지원하며 Task에 맞게 설정해야 한다.

• 출력을 하나의 확률분포로 해석하는 경우: Cross Entropy
• 조건부 확률 분포로 추정하도록 훈련하는 경우: Predictive log-likelihood
  • $y$ 값의 sequence의 결합 확률 분포를 단일 단계 확률 예측으로 분해하는 방식은 전체 결합 확률 분포에 대해 이해할 수 있는 하나의 방식이다.
  • $$
    P(\mathbb Y)=P(y^{(1)}, ..., y^{(\tau)})=\prod^\tau_{t=1} P(y^{(t)}|y^{(t-1)}, ..., y^{(1)})\\
    \text{negative log likelihood: } L = \sum_t L^{(t)}\\
    L^{(t)}=-\log P(y^{(t)}=y^{(t-1)},y^{(t-2)}, ..., y^{(1)})
    $$

과거 y 값들을 신경망에 다시 입력으로 넣는 경우 directed graphical model의 과거 모든 $y^{(i)}$로부터 현재 $y^{(t)}$로 가는 간선이 존재하게 된다.

이때 이러한 Graphical model의 간선은 변수들 사이의 직접적인 의존 관계를 의미하게 된다.

이런 표현의 경우 통계적 계산적 효율성을 위해 strong한 interaction이 아닌 간선은 생략하는 경우가 많은데 이러한 경우의 대표적 예시로 Markov assumption(최근 $k$ 개의 $y$ 값만이 $y^{(t)}$로 간선이 이어짐)이 존재한다.

하지만 위처럼 RNN을 완전그래프로 해석하는 경우 hidden unit $h^{(t)}$를 주변화(marginalize)를 통해 무시하게 된다.

그렇다면 hidden unit $h^{(t)}$를 무시하지 않고 확률 변수로 간주해 그래프모형에 포함시킨 경우는 어떨까? 이에 대한 그림이 바로 위 그림이다.

위와 같은 그림을 보면 $y$를 바로 $y^{(t)}$에 넣는 것이 아닌 한번 $h^{(t)}$로 변환해 넣어주는 것을 확인할 수 있으며, 이 경우 동일한 구조가 반복되는 것을 확인할 수 있다. 이를 통해 Parameter sharing이 가능함을 확인 가능하며, 이때 각 $h^{(t)}$ 노드는 먼 과거 변수 $y^{(i)}$에 대한 정보도 가지고 있어 이를 통해 $y^{(t)}$에 $y^{(i)}$가 영향을 끼칠 수 있게 한다.

그렇다면 Graphical model의 parameterization의 단점은 무엇이 있을까?

• 결측치가 있는 경우 연산이 computationally 까다로워진다.
• Parameter sharing을 통하여 매개변수를 줄인 대신 RNN은 최적화가 쉽지 않게 된다.
  • RNN의 Parameter sharing은 모든 time step에서 같은 parameter를 사용할 수 있다는 가정에 근거하게 되는데, 이는 모든 과거 시점과 현재 시점의 상호작용이 $t$에 의해 영향을 받지 않는다는 가정과 동일하다.
    • 각 time step에서 $t$에 대한 추가 입력을 주어 최대한 parameter sharing을 하며 임의의 시간 의존성을 학습하는 방식도 존재하는데 이 방식이 차라리 전체 time step마다 다른 filter를 사용하는 것보다는 훨씬 낫다.

마지막으로 RNN을 Graphical model로 보는 관점을 완성하기 위해선 모델에서 sample을 추출할 수 있어야한다.

이때 모델은 sequence의 길이를 알아야하는데, 이를 알려주는 방법을 책에서는 다음과 같이 3가지를 제시했다.

1. Sequence의 끝을 의미하는 symbol을 출력 집합에 추가해 이 symbol이 출력되면 중지
2. 각 time step에서 생성을 계속 할지 말지를 결정하는 Bernoulli 출력을 도입
3. Sequence 길이 자체를 예측하는 추가적인 출력을 모델에 도입해 를 예측하고 그 크기 만큼 예측

Modeling Sequences Conditioned on Context with RNNs

이전 섹션에서는 입력 $x$가 없는 확률변수 $y^{(t)}$의 순차열의 directed graphical model로서의 RNN을 알아보았다.

이번에는 입력 $x$가 주어진 $y$의 조건부 분포에 대해 알아보도록 하자.

이전 feed forward에서 $P(y;\theta)$를 $P(y|w)$ 로 조건부 확률로 재해석 할 수 있다고 했다. (단 $w=\theta$)

이전과 동일하게 만약 $w$가 입력 $x$의 함수인 경우 $P(y|w)$를 사용해 $P(y|x)$의 분포를 나타내도록 확장할 수 있다. RNN에서는 이것을 여러 방식으로 보여줄 수 있다.

이전에 RNN에 입력 $x^{(t)}, t=1,...,\tau$인 순차열을 입력받는 것에 대해 보았었다. 이번에는 single vector $x$만을 입력으로 받는 경우로 단순화 해서 보도록 하자.

이 경우 다음과 같은 방식으로 입력 $x$를 모델에 추가 가능하다.

1. 각 time step마다 추가 입력 $x$ 주기
2. 초기 hidden unit을 $x$로 두기
3. 둘 다 쓰기

이는 각 time step마다 가중치 $R$로 입력 $x$를 parameterize하여 입력으로 넣어 bias 역할을 수행한다. 이는 $x$값에 따라 결정되는 bias로 조건부 분포를 표현하게 된다.

이런 방식은 이미지 하나를 입력받아 이에 대한 caption을 다는 작업에 유용한 구조이다.

이번에는 sequence로 $x$가 입력이 들어오는 경우를 생각해보자. 이러한 RNN은 조건부 분포 $P(y^{(1)}, ..., y^{(\tau)}|x^{(1)}, ..., x^{(\tau)})$에 해당한다. 이때 조건부 독립이라는 가정이 포함되어 다음과 같이 표현할 수 있다.

$$
P(y^{(1)}, ..., y^{(\tau)}|x^{(1)}, ..., x^{(\tau)}) = \prod_t P(y^{(t)}|x^{(1)},...,x^{(t)})
$$

이러한 조건부 독립이라는 가정을 제거하기 위해서는 아래 그림처럼 output또는 목표에서 다음 hidden state로의 간선을 추가해 이 가정을 제거할 수 있다.

이렇게 조건부 독립 가정을 제거하는 경우 모델을 $y$ sequence에 대한 임의의 확률 분포로 유연하게 표현할 수 있다.

하지만 위 방식의 입력과 출력의 길이가 같아야한다는 단점이 존재한다.

Bidirectional RNNs

이때까지 본 RNN의 구조는 전부 과거의 정보만을 capture하는 형태였다. 하지만 몇몇 모델은 모든 시점의 정보를 capture 하도록 설계한 모델들이 존재한다.

이러한 모델은 예측 값 $y^{(t)}$가 전체 입력 ($x^{(1)}, ..., x^{(n)}$)에 의존하는 경우 사용 (Ex. 음성 인식, 글자 인식)하게 되며 Bidirectional RNN이라 부른다.

Bidirectional RNN

위 그림은 Bidirectional RNN의 계산 그래프이다.

$h^{(t)}$를 이루는 계산 그래프를 보면 이전까지 본 단순 시간순 RNN이지만, $g^{(t)}$는 지금과는 다른 역시간순 RNN이다. 그리고 이 둘을 합친 $o^{(t)}$는 결국 시점 $t$에서 시점 $1\sim t-1$의 정보들과 $t+1 \sim n$까지의 정보를 전부 가지고있는 hidden state로 볼 수 있다. (이때 당연하게도 시점 t 근처의 입력값들에 가장 민감하다.)

이를 이미지와 같은 2차원으로 확장한 경우도 생각해볼 수 있다. 2차원의 경우 상하좌우 방향으로 4개의 RNN이 필요하며, 점 $(i,j)$의 출력 $O_{i,j}$는 먼 입력들을 고려해 $(i,j)$ 주변의 국소적 정보를 포착하게 된다. 이는 CNN보다 계산비용이 높으나, feature map의 먼 feature 사이의 상호작용을 학습할 수 있다는 장점이 있다.

Encoder-Decoder Sequence-to-Sequence Architectures

RNN의 출력을 Fixed size vector가 아닌 좀 더 유연하게 가져가는 방법은 없을까?

이에 대한 고민으로 나온 것이 이번에 볼 Seq2Seq이다.

Seq2Seq의 경우 위 그림처럼 Encoder-Decoder 구조를 하며 이러한 구조를 통하여 기계 번역에서 매우 좋은 성과를 보였다.

Encoder-Decoder 구조는 Encoder 부분에서 input sequence를 받으며, 최종적으로 Context vector $C$를 출력한다. Decoder 부분에서는 Encoder에서 출력한 Context vector $C$를 입력으로 받아 이를 조건부로 출력 순차열을 출력한다. 이때 기존과 다른 점은 입력과 출력의 길이가 다를 수 있다는 점이다.

이러한 Seq2Seq은 결국 2개의 RNN을 학습하며, 학습 데이터의 x와 y 쌍에 대해 $\log P(y^{(1)}, ..., y^{(n_y)}|x^{(1)}, ..., x^{(n_x)})$의 평균을 최대화 하도록 학습한다.

하지만 input을 $C$라는 context vector에 압축하기 때문에 $C$의 차원이 충분하지 않다면, 정보의 손실이 발생할 수 있다는 한계점이 존재한다. 이후 알아볼 Attention 기법을 사용한 방법은 이를 완화 시킨 방법인데 이는 12장에서 다시 보도록 하자.

Deep Recurrent Networks

RNN의 계산은 크게 3가지로 분해 할 수 있다.

1. input → hidden state
2. 이전 hidden state → 다음 hidden state
3. hidden state → output

이러한 변환들은 단일 행렬 연산에 해당된다. 이때 이런 단일 행렬 연산은 이전 Feedforward Network에서 단일 layer로 표현되는 shallow(얕은) 변환이라 볼 수 있다.

이러한 작업을 여러 번 쌓아 깊게 만든다면 이전처럼 성능의 향상을 볼 수 있다는 것이 실험적으로 증명되었다.

위 그림은 이러한 작업을 여러 번 쌓아 깊게 만든 Deep Recurrent Network의 예시들이다.

1. RNN의 state를 여러 층으로 분해하여 deep 함을 추가
2. state와 state 사이 MLP 연산을 추가해 deep 함을 추가
3. skip connection과 state 사이 MLP 연산을 추가해 deep 함을 추가

Recursive Neural Networks

Recursive Neural Network는 자료 구조를 네트워크 구조에 도입한 RNN의 다른 일반화로 Recursive Neural Network의 계산 그래프는 트리 형태이다.

Recursive Neural Network는 RNN과는 달리 동일한 길이 $t$의 sequence에 대해 시간 복잡도가 $O(t)$에서 $O(\log t)$로 크게 감소하고, Long-term dependency에 도움을 줄 수 있다는 장점이 존재한다.

하지만, 신경망 트리의 구조를 어떻게 설계할 지가 가장 큰 문제이다.

이에 대한 해결책으로 1) 그냥 균형 이진 트리를 사용하기 2) 구문 분석 트리 구조 등의 외부 메서드를 사용해 구조를 설계 3) 주어진 입력에 적합한 트리 구조 발견하기 등으로 구조를 설계할 수 있다.

The Challenge of Long-Term Dependencies

RNN은 input series에서 long-term으로 dependency를 학습시 몇가지 문제점을 가지고 있다.

1. 너무 작은 기울기가 연속적으로 곱해져, Gradient Vanishing이 발생
2. 너무 큰 기울기가 연속적으로 곱해져, Gradient Exploding이 발생
3. Series의 길이가 너무 길어져 hidden unit이 매우 이전에 input으로 들어온 정보를 잊어버리는 현상

RNN의 hidden state 연산은 $h^{(t)}=W^\top h^{(t-1)}$과 같다. 이러한 recurrence relation은 아래와 같이 power 형태로 정의될 수 있다. (간단함을 위해 activation function은 생략)

$$
h^{(t)} = (W^t)^\top h^{(t-1)}
$$

이때 $W$가 square matrix인 경우 고유값 분해가 가능하며 $h^{(t)}$는 결국 다음과 같다.

$$
W=Q\Lambda Q^\top, h^{(t)}=Q\Lambda^t Q^\top h^{(0)}

$$

위 식을 보면 결국 $W$의 eigen value가 $t$회 거듭 제곱을 이루게 되므로 이때 1보다 작은 고유값은 0으로 vanishing하며, 1보다 큰 고유값들은 exploding하게 된다. 즉, $h^{(0)}$의 성분중 가장 큰 고유 벡터와 방향이 다른 성분은 전부 제거된다.

그렇다면 왜 FC와 같은 네트워크에서는 이런 일이 발생하지 않을까?

FC와 같은 비 순환 신경망의 경우 초기 상태를 1이라 가정시 $\prod_t w^{(t)}$가 된다. 이때 $w^{(t)}$의 값이 서로 독립적으로 평균이 0, 분산이 $v$인 분포에 따라 무작위로 생성된다 가정시 최종 결과의 평균은 0, 분산은 $O(v^n)$이 된다. 즉, 적절한 분산 $v^\ast$를 만들고 싶다면, 분산을 $v=^n\sqrt{v^\ast}$으로 설정해 원하는 분산을 만들 수 있다.

그렇다면, RNN의 vanishing, exploding 문제도 이러한 방식으로 풀 수 있지 않을까?

이를 바탕으로 어떤 논문에선 RNN의 파라미터를 안정된 지역에만 제한하도록 학습을 하였다.

하지만 RNN이 작은 값의 변동에 robust하도록 memory를 저장하기 위해선, gradient가 vanishing하는 지역으로 파라미터가 이동해야한다는 결과를 얻었다.

특히 long-term interaction의 기울기는 short-term보다 훨씬 작다. 하지만 이것은 학습이 불가능하다는 것을 의미하진 않는다. 그저 short-term에서 발생하는 작은 변동에 long-term의 신호가 숨어 학습이 어려워 학습에 매우 오랜 시간이 걸린다는 것을 의미한다.

허나 실무에서는 capture 해야 할 long-term의 길이가 10~20 정도만 되도 단순 RNN과 SGD로 학습에 성공할 확률이 0에 수렴한다고 한다.

Echo State Networks

RNN의 가장 학습하기 어려운 부분은 $h^{(t-1)}\rightarrow h^{(t)}$인 hidden to hidden 부분과 $x^{(t)} \rightarrow h^{(t)}$인 input to hidden 부분이다.

이번에 알아볼 ESN(Echo State Network)와 Liquid State Machine은 hidden unit의 weight를 과거 기록을 잘 capture하도록 고정하고, output unit의 weight만을 학습시키는 방법을 통해 방금 언급한 RNN의 학습의 어려움을 피한 방식이다.

ESN과 Liquid State Machine의 차이는 hidden unit이 전자는 연속값 hidden unit을 사용하고, 후자는 spicking neuron이라는 이진값을 사용한다는 점만 다르다. 이 두 모델은 reservoir computing이라 부르며, hidden unit이 input 간의 historical한 temporal feature를 capture한다고 붙여진 이름이다.

ESN에 대해 생각해보는 방식으로 커널 머신으로 보는 방식이 있다. 그도 그럴것이 커널 머신은 decision boundary를 설정하기 좋은 latent space로 mapping을 한 후 좋은 decision boundary를 학습하는 방식이다. 이러한 방식은 좋은 latent space로 mapping하는 weight 함수를 고정하고 decision boundary를 학습하도록 output weight를 학습하는 ESN과 비슷한 경향을 보인다 할 수 있을것 같다.

이때 이러한 Decision boundary의 학습은 출력이 선형 회귀이고, 학습 판정이 MSE인 경우 볼록 함수인 경우 단순 선형 회귀 알고리즘으로 해결 가능하다.

이제 중요한것은 RNN의 state가 input의 정보들을 표현하도록 입력 가중치와 순환 가중치를 어떻게 설정할 지이다. 이 방법으로 책에서는 RNN을 하나의 dynamic system으로 보고 dynamic system이 edge of stability 근처에 있도록 RNN의 가중치를 설정하는 것이다. 이를 위한 방법으로 state transition의 weight의 jacobian의 eigen value를 1에 가깝게 하는 방식이 있다.

이때 eigen value가 1에 가까운것이 중요한 이유는 $v$가 야코비 행렬 $J={\frac{\partial h^{(t)}}{\partial h^{(t-1)}}}$의 한 고유벡터이고, $\lambda$는 해당 고유 값이라 할 떄 초기 기울기 벡터 $g$로 시작해 역전파를 실행시 n 단계에서 $J^ng$가 된다.

이때 g에 약간의 진동 $\delta v$을 주게 된다면 $J^n(g+\delta v)$가 되며 이는 이전과 $J^n\delta v$만큼 다르다.

이때 $v$가 $J$의 한 고유벡터이므로 이는 단순 scaling만 되기 떄문에 결국 $\delta |\lambda|^nv$만큼 변하며 이때 고유 값 $\lambda$가 1보다 큰 경우 차이가 explode하게 되며, 1보다 작은 경우 차이가 vanishing하게 된다.

이는 단순함을 위해 비선형성이 없는 경우에 대해 알아본 것이지만 비선형성이 있는경우도 작은 변동이 여러 단계 이후 큰 변동으로 바뀔 수 있다는 것은 동일하다. 하지만 $\tanh$와 같은 작은 영역으로 squashing하게 만드는 함수를 도입해 강제적으로 3 정도의 값으로 x를 매핑하도록 의도적으로 가중치를 고정 설정하여 ESN은 feedforward 시 값이 폭발하는 것을 막을 수 있다. 그렇기에 ESN 관련 최근 논문에서는 대부분 1보다 더 큰 eigen value를 가져도 되게 하는것을 권장한다.

위키피디아에 따르면 컴퓨팅 리소스가 향상되며 현재는 많이 쓰이지는 않게 되었다고 한다.

Leaky Units and Other Strategies for Multiple Time Scales

Long-term dependency를 처리하는 한 방법으로 multi time scale로 모델을 설계하는 방법이 있다. 즉, 모델의 일부는 fine-grained(조밀한) time scale에서 작동하여 small detail을 잡고, 또 일부는 coarse(rough) time scale에서 작동하여 먼 과거의 정보를 현재로 효율적으로 전달하도록 하는 것이다. 이것을 모델에 반영하는 방식들에 대해서 알아보자.

Adding Skip Connection through Time

먼 과거 variable에서 현재 variable로 직접적인 연결을 추가(skip connection)하여 Long-term dependency를 해결할 수 있다. 일반적인 RNN에서는 $t$와 $t+1$사이에만 recurrent connection이 존재하는 반면, 이런 skip connection을 추가한다면, 이보다 더 큰 time delay를 가진 연결을 할 수 있다.

이때 이러한 time step의 수와 관련해 gradient는 exponentially vanish되거나 explode 할 수 있는데, 이를 해결하기 위해 한 논문에서는 time delay를 $d$인 recurrent 연결을 하여 이 문제를 완화하였다.

이 방식을 적용 시 아래와 같은 특성이 있다.

• 기울기들은 $\tau$가 아닌 $\frac{\tau}{d}$가 되어 exponentially vanishing 됨
• 한 RNN에 time delay 연결과 기존 연결이 존재하기 때문에 $\tau$에 따라 기울기가 explode할 가능성은 여전히 남아있음 (즉, 완전히 해결은 못 함)
• 학습 알고리즘이 더 긴 dependency를 잡아낼 수 있으나, 이 방법으로 잡아낼 수 없는 Long-term dependency는 여전히 존재

Leaky Units and a Spectrum of Different Time Scales

어떤 값 $v^{(t)}$의 이동 평균 $\mu^{(t)}$를 $\mu^{(t)} \leftarrow \alpha\mu^{(t-1)}+(1-\alpha)v^{(t)}$로 얻어진다 하면, 이때 parameter $\alpha$가 바로 $\mu^{(t-1)}$에서 $\mu^{(t)}$로의 linear self connection의 예시다. $\alpha$가 1에 가까우면 이동 평균은 먼 과거 정보를 기억하며, 0에 가까우면, 과거 정보는 빠르게 버려진다. linear self connection이 있는 hidden units는 이런 이동 평균과 비슷하게 행동하며 이런 hidden unit들을 leaky unit이라 부른다.

linear self connection의 시간 상수를 설정하는 전략은 크게 2가지로 1) 그냥 고정 값 사용하기, 2) 자유 매개변수로 두고 학습 시키기가 있다. 다양한 time scale의 leaky unit을 두는 경우 Long-term dependency를 처리하는데 도움이 된다는 논문들이 존재한다.

Removing Connections

Long-term dependency를 처리하는 또 다른 방법으론 RNN의 states를 서로 다른 time scale에서 처리해 coarse한 time scale에서는 멀리 떨어진 time step 사이의 정보가 더 원활하게 하는 것이 있다.

앞서 본 skip connection도 비슷하지만 이번에 볼 방식은 길이가 1인 연결을 능동적으로 제거하고, 더 먼 connection을 넣는다는 점에서 skip connection과는 다르다.

이 방식으로 edge가 제거된 unit들은 더 긴 time scale에서 작동하지만, skip connection만 받는 unit들은 긴 time scale에서 작동하는 방법을 배울 수도 있고, 그냥 단기 연결에 집중할 수도 있다.

여러 recurrent unit들이 서로 다른 time scale에서 작동하도록 강제하는 방법은 다음과 같다.

1. leaky unit들로 이루어진 recurrent unit들을 각자 서로 다른 고정 time scale과 연관 시키기
2. unit group들을 각자 다른 빈도로 업데이트하기

The Long Short-Term Memory and Other Gated RNNs

Gated RNN은 Leaky unit을 사용하는 RNN 처럼 기울기가 exploding하지도, vanishing하지도 않는 시간 경로를 만든다는 아이디어에 기초한다. 이전에 본 Leaky unit을 사용하는 RNN들은 연결 가중치를 직접 설정하거나, 학습하는 방식으로 이런 경로를 생성하였지만 Gated RNN은 이를 가중치들이 time step 마다 변할 수 있도록 일반화 한다.

Leaky unit을 사용하는 방식에서는 정보를 오랜 기간 누적 할 수 있다. 근데 어떤 정보들은 일단 사용된 후 잊어버리는 것이 나을 수 있다. 기존 상태를 언제 제거할지 명시하는 것 보다는 그 시점을 모델이 결정하도록 하는 것이 바람직하다. 이를 Gated RNN이 해준다.

LSTM & Other Gated RNNs

Long Short-Term Memory (LSTM) 이해하기

[Long Short-Term Memory (LSTM) 이해하기

이 글은 Christopher Olah가 2015년 8월에 쓴 글을 우리 말로 번역한 것이다. Recurrent neural network의 개념을 쉽게 설명했고, 그 중 획기적인 모델인 LSTM을 이론적으로 이해할 수 있도록 좋은 그림과 함께

dgkim5360.tistory.com](https://dgkim5360.tistory.com/entry/understanding-long-short-term-memory-lstm-kr)

LSTM 설명은 책보다는 위 블로그 그림 및 설명이 훨씬 나음

Optimization for Long-Term Dependencies

앞서 RNN을 여러 time step동안 길게 최적화할 때 발생하는 gradient vanishing & exploding에 대해 알아보았다. 어떤 논문에서는 1차 gradient가 vanishing할 때 2차 gradient도 vanishing할 수 있다는 아이디어를 제안했다.

이를 좀 더 쉽게 생각하기 위해선 1차 미분을 2차 미분으로 나눈 결과에 대해 생각해보면 된다. 1차 미분을 2차 미분으로 나눈 결과는 1차 미분과 2차 미분이 비슷한 속도로 감소한다면, 이 ratio는 그다지 변하지 않을 것이다. 하지만 이러한 2차 최적화 방법들은 더 큰 미니 배치를 필요로 하며, 안장점으로 가기가 쉽다.

다른 2차 최적화 방법으로 Nesterov momentum 처럼 간단한 방법으로 초기 값을 세심히 설정 시 위와 비슷한 결과를 얻을 수 있다고 한다. 하지만 이 두 방법들은 그냥 SGD를 사용한 LSTM 방식보다 좋지 않았다.

즉, 최적화가 쉬운 model을 설계하는 것이 더 강력한 최적화 알고리즘을 만드는 것보다 쉬울 때가 많다는 것을 보여준다.

Clipping Gradients

여러 시간 단계를 거치는 RNN과 같이 고도로 non-linear한 함수들은 미분 값이 매우 커지거나(explode) 아님 아예 사라져버리는 (vanish) 경향이 있다.

위 그림은 Object function이 만드는 지형의 절벽(cliff)를 보여준다.

이와 같이 매개변수 기울기가 아주 크면 gradient descent로 갱신하는 과정에서 매개 변수들이 object function이 더 커져 버리는 먼 영역으로 가버릴 수도 있다. 이렇게 되면 지금까지 학습한 노력이 물거품이 되어버린다.

즉, 업데이트하는 크기는 object function이 커지지 않을 정도로 작아야 한다.

이 문제에 대한 널리 쓰이고 있는 해결책으로 Gradient Clipping이 있다. Gradient Clipping을 구현하는 방식은 여러 방식이 있다.

1. 업데이트 직전 매개변수 기울기를 성분 별로 clipping(절단)하는 방법
2. 업데이트 직전 기울기 $g$를 norm $||g||$로 나누어 clipping(절단)하는 방법
3. 기울기가 inf나 nan인 경우 무작위로 업데이트하기

2번 방식은 다음과 같다.

$$
\text{if }||g|| > v \text{ then } g \leftarrow \frac{gv}{||g||}
$$

이때 $v$는 norm의 threshold이다. 이 방식은 모든 매개변수의 기울기를 하나의 scaling factor로 renormalize하기 때문에 각 step이 기존 gradient의 방향을 유지한다는 장점이 있으며 기울기가 폭발해도 현재 solution에서 멀리 떨어지지 않게 업데이트 된다.

반면 1번 방식처럼 성분 별로 clipping을 하는 경우 성분 별 기울기를 clipping하는 방식은 기존 gradient와 방향이 다르다는 특징이 존재한다.

하지만 소개한 1, 2, 3번 방식 모두 실험 상에서 잘 작동한다고 한다.

Regularizing to Encourage Information Flow

Clipping Gradient는 Gradient Exploding을 다루는 것에는 도움이 되지만, vanishing하는 문제에 대해서는 도움이 되지 않는다. 이런 문제를 해결하고 long-term dependency를 좀 더 잘 포착하기 위한 방법으로 파라미터에 regularize나 constrain를 가해 Back-prop 과정에서 gradient vector $\nabla_{h^{(t)}}L$의 크기가 일정하게 유지되게 하는 방법이 있다.

이를 공식으로 표현하면 다음과 같다.

$$
\nabla_{h^{(t)}}L{\frac{\partial h^{(t)}}{\partial h^{(t-1)}}} \ge \nabla_{h^{(t)}}L
$$

이를 위해 다음과 같은 regularize 항이 제안 되었다.

$$
\Omega=\sum_t (\frac{||(\nabla_{h^{(t)}}L) \frac{\partial h^{(t)}}{\partial h^{(t-1)}}||}{||\nabla_{h^{(t)}}L||} - 1)^2
$$

위 방식을 사용 시 기울기의 방향은 유지하며, 기울기가 작은 경우 1에 가깝게 만들어준다.

위 기법은 gradient가 exploding하는 경계를 넘나들게 하므로, clipping gradient를 꼭 사용해주어야 학습이 가능하며, 이를 통해 RNN이 훨씬 더 긴 dependency를 학습할 수 있다.

하지만 이 방법은 data에 중복이 많은 task에 경우 LSTM에 비해 덜 효과적이다.

Explicit Memory

이 부분은 NTM 등 약간 다른 느낌을 설명하기 때문에 필요하면 정리할 예정...