Optimization 심화 : Noise에 대하여 (1)

 

 

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

 

오늘부턴 stochastic gradient의 중요한 특징 중 하나인 'Noise'에 대해서 살펴보고자 한다.

 

'Deterministic' gradient descent는 모든 data를 활용해서 계산된 loss와 gradient이기 때문에 우리는 이를 효율적으로 대체하기 위해 매 iteration마다 data의 일부를 (random) sampling해서 'mini-batch'를 활용하여 gradient를 계산한다.

당연히 이는 가장 가파른 하강방향 (Deterministic 'Negative' gradient)과 차이가 있을 수밖에 없고 이 차이를 만드는 요소가

noise이다.

 

noise는 다음과 같은 term을 의미한다.

$g_t - \nabla f(x_t)$

 

noise의 크기는 일반적으로 다음과 같이 norm을 이용해서 측정된다.

$\lVert g(x_t) - \nabla f(x_t) \rVert_2$

 

오늘은 이 noise가 convergence에 미치는 영향을 살펴보자.

 

일단 noise가 꼭 부정적인 영향만 있는 것은 아니다. 

loss landscape은 'non-convex'하기 때문에 무수히 많은 local minima와 global minima등이 존재한다.

만약 우리가 'Deterministic' gradient 만을 사용하면 어떤 local minima에 도달했을 때 이 지점에선 더 이상 파라미터가 이동하지 못한다. 

당연히 local minima에선 $\nabla f(x) = 0$이기 때문에 파라미터가 더 이상 이동하지 못할 것이다.

하지만, stochastic gradient는 $\nabla f(x) = 0$인 지점에서도 $g(x_t) \neq 0$일 수 있기 때문에 이동이 가능하다.

 

이는 충분히 학습이 이뤄지지 않은 상태에서 파라미터가 'bad' local minima에 빠지는 것을 방지하며 noise의 긍정적인 효과로 여겨진다.

 

하지만 stochastic gradient는 학습의 속도를 'deterministic' gradient에 비해서 느리게 한다.

이는 다음과 같은 대표적인 그림이 있다.

 

https://www.nomidl.com/machine-learning/what-is-gradient-descent-batch-gradient-descent-stochastic-gradient-descent-mini-batch-gradient-descent/

 

 

여기서 Batch gradient descent라고 써져 있는 것이 'full-batch' gradient descent이다.

SGD는 '평균적으로' Gradient의 방향을 따라가지만, 매 step마다는 전혀 엉뚱한 방향을 향할 수 있다.

 

그렇기 때문에 우리는 SGD의 convergence를 유도할 때 다음과 같은 가정을 한다.

 

$ \mathbb{E}[\lVert g(x) - \nabla f(x) \rVert^2] \le \sigma^2$

 

위 가정은 일반적으로 많이 쓰이는 stochastic gradient의 'variance'가정이며 stochastic gradient가 unbiased estimator이며 true gradient의 norm이 'upper' bound돼 있다는 가정 하에선 다음과 같은 가정과 동치이다.

 

$\mathbb{E} [\lVert g(x) \rVert^2] \le \sigma^2$

 

최근에는 이 가정을 조금 더 완화한 가정이 많이 쓰이는데 variance / second moment에 대해서 affine 함수를 upper bound로 설정하는 것이다. 즉 다음과 같은 형태이다.

 

$\mathbb{E}[\lVert g(x) - \nabla f(x) \rVert^2] \le \sigma_0^2 + \sigma_1^2 \lVert \nabla f(x_t) \rVert^2$

 

이를 second moment에 대한 가정으로 바꿀 때, 우리는 true gradient의 norm이 upper bound돼 있다는 가정 없이 다음과 같이 바꿀 수 있다.

 

$\mathbb{E} [\lVert g(x) \rVert^2] \le \sigma_0^2 + (\sigma_1^2 + 1) \lVert \nabla f(x_t) \rVert^2$

 

이 가정에서 $\sigma_0 = 0$인 경우를 다양한 경우가 있는데 가장 대표적으로 overparameterized case이다.

즉, 모델의 파라미터가 training data points를 interpolate하는 것이 가능하여, train loss를 0이 되게 만드는 것이 가능한,

그리고 그 지점에서는 (true gradient가 0인 지점) stochastic gradient도 0이 된다.

 

하지만, $\sigma_0 > 0$인 경우는 true gradient가 0이더라도 stochastic gradient는 0이 되지 않는 상황을 포함한다.

 

이외에도 여러 다양한 형태의 가정들이 있다.

예를 들어, noise의 distribution 자체를 가정하는 경우도 있다.

가장 많이 쓰이는 가정이 noise가 'sub-Gaussian distribution'을 따른다인데, 이는 light-tail modeling으로 알려져 있다.

이는 앞서 소개된 일반적인 분산 가정보다 더 강한 가정에 속한다.

 

하지만 실제 neural network를 학습할 때는 stochastic gradient의 noise는 'heavy-tail noise'를 따른다는 실험적 관찰이 많이 나와있고, 이를 반영한 수렴 분석 논문들이 여럿 꾸준히 나오고 있다.

 

heavy-tail distribution과 light-tail distribution을 구분하는 기준은 exponential distribution이다.

 

 

위 그림을 보면 분포의 꼬리 (tail)부분이 exponential 보다 '천천히' 감소함을 볼 수 있는데 이를 우리는 'heavy-tail'이라고 부른다. 즉, $0$으로 향하는 속도가 지수분포보다 느리기 때문에 이상치 (outlier)들이 나타날 확률이 그것보다 훨씬 높은 것이다. 이를 sgd의 noise가 heavy-tail distribution을 갖는다는 상황으로 대입해보면, true gradient와 차이가 매우 큰 (noisy) gradient가 나올 확률이 매우 높음을 의미하고 이는 당연히 학습에 부정적 영향을 미칠 수 밖에 없게 된다.

 

heavy-tail distribution의 수학적인 엄밀한 정의는 다음과 같다.

 

확률변수 $X$의 분포함수 $F$가 heavy-tail을 갖는다는 의미는, 그것의 Moment generating function (MGF) $M_x(t)$가 infinite한 경우, $F$가 heavy-tail distribution이라고 정의한다.

대표적으로 'fat-tailed distribution', 'long-tailed distribution', 'subexponential distribution'이 있다.

 

일반적으로 Optimization for ML 논문들에서 noise가 heavy-tailed distribution을 갖는다는 다음과 같이 표현된다.

 

$\mathbb{E}[\lVert g(x) - \nabla f(x) \rVert^{\sigma}] \le \alpha^{\sigma}$

for $\sigma \in (1, 2]$

 

위 상황에서 $\sigma < 2$일 때 우리는 heavy-tail distribution이라고 이야기한다.

즉, variance가 upper bound되어져 있지 않은 것이고 이는 곧 'infinite' variance를 허용하는 것이다.

 

heavy-tail distribution에서 SGD는 수렴하지 못하고, 발산하기 때문에 이때 일반적으로 사용하는 기술이 'gradient clipping'이다.

이에 대해선 추후 기회가 있다면 다뤄보자.