이것저것 잡동사니
[논문 읽기] Gradient Descent 최적화 알고리즘 총 정리 본문
Submitted on 15 Jun 2017
An overview of gradient descent optimization algorithms
An overview of gradient descent optimization algorithms
Gradient descent optimization algorithms, while increasingly popular, are often used as black-box optimizers, as practical explanations of their strengths and weaknesses are hard to come by. This article aims to provide the reader with intuitions with rega
arxiv.org
Abstract
Gradient descent optimization algorithm들은 가장 널리 쓰이는 black-box optimizer들이다. 각 알고리즘의 동작에 대한 직관을 제공하는 것이 이 논문의 목적이다.
1. Introduction
Gradient descent는 objective function \(J(\theta)\)의 값을 최소화시키는 방법이다. 이는 모델의 파라미터 \(\theta\in\mathbb{R}^d\)를 \(\theta\,\)에 대한 \(J\)의 그래디언트의 반대 방향으로 업데이트하는 방식으로 이루어진다.
$$\theta=\theta-\eta\cdot\nabla_\theta J(\theta)$$
Learning rate \(\eta\)는 (local)minimum 에 도달하기 위한 step의 크기를 조절한다.
2. Gradient descent variants
Objective function의 그래디언트를 계산할 때 사용하는 데이터의 개수에 따라 세 가지 종류의 gradient descent가 있다.
2.1 Batch gradient descent
Vanilla(기본) gradient descent, 파라미터 업데이트에 데이터셋 전체를 사용한다.
$$\theta=\theta-\eta\cdot\nabla_\theta J(\theta)$$
장점
1. Convex error surface에서 global minimum으로의 수렴이 보장된다.
2. Non-convex error surface에서 local minimum으로의 수렴이 보장된다.
단점
1. 한 번의 파라미터 업데이트에 많은 시간이 소요된다.
2. 메모리 용량보다 데이터셋의 크기가 클 경우 매우 비효율적이다.
3. Online(On-the-fly 방식 등)으로 모델 업데이트가 불가능 하다 (=새로운 데이터에 대한 적응이 느리다).
2.2 Stochastic Gradient descent (SGD)
한 번의 파라미터 업데이트에 하나의 학습 데이터 (\(x^{(i)}\)와 \(y^{(i)}\)쌍)이 사용된다. 매 epoch마다 순서를 랜덤으로 섞어 사용한다.
$$\theta=\theta-\eta\cdot\nabla_\theta J(\theta\,;x^{(i)};y^{(i)})$$
장점
1. Batch gradient descent보다 수렴 속도가 빠르다.
2. Online으로 모델 업데이트가 가능하다.
3. 목적 함수의 값이 크게 요동치면서 더 좋은 local minimum을 찾아갈 수도 있다.
단점
1. 목적 함수의 값이 크게 요동치게 된다. (업데이트의 분산이 크므로)
2. 정확한 minimum 값으로의 수렴이 어렵다. 값이 계속 튀게 된다.
특징
1. 학습이 진행되면서 learning rate를 천천히 줄이면 batch gradient descent와 같은 수렴 특성을 보인다.
2.3 Mini-batch gradient descent
한 번의 파라미터 업데이트에 \(n\)개의 데이터를 사용한다. \(n\)의 값은 경우에 따라 최적의 값이 달라진다. 매 epoch마다 순서를 랜덤으로 섞는다.
$$\theta=\theta-\eta\cdot\nabla_\theta J(\theta\,;x^{(i:i+n)};y^{(i:i+n)})$$
장점
1. 파라미터 업데이트의 분산을 줄일 수 있어 SGD에 비해 더 안정적인 학습이 가능하다.
Mini-batch gradient descent는 모델을 학습할 때 주로 사용되는 알고리즘이며 mini-batch가 사용되어도 주로 SGD라고 한다. 이 논문의 나머지는 SGD의 변형에 관한 것이다.
3. Challenges
3.1 적당한 learning rate를 알아내기 어렵다.
너무 작은 learning rate는 수렴을 너무 느리게 한다. 너무 큰 learning rate는 loss function이 minimum 근처에서 요동치게 하거나 발산시키면서 수렴을 방해한다.
Learning rate schedule 기법으로 objective fucntion의 값이 감소함에 따라 learning rate도 감소하도록 할 수 있다. 하지만 사람이 사전에 값을 세팅해주어야 하므로 각 데이터셋의 특성에 알맞게 세팅하기란 쉽지 않다.
3.2 빈도가 낮은 데이터의 학습
빈도가 낮은 데이터(또는 feature)에 대해서 learning rate를 크게 하여 학습이 되도록 하고 싶어도 불가능하다.
3.3 Saddle points
Global minima가 아닌 local minima(suboptimal local minima)에 빠지지 않아야 한다. 하지만 그보다 saddle point에 갇히는 것을 더 조심해야 한다. Saddle point는 모든 방향으로의 그래디언트가 0이므로 SGD는 해당 지점을 빠져나가기 어렵다.
4. Gradient descent optimization algorithms
앞서 서술한 문제들을 해결하기 위해 다음과 같은 기법들이 사용될 수 있다.
4.1 Momentum
SGD의 진동 현상을 줄여주고 수렴을 가속시켜준다.
4.2 Nestrov Accelerated Gradient(NAG)
미래 예측 능력을 가진 momentum이라고 보면 된다. Local mimimum 근처에서 수렴 속도를 미리 줄여준다.
여기부터는 Adaptive Learning Rate 방식을 사용 (파라미터마다 다른 learning rate를 사용해 모든 파라미터의 변화율이 비슷하도록 하여 희소 특성도 잘 학습되도록 한다)
4.3 Adagrad
Adaptive learning rate 방식을 사용한다. 하지만 학습이 진행될수록 learning rate가 0에 수렴하는 문제가 있다.
4.4 Adadelta
Adagrad를 개선해 learning rate가 0에 수렴하는 문제를 해결했다. \(\eta\)값을 정해줄 필요가 없다는 특징이 있다.
4.5 RMSprop
Adadelta의 다른 버전이다.
4.6 Adam
2nd momentum만 사용하는 Adagrad, Adadelta와 달리 1st momentum도 사용한다. 두 momentum의 값이 0으로 쏠리는 현상이 있어 momentum을 변형해 사용한다. 실험적으로 가장 성능이 좋다.
4.7 AdaMax
Adam의 2nd momentum (\(l_2\) norm) 대신 \(l_\infty\) norm을 사용해 momentum의 값이 0으로 쏠리는 현상을 방지했다. \(l_\infty\) norm이 max 연산으로 정의되므로 AdaMax라는 이름이 붙었다.
4.8 Nadam
Adam + NAG
어떤 optimization algorithm을 사용할 지 고민이라면 일단 Adam을 쓰자.
4.1 Momentum
Local optima 주변에는 다음과 같은 계곡(ravine) 형태의 곡면이 자주 발생한다. SGD는 이러한 ravine에서 진동하게 되며 느리게 수렴한다.
Momentum은 SGD의 진동 현상을 줄여주고 진행 방향으로의 수렴을 가속시킨다. 현재 step의 업데이트 벡터에 이전 step의 업데이트 벡터에 \(\gamma\)를 곱한 값을 더해 사용한다. (\(\gamma < 1\))
$$\begin{align}v_t&=\gamma\, v_{t-1}+\eta\nabla_\theta J(\theta) \\ \theta&=\theta-v_t\end{align}$$
4.2 Nestrov accelerated gradient (NAG)
Momentum이 진행 방향으로 무작정 가속시켜주었다면 NAG는 다음 step의 그래디언트를 예측해 local minima에 가까워지면 수렴 속도를 미리 줄여준다. 미래 예측 능력을 가진 momentum이라고 보면 된다.
$$\begin{align}v_t&=\gamma \, v_{t-1}+\eta\nabla_\theta J(\theta-\gamma\, v_{t-1}) \\ \theta&=\theta -v_t \end{align}$$
4.3 Adagrad
파라미터 각각의 희소 정도에 따라 파라미터마다 다른 learning rate를 사용하도록 한다. 즉, 이전 업데이트들에서 작은 그래디언트 값을 가진 파라미터들에 더 큰 learing rate를 부여해 각 파라미터의 변화율이 비슷하도록 한다. 그러면 희소 특성들도 잘 학습.
식을 간략히 표기하기 위해 그래디언트를 \(g\)로 표기한다:
$$g_{t, i}=\nabla_{\theta_t}J(\theta_{t, i})$$
$$\theta_{t+1, i}=\theta_{t, i}-\frac{\eta}{\sqrt{G_{t, ii}+\epsilon}}\odot g_{t, i}$$
\(G_t\in\mathbb{R}^{d\times d}\)는 diagonal matrix이다. 원소 \(i, i\)는 \(\theta_i\)의 step \(t\) 까지의 그래디언트 제곱을 모두 더한 값이다. \(\epsilon\)은 divide-by-zero 에러를 피하기 위한 매우 작은 값이다.
위 식을 다음과 같이 벡터 식으로 표현할 수 있다. (\(\odot\) : element-wise matrix-vector multiplication)
$$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{G_t+\epsilon}}\odot g_t$$
Step \(t\)가 증가할수록 \(G_t\)에 축적되는 값이 커진다. 그러므로 어느 순간부터는 learning rate가 \(0\)에 매우 가까워져 모델이 학습되지 않는다. 다음에 소개되는 Adadelta는 이러한 문제점을 해결하였다.
4.4 Adadelta
Adagrad의 learning rate 소실 문제를 해결하기 위해 Adadelta는 최근 \(w\)개의 그래디언트만 사용하기로 한다. 하지만 과거의 그래디언트를 저장하는 것은 비효율적이므로 대신 다음과 같이 running average를 정의하여 사용한다.
$$E\left[g^2\right]_t=\gamma E\left[g^2\right]_{t-1}+(1-\gamma)g^2_t$$
\(\gamma\)는 momentum과 비슷하게 0.9 정도를 사용한다. 이제 파라미터 업데이트 식은 다음과 같다.
$$\theta_{t+1}=\theta_t+\Delta\theta_t=\theta_t-\frac{\eta}{\sqrt{E\left[g^2\right]_t+\epsilon}}g_t$$
분모의 값은 그래디언트 제곱의 평균에 루트를 씌운 것이므로 RMS(Root Mean Squared)와 같다. 그러므로, 다음과 같이 간략히 표현할 수 있다.
$$\theta_{t+1}=\theta_t+\Delta\theta_t=\theta_t-\frac{\eta}{\text{RMS}\left[g\right]_t}g_t$$
하지만 위 식은 좌우변의 단위(unit)이 맞지 않는다. 그래서 다음과 같이 정의한 또 다른 exponentially decaying average를 사용해 이를 해결하고자 했다.
$$E\left[\Delta\theta^2\right]_t=\gamma E\left[\Delta\theta^2\right]_{t-1}+(1-\gamma)\Delta\theta^2_t$$
\(\Delta\theta_t\)의 RMS 값은 step \(t\)에서 구할 수 없으므로 이전 step의 RMS 값으로 근사하여 사용한다.
$$\text{RMS}\left[\Delta\theta\right]_t=\sqrt{E\left[\Delta\theta^2\right]_t+\epsilon}\approx\text{RMS}\left[\Delta\theta\right]_{t-1}$$
이 RMS 값을 \(\eta\)값을 대신해 사용하면 다음과 같이 Adadelta의 업데이트 식을 얻을 수 있다.
$$\begin{align}&\Delta\theta_t=-\frac{\text{RMS}\left[\Delta\theta\right]_{t-1}}{\text{RMS}\left[g\right]_t}g_t \\&\theta_{t+1}=\theta_t+\Delta\theta_t\end{align}$$
식에서 알 수 있듯이 Adadelta는 기본 learning rate를 설정해줄 필요가 없다.
4.5 RMSprop
Adadelta에서 양 변의 단위를 맞추는 작업을 하기 전의 업데이트 식이다.
$$E\left[g^2\right]_t=\gamma E\left[g^2\right]_{t-1}+(1-\gamma)g_t^2$$
$$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{E\left[g^2\right]_t+\epsilon}}g_t$$
\(\gamma=0.9\), \(\eta=0.001\)이 주로 사용된다.
4.6 Adam
Adadelta와 RMSprop처럼 Adam도 adaptive learning rates(각 파라미터별 다른 learning rate)를 사용하며 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\)는 1st moment로 mean을 근사하고 \(v_t\)는 2nd moment로 uncentered variance를 근사한다. \(m_t\)와 \(v_t\) 모두 zero vector로 초기화되기 때문에 0으로 값이 쏠리는 현상이 발생한다. 때문에 다음과 같이 변형되어 사용된다.
$$\hat{m}_t=\frac{m_t}{1-\beta_1^t} \ , \quad \hat{v}_t=\frac{v_t}{1-\beta_2^t}$$
파라미터 업데이트 식은 다음과 같이 Adadelta, RMSprop과 비슷하다.
$$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat{v}_t}+\epsilon}\hat{m}_t$$
보통 \(\beta_1=0.9\), \(\beta_2=0.999\), \(\epsilon=1e-8\)이 사용된다.
4.7 AdaMax
Adam의 \(v_t\)는 \(g_{t-1}\)(\(v_{t-1}\)에 포함)와 \(g_t\)의 \(l_2\) norm이다. 이를 다음과 같이 \(l_p\) norm으로 일반화시킬 수 있다. \(\beta_2\)도 \(\beta_2^p\)로 파라미터화시켰다.
$$v_t=\beta_2^p v_{t-1}+(1-\beta_2^p)\lvert g_t\rvert^p$$
\(l_\infty\) norm을 사용하면 다음과 같이 수렴한다고 한다. Adam과 구별하기 위해 \(v_t\) 대신 \(u_t\)를 사용한다.
$$u_t=\beta_2^\infty v_{t-1}+(1-\beta_2^\infty)\lvert g_t\rvert^\infty=\max\left\{\beta_2 v_{t-1}, \lvert g_t\rvert\right\}$$
이를 Adam의 업데이트 식에 \(\sqrt{\hat{v}_t}+\epsilon\) 대신 사용하면 AdaMax의 업데이트 식이 된다.
$$\theta_{t+1}=\theta_t-\frac{\eta}{u_t}\hat{m}_t$$
\(u_t\)가 max 연산을 사용하므로 \(m_t\)처럼 0으로 쏠리는 현상이 발생하지 않는다. 보통 \(\eta=0.002\), \(\beta_1=0.9\), \(\beta_2=0.999\)를 사용한다.
4.8. Nadam
Adam + NAG(Nesterov Accelerated Gradient)이다. 유도 과정은 꽤 길기 때문에 논문을 참고하길 바란다.
$$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{\hat{v}_t}+\epsilon}\left(\beta_1\hat{m}_t+\frac{(1-\beta_1)g_t}{1-\beta_1^t}\right)$$
4.9 Visualization of Algorithms
Beale loss function과 saddle point에서 각 알고리즘을 테스트한 결과, adaptive leraning rate 방식을 사용하는 알고리즘들이 훨씬 잘 작동함을 확인할 수 있었다.
4.10 Which optimizer to use?
일단 Adam을 쓰자.
5. Parallelizing and distributing SGD
생략
6. Additional strategies for optimizing SGD
6.1 Shuffling and Curriculum Learning
일반적으로, 학습 데이터의 순서가 유의미하게 정렬된 상태로 모델을 학습시키면 모델이 편중되어 학습된다. 매 epoch마다 모델의 순서를 랜덤하게 섞어주는 것이 좋다.
6.2 Batch normalization
Regularization과 weight initialization 문제를 한 번에 해결할 수 있다.
6.3 Early stopping
Validation error가 더 이상 개선되지 않을 때 학습을 임의로 중지시킬 수 있다.
6.4 Gradient noise
업데이트 시, 그래디언트에 Gaussian noise를 추가하면 initialization에 영향을 덜 받으며 깊고 복잡한 모델의 학습에 도움이 된다고 한다.
$$g_{t, i}=g_{t, i}+N(0, \sigma_t^2) \ , \quad \sigma_t^2=\frac{\eta}{(1+t)^\gamma}$$
노이즈를 추가하면 새로운 local minima를 탐색할 수 있어서라는 추측이 있다. 특히 깊은 모델일수록 새로운 local minima를 탐색해낼 가능성이 높아진다.