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

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

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

 

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

 

 

 

1. 퍼셉트론(Perceptron)

그림 1. 퍼셉트론의 구조

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

$$ a = w_0 + \sum_{i = 1}^p w_i x_i = \mathbf{w}^{\top} \mathbf{x}$$

을 통해 $a$값을 얻게 됩니다. 여기서 $\mathbf{w} = \left[ w_0, \cdots, w_p \right]$로, 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} = \left\{ (\mathbf{x}_n, y_n), n = 1, \cdots, N \right\}$에 대하여,  

$$\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} \gets \mathbf{w} - \eta \triangledown_{\mathbf{w}}E_n(\mathbf{w})$$ 으로 GDA를 적용하여 $E_n(\mathbf{w})$를 최소로 하는 $\mathbf{w}$를 찾을 수 있겠죠.

 

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

$$w_{ij} \gets 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} \gets w_{ij} - \eta \frac{\partial E_n}{\partial w_{ij}}$$