ADAM - A Method for Stochastic Optimization

2017년

[Abstract]

이 논문에서는 저차를 이용한 예측에 기반한 확률적 목적함수의 1차 기울기 기반의 최적화 알고리즘인 Adam을 소개한다. 이 방법은 구현하기에 직접적이고, 계산량이 효과적이고, 메모리가 적게 필요하고, 기울기를 diagonal rescaling하는데 변함이 없고, 큰 데이터나 파라미터에 적용하는 데에 적합하다. 이 방법은 또한 매우 노이즈가 많거나 기울기가 sparse한 등의 변화하는 목적이나 문제에 적합하다. 조정 변수는 직관적으로 해석될 수 있으며 약간의 전형적인 튜닝만을 필요로 한다. Adam을 만드는 데에 영감을 준 관련된 알고리즘과의 연결고리도 소개된다. 또한 알고리즘의 이론적인 수렴 성질도 분석했고, 알려진 최고의 알고리즘들과 비교하여 수렴도에 대한 regret bound도 제공한다. 실험 결과는 아담이 다른 최적화 방법들과 비교해도 잘 작동한다는 것을 보여준다. 마지막으로, AdaMax에 대해서도 논의할 것이다.

[1] Introduction

1차 기반 최적화는 널리 쓰였는데, 계산량에서 효율적이다. SGD도 많이 쓰이는데, 이때 목적함수는 data subsampling 말고 또다른 노이즈 소스(dropout같은)가 있을 수 있다. 따라서 noisy할 경우에 대해 더 효과적인 알고리즘이 필요하다. 이 논문은 고차원 파라미터 공간에서의 SGD 최적화와 1차 최적화 방법에 중점을 둔다.

Adam은 1차 방법인데, 적은 메모리를 사용하여 효율적인 확률론적 최적화를 한다. 이 방법은 각각의 파라미터에 대해 gradient의 첫번째와 두번째 moment의 추정치를 이용하여 최적의 learning rate를 계산한다. 또한 AdaGrad(sparse gradient에 효과적)와 RMSProp(on-line, non-stationary에 효과적)의 장점을 합친 방법이다.

Adam의 장점은 엄청난 수의 파라미터 업데이트가 기울기를 rescaling해도 변화가 없다는 것, step size가 제한되는 것, 불변 목적함수가 필수가 아닌 것, sparse한 기울기에서도 잘 작동하는 것, 그리고 step size annealing을 자동으로 하는 것이다.

[2] Algorithm

$\alpha$ : step size
$\beta_1, \beta_2$ : moment 예측의 지수 decay rate
$f(\theta)$ : 목적 함수
$\theta_0$ : 초기 파라미터

$\begin{align}\text{while }&\theta_t\text{ not converged, do}\\ & t\leftarrow t+1\\ & g_t\leftarrow\triangledown_\theta f_t(\theta_{t-1})\\ & m_t\leftarrow\beta_1\cdot m_{t-1}+(1-\beta_1)\cdot g_t\\ & v_t\leftarrow\beta_2\cdot v_{t-1}+(1-\beta_2)\cdot g_2^t\\ & \hat{m_t}\leftarrow\frac{m_t}{1-\beta_1^t}\\ & \hat{v_t}\leftarrow\frac{v_t}{1-\beta_2^t}\\ & \theta_t\leftarrow\theta_{t-1}-\alpha\cdot\frac{\hat{m_t}}{\sqrt{\hat{v_t}}+\epsilon}\\ \text{end while} \end{align}$

알고리즘은 기울기와 기울기의 제곱의 지수평균을 업데이트하고, hyper-parameter $\beta_1, \beta_2$는 이 이동 평균의 지수적인 decay rate을 조절한다. 이 두 움직임의 평균은 기울기의 1차와 2차 모멘트로부터 예측된다. 0으로 초기화 되기 때문에 초기 시점에나 $\beta_1, \beta_2$가 작을 때 0으로 bias되는 경우가 생기는데, 뒤에서 상쇄가 가능하다. 위 알고리즘 1의 뒤쪽에 약간의 순서 변경을 하면 표현의 명확성이 떨어지지만, 효율성을 더 확보할 수 있다.

[2.1] Adam’s update rule

Adam의 특징 중 하나는 업데이트할 때 stepsize를 신중하게 선택해야 한다는 점이다.

$\triangle t=\alpha \cdot \frac{\hat{m}_t}{\sqrt{\hat{v}_t}}$

이게 effective한 step 이다. 이 stepsize는 $(1-\beta_1)\gt\sqrt{1-\beta_2}$일 경우($|\triangle_t|\le\alpha\cdot\frac{(1-\beta_1)}{\sqrt{1-\beta_2}}$)와 이 경우가 아닐 경우($|\triangle_t|\le\alpha$)에 대해 두 개의 upper bound가 있다. 첫번째 경우는 현재 timestep 제외하고 대부분 gradient가 0일 경우 같은 매우 sparse한 경우이고, 두번째 경우는 덜 sparse한 경우인데, 효과적인 step size가 줄어든다.

일반적인 경우는 후자인데, 결국 effective stepsize는 $\alpha$에 의해 bound된다. 현재 기울기 예측이 충분한 정보를 주지 않더라도 trust region을 구축하기 위한 것이라고 이해될 수 있다. 따라서 $\alpha$의 적절한 크기를 아는 것이 상대적으로 쉽다. (보통 머신러닝 모델에서 우리는 적절한 파라미터 값을 대략적으로 알고 있다.)

약간 과장하면, $\frac{\hat{m}_t}{\sqrt{\hat{v}_t}}$ 를 signal-to-noise ratio(SNR)이라고 할 수 있다. SNR이 더 작으면 $\triangle_t$는 0에 더 가까워진다. SNR이 작다는 말은 $\hat{m_t}$가 진짜 기울기 방향으로 가고 있다는 데에 더 큰 불확실성을 갖는다는 말, 즉 현재 optima에 거의 다 왔으므로 어디로 갈지 모르는 상황이 되어 effective stepsize가 더 작아진다. 따라서 자동 annealing의 형태를 띤다. 또한 $\triangle_t$는 gradient의 scale이 변해도 변하지 않는다(분수이므로 scale된것이 사라진다).

[3] Initialization Bias Correction

우리는 제곱된 기울기의 지수 평균과 decay rate $\beta_2$를 이용하여 f의 2차 moment를 알아내려고 한다. 먼저 지수 이동 평균을 0으로 초기화한다. 위 알고리즘의 식에 대입하면, 다음 지수 이동 평균을 구할 때 이전의 gradient가 $\beta_2$의 지수만큼 기여하게 된다. $\mathbb{E}[v_t]$와 $\mathbb{E}[g_t^2]$와의 관계성을 알면 그 차이를 없앨 수 있다. 알고리즘의

$v_t = (1-\beta_2)\sum_{i=1}^t\beta_2^{t-i}\cdot g_i^2$

식에 평균을 취하면

$\mathbb{E}[v_t] = \mathbb{E}[g^2_t]·(1−\beta_t^2) +\zeta$

이 식을 얻을 수 있다. 만약 $g_t$가 변하지 않는 값이면 $\zeta=0$이 되는데, 만약 $g_t$가 변하더라도 아주 이전의 gradient에는 작은 계수가 붙기 때문에, $\zeta$는 아주 작은 숫자가 된다. $1-\beta_2^t$는 running average를 0으로 초기화하면서 생긴 텀인데, 초기 bias를 없애주기 위해 알고리즘 1에서는 bias correction을 위해 이 식으로 나눠준다.

gradient가 sparse할 경우에는, 믿을만한 2차 모멘트의 예측을 위해서는 작은 $\beta_2$를 선택하여 많은 기울기를 평균해야 한다. 그러나 작은 $\beta_2$를 선택하면 초기 bias의 correction이 없게 되므로(bias correction은 $1-\beta_2$로 나누는 것이므로, 작은 $\beta_2$를 선택할 경우 나누는 항이 1이 되어 bias correction이 줄어든다) sparse하지 않을 경우보다 초기 step이 더 커지게 된다. (앞의 [2.1] stepsize의 bound 식을 보면 이 경우의 bound가 더 크다)

[4] Convergence Analysis

각 시간 t에 대해, 우리의 목적은 $\theta_t$를 예측하고 그 예측을 unknown cost function $f_t$에 대해 평가하는 것이다. sequence가 이전에 알려져있지 않기 때문에 regret이라는 것을 사용해서 평가한다.

$R(T) = \sum_{t=1}^T[f_t(\theta_t)-f_t(\theta^* )]$

이게 regret 식이다. Adam은 $O(\sqrt{T})$의 regret bound 갖고 있다. 이 결과는 현존하는 online learning중 최고이다.

[Thm4.1]

Thm 1은 $\alpha_t$가 $t^{-1/2}$로 decay하고, $\beta_1$이 $\lambda^t$ 로($\lambda$는 $1$에 엄청나게 가까운 수)로 decay할 때 성립한다. Thm1은 데이터가 sparse하고 제한된 기울기를 갖고 있을 때, $\sum$ 항이 그 상한보다 훨씬 작다는 것을 의미한다(특정한 함수와 데이터 특징에 대해). 이 결과에 기댓값($\mathbb{E}$)을 적용하면 Adam에도 적용될 수 있다. Adaptive method는 non-adaptive 모델보다 더 좋은 convergence를 갖는다. $\beta_1$의 decay가 중요한 역할을 하는데, 이전에 있었던 모멘텀 계수를 줄이는 것이 수렴을 향상시킨다는 연구결과와도 들어맞는다.

[Cor4.2]

Thm4.1의 따름정리인데, 결국은 $\frac{R(T)}{T}$ 가 0으로 수렴한다는 내용이다.

Adam에 직접적으로 영향을 준 연구는 RMSProp과 AdaGrad이다. vSGD, AdaDelta, natural Newton Method같은 stochastic 방법들은 1차 미분 정보에서 곡률을 예측하여 stepsize를 정한다. SFO는 mini-batch 기반의 quasi-newton 방법인데, Adam과 달리 선형적인 메모리가 필요해 GPU에서는 사용할 수 없다. NGD와 같이 Adam은 데이터의 구조에 적응하는 preconditioner를 도입했다(Adam에서의 $\hat{v_t}$는 Fisher information matrix의 근사이다). 그러나 Adam의 preconditioner는 AdaGrad에서와 비슷한데, 그냥 NGD보다 더 적응이 느리다.

[기본지식]

newton’s method : GD랑 비슷하지만 $x_n+1 = x_n - \frac{f’}{f’’}$ 으로 업데이트 하는 방법
quasi-newton method : newton’s method와 비슷하지만 계산량이 훨씬 적다.$f’’$ 대신 $f’‘$을 근사한 행렬을 사용한다.

[RMSProp]

모멘텀을 이용한 RMSProp에서는 rescale된 gradient에 momentum을 사용하여 파라미터 업데이트를 하는데, Adam은 현재 기울기의 1차, 2차 momentum의 평균을 이용하여 바로 예측한다(rescale이 없음). 또한 RMSProp은 bias-correction 항이 없다. 이러면 너무 큰 stepsize나 발산으로 이어질 수 있다.

[AdaGrad]

sparse한 gradient에 잘 작동하는 알고리즘이다. Adam에서 $\alpha$와 $\beta$를 적절하게 설정하면 AdaGrad와 똑같다. bias-correction 항이 없으면 비슷하지 않게 된다. 과거의 기울기의 변화량(momentum)을 참고하여 update하는 것이 특징이다.

[6] Experiments

큰 모델과 데이터셋을 사용하므로써, Adam이 현실에서도 효과적이라는 것을 증명한다. hyper-parameter의 경우는, dense grid로 찾고, 가장 좋은 결과를 내는 hyper-parameter를 비교에 사용한다.

[6.1] Experiment : Logistic Regression

L2 정규화된 multi-class logistic regression을 MNIST를 이용하여 평가했다. logistic regression은 convex한 목적함수를 갖고 있다. Adam은 모멘텀을 사용한 SGD와 비슷하게 수렴했고 Adagrad보다는 빨랐다.

AdaGrad는 feature와 gradient가 sparse할 때 유리하다. Adam이 $\frac{1}{\sqrt{t}}$의 stepsize를 사용한다면 이론적으로 AdaGrad의 성능과 같다. 이 부분에 대해서는 IMDB 영화 리뷰 데이터셋을 이용해 sparse feature 문제를 시험했다. 결과는 이론과 같았다.

[6.2] Experiment : Multi-Layer Neural Networks

여기서 non-convex한 함수에 대한 분석은 이루어지지 않았지만, 경험적으로 Adam이 이런 상황에서도 좋은 성능을 낸다는 것을 알았다. 우선 기본 deterministic cross-entropy 목적함수와 L2 weight decay를 사용하여 여러 다른 optimizer들을 연구했다. SFO 방법은 최근에 제안된 minibatch 기반의 quasi-Newton 방법인데, multi-layer NN에서 좋은 성능을 보여준다. 그런데 Adam의 iteration이 덜 필요했고, 절대적인 시간도 빨랐다. (곡선 정보를 update하는 데에 SFO는 시간이 더 필요하고, linear memory가 필요하다.) 또한 dropout을 사용한 다른 확률론적 방법들과의 비교에서도 Adam이 월등한 성적을 보여주었다.

[6.3] Experiment : Convolutional Neural Networks

CNN에서도 Adam이 효율적으로 작동할 수 있다. 처음에는 Adam과 AdaGrad가 빠른데, 나중에는 SGD와 Adam이 잘 수렴한다. 이 이유는 2차 moment 예측 $\hat{v_t}$가 몇 epoch뒤에는 사라지고 $\epsilon$이 성능을 좌우하기 때문이다. fully connected NN과 비교할 때, CNN에서는 2차 moment 예측은 cost function의 지형을 근사하는 데에 실패한 것이다. CNN에서는 1차 moment를 통해 minibatch의 분산을 줄이는 것이 더 중요하다. Adam은 SGD보다 약간 더 좋은데, 또한 SGD처럼 수동으로 learning rate를 조절해야 하는 것이 아니라 자동으로 서로 다른 layer들에 대한 learning rate를 조절해준다.

[6.4] Experiment : Bias-Correction Term

bias term은 Adam에서 매우 중요하며 bias correction term을 없애는 것은 momentum을 사용한 RMSProp과 같은 결과를 보여준다. 이 논문에서는 $\beta_1$과 $\beta_2$, $\alpha$를 다양하게 바꾸며 실험했다. $\beta_2$가 1에 가까우면 sparse한 gradient에 견고성이 더 요구되므로 더 큰 초기 bias가 생긴다. 따라서 이 논문에서는 느린 decay같은 상황에서 bias correction term이 중요하다고 예상했고, 실험 결과에서는 $\beta_2$가 1에 가깝고 bias term이 있는 것이 가장 성능이 좋았다(예상한 것이 맞았다). 결과적으로, Adam은 RMSProp보다 같거나 더 좋다.

[7] Extensions 안읽었음

[8] Conclusion

이 논문에서는 간단하고 계산효율적인 기울기 기반의 확률 목적 함수 최적화 알고리즘을 소개하였다. 이 방법은 큰 데이터셋과 고차 파라미터 공간을 위한 것이다. Adam은 두 유명한 최적화 방법인 AdaGrad 와 RMSProp의 장점을 결합하여 만들어졌는데, AdaGrad의 sparse한 기울기에 대한 장점과 RMSProp의 변동 목적함수에 대한 장점이다. 이 방법은 구현이 직관적이고 적은 메모리를 사용한다. 실험은 convex 문제에서의 수렴도 해석을 증명해주었다. 종합하면, Adam은 딥러닝에서의 다양한 non-convex 최적화 문제에서 강건하고 잘 맞는다.

다음에 읽어볼 논문 : AdaGrad, RMSProp