[DL] RNN(Recursive Neural Network)의 이해

RNN(Recurrent Neural Network)

Sequential data

일반적으로 deep neural network에서는 input과 output이 하나의 vector인 one-to-one으로 이루어진다. 하지만 어떤 경우에는 sequential data가 input이나 output에 포함되는 경우가 있다. 예를 들어 stochastic process(time series)^[각주:1]나 ordered data structures가 있다. speech recognition이 time series에 해당하는 주요 예시가 될 것이고, machine translation이 ordered data structure의 예가 될 것이다. 이런 경우에 one-to-many나 many-to-many, many-to-one의 형태로 input과 output이 구성될 수 있다. 

 

Figure 1 : 이미지를 glimpse의 series로 classify한다.

요즈음에는 non-sequence data의 경우에도 sequential하게 processing하는 경우도 있다. 위의 Figure은 MNIST dataset을 visual attention의 sequence로 처리하는 과정의 일부이다.

 

즉, observation sequence $\mathbf{\text{x}}=\{{\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathbf{x}}_{\mathbf{T}}\}$와 corresponding label $y=\{y_1,y_2,...,y_T\}$에 대해서, mapping transformation $f:\mathbf{\text{x}}\mapsto y$을 학습하는 것이다. 이 경우에, sequential data를 model하는 방법으로서 RNN이 사용된다.

---

Recurrent Neural Network

Figure 2 : RNN example, 좌측은 recursive description이고, 오른쪽은 unfolded한 것이다.

RNN은 이전의 입력 데이터들에 대한 정보를 hidden state $h$라는 모델 내에 숨겨진 unit에 저장한다. 그리고 시간 $t$에서 새로운 input ${\mathbf{x}}_{\mathbf{t}}$가 들어올 때, ${\mathbf{x}}_{\mathbf{t}}$ 뿐 아니라 이전 state의 $h_{t-1}$도 함께 포함하여 $h_t$와 output $z_t$를 계산하게 된다. 이를 수식으로 표현하면 다음과 같다 : 

$$h_t=f(h_{t-1},x_t)$$

따라서, 현재 $h_t$는 현재의 input ${\mathbf{x}}_{\mathbf{t}}$에 대한 정보만 저장하고 있는 것이 아니라 지금까지 입력된 모든 $\mathbf{x}$에 대한 정보를 포함하고 있다. 

 

이때 hidden state에 대한 non-linear transformation은 $tanh$를 사용하고, output으로는 $softmax$를 사용한다.

$$h_t=tanh(W_{hh}{h}_{t-1}+W_{xh}{x}_t+b_h)$$

$$z_t=softmax(W_{hz}{h}_t+b_z)$$

 

한 가지 기억해야 할 점은, 각 time에서 사용하는 parameter $W$는 모든 sequence에 대해서 동일하게 사용된다. 또한 여기에서는 $W_{hh},W_{xh}$등으로 나누어 표기하고 있지만, 실제로는 하나의 행렬 $W$의 부분을 나누어 사용하게 된다. 즉, update해야 할 paramter는 $W$하나 뿐이다.

---

Backpropagation

sequence labeling에서, Loss function은 negative log likelihood를 사용한다. 

$$L(x,y)=-\sum _t{y}_t\log z_t$$

여기서 $z_t$는 output vector $z$에서 정답 레이블의 값을 나타낸다. y_t는 정답 레이블일 때만 1이고 나머지는 0이므로, 정답 레이블일 경우에만 loss function에 포함되고, 그 경우 z_t가 높을 경우 log의 값이 커지고, negative log likelihood, 즉 loss function의 값이 줄어들게 된다. 

 

이때 $softmax$에 들어가기 전 값을 ${\alpha }_t=W_{hz}{h}_t+b_z$라고 하면 위의 값은 다음과 같이 나타낼 수 있다.

 

$$L(x,y)=-\sum _t{y}_t\log (softmax({\alpha }_t))$$

 

이를 $\alpha$에 대해서 미분해 보자. 먼저 정답 레이블 $j$일 때, 

$$p({\hat{y}}_h|{\mathbf{h}}_{\mathbf{t}};\mathrm{\Theta })=\frac{\exp ({\alpha }_j(\mathrm{\Theta })}{\sum _k\exp ({\alpha }_k(\mathrm{\Theta }))}$$

이므로 ${\alpha }_j(\mathrm{\Theta })$의 partial derivative를 구하면

$$\begin{array}{rl}& \frac{\partial y_j\log p({\hat{y}}_j|{\mathbf{h}}_{\mathbf{t}};\mathrm{\Theta })}{\partial {\alpha }_j}\\ & =\frac{\partial y_j\log (\frac{\exp ({\alpha }_j)}{\sum _k\exp ({\alpha }_k)})}{\partial {\alpha }_j}\\ & =y_j\sum _k\exp ({\alpha }_k)(\frac{-(\exp ({\alpha }_j){)}^2}{(\sum _k\exp ({\alpha }_k){)}^2}+\frac{\exp ({\alpha }_j)}{\sum _k\exp ({\alpha }_k)})\\ & =y_j\left(\frac{\sum _k\exp ({\alpha }_k)-\exp ({\alpha }_j)}{\sum _k\exp ({\alpha }_k)}\right)\\ & =y_j(1-p_j)\end{array}$$

 

이다.

 

비슷한 방법으로 $\mathrm{\forall }k\ne j$인 경우에 그 prediction $p({\hat{y}}_k)$ 에 대해서도, ${\alpha }_j(\mathrm{\Theta })$에 대한 미분을 구하면 다음과 같다.

 

$$\begin{array}{rl}& \frac{\partial y_k\log p({\hat{y}}_k|{\mathbf{y}}_{\mathbf{t}};\mathrm{\Theta })}{\partial {\alpha }_j}\\ & =\frac{y_k}{p({\hat{y}}_k}\frac{-\exp ({\alpha }_k(\mathrm{\Theta }))\exp ({\alpha }_j(\mathrm{\Theta }))}{[\sum _s\exp ({\alpha }_s(\mathrm{\Theta })){]}^2}\\ & =-y_{k}p({\hat{y}}_j)\end{array}$$

 

전체 vector $\mathbf{y}$의 ${\alpha }_j(\mathrm{\Theta })$에 대한 그래디언트는 위 두 값의 합이다. 따라서 다음과 같이 계산된다.

 

 

$$\begin{array}{rl}& \frac{\partial p(\hat{\mathbf{y}})}{\partial {\alpha }_j}=\sum _j\frac{\partial y_j\log p({\hat{y}}_j|{\mathbf{h}}_{\mathbf{i}};\mathrm{\Theta })}{\partial {\alpha }_j}\\ & =\frac{\partial \log p({\hat{y}}_j)|{\mathbf{h}}_{\mathbf{i}};\mathrm{\Theta })}{\partial {\alpha }_j}+\sum _{k\ne j}\frac{\partial \log p({\hat{y}}_k|{\mathbf{h}}_{\mathbf{i}};\mathrm{\Theta })}{\partial {\alpha }_j}\\ & =y_j-y_{j}p({\hat{y}}_j)-\sum _{k\ne j}{y}_{k}p({\hat{y}}_j)\\ & =y_j-p({\hat{y}}_j)(y_j+\sum _{k\ne j}{y}_k)\\ & =y_j-p({\hat{y}}_j)\end{array}$$

 

이제 $W$와 $b$에 대한 derivative를 계산하면 된다. 먼저 $W_{hz}$에 대한 loss의 propagation는 다음과 같다 :

$$\frac{\partial L}{W_{hz}}=\sum _t\frac{\partial L}{\partial z_t}\frac{\partial z_t}{\partial W_{hz}}$$

 

$W_{hh}$와 $W_{xh}$에 대해서는 이전 hidden state에 있는 dependent들을 모두 생각해야 한다. 따라서 $t+1$에서의 output만 고려했을 떄, propagation 값은 다음과 같다 : 

$$\frac{\partial L(t+1)}{\partial W_{hh}}=\sum _{k=1}^t\frac{\partial L(t+1)}{\partial z_{t+1}}\frac{\partial z_{t+1}}{\partial {\mathbf{h}}_{\mathbf{h}\mathbf{+}\mathbf{1}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{+}\mathbf{1}}}{\partial {\mathbf{h}}_{\mathbf{k}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}}}{\partial W_{hh}}$$

 

만약 모든 time에 대해서 backpropagation 값을 고려한다면 다음과 같다 : 

$$\frac{\partial L}{\partial W_{hh}}=\sum _t\sum _{k=1}^t\frac{\partial L(t+1)}{\partial z_{t+1}}\frac{\partial z_{t+1}}{\partial {\mathbf{h}}_{\mathbf{h}\mathbf{+}\mathbf{1}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{+}\mathbf{1}}}{\partial {\mathbf{h}}_{\mathbf{k}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}}}{\partial W_{hh}}$$

 

같은 방법으로 이전 hidden state에 dependency가 있는 $W_{xh}$에 대한 backpropagation 값도 계산할 수 있다 : 

$$\frac{\partial L}{\partial W_{xh}}=\sum _t\sum _{k=1}^t\frac{\partial L(t+1)}{\partial z_{t+1}}\frac{\partial z_{t+1}}{\partial {\mathbf{h}}_{\mathbf{h}\mathbf{+}\mathbf{1}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{+}\mathbf{1}}}{\partial {\mathbf{h}}_{\mathbf{k}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}}}{\partial W_{xh}}$$

 

---

Vanishing gradient and Exploding Gradient problem

위의 gradient 계산 부분을 보면 이전 hidden state에 dependency가 있는 경우에 $\frac{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{+}\mathbf{1}}}{\partial {\mathbf{h}}_{\mathbf{k}}}$이 포함되어 있는 것을 볼 수 있다.

 

이는 chain rule에 의해서 다음과 같이 계산된다 : 

$$\frac{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{+}\mathbf{1}}}{\partial {\mathbf{h}}_{\mathbf{t}}}\frac{\partial {\mathbf{h}}_{\mathbf{t}}}{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{-}\mathbf{1}}}\cdots \frac{\partial {\mathbf{h}}_{\mathbf{k}\mathbf{+}\mathbf{1}}}{\partial {\mathbf{h}}_{\mathbf{k}}}$$

 

이는 풀어서 쓰면 다음과 같다 : 

$$\frac{\partial \tanh (W{\mathbf{h}}_{\mathbf{t}}+Wx+b)}{\partial {\mathbf{h}}_{\mathbf{t}}}\frac{\partial \tanh (W{\mathbf{h}}_{\mathbf{t}\mathbf{-}\mathbf{1}}+Wx+b)}{\partial {\mathbf{h}}_{\mathbf{t}\mathbf{-}\mathbf{1}}}\cdots \frac{\partial \tanh (W{\mathbf{h}}_{\mathbf{k}}+Wx+b)}{\partial {\mathbf{h}}_{\mathbf{k}}}$$

 

이때 

$$\begin{array}{rl}& \frac{\partial \tanh (W{\mathbf{h}}_{\mathbf{t}}+Wx+b)}{\partial {\mathbf{h}}_{\mathbf{t}}}\\ & =(1-{\tanh }^2(W{h}_t+Wx+b))W\end{array}$$

 

문제가 되는 것은 $W$ term인데, 긴 sequence에 대해 backpropagate를 할 때에는 이 동일한 matrix를 계속해서 곱하게 되기 때문이다. 같은 값을 곱할 때에는 정확히 같은 값이 되거나, 0에 수렴하게 되거나(vanishing gradient), 발산하는 경우(exploding gradient)가 있다. 같은 값이 되는 경우는 practical하게는 거의 나타나지 않으므로 긴 sequence의 backpropagation에서는 항상 두 문제 중 하나가 발생한다고 보아야 한다.

 

이 심각한 문제를 해결하기 위해 여러 가지 방법이 제안되었는데, Gradient clipping도 그 중 하나이다. gradient clipping은 값의 L2 norm이 너무 커지면 나누어 주는 heuristic이다. 

 

결과적으로는 LSTM이 가장 효과적인 대안으로 제시되었고, 오늘날에는 vanilla RNN은 거의 사용하지 않는다. 

---

References

Gang Chen. (2016). A Gentle Tutorial of Recurrent Neural Network with Error Backpropagation. Department of Computer Science and Engineering, SUNY at Buffalo. 

Fei-Fei Li, J. Johnson, S. Yeung. (2017). Convolutional Neural Networks for Visual Recognition. Dept. of Comp. Sci., Stanford University, Palo Alto, CA, USA, spring 2017 [Online]. 

 

Footnotes

1. time series는 index가 integer $t$로 이루어진 특수한 경우를 가리킨다. reference :  https://stats.stackexchange.com/questions/126791/is-a-time-series-the-same-as-a-stochastic-process [본문으로]