Lecture 4: Backpropagation and Neural Networks

Stanford에서 강의하는 CS231n에 대해서 공부하고 정리한 글입니다.

Slide: cs231n_2017_lecture4.pdf

What we want..

우리는 지난시간 raw data로부터 class score를 구하는 scores function, function이 얼마나 구린지를 정량화할 수 있는 SVM loss, 분류기를 일반화 할 수 있는 regularization 에 대해 배웠다.

그렇다면, 최적의 loss를 찾기 위해 파라미터 $w$를 찾는 방법을 알아보자.

Optimization

최적의 $w$에 관한 gradient를 찾는 것은 Optimization을 사용해서 구할 수 있다.

이는 gradient가 음수인 방향(경사가 하강하는 방향)을 반복적으로 구해 최적의(가장 낮은) loss에 도달하는 방법이며, 오른쪽 이미지와 같은 궤도를 나타낸다.

가장 먼저 생각해 볼 수 있는 단순한 방법은 임의 탐색(Random search) 이다. 임의로 샘플링한 $w$들을 모아놓고 Loss를 계산해서 어떤 $w$가 좋은지 살펴보는 것이다. 당연히 이 방법은 좋지 않은 알고리즘이지만 한번쯤 생각해 볼 법한 방법이다.

다른 한 가지는 유한 차분 근사(finite difference approximation)을 이용해 계산할 수 있다.

우리는 Loss 함수에서 최솟값을 찾아야 한다. 이는 Loss 함수의 기울기를 통해 구할 수 있다. 아래 간단한 예시를 통해 알아보자.

왼쪽의 파라미터 $W$가 있다. 이 $W$를 사용하면 Loss가 1.25347이 나온다. 앞서 배운 유한 차분법을 통해 $dw$를 계산해본다.

$W$의 첫번째 요소(0.34)에 아주 작은 값 h를 더한 뒤 Loss는 1.25322 이다.

이는 $W$의 첫번째 요소를 조금 변화(양의 방향으로)시킬 때 Loss가 1.25347에서 1.25322로 감소한다는 뜻이다.

이를 통해 $W$의 첫번째 요소의 $dW$를 구할 수 있다.

이 예제에선 이 방법으로 10개의 $dW$만 구하면 되지만, 실제로 엄청 크고 깊은 신경망 모델이라면 파라미터가 기하 급수적으로 늘어나며, 모든 파라미터의 $dW$를 계산하기엔 많은 Cost가 소모된다.

이는 Numerical gradient 라고 하며, 유한차분법을 사용한 gradient 계산법을 일컫는다.

반면, 도함수를 직접 구해 Optimization 하는 방법은 Analytic gradient 라고 부른다. 이 방법은 빠르며 정확하지만 에러가 발생할 수 있다.

따라서 실제로는 Analytic gradient 방식으로 gradient를 계산하며, 오차 검증 과정에서 Numerical gradient 방식을 사용한다.

Analytic gradient

Backpropagation

Analytic gradient 방법인 Chain Rule 을 설명하기 위해서 Computational graphs를 사용한다.

이 예제는 input이 $x$, $W$인 선형 classifier를 Computational graph로 나타낸 것이다.

다른 복잡한 모델(CNN, Neural Turing Machine) 등에도 적용될 수 있다.

그럼, 간단한 예시를 통해 Backpropagation을 살펴본다.

이 경우 $f = (x+y)*z$ 와 같다.

우리는 function f의 출력에 대한 어떤 변수의 gradient를 찾기를 원한다.

(쉽게 말해 x, y, z가 각각 출력에 미치는 독립적인 영향을 찾는다)

1) $x+y$ 지점을 $q$라 지정하며 값을 적어준다.

2) $(x+y)*z$ 지점(출력)을 $f$라 지정하며 값을 적어준다.

3) (출력 지점에서부터) 현재 노드가 출력에 미치는 영향, 즉 출력에 대한 gradient를 구한다. $\frac{\partial f}{\partial f} = 1$

4) 출력 노드에서부터 이전 노드로 이동하며 gradient를 구한다.

$f$ 지점에서의 gradient를 구했다면, 이전 노드로 넘어가 $z$와 $q$의 gradient를 구해준다.

$z$의 gradient는 $\frac{\partial f}{\partial z}$ 이며, $f$를 $z$로 편미분하여 구할 수 있다. 편미분 값은 $q$ 이며, 입력값 $x = -2, y = 5$ 를 통해 3을 얻을 수 있다.

$q$ 의 gradient는 $\frac{\partial f}{\partial q}$ 이며, -4 임을 알 수 있다.

$y$의 gradient는 $\frac{\partial f}{\partial y}$ 이며 Chain rule을 이용해 $\frac{\partial f}{\partial y} = \frac{\partial f}{\partial q} \frac{\partial q}{\partial y}$ 를 이용해 구할 수 있다. 값은 $z \times 1 = -4$ 이다.

$y$의 gradient를 계산한 방식대로 $x$의 gradient를 계산할 수 있다.

이를 일반화 하여, 앞의 노드에서 넘어오는 gradient는 Upstream gradient, 뒤의 노드로 넘어가는 gradient는 local gradient라고 칭한다.

그림에서는 $\frac{\partial L}{\partial z}$가 Upstream gradient, $\frac{\partial L}{\partial x}, \frac{\partial L}{\partial y}$가 local gradient 이다.

조금 더 복잡한 수식에서의 gradient를 계산해 본다.

이것은 $y = w_0x_0 + w_1x_1 + w_2$인 선형 함수에 Activation function인 sigmoid를 사용한 예시이다.

출력 지점에서부터 Backpropagation을 시작한다.

최종 변수에 대한 출력의 gradient는 1이다. ($\frac{\partial f}{\partial f} = 1$)

$\frac{1}{x}$ 노드를 q라고 칭했을 때, q 노드의 local gradient는 $-\frac{1}{x^2}$ 이며, upstream gradient는 $1$ 이다. 따라서 최종 gradient는 $-\frac{1}{x^2} \times 1 = \frac{-1}{1.37^2} \times 1 = -0.53$ 이다.

$x+1$ 의 local gradient는 $1$ 이며, upstream gradient는 $-0.53$ 이다. 따라서 최종 gradient는 $1 \times (-0.53) = -0.53$ 이다.

이렇게 계속해서 gradient를 구해나가다보면 그림과 같이 두개의 브랜치로 나눠지는 구간이 생긴다.

위 부분은 $w_0x_0 + w_1x_1$, 아랫 부분은 $w_2$ 이다. 여기서 upstream gradient는 0.20, local gradient는 각각 1이므로 최종 gradient는 0.2 로 동일하다.

이렇게 모든 gradient를 구해준다.

모든 gradient를 구했으므로, 확인해보자.

아래 Computational graph에서 파란색 박스쳐진 부분은 sigmoid gate이다.

sigmoid function은 $\frac{1}{1+\exp^{-x}}$ 이며, 그 도함수는 $(1 - \sigma(x))\sigma(x)$ 이다.

$\sigma(0.73) = (0.73) \times (1-0.73) = 0.2$

이는 우리가 backpropagation으로 구한 gradient인 0.2와 같다.

우리는 backpropagation을 진행하며 여러(add, max, mul) 등의 노드를 보았다. 각각의 노드가 갖는 의미가 무엇일까?

add gate는 upstream gradient를 연결된 브랜치에 정확히 같은 값으로 전달해준다.

max gate는 연결된 브랜치 중 더 큰 입력값을 그대로 통과시켜 주며, upstream gradient도 통과시켜 준다. (단, 입력 값이 더 작은 브랜치 쪽의 gradient는 0이 된다.)

mul gate는 upstream gradient를 받아 다른 브랜치로 값을 scaling 해준다.

만약, 입력 값이 scalar 가 아닌, vector인 경우엔 어떻게 될까?

모든 흐름은 똑같다. 차이점이라면, gradient가 Jacobian 행렬이라는 점이다.

입력이 4096 차원의 벡터이고, 출력이 4096 차원의 벡터라면, Jacobian matrix의 사이즈는 4096 $\times$ 4096 이 된다.

output의 각 element를 input의 각 element로 편미분 한 값으로 구성되기 때문이다.

또한, Jacobian matrix는 대각 행렬이 된다. ($f(x) = max(0,x)$ 이며, 입력의 $i$ 번째 요소는 출력의 $i$ 번째 요소에만 영향을 미치기 때문)

이제 Scalar가 아닌, 벡터를 입력으로 사용하는 예제에서 gradient를 구해보자.

출력값을 구하는 forward 부분과, 마지막 노드의 upstream gradient는 1임을 쉽게 구할 수 있다.

$L2 = q_1^2 + ... + q_n^2$ 이며, $\frac{\partial f}{\partial L2} = 2q$ 임을 알 수 있다.

따라서, $2 \pmatrix{0.22 \\ 0.26} 1.00 = \pmatrix{0.44 \\ 0.52}$ 임을 알 수 있다.

$W$의 gradient는 그림으로 다시 계산해보았다.

$\frac{\partial f}{\partial w}$는 vectorized term으로 나타내면 $2q\bullet x^T$로 표현할 수 있다.

$\left [ \begin{matrix}
0.088 & 0.176 \\
0.104 & 0.208 \\
\end{matrix} \right ]$ 이 되려면 $\left [ \begin{matrix}
0.44 \\ 0.52
\end{matrix} \right ]$와 $\left [ \begin{matrix}
0.2 & 0.4 \\
\end{matrix} \right ]$의 곱을 통해 얻을 수 있기 때문이다.

$\frac{\partial f}{\partial x}$를 구하는 방법은 위와 같다.