Deep dive into optimization: Gradient descent - Updated

"모바일 앱 환경에서는 latex이 깨져 나타나므로, 가급적 웹 환경에서 봐주시기 바랍니다.:)"

 

오늘부터 이제 본격적인 딥러닝 최적화 (Optimization)에 대한 이야기가 시작된다.

 

그 첫 번째 주제는 현재 딥러닝 학습 기법의 가장 기본이 되는 경사하강법 (Gradient descent)이다.

우선 경사하강법이 무엇인지 이야기하기 전에 이것이 왜 현재 딥러닝의 학습 기법의 base가 되었는지부터 이야기해보자.

 

지난 글에서 'convex'에 대해 설명하면서 convex function의 중요한 성질은 'local minima가 곧 global minima이다.'라고 하였다.

하지만, 딥러닝에서 학습이란 곧 손실함수에 대한 최적화를 의미하고, 이때 최적화가 이루어지는 손실 함수 (loss function)는 일반적으로 convexity를 보장할 수 없다.

또한, Neural network는 파라미터의 개수가 매우 많고 이는 곧 loss function의 파라미터 개수도 매우 많음을 의미한다. 즉 함수 자체가 고차원 (High dimension) 에 있는 함수이고, 우리는 함수 전체의 모양을 한 번에 알 수 없다.
이 말은 손실 함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}$이 정의되어져 있을 때, $n$의 크기가 매우 크다는 의미이다.

함수 전체의 모양을 알 수 없고, convex를 보장할 수 없는 경우가 일반적이므로, 학습 알고리즘이 그 함수의 global minima (=loss 값의 전역 최소) 를 찾는 것은 현실적으로 불가능에 가깝다.

이를 조금 더 유식한 표현으로 NP-Hard 문제라고 표현한다. 

 

기본적으로 P문제는 어떤 문제를 다항 시간 (Polynomial time) 내에 풀 수 있음을 의미하고, NP문제는 다항 시간 내에 풀 수 없고, 지수 시간 (Exponential time)에 풀 수 있음을 의미하는데 이는 쉽게 표현하면 현실적으로 정확한 답을 구하기 매우 어려운, 불가능한 문제를 표현한다.

딥러닝에서의 최적화 문제는 대표적인 NP-hard 문제에 속하며 우리는 neural network의 loss function의 최솟값, 또는 최소화하는 지점 (global minima) 을 정확하게 찾는 것이 현실적으로 불가능에 가깝다.

그래서 우리는 손실 함수를 '근사' (approximate) 하여 approximated function 을 최소화하는 방향으로 문제를 바꿔서 푸는데 이 때 나온 방법이 "경사하강법" (Gradient descent)이다.

 

미분 가능한 함수 $f(w)$를 최소화하는 $w$를 찾는다고 생각해보자. $f(w)$가 neural network의 손실함수이고 $w$가 그 파라미터라면, 이게 바로 딥러닝의 학습이다.

우리는 현실적으로 저 문제의 정확한 해를 구할 수 없기 때문에 이를 first-order taylor approximation을 사용한다.

$w_{t+1}$은 $t + 1$번째 iteration (step)에서 파라미터 값이다. 

딥러닝에서 학습은 iterative algorithms 으로 진행되기 때문에 파라미터를 여러 번의 반복 (=iteration) 을 거쳐 업데이트를 진행하는데, 이러한 알고리즘을 iterative algorithm이라 하고 gradient descent도 대표적인 iterative algorithm이다.

우선은 손실 함수를 우리는 Taylor approximation을 사용하여 근사된 함수를 최적화하는 것이기 때문에 당연히 오차가 발생할 수 밖에 없고, 근사로 인해 발생한 오차를 최대한 줄이기 위해 iterative algorithm을 사용한다고 생각하자.

 

자 그런데 여기서 $\frac{1}{2 \eta} \lVert w- w_t \rVert^2$가 무엇인지 궁금해질 것이다.

이 Term이 없다면, $f(w_t) + \langle \nabla f(w_t), w - w_t \rangle$까지는 $f(w)$의 $w_t$에서의 접선 (tangent plane)이다.

하지만 접선 (=직선)의 최솟값은 $-\infty$이다. 

그리고 일차 함수로 근사하면 $w$가 $w_t$근방에서는 오차 (=원래 함수와 근사된 함수의 차이)가 작을지라도, $w$가 $w_t$에서 멀어지면 멀어질수록 그 오차의 정도는 매우 커진다.

그래서 $w$가 $w_t$에서 멀리 떨어지지 않도록 그것을 규제해주는 항 $\lVert w - w_t \rVert^2$를 더해준다.

만약 $\eta$가 커지면 이 규제의 정도가 상대적으로 약해질 것이고 (=즉 $w$가 $w_t$에서 상대적으로 멀리 떨어지는 것을 허용), 만약 $\eta$가 작아지면 이 규제의 정도가 상대적으로 커질 것이다. (=즉 $w$가 $w_t$에서 멀리 떨어지는 것을 허용 X)

 

어떤 함수를 최소화하는 값을 찾는 가장 기본적인 방법은 그 함수를 미분해서 기울기가 0이 되는 지점을 찾는 것이므로 위 함수를 미분한다. 위 함수는 $w$에 대해 2차 함수 꼴이기 때문에 convex하고 local minima = global minima이다.

그것을 정리하면 다음과 같이 된다.

 

이것이 바로 gradient descent 알고리즘이다.

현재 파라미터 $w_t$에서 Negative gradient 방향으로 이동하는 것이 바로 경사하강법이다.

이때 얼마만큼의 크기로 이동할 것이냐에 영향을 미치는 것이 $\eta$이다.

이는 앞서 언급한 직관적 해석과 상당히 잘 이어진다. 만약 $\eta$값이 크면 현재 파라미터 $w_t$에서 이동하는 것을 허용하는 것이고, 이는 곧 위에 first-order approximation 식에서 $w$가 $w_t$에서 멀리 떨어지는 것을 허용하는 것과 동치이다.

이때 $\eta$를 우리는 딥러닝에서 step-size (=learning rate)라고 부른다. 학습률이다.

 

경사하강법은 상당히 좋은 성능을 보여준다. 즉, 실제 목적함수에 대한 최소화를 상당히 잘 수행해준다.

또한, 함수 $f$와 step size $\eta$에 대한 적절한 가정 하에서 수렴성이 보장되어져 있고, 수렴 속도도 알려져 있다.

하지만, 현재 딥러닝에서 이 경사하강법을 그대로 사용하기에는 어려움이 있다.

바로 Training dataset의 크기가 매우 크다는 점이다.

 

예전 최적화 글에서 딥러닝에서 손실함수는 결국 모델의 아웃풋과 정답 (label)사이의 정량적으로 측정한다고 하였다.

그렇다면 모델의 아웃풋은 인풋으로 데이터를 받아서 나오는 것이기 때문에 데이터의 개수가 많으면 많을수록 연산량이 당연히 크게 증가할 수밖에 없다. 

현재 딥러닝은 Neural network의 사이즈가 상당히 커지고 있고 (e.g : Overparameterized model) 이를 학습시키기 위한 데이터셋의 크기도 상당히 커지고 있기 때문에  모든 데이터셋을 활용해서 한 번에 손실함수 값을 계산하고, 이의 기울기를 구해서 (이를 backpropagation이라 하는데 이는 Deep dive into deep learning 시리즈에서 다루겠다.) 파라미터 업데이트를 진행한다면 연산량이 상당히 증가할 것이고 학습하는데 걸리는 시간도 상당히 길어질 것이다.

(Gradient descent가 iterative algorithm임을 기억하자)

그렇다면 여기서 또 한 번에 근사를 사용하는데 모든 데이터셋을 사용해서 loss value (=참값)를 계산하는 것이 아니라, 일부 데이터셋을 사용해서 loss value를 계산 (=근삿값)하고 그것이 원래의 참값에 대해 좋은 추정치 (good estimator)라는 것을 보이는 것이다. 일부 데이터만을 사용하여 계산한 손실 함수의 기울기 (이를 $g(w_t)$라고 하자)는 전체 데이터를 사용하여 계산한 손실 함수의 기울기 ($\nabla f(w_t)$)의 불편 추정량 (Unbiased estimator, $\mathbb{E} g(w_t) = \nabla f(w_t)$)이다.

이를 위해서는 기본적인 수리통계학 개념이 필요한데 통계학적 개념에 대한 설명은 스킵하도록 하겠다.

 

이렇게 일부 데이터셋을 사용하는 경사하강법에는 크게 두 가지 종류가 있다.

Stochastic gradient descent와 Mini-batch gradient descent이다. 

이는 손실 함숫값을 계산할 때 사용하는 데이터의 개수에 따라 구분되는데 데이터 example 한 개 (sample 한 개)만을 사용하여 계산하는 방법을 Stochastic gradient descent (SGD), 여러 개를 사용하되 전체 데이터셋을 다 사용하지 않는 경우, 즉 부분집합만을 사용하여 계산하는 방법을 Mini-batch gradient descent라고 부른다.

 

앞서 손실함수를 $f(w)$라고 하자고 하였는데 이는 다음과 같은 꼴로 표현할 수 있다.

 

각각의 $f_i(w)$가 바로 데이터 샘플 하나에 대한 손실함수 값이다. 데이터 셋 크기가 $n$이라면, f(w)는 결국 각각의 데이터 샘플에 대한 손실함수 값의 평균이기 때문에 위와 같이 정의될 수 있다.

이 때 우리는 지금 하나의 손실함수 즉, $f_i(w)$를 사용하여 파라미터를 업데이트 한다면 이를 SGD, $n$보다 작은 어떤 부분집합을 사용하여 파라미터를 업데이트한다면 이를 mini-batch SGD라고 할 수 있을 것이다.

 

당연히 SGD, Mini-batch SGD는 Grdaient descent보다 계산량이 많이 적을 것이다. 하지만 이 방법 또한 gradient descent에서는 발생하지 않는 새로운 문제점이 있는데 이에 대해서는 다음 포스팅에서 살펴보고 이를 어떻게 해결/보완하는지도 함께 살펴보도록 하자.