역 전파 알고리즘

역 전파 알고리즘

Back Propagation Algorithm

이 글은 역전파 알고리즘의 원리를 수학 전공자가 이해하기 쉽도록 작성되었다.

표기법

1.PNG

위 그림과 같은 인공 신경망이 주어졌다고 하자. $\mathbf{x} = (x_{1}, x_{2}, \dots, x_{n_{0}})$는 입력input, $y_{j}^{l}$는 $l$번째 층의 $j$번째 노드, $\hat{\mathbf{y}} = (\hat{y}_{1}, \hat{y}_{2}, \dots, \hat{y}_{\hat{n}})$는 출력output이다.

$L \in \mathbb{N}$은 은닉층hidden layer의 개수이고, $\mathbf{n}=(n_{0}, n_{1}, \dots, n_{L}, \hat{n}) \in \mathbb{N}^{L+2}$의 성분은 순서대로 입력층, $L$개의 은닉층, 출력층의 노드의 수를 의미한다. 또한 편의상 $0$번째 은닉층은 입력층을 의미하고, $L+1$번째 은닉층은 출력층을 의미한다고 하자.

$w_{ji}^{l}$은 $l$번째 층의 $i$번째 노드와 그 다음 층의 $j$번째 노드를 연결하는 가중치를 나타낸다. 그러면 각 층에서 다음 층으로의 전파는 아래의 움짤과 같이 일어난다.

1.gif

여기서 $\phi$는 임의의 활성화 함수이다. $l$번째 층에서 다음 층의 $j$번째 노드로 전달되는 선형결합을 $v_{i}^{l}$로 표기하자.

$$ \begin{align*} v_{j}^{l} &= \sum _{i=1}^{n_{l}} w_{ji}^{l}y_{i}^{l} \\ y_{j}^{l+1} &= \phi ( v_{j}^{l} ) = \phi \left( \sum \nolimits_{i=1}^{n_{l}} w_{ji}^{l}y_{i}^{l} \right) \end{align*} $$

이를 정리하면 다음과 같다.

기호 의미
$\mathbf{x}=(x_{1}, x_{2}, \dots, x_{n_{0}})$ 입력
$y^{l}_{j}$ $l$번째 층의 $j$번째 노드
$\hat{\mathbf{y}} = (\hat{y}_{1}, \hat{y}_{2}, \dots, \hat{y}_{\hat{n}} )$ 출력
$n_{l}$ $l$번째 층의 노드 수
$w_{ji}^{l}$ $l$번째 층의 $i$번째 노드와 그 다음 층의 $j$번째 노드를 연결하는 가중치
$\phi$ 활성화 함수
$v_{j}^{l} = \sum \limits _{i=1} ^{n_{l}} w_{ji}^{l}y_{i}^{l}$ 선형결합
$y^{l+1}_{j} = \phi (v_{j}^{l})$ $l$번째 층에서 다음 층으로의 전파

정리

$E = E(\hat{\mathbf{y}})$를 미분가능한 적절한 손실 함수라고 하자. 그러면 $E$를 최적화하는 방법은 각 층에서의 가중치 $w_{ji}^{l}$들을 다음과 같이 업데이트하는 것이다.

$$ \begin{equation} w_{ji}^{l} \leftarrow w_{ji}^{l} + \alpha \delta^{l}_{j} y_{i}^{l} \label{thm} \end{equation} $$

이때 $\alpha$는 학습률이고, $\delta_{j}^{l}$은 다음과 같다. $l=L$일 때,

$$ -\delta_{j}^{L} = \phi ^{\prime} (v_{j}^{L}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{j}} $$

$l \in \left\{ 0,\dots, L-1 \right\}$일 때,

$$ \delta_{j}^{l} = \phi ^{\prime} (v_{j}^{l}) \sum_{i=1}^{n_{l}} \delta_{i}^{l+1} w_{i j}^{l+1} $$

설명

$\eqref{thm}$을 살펴보자. $l$번째 층과 $l+1$번째 층 사이의 가중치를 업데이트할 때 $l$번째 노드들 $y_{j}^{l}$에 의존한다는 말인데, 각 층의 출력에 따라 최종적으로 출력 $\hat{\mathbf{y}}$이 결정되므로 당연하다고 볼 수 있다. 또한 $y_{j}^{l}$들은 $l$번째에서 $l+1$번째 층으로 전파될 때의 입력으로 볼 수 있는데, 이는 선형회귀모델에서 LMSLeast Mean Squares로 학습하는 방법과 비슷한 꼴이다.

$$ \mathbf{w} \leftarrow \mathbf{w} - \alpha (\mathbf{w}^{T}\mathbf{x} - \mathbf{y}) \mathbf{x} $$

한편 각 층에서의 출력 $y_{j}^{l}$들은 입력층에서부터 출력층으로 계산되는 반면에 최적화를 위한 $\delta_{j}^{l}$들은 다음과 같이 출력층에서부터 입력층으로 거꾸로 계산되기 때문에 이러한 최적화 기법을 역 전파 알고리즘back propagation algorithm이라 한다.

$$ \begin{align*} \delta_{j}^{L} &= - \phi ^{\prime} (v_{j}^{L}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{j}} \\ \delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \delta_{j}^{L} w_{ij}^{L} \\ \delta_{j}^{L-2} &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \delta_{i}^{L-1} w_{ij}^{L-1} \\ \delta_{j}^{L-3} &= \phi ^{\prime} (v_{j}^{L-3}) \sum _{i} \delta_{i}^{L-2} w_{ij}^{L-2} \\ &\vdots \\ \delta_{j}^{1} &= \phi ^{\prime} (v_{j}^{1}) \sum _{i} \delta_{i}^{2} w_{ij}^{2} \\ \delta_{j}^{0} &= \phi ^{\prime} (v_{j}^{0}) \sum _{i} \delta_{i}^{1} w_{ij}^{1} \end{align*} $$

증명

입력층에서부터 출력층으로의 계산이 끝났다고 하자. 가중치를 손실 함수 $E$가 줄어드는 방향으로 수정하는 방법은 경사하강법을 사용하면 다음과 같다.

$$ \begin{equation} w_{ji}^{l} \leftarrow w_{ji}^{l} - \alpha \dfrac{\partial E(\hat{\mathbf{y}})}{\partial w_{ji}^{l} } \label{gradesent} \end{equation} $$

각각의 $y_{i}^{l}$들은 주어진 값이므로, 편미분 부분을 계산할 수 있는 꼴로 풀어내면 된다. 우변의 편미분은 연쇄법칙에 의해 다음과 같다.

$$ \begin{equation} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial w_{ji}^{l}} = \dfrac{\partial E(\hat{\mathbf{y}}) }{\partial v_{j}^{l}} \dfrac{\partial v_{j}^{l}}{\partial w_{ji}^{l}} = \dfrac{\partial E(\hat{\mathbf{y}})}{\partial v_{j}^{l}} y_{i}^{l} \label{chainrule} \end{equation} $$

$\eqref{chainrule}$의 우변의 편미분을 $-\delta_{j}^{l}$로 두면, $\eqref{gradesent}$로부터 $\eqref{thm}$을 얻는다.

$$ w_{ji}^{l} \leftarrow w_{ji}^{l} + \alpha \delta^{l}_{j} y_{i}^{l} $$

각 층에서 $\delta_{j}^{l}$를 다음과 같이 구한다.

  • $l = L$인 경우

    $j \in \left\{ 1, \dots, \hat{n} \right\}$에 대해서 다음이 성립한다.

    $$ \begin{equation} -\delta_{j}^{L} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial v_{j}^{L}} = \dfrac{\partial E ( \hat{\mathbf{y}} ) } {\partial \hat{y}_{j}} \dfrac{d \hat{y}_{j}}{d v_{j}^{L}} \label{deltamL} \end{equation} $$

    이때 $\hat{y}_{j} =\phi (v_{j}^{L})$이므로 다음을 얻는다.

    $$ -\delta_{j}^{L} (t) =\phi ^{\prime} (v_{j}^{L}(t)) \dfrac{\partial E (\hat{\mathbf{y}})}{\partial \hat{y}_{j}} $$

  • $l = L-1$인 경우

    $j \in \left\{ 1, \dots, n_{L-1} \right\}$에 대해서 다음과 같다.

    $$ -\delta_{j}^{L-1} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial v_{j}^{L-1}} = \dfrac{\partial E ( \hat{\mathbf{y}} ) } {\partial y_{j}^{L}} \dfrac{d y_{j}^{L}}{d v_{j}^{L-1}} $$

    이때 $y_{j}^{L} =\phi (v_{j}^{L-1})$이므로 다음을 얻는다.

    $$ -\delta_{j}^{L-1} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial y_{j}^{L}} \dfrac{\partial y_{j}^{L}}{\partial v_{j}^{L-1}} = \phi ^{\prime} (v_{j}^{L-1}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L}} $$

    우변의 편미분은 연쇄법칙에 의해 다음과 같이 계산된다.

    $$ \begin{align*} -\delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L}} \\ &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{\partial \hat{y}_{i}}{\partial y_{j}^{L}} \\ &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \dfrac{\partial v_{i}^{L}}{\partial y_{j}^{L}} \end{align*} $$

    여기서 $\eqref{deltamL}$와 ${\color{green}v_{i}^{L}=\sum_{j}w_{ij}^{L}y_{j}^{L}}$에 의해 다음을 얻는다.

    $$ \begin{align} && -\delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i=1} {\color{blue}\dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{\partial \hat{y}_{i}}{\partial v_{i}^{L}}} {\color{green} \dfrac{d v_{i}^{L}}{d y_{j^{L}}} } \nonumber \\ && &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} {\color{blue} -\delta_{i}^{L}} {\color{green} w_{ij}^{L} }\nonumber \\ {}\nonumber \\ \implies && \delta_{j}^{L-1} &= \phi ^{\prime} (v_{j}^{L-1}) \sum _{i} \delta_{i}^{L} w_{ij}^{L} \label{deltajL-1} \end{align} $$

  • $l = L-2$인 경우

    $j \in \left\{ 1, \dots, n_{L-2} \right\}$에 대해서 다음과 같다.

    $$ -\delta_{j}^{L-2} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial v_{j}^{L-2}} = \dfrac{\partial E ( \hat{\mathbf{y}} ) } {\partial y_{j}^{L-1}} \dfrac{d y_{j}^{L-1}}{d v_{j}^{L-2}} $$

    이때 $y_{j}^{L-1} =\phi (v_{j}^{L-2})$이므로 다음을 얻는다.

    $$ -\delta_{j}^{L-2} = \dfrac{\partial E (\hat{\mathbf{y}})}{\partial y_{j}^{L-1}} \dfrac{d y_{j}^{L-1}}{d v_{j}^{L-2}} = \phi ^{\prime} (v_{j}^{L-2}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L-1}} $$

    우변의 편미분은 연쇄법칙에 의해 다음과 같이 계산된다.

    $$ \begin{align*} -\delta_{j}^{L-2} &= \phi ^{\prime} (v_{j}^{L-2}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{\partial \hat{y}_{i}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \dfrac{\partial v_{i}^{L}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \sum _{k} \dfrac{\partial v_{i}^{L}}{\partial y_{k}^{L}} \dfrac{\partial y_{k}^{L}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}} \sum _{k} \dfrac{\partial v_{i}^{L}}{\partial y_{k}^{L}} \dfrac{d y_{k}^{L}}{d v_{k}^{L-1}} \dfrac{\partial v_{k}^{L-1}}{\partial y_{j}^{L-1}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \sum _{i} {\color{blue}\dfrac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i}} \dfrac{d \hat{y}_{i}}{d v_{i}^{L}}} {\color{red}\dfrac{\partial v_{i}^{L}}{\partial y_{k}^{L}} } {\color{green}\dfrac{d y_{k}^{L}}{d v_{k}^{L-1}}} {\color{purple}\dfrac{d v_{k}^{L-1}}{\partial y_{j}^{L-1}}} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \sum _{i} {\color{blue} -\delta_{i}^{L}} {\color{red} w_{ik}^{L}} {\color{green} \phi^{\prime}(v_{k}^{L-1})} {\color{purple} w_{kj}^{L-1}} \end{align*} $$

    따라서 다음을 얻는다.

    $$ \delta_{j}^{L-2} = -\phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \sum _{i} \delta_{i}^{L} w_{ik}^{L} \phi^{\prime}(v_{k}^{L-1}) w_{kj}^{L-1} $$

    이때 $\eqref{deltajL-1}$에 의해 다음이 성립한다.

    $$ \sum _{i} \delta_{i}^{L} w_{ik}^{L} \phi^{\prime}(v_{k}^{L-1}) = \phi^{\prime}(v_{k}^{L-1}) \sum _{i} \delta_{i}^{L} w_{ik}^{L} = \delta_{k}^{L-1} $$

    따라서 다음을 얻는다.

    $$ \begin{align*} \delta_{j}^{L-2} &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{k} \delta_{k}^{L-1} w_{kj}^{L-1} \\ &= \phi ^{\prime} (v_{j}^{L-2}) \sum _{i} \delta_{i}^{L-1} w_{ij}^{L-1} \end{align*} $$

  • 일반화: $l \in \left\{ 1, \dots, L-1 \right\}$

    위의 결과들을 토대로 다음과 같이 일반화 할 수 있다. $j \in \left\{ 1, \dots, n_{l} \right\}$에 대해서 다음과 같다.

    $$ -\delta_{j}^{l} = \phi ^{\prime} (v_{j}^{l}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{l}} $$

    우변의 편미분을 연쇄법칙으로 풀어내면 다음과 같다.

    $$ \begin{align*} &\quad \delta_{j}^{l} \\ &= -\phi ^{\prime} (v_{j}^{l}) \dfrac{\partial E(\hat{\mathbf{y}})}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{\partial \hat{y}_{i_{(1)}}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{\partial y_{i_{(2)}}^{L}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{i_{(3)}}^{L-1} } \frac{\partial y_{i_{(3)}}^{L-1} }{ \partial y_{j}^{l}} \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{i_{(3)}}^{L-1} } \frac{d y_{i_{(3)}}^{L-1} }{d v_{i_{(3)}}^{L-2} } \frac{\partial v_{i_{(3)}}^{L-2} }{ \partial y_{j}^{l}} \\ & \quad \vdots \\ &= -\phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} \frac{\partial E(\hat{\mathbf{y}})}{\partial \hat{y}_{i_{(1)}}} \frac{d \hat{y}_{i_{(1)}}}{d v_{i_{(1)}}^{L}} \frac{\partial v_{i_{(1)}}^{L}}{\partial y_{i_{(2)}}^{L}} \frac{d y_{i_{(2)}}^{L}}{d v_{i_{(2)}}^{L-1}} \frac{\partial v_{i_{(2)}}^{L-1}}{\partial y_{i_{(3)}}^{L-1} } \frac{d y_{i_{(3)}}^{L-1} }{d v_{i_{(3)}}^{L-2} } \frac{\partial v_{i_{(3)}}^{L-2} }{ \partial y_{i_{(4)}}^{L-2}} \cdots \frac{d y_{i_{(L-l+1)}}^{l+1} }{d v_{i_{(L-l+1)}}^{l} } \frac{\partial v_ {i_{(L-l+1)}}^{l} }{ \partial y_{j}^{l}} \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \sum_{i_{(2)}} \sum_{i_{(1)}} -\delta_{i_{(1)}}^{L} w_{i_{(1)}i_{(2)}}^{L} \phi^{\prime}(v_{i_{(2)}}^{L-1}) w_{i_{(2)} i_{(3)}}^{L-1} \phi^{\prime}( v_{i_{(3)}}^{L-2} ) w_{i_{(3)} i_{(4)}}^{L-2} \cdots \phi^{\prime}(v_{L-l+1}^{l})w_{i_{(L-l+1)} j}^{L} \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \sum_{i_{(2)}} \delta_{i_{(2)}}^{L-1}w_{i_{(2)} i_{(3)}}^{L-1} \phi^{\prime}( v_{i_{(3)}}^{L-2} ) w_{i_{(3)} i_{(4)}}^{L-2} \cdots \phi^{\prime}(v_{L-l+1}^{l})w_{i_{(L-l+1)} j}^{L} \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \cdots \sum_{i_{(3)}} \delta_{i_{(3)}}^{L-2} w_{i_{(3)} i_{(4)}}^{L-2} \cdots w_{i_{(L-l)} j}^{L} \\ &\quad \vdots \\ &= \phi ^{\prime} (v_{j}^{l}) \sum_{i_{(L-l)}} \delta_{i_{(L-l)}}^{l+1} w_{i_{(l-l)} j}^{l} \end{align*} $$

    따라서 정리하면 다음과 같다.

    $$ \delta_{j}^{l} = \phi ^{\prime} (v_{j}^{l}) \sum_{i} \delta_{i}^{l+1} w_{ij}^{l+1} $$

댓글