[딥러닝] Adam: A Method for Stochastic Optimization

저자 : Diederik P. Kingma, Jimmy Lei Ba

링크 : https://arxiv.org/abs/1412.6980

Adam: A Method for Stochastic Optimization

 

대학원 진학을 준비하면서 인공지능을 처음 접하게 되었고, 딥러닝 코드를 다루다 보니 정말 자주 보게 된 것이 바로 Adam인데요...! Adam의 기본적인 작동 원리는 알고 있었지만 왜 그렇게 많은 딥러닝 코드에서 Adam을 최적화 방법으로 사용하는지 궁금했습니다. 인공지능 강의에서도 '웬만하면 Adam을 쓰는 게 좋다'라고 하고 대충 넘어가기도 했고요. 그래서 Adam을 처음 제안한 논문을 읽고, 이해를 돕기 위해 나름 제 언어로 쉽게 재구성해보았습니다.

---

1. Introduction

• Random data subsampling이나 noise, dropout 등에 의해서 인공지능 머신의 목적함수는 확률적(stochastic)일 때가 많음. 따라서 고차원의 파라미터 공간 상에서 확률적 목적함수를 효율적으로 최적화하는 기법이 중요함.
• 고차 도함수(ex. Newton method)를 사용하는 최적화 기법의 경우 텐서 연산의 시간 복잡도가 차수에 지수적으로 증가하므로 매우 비효율적임. 또한 비볼록(non-convex) 최적화 문제에서는 알고리즘 성능이 좋지 않음. 따라서 1차 도함수 기반 최적화 기법에 집중하였음.

경사하강법 vs 뉴턴법

• Adam은 1차 도함수 및 1차•2차 모멘트만을 사용하여 각 파라미터의 learning rate을 adaptive하게 조정함. 간단한 알고리즘 구조로 인해 메모리 사용량이 적음.
• Adam은 기울기의 합을 누적하여 sparse gradient에 적합한 AdaGrad와, 현재 기울기에 가중치를 부여하여 on-line (실시간) 및 non-stationary(시간에 따라 통계적 특성이 변화하는 비정상성)에 적합한 RMSProp의 장점을 통합함.

2. Algorithm

Adam Algorithm

• $g_t$는 시간 $t$에서 목적함수의 기울기(그라디언트)를 의미함.
  $m_t$는 $g_t$의 지수이동평균을, $v_t$는 $g_t^2$의 지수이동평균을 의미함.
• 지수이동평균(exponential moving average, EMA)이란 과거의 모든 기간을 계산 대상으로 하며 최근의 데이터에 더 높은 가중치(과거로 갈수록 지수적으로 감소하도록 설정)를 두는 가중이동평균법.

Adam Optimizer 지수이동평균의 점화식을 일반항으로 표현한 식.

• Adam은 update stepsize을 신중하게 선택하는 알고리즘임.
• Sparse gradient가 극단적인 경우, 과거의 모든 시점에서 gradient가 0이므로 현재 시점에서의 업데이트가 느리고 비효율적임. 따라서 stepsize를 크게 조정해줄 필요가 있고, 이는 learning rate($\alpha$)에 1보다 큰 상수 $(1-\beta_1) / \sqrt{1-\beta_2}$를 곱해줌으로서 보정할 수 있음.
• 본 논문에서 sparse gradient의 경우에 $(1-\beta_1) > \sqrt{1-\beta_2}$의 부등식이 성립한다고 한 이유가 뭘까?
  Sparse gradient의 경우에서는 stepsize $|\Delta_t| = \left\vert \alpha \frac{\hat{m}_t}{\sqrt{\hat{v}_t}} \right\vert$를 키워주기 위해 분자에 위치한 $m_t$는 크게, 분모에 위치한 $v_t$는 작게 보정해야 함. 이를 위해서는 $m_t$를 계산할 때에는 과거의 데이터를 적게, $v_t$를 계산할 때에는 과거의 데이터를 많이 고려해야 함. 왜냐하면 과거의 그라디언트는 대부분 0이기 때문에 이를 모두 고려하면 지수이동평균의 절댓값은 작아지게 되고, 반대로 적게 고려하면 절댓값은 커지게 됨. 따라서 $\beta_1$는 줄여야하고 $\beta_2$는 키워야 효과적으로 stepsize를 크게 보정할 수 있음.
  
• 이외의 일반적인 경우에는 $(1-\beta_1) \leq \sqrt{1-\beta_2}$이므로 $|\Delta_t| \leq \alpha$가 성립함. 따라서 모델 파라미터에 대한 사전 분포를 알고 있는 경우 learning rate($\alpha$)의 scale을 적절하게 추정할 수 있음.
• Learning rate($\alpha$)에 곱해진 상수 $\hat{m}_t / \sqrt{\hat{v}_t}$는 마치 SNR처럼 해석할 수 있음. 이 SNR은 최적점에 도달할수록 0에 접근하므로 알고리즘 내재적으로 gradient annealing을 구현할 수 있음.
• 목적함수의 그라디언트 $g_t$가 상수배가 되어도 $\hat{m}_t$와 $\sqrt{\hat{v}_t}$ 모두 동일한 만큼 scaling되므로 stepsize $|\Delta_t|$에 영향을 미치지 않음. 즉, stepsize는 그라디언트의 scale에 불변(invariant)함.

3. Initialization Bias Correction

• $m_0 = v_0 = 0$이므로 모멘트의 추정값은 0 근처에 biased됨. 이는 머신의 학습을 방해할 수 있기 때문에 모멘트 값을 보정하여 효율적인 학습을 유도함.
• Batchwise의 학습 방식은 $g_t^2$의 실제 기댓값을 정확하게 계산할 수 없기 때문에 $v_t$의 기댓값으로부터 추정해야 함(메모리 효율성 등의 이유도 있을 것임). 이 때 아래와 같은 관계가 성립함. $\zeta$는 $g_i^2$이 시간에 따라 독립적이라고 가정한 결과 발생한 오차를 나타내는 항임.

• $\beta$의 값을 적절히 선택하여 $\zeta$가 0에 근접하도록 할 수 있음.
  그러면 $\mathbb{E}[g_t^2] = \frac{\mathbb{E}[v_t]}{(1-\beta_2^t)}$가 성립하므로 위와 같이 bias-correction term을 도입할 수 있음.

4. Convergence Analysis

• Regret이란 결정 이론(decision theorem) 및 후회 이론(regret theorem)에 기반한 개념으로, 모든 선택의 순간에서 최선의 선택과 실제 선택의 차이에 의한 손실의 합으로 정의됨. Reinforcement learning과 같은 stochastic learning model에서 성능을 평가하는 주요 지표로 자주 활용됨.

• Adam algorithm에서 regret은 일정 상한 이하로 유계이며, regret bound는 𝒪($\sqrt{T}$)의 복잡도를 가짐. 따라서 시간에 따른 평균 regret $\frac{R(T)}{T}$는0에 수렴함. 이는 장기적으로 알고리즘이 최적의 결정을 내림을 보장함.
• 학습 후반부에서 파라미터들이 최적점에 접근함에 따라 그라디언트의 변동성이 감소하므로 학습의 효율성을 위해서는 과거 그라디언트 정보의 의존도를 줄이는 것이 좋음. 따라서 학습 후반부에서 $\beta$를 감소시키면 좋음. 본 논문에서는 시간에 따라서 지수적으로 $\beta$를 감소하는 방법($\beta_{1,t} = \beta_1 \lambda^{t-1}$)을 제시함.
• Data가 sparse한 경우 그라디언트가 0인 파라미터에 의해 regret의 상한 값은 더욱 감소함. 따라서 Adam은 sparse한 문제에도 적합한 알고리즘임.

5. Related Work

• Adam은 RMSProp과 Momentum의 장점을 통합한 알고리즘으로 생각할 수 있지만, 단순히 둘을 병합한 것과는 차이가 있음. RMSProp + Momentum은 rescaled gradient($G_{t,j}$)의 모멘텀($V_{t,j}$)을 이용하여 파라미터를 업데이트하지만, Adam은 1차 및 2차 모멘텀의 이동평균을 보정해 파라미터를 직접적으로 업데이트함.
• AdaGrad는 Adam의 특수한 경우로 $\beta_1=0, \beta_2 \approx{1}$인 Adam algorithm에 $\alpha_t = \frac{\alpha}{\sqrt{t}}$의 learning rate schedule를 적용한 것과 동일함.

6. Experiments

• MNIST dataset: 1/√t decay를 적용한 AdaGrad, SGD와 Adam의 로지스틱 회귀 모델 성능 비교.
  → Adam은 AdaGrad보다 빠르게, SGD와 유사하게 수렴함.
• IMDB BoW dataset: Dropout과 전처리를 적용한 sparse dataset에 대하여 AdaGrad, RMSProp, SGD, Adam의 성능을 비교.
  → Adam은 sparse features에 대해 좋은 성능을 보였고, 특히 SGD보다 크게 개선된 수렴 속도를 보였음.
• Multi-layer NN (+ Dropout) 모델 비교
  → Non-convex 최적화 문제임에도 불구하고 Adam이 가장 빠르게 수렴하였음.
  (SFO method: 전체 목적 함수를 미니배치 단위의 부분 함수들의 합으로 분해하여 stochastic과 quasi-Newton method의 장점을 결합)
• CNN (+ Dropout) 모델 비교
  → Dropout을 적용한 모델과 적용하지 않은 모델끼리 묶어서 비교했을 때 둘 다 Adam이 가장 빨리 수렴.
  (다만 실제로는 SGDMomentum가 Adam보다 좋은 성능을 보일 때도 많음.)
• Bias-Correction Term 분석 (RMSProp + Momentum과 Adam의 비교)
  → Bias-correction term이 없을 시 $\beta_2$가 1에 접근할수록 loss가 불안정해짐. 가장 안정한 경우는 bias-correction term과 함께 $\beta_2$가 1에 가까운경우임. 하이퍼-파라미터의 설정과 관계 없이 Adam은 $\beta_1 = 0$인 (RMSProp + Momentum)의 경우보다 우수한 robustness 및 최적화 성능을 보임.

7. AdaMax

• Adam의 분모($L^2$ norm)를 $L^p$ norm으로 확장함. $p$가 무한히 커질 때 간단하고 안정한 알고리즘이 유도됨.

빨간색 부분이 기존의 Adam algorithm과 다른 부분.

• Adam과 비교했을 때 bias-correction term이 빠지고 2차 모멘텀의 정의가 $L^p$ norm의 재귀적 표현으로 수정되었음. Bias-correction term이 필요 없는 이유는 $L^p$ norm의 수학적 특성상 max 연산자에 의해 초기값 0의 영향 및 bias가 첫 번째 계산 이후 사라지기 때문임.
• Bias-correction이 필요 없고 update stepsize의 상한 추정이 간단해졌다는 장점이 있음. 또한 max 연산자의 특성상 sparse gradient나 high variance gradient에 의한 민감성을 평탄화할 수 있음. 그러나 max 연산자 때문에 분모가 계속 커지므로 vanishing gradient에 취약함.

8. Conclusion

•    Adam은 RMSProp과 AdaGrad의 장점을 통합하고, non-convex 최적화 문제에도 잘 적용되니까 좋다...!