역전파 알고리즘(Back-propagation Algorithm)

Francisco S. Melo 선생님의 Neural networks and the Back-propagation algorithm을 참고하였음을 밝힙니다.

구글에 검색하면 pdf파일 나오니까 참고하면서 보면 좋을 듯합니다. 여기에서 다운로드 받으실 수 있습니다.

 

이제 수식으로 역전파 알고리즘을 이해해볼텐데요, 편미분과 그래디언트 디센트 알고리즘(Gradient Descent Algorithm), 벡터의 내적과 행렬의 곱셈에 대한 개념이 있어야 이해에 도움이 될 것입니다.

 

 

 

1. 퍼셉트론(Perceptron)

그림 1. 퍼셉트론의 구조

퍼셉트론을 잘 나타내는 그림입니다. 데이터 $\mathbf{x}=[x_0,\cdots ,x_p]$가 activation 함수를 거치면

$$a=w_0+\sum _{i=1}^p{w}_i{x}_i={\mathbf{w}}^{\mathrm{\top }}\mathbf{x}$$

을 통해 $a$값을 얻게 됩니다. 여기서 $\mathbf{w}=[w_0,\cdots ,w_p]$로, weight 벡터로 보면 됩니다. 퍼셉트론이 $n$개의 뉴런을 가지고 있다면 $\mathbf{w}$는 $n\times p$행렬이 되겠죠. 이렇게 얻은 $a$값이 Threshold 함수를 거치면 0과 1사이의 값을 갖게 됩니다. 보통 미분가능한 Threshold 함수로 Sigmoid 함수를 채택하는 것 같습니다. Sigmoid 함수는 

$$Sigmoid(x)=\frac{1}{1+e^{-x}}$$

로 나타낼 수 있고, 그래프로 나타내면

그림 2. Sigmoid 함수

이렇게 됩니다.

 

이 포스트에서는 역전파 알고리즘이 어떻게 작동하는지 보이는 것이 목적이기 때문에 퍼셉트론에 대한 설명은 이 정도로 충분할 것 같습니다. 다중 퍼셉트론에 대한 개념은 미리 알고 이 포스트를 보기를 권장합니다. 또한 이 포스트에서는 앞으로 이 Sigmoid 함수를 

$$\sigma (x)=\frac{1}{1+e^{-x}}$$

로 쓸 것입니다.

 

 

 

 

2. 역전파 알고리즘(Back-propagation Algorithm)

그림 3. Unit $j$ in the network

먼저 이 그림을 보겠습니다. 각 $a_j$는 이전 단계의 Sigmoid 함수를 거친 $\mathbf{z}$ 벡터와 $\mathbf{w}$ 벡터의 내적을, 각 $z_j$는 해당 $a_j$의 Sigmoid 함수값을 나타냅니다.

 

우리의 목표는 우리가 만든 인공신경망을 통과하여 얻은 클래스값과 데이터가 실제로 가지고 있는 클래스값의 차이, 즉 오차를 최소화하는 것입니다. 오차들의 제곱합을 수식으로 나타내면 주어진 데이터셋 $\mathcal{D}=\{({\mathbf{x}}_n,y_n),n=1,\cdots ,N\}$에 대하여,  

$$\mathcal{E}(\mathbf{w})=\frac{1}{2}\sum _{n=1}^N(\hat{y}({\mathbf{x}}_n)-y_n{)}^2$$

입니다. weight벡터에 따라 오차가 결정되는 것이죠. $\hat{y}$는 데이터셋이 신경망을 통과하고 갖게 되는 값입니다. 우변의 앞에 $\frac{1}{2}$를 붙인 까닭은 이후에 미분했을 때 모양을 잘 나오게 하기 위함입니다.

 

오차함수 $\mathcal{E}$를 최소화하는 $\mathbf{w}$를 구하기 위해 그래디언트 디센트 알고리즘(Gradient Descent Algorithm; GDA)가 필요하다는 것은 알고있어야 합니다. GDA에 대해 모른다면 이에 대해 먼저 공부하고 이 포스트를 읽기를 권장합니다.

 

아무튼 오차함수 $\mathcal{E}$는 각 데이터에 대한 오차들의 제곱합입니다. 따라서 GDA를 그대로 적용하기에 무리가 있죠. 따라서 역전파 알고리즘은 각 데이터의 오차 제곱을 $$E_n(\mathbf{w})=\frac{1}{2}(\hat{y}({\mathbf{x}}_n)-y_n{)}^2$$으로 두기로 하고, 그러면 오차함수를 $$\mathcal{E}(\mathbf{w})=\sum _{n=1}^N{E}_n(\mathbf{w})$$으로 다시 쓸 수 있습니다. 이제 GDA를 쓰기 괜찮은 모양이 되었습니다. $$\mathbf{w}\leftarrow \mathbf{w}-\eta {▽}_{\mathbf{w}}{E}_n(\mathbf{w})$$ 으로 GDA를 적용하여 $E_n(\mathbf{w})$를 최소로 하는 $\mathbf{w}$를 찾을 수 있겠죠.

 

지금부터 편미분 개념이 필요합니다. 오차를 최소화하는 $\mathbf{w}$을 찾기 위해서 각 $w_{ij}$에 대해 $E_n$을 편미분 할 것입니다. 이 과정을 통해 원래 우리가 하고자 했던 $$\mathbf{w}\leftarrow \mathbf{w}-\eta {▽}_{\mathbf{w}}{E}_n(\mathbf{w})$$에서 $\mathbf{w}$를 $w_{ij}$로 치환하여

$$w_{ij}\leftarrow w_{ij}-\eta \frac{\partial E_n}{\partial w_{ij}}$$을 구하는 것이죠. 한 번에 벡터를 구할 수 없으니 개별 값을 하나하나 구하는 것입니다. 그래디언트 기호가 편미분 기호로 바뀐 것은 $E_n$을 단일 변수인 $w_{ij}$에 대해 편미분 했기 때문입니다.

 

자, 이제 $\frac{\partial E_n}{\partial w_{ij}}$를 구해야겠죠. Chain Rule을 이용해 다음과 같이 나타낼 수 있습니다.

$$\frac{\partial E_n}{\partial w_{ij}}=\frac{\partial E_n}{\partial a_j}\frac{\partial a_j}{\partial w_{ij}}$$ 

식이 좀 복잡하니 간단하게 풀어봅시다. $${\delta }_j=\frac{\partial E_n}{\partial a_j}$$ 으로 두고, 그림 3을 통해

$$\frac{\partial a_j}{\partial w_{ij}}=z_i$$임을 알 수 있죠. ($\because a_j=\cdots +w_{ij}{z}_i+\cdots$) 이제 이 식들을 모두 종합해 정리하면 $$\frac{\partial E_n}{\partial w_{ij}}={\delta }_j{z}_i$$ 입니다. 여기서 우리는 $z_i$을 이미 알고 있기 때문에 ${\delta }_j$값만 계산하면 됩니다.

이제 두 가지 케이스로 나누어 생각해야합니다. 그 전에 수식을 좀 많이 봤으니 우리가 최종적으로 구하고자 하는 것이 무엇인지 상기하도록 하죠. 우리는 오차함수를 최소화하는 $\mathbf{w}$를 구하기 위해 새로운 함수 $E_n$를 선언했고, 이 $E_n$을 최소화하기 위해 GDA를 사용할 것입니다. 그러기 위해 $E_n$을 $w_{ij}$에 대해 편미분하여 식을 간단히 바꾸는 과정까지 완료했습니다. $\frac{\partial E_n}{\partial w_{ij}}$를 구하기 위해 앞으로 나올 두 가지 케이스는 다음과 같습니다.

 

Case 1. $j$가 output unit일 때

$j$가 output unit이라면 $$E_n=\frac{1}{2}(\sigma (a_j)-y_n{)}^2$$이 되겠죠. 여기서 우리는 양변을 $a_j$로 편미분할 것입니다. 그러면, $$\frac{\partial E_n}{\partial a_j}={\delta }_j={\sigma }^{\prime }(a_j)(\sigma (a_j)-y_n)=\sigma (a_j)(1-\sigma (a_j))(\sigma (a_j)-y_n)$$이 됩니다. 도함수 ${\sigma }^{\prime }$가 위 식처럼 어떻게 변하는지는 직접 계산해보시기 바랍니다. 직접 해보면 그리 어렵지 않습니다.

 

Case 2. $j$가 output unit이 아닐 때(역전파)

$j$가 output unit이 아니라면, 해당 $a_j$에 대해서 Sigmoid 함수를 거친 $z_j$값이 있을 것이고, 그 $z_j$값과 연결된 다음 단계인 $k$번 째 Layer의 Node(weight)들이 있을 것입니다. 이해가 어려울 수 있는데 그림 3을 보면서 이해해보시기 바랍니다. 지금 우리가 구하고자 하는 값은 $\frac{\partial E_n}{\partial w_{jk}}$입니다. 이 값을 ${\delta }_k{z}_j$로 간단하게 만들었었죠? 이미 $z_j$값은 알고있기 때문에 ${\delta }_k=\frac{\partial E_n}{\partial a_k}$만 구하면 됩니다. 아래의 식을 보시죠.

$$\frac{\partial E_n}{\partial a_j}=\sum _{k=1}^K\frac{\partial E_n}{\partial a_k}\frac{\partial a_k}{\partial a_j}=\sum _{k=1}^K{\delta }_k\frac{\partial a_k}{\partial a_j}$$

위 식에서 $a_k$는 $k$번 째 Layer에서 $a_j$로부터 영향을 받은 값들입니다. 즉 $z_j=\sigma (a_j)$에 어떤 weight가 곱해진 값이겠죠. 그렇기 때문에 Chain Rule을 이용해 위와 같은 식으로 나타낼 수 있습니다. 이제 우리는 아래와 같은 식을 얻을 수 있습니다. 

$$\frac{\partial a_k}{\partial a_j}=w_{jk}{\sigma }^{\prime }(a_j)$$

앞에서 $a_k$는 $a_j$의 영향을 받았다고 했죠. 이것을 수식으로 나타내면 $a_k=\cdots +w_{jk}\sigma (a_j)+\cdots$입니다. $w_{jk}$는 $k$번 째 Layer의 $j$번 째 Node였죠. 따라서 이 weight가 $a_j$의 Sigmoid 함수값과 곱해진 값이 $a_k$를 구성하게 됩니다. 따라서 $a_k$를 $a_j$에 대해 편미분했을 때 위와 같은 식을 얻을 수 있는 것이죠. 따라서 ${\delta }_j$에 대해

$${\delta }_j=\frac{\partial E_n}{\partial a_j}={\sigma }^{\prime }(a_j)\sum _{k=1}^K{w}_{jk}{\delta }_k$$

위와 같은 식을 얻을 수 있습니다.

 

이제 역전파 알고리즘을 수행할 모든 준비가 끝난 것입니다. 알고리즘을 수행하기에 앞서 $\mathbf{w}$의 초기값을 설정해주어야 합니다. 초기값을 잘 설정하는 방법이 있겠지만 저도 아직 딥러닝을 처음 공부하는 사람인지라,,^^ 일단 임의로 초기값을 설정하는 것으로 하죠.

 

역전파 알고리즘은 다음과 같습니다. 주어진 데이터셋 $\mathcal{D}=\{({\mathbf{x}}_n,y_n),n=1,\cdots ,N\}$ 에 대해, 

 

1. 각 데이터 $({\mathbf{x}}_n,y_n)\in \mathcal{D}$에 대해 forward propagate합니다. 

forward propagate는 초기값을 설정한 퍼셉트론에 일단 데이터를 넣고 각 Layer와 Node에 대해 모든 $a_j$값들을 구하고 최종적으로 $\hat{y}({\mathbf{x}}_n)$까지 모두 구하는 과정을 말합니다.

 

2. Output unit에 대해 ${\delta }_j$를 구합니다.

 

3. 역전파 과정을 통해 output unit이 아닌 모든 $j$에 대해 ${\delta }_j$를 구합니다.

 

4. 모든 노드들에 대해서 $\frac{\partial E_n}{\partial w_{ij}}$을 구합니다.

 

5. GDA로 $w_{ij}$의 수렴값을 찾습니다. 다음과 같은 식을 쓰면 되겠죠. $$w_{ij}\leftarrow w_{ij}-\eta \frac{\partial E_n}{\partial w_{ij}}$$