[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 $\textbf{x} = \{\bf{x_1,x_2,...,x_T}\}$와 corresponding label $y=\{y_1,y_2,...,y_T\}$에 대해서, mapping transformation $f: \textbf{x} \mapsto y $을 학습하는 것이다. 이 경우에, sequential data를 model하는 방법으로서 RNN이 사용된다.

---

Recurrent Neural Network

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

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

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

따라서, 현재 $h_t$는 현재의 input $\bf {x_t}$에 대한 정보만 저장하고 있는 것이 아니라 지금까지 입력된 모든 $\bf {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 \left ( softmax(\alpha_t) \right )$$

 

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

$$p(\hat y_h | {\bf h_t } ; \Theta) = {\exp(\alpha_j(\Theta) \over \sum_k \exp(\alpha_k (\Theta)) } $$

이므로 $\alpha_j(\Theta)$의 partial derivative를 구하면

$$\begin{align} &{  \partial y_j \log p(\hat y_j | {\bf h_t}; \Theta ) \over \partial \alpha_j} \\  &= { \partial y_j \log ({\exp(\alpha_j) \over \sum_k \exp(\alpha_k)} ) \over \partial \alpha_j} \\ &= y_j \sum_k \exp(\alpha_k) \left ( { - (\exp(\alpha_j))^2 \over (\sum_k {\exp (\alpha_k) })^2 } + {\exp(\alpha_j) \over \sum_k {\exp(\alpha_k)}}\right ) \\ &= y_j \left ( {\sum_k{\exp(\alpha_k)} - \exp(\alpha_j) \over \sum_k{\exp(\alpha_k)} }\right ) \\ &=y_j(1-p_j)\end{align}$$

 

이다.

 

비슷한 방법으로 $\forall k \neq j$인 경우에 그 prediction $p(\hat y_k)$ 에 대해서도, $\alpha_j(\Theta)$에 대한 미분을 구하면 다음과 같다.

 

$$ \begin{align} &{ \partial y_k \log p(\hat y_k | {\bf y_t} ; \Theta) \over \partial \alpha_j } \\ &= {y_k \over p (\hat y_k} {-\exp(\alpha_k(\Theta)) \exp(\alpha_j(\Theta)) \over  [ \sum_s \exp(\alpha_s (\Theta)) ]^2} \\ &= -y_k p(\hat y_j)\end{align} $$

 

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

 

 

$$ \begin{align} &{\partial p(\hat {\bf y}) \over \partial \alpha_j} = \sum_j {\partial y_j \log p(\hat y_j | {\bf h_i}; \Theta) \over \partial \alpha_j} \\ &={\partial \log p (\hat y_j)  | {\bf h_i} ; \Theta ) \over \partial \alpha_j } + \sum_{k \neq j} {\partial \log p(\hat y_k | {\bf h_i } ; \Theta ) \over \partial \alpha_j} \\ &=  y_j - y_jp(\hat y_j ) - \sum_{k \neq j} y_k p (\hat y_j) \\ &= y_j - p(\hat y_j)(y_j + \sum_{k \neq j} y_k ) \\ &= y_j - p(\hat y_j)\end{align} $$

 

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

$$ { \partial L \over W_{hz}} = \sum_t {\partial L \over \partial z_t} {\partial z_t \over \partial W_{hz}} $$

 

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

$$ {\partial L(t+1) \over \partial W_{hh}} = \sum_{k=1}^t {\partial L(t+1) \over \partial z_{t+1}} {\partial z_{t+1} \over \partial {\bf h_{h+1}}} {\partial {\bf h_{t+1}} \over \partial {\bf h_k}} {\partial {\bf h_t} \over \partial W_{hh}} $$

 

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

$$ {\partial L \over \partial W_{hh}} = \sum_t \sum_{k=1}^t {\partial L(t+1) \over \partial z_{t+1}} {\partial z_{t+1} \over \partial {\bf h_{h+1}}} {\partial {\bf h_{t+1}} \over \partial {\bf h_k}} {\partial {\bf h_t} \over \partial W_{hh}} $$

 

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

$$ {\partial L \over \partial W_{xh}} = \sum_t \sum_{k=1}^t {\partial L(t+1) \over \partial z_{t+1}} {\partial z_{t+1} \over \partial {\bf h_{h+1}}} {\partial {\bf h_{t+1}} \over \partial {\bf h_k}} {\partial {\bf h_t} \over \partial W_{xh}} $$

 

---

Vanishing gradient and Exploding Gradient problem

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

 

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

$$ {\partial {\bf h_{t+1}} \over \partial {\bf h_t}}{\partial {\bf h_{t}} \over \partial {\bf h_{t-1}}} \cdots {\partial {\bf h_{k+1}} \over \partial {\bf h_k}}$$

 

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

$$ {\partial \tanh( W {\bf h_{t}} + Wx + b) \over \partial {\bf h_t}} {\partial \tanh( W {\bf h_{t-1}} + Wx + b) \over \partial {\bf h_{t-1}}} \cdots {\partial \tanh( W {\bf h_{k}} + Wx + b) \over \partial {\bf h_k}}$$

 

이때 

$$\begin{align} &{\partial \tanh( W {\bf h_{t}} + Wx + b) \over \partial {\bf h_t}} \\ &= \left ( 1-\tanh ^2 (Wh_t + Wx + b) \right ) W \end{align}$$

 

문제가 되는 것은 $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 [본문으로]