Optimizers: SGD with Momentum, NAG, Adagrad, RMSProp, AdaDelta, and ADAM

Soraemon·2022년 7월 15일

AdaGrad Adadelta NAG Optimizer RMSProp SGD adam

Deep Learning

목록 보기

1/1

1. Introduction

1.1 Gradient Descent (GD)

최적의 예측 모델을 만들기 위해서는 실제값과 예측값의 error를 나타내는 cost function $J(\theta)$ 가 최소가 되어야 한다. Cost function을 최소화시키는 최적의 파라미터를 찾기 위해 여러 Optimizer가 고안되고 있으며, 가장 기본적인 방법은 Gradient Descent(GD)이다. GD는 cost function의 기울기(gradient) 반대 방향으로 정해진 step size(learning rate) $\alpha$ 만큼 이동하여 cost function이 최소가 되도록 파라미터를 조정해 나간다. 다시 말해, gradient는 어느 방향으로 학습할지를 결정하고 learning rate는 한 번에 얼마나 학습할지를 결정한다. 여기서 learning rate $\alpha$ 는 hyper파라미터로 $0$ ~ $1$ 사이의 값을 가지며 보통 $0.01$ ~ $0.001$ 정도의 크기를 사용한다. 값이 너무 크면 발산, 너무 작으면 파라미터가 거의 업데이트 되지 않아 학습 시간이 오래 걸린다. 한 iteration에서의 파라미터 업데이트 식은 다음과 같다.

\theta = \theta - \alpha \,{\nabla _\theta }J\left( \theta \right)

이 방법은 정확하게 파라미터를 찾아가지만 모든 데이터에 대하여 cost function을 계산하고 미분해야 하기 때문에 계산량이 매우 많다. 또한 초기 파라미터 값에 매우 큰 영향을 받아 local minimum에 빠질 수 있다는 단점이 있다.


Figure 1. Local minimum과 Global minimum
파라미터가 A 지점에서 시작하면 local minimum으로 수렴하고, B 지점에서 시작하면 global minimum으로 수렴하게 된다.

1.2 Stochastic Gradient Descent (SGD)

Machine learning에서는 한 번의 training 횟수를 1 epoch이라고 하고 파라미터를 조정하기 위해 사용하는 데이터 양을 batch라고 한다. GD는 한 epoch에 모든 파라미터 업데이트를 단 한번 수행한다. 따라서 기존의 GD는 전체 데이터에 대해 계산하기 때문에 학습이 너무 오래 걸린다. Stochastic Gradient Descent(SGD)는 cost function을 계산할 때 전체 데이터 대신 확률적으로 랜덤하게 추출한 일부 데이터(mini-batch)에 대해서 cost function을 계산한다. mini batch 단위로 정의되는 cost function을 $J_i(\theta)$ $(i = 1,...,M)$ 라 했을 때 SGD의 파라미터는 다음과 같이 업데이트 된다.

\theta = \theta - \alpha \,{\nabla _\theta }{J_i}\left( \theta \right)

기존의 GD보다 다소 부정확할 수 있지만 계산 속도가 훨씬 빠르다. 그러나, 그림 2. (b)에서 보여지는 것처럼 최적의 값을 찾아가는 방향이 GD는 매 step이 매우 효율적으로 움직이는 반면, SGD는 방향이 양 $(+)$ 방향, 음 $(-)$ 방향으로 순차적으로 일어나는 지그재그 현상이 일어나 탐색 경로가 비효율적이다. 최솟값의 방향으로만 움직이기 때문에 방향에 따라 기울기 값이 달라지는 경우 global minimum으로 향하지 않고 local minimum에 빠져 학습이 더 이상 진행되지 않는 현상도 발생한다.


(a) batch	(b) 최적값을 찾아가는 과정
Figure 2. GD와 SGD 비교

최근 Deep Neural Network를 효과적으로 학습시키기 위해 각각의 문제점들을 개선하는 SGD의 변형들이 제안되었다. SGD의 변형은 크게 두 가지로 나뉜다. 첫 번째는 momentum이라는 개념을 도입하여 gradient를 수정하는 알고리즘이고, 두 번째는 learning rate를 조절하는 알고리즘이다. 다시 말해, SGD의 변형은 방향과 step size를 고려하는 optimizer들이다. Figure 3은 이러한 분류에 따라 최근에 제안된 SGD의 변형들을 분류한 것이다.


Figure 3. SGD 기반 Optimizer 분류도

2. Momentum based Gradient

2.1 SGD with Momentum

SGD with Momentum은 관성이라는 물리학 법칙을 이용한 방법이다. momentum은 현재 기울기에 한 step 전의 이동 방향으로 일정 비율 $\gamma$ 만큼 추가하여 이동하는 방식이다. $v_t$ 는 time step $t$ 에서의 이동벡터라고 할 때, momentum을 수식으로 표현하면 다음과 같다.

\begin{array}{c} {v_t} = \gamma {v_{t - 1}} + \alpha \,{\nabla _\theta }J\left( \theta \right)\\ \theta = \theta - {v_t} \end{array}

여기서 $\gamma$ 는 momentum term으로 보통 $0.9$ 정도의 값을 사용한다. momentum을 사용하면 지그재그 현상이 줄어들고 진동을 하더라도 중앙으로 가는 방향에 힘을 얻기 때문에 SGD에 비해 상대적으로 빠르게 이동할 수 있다. 또한 관성에 의하여 local minimum에서 빠져나오는 효과를 기대할 수 있다. 반면 기존의 파라미터 $\theta$ 외에도 과거의 이동했던 양을 파라미터별로 저장해야 하므로 파라미터에 대한 메모리가 기존의 두 배가 필요하게 된다.


(a) SGD	(b) SGD with Momentum
Figure 4. 기본적인 SGD와 Momentum을 결합한 SGD

2.2 Nesterov Accelerated Gradient (NAG)

현재 위치에서의 momentum step과 gradient step을 독립적으로 계산하고 합하여 actual step을 만드는 기존 momentum과 달리 Nesterov Accelerated Gradient(NAG)는 momentum step을 먼저 고려하여 momentum step이 적용된 지점에서 gradient를 구해서 gradient step을 이동한다. 파라미터 \theta\를 업데이트 하기 위해 momentum $\gamma v_{t-1}$ 을 이용하므로 $\theta - \gamma v_{t-1}$ 을 계산하면 파라미터의 다음 위치에 대한 근사치를 얻을 수 있다. 이를 수식으로 표현하면 다음과 같다.

\begin{array}{c} {v_t} = \gamma {v_{t - 1}} + \alpha \,{\nabla _\theta }J\left( {\theta - \gamma {v_{t - 1}}} \right)\\ \theta = \theta - {v_t} \end{array}

기본적인 momentum은 현재의 가속도를 고려하지 않고 속도를 설정한다면, NAG는 현재 가속도를 어느정도 고려하여 속도를 설정한다고 볼 수 있다. 이러한 업데이트 방식을 통해 NAG는 momentum을 이용한 빠른 이동이라는 장점을 유지하면서 momentum에 의해 과하게 이동하는 단점을 보완한다.


(a) Momentum update	(b) NAG Momentum update
Figure 5. 기본적인 Momentum과 NAG의 momentum방식의 차이

3. Adaptive Learning Rate

3.1 Adaptive Gradient (Adagrad)

파라미터들은 각자 의미하는 바가 다르기 때문에 모든 파라미터에 동일한 learning rate를 적용하는 것은 비효율적이다. Adaptive Gradient(Adagrad)는 각 파라미터에 서로 다른 learning rate를 적용시키는 방법이다. 이 때, 변화가 많은 파라미터는 optimum에 가까이 있을 확률이 높기 때문에 learning rate를 작게 설정하고 변화가 적은 파라미터는 learning rate를 높게 설정한다. Adagrad는 대표적으로 word2vec이나 GloVe와 같이 단어의 등장 확률에 따라 variable 사용 비율이 확연하게 차이나는 word representation을 학습시킬 때 유용하다. Adagrad의 수식은 다음과 같다.

G_t = G_{t - 1} + ({\nabla_{\theta}J(\theta_t))^2}\\ {\theta _{t + 1}} = {\theta _t} - \frac{\alpha }{{\sqrt {{G_t} + \varepsilon } }} \cdot {\nabla _\theta }J\left( {{\theta _t}} \right)

Neural Network의 파라미터가 $k$ 개라고 할 때, $G_t$ 는 $k$ 차원 벡터로서 'time step $t$ 까지 각 변수가 이동한 gradient의 sum of squares'를 저장한다. $\theta$ 를 업데이트 할 때는 step size $\alpha$ 에 $\sqrt{G_t}$ 에 반비례한 크기로 이동을 진행하며 지금까지 많이 변화한 변수일수록 적게 이동하고 적게 변화한 변수일수록 많이 이동하도록 한다. 이 때, $\varepsilon$ 은 일반적으로 $10^{-4}$ ~ $10^{-8}$ 와 같은 매우 작은 수로 설정되어 $0$ 으로 나누는 것을 방지하기 위해 추가되었다. 여기서 $G_t$ 를 업데이트하는 식에서 제곱은 element-wise 제곱을 의미하며 $\theta$ 를 업데이트하는 식에서도 $\cdot$ 은 element-wise한 연산을 의미한다.

Adagrad는 learning rate decay와 같은 방법들을 이용하여 learning rate를 직접적으로 조절하지 않아도 된다는 장점이 있다. 모든 변수에 일괄적으로 동일한 learning rate를 적용하는 기존의 SGD 기반 알고리즘과는 다르게 각 변수들마다 적합한 learning rate를 자동으로 설정한다는 이점이 있지만 학습이 오래 진행될 경우 $G$ 에는 계속 제곱한 값이 더해지기 때문에 learning rate가 매우 작아져 업데이트가 이루어지지 않는다. 이러한 문제점을 해결하고자 제안된 알고리즘이 RMSProp와 AdaDelta이다.

3.2 Root Mean Square Propagation (RMSProp)

RMSProp은 Adagrad의 $G_t$ 가 무한히 커지는 것을 방지하고자 제안된 방법으로 $G_t$ 를 gradient의 제곱의 합이 아닌 지수 이동 평균으로 대체하여 다음과 같이 정의한다.

{G_t} = \gamma {G_{t - 1}} + \,\left( {1 - \gamma } \right){\left( {{\nabla _\theta }J\left( {{\theta _t}} \right)} \right)^2}\\ {\theta _{t + 1}} = {\theta _t} - \frac{\alpha }{{\sqrt {{G_t} + \varepsilon } }} \cdot {\nabla _\theta }J\left( {{\theta _t}} \right)

이렇게 대체할 경우 $G_t$ 를 이전의 변화량과 현재의 변화량의 지수 이동 평균으로 정의되기 때문에 Adagrad처럼 $G_t$ 가 무한히 커지지 않아 learning rate가 급격하게 감소하는 현상을 방지할 수 있다. RMSProp의 $G_t$ 가 갖는 또 다른 특징은 최근의 변화량에 더 높은 가중치를 준다는 것이다. 만약 $\gamma=0.9$ 인 경우, $G_t$ 는 다음과 같이 계산된다.

{G_t} = 0.9{G_{t - 1}} + 0.1{\left( {{\nabla _\theta }J\left( {{\theta _t}} \right)} \right)^2} = 0.81{G_{t - 2}} + 0.09{\left( {{\nabla _\theta }J\left( {{\theta _{t - 1}}} \right)} \right)^2} + 0.1{\left( {{\nabla _\theta }J\left( {{\theta _t}} \right)} \right)^2}

현재 시간에 대한 $G_t$ 는 $0.1$ 의 가중치를 갖는 현재 시간의 변화량 $(\nabla_\theta J(\theta_t))^2$ 과 그보다 작은 $0.09$ 의 가중치를 갖는 이전 시간의 변화량 $(\nabla_\theta J(\theta_{t-1}))^2$ , 그리고 $G_{t-2}$ 로 구성되는 것을 볼 수 있다.

3.3 Adaptive Delta (AdaDelta)

AdaDelta는 RMSProp와 유사하게 AdaGrad의 단점을 보안하기 위해 제안되었다. AdaDelta는 $G_t$ 를 구할 때 합을 구하는 대신 지수 평균을 구한다. 다만 여기에서는 step size를 단순하게 $\alpha$ 로 사용하지 않고 step size의 변화값의 제곱을 가지고 지수 평균을 적용한다.

{G_t} = \gamma {G_{t - 1}} + \,\left( {1 - \gamma } \right){\left( {{\nabla _\theta }J\left( {{\theta _t}} \right)} \right)^2}\\ {s_t} = \gamma {s_{t - 1}} + \,\left( {1 - \gamma } \right)\Delta _{{\theta _t}}^2\\ {\Delta _{{\theta _t}}} = \frac{{\sqrt {{s_{t - 1}} + \varepsilon } }}{{\sqrt {{G_t} + \varepsilon } }} \cdot {\nabla _\theta }J\left( {{\theta _t}} \right)\\ {\theta _{t + 1}} = {\theta _t} - {\Delta _{{\theta _t}}}

이 수식은 GD와 같은 1st order optimization 대신 2nd order optimization(Hessian)을 approximate 하기 위한 방법이다. SGD, Momentum, Adagrad와 같은 식들의 경우 $\Delta_\theta$ 의 unit을 구해보면 $\theta$ 의 unit이 아닌 unit의 역수를 따른다. $\theta$ 의 unit을 $u(t)$ 라고 하고 $J$ 는 unit이 없다고 가정할 경우 1st order optimization에서는

{\Delta _\theta } \propto \frac{{\partial J}}{{\partial \theta }} \propto \frac{1}{{u\left( \theta \right)}}

이다. 반면 Newton method와 같은 2nd order optimization을 보면

{\Delta _\theta } \propto \frac{{\frac{{\partial J}}{{\partial \theta }}}}{{\frac{{{\partial ^2}J}}{{\partial {\theta ^2}}}}} \propto u\left( \theta \right)

이므로 바른 unit을 가지게 된다. 따라서 $1/{\frac{\partial^2 J}{\partial\theta^2}} = \Delta\theta/{\frac{\partial J}{\partial\theta}}$ 이므로 이를 분자의 Root Mean Square(RMS), 분모의 RMS 값의 비율 $\frac{{\sqrt {{s_{t - 1}} + \varepsilon } }}{{\sqrt {{G_t} + \varepsilon } }}$ 로 근사한 것이다. 또 Hessian을 사용하기 때문에 해당 지점이 극대인지 극소인지, Saddle point인지 critical point 종류를 판별할 수 있다는 장점이 있다. 반면 2차 미분까지 하기 때문에 계산 속도가 상대적으로 느리다.

4. Gradient + Learning Rate

4.1 Adaptive Moment Estimation (ADAM)

Adaptive Moment Estimation(Adam)은 RMSProp와 Momentum 두 방식의 장점을 합친 방식으로 현재 Deep neural network에서 학습에 가장 광범위하게 이용되고 있는 알고리즘이다. Momentum의 방식처럼 지금까지 계산해온 gradient의 지수 평균을 저장하고 RMSProp의 방식처럼 gradient의 제곱을 지수 평균한 값을 저장하여 수식에 활용한다.

{m_t} = {\beta _1}{m_{t - 1}} + \left( {1 - {\beta _1}} \right){\nabla _\theta }J\left( \theta \right)\,\,\,\,\,\,\,\,\,\,\,{\rm{momentum\ term}}

{v_t} = {\beta _2}{v_{t - 1}} + \left( {1 - {\beta _2}} \right){\left( {{\nabla _\theta }J\left( \theta \right)} \right)^2}\,\,\,\,\,\,{\rm{RMSProp\ term}}

이 때 ${\beta_1},{\beta_2} \in {[0,1)}$ 는 일반적으로 각각 $0.9$ 와 $0.999$ 로 설정한다. 다만 Adam은 $m_t$ 와 $v_t$ 가 처음에 $0$ 으로 초기화 되어있기 때문에 학습 초반에는 $0$ 에 가깝게 bias 되어있을 것이라고 판단하여 unbiased expectation의 형태로 이용하기 위해 다음과 같이 변형한다.

{\hat m_t} = \frac{{{m_t}}}{{1 - \beta _1^t}},\,\,\,\,\,\,\,\,\,\,\,\,{v_t} = \frac{{{v_t}}}{{1 - \beta _2^t}}

최종적으로 $\theta$ 에 대한 업데이트 식은 다음과 같이 이루어진다.

\theta = \theta - \frac{\varepsilon }{{\sqrt {{{\hat v}_t} + \varepsilon } }}{\hat m_t}

5. Conclusion

지금까지 다양한 Optimizer를 알아보았다. 어떤 알고리즘이 가장 좋다라고 할 수 없으므로 실제로 네트워크를 학습시킬 때는 다양한 시도를 해보며 성능에 대해 실험해볼 필요가 있다. Table 1은 일반적으로 많이 이용하는 NAG, AdaGrad, RMSProp, Adam의 momentum, learning rate, weight update과 Tensorflow에서 권장하는 하이퍼파라미터의 기본값을 요약한 것이다.


Table 1. NAG, AdaGrad, RMSProp, Adam 요약

Soraemon

소라에몽