Fancier Optimization

August 31, 2021

이번 시간에는 Optimization에 대해서 알아보겠습니다!✌ Deep learning에서는 forward와 back propagation을 반복하며 학습을 진행하게 됩니다. Loss function을 정의하여 forward해서 나온 결과 값과 label값을 비교하여 Loss가 얼마인지 계산하게 됩니다. 구한 Loss값을 통해 우리는 수 많은 weight에 대해 편미분 하고 빼줌으로써 각각의 weight를 update 시키죠! 이 방법은 우리가 평상시에 사용하고 있는 gradient descent 방법입니다. 오늘은 이 gradient descent를 base하는, 더 좋은 optimizer를 알아보도록 하겠습니다. 이번 포스팅에 대한 Category는 다음과 같습니다.

SGD

우리가 평상시에 사용하는 Gradient Descent는 아래와 같은 수식을 통해 parameter를 update하게 됩니다.

$w_{t+1} = w_t-\alpha \triangledown L(w_t)$

위의 수식은 basic하고 classic한 SGD의 형태입니다. $Loss$ 를 $w_t$ 에 대해서 편미분하고 이를 learning rate에 곱하여 $w_t$ 에 빼주게되면 update된 $w_{t+1}$ 이 나오게 됩니다. 하지만 SGD는 optimizor로써 다양한 문제를 갖게 되는데 어떤 문제를 갖고, 왜 발생하는지에 대해 알아보도록 하겠습니다.

The Problem of SGD

SGD는 아래와 같은 문제를 갖게 됩니다.

① zigzag를 그리며 수렴하여 convergence speed가 느립니다.

② saddle point에 빠질 수 있습니다.

③ local minima에 빠질 수 있습니다.

먼저 ①에 대해서 살펴보겠습니다. 우리가 어떤 parameter $W_1$ 과 $W_2$ 에 대해서 최적화를 진행한다면 $z$ 축을 Loss라 했을 때 아래와 같은 그래프를 생각해볼 수 있습니다.

assets 2021 08 31 1

위의 그림에 나와있는 두 개의 parameter인 $\theta_1$ 과 $\theta_2$ 를 각각 $W_1$ 과 $W_2$ 에 mapping된다고 가정하고 설명하겠습니다. 위의 그림은 두 개의 parameter $W_1$ 과 $W_2$ 에 대한 $Loss$ 그래프 입니다. 우리는 이 두 개의 파라미터에 대해서 $Loss$ 가 minimum일 때의 $W_1$ 과 $W_2$ 값을 알고 싶어합니다. $Loss$ 가 minimum이 되는 곳에 가기 위해서 gradient descent을 통해 천천히 다가가겠죠?😉

우선, 초기 상태의 $W_1$ 과 $W_2$ 의 값이 아래 그림에 있는 하얀색 점이라고 생각해봅시다.

assets 2021 08 31 2

그렇다면 우리는 저 하얀색 점에서부터 차근차근 내려가서 Loss가 minimum일 때인 빨간색 지점까지 gradient descent를 통해서 가야할 겁니다. 우리가 생각하는 ideal optimization의 방향은 아래의 그림과 같습니다.

assets 2021 08 31 3

하얀색 점이 $W_1$ 과 $W_2$ 의 초기 값이라면 당연히 gradient descent를 사용해서 위의 그림처럼 곧바로 수렴하면 좋겠죠? 하지만 gradient descent는 실제로 이렇게 동작하지 않습니다. 왜냐하면 Loss함수가 각각의 가중치들의 변화에 반응하는 정도(가중치마다 적용되는 gradient)가 다르기 때문입니다.

각각의 가중치들은 서로 다른 gradient를 갖게 됩니다. 당연히 $w_1$ ~ $w_n$ (모든 $weight$ )가 서로 같은 gradient를 가질 순 없겠죠?? 그 이유는 forward pass할 때, 모든 weight들이 서로 다른 input( $x$ 값)을 갖게되는데 back propagation을 진행하면서 chain rule에 따라 ${\vartheta (h(x)=wx+b) \over \vartheta w} = x$ 가 곱해지기 때문입니다. 또한, chain rule에 의해 앞에있는 layer들의 gradient들도 곱해지기 때문에 모든 weight들의 gradient는 다양한 값을 갖게 됩니다. 여기서 weight들 중 높은 gradient를 갖는 weight와 낮은 gradient를 갖는 weight가 생기게 되는 것입니다. 그렇다면 gradient 값이 많이 차이나는 두 개의 weight를 최적화시켜야 한다면 어떤 일이 일어날까요?

만약 Loss가 $W_1$ 보다 $W_2$ 의 변동에 더 민감하게 반응한다면 아래와 같은 현상이 일어나게 됩니다.

assets 2021 08 31 4

위의 그림을 좀 더 과장되게 그려보면 아래와 같이 나타나게 됩니다.

assets 2021 08 31 5

수직방향의 weight가 $W_2$ , 수평방향의 weight가 $W_1$ 이라고 해봅시다. 위의 그림을 보게 되면 Loss가 수직 방향의 가중치( $W_2$ ) 변화에 훨씬 더 민감한 것(gradient가 높은 것)을 볼 수 있습니다. 가운데 지점(smile 표정)이 Loss함수의 아래로 convex한 부분이라면 3차원의 Loss함수를 생각해봤을 때 $W_2$ 변화에 대해 3차원 Loss함수가 너무 민감하게 반응(gradient가 높다)하고 $W_1$ 변화에는 둔감(gradient가 낮다)하기 때문에 convex부분으로 가는 벡터의 크기가 현저히 달라지게 됩니다. 이에 zigzag를 그리며 optimal한 곳으로 가기 때문에 convergence speed가 너무 느린 것을 알 수 있습니다.

위에서 본 것과 같이 Loss함수는 한 방향으로는 엄청나게 민감할 수 있고 또 다른 방향으로는 덜 민감할 수 있습니다. 하지만 위에서 설명했던 것은 2개의 파라미터가 존재할 때이며 실제로는 parameter가 수천개가 될 수 있습니다. 이런 문제는 고차원 공간에서 훨씬 더 빈번하게 발생하게 됩니다. 만약 가중치가 수천개, 수천억개가 된다면 이동할 수 있는 방향이 너무나도 많고 이동할 수 있는 방향의 정도가 다양합니다. 이런 방향 중 불균형한 방향이 존재한다면 위와 같이 더 심한 zigzag를 그리며 수렴하거나 수렴하지 않을 수 있습니다(대부분 잘 동작하지 않겠죠??😊)

또한 ②, ③에서 적혀있는 것처럼 saddle point와 local minima에 빠질 수 있습니다. 아래의 그림은 saddle point와 local minima를 표현한 그림입니다.

< Local minima >

assets 2021 08 31 6

< Saddle point >

assets 2021 08 31 7

vanilla SGD를 위의 상황에 적용한다면 학습이 진행 되지 않습니다. 왜냐하면 local minima와 saddle point에서의 gradient는 0이기 때문입니다. 이에 우리는 momentum이라는 term을 SGD에 대입시켜 위와 같은 상황을 극복할 수 있습니다.

Momentum

Momentum을 사용한 SGD는 아래의 수식과 같습니다.

v_{t+1} = \rho v_t + \triangledown f(w_t)

w_{t+1}=w_t-\alpha v_{t+1}

Momentum을 추가한 SGD는 기존의 $velocity$ 를 유지합니다. vanilla SGD는 오로지 gradient 방향으로만 이동하였는데 Momentum을 추가한 SGD(이후부터는 M-SGD로 표기)는 gradient를 계산할 때 velocity를 이용하여 기존의 방향을 어느정도 유지한 채로 구하게 됩니다. 즉, 현재 미니 배치의 gradient 방향만을 고려하는 것이 아닌 이전의 velocity를 같이 고려하게 되는 것입니다(참고로 mini-batch를 사용할 경우, noise가 낀 학습데이터를 batch_size로 학습하기 때문에 살짝씩 튀면서 학습되며 수렴합니다.).

M-SGD는 하이퍼 파라미터 $\rho$ (rho)가 추가적으로 사용되고 이것은 momentum을 얼마나 반영할 것인지, 기존의 velocity를 얼마나 유지할 것인지 결정하게 됩니다. 보통 $\rho$ 는 0.9나 0.99와 같은 높은 값으로 맞춰주게 됩니다. 이렇게 하여 gradient vector 그대로의 방향이 아닌 velocity vector의 방향도 고려하여 나아가게 되는 것입니다.

이 momentum term을 사용하므로써 local minima와 saddle point에서 벗어날 수 있습니다. 또한, zigzag로 수렴하는 현상도 완화시킬 수 있습니다.이전의 velocity를 계속해서 더해줌으로써 velocity가 증가하게 되어 현재의 gradient값이 작아도 velocity를 더해주기 때문에 특정 dimension(weight)에 둔감했던 loss가 빠르게 줄어들게 됩니다.

하지만 momentum을 추가한 SGD가 좁고 깊은 global minima를 지나치면 안된다고 생각할 수 있습니다. 하지만 좁고 깊은 minima는 overfitting을 유발하게 된다고 합니다. training set를 더 늘린다면 이런 좁고 깊은 민감한 minima는 사라지게 되기에 training data의 변화에 좀 더 강인한 평평한 minima를 얻길 원합니다. 평평한 minima가 좀 더 일반화를 잘 할 수도 있으며 testing data에서도 더 좋은 결과를 얻을 수 있을거라고 합니다. 오히려 좁고 깊은 minima를 무시하는 것이 error가 아니라 momentum의 장점이 된다는 것입니다.

AdaGrad

SGD에 momentum term을 추가시키는 것 말고도 AdaGrad라는 최적화 방법이 존재합니다. AdaGrad는 M-SGD가 사용하는 momentum term 대신에 grad squared term을 사용하게 됩니다. AdaGrad의 구현 코드는 아래와 같습니다.

grad_squared = 0
while True:
	dx = compute_gradient(x)
	grad_squared += dx * dx
	x = x - learning_rate * dx / (np.sqrt(grad_squared) + 1e-7)

grad_squared term은 학습 중에 계산되는 gradient에 제곱을 하여 계속 더해주게 됩니다. weight를 update를 할 때는 앞서 계산한 grad_squared term으로 나눠주게 됩니다.

이 연산을 통해 gradient가 항상 높은 차원(weight)은 grad_squared term이 크므로 이 값을 나눠주게 되면 속도가 떨어지게 되고, gradient가 항상 낮은 차원(another weight)은 grad_squared term이 작아 이 값을 나눠주게 되면 속도가 붙게 됩니다.

하지만 학습 횟수가 늘어나게 되면 grad_squared term이 커지게 되는데 이 값을 나눠주게 되면 step size가 서서히 작아지게 됩니다. 이 현상은 loss함수가 convex한 경우, minmum에 근접하게 될 때 서서히 속도를 줄여서 수렴할 수 있기 때문에 좋은 특징이 됩니다. 하지만 non-convex 한 경우에서는 문제가 될 수 있습니다. saddle point에 걸려 AdaGrad가 멈춰버릴 수 있기 때문입니다. 이에 AdaGrad의 변형인 RMSProp이 등장하게 됩니다.

RMSProp

RMSProp에서는 AdaGrad의 grad_squared를 그대로 사용하게 됩니다. 하지만 조금 변형된 grad_squared term을 사용하는데 RMSProp의 코드는 아래와 같습니다.

grad_squared = 0
while True:
	dx = compute_gradient(x)
	grad_squared = decay_rate * grad_squared + (1-decay_rate) * dx * dx
	x = x - learning_rate * dx / (np.sqrt(grad_squared) + 1e-7)

위의 코드를 보게 되면 기존의 AdaGrad의 grad_squared와 다르다는 것을 볼 수 있습니다. 기존의 AdaGrad는 무작정 현재의 gradient를 제곱해서 더했지만 RMSProp는 decay_rate을 추가시켜 지수 가중 이동 평균(Exponential weighted moving average)을 사용하므로써 얼마나 이전의 grad_squared 값을 반영할 건지 결정할 수 있습니다. 또한, 현재 gradient의 제곱값을 (1-decay_rate)만큼 곱해주어 반영하게 됩니다.

RMSProp에서는 decay_rate를 보통 0.9나 0.99를 사용하게 되며 현재 gradient의 제곱을 계속해서 더하고 나눠준다는 점이 AdaGrad와 유사합니다. 이를 통해 두 개의 optimizer는 step의 속도를 감속시키거나 가속시킬 수 있습니다.

하지만 RMSProp은 step size가 점점 줄어드는, 즉 점점 속도가 줄어드는 문제를 해결하였습니다.

지금까지 SGD와 M-SGD, AdaGrad, RMSProp에 대해서 알아보았습니다. Momentum은 $velocity$ (momentum)를 이용해서 step을 조절하고 AdaGrad와 RMSProp은 grad squared term을 나눠주는 방식으로 step을 조절해주었습니다. 만약 Momentum에서 사용한 $velocity$ 의 개념과 RMSProp에서 사용했던 grad squared term을 조합하면 어떨까요?😉

Adam

Momentum과 AdaGrad, RMSprop의 개념을 조합하여 만든 optimization algorithm이 바로 Adam입니다. Adam은 first_moment와 second_moment를 이용해서 이전의 정보를 유지시키는데 Adam의 first_moment는 Momentum에, second_moment는 AdaGrad와 RMSProp에 대응되는 개념입니다. Adam의 코드는 아래와 같습니다.

first_moment = 0
second_moment = 0
while True:
	dx = compute_gradient(x)
	first_moment = beta1 * first_moment + (1-beta1) * dx
  second_moment = beta2 * second_moment + (1-beta2) * dx * dx
	x = x - learning_rate * first_moment / (np.sqrt(second_moment)+1e-7)

first_moment부터 살펴보게 되면 Momentum때와는 다르게 가중합을 사용하였습니다. Momentum의 식은 아래와 같습니다.

v_{t+1} = \rho v_t + \triangledown f(w_t)

위의 수식을 보게되면 $velocity$ 는 exponential weighted moving average를 사용하지 않았는데 first_moment에서는 gradient의 exponential weighted moving average를 사용한 것을 볼 수 있습니다. 하지만 first_moment는 Momentum에서의 $velocity$ 와 의미적으로 같습니다.

second_moment는 AdaGrad와 RMSProp처럼 gradients의 제곱을 이용합니다. AdaGrad와 RMSProp와 같이 sqrt(second_moment)를 나눠주게 되며 똑같은 역할을 하게 됩니다(큰 값을 갖게 되면 작은 step으로, 작은 값을 갖게 되면 큰 step으로 학습 진행).

이에 Adam의 형태를 momentum + grad squared term으로 구성되어 있는 것으로 볼 수 있습니다. 하지만 현재의 Adam은 문제가 있습니다.

초기에 second_moment를 0으로 초기화하여 epoch를 돌때마다 second_moment는 update를 거치게 됩니다. 하지만 beta2는 decay_rate로 0.9나 0.99의 값을 가지기 때문에 second_moment는 0에 가까운 값을 초기 상태에서 갖게됩니다. weight를 update 해줄 때 second_moment로 나누기 때문에 초기의 step이 엄청나게 커지게 됩니다. 초기의 step이 엄청나게 커진 것은 손실 함수자체가 가파르기 때문이 아니라 second moment를 0으로 초기화 시켜 발생한 인공적인 현상이기에 문제가됩니다.

first_moment 또한 작아서 상쇄될거라 생각할 수 도있지만 상쇄되지 않고 초반 step이 엄청나게 커져 엉뚱한 곳으로 이동하여 잘못될 수 도 있습니다. 이에 문제를 해결하고자 보정항(bias correction term)을 따로 추가하게 됩니다.

bias correction term을 추가한 Adam의 코드는 아래와 같습니다.

first_moment = 0
second_moment = 0
for t in range(num_iterations):
	dx = compute_gradient(x)
	# Momentum
	first_moment = beta1 * first_moment + (1-beta1) * dx

	# AdaGrad, RMSProp
    second_moment = beta2 * second_moment + (1-beta2) * dx * dx

	# Bias correction
	first_unbias = first_moment / (1 - beta1 ** t)
	second_unbias = second_moment / (1 - beta2 ** t)

	# AdaGrad, RMSProp
	x = x - learning_rate * first_moment / (np.sqrt(second_moment)+1e-7)

first_moments와 second_moments를 update하고 난 후 현재 step에 적절한 bias correction term(firstunbias와 secondunbias)을 계산합니다. 이 bias correction term을 통해 초기 step에서 기존 Adam의 작은 second_moment로 나눠줄 때 step이 엄청 커지는 문제를 해결할 수 있습니다. second_unbias에 있는 beta2 ** t는 초기 step에서 값이 0.9나 0.99가 됩니다. 이 값을 1에 빼게 된다면 0.1이나 0.01이 나오게 되는데 이 값으로 second_moment를 나눠줌으로써 second_moment의 값이 10배, 100배로 늘어나며 기존의 문제를 해결할 수 있습니다. 초기 step에서 기존 Adam의 second_moment값이 작은게 문제였기 때문에 이 값을 10배, 100배로 늘려줘서 보정을 한 것입니다. first_moment 또한 기존 Adam에서의 초기 step에서 매우 작은 값을 가지고 있었지만 늘려주게 되면서 보정됩니다.

Adam은 다양한 문제들에도 잘 작동하여 모든 문제에서 기본 알고리즘으로 Adam을 사용한다고 합니다. 실제로 Adam은 beta1=0.9, beta2=0.999, learning_rate=1e-3 or 5e-4(1e-4~1e-3)가 많은 모델의 첫 시작 포인트로 좋습니다.

Compare

assets 2021 08 31 8

위의 그림에서 검정색은 SGD, 파란색은 M-SGD, 빨간색은 RMSProp, 보라색은 Adam을 사용했을 때의 결과입니다. Momentum은 $velocity$ 를 이용해서 step을 조절하고 AdaGrad와 RMSProp은 grad squared term을 나눠주는 방식으로 step을 조절해줍니다. 이에 momentum의 경우, $velocity$ 덕분에 overshoot한 이후에 다시 minima로 돌아오게 됩니다. 하지만 RMSProp의 경우 gradient가 크면 작은 step으로 줄어들고, gradient가 작다면 좀 더 큰 step으로 줄어들기 때문에 각 차원마다(각 weight마다) 상황에 맞도록 수렴합니다.

Adam은 momentum과 RMSProp을 섞은 듯한 모습을 보여줍니다. Adam이 momentum처럼 overshoot을 하긴 하지만 momentum 만큼 심하게 overshooting되지 않게 됩니다. 왜냐하면 현재 gradient에 (1-beta1)을 곱해서 더해주며(가중합을 말하는겁니다😉) 현재 gradient가 높으면 작은 step으로 가게끔 보정해주고 낮으면 큰 step으로 가게끔 보정(gradsquared & unbiased term)해주기 때문입니다. 이에. Adam은 RMSProp의 특징을 갖고있다고 말할 수 있습니다. 위에서 말했던 것처럼 **overshooting의 정도를 줄여주는데 gradsquared term과 unbiased term이 기여하기 때문입니다. 이에 **Adam또한 각 차원(수많은 weight들)의 상황을 고려해서 step을 이동한다고 말할 수 있습니다.

따라서 Adam은 momentum처럼 동작하는 동시에 RMSProp처럼 동작합니다.

Conclusion

많은 optimization algorithm을 알아보았지만 Adam을 가장 많이 사용한다고 합니다. 지금까지 optimization algorithm들이 training error를 줄이고 손실함수를 최소화시키기 위해 동작하는 것처럼 설명했지만 사실 우리의 목표는 training error를 줄이는 것이 아닙니다. 우리의 목표는 한번도 보지 못한 데이터, 즉 test(validation) dataset에 대한 성능을 끌어올리는 것이 목표입니다. 이에 training error를 줄이는 것도 좋지만 우리가 정말 하고자 하는 것은 test dataset에 대한 error를 줄이는 것입니다. 이에 모델이 학습될 수록 떨어지는 training error와 한번도 보지못한 데이터인 test datset의 error의 격차를 줄이는 것이 중요합니다. 그렇다면 우리가 Loss에 대해 최적화를 모두 마친 상태에서 한번도 보지 못한 데이터인 test dataset에서의 성능을 올리기 위해서는 어떻게 해야할까요?

첫번째 방법은 Ensemble 입니다. 여러개의 모델을 독립적으로 학습시켜 모델들의 결과의 평균을 이용하는 방법입니다. 모델이 늘어날 수록 overfitting이 줄어들게 되며 성능이 향상되게 되는데 보통 2%정도 상승하게 된다고 합니다. 그렇다면 단일모델에서의 validation set에 대한 성능을 올리려면 어떻게 해야할까요?

이 방법은 다음 포스팅 때 올리도록 하겠습니다!
감사합니다😎

Summary

SGD는 Loss값이 각 parameter( $weight$ )의 변동에 따라 민감한 정도가 다르기 때문에 zigzag를 그리면서 수렴하므로 convergence speed가 느려질 수 있으며, saddle point와 local minima에 빠질 수 있습니다. 고차원 공간(여러개의 weight)에서는 zigzag로 수렴하는 현상, saddle point, local minima에 더 잘 빠질 수 있습니다.
SGD에 momentum term을 추가시키면 기존의 $velocity$ 를 $\rho$ 만큼 유지한채로 현재 gradient값을 더하여 update하기 때문에 saddle point와 local minima에서 빠져나올 수 있습니다.
M-SGD의 $\rho$ 값을 보통 0.9나 0.99로 설정합니다.
좁고 깊은 minima(=overfitting)를 원하는 것이 아니라 평평한 minima를 찾는 것을 optimizer는 목표로 합니다.
AdaGrad는 Neural Network를 학습시킬 때 잘 사용하지 않습니다.
RMSProp에서는 decay_rate를 보통 0.9나 0.99를 사용합니다.
Momentum은 $velocity$ (momentum)를 이용해서 step을 조절하고 AdaGrad와 RMSProp은 grad squared term을 나눠주는 방식으로 step을 조절한다.
초기 seoncd_moment가 너무 작아 step이 너무 커지기 때문에 발산할 수 있습니다. 이에 Adam에서는 보정항(bias correction term)을 사용합니다.
Adam은 beta1=0.9, beta2=0.999, learning_rate=1e-3 or 5e-4(1e-4~1e-3)가 많은 모델의 첫 시작 포인트로 좋습니다.
Optimizer를 사용할 때 Adam을 사용합시다!😎

Reference

SGD+Momentum: https://hyunw.kim/blog/2017/11/01/Optimization.html
Difference between SGD and GD: https://datascience.stackexchange.com/questions/36450/what-is-the-difference-between-gradient-descent-and-stochastic-gradient-descent
GD vs BGD vs MSGD: https://skyil.tistory.com/68
cs231n Lecture

Written by@[Gunu]

AI, 수학에 관심이 많은 대학생입니다😊

GitHub