[ML/DL] 최적화(Optimization), 경사하강법 (Gradient Descent Methods) (2)

수식이 포함되어 있는 글입니다. 원활한 이해를 위해 데스크탑 모드로 전환하실 것을 권합니다.

 

Gradient Descent

First-order iterative optimization algorithm for finding a local minimum of a differentiable function

cf.) first-order optimization

first-order optimization 같은 경우에는 최소 한 번 미분한 값을 활용하여 optimization을 하는 경우를 의미하고,
second-order optimization과 같은 경우에는 두 번 미분한 값 (or gradient)를 활용하여 최적화를 하는 경우를 의미함.
일반적으로, nth optimization 같은 경우에는 rank = n인 텐서를 활용하여 최적화를 진행하는 경우를 의미한다.

---

Gradient Descent Methods

https://www.slideshare.net/yongho/ss-79607172?from_action=save

• Stochastic gradient descent
• Momentum
• Nesterov accelerated gradient (NAG)
• Adagrad
• Adadelta
• RMSprop
• Adam

gradient descent 방법에는 위와 같은 다양한 방법들이 있다. 위와 같은 방법론들을 아래에서 다룰 예정이다.

---

(Stochastic) Gradient Descent

$$W_{t+1} ← W_t - \eta g_t$$

$\eta$ : learning rate
$g_t$ : gradient

 

gradient descent 방법의 문제점은 learning rate를 적절하게 설정하는 것이 어렵다는 점이다. learning rate를 너무 크게 가져갈 경우 학습이 제대로 이루어지지 않고, weight 움직임이 계속 튀면서 발산하거나 하는 경우(shooting)가 생길 수 있음. 반대로 learning rate를 작게 가져갈 경우 학습 속도가 지나치게 느리다는 단점이 있다.

 

---

Momentum

위의 gradient descent의 단점을 보완하기 위한 방법으로 제안된 개념. momentum은 관성으로, 한 번 gradient가 흐르던 방향을 다음 스텝에서 그래디언트가 조금 튀더라도 이전에 가던 방향에 대한 정보를 어느 정도 가져가자는 의미 정도로 해석 가능하다.

$$a_{t+1} \leftarrow \beta a_{t} + g_t$$
$$W_{t+1} \leftarrow W_t - \eta a_{t+1}$$

$\beta$: momentum
$\eta$: learning rate
$a_t$: accumulation

앞서, SGD에서는 $g_t$​ 의 경우 매 시점마다 변화했음. 즉, $W_t$에 반영되는 게 매 시점마다 달라지고 이전 정보를 지속적으로 활용한다고 보기는 어려움.

momentum 항을 추가함으로써 accumulation인 $a_t$​를 활용하고, 여기에 이전 시점의 그래디언트와 이전 시점의 accumulation을 beta라는 momentum 항만큼 곱해주면서 $a_t$​를 업데이트해주고, 이러한 $a_t$​를 $W_t$​의 업데이트에 반영을 해주는 것. (간단하게 정리하자면, 매 시점마다 $g_t$​를 바로 가중치 $W_t$​의 업데이트에 반영해주는 것이 아니라, $a_t$​에 $g_t$​와 이전 시점의 accumulation인 $a_{t-1}$을 동시에 넣어준 후 이를 활용해 $W_t$​를 업데이트 시켜줌으로써 학습 시에 현재 방향과 지금까지의 방향성을 동시에 가져가는 것!)

한 번 흘러가기 시작한 direction을 어느 정도 유지해주기 때문에 gradient가 계속 shooting을 한다고 해도 어느 정도의 학습 성능을 보장해준다는 것.

 

---

Nesterov Accelerated Gradient (NAG)

momentum과 비슷하지만 약간의 variation이 추가된 상태. (다음 스텝의 그래디언트를 활용하겠다)

$$a_{t+1} \leftarrow \beta a_t + \nabla L(W_t - \eta \beta a_t)$$
$$W_{t+1} \leftarrow W_t - \eta a_{t+1}$$

$\nabla L(W_t - \eta \beta a_t)$: Lookahead gradient

위의 momentum 식에서는 $a_t$에 바로 $g_t$​를 더해주지만, 여기에서는 lookahead gradient라는 것을 활용함.

Lookahead gradient란,$a_t$를 활용하여 step을 하나 밟아보고 그 곳에서의 gradient 정보를 의미함.

NAG와 같은 경우에는 minima에 조금 더 빠르게 수렴할 수 있다. momentum의 경우에는 실제 local minima 등에 가까워졌지만 이를 지나쳤을 때 계속해서 local minima와 반대 방향으로 가고자 하는 관성이 있으므로 수렴을 하는 데에 조금 더 오랜 시간이 걸릴 수 있다. 하지만, NAG와 같은 경우에는 한 스텝 이후의 그래디언트를 $a_t$에 반영되는 방식이므로 local minima를 지나친다고 하더라도 현 시점에서 한 스텝을 더 밟은 그래디언트를 반영하기 때문에 minima를 지나치고자 하는 관성을 조금 더 빠르게 탈출할 수 있다. (이론적으로 converge ratio가 빠르다는 것이 증명되어 있음)

 

---

Adagrad

"Ada" → Adaptive.

$$W_{t+1} = W_t - \frac{\eta}{\sqrt{G_t}+\epsilon}g_t$$

$G_t$​ : Sum of gradient squares (t시점까지의 그래디언트 제곱합)
$\epsilon$ : for numerical stability (zero division error를 회피하기 위해 분자에 더해주는 아주 작은 수)

learning rate 조절을 통해 뉴럴넷 내에서 많이 변화한 파라미터들에 대해서는 적게 변화를 시키고 그렇지 않은 파라미터들에 대해서는 많이 변화를 시키는 방법.

어떻게 많이 변화했는지 혹은 적게 변화했는지를 알 수 있는가? 에 대한 정보는 $G_t$​에 저장을 해두는 것. $\eta$를 $\sqrt{G_t + \epsilon}$ 으로 나눠줌으로써 지금까지 많이 변화한 파라미터는 학습률이 낮아질 것이고, 또한 지금까지 적게 변화한 파라미터는 오히려 학습률이 높아질 것이다. (여기서 그래디언트의 제곱합은 해당 파라미터가 얼마나 많이 변화를 했는가 를 의미하는 것이겠지?)

하지만 training이 길어질 때 $G_t$가 지속적으로 커지면서(property of monotonic increasing) $g_t$ 앞의 항이 0에 가까워지며 학습이 이루어지지 않는다는 단점이 존재한다.

 

---

Adadelta

Adadelta는 Adagrad에서 $G_t$가 지속적으로 커지는 현상을 방지하고자 함 (by restricting the accumulation window).

$$G_t = \gamma G_{t-1} + (1-\gamma) g_t^2 $$
$$W_{t+1} = W_t - \frac{\sqrt{H_{t-1}} + \epsilon}{\sqrt{G_t} + \epsilon} g_t $$
$$H_t = \gamma H_{t-1} + (1-\gamma) (\Delta W_t)^2$$

$G_t$​ : EMA of gradient squares
$H_t$​: EMA of difference squares

앞선 Adagrad에서는 모든 timestep에 대해서 $G_t$를 계산했다면, Adadelta에서는 기간(window)을 설정해놓고 그 window size만큼의 기간에 해당하는 Gradient만 반영을 하겠다는 것임. 다만 window size만큼의 기간에 해당하는 gradient를 저장해두어야 하기 때문에 공간적으로 비효율적임. Adadelta에서는 이러한 비효율성을 방지하기 위해exponential moving average(EMA) 를 사용한다. ($\gamma$와 $1-\gamma$를 곱해주는 부분이 EMA 부분)

Adadelta에서는 learning rate이 따로 존재하지 않음. 즉, 우리가 바꿀 수 있는 부분이 많이 없기 때문에 많이 활용되는 편은 아니다.

 

---

RMSprop

$$G_t = \gamma G_{t-1} + (1-\gamma)g_t^2 $$
$$W_{t+1} = W_t - \frac{\eta}{\sqrt{G_t }+ \epsilon} g_t$$

$G_t$​ : EMA of gradient squares

Adadelta와 마찬가지로 gradient squares의 지수이동평균을 사용하지만, 여기서는 학습률인 $\eta$를 도입해서 이를$G_t$의 square root로 나눠주는 방식을 취함. 즉, Adadelta에서 다시 학습률을 도입한 최적화 방법론이다.

 

---

Adam (Adaptive Moment Estimation)

가장 무난하게 사용.

$$m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t$$
$$v_t = \beta_2v_{t-1} + (1-\beta_2)g_t^2$$
$$W_{t+1} = W_t - \frac{\eta}{\sqrt{v_t} + \epsilon} \frac{\sqrt{1-\beta_2^t}}{1-\beta_1^t}m_t$$

$m_t$ : gradient
$v_t$​ : EMA of gradient squares
$\epsilon$ : zero division error를 방지하기 위한 항 (practice에선 꽤 중요함. 대략적으로 e-7로 조절)

과거의 그래디언트와 과거의 squared gradient를 모두 이용함. Adam 알고리즘은 adaptive learning rate 방법과 momentum을 효과적으로 combine한 알고리즘이다.
$m_t$​ 앞의 항은 unbiased estimator가 되기 위해 붙인 항 (크게 중요한 항은 아님)

 

---

Conclusion

  단순 Gradient Descent 방법에서 learning rate 조절과 momentum 등을 적절히 활용하여, optimization을 조금 더 효율적으로 수행할 수 있도록 하는 다양한 advanced 방법론을 소개해봤다.
 optimizer와 같은 경우에도 정답은 없다. Adam이 가장 무난하게 사용된다고는 하지만, 구글에서는 실험 시에 SGD를 사용하여 최적의 성능을 뽑아내기도 한다. 물론 실험을 다양하게 할 컴퓨팅 자원이 없다면 Adam이 가장 무난하고 효율적으로 정답에 가까운 결과를 내줄 것이다.

 

[reference]
1. 고려대학교 인공지능학과 최성준 교수님 optimization 강의 (boostcamp ai tech)
2. 하용호님의 슬라이드 (https://www.slideshare.net/yongho/ss-79607172?from_action=save)