Week 05: 2. Backpropagation Algorithm

Week 05: 2. Backpropagation Algorithm

---

본 장에서는 각각의 레어이어의 Wegiht을 학습하기위한 backpropagation알고리즘에 대해서 다룬다.

Gradient computation with forward propagation

각각의 Layer의 wegiht 초기 값을 결정하기 위해서 아래와 같이 forward propagation을 수행하게 된다.

아래와 같이 각각의 레이어에 맞는 $a^{(j)}$ 값들이 결정 된다.

Gradient computation: Backpropagation algorithm

Bakpropagatio 알고리즘의 목적은 각각의 $\theta$값들이 Cost function $J$에 미치는 영향을 효율적으로 계산하는 것이다. 즉Gradient를 계산 하는 것이다.

Gradient를 구하게 되면, Gradient descent알고리즘으로 아래와 같이 cost $J$를 최소화 하는 $\Theta$를 찾을 수 있다.

$$ min_{\theta}J(\theta) $$

Gradient는 아래와 같이 편미분을 수행 해야 한다.

$$\dfrac{\partial}{\partial \Theta_{i,j}^{(l)}}J(\Theta)$$

이것을 빨리 계산하기 위해서 Backpropagation알고리즘을 이용한다.

각각의 레어이어의 노드 j에서의 에러는 아래와 같이 정의된다.

$\delta_{j}^{(l)}$ = error of node $j$ in layer $l$.

마지막 레이어 에서의 error 값은 델타는 아래와 같이 계산 된다.
$$ \delta^{(L)} = a^{(L) - y} $$
L은 총 레이어의 수를 의미하고 $a^{L}$은 마지막 레이어에서의 activiation unit의 output이다.

각 레이어의 local error를 나타내는 식은 아래와 같이 $\delta$로 표현 된다.

$$\delta^{(l)} = ((\Theta^{(l)})^T \delta^{(l+1)})\ .*\ g'(z^{(l)})$$

이후 뉴런 계층도 아래와 같이 계산된다.
$$\delta^{(3)} = ((\Theta^{(3)})^T \delta^{(4)})\ .*\ g'(z^{(3)})$$

$$\delta^{(2)} = ((\Theta^{(2)})^T \delta^{(3)})\ .*\ g'(z^{(2)})$$

$\delta^{(L)}$를 이용해서 나머지 $\delta$들의 값들은 위와 같이 계산된다.
여기서 $\delta^{(1)}$이 없는 이유는 input 값을 변경하지 않기 위함이다.
input은 error로 생각하지 않는다.

식 유도하기

우선, network 구조는 위의 네트웍을 따른다.

이제 아래와 같이 $\theta^{(3)}$이 Cost function에 미치는 영향(gradient)을 계산해보자.

Sigmoid derivative
$$g(x) = \dfrac{1}{1 + e^{-x}}$$
$$\dfrac{d}{dx}g(x) = g(x)(1 - g(x))$$

Chain rule에 의해서 Cost function은 다음과 같이 편미분 된다.
Cost function을 미분을 간단하기 위해서 cross entropy가 아닌 square error로 생각하자. 그리고 non-multiclass classification (k=1)로 생각한다. 그럼 아래의 cross entropy가 간단해 진다.
실제로도 거의 유사하게 동작하기 위해서 만들어진 cost function이다.

$$cost(t) =y^{(t)} \ \log (h_\Theta (x^{(t)})) + (1 - y^{(t)})\ \log (1 - h_\Theta(x^{(t)}))$$

$$Cost = \frac{1}{2}(\hat{y}-y)^2$$

$$ \frac { \partial Cost }{\partial \theta^{ (3) }} = \frac { \partial Cost } {\partial a^{(4)} } \cdot \frac { \partial a^{(4)} }{\partial z^{ (4) }} \cdot \frac { \partial z^{(4)}} {\partial \theta ^{ (3) }} $$

$$ = (\hat{y}-y) \times g(z^{(4)})(1-g(z^{(4)}))\times a^{ (3) }$$

$$ = (\hat{y}-y) \times \hat{y}(1-\hat{y})\times a^{ (3) }$$

결국 $g(z^{(4)})=a^{(4)}$는 예측 값이므로 $\hat{y}$로 치환한 것이다.
그리고 특정 부분을 $\delta^{L}$로 치환 하면 아래와 같다.
여기서 $L$은 마지막 Layer를 의미한다.

$$\delta ^{ (L) }= (\hat{y}-y) \times \hat{y}(1-\hat{y})$$

$$=\delta^{(L)}\times a^{ (3) }$$

두 번째는 $\theta^{(2)}$이 Cost function에 미치는 영향을 계산해보자.

$$\frac { \partial Cost }{\partial \theta^{ (2) }} = \frac { \partial Cost } {\partial a^{(4)} } \cdot \frac { \partial a^{(4)} }{\partial z^{ (4) }} \cdot \frac { \partial z^{(4)}} {\partial a^{(3)}} \cdot \frac { \partial a^{(3)}} {\partial z^{(3)}} \cdot \frac { \partial z^{(3)}} {\partial \theta^{(2)}} $$

$$=(\hat{y}-y) \times \hat { y } (1-\hat { y } )\times \theta ^{ (3) }\times \frac { \partial a^{(3)}} {\partial z^{(3)}} \times \frac { \partial z^{(3)}} {\partial \theta^{(2)}}$$

나머지 뒷 부분도 모두 미분하면 아래와 같이 유도 된다.

$$=(\hat{y}-y) \times \hat { y } (1-\hat { y } )\times \theta ^{ (3) }\times g(z^{(3)})(1-g(z^{(3)}))\times a^{(2)} $$

여기서도 위와 마찬가지로 $\delta^{(3)}$을 정의해서 치환 하면 아래와 같다.

$$\delta^{(3)} = (\hat{y}-y) \times \hat{y}(1-\hat {y} )\times \theta^{(3)}\times g(z^{(3)})(1-g(z^{(3)}))$$

$$ \frac { \partial Cost } {\partial \theta ^{ (2) }} = \delta^{(3)}\times a^{ (2) }$$

그리고 $\delta^{(3)}$을 계산하기 위해서 앞에서 계산된 $\delta^{(L)}$을 활용할 수 있다.

$$\delta^{(L)} = (\hat{y}-y) \times \hat { y } (1-\hat { y } )$$

$$\delta^{(3)} = \delta ^{(L)} \times \theta^{(3)}\times g(z^{(3)})(1-g(z^{(3)}))$$

결국 생각해보면 각각의 $\delta$만 계산할 수 있다면, 해당 $\theta$즉 wegiht가 Cost function에 미치는 영향(Gradient)를 계산할 수 있다.
왜냐하면, $a^{(3)}$, $a^{(2)}$같은 값들은 forward propagation을 통해서 쉽게 구할 수 있기 때문이다.
그리고 각 layer에서의 gradient는 앞에서 계산한 delta를 활용하여 계산량을 줄일 수 있다.

$\delta_j^{(l)}$의 의미는 $a_j^{(l)}$에 대한 에러이다.
좀 더 formal하게 표현 하면 delta values are actually the derivative of the cost function:

$$\delta_j^{(l)} = \dfrac{\partial}{\partial z_j^{(l)}} cost(t)$$

결국 아래와 같이 Andrew Ng교수님이 말한 식이 유도 된 것이다.

$$\delta^{(l)} = ((\Theta^{(l)})^T \delta^{(l+1)})\ .*\ g'(z^{(l)})$$

$$ \frac { \partial Cost } {\partial \theta^{(l)}}=a^{(l)}\delta^{(l+1)}$$

결국 아래의 Andrew Ng 교수님 수업에서 말한 식이 도출 되었다.

Analyzing the mathematics

위 예제는 결국 [3-5-5-5]의 구조를 가진다. bais는 생각하지 않는다.
$\theta^{3}$는 [4 X 5]의 matrix 이다. bias를 포함하면 4 X 6 이지만 그렇게 생각하지 않는다.
$(\theta^{(3)})^{T}$라고 하면 결국 transpose 이기 때문에 [5 X 4] matrix가 된다.

이전에 계산한 $\delta^{4}$는 4x1 vector라고 하자.
[5 X 4] matrix with [4 X 1] vector를 계산하면 결국 [5 X 1] vector가 된다.
[5 X 1] matrix의 dimensionality는 $a^3$ vector와 같게 된다. 따라서 pairwise multiplication이 성공 한다.

결국, $\delta^{3}$은 $a^3.*(1-a^3)$이랑 연산을해서 구해 질 수 있다.
$\delta^2$도 마찬가지로 구할 수 있다.

Why do we do this?

모든 $\delta$를 계산 했다면 그것을 가지고
Cost function에 대한 각각의 $\theta$에 따른 Partial Derivative를 구할 수 있다.
이러한 Partial Derivative를 통해서 $\theta$값들이 Cost Function에 미치는 영향을 알 수 있다.
그리고 이 영향을 이용해서 gradient descent를 수행해서 최적화를 달성 할 수 있다.

Backpropagation의 장점은 이런한 각각의 $\theta$값을 $\delta$를 이용해서 효율적으로 구할 수 있다는 것이다.
하지만 이 방법을 이용하면 쉽게 구할 수 있다.

결국 아래와 같이 regularization을 람다 0으로 설정해서 무시한다면 간단한 식이 완성 된다.
$$ \dfrac{\partial}{\partial \Theta_{i,j}^{(l)}}J(\Theta) = a_j^l \delta_i^{(l+1)}$$

그리고 이러한 partial derivative 값들을 이용해서 cost function을 최소화 하는 $\theta$값들을 찾게 된다.
즉 각각의 $\theta$가 y에 미치는 영향을 계산하여 각각의 $\theta$를 업데이트 할 수 있는 것이다.

좀 더 자세한 Python기반 코드는 링크에 있다.

알고리즘 상세 설명

Training set이 아래와 같이 있다고 가정해 보자.
$\lbrace (x^{(1)}, y^{(1)}) \cdots (x^{(m)}, y^{(m)})\rbrace$

최종적인 델타값은 모든 트레닝에 대해서 각각의 델타값을 누적한다음 평균값을 구해야 한다.
따라서 누적을 위한 델타 값을 아래와 같이 0으로 설정한다.
$\Delta^{(l)}_{i,j}$

이제 루프를 전 트레이닝 셋에 대해서 돌면서 수행 한다.

For t = 1 to m 까지

$a^{(1)}$은 $x^{(t)}$로 초기화 된다.
forward propagation을 통해서 각각의 layer에 있는 $a^l$들을 계산한다. l=1,2,..,L 까지 존재한다.
그다음 output label과 함께 $\delta^L$을 계산하고 그것을 이용해서 순차적으로 $\delta^L=a^L-y^t$를 계산하게 된다.
이렇게 함으로써 초기 delta 값들이 구해진다.
그다음 back propagation을 통해서 L-1 layer 를 구하고 차큰 차큰 내려 간다.
그리고 각 layer에서의 델타들을 아래와 같이 누적 시킨다.

여기서,

• $l$ = layer
• $j$ = node in that layer
• $i$ = the error of affected node in the target layer

위의 것을 vectorize하면 아래와 같다.

Finally
Loop를 모두 실행 하면 아래와 같이 누적한 값으로 평균 값을 구한다.
해당 평균 에러는 모든 트레이닝 데이터에 대한 값이 된다.

최종 Cost function J에 대한 partial derivative는 아래와 같이 구해진다.

결국 이를 통해서 각각의 $\theta$즉 parameter에 대한 partial derivative를 계산 할 수 있게 된다.
출력값에 미치는 영향을 계산 할 수 있으므로 이를 조정 할 수 있게 된다.

강의 슬라이드 페이지는 아래와 같다.

사실, Back-propagation의 좀 더 자세한 내용은 많인 강의에서 다루지 않는다.
이것도 나름 상세한 강의에 속하는 것 같다.
대략적인 컨셉과 수식적 표현은 알겠는데 아직 까지 남에게 설명할 정도는 안되는 것 같다.