[논문 Review] 04. Overview of Gradient Descent algorithms

 

Gradient Descent를 활용한 Optimizer가 어떻게 발전했는지 알아보자

---

 

 

Abstract

본 논문에서는 각 Gradient Descent Algorithms의 장단점을 알아보고, 다양한 알고리즘의 동작에 대한 직관을 가질 수 있게 한다. 수식적인 부분은 증명보다는 대략적인 동작 과정을 이해하는 정도로 쓰일 것이고, 자세한 증명은 원본 논문을 참고하면 좋을 것 같다.

 

Introduction

What is Gradient Descent?

Gradient Descent는 모델의 파라미터 \(\theta \in R^d\) 에 의해 파라미터화된 목적 함수인 \(J(\theta\)) 를 최소화하는 방법으로, 파라미터를 기준으로 목적 함수에 대한 그래디언트 \(\nabla_{\theta}J(\theta)\) 반대 방향으로 파라미터를 업데이트하여 최소화한다.

보다 직관적으로 설명하면 목적 함수가 일종의 경사면을 만들고, 거기에 공을 굴려서 가장 낮은 지점 (local minima, global minima) 에 도달하도록 하는 방식이다.

 

[각주:1]">

[그림 1] 여러 가지 gradient descent algorithms를 시각화^[각주:2]

 

본격적으로 각각의 기법들을 알아보며 Gradient Descent algorithms (이하 GD algorithms) 를 기반으로 한 Optimizer가 어떤 이유로, 그리고 어떤 방식으로 발전했는지 수식과 간단한 수도 코드를 통해 알아보고자 한다.

 

Gradient Descent Variants

Batch Gradient Descent (vanila GD, BGD)

가장 초기에 나온 기본적인 GD algorithm이다. 전체 데이터를 가지고 gradients를 계산하고 한 번에 업데이트를 해버린다는 매우 심플한 방법이다.

BGD update

• \(\theta\) : 파라미터
• \(\eta\) : 학습률. minimum 에 도달하기 위한 step의 크기를 나타내는 주요 파라미터이다.
• \(J (\theta)\) : 목적함수

for i in range(nb_epochs):

    # 지정한 loss function (목적함수) 에 대해 전체 data를 통해 일괄적으로 gradient 계산
    params_grad = evaluate_gradient ( loss_function , data , params )
    
    # 지정해둔 learning rate를 통해 step size 조절. 업데이트를 진행
    params = params - learning_rate * params_grad

 

장점

• 이해가 쉽고 직관적이다

단점

• 전체 데이터의 gradient를 계산해야 하므로 매우 느릴 수 있고, 데이터가 큰 경우에는 아예 메모리에 못 올릴 수도 있다.
• 온라인 학습이 불가능 (새로운 예제 추가 X)

 

 

Stochastic Gradient Descent (SGD)

Batch GD 방식의 단점은 '한 번에 전체 데이터를 계산해야 한다' 는 것에서 기인한다.

그렇다면 아예 데이터 샘플 1개마다 1번씩 업데이트를 수행하는 것은 어떨까?

SGD update

방식은 앞서 살펴본 BGD와 동일하지만 샘플 1개씩 gradient를 계산하고 업데이트를 한다는 점에서 차이가 있다.

for i in range (nb_epochs):
	# 데이터를 셔플
    np.random.shuffle(data)
    
    # 데이터의 샘플마다 gradient를 계산하고 파라미터를 업데이트 
    for example in data :
        params_grad = evaluate_gradient ( loss_function , example , params )
        params = params - learning_rate * params_grad

 

장점

• BGD보다 업데이트가 훨씬 빠르다
• 새로운 예제가 추가되는 경우 (온라인 학습 등) 에도 사용할 수 있다 

 

단점

• 샘플 하나마다 graident 업데이트가 진행되기 때문에 변동이 심하다. 즉 수렴 과정에서의 안정성이 떨어진다

[각주:3]">

SGD vs BGD^[각주:4]

 

흥미로운 점은 이러한 SGD의 변동성으로 인해 BGD보다 오히려 더 좋은 local minima에 도달할 수도 있다는 점이다.

그러나 동시에 정확한 최적점으로 도달하기 어렵게 만드는 요인이기도 하다.

 

이러한 문제를 해결하기 위해서는 LR scheduler 등을 활용하여 학습 과정에서 learning rate를 천천히 줄여나가는 방법이 있다.

이렇게 학습률을 스케줄링하면 BGD처럼 안정적으로 수렴하는 과정을 볼 수 있고, 대부분의 non-convex & convex 목적 함수에서 local 혹은 global minimum으로의 수렴을 보장한다.

 

 

Mini-batch Gradient Descent

Mini-batch GD는 위 두 가지 방식 (BGD, SGD) 를 적절히 섞은 훈련 방식으로,

전체 데이터를 한 번에 업데이트 하는 것도, 샘플마다 한 번씩 업데이트 하는 것도 아니라 데이터를 n개의 mini-batch로 나누어 업데이트를 진행하는 것이다.

Mini-batch GD update

for i in range (nb_epochs):
	# SGD와 마찬가지로 데이터를 셔플
    np.random.shuffle(data)
    
    # 지정된 배치 사이즈로 데이터를 분할하고 iterate하며 gradient를 업데이트
    for batch in get_batches (data , batch_size =50):
        params_grad = evaluate_gradient ( loss_function , batch , params )
        params = params - learning_rate * params_grad

 

장점

• SGD의 단점인 수렴 과정에서의 불안정성을 줄이고 보다 안정적으로 수렴이 가능하다
• 최신 딥러닝 라이브러리에 공통적으로 사용되는 matrix optimizations를 활용해 gradient 계산을 매우 효율적으로 수행할 수 있다

 

이렇듯 mini-batch GD에서는 업데이트되는 데이터의 사이즈를 조절하며 앞서 나온 SGD, BGD 방식의 단점들을 개선했지만 해당 방식으로는 해결되지 않는 근본적인 문제점들이 존재한다.

 

단점

• 적절한 학습 속도를 선택하는 것이 어렵다. 어떻게 보면 실험할 여지가 많다고도 볼 수 있겠지만, 학습률 하이퍼파라미터에 크게 의존하여 수렴 속도가 매우 느려지거나 아예 overshooting이 일어나는 경우가 존재하므로 골치 아픈 문제다.

• 앞서 나온 LR schedule은 서서히 학습률을 감소시키며 안정적인 수렴을 가능하게 하지만 스케줄러의 하이퍼파라미터 또한 미리 지정해야 하므로 데이터의 특성에 따라 유연하게 조정하기 어렵다.
• 데이터가 sparse하고 피처마다 매우 다른 빈도수를 보일 때, 드물게 나오는 피처에 대해 더 큰 업데이트를 수행하고 싶을 수 있다. 그러나 현재 방식에서는 모든 파라미터 업데이트에 동일한 학습률이 적용되므로 유연한 조정이 불가능하다.
• non-convex 목적함수를 최적화할 때, (특히 고차원 데이터에서) 문제가 되는 것은 local minima보다 saddle point일 수 있다는 선행 연구가 존재한다.^[각주:5] 기존의 gradient descent 방식은 특히나 saddle point에 갇혔을 때 빠져나오기 힘든 것으로 알려져있다.

 

saddle point

 

[각주:6]">

local minima vs saddle point^[각주:7]

 

 saddle point는 모든 가중치의 기울기는 0이지만 모든 가중치가 극소점은 아닌 지점이다. 

[각주:8]">

saddle point ^[각주:9]

그림의 출처인 위키피디아로 가보면 여러 가지 수학적 논의를 통해 saddle point (안장점) 의 개념이 설명되어 있다. ( 근데... 좀 어렵다..)

직관적으로 이해하자면 local minima도 아니면서 주변 모든 차원의 기울기가 0에 가까운 값이라서 더 이상 업데이트가 진행되지 않는 (갇히는) 상황이라고 볼 수 있겠다.

 

 

 

 

---

이제 본격적으로 새로운 기법들을 도입해 gradient를 최적화하는 다양한 Optimizer를 살펴보도록 하겠다.

 

Momentum

Saddle point에 갇히는 것을 막고, 안정적인 수렴을 가능하게 하자!

SGD는 비등방성 함수에서 최적화에 어려움을 겪는다.

비등방성 함수는 방향에 따라 기울기가 달라지는 함수로, 해당 함수에서 최적화를 진행할 때 1차 미분인 기울기만 사용했을 때에는 최적점에 안정적으로 도달하기 힘들고 2차 미분인 곡률을 사용해야 최적의 경로로 수렴이 가능하다. ^[각주:10]

[각주:11]">

수렴과정에서 SGD의 비효율적 움직임 ^[각주:12]

 

SGD를 minima 방향으로 가속하고 진동을 감쇠시켜 문제를 해결하고자 SGD에 Momentum 항을 추가했다.

Momentum 항은 과거 time step의 update vector 일부분을 현재 업데이트 벡터에 추가하는 것이다.

즉, 이름 그대로 현실 세계의 '관성' 역할을 하는 것이다. 

Momentum update

 

• \(v_t\) : 파라미터 업데이트를 할 gradient vector
• \(\gamma\) : 과거 time step의 update vector를 얼마나 적용할 지 조정하는 하이퍼파라미터. 보통 0.9 정도의 값을 사용한다

새로이 추가된 momentum 항으로 인해 gradient가 같은 방향을 가리키는 차원에서는 업데이트 속도가 증가하고, gradient가 다른 방향을 가리키는 차원 (방향이 바뀌는 지점) 에서는 업데이트 속도가 감소한다.

 

[각주:13]">

기존 SGD VS 모멘텀 항 추가 후 SGD ^[각주:14]

 

해당 그림을 통해 (특히 비등방성 함수에서) Momentum이 추가된 SGD가 보다 안정적으로 수렴하는 모습을 볼 수 있다.

 

 

Nesterov Accelerated Gradient (NAG)

가까운 미래 위치를 예측해 보다 안정적 수렴이 가능하도록 하자!

이전에 gradient descent 방식을 설명할 때 언덕에서 굴러 내려가 최적점에 도달하는 공으로 비유하여 설명했었다. 더욱이 Momentum이 추가된 GD 방식은 관성이 적용된 현실의 공에 빗댈 수 있겠다.

그러나 우리는 이런 현실의 공보다 똑똑한 공을 만들어내고 싶다!

관성이 붙어서 최적점을 지나 새로운 slope를 올라가버리기 전에 스스로 속도를 늦춰주는 똑똑한 공을 만들어보자.

그러기 위해 현재의 파라미터 \(\theta\) 에 대한 gradient만 보는 것이 아니라 가까운 미래의 위치에 대한 gradient를 계산하여 효과적으로 앞을 내다보도록 한다.

 

그렇다면 가까운 미래 위치의 gradient는 어떻게 계산해야 할까?

기존에 Momentum 항으로 사용되던 \(\gamma v_{t-1}\) 를 이용해서 \(\theta - \gamma v_{t-1}\)  (Lookahead gradient) 를 계산하면 파라미터의 다음 위치를 계산할 수 있을 것이다.

1. 기존 모멘텀처럼 이전 누적 gradient에 따라 "jump"를 진행한다

2. 그런 다음 끝나는 지점의 gradient를 측정하고 "correction"을 진행한다.

 

이를 그림으로 나타내면 아래와 같다.

[각주:15]">

NAG gradient 계산^[각주:16]

• 파란색 화살표는 기존의 Momentum 기법
• 갈색 화살표는 기존 Momentum처럼 이전 누적 gradient에 따라 진행되는 과정
• 빨간색 화살표는 미래 위치 gradient를 계산 후 수정하는 과정
• 녹색 화살표는 NAG의 진행 방향

 

이를 수식으로 나타내면 다음과 같다.

NAG update

Momentum의 수식과는 목적함수 항만 달라진 것을 볼 수 있는데, \(\theta\) 에 대한 계산이 아니라 \(\theta - \gamma v_{t-1}\) 를 이용해 다음 위치를 예측하는 것을 볼 수 있다.

너무 빠른 (어쩌면 minima를 지나칠 정도의) 학습을 조정해 local minima에서 잘 수렴하지 못한다는 momentum의 문제점을 해결했다.

특히 RNN에 적용되었을 때 여러 태스크에서 의미 있는 성능 향상을 보였다고 한다.

 

 

Adagrad

파라미터마다 학습 속도를 다르게 하고 싶어!

이에 더해서 파라미터의 학습률도 개별적으로 조정하고 싶어서 나온 것이 바로 이 Adagrad이다.

드물게 업데이트되는 파라미터는 학습률을 크게 해서 더 큰 업데이트를 수행하고,

자주 업데이트되는 파라미터는 학습률을 작게 해서 더 작은 업데이트를 수행하는 것이다.

 

이전에는 모든 파라미터 \(\theta_i\)가 동일한 학습률 \(\eta\)를 사용했기 때문에 모든 파라미터를 한 번에 업데이트했는데, Adagrad에서는 각 timestep t에서 파라미터마다 다른 학습률을 사용한다.

Adagrad gradient - 1

• \(g_{t,i}\) : timestep t에서 파라미터 \(\theta_i\) 에 대한 목적 함수 gradient

 

이제 각 파라미터에서 학습률이 수정되는 과정을 알아보자.

비교를 위해 먼저 SGD에서각 파라미터 \(\theta_i\) 에 대한  업데이트를 살펴보겠다.

SGD gradient

Adagrad는 이전 gradients에 따라서 learning rate \(eta\)를 조정한다.

따라서 SGD에서 general learning rate로 쓰인 \(eta\) 를 다음과 같은 항으로 대체한다.

Adagrad gradient - 2

• \(G_{t, ii}\) : timestep t까지의 gradient 제곱합인 diagonal element i,i 를 가지는 대각행렬 = 과거 t번째 timestep까지의 누적 gradaient
• \(\epsilon\) : 분모가 0이 되는 것을 막기 위한 평활화 항 (1e-8)

분모의 제곱근 연산이 없어지면 알고리즘의 성능이 훨씬 나빠진다고 한다. (본 논문에는 이에 대한 근거가 서술되어 있지 않다.)

 

이를 벡터로 만들면 다음과 같은 수식이 완성된다.

Adagrad gradient - 3

 

학습 속도를 수동으로 조정할 필요가 없다는 장점이 있다. (분자에 있는 \(\eta\) 는 보통 기본값인 0.01을 그대로 둔다)

그러나 치명적인 단점도 존재하는데, 분모에 gradient의 제곱합을 사용한다는 것이다.

추가되는 모든 항이 양수이기에 훈련하는 동안 누적합이 계속 증가하고, 이로 인해 학습 속도가 점차 줄다가 0에 가까워지며 더 이상 학습을 할 수 없게 되는 것이다.

 

 

Adadelta

Adagrad에서 여러 timestep이 지난 후 학습률이 0이 되는 문제를 해결하자!

Adadelta는 기본적으로 Adagrad와 비슷하지만 과거의 모든 gradient 제곱합을 누적하는 대신 고정된 크기 w만큼의 과거 gradient만 누적하고, 단순 제곱합 대신 평균을 이용한다.

•  \(E[g]^2_t\) : timestep t에서의 평균값. momentum * 이전 평균과 현재 기울기에만 의존한다.
• \(\gamma\) : momentum에서와 같이 이전 gradient를 얼마나 반영할 지 조정하는 하이퍼파라미터. 동일하게 기본값은 0.9이다.

 

비교를 위해 이전 Adagrad의 파라미터 업데이트 벡터를 다시 살펴보자.

Adagrad update vector

여기서 분모 항에 사용된 대각행렬 \(G_t\)를 앞서 계산한 평균값으로 대체한다.

Adadelta update vector

분모는 gradient의 RMS (root mean squared) 이므로 치환하면 수식을 간단히 할 수 있다.

Adadelta update vector

논문에서 저자는 SGD, Momentum, Adagrad 모두 가중치의 업데이트 단위(unit) 가 일치하지 않는다는 문제점이 존재한다는 것을 지적했다.

따라서 Adadelta에서는 분자에서도 동일한 units 로 계산하기 위해 파라미터 업데이트의 제곱 평균을 정의한다.

이에 대한 설명은 참고 블로그^[각주:17] , Adadelta 원본 논문에 자세히 서술되어 있다.

이 때 \(RMS[\Delta \theta]_t\)는 정확하게 알 수 없으므로 이전 timestep 까지의 파라미터 업데이트 RMS로 근사치를 구한다. 

general learning rate인 \(\eta\)를 위에서 구한 RMS 수식으로 대체하면 최종적으로 Adadelta의 업데이트 규칙이 완성된다.

 

Adagrad와 다르게 \(\eta\)가 수식에서 완전히 사라졌기 때문에 default learning rate를 정할 필요조차 없다.

 

 

 

RMSprop

RMSprop은 정식으로 publish된 논문은 아니고 G.Hinton의 수업에서 '이렇게 해봤더니 잘되더라' 하며 공개된 방식이다.

기본적으로는 Adadelta와 비슷하다.

 

• decay rate \(\gamma\) = 0.9로 설정
• 분자를 RMS로 계산하지 않고 global learning rate = 0.001로 유지

 

 

 

Adaptive Moment Estimation (Adam)

Adaptive Learning + Momentum

Adadelta, RMSprop처럼 이전 squred gradient의 평균을 사용한 것에 더해 Momentum과 유사하게 과거 \(gradient m_t\)의 평균도 저장한다.

• \(m_t\) : first moment (평균) 의 추정치
• \(v_t\) : second moment (분산) 의 추정치

이 때 \(m_t\) 와 \(v_t\)는 zero vector로 초기화되므로 초기 timestep에서 (그중에서도 감쇠율인 \(beta_1, beta_2\)가 1에 가까울 때) 0에 편향되어 있음을 볼 수 있었다.

이를 보정하기 위해 다음 수식을 적용한다.

 

biased estimator vs unbiased estimator

• biased estimator : 파라미터 추정 평균에 대해 bias 값이 0이 아닌 경우 → bias 값이 크다면 추정된 파라미터가 실제 파라미터와는 상당히 멀리 떨어져있음을 나타냄
• unbiased estimator : 파라미터 추정 평균에 대해 bias 값이 0인 경우

따라서 편향을 보정해 unbiased estimator에 가깝게 만들고자 하는 것이라 볼 수 있다.

 

Adam의 최종 업데이트 수식은 다음과 같다.

 

NAdam

NAG와 Adam을 합쳐보자!

Adam이 RMSprop + Momentum 이라면, NAdam은 거기에 NAG 기법까지 더해본 것이다.

NAG의 파라미터 업데이트 수식을 다시 한 번 살펴보자.

 

NAG는 현재 위치인 \(\theta_t\)에서 현재의 Momentum만큼 이동한 자리에서 기울기를 구했고, 이를 더해줘서 현재의 Momentum을 갱신했다.

NAdam에서는 momentum step을 두 번 진행하는 대신 lookahead momentum vector를 직접 적용해서 현재 파라미터를 업데이트 한다.

\(m_{t-1}\) 부분이 \(m_t\)로 바뀐 것을 볼 수 있다.

 

이를 Adam 업데이트 규칙에 적용하면 다음과 같은 업데이트 규칙이 완성된다.

 

 

 

Which optimizer to use?

그래서 어떤 Optimizer를 사용해야 할까?

딥러닝의 모든 태스크가 그러하듯... 데이터 바이 데이터, 태스크 바이 태스크이다.

본 논문에서는 전반적인 흐름에 대해서만 언급한다.

• 데이터가 sparse한 경우 adaptive learning 기법 중 하나를 택한다. 파라미터마다 학습률을 다르게 할 수 있기 때문이다.
• Adam이 보편적으로 좋은 선택일 수 있다
• 흥미롭게도 최근 논문 중 일부는 momentum이나 LR scheduling이 적용되지 않은 Vanila SGD를 사용한 경우도 있다. 일반적으로 non-convex, convex function에서의 최적값을 찾을 수 있기 때문이다.
• 그러나 local minima가 아닌 saddle point에 멈출 수 있고 다른 최적화 기법에 비해 시간이 훨씬 오래 걸리므로 빠른 수렴이 중요한 경우나 복잡한 신경망을 훈련하는 경우에는 Adaptive learning 기법들을 추천한다. 

 

 

 

Additional strategies for optimizing SGD

Shuffling or Curriculum Learning

일반적으로 모델에 의미 있는 순서로 sample을 넣는 것은 잘못된 방향으로 학습을 유도할 수 있다. 따라서 매 epoch 마다 학습 데이터를 shuffle 하는 것을 권장한다.

그러나 몇몇 케이스에서는 sample을 의미 있는 순서로 제공했을 때 오히려 성능이 향상되는 것을 확인할 수 있었다. 이렇게 의미 있는 순서를 설정하는 방법을 curriculum learning이라고 한다.^{[각주:18] [각주:19]}

 

Batch normalization

학습을 용이하게 하기 위해 학습 시작 전 파라미터의 평균과 분산이 0이 되도록 초기화한다. 그러나 학습이 진행되고 파라미터가 업데이트되며 정규화가 손실되어 학습 속도가 느려지게 된다.

batch normalization은 mini-batch마다 재정규화를 진행하고 변경 사항을 역전파시킨다. 이를 통해 더 높은 learning rate 사용이 가능해지며 파라미터의 초기값 의존도가 낮아진다. 또한 규제의 역할도 수행하여 dropout의 필요성을 줄인다는 추가적 이점도 존재한다.

 

Early stopping

익히 알고 있는 그 기법

validation set의 loss를 monitoring하다가 일정 수준 이하로 줄어들지 않는 지점에서 학습을 중단해 overfitting을 방지한다.

 

Gradient noise

각 gradient 업데이트에 가우시안 분포를 따르는 노이즈를 추가하는 기법이다.

add gradient noise

해당 논문에서는 노이즈를 추가할 때 초기화 상태가 좋지 않은 네트워크가 더 견고해지며, 특히 깊고 복잡한 네트워크를 훈련하는 데 도움이 된다고 주장한다.

성능 향상의 이유는 노이즈가 추가될 때 새로운 local minima를 찾아낼 수 있는 기회가 더 많아지기 때문이라고 추정하고 있다. 

 

 

 

---

참고 문헌

https://arxiv.org/abs/1609.04747

An overview of gradient descent optimization algorithms

 

1. https://imgur.com/a/Hqolp [본문으로]
2. https://imgur.com/a/Hqolp [본문으로]
3. https://medium.com/analytics-vidhya/journey-of-gradient-descent-from-local-to-global-c851eba3d367 [본문으로]
4. https://medium.com/analytics-vidhya/journey-of-gradient-descent-from-local-to-global-c851eba3d367 [본문으로]
5. Dauphin, Yann N., et al. "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization." Advances in neural information processing systems 27 (2014). [본문으로]
6. https://medium.com/analytics-vidhya/journey-of-gradient-descent-from-local-to-global-c851eba3d367 [본문으로]
7. https://medium.com/analytics-vidhya/journey-of-gradient-descent-from-local-to-global-c851eba3d367 [본문으로]
8. https://ko.wikipedia.org/wiki/%EC%95%88%EC%9E%A5%EC%A0%90 [본문으로]
9. https://ko.wikipedia.org/wiki/%EC%95%88%EC%9E%A5%EC%A0%90 [본문으로]
10. https://velog.io/@cha-suyeon/DL-%EC%B5%9C%EC%A0%81%ED%99%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 [본문으로]
11. https://blog.naver.com/PostView.naver?blogId=cni1577&logNo=221808882801&categoryNo=57&parentCategoryNo=0 [본문으로]
12. https://blog.naver.com/PostView.naver?blogId=cni1577&logNo=221808882801&categoryNo=57&parentCategoryNo=0 [본문으로]
13. https://willamette.edu/~gorr/classes/cs449/momrate.html [본문으로]
14. https://willamette.edu/~gorr/classes/cs449/momrate.html [본문으로]
15. G. Hinton's lecture 6c [본문으로]
16. G. Hinton's lecture 6c [본문으로]
17. https://medium.com/konvergen/continuing-on-adaptive-method-adadelta-and-rmsprop-1ff2c6029133 [본문으로]
18. Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning.
    Proceedings of the 26th annual international conference on machine learning, pages 41–48,
    2009. [본문으로]
19. Wojciech Zaremba and Ilya Sutskever. Learning to Execute. pages 1–25, 2014. [본문으로]