[Machine Learning] Neural Network(Cost Function, Backpropagation Algorithm)

해당 내용은 Andrew Ng 교수님의 Machine Learning 강의(Coursera)를 정리한 내용입니다.

 

BP : Back-Propagation 역전파

FP : Forward Propagation 순전파

[Neural Network(Classification)]

우리는 Neural Network의 Cost Function 비용함수와, Parameter \(\theta\)를 구해주어야 한다.

위 그림과 같은 Neural Network와 m개의 Training Set이 주어졌을 때, 용어는 아래와 같이 정의한다.

\(L = \text{ total num layers in network}\)

\(s_l = \text{ num of unit(not counting bias unit) in layer l}\)

\(K = \text{ num of units(classes) in output layer}\)

위 그림에서 L = 4, \(s_1 = 3, s_2 = 5, s_3 = 5, s_4 = s_K = 4\), K = 4로 나타낼 수 있다. 

 

Classification 문제는 Binary Classification과 Multi-Class Classification(K classes)로 나누어지며, 아래처럼 정리할 수 있다.

Binary Classification은 1개의 Output Unit만 가지고, Multi-Class Classification은 K개의 분리된 Class에 대해서 각각의 Output Unit을 가지므로 K개의 Output Unit을 갖게되며, Hypothesis Fucntion의 결과값이 K 차원의 Output Vector로 나타난다. 

 

Binary Classification과 Multi-Class Classification의 Cost Function은 다음과 같이 나타낼 수 있다.

Binary Classification은 이전에 배운 Logistic Regression의 Cost Fucntion이며(Regularized된), Multi-Class Classification, 즉, Neural Network의 Cost Function은 Logistic Regression이 여러개인, 일반화된 것이라고 볼 수 있다.

$$ \begin{align*}J(\Theta) = -\frac{1}{m} \left [ \sum_{i = 1}^{m}{\color{red}\sum_{k = 1}^{K}}y_{\color{red}k}^{(i)}log(h_\Theta(x^{(i)}))_{\color{red}k} + (1 - y_{\color{red}k}^{(i)})log(1 - (h_\Theta(x^{(i)}))_{\color{red}k}) \right ] \\+ \frac{\lambda}{2m}{\color{red}\sum_{l = 1}^{L - 1}\sum_{i = 1}^{s_l}}\sum_{j = 1}^{\color{red}{s_{s_l + 1}}}{\color{red}(\Theta_{j,i}^{(l)})^2} \end{align*}$$

 

위 식에서 Ouput이 multiple nodes(K units)으로 나오기 때문에 몇 개의 nested summation이 추가되었다. 대괄호 사이에서는, Cost Function이 전체의 ouput node에 대해서 계산되어져야 하기 때문에 output node K 갯수만큼 반복되는 것이 추가되었다. 

Regularization(정규화) 항에서 \(\Theta\) 행렬의 열 갯수(i 항)는 현재 layer \(l\)의 node 갯수이고, 행 갯수(j 항)은 다음 layer의 node 갯수와 같다. 

즉 \(\Theta^{(l)}\)을 행렬로 나타내면,

$$\Theta^{(l)} = \begin{bmatrix} \Theta_{1,0}^{(l)} && \Theta_{1,1}^{(l)} && ... && \Theta_{1,s_j}^{(l)} \\ \Theta_{2,0}^{(l)} && \Theta_{2,1}^{(l)} && ... && \Theta_{2,s_j}^{(l)} \\ ... && ... && ... && ... \\ \Theta_{s_{j+1},0}^{(l)} && \Theta_{s_{j+1},1}^{(l)} && ... && \Theta_{s_{j+1},s_j}^{(l)} \end{bmatrix} $$

여기서 1열의 값은 현재 layer의 bias unit이고, 실제 삼중 합에서는 bias unit은 포함하지 않는다.

 

 

[Backpropagation Algorithm : 역전파 알고리즘]

이번에는 우리가 앞서 구한 Cost Function을 미분하고, 이 Cost를 최소화하는 Parameter \(\Theta\)를 구하는 알고리즘 Backpropagation Algorithm을 알아볼 것이다.

$$ \begin{align*}J(\Theta) = -\frac{1}{m} \left [ \sum_{i = 1}^{m}\sum_{k = 1}^{K}y_k^{(i)}log(h_\Theta(x^{(i)}))_k + (1 - y_k^{(i)})log(1 - (h_\Theta(x^{(i)}))_k) \right ] \\+ \frac{\lambda}{2m}\sum_{l = 1}^{L - 1}\sum_{i = 1}^{s_l}\sum_{j = 1}^{s_{s_l + 1}}(\Theta_{j,i}^{(l)})^2 \end{align*}$$

\(\rightarrow \underset{\Theta}{\min}J(\Theta)\)

우리는 위와 같은 Cost Function을 구했고, 이 Cost Function을 최소화하는 Parameter \(\Theta\)를 찾아야 한다. 

그러기 위해서는 Gradient Descent나 다른 알고리즘을 사용해야 한다.

즉, 우리는 Cost Function을 계산하고, 이를 편미분하는 코드를 사용해야 한다.

편미분 함수를 구하는데에, 우선 Training Set이 한 개의 (x, y)로 구성된 예제가 있다고 생각해보자.(1 example)

우리는 앞서 Forward Propagation(순전파)에 대해서, 아래와 같이 input layer에서 output layer로 진행된다고 배웠다.

 

input layer에서 ouput layer로 진행하면서 ouput을 구하는 Forward Propagation과는 반대로, BackPropagation은 ouput layer에서 시작해서(마지막 결과의 error를 먼저 구하고), 해당 error 값을 이용해서 각각의 layer에서의 error를 계산한다.

각 node의 error는 아래와 같이 나타낸다.

\(\delta_j^{(l)} = \text{ "error" of node j in layer l}\)

 

위의 예제와 같이 layer의 개수가 4개인 경우에 \(\delta_j^{(4)}\)는 단순히 계산된 \(a_j^{(4)}\) 값과 label 결과값 y의 차가 된다.

\(\delta_j^{(4)} = a_j^{(4)} - y_j\) (여기서 \(a_j^{(4)}\)는 \((h_\theta(x))_j\)이다.)

벡터화 하여 표현하면 \(\delta^{(4)} = a^{(4)} - y\) 이다.

그리고 이전 layer의 delta는 다음 공식에 의해서 구해진다.

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

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

여기서 .* 은 matlab(octave)에서 행렬의 element끼리의 곱을 의미하며, \({g}'\) 항은 sigmoid \(g(z)\) 를 미분한 것이고 아래와 같다.

\({g}'(z^{(3)}) = a^{(3)} .* (1 - a^{(3)})\)

\({g}'(z^{(2)}) = a^{(2)} .* (1 - a^{(2)})\)

 

---

\(g(z)\) 의 미분(\(g(z) = \frac{1}{1 + e^{-z}}\))

\(\frac{1}{1 + e^{-z}}\)에서 \(1 + e^{-z}\)를 \(f(z)\)로 둔다.

\( \begin{align*} \frac{\partial}{\partial z}g(z) &= \frac{\partial}{\partial z}\frac{1}{f(z)} = \frac{\partial}{\partial z}(1 + f(z))^{-1} \\ &= -(1 + f(z))^{-2}{f}'(z) = -(1 + f(z))^{-2}(-e^{-z}) = (\frac{1}{1 + e^{-z}})^2e^{-z} \\ &= (\frac{1}{1 + e^{-z}})(\frac{1}{1 + e^{-z}})(e^{-z}) \\ &= (\frac{1}{1 + e^{-z}})(\frac{e^{-z}}{1 + e^{-z}}) \\ &= g(z)(1 - g(z)) \end{align*}\)

---

 

1 ~ L의 layer를 가진 신경망에 일반화 한다면 다음과 같다.

\(\delta^{(L)} = a^{(L)} - y\)

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

이때, \({g}'(z^{(l)}) = a^{(l)} .* (1 - a^{(l)})\) 로 나타낼 수 있다.

 

즉, 

$$ \begin{align*} \delta^{(l)} &= ((\Theta^{(l)})^T\delta^{(l + 1)}) .* {g}'(z^{(l)}) \\ &= ((\Theta^{(l)})^T\delta^{(l + 1)}) .* a^{(l)} .* (1 - a^{(l)}) \end{align*}$$

로 나타낼 수 있다.

 

마지막으로 미분은 매우 복잡한데, 수학적으로 풀게되면 아래와 같은 결과를 얻을 수 있다.

$$ \frac{\partial}{\partial\Theta_{ij}^{(l)}}J(\Theta) = a_j^{(l)}\delta_i^{l + 1} \text{ (if }\lambda = 0 ) $$

정규화 항은 밑에서 추가할 것이다.

 

 

이제 한 개가 아닌 모든 Training Set에 대한 경우에 대해서 Backpropagation 알고리즘이 어떻게 동작하는지 살펴보자.

우리는 모든 l, i, j에 대해서 \(\Delta\) 항을 우선 0으로 세팅한다. 위에서 본 \(\delta\)와는 다른 것이고, 이것은 \(\frac{\partial}{\partial\Theta_{ij}^{(l)}}\)을 계산하는데 사용될 것이다.

그리고 모든 Training Set Example (i) (for 1 ~ m) : \((x^{(i)}, y^{(i)})\)을 가지고 아래와 같이 진행한다.

 

For \(i = 1\) to \(m\)

     1. Set \(a^{(1)} = x^{(i)}\)

     2. Perform forward propagation to compute \(a^{(l)}\) for \(l = 2, 3, ..., L\)

     3. Using \(y^{(i)}\), compute \(\delta^{(L)} = a^{(L)} - y^{(i)}\)

     4. Compute \(\delta^{(L-1)}, \delta^{(L-2)}, ..., \delta^{(2)}\), not compute \(\delta^{(1)}\)

     5. \(\Delta_{ij}^{(l)} := \Delta_{ij}^{(l)} + a_j^{(l)}\delta_i^{(l + 1)}\)

위 과정을 거쳐서 우리는 D를 다음과 같이 계산한다.

\(D_{ij}^{(l)} := \frac{1}{m}(\Delta_{ij}^{(l)} + \lambda\Theta_{ij}^{(l)})\)   \(\text{if } j \neq 0\)

\(D_{ij}^{(l)} := \frac{1}{m}\Delta_{ij}^{(l)}\)                   \(\text{if } j = 0\)

j = 0 인 경우에는 bias term에 해당하기 때문에 정규화항이 없다.

 

※ 5번 순서의 식에서 행렬화하여 표현하면 다음과 같이 표현할 수 있다.

\(\Delta^{(l)} := \Delta^{(l)} + \delta^{(l + 1)}(a^{(l)})^T\)

 

여기서 구한 \(D\)는 'accumulator'로 사용되고, 우리가 구한 값들을 더하고 궁극적으로는 편미분을 구하는데 사용된다.

그래서 우리는

$$\frac{\partial}{\partial\Theta_{ij}^{(l)}}J(\Theta) = D_{ij}^{(l)}$$

를 구할 수 있다.

 

 

[Backpropagation intuition]

BP 알고리즘을 살펴보기 전에 다시 한 번 FP를 살펴보자.

위와 같이 Input Layer 1개, Hidden Layer 2개, Ouput Layer로 이루어진 NN(Neural Network)가 있다고 할 때, 먼저 input layer의 unit에 \(x_1, x_2\)를 Set해주고 \(\theta\)요소들과의 연산으로 \(z_i^{(l)}\)을 구해준다.

예를 들어, \(z_1^{(3)}\) 을 구할 때, \(z_1^{(3)} = \theta_{10}^{(2)} \times (+1) + \theta_{11}^{(2)}a_1^{(2)} + \theta_{12}^{(2)}a_2^{(2)}\) 로 구할 수 있다.

 

 

BP는 FP와 반대 방향으로 계산된다. 

1개의 Input Unit \(x^{(i)}, y^{(i)}\)과 1개의 Output을 가지고 \(\lambda = 0\)인 문제에서 Cost는 아래와 같다.

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

간단히 \(cost(i) \approx (h_\theta(x^{(i)}) - y^{(i)})^2\)으로 생각한다.(강의에서 추가적인 언급은 없다)

BP의 역할은 편미분항을 위한 \(l\)번째 layer의 \(j\)번째 unit의 Error인 \(delta_j^{(l)}\)를 구하는 것이고, 다음이 성립하게 된다.

$$ \begin{matrix} \text{Formally, }\delta_j^{(l)} = \frac{\partial}{\partial z_j^{(l)}}cost(i) \text{  (for }j \leq 0 ) \text{ ,where} \\ cost(i) = y^{(i)}log(h_\Theta(x^{(i)}) + (1 - y^{(i)})log(1 - h_\Theta(x^{(i)})) \end{matrix}$$

 

BP의 역할은 결국 우리가 NN의 Weight를 어떻게 조정해야하는지에 대한 오차를 구하는 것이다. 

위 예제에서 \(\delta^{(2)}\)를 구한다고 하자.

\(\delta_1^{(4)} = y^{(i)} - a_1^{(4)}\) 을 구하고, \(\delta_2^{(2)} = \theta_{12}^{(2)}\delta_1^{(3)} + \theta_{22}^{(2)}\delta_2^{(3)}\) 그리고 \(\delta_2^{(3)} = \theta_{12}^{(3)}\delta_1^{(4)}\) 를 구해서 \(\delta^{(2)}\)를 구하면 된다.

\(\delta_0^{(l)}\) 항은 Bias Unit의 경우로 신경쓰지 않아도 된다.

 

다음 글에서 BP의 예제를 살펴보도록 하겠다.