2016년 학회는 아닌 아카이브에 등재된 논문이며, 인용 횟수가 꽤 높은 Gradient Descent Optimaization Algorithms 논문입니다. 전반적인 GD Optimization Algorithm 들에 대해 정리가 잘 되어 있는 논문이며, 알고리즘들의 동작 원리와 사용 이유, 차이점에 대해 이해하기 위한 논문 리뷰입니다. 이 논문 내의 기능들은 대부분 PyTorch 내에 구현되어 있기 때문에 사용은 어렵지 않습니다. 애초에 알고리즘들을 정리하는 논문이기 때문에 원본 논문의 내용을 살리되 논문 내용 뿐 아니라 추가적으로 이해에 도움이 되는 외부 자료나 gif 등을 추가하면서 정리하도록 하겠습니다.
An overview of gradient descent optimization algorithms
Abstract
이 논문은 독자들에게 Gradient descent optimization algorithms 에 대한 통찰력과 직관을 제공하는 것을 목표로 둡니다. Optimization algorithms 에 대한 이해도가 높아지면 설계한 모델에 대해 적합한 알고리즘을 선택할 수 있습니다. 이해도를 높이기 위해 gradient descent의 3가지 분류를 살펴보고, 해결해야 할 문제점을 제시하고 이 문제점을 해결하기 위해 제시된 8가지 algorithms(Adam, RMSprop, Adagad 등등)를 소개합니다.
1. Introduction
Gradient Descent(GD) 는 최적화를 수행하는 가장 유명한 알고리즘 중 하나이며, 신경망을 최적화 시키는 가장 일반적인 방법입니다. 현재까지 나온 모든 SOTA 딥러닝 라이브러리는 GD를 최적화하기 위한 다양한 알고리즘 구현이 포함되어 있습니다. 그러나 이런 알고리즘들은 Black-box optimizer 로 주로 사용되기 때문에, 이에 대한 장단점을 설명하기가 어렵습니다.
본 논문은 독자들에게 GD optimizing (경사 하강 최적화)를 위한 다양한 알고리즘의 동작과 관련된 직관을 제공하여 사용에 도움이 되는 것을 목표로 합니다. 2절에서 먼저 경사 하강의 다양한 변형을 살펴보고 그를 간단히 요약합니다. 3절에서는 학습과정 중 발생하는 문제점에 대해, 4절에서는 이를 해결해가는 가장 일반적인 최적화 알고리즘들을 소개합니다. 이후 5절에서는 parallel, distributed setting 에서(병렬, 분산 환경에서) GD를 최적화 하기 위한 알고리즘과 아키텍처에 대해 다룹니다. 마지막으로 6절에서는 GD를 최적화 하는데 도움이 되는 추가적인 전략에 대해 다룹니다.
GD 는 모델의 파라미터 $\theta \in \mathbb{R}^d$ 에 의해 매개변수화된 목적 함수(objective function) $J(\theta)$ 를 목적함수의 그레디언트 $\nabla_\theta J(\theta)$의 반대 방향으로 업데이트 하는 방법입니다. 학습률 $\eta$ 는 (Local)최솟값에 도달하기 위한 단계의 크기(size of steps) 를 결정합니다.
[DL] 경사 하강법 ( Gradient Descent )
기계학습 문제는 학습의 목표가 최적의 매개변수를 찾는 것이고, 이는 곧 손실 함수가 최솟값이 될 때의 매개변수를 찾는 것과 동일합니다. 이 때 기울기를 사용해서 함수의 최솟값을 찾는 아이
songsite123.tistory.com
2. Gradient descent variants
GD에는 3가지의 구분이 있는데, 이는 우리가 목적함수의 그레디언트를 계산(한 번의 업데이트에) 하기 위해 얼마나 많은 데이터를 사용하는지 에 따라 구분됩니다. 데이터의 양에 따라 매개변수 업데이트의 정확도와 학습 시간에는 trade-off 가 존재합니다.
2.1 Batch gradient descent
Batch gradient descent 라고도 불리는 Vanilla gradient descent 는 전체 Training dataset으로 매개 변수에 대한 비용 함수의 기울기를 계산합니다.
$$ \theta = \theta - \eta \cdot \nabla_\theta J(\theta) $$
$\theta$ 는 파라미터, $\eta$는 학습률, $\nabla$는 그레디언트를 의미합니다. 단 한 번의 가중치(\theta) 업데이트를 위해 전체 데이터 세트에 대한 그레디언트를 계산해야 합니다. 따라서 매우 느리게 동작하며, 메모리에 알맞은 크기가 아니라면 사용할 수 없습니다. 또한 새로운 이미지에 일시적으로만 접근이 가능한 온라인(online) 상황에서는 사용할 수 없습니다.
코드 상으로 Batch Gradient Descent는 아래와 같이 구현됩니다.
for i in range(nb_epochs):
params_grad = evaluate_gradient(loss_function, data, params)
params = params - learning_rate * params_grad미리 정의된 epoch의 수 nb_epochs 에 대해, 전체 데이터 집합에 대한 손실 함수의 기울기 벡터 params_grad 를 먼저 계산합니다. 그 후 학습률과 그레디언트의 곱으로 매개변수를 업데이트 합니다. Batch GD 는 볼록한(convex)한 경우, 전역으로 수렴되는 것이 보장되어 있습니다. [원문 : Batch gradient descent is guaranteed to converge to the global minimum for convex error surfaces and to a local minimum for non-convex surfaces.]
즉 정리해보면 배치 GD는 전체 데이터세트를 그레디언트를 계산하여 한 번에 매개변수를 갱신하는 방법이며, 이로 인해
- 매우 느리고
- 메모리에 적합하도록 dataset을 다루기 어렵다
- non-convex surface 에서는 local minimum에 빠지면 벗어나기 어렵다.
- 전체 dataset으로 기울기를 구하는 과정에 불필요한 연산이 많다.
2.2 Stochastic gradient descent
SGD는 각 Training example 에 대해 매개변수를 갱신합니다.
$$ \theta = \theta - \eta \cdot \nabla_\theta J(\theta ; x^{(i)}; y^{(i)}) $$
한 번의 가중치(\theta) 업데이트를 위해 단 하나의 학습 데이터에 대한 기울기를 계산합니다. SGD는 한 번에 하나의 업데이트가 수행되기 때문에 중복성이 제거되어 빠른 속도를 가지고, 온라인 상황에서도 사용할 수 있습니다. 하지만 기울기가 높은 분산(High variance)을 가져 손실 값이 크게 변동하는(fluctuating) 단점이 있습니다.
크게 변동한다는 것은 2가지 의미를 가집니다. 첫 번째는 요동치며 오버슈팅하는 경향이 있으나, local minimum에 빠졌을 때 큰 변동으로 이를 빠져나오고 새로운 local minimum 을 찾을 수 있다는 것을 의미합니다. 두 번째는 크게 변동하므로 정확한 값에 수렴하기 어렵다는 것을 의미합니다. 하지만 이는 learning rate를 천천히 낮춰주며 수렴하도록 할 수 있습니다.
코드 상으로 반복문을 추가하는 것으로 기울기를 평가합니다. 이 때 6.1절에서 설명하는 내용으로 매 epoch마다 훈련 데이터를 셔플합니다.
for i in range(nb_epochs):
np.random.shuffle(data)
for example in data:
params_grad = evaluate_gradient(loss_function, example, params)
params = params - learning_rate * params_grad
( 원래 SGD 라고 알고 있던 것은 SGD가 아닌 2-3 Mini-batch gradient descent 이다. 명확한 정의는 SGD는 한 개의 데이터, Mini-batch는 적당한 크기의 데이터 묶음을 사용. )
2.3 Mini-batch gradient descent
미니 배치 GD 는 양 쪽의 장점을 최대한 활용하고, 우리가 평소 일반적으로 말하던 SGD를 의미합니다. 이름 그대로 n 개의 Training examples 로 묶인 Mini-batch 에 대해 기울기를 계산하고 매개변수를 갱신합니다.
$$ \theta = \theta - \eta \cdot \nabla_\theta J(\theta ; x^{(i:i+n)}; y^{(i:i+n)}) $$
파라미터 업데이트의 분산을 줄일 수 있기 때문에, 더욱 안정된 수렴을 유도합니다. 현대의 딥러닝 라이브러리는 행렬 연산에 최적화되어 mini-batch 에 대한 기울기를 매우 빠르게 계산합니다. 일반적인 미니 배치 크기의 범위는 50 ~ 256 이지만 응용 프로그램마다 다를 수 있습니다. (통상적으로 16 ~ 512 의 미니 배치 크기 사용). 신경망을 학습할 때 가장 일반적으로 선택되는 알고리즘이며, SGD라는 용어는 미니 배치가 사용되는 경우에도 사용됩니다.
for i in range(nb_epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size = 50):
params_grad = evaluate_gradient(loss_function, batch, params)
params = params - learning_rate * params_grad
3. Challenges
위에서 알아본 경사 하강법은 좋은 수렴을 보장하지 않습니다. 따라서 해결해야 할 몇 가지 문제를 소개합니다.
- 적절한 Learning rate 를 선택하는 것이 어려울 수 있습니다. lr 이 너무 작으면 너무 느리게 수렴되고 lr이 너무 크면 수렴이 어려워지고 최솟값 근처에서 변동하거나 심지어 벗어날 수도 있습니다.
- Learning rate schedule 을 사용해 학습 도중 learning rate 를 조정할 수 있습니다. 사전 정의된 스케줄러에 따라 lr을 감소시키거나, 매 epoch마다 loss 가 임계값 아래로 떨어지면 lr를 감소시키는 방법이 있습니다. 그러나 이 두 방법은 사전에 정의되어야 하며, dataset의 특성에 적용될 수 없습니다.
- 또한 동일한 lr이 모든 매개 변수 업데이트에 적용됩니다. 만약 데이터가 sparse 하고 features 가 매우 다른 빈도수를 가지고 있으면, 이 모든 것들을 동일한 정도로 갱신하면 안됩니다. 드물게 발생하는 특징에 대해서는 더 큰 갱신을 수행해야 합니다.
- 단순히 SGD를 사용하면 최적이 아닌 local minima와 안장점(saddle point)에 빠질 위험이 있습니다. 안장점이 최솟값이 아니더라도 0의 기울기를 지니고 있으면, 매개변수는 갱신되지 않습니다.
4. Gradient descent optimization algorithms
위에 언급한 문제들을 처리하기 위해 딥러닝 커뮤니티에서 널리 사용하는 몇 가지 알고리즘을 소개합니다. 이 때 고차원 데이터 세트에 대해 실제로 계산할 수 없는 알고리즘에 대해서는 논의하지 않습니다.
4.1 Momentum
SGD는 기울기가 높은 평면에서 최적값을 향해 잘 찾아가지 못합니다. 아래 그림처럼 경사도의 기울기를 따라 왔다갔다 하는 것을 확인할 수 있습니다.
Momentum 은 SGD를 관련 방향(relevant direction)으로 가속하고 진동을 완화시키는데 도움이 되는 방법입니다. 이는 과거 시간 단계의 업데이트 벡터에 상수 $\gamma$ 를 곱한 값을 현재 업데이트 벡터에 추가하여 수행합니다.
$$ \begin{align*} & v_t = \gamma v_{t-1} + \eta \nabla_{\theta} J(\theta) \\ & \theta = \theta - v_t \end{align*}$$
이 때 $\gamma v_{t-1}$ 이 Momentum term 이 됩니다. SGD 수식에서 모멘텀 항을 추가적으로 빼주는 것을 확인할 수 있습니다. 이 변수는 내리막길에서는 가속하도록 도와주고, 방향이 바뀌었을 때 파라미터가 갱신하는 양을 감소시킵니다.
물리적인 관성을 생각하면 이해하기 더 편합니다. momentum 을 사용한다는 것은 공을 언덕에서 굴리는 것과 같습니다. 수식에 모멘트를 추가하여 이전에 이동하던 방향과 크기를 현재 갱신 값에 영향을 주도록 한 것이고, 이 덕분에 이동하는 방향으로 계속 이동하려는 관성이 추가됩니다. 빠르게 이동하는 자동차가 갑자기 방향을 바꾸기 어렵듯, SGD에 관성을 추가하여 갑자기 방향을 바꾸기 어렵게 하고, 이전과 동일한 방향으로 나아갈 때는 가속이 작용되도록 합니다.
장점을 가장 이해하기 쉬운 부분으로, Local mininum 에서는 Gradient 가 0이지만, 이전의 모멘텀 때문에 Local minimum에 빠지지 않고 계속 이동합니다.
4.2 Nesterov accelerated gradient
Momentum 은 단순히 경사(slope)를 따라서 언덕을 타고 내려갑니다. 이는 결과적으로 과도하게 이동하여 좋지 않은 위치에 도달할 수 있습니다. 이를 해결하기 위해 네스테로프 가속 그레디언트 (Nesterov accelerated gradient, NAG) 를 사용합니다. NAG는 멈춰야할 시기에 더 나아가지 않고 제동을 거는 방법입니다. NAG는 비용 함수의 기울기를 계산할 때, 매개변수에 이전 모멘텀을 빼주어($\theta - \gamma v_{t-1})$ 다음 위치를 근사화하여 비용함수의 기울기를 계산합니다. 같은 말로 이전에 계산된 모멘텀 항에서 다음 매개변수의 위치를 예측합니다.
$$ \begin{align*} & v_t = \gamma v_{t-1} + \eta \nabla_{\theta} J(\theta -\gamma v_{t-1}) \\ & \theta = \theta - v_t \end{align*}$$
이를 조금 더 쉽게 이해해보자면 NAG는 momentum 방향으로 미리 가보는 방법[next position approximation]
을 사용한다고도 할 수 있습니다. 해당 방향으로 미리 가본 뒤에, 교정[correction] 하는 것으로 이해할 수 있습니다.
$\gamma$ 를 약 $0.9$ 정도의 값으로 설정한다고 가정합니다. 모멘텀은 먼저 현재 그레디언트 (작은 파란색 벡터)를 계산하고 업데이트 된 누적 그레디언트(큰 파란색 벡터) 방향으로 크게 점프하는 반면 NAG는 먼저 이전 누적 그레디언트 방향으로 크게 점프(갈색 벡터)합니다. 그레디언트를 측정한 다음 보정(빨간색 벡터)을 수행하여 전체 NAG 업데이트(녹색 벡터)를 얻습니다.
즉 Momentum 은 현재 기울기를 계산하고 모멘텀을 적용시켜 그 방향으로 크게 이동합니다. NAG는 Momentum 위치에서 다음 위치를 예측하여 파라미터를 갱신합니다. NAG는 모멘텀에 비해 상대적으로 느린 속도로 값이 갱신되고, 너무 빠르게 기울기가 수정되는 것을 방지할 수 있습니다.
NAG는 우리가 너무 빨리 지나가는 것(기울기의 급격한 변화)을 방지하고 응답성을 향상시켜 여러 작업에서 RNN의 성능을 크게 향상시킵니다.
4.3 Adagrad
Adagrad 는 학습 속도를 매개 변수에 맞게 조정하여 자주 등장하는 매개 변수에 대한 업데이트 빈도를 낮추고 업데이트 횟수를 줄입니다. 이런 특징 때문에 sparse 데이터에 유리합니다. 즉 Adagrad 는 각 파라미터 마다 learning rate 를 다르게 적용하는 방법을 뜻합니다.
빈도수가 높은 파라미터는 작은 업데이트(smaller update), 빈도수가 낮은 파라미터는 큰 업데이트(larger update) 를 수행합니다. Adagrad 는 SGD의 견고성을 크게 향상시켜 대규모 신경망을 훈련 시키는데에도 적합합니다.
이전까지는 모든 매개변수 $\theta_i$ 가 동일한 학습률 $\eta$를 사용하기 때문에 모든 매개변수 $\theta$에 대한 업데이트를 한 번 수행했습니다. Adagrad는 매 단계의 $t$마다 모든 매개변수 $\theta_i$에 대해 다른 학습률을 적용하므로 Adagrad의 매개변수 별 업데이트를 먼저 수행한 다음 벡터화합니다.
$$ g_{t, i} = \nabla_{\theta_{t}} J(\theta_{t, i}) $$
$g_{t, i}$ 는 시간 단계 $t$에서의 파라미터 $\theta_i$에 대한 목적 함수의 기울기입니다. 각 시간 단계 $t$에서 모든 매개변수 $\theta_i$에 대한 SGD 업데이트는 다음과 같습니다.
$$ \theta_{t+1, i} = \theta_{t, i} - \eta \cdot g_{t, i} $$
업데이트 규칙에서, Adagrad는 $\theta_i$에 대해 이전에 계산된 기울기를 기반으로 모든 매개변수 $\theta_i$에 대한 각 시간 단계 $t$에서 일반적인 학습률 $\eta$를 수정합니다.
$$ \theta_{t+1, i} = \theta_{t, i} - \dfrac{\eta}{\sqrt{G_{t, ii}+\epsilon}} $$
$G_{t} \in \mathbb{R}^{d\times d}$ 인 대각행렬로 여기에서 각 원소 $G_{t, ii}$ 가 의미하는 것은 $t$시점 까지의 대각요소들을 의미하며, 이는 곧 그레디언트들의 누적 제곱합을 의미합니다. [원문 : $G_{t} \in \mathbb{R}^{d\times d}$ is a diagonal matrix where each diagonal element $i, i$ is the sum of the squares of the gradients.] $\epsilon$은 0으로 나누어주는 것을 방지하기 위한 아주 작은 숫자를 의미합니다.
이는 풀어 설명하면 $G_{t+1, ii} = G_{t, ii} + g_{t, i}^2 $ 과 같습니다. $G_t$를 통해 Learning rate decay 효과를 얻을 수 있습니다. 많이 변화한 파라미터 $g_{t, i}$ 는 $G_{t, ii}$ 값이 크기 때문에, 상대적으로 적게 업데이트가 이루어집니다.
$G_t$는 대각 행렬이고, 대각 요소가 모든 매개변수에 대한 비용 함수의 기울기의 제곱합으로 이루어져 있으므로, elementwise matrix vector multiplication ⊙ 를 이용하여 정리할 수 있습니다.
$$ \theta_{t+1} = \theta - \dfrac{\eta}{\sqrt {G_t + \epsilon}}⊙g_t $$
$G_t$는 $d\times d$ 차원, $g_t$ 는 $d$차원이므로 결과적으로 위 연산을 통해 $d$차원의 업데이트 벡터를 얻을 수 있습니다. Adagrad 의 장점은 학습률을 수동으로 조정할 필요가 없다는 것입니다. 초기 합습률을 0.01로 지정해주고 이를 그대로 두면 $G_t$가 자동으로 학습률을 조정해줍니다.
Adagrad 의 단점은 분모에 제곱된 기울기가 계속 축적된다는 것입니다. 모든 항이 양수라면 학습 동안 계속해서 값이 커지게 됩니다. 이는 학습률이 계속 줄어들고, 결과적으로 학습률이 매우 작은 값이 되어 알고리즘이 추가적인 정보를 얻지 못하고 따라서 업데이트가 잘 수행되지 않습니다. 다음의 Adadelta 알고리즘은 이 결함을 해결하는 것을 목표로 합니다.
4.4 Adadelta
Adadelta 는 단조롭게 감소하는 학습 속도를 줄이기 위한 Adagrad의 확장판입니다. Adagrad는 과거의 모든 기울기 ($1$부터 $t-1$까지)를 누적한 값을 갖고 있는 $G_t$를 사용합니다. Adadelta는 그를 대신하여 fixed size $w$의 크기를 갖는 window를 사용합니다.
이전의 제곱된 모든 그레디언트를 비효율적으로 저장하여 평균을 계산하지 않고, 이전에 제곱된 기울기의 이동 평균(running average, $E[g^2]_t$)을 이용하여 평균을 계산합니다. 가중 평균 $E[g^2]_t$ 는 $t$ 시점에서, 단지 이전까지의 평균과 현재 기울기만을 사용합니다.
$$ E[g^2]_t = \gamma E[g^2]_{t-1} + (1-\gamma)g_t^2 $$
$\gamma$는 모멘텀 항과 비슷한 $0.9$로 설정한다고 가정합니다. 이전 시점까지의 평균값의 0.9 비율과 갱신될 제곱된 기울기 0.1 비율을 더해주어 평균을 계산합니다.
Adadelta 에서는 매개변수의 변화량 $\Delta$을 이용하여 수식을 표현합니다. SGD에서의 수식을 매개변수 변화량으로 표기하면 다음과 같습니다.
$$ \begin{align*} & \Delta \theta_t = - \eta \cdot g_{t, i} \\ & \theta_{t+1} = \theta_t + \Delta \theta_t \end{align*} $$
이전에 파생 된 Adagrad의 매개변수 업데이터 벡터는 다음과 같은 형식을 취합니다.
$$ \Delta \theta_t = - \dfrac{\eta}{\sqrt {G_t + \epsilon}}⊙g_t $$
이동 평균을 이용하는 Adadelta 에서는 대각 행렬 $G_t$ 를 이동 평균으로 대체해줍니다.
$$ \Delta \theta_t = - \dfrac{\eta}{\sqrt {E[g^2]_t + \epsilon}}g_t $$
분모가 기울기의 root mean squared(RMS) 이므로, 다음과 같이 표현할 수 있습니다.
$$ \Delta \theta_t = - \dfrac{\eta}{RMS[g]_t}g_t $$
Adadelta 논문 저자는 SGD, Momentum, Adagrad, Adadelta 에서 이 업데이트가 일치하지 않는다는 문제점이 있다고 말합니다. 즉 업데이트의 매개 변수와 동일한 가상 단위가 있어야 합니다. 이를 해결하기 위해 또 다른 가중 평균을 정의합니다. 이번에는 제곱된 기울기가 아닌 제곱된 매개변수를 이용하여 갱신합니다.
$$ E[\Delta \theta^2]_t = \gamma E[\Delta \theta^2]_{t-1} + (1-\gamma ) \Delta \theta^2_t $$
따라서 매개변수의 root mean squared(RMS) 는 다음과 같이 정리됩니다.
$$ RMS[\Delta \theta]_t = \sqrt{E[\Delta \theta]_t + \epsilon} $$
최종적으로 매개변수의 변화량을 이용해 Adadelta 식을 정리하면 다음과 같습니다.
$$ \begin{align*} & \Delta \theta_t = - \dfrac{RMS [\Delta \theta]_{t-1}}{RMS[g]_t} g_t \\ & \theta_{t+1} = \theta _t + \Delta \theta_t \end{align*} $$
Adadelta 는 기본 학습률을 설정할 필요가 없습니다. 수식에서 학습률이 제거되었기 때문입니다.
수식이 길어졌기 때문에 Adadelta 다시 요약
Adagrad 의 문제점 : 과거의 모든 기울기를 누적하여 가지고 있는 $G_t$를 사용하기 때문에 불필요한 연산이 많고, 분모가 커져 업데이트가 안되는 문제점 발생 => Adadelta는 fixed size $w$를 가지고 있는 window, 즉 최근 $w$개의 기울기만을 사용한다. 하지만 이 때 실제로 $w$개를 저장하는 것이 아닌, running average 를 사용한다.
수식적으로는 $G_t$ 대신 running average $E[g^2]_t$ 를 사용한다.
$$ E[g^2]_t = \gamma E[g^2]_{t-1} + (1-\gamma)g_t^2 $$
이전까지의 이동 평균과 현재 기울기만을 사용해 현재의 이동평균을 갱신한다. 이는 풀어 써보면 재귀적으로 반복이 되며, 이로 인해 과거의 기울기(gradient)의 영향력이 감소한다.
$$ E[g^2]_t = (1-\gamma)g_t^2 + \gamma (1-\gamma)g_{t-1}^2\gamma^2(1-\gamma)g_{t-2}^2 +\gamma^3(1-\gamma)g_{t-3}^2 + \cdots $$
또한 Adadelta 공식에서는 분모 부분을 단순히 RMS 로 표현이 가능하다. 또한 Adadelta 는 추가적으로 다른 exponentially decaying average 를 제안한다. 이로 인해 squared gradients 가 아닌 squared parameter updates 의 평균 값을 정의해 사용한다. Learning rate 대신에 직전에 업데이트한 크기를 사용하여 최종적인 Adadelat 식이 나타난다. Learning rate 대신 직전 업데이트 크기를 대신 사용하기 때문에 기본 학습률을 설정할 필요가 없다.
4.5 RMSprop
RMSprop 은 따로 출판되지 않은(unpublished) 방법으로, Geoff Hinton 의 코세라 강의에서 제안된 방법입니다. RMSprop 와 Adadelta 는 Adagrad의 학습률이 소실되는 문제를 해결하기 위해 동시에 독자적으로 발전된 기법입니다. RMSprop는 실제로 Adadelta 의 첫 번째 업데이트 벡터와 동일합니다.
$$ \begin{align*} & E[g^2]_t = \gamma E[g^2]_{t-1} + (1-\gamma)g_t^2 \\ & \theta_{t+1} = \theta_t - \dfrac{\eta}{\sqrt{E[g^2]_t+\epsilon}g_t}\end{align*}$$
Hinton은 기본적으로 $\gamma = 0.9$, 학습률($\eta$) $ = 0.001$ 로 제안합니다.
4.6 Adam (Adaptive Moment Estimation)
Adam (Adaptive Moment Estimation) 각 매개변수에 대해 개별적인 학습률을 적용하는 또 다른 방법입니다. 직관적으로는 RMSprop 와 Momentum 을 합친 것으로 이해할 수 있습니다. Adadelta와 RMSprop과 같이 과거의 제곱된 기울기 $v_t$의 지수적으로 감소하는 가중 평균을 적용할 뿐 아니라, Momentum 과 비슷하게 과거의 기울기 $m_t$의 지수적으로 감소하는 가중 평균을 적용합니다.
- Momentum 과 유사하게 과거의 gradient의 exponentially decaying average를 유지
- RMSprop 과 유사하게 과거의 gradient의 제곱의 exponentially decaying average를 저장
$$ \begin{align*} & m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t \\ & v_t = \beta_2 v_{t-1} + (1-\beta_2 ) g_t^2 \end{align*} $$
$m_t$ 는 기울기의 1차 모멘트(평균)의 추정량이고 $v_t$는 2차 모멘트(분산)의 추정량입니다.
$m_t$와 $v_t$는 0으로 초기화 되기 때문에, 학습 초기나 decay rate가 매우 작을 때($\beta_1$, $\beta_2$가 1에 가까울 때) 이 값들이 계속 0으로 편향되어 있습니다(초반에는 0에 가까운 값이 계속 나온다는 뜻). 이를 해결하기 위해 바이어스가 수정된 1차 모멘트와 2차 모멘트의 추정값을 이용(Bias correction)합니다.
$$ \hat{m}_t = \dfrac{m_t}{1-\beta_1^t} \quad \quad \quad \hat{v}_t = \dfrac{v_t}{1-\beta_2^t} $$
위와 같이 수정함으로써 초기에 0으로 편향되어 있던 현상을 예방할 수 있습니다. 그 이후 Adadelta 및 RMSprop 에서와 마찬가지로 매개변수를 업데이트하여 Adam 업데이트 규칙을 생성합니다. ( = 위 수식을 매개변수 갱신에 사용)
$$ \theta_{t+1} = \theta_t - \dfrac{\eta}{\sqrt{\hat{v}_t} + \epsilon } \hat{m}_t $$
즉 $\hat{m}_t$는 momentum 역할을 수행하고, $\hat{v}_t$는 각각 파라미터에 서로 다른 학습률을 적용하는 역할을 합니다.
저자는 $\beta_1$에 대해 0.9, $\beta_2$에 대해 0.999, $\epsilon$에 대해 $10^{-8}$ 의 기본값을 사용합니다. 또한, Adam 은 다른 adaptive learning 알고리즘과 비교하여 다양한 상황에서 매우 실용적으로 잘 동작합니다.
4.7 AdaMax
Adam의 $v_t$는 과거의 기울기들의 $l_2$norm에 반비례(inverse proportion) 하여 증가합니다.
$$ v_t = \beta_2 v_{t-1} + (1-\beta_2) |g_t|^2 $$
$l_2$ norm 을 $l_p$ norm 으로 확장할 수 있습니다.
$$ v_t = \beta_2^p v_{t-1} + (1-\beta_2^p) |g_t|^p $$
$p$값이 커질수록 수치적으로 불안정해지므로, $l_1$ norm, $l_2$ norm 을 이용하는 것이 일반적입니다. 하지만 $p = \infty $ 인 경우 또한 $l_{\infty}$ norm 은 좀 더 안정적(stable)으로 수렴한다고 하고, 이를 채택합니다. Adam 과 혼동을 피하기 위해 $v_t$ 대신 $u_t$를 사용해 infinity norm-constrained $v_t$를 나타냅니다.
$$ \begin{align*} u_t &= \beta_2^{\infty} v_{t-1} + (1-\beta_2^{\infty}) |g_t|^{\infty} \\ &= \text{max}(\beta_2 \cdot v_{t-1}, |g_t|) \end{align*} $$
이처럼 $u_t$는 max 연산에 의존하므로 Adamax 라는 이름이 붙여졌습니다. 또한 max 연산이므로 $m_t$와 $v_t$가 0에 편향되지 않습니다. (Adam에서 Bias correction 을 통해 해결한 부분이 필요가 없음)
$\sqrt{\hat{v}_t} + \epsilon$을 $u_t$로 바꿈으로써 최종적으로 수식을 정리하면 다음과 같습니다.
$$ \theta_{t+1} = \theta_t - \dfrac{\eta}{u_t}\hat{m}_t $$
4.8 Nadam
지금까지 살펴본 optimization을 간단히 뒤짚어보면, Adam 은 RMSprop와 momentum 의 결합으로 볼 수 있습니다. RMSporp는 제곱된 기울기 $v_t$의 가중 평균을 이용했고, momentum 은 기울기 $m_t$의 가중 평균을 이용했습니다. 또한 NAG는 SGD보다 성능이 더 좋았습니다.
Nadam(Nesterov-accelerated Adaptive Moment Estimation)은 Adam 과 NAG를 결합한 것입니다. NAG를 Adam으로 통합시키기 위해 momentum 항인 $m_t$를 수정해야 합니다.
다시 momentum update rule 에 대해 확인해보겠습니다.
$$ \begin{align*} g_t &= \nabla_{\theta_t}J(\theta_t) \\ m_t &= \gamma m_{t-1} + \eta g_t \\ \theta_{t+1} &= \theta_t - m_t \end{align*} $$
$J$는 비용 함수, $\gamma$는 momentum decay term, $\eta$는 학습률입니다. 위의 3번째 식을 아래와 같이 표현할 수 있습니다.
$$ \theta_{t+1} = \theta_t - (\gamma m_{t-1} + \eta g_t ) $$
이 수식은 이전의 momentum vector 와 현재 기울기의 방향을 모두 고려합니다.
NAG는 그레디언트를 계산하기 이전에, 모멘텀 방향으로 매개변수를 업데이트 한 이후에 기울기를 계산합니다. 즉 기울기 계산 전 momentum을 매개변수에 빼주어 $g_t$를 계산하는데, 이로써 기울기 방향으로 더 정확하게 나아갈 수 있습니다. 따라서 NAG 처럼 그레디언트 $g_t$를 수정하면 됩니다.
$$ \begin{align*} g_t &= \nabla_{\theta_t}J(\theta_t-\gamma m_{t-1}) \\ m_t &= \gamma m_{t-1} + \eta g_t \\ \theta_{t+1} &= \theta_t - m_t \end{align*} $$
Dozat이 새로운 방법으로 NAG를 수정하는 것을 제안합니다. momentum step을 2번 적용(기울기 $g_t$를 갱신할 때, 매개변수 $\theta_{t+1}$을 갱신할 때)하는 것 대신, 현재 매개변수를 갱신하기 위해 직접적으로 현재의 momentum vector 를 이용합니다.
$$ \begin{align*} g_t &= \nabla_{\theta_t}J(\theta_t) \\ m_t &= \gamma m_{t-1} + \eta g_t \\ \theta_{t+1} &= \theta_t - (\gamma m_t + \eta g_t) \end{align*} $$
매개변수를 갱신할 때 $m_{t-1}$ 이 아닌 $m_t$ 를 사용합니다. 위 식을 통해 이전의 momentum 벡터가 아닌, 현재의 momentum를 사용할 수 있습니다. Adam에 위의 Nesterov momentum을 추가하기 위해서는 이전의 모멘텀 벡터를 위의 모멘텀 벡터로 대체해야 합니다.
Adam 의 update rule 을 다시 보면 아래와 같습니다.
$$ \begin{align*} m_t &= \beta_1 m_{t-1} + (1 - \beta_1) g_t \\ \hat{m}_t &= \dfrac{m_t}{1-\beta_1^t} \\ \theta_{t+1} &= \theta_t - \dfrac{\eta}{\sqrt{\hat{v}_t} + \epsilon } \hat{m}_t \end{align*} $$
$\hat{m}_t$와 $m_t$의 정의로, 마지막 수식을 확장하면 아래와 같습니다.
$$ \theta_{t+1} = \theta_t - \dfrac{\eta}{\sqrt{\hat{v}_t}+ \epsilon} \left( \dfrac{\beta_1 m_{t-1}}{1 - \beta_1^t} + \dfrac{(1-\beta_1)g_t}{1-\beta_1^t} \right) $$
$\dfrac{\beta_1 m_{t-1}}{1 - \beta_1^t}$ 는 이전 단계의 momentum 벡터의 바이어스 보정된 추정값 [bias-corrected estimate of the momentum vector of the previous time step] 입니다. 따라서 이를 $\hat{m}_{t-1}$ 로 대체할 수 있습니다.
$$ \theta_{t+1} = \theta_t - \dfrac{\eta}{\sqrt{\hat{v}_t}+ \epsilon} \left( \beta_1 \hat{m}_{t-1} + \dfrac{(1-\beta_1)g_t}{1-\beta_1^t} \right) $$
이 식은 위의 momentum update rule과 유사합니다. 이전 시간 단계의 바이어스 보정 추정치 벡터 $\hat{m}_{t-1}$을 현재의 momentum vector $\hat{m}_t$ 의 바이어스 보정 추정치로 단순히 대체함으로써 Nasterov momentum 을 추가할 수 있습니다. 즉, Adam에 Nesterov momentum을 적용시키기 위해 이전 momentum vector를 현재 momentum vector 로 바꿔주면 됩니다. 최종적으로 Nadam 식은 다음과 같이 정리됩니다.
$$ \theta_{t+1} = \theta_t - \dfrac{\eta}{\sqrt{\hat{v}_t}+ \epsilon} \left( \beta_1 \hat{m}_{t} + \dfrac{(1-\beta_1)g_t}{1-\beta_1^t} \right) $$
4.9 Visualization of algorithms
Adagrad, Adadelta, RMSprop 은 즉각적으로 옳은 방향으로 이동하여 빠르게 수렴합니다. Momentum, NAG는 초반에 경로를 벗어났지만, 결론적으로는 miminum에 도달하고 있습니다.
위 예시는 Saddle point에서의 동작을 확인합니다. 이는 SGD한테는 어려운 문제입니다. SGD는 끝내 saddle point 를 탈출하지 못합니다. Adagrad, Adadelta, RMSprop는 초반부터 빠르게 올바른 방향으로 이동하여 수렴합니다. Momentum, NAG는 초반에 saddle point 를 탈출하지 못하지만 결과적으로는 minimum에 도달하게 됩니다.
Conclusion
본 논문에서 3가지의 Gradient descent 구분에 대해 알아보았고, SGD를 최적화하기 위해 자주 사용되는 알고리즘 (SGD, Momentum, NAG, Adagrad, Adadelta, RMSprop, Adam, Adamax, Nadam) 에 대해 알아보았습니다. 이 논문에는 요약하지 않은 나머지 부분에서는 optimization 뿐 아니라 이를 향상시키는 또 다른 전략들 (shuffling, batch normalization, early stopping ..) 에 대해 전반적으로 짧게 소개합니다. 감사합니다.
Reference :
https://arxiv.org/pdf/1609.04747.pdf
https://en.wikipedia.org/wiki/Lp_space
https://github.com/ilguyi/optimizers.numpy
https://cs231n.github.io/neural-networks-3/
https://www.ruder.io/optimizing-gradient-descent/
http://www.denizyuret.com/2015/03/alec-radfords-animations-for.html
https://laptrinhx.com/momentum-rmsprop-and-adam-optimizer-2337787365/
https://www.ruder.io/content/images/2016/09/saddle_point_evaluation_optimizers.gif