앞선 글에서 다루었던 내용들은 linear classification task에 대해 classifier로 사용될 수 있는 support vector machine(SVM)과 softmax에 대한 형태, 그리고 각각의 classifier의 최적화 과정에서 loss function으로 사용되는 hinge loss와 cross-entropy loss에 대해서 살펴볼 수 있었다. 또한 weight $W$와 bias $b$를 통해 parameterize되는 score function $f$ 및 loss function을 최적화할 수 있는 여러 방법들 중 gradient descent에 대해서 언급했었고, 모든 sample에 대한 analytic gradient를 구하는 연산 과정이 computationally cost했기 때문에 stochastic gradient descent(SGD) algorithm과 보다 noisy한 학습을 줄이고 빠른 최적화를 위한 방법인 mini-batch gradient descent에 대해서도 확인할 수 있었다. 지금부터 다룰 내용은 이전에 살펴본 단일 신경망(perceptron)을 포함한 다층 신경망 구조(Multilayer perceptron)에서 어떤 방식으로 parameter를 효율적으로 최적화할 수 있는지에 대한 방법론으로, 이 글에서 인공지능의 침체기와 그 발전 방향에 대한 역사 총체에 대해서 다룰 것이다.
인공 신경망이라는 개념(Artificial neural network, ANN)은 1943년에 발표된 A logical calculus of the ideas immanent in nervous activity에서 처음 제안되었다. 해당 논문을 publish한 McCulloch와 Pitts는 위와 같은 인간의 신경 구조를 복잡한 스위치들이 연결된(일종의 논리 함수) 네트워크로 표현할 수 있다고 설명하였다. 하지만 해당 연구에서는 perceptron을 실질적으로 활용할 생각은 못했고, 이보다 응용에 가까운 알고리즘을 제시한 것이 바로 현재의 인공지능 시대를 처음으로 열고자 했던 perceptron 논문 이었고, 이는 1958년 Frank Rosenblatt에 의해 발표되었다. Resenblatt은 퍼셉트론이라는 선형 분류를 수행할 수 있는 feed forward neural network를 제안하였고, 이 구조는 우리가 흔히 알고 있는 input에 대해 weight를 곱하고, 여기에 activation function(활성화 함수)를 적용하여 그 값이 특정 threshold보다 크면 $1$, 작으면 $-1$을 출력하는 형태의 구조를 가지고 있었다.
현재 사용하고 있는 딥러닝도 형태만 살짝 다를 뿐 이러한 함수 구조를 여러 개의 node와 여러 개의 layer로 구성했다는 점에서 perceptron과의 근본적인 형태는 동일하다. Frank Rosenblatt의 perceptron은 현재의 딥러닝과 같이 당시에는 학계와 여러 언론으로부터 기대와 주목을 받았으며, 곧 세상을 인공지능이 대체할 수 있을 것이라는 보도가 나기 시작했다.
그러나 이런 기대와 열기는 1969년 MIT의 Marvin Minsky와 Seymour Papert가 저자로 참여한 Perceptrons라는 책을 통해 한계를 수학적으로 증명당하면서 급격히 줄어들게 되었다.
Minsky와 Papert는 단순한 선형 분류를 할 수 있는 perceptron의 경우 간단한 XOR 논리 연산을 추행할 수 없다는 것을 지적하였고, 가장 간단한 논리 문제에서부터 제안된 방법론이 수행될 수 없다는 점은 인간의 일상생활에서 접할 수 있는 대부분의 문제를 해결할 수 없음을 의미하였다. Minsky는 이에 추가적으로 perceptron을 여러 층으로 구성한 multilayer perceptron(MLP)이 해당 논리 문제를 해결할 수 있을 것이라 제안했지만, 그와 동시에 MLP의 parameter를 학습할 수 있는 방법론을 제시하지 못하였다.
인공 신경망에 대한 한계점을 찾아내자, 연구자들의 관심은 금방 사그라들었지만 이에 굴하지 않고 꾸준히 연구를 계속하는 사람들도 있었다. 1986년 Parallel Distributed Processing라는 책을 통해 hidden layer를 가진 multi-layer perceptron과 backpropagation 알고리즘을 제시하였다. 기존의 perceptron은 단일 신경망 layer를 가지고 있었기 때문에 linear classification의 한계를 넘어설 수 없었지만, multilayer perceptron(MLP)는 hidden layer라는 추가 layer를 제안함으로써, XOR과 같은 문제에서 선형 분류선을 추가할 수 있는 가능성을 보여주었다.
그러나 MLP의 경우 parameter의 수가 단일 perceptron에 비해 많아지면서 적절한 weight와 bias를 찾는 과정이 어려웠는데, 여기서 backpropation 알고리즘이 제안되면서 이 문제를 해결할 수 있었다. Backpropagation algorithm이란 input을 다층 신경망에 정방향(feed-forward) 방향으로 통과시킨 후 output값(에측값)을 토대로 원하는 기준(ground truth)와 비교함으로써, 해당 차이(error)를 역방향(backward)으로 돌려주면서 parameter를 update하게 된다.
사실 concept만 이런 식으로 정의하게 되면 이해가 쉽지 않기 때문에 다음과 같은 예시를 들어보도록 하겠다. 이전에 다루었던 단일 신경망(perceptron)을 활용한 선형 분류기의 경우 score function $f$을 구성하는 요소가 weight 및 bias 였고, 이를 단순한 trick을 사용하여 단일 layer의 parameter를 weight로만 정의할 수 있었다. 이를 식으로 표현하게 되면 score function $f$와 loss function $\rho$에 대하여,
[ \begin{aligned} \hat{y} =& f(W;~X) = X \cdot W \newline \delta =& \rho(\hat{y},~y) \end{aligned}
]
score function $f$를 통해 예측한 prediction $\hat{y}$과 ground truth $y$를 loss metric $\rho$를 통해 비교한 error 값인 $\delta$를 정의할 수 있다. Error가 의미하는 바는 곧 output이 이동해야할 방향(direction)와 같다. 다르게 말하자면 input $W,~x$에 대한 prediction $\hat{y}$의 변화량을 제시했기 때문에, 기준점에 대한 input의 변화량은 미분을 통해 구할 수 있다. 길게 돌고 돌아서 설명하긴 했지만 이전에 설명했던 gradient descent 방식을 풀어서 설명한 것이다. Parameter인 $W$의 변화량에 대한 $\delta$의 변화는 다음과 같다.
[ \frac{\partial \delta}{\partial W}
]
여기서 만약 $\delta$ 값을 구할 수 있다면, 이에 따라 $W$의 변화량도 계산할 수 있다. 물론 여기서 구한 변화량은 hyperplane에 대한(tangential plane) direction이 되기 때문에 실제 loss function의 global minima를 찾을 수는 없다. 이 역시 step size를 기반으로 조금씩 내려가는 형태의 gradient descent 알고리즘을 적용해야한다.
[ \delta_W = \delta \times \frac{\partial W}{\partial \delta} = \delta \times \frac{\partial \hat{y}}{\partial \delta} \times \frac{\partial W}{\partial \hat{y}} ]
방금은 layer가 하나인 경우에 대해서만 설명하였고, 만약 이러한 layer가 여러 층 있다고 생각해보자. 식에서 $\sigma$는 activation function으로 생각해주면 된다.
[ \begin{aligned} \hat{y} = f(W_1,~W_2,~\cdots,~W_n;~X) =& \sigma( \cdots \sigma(\sigma(X \cdot W_1) \cdot W_2) \cdots W_n) \newline \delta =& \rho(\hat{y},~y) \end{aligned}
]
수식을 단순하게 하기 위해 $y_k$는 $k$번째 레이어 이후의 결과값이라고 생각해보자. 따라서 위의 수식에서 $\hat{y} = y_n$이다. 앞서 단일 perceptron의 경우와 동일하게 이번에도 output의 변화량에 대한 input의 변화량을 나타낼 수 있다.
[ \delta_{W_n} = \delta \times \frac{\partial \sigma}{\partial \delta} \times \frac{\partial W_n}{\partial \sigma} = \delta \times \frac{\partial y_n}{\partial \delta} \times \frac{\partial \sigma}{\partial y_n} \times \frac{\partial W_n}{\partial \sigma} ]
다만 이번에는 output $\hat{y}$가 activation function $\sigma$에 대한 추가 합성 함수로 구성되기 때문에 위와 같은 chain rule을 따르게 된다. 마찬가지로,
[ \delta_{W_{n-1}} = \delta \times \frac{\partial \sigma}{\partial \delta} \times \frac{\partial y_{n-1}}{\partial \sigma} \times \frac{\partial W_{n-1}}{\partial y_{n-1}} ]
위와 같이 forward 과정에서 이미 연산된 결과 $y_k$에 대해 local derivatives를 계속해서 계산된 미분값에 곱해가게 되고, 이를 backpropagation이라고 한다. 위는 multilayer perceptron에 대한 예시였고, 다음과 같은 간단한 논리 회로에 대해 예시를 보게 되면
초록색으로 표시된 값들이 실제 input($x,~y,~z$ 그리고 논리 연산에 의한 값)이고, 빨간색으로 표시된 값들이 미분값에 해당된다. 위와 같이 input에 대해 어떠한 결과가 도출되는 복잡한 신경망 회로를 구성한 것이 multilayer perceptron이다. 이를 학습시키기 위해 backpropagation을 진행하는 과정을 직관적인 그림으로 표현한 것이 위의 그림이다. 첫번째 빨간색 미분값은 앞서 보았던 metric에 의한 오차 그대로를 미분한 것과 같다. 논리 회로를 하나의 함수 $f$라고 생각한다면 이를 $f$로 미분한 결과는 그대로 $1$이 되기 때문이다. 그 다음으로 볼 수 있는 두번째 빨간색 미분값($q$라고 적혀있는 부분에 해당)은 $-4$이다. 왜냐하면 $f = qz$를 $q$로 편미분한 것은 $z$값이기 때문이다. 세번째 빨간색 미분값($x$라고 적혀있는 부분에 해당)은 $-4$이다. 왜냐하면 $f = qz = (x+y)z$를 $x$로 편미분한 것은 $z$값이기 때문이다(by chain rule). 네번째 빨간색 미분값($y$라고 적혀있는 부분에 해당)은 $-4$이다. 왜냐하면 $f = (x+y)z$를 $y$로 편미분한 것은 $z$값이기 때문이다(by chain rule). 그리고 마지막 빨간색 미분값($z$라고 적혀있는 부분에 해당)은 $3$이다. 왜냐하면 $f$를 $z$로 편미분한 것은 $x+y$값이기 때문이다. 이 논리 회로의 연산 과정은 간단하고, 크게 어렵지 않지만 해당 예시에서 얻어갈 수 있는 insight는 다음과 같다.
Backpropagation은 local process(지역적 연산 결과)이다. 회로 다이어그램에서의 각 gate는 input을 받아 두 가지 계산 결과를 가진다. 첫번째는 말 그대로 gate의 논리에 따른 연산 결과(위의 그림 예시에서 볼 수 있었던 초록색 값), 그리고 두번째는 input에 대한 output의 local gradient(위의 그림 예시에서 볼 수 있었던 빨간색 값)를 계산한 값이다. 실제로 gate가 속해있는 전체 회로가 어떤 구조로 구성되어있어도 이와는 상관없이 각 gate에서 수행되는 논리 계산과 gradient 계산은 완전히 독립적으로 생각할 수 있다. 그렇기에 forward pass가 한번 끝나게 되면, backpropagation이 진행되는 동안에 전체 회로의 output value를 기준으로 신경망을 구성하는 모든 parameter에 대해서 gradient를 계산할 수 있는 것이다. 이를 실질적으로 수행할 수 있게 만드는 수학적 메커니즘인 chain rule로 하여금 gate의 모든 input에 대해 gradient를 곱하는 형태로 계산이 진행되어야하는 것이다. 여기서 gradient의 곱은 반대로 가는 경로(backward process)에 놓이는 모든 output에 대해서 생각해주면 된다. 즉, chain rule에 따른 multiplication은 곧 복잡한 신경망 회로 내에서 서로 무관하게 놓인 perceptron들을 유기적으로 학습할 수 있는 방법론이 된 것이다. 앞의 예시를 다시 가져와서 생각해보면,
덧셈 연산을 수행하는 gate는 input으로 $-2$, $5$를 받고 output인 $3$을 내보냈다. Gate는 단순히 input에 대해서 덧셈을 수행하기 때문에, 모든 input에 대한 gradient는 $+1$이다. 덧셈 연산을 수행하는 gate를 포함한 전체 논리회로는 최종 결과인 $-12$를 출력한다. Backward pass(backpropagation) 과정에서 chain rule이 적용되고, backpropagation 연산 결과, 덧셈 gate는 해당 output에 대한 gradient로 $-4$를 가지게 된다. 여기서 만약 회로가 만약 'output으로 더 큰 값을 뽑아내길 원한다'고 생각해보자. 회로에서 덧셈 gate의 gradient가 마이너스값($-4$)이었으니, 실제로 덧셈 gate의 output으로는 더 작은 값을 원하겠거니 생각할 수 있다. 빨간색으로 계산된 gradient 결과는 결국 output에 대한 각 gate output의 변화량 및 방향을 표현한 것이기 때문이다. Backpropation을 진행하는 과정에서, 덧셈 gate는 자기가 받는 모든 input(그림에서는 $x$, $y$)에 대한 local gradient에 덧셈 gate의 output $q$에 대한 gradient를 모두 곱하게 된다. 따라서, input $x$에 대해서나 $y$에 대해서 모두 $1 \times (-4) = -4$가 되는 것이다. 이를 토대로 우리가 input과 회로 전체에 대해 이해할 수 있는 바는 $x$, $y$가 모두 감소하게 되면 덧셈 gate의 output도 감소하게 되고, gate의 output은 증가하게 된다는 것이다. 이를 요약하자면 회로의 output으로 하여금 gate에 적용되는 gradient에 해당 gate의 input 변수들의 local gradient를 곱하게 되면 각 input들의 적용되는 gradient를 계산할 수 있고, 이를 통해 각 input이 어떤 방향으로 얼만큼 변화해야 원하는 output을 얻을 수 있는지에 대한 정보를 알아낼 수 있다. 회로 안의 모든 gate는 backpropagation이라는 과정을 통해 서로 소통할 수 있게 되고, 소통 수단은 chain rule을 기반으로 계산된 값이 될 것이다.
[ f(w,~x) = \frac{1}{1+e^{-(w_0x_0 + w_1x_1 + w_2)}}
]
위의 식은 입력 차원이 $2$인 단일 신경망에 대해서 sigmoid activation function을 적용하는 간단한 회로이다. 위의 식에서 사용되는 각 논리 회로에 대한 미분은 다음과 같다.
[ \begin{aligned} f(x) =& \frac{1}{x} \rightarrow \frac{df}{dx} = -\frac{1}{x^2} \newline f(x) =& x + c \rightarrow \frac{df}{dx} = 1 \newline f(x) =& e^x \rightarrow \frac{df}{dx} = e^x \newline f(x) =& ax \rightarrow \frac{df}{dx} = a \end{aligned}
]
식을 기반으로 회로를 구성하면 다음과 같은 그림이 된다.
그림을 보면 각 연산 순서에 맞게 value(초록색)와 gradient(빨간색)를 계산해놓은 것을 알 수 있다. 앞서 예제에서 했던 것과 같이 backpropagation을 진행하면 다음과 같다. 가장 output인 $1.00$을 기준으로 시작해보자. $\frac{1}{x}$ gate에 대한 local gradient 식은 $\frac{df}{dx} = -\frac{1}{x^2}$가 된다. 식에서 $x$에 유일한 input인 $1.37$을 대입하고, 역방향을 기준으로 gate의 gradient를 모두 곱하면 $1 \times (-1/(1.37)^2) = -0.53$이다. 그 다음에 있는 1을 더하는 operation은 gradient에 영향을 주지 않기 때문에(input에 상관없이 local gradient가 1이기 때문에) $-0.53$이 그대로 전달된다.
그 다음으로 exponential operation에 대한 local gradient($\frac{df}{dx} = e^x$)는 input에 대한 output과 local gradient가 서로 같은 값을 가지기 때문에, 앞서 연산된 gradient에 output을 곱하게 되면 $-0.53 \times 0.37 = -0.20$이 된다. $-1$을 곱하는 연산은 gradient 부호를 바꾸는 연산이 되므로 전달되는 값은 $(-0.20) \times (-1) = 0.20$이 된다.
이후로는 input이 두 갈래로 나뉘게 되는데, 우선 $w2$와 이어진 부분을 보게 되면 덧셈 연산으로 구성되기 때문에 gradient가 변수에 대해서 $1$이 고정값으로 쓰인다. 따라서 $0.20$이 그대로 유지된다. 위쪽으로도 또다른 덧셈 연산이 이어지고, 여기서도 동일하게 $0.20$이 유지되는 것을 알 수 있다. 다시 위쪽 덧셈 연산 gate를 기준으로 두 갈래로 나뉘게 되는데, 여기서도 마찬가지로 덧셈 연산이기 때문에 $0.20$의 gradient가 유지된다.
남은 부분은 곱셈 연산 gate인데, gate로 전달된 gradient가 $0.20$이기 때문에 여기서 서로 다른 input을 곱한 것이 해당 input에 대한 gradient가 된다. 예를 들어 $f(x,~y) = xy$인 gate가 있다면, 각 input에 대한 local gradient는 $\frac{\partial f}{\partial x} = y,~\frac{\partial f}{\partial y} = x$가 되는 것이다. 이를 토대로 계산하게 되면 $w0$에 대한 gradient는 $0.20 \times x0 = -0.20$, $x0$에 대한 gradient는 $0.20 \times w0 \simeq 0.39$(여기서 연산이 살짝 안 맞는데, 이 부분은 소숫점 아래 두번째 자리까지 반올림하면서 생긴 오차인 듯)이 된다. $w1,~x1$에 대한 gradient도 같은 방법을 통해 계산하게 되면 각각 $-0.39,~-0.59$가 되는 것을 쉽게 알 수 있다.
위에서 사용된 회로는 sigmoid function을 여러 기본 논리 회로를 통해 표현한 형태가 된다. 그러나 굳이 이렇게 세세히 분리할 필요 없이 sigmoid function의 analytic한 도함수를 구할 수 있다.
[ \begin{aligned} \sigma (x) =& \frac{1}{1+e^{-x}} \newline \frac{d \sigma(x)}{dx} =& \frac{e^{-x}}{(1+e^{-x})^2} \end{aligned}
]
Sigmoid function의 도함수는 다음과 같이 표현할 수 있다.
[ \frac{d \sigma(x)}{dx} = \left( \frac{1+e^{-x}-1}{1+e^{-x}} \right)\left( \frac{1}{1+e^{-x}} \right) = (1-\sigma(x))\sigma(x)
]
그렇다면 위에서 계산된 결과를 토대로 보게 되면, $w0x0 + w1x1 + w2$가 곧 sigmoid function의 input인 $x$가 되기 때문에 $\sigma(x) = 0.73$, $\sigma (x)(1-\sigma (x)) = 0.73 \times (1-0.73) = 0.1971$임을 바로 구할 수 있다.
기존 linear classification만 가능했던 퍼셉트론의 한계를 극복하기 위해 다층 신경망 구조를 역사와 함께 간단하게 소개했고, 그러한 다층 신경망을 학습시키기 위한 방법으로 제시된 backpropagation이란 개념을 알아볼 수 있었다. Backpropagation은 각 레이어마다 local gradient 계산을 통해 모든 신경망 구조의 요소들을 유기적으로 엮어주는 역할을 했으며, perceptron이 해결하지 못한 실생활의 task에 적용될 수 있는 딥러닝의 발전이 시작된 지점이었다.
[ f(x,~y) = \frac{x+\sigma (y)}{\sigma (x) + (x+y)^2}
]
x = 3 # example values
y = -4
# forward pass
sigy = 1.0 / (1 + math.exp(-y)) # sigmoid in numerator #(1)
num = x + sigy # numerator #(2)
sigx = 1.0 / (1 + math.exp(-x)) # sigmoid in denominator #(3)
xpy = x + y #(4)
xpysqr = xpy**2 #(5)
den = sigx + xpysqr # denominator #(6)
invden = 1.0 / den #(7)
f = num * invden # done! #(8)
# backprop f = num * invden
dnum = invden # gradient on numerator #(8)
dinvden = num #(8)
# backprop invden = 1.0 / den
dden = (-1.0 / (den**2)) * dinvden #(7)
# backprop den = sigx + xpysqr
dsigx = (1) * dden #(6)
dxpysqr = (1) * dden #(6)
# backprop xpysqr = xpy**2
dxpy = (2 * xpy) * dxpysqr #(5)
# backprop xpy = x + y
dx = (1) * dxpy #(4)
dy = (1) * dxpy #(4)
# backprop sigx = 1.0 / (1 + math.exp(-x))
dx += ((1 - sigx) * sigx) * dsigx #(3)
# backprop num = x + sigy
dx += (1) * dnum #(2)
dsigy = (1) * dnum #(2)
# backprop sigy = 1.0 / (1 + math.exp(-y))
dy += ((1 - sigy) * sigy) * dsigy #(1)
코드에 맞게끔 다이어그램에서의 value와 gradient를 매칭시키면 다음과 같다.
빨간색으로 표시된 부분이 forward process에서 계산된 value, 초록색으로 표시된 부분이 backward 연산 시 계산된 gradient를 변수명에 맞게 위치시킨 것이다. 가장 먼저, $f(x,~y)$를 기준으로 곱셈 연산 gate가 있기 때문에 앞선 예제에서와 같이 input을 서로 교차해서 곱해주면된다. Output에 대한 gradient는 $1$이기 때문에, $1$에 각각의 input을 곱해주면 된다. 따라서 코드는 다음과 같다.
# backprop f = num * invden
dnum = invden # gradient on numerator #(8)
dinvden = num #(8)
다음으로는 $1/x$ 연산에 대한 gradient를 곱해주기 위해 input인 den에 대한 $-1/x^2$을 곱해준다. 코드는 다음과 같다.
# backprop invden = 1.0 / den
dden = (-1.0 / (den**2)) * dinvden #(7)
그리고 xpysqr과 sigx가 더해지게 되므로, dsigx와 dxpysqr은 각각 dden의 gradient가 그대로 유지된다.
# backprop den = sigx + xpysqr
dsigx = (1) * dden #(6)
dxpysqr = (1) * dden #(6)
제곱에 대한 gradient는 쉽게 구할 수 있으므로 dxpy는 넘어가도록 하겠다.
# backprop xpysqr = xpy**2
dxpy = (2 * xpy) * dxpysqr #(5)
마찬가지로 dxpy의 gradient는 덧셈 게이트의 input인 x와 y에 대해 그대로 유지된다. 따라서 dx와 dy는 다음과 같다.
# backprop xpy = x + y
dx = (1) * dxpy #(4)
dy = (1) * dxpy #(4)
앞선 예제에서 $\sigma$ 함수의 gradient를 표현하는 방법에 대해서 알아보았다. 해당 공식을 그대로 사용하게 되면 output인 sigx에 대해서
# backprop sigx = 1.0 / (1 + math.exp(-x))
dx += ((1 - sigx) * sigx) * dsigx #(3)
위와 같으며, 기존에 이미 연산된 dx가 있기 때문에 여기에 추가로 더해주게 된다. dnum = x + sigy에 대해 덧셈 gate는 gradient가 유지되므로 다음과 같이 계산할 수 있다.
# backprop num = x + sigy
dx += (1) * dnum #(2)
dsigy = (1) * dnum #(2)
여기에 마지막으로 $\sigma$ 함수의 gradient를 계산해주면 마무리된다.
# backprop sigy = 1.0 / (1 + math.exp(-y))
dy += ((1 - sigy) * sigy) * dsigy #(1)