Deep dive into optimization : Gradient descent - Updated

 

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

 

 

지난 포스팅에서는 Gradient descent 알고리즘이 어떻게 나오게 되었는지를 설명하였다.

$t+1$번째 iteration (step)에서의 파라미터 $w_{t+1}$는 다음과 같이 업데이트가 진행된다.

$w_{t+1} = w_t - \eta \nabla f(w_t)$

 

이때 $\nabla f(w_t) := \frac{1}{n} \sum_{i=1}^n \nabla f_i(w_t)$이므로, 모든 training data를 활용해서 Loss 값 $f(w_t)$를 계산하고 이를 backpropagation 알고리즘을 통해 $\nabla f(w_t)$를 구하는 것이 gradient descent이다.

https://saugatbhattarai.com.np/what-is-gradient-descent-in-machine-learning/

 

하지만 이 방법은 현재의 딥러닝에 적용하기에는 현실적인 문제점이 있다고 하였는데 바로 학습하는데 시간이 너무 오래걸린다는 점이다. 왜냐하면 모델 파라미터를 한 번 업데이트할 때 전체 dataset에 대해서 Forward-Backward 연산을 수행해야 하는데 현재 딥러닝의 모델 사이즈는 점점 커지고 있고 (e.g. overparameterized model) 이를 학습시키기 위한 데이터셋 크기도 계속해서 커지고 있기 때문에 매 iteration에서 전체 데이터셋에 대해 연산을 수행하는 것은 계산량이 매우 큰 작업이다.

 

그래서 현재 딥러닝을 학습할 때는 gradient descent를 잘 사용하지 않는다.

그 대신 매 iteration에서 데이터셋 전체가 아닌 일부 (Mini-batch stochastic gradient descent)만 사용하는 방법이 하나의 표준으로 자리잡았다.

우선, Stochastic Gradient descent (SGD)를 먼저 알아보자.

SGD란 데이터 샘플 하나를 사용해서 loss value, gradient value를 구한 다음 파라미터를 업데이트하는 것을 의미한다.

SGD

 

여기서 딥러닝 기본 용어를 점검하고 가자. 위와 같이 파라미터 업데이트를 한 번 진행하는 과정을 'iteration (step)'이라 한다.

그리고 위와 같이 SGD는 매 step에서 data sample을 random sampling하고, 그 데이터를 활용해서 loss value, gradient value를 계산하고 파라미터를 업데이트하는데, 이 과정을 여러 번 반복하면 모델이 모든 데이터셋을 경험하게 될 것이다.

그렇게 모델이 전체 dataset을 모두 활용하는 것을 '1 epoch'이라 한다.

예를 들어서 데이터셋이 이미지 10,000장이고 SGD를 활용해 모델을 학습시킨다면, 10,000번의 iteration이 지나면 1 epoch이 된다.

 

그렇다면, Mini-batch SGD란?

데이터셋의 부분집합을 sampling하여 모델을 학습시키는 것이다. 이 때 부분집합의 크기를 Mini-batch Size라 하는데 이를 $|b|$라 하자. 그러면 Mini-batch SGD는 다음과 같이 표현할 수 있다.

Mini-batch SGD

 

당연히 $b << n$이다.

자, 그렇다면 SGD는 결국 다음과 같이 생각할 수 있다.

데이터셋 전체를 이용해서 구한 loss value, 즉 $f(w_t)$와 그때의 gradient $\nabla f(w_t)$가 참값이라 하면, 이를 직접 구하는 것은 연산량이 매우 큰 작업이기 때문에 이에 대한 추정치 $f_i(w_t)$와 그때의 gradient $g(w_t) := \nabla f_i(w_t)$를 대신 활용하는 것이다.

그렇게 추정치를 활용해서 모델을 학습시켜도 상당히 학습이 잘 되어왔기 때문에 SGD, Mini-batch SGD는 현재 딥러닝 학습 방법의 가장 대표적인 알고리즘으로 자리잡게 되었다.
(왜? 인지에 대해서는 현재도 활발하게 연구가 이뤄지고 있는 중요한 이론 연구의 토픽이다.)

 

그렇다면 SGD는 문제점이 없을까? 정말 GD와 비교했을 때 연산량이 적다는 장점만 존재하는 것일까?

아쉽게도 그렇지 않다. 문제점이 있다.

 

전체 데이터셋에서 mini-batch를 sampling하는 확률분포가 (i.i.d) Uniform distribution을 따른다고 가정하면, $\mathbb{E} g(w) = f(w)$이지만, 문제는 분산 (또는 stochastic noise)가 존재한다는 것이다.

gradient가 임의로 샘플링된 데이터에 의해 구해진 값이기 때문에 확률적인 값이고 (stochastic) 그렇다면 확률 분포를 가지고 있을 것이다. 

이 분포가 정확히 어떤 분포인지는 알 수 없지만 그것의 평균이 True gradient ($\nabla f(w)$)이고, 그것의 분산이 존재한다고 가정하자.

즉, $\mathbb{E} [g(w) - \nabla f(w)]^2 \le \sigma^2$인 어떤 $\sigma$가 존재한다고 가정하는 것이다.

이것 자체는 하나의 가정이다. $\sigma^2$가 어떤 고정된 상수, constant일지, 아니면 저 값이 존재하지 않을지 우리는 모른다.

하지만 위와 같이 고정된 상수 $\sigma^2$가 존재한다고 가정하는 경우가 일반적인 가정이고 현재 본 포스팅에서는 이 가정만으로도 우리는 충분하기 때문에 위와 같이 가정하고 넘어가겠다. 

조금 더 심화된 내용들은 추후 paper review 카테고리에서 다룰 기회가 있지 않을까 싶다.

 

그렇다면 저 분산, 일종의 noise ($\lVert g(w) - \nabla f(w) \rVert$) 때문에 어떤 현상이 발생할까?

https://www.analyticsvidhya.com/blog/2022/07/gradient-descent-and-its-types/

 

여기 이를 아주 잘 표현하는 그림이 있다.

먼저 Batch gradient descent가 앞서 언급한 Gradient descent (GD)이다. 앞에 Batch, deterministic 등을 붙이기도 한다.

$+$로 표시돼 있는 optimal point를 향해 학습이 진행되는데, 이때 GD는 일직선으로 목표 지점을 향해 잘 수렴하지만, SGD는 optimal point를 향해 일직선으로 이동하지 않고 위 아래로 진동하면서 이동하는 모습을 보인다.

Mini-batch SGD도 진동의 정도는 SGD보다 약하지만 역시나 진동하는 모습을 보인다.

그리고 진동의 정도는 optimal point에 가까우면 가까울수록 더 심해지는데 이는 결국 local minima 정확히 그 지점으로 쉽게 수렴하지 못함을 의미한다. (실제로 위 그림에서 SGD가 완전히 $+$에 다다르진 못했음을 볼 수 있다.)

 

 

 

이를 표현한 또 다른 그림이다.

직관적으로 이러한 현상이 발생하는 이유는 결국 loss value, gradient value가 참값이 아니라, 어떤 확률분포를 가지고 있는 stochastic value이기 때문에 매 step에서 최적의 방향으로 이동하지 못하기 때문이다. 그리고 gradient는 0일지라도, stochastic gradient는 0이 아닐 수도 있다.

그렇다면 위와 같이 학습 후반부로 갈수록 진동하는, 그리고 결국 optimal point로 수렴하지도 못하는 상황을 방지하기 위해서, 완화하기 위해서 우리는 무엇을 할 수 있을까?

 

바로 step-size를 조정하는 것이다. 

step-size ($\eta$)의 역할이 무엇인가? 앞선 포스팅에서 step-size가 작으면 1차 테일러 근사식에서 $w_{t+1}$가 $w_t$에서 멀리 떨어지는 것을 강하게 규제하는 것이고, step-size가 크면 $w_{t+1}$이 $w_t$에서 멀리 떨어지는 것을 덜 규제하는 것이라고 하였다.

실제로 $w_{t+1} = w_t - \eta g_t$를 보더라도 $\eta$는 0보다 큰 스칼라 값이고, 이것이 크면 $w_{t+1}$이 멀리 이동할 것이고, 작으면 상대적으로 덜 이동할 것임을 알 수 있다.

즉, step-size를 어떤 일정한 값이 아니라, 학습이 진행됨에 따라 이를 조정해나가면 우리는 학습 후반부에 진동의 정도를 완화할 수 있고, optimal point로 수렴하지 못함을 방지할 수도 있다.

그렇다면 $\eta$를 어떻게 조정해야 할까? 점점 증가시켜야 할까? 점점 줄여야 할까?

이는 현재 딥러닝 최적화 분야에서 상당히 활발하게 연구가 이뤄져왔고, 현재도 진행중인 주제이다.

이에 대해서는 추후 paper review에서 기회가 된다면 관련 논문을 다루도록 하겠다.

 

일단, 가장 일반적인 정답을 이야기하고 마무리하자면 step-size를 점차 줄여나가야 한다.

(정확히는 Robbins-Monro condition을 만족해야 한다는 것이 정설이다.)

 

* Robbins Monro condition

step size $\eta_t$가 다음과 같은 조건을 만족하고 stochastic gradient의 분산이 $\sigma^2$으로 upper bounded돼 있으면, SGD의 수렴성이 보장된다 (with a probability $1$).
$1. \sum_{t=1}^T \eta_t = \infty$

$2. \sum_{t=1}^T \eta_t^2 < \infty$

 

왜 step size를 줄여나가야 하냐면, 학습 후반부에 local minima 근처에서 iteration 낭비가 되고 있는데 (stochastic noise 때문에) 이 상황에서 상대적으로 큰 step-size를 사용한다면, local minima에서 더 멀리 벗어나게 될 수도 있고, 결국 loss value가 다시 증가하는 더 안 좋은 상황을 맞이할 수도 있기 때문이다.

https://www.jeremyjordan.me/nn-learning-rate/

 

즉, 적절한 값의 step-size를 활용하면서 이를 잘 조정해나가야지만 우리는 SGD를 활용해 모델을 잘 학습시킬 수 있다.

하지만 step size를 줄여나가는 것은 constant step size를 사용할 때보다 수렴 속도를 감소시키는 부정적 요소가 있다. 그래서 stochastic gradient descent는 gradient descent보다 수렴 속도가 일반적으로 느리다.

이렇게 step size를 학습 과정 중에 그 값을 조정해나가는 테크닉을 Scheduling이라 하는데 이는 실험적/이론적으로 매우 활발하게 연구되어져 왔고, 현재도 진행중인 분야이다. (매우 중요한 주제이다.)

 

자, 그렇다면 SGD, Mini-batch SGD의 기본적인 개념에 대해 살펴보았다.

다음 시간에는 이들이 실제로 optimal point로 수렴하는지, 그렇다면 어느 정도의 빠르기로 수렴하는지, loss function에 대한 적절한 가정을 통해 이를 수식적으로 유도해보자.