![[Review] An overview of gradient descent optimization algorithms](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdwYxRp%2FbtrrunIbNib%2FJEZpmbOxkjPM2UUNUGi2C1%2Fimg.png)
An overview of gradient descent optimization algorithms
최적화 알고리즘에 대한 내용이 담긴 An overview of gradient descent optimization algorithms Paper에 대해 정리해보려고 한다.
◼ 논문 링크 : An overview of gradient descent optimization algorithms
경사하강법은 최적화를 수행하는 가장 널리 사용되는 알고리즘 중 하나이며 신경망을 최적화하는 가장 일반적인 방법이다. 하지만 이러한 알고리즘은 강점과 약점에 대한 실제적인 설명이 나오기 어렵기 때문에 종종 블랙 박스 최적화 프로그램으로 사용된다.
경사 하강법(Gradient descent)
Gradient descent는 $\theta $를 미지수로 갖는 목적함수 $J(\theta)$ 를 최소화시키는 방법이다.
✔ 어떤 위치에 있는 $\theta $ 를 그 위치에서의 gradient인 $\bigtriangledown_{\theta } J(\theta)$의 반대 방향으로 이동시켜준다.
✔ 일반적인 gradient descent의 업데이트 식은 다음과 같다.
$\theta_{t+1} = \theta_{t} - \eta \bigtriangledown_{\theta } J(\theta)$
여기서 $\eta$는 learning rate로 gradient 반대 방향으로 얼마나 업데이트할 것인지 결정한다.
✔ 작은 $\eta$ 는 수렴 속도를 늦출 것이고, 큰 $\eta$ 는 minimum을 그냥 지나쳐버릴 수 있고 심하면 발산한다.
다양한 경사 하강법(Gradient descent variants)
목적 함수의 기울기를 계산하는데 사용하는 데이터의 양이 다른 경사 하강법에는 세 가지 변형이 있다.
데이터의 양에 따라 매개 변수 업데이트의 정확성과 업데이트를 수행하는 데 걸리는 시간간에 균형을 맞춘다.
1. Batch gradient descent
전체 training dataset으로 파라미터 $\theta $ 에 대한 비용 함수의 기울기를 계산한다.
$\theta $ 는 파라미터, 는 학습률, $\bigtriangledown $ 은 미분을 의미한다.
한 번의 업데이트를 위해 모든 데이터가 계산에 포함되므로 속도가 느리고, memory에 적합하도록 dataset을 다루기가 어렵다. 또한 손실함수가 convex할 경우 global minimum 수렴을 보장하고, nonconvex일 경우 local minimum이 보장된다. non-convex surface에서 local minimum에 빠지면 벗어나기 어렵다.
batch gradient descent는 전체 dataset으로 기울기를 계산하기 때문에 불필요한 연산을 수행한다.
for i in range(nb_epochs):
params_grad = evaluate_gradient(loss_function, data, params)
params = params - learning_rate * params_grad
2. Stochastoc gradient descent(SGD)
SGD는 한 번의 파라미터 업데이트를 위해 하나의 훈련 데이터를 사용한다.
SGD는 하나의 data로 매개변수(파라미터)를 한번 갱신하므로 불필요한 연산을 하지 않는다. 따라서 SGD는 batch gradient보다 훨씬 빠르게 업데이트가 진행되며 온라인 학습에도 사용할 수 있다.
SGD는 높은 편차로 빈번하게 갱신을 수행하므로 아래 그림과 같이 비용 함수가 크게 변동한다.
SGD는 local minimum에 빠졌을 때 큰 변동으로 이를 빠져나오고 새로운 local minimum을 찾을 수 있다. 하지만 크게 변동하므로 정확한 값에 수렴하기가 어렵다는 것을 의미한다. 그렇지만 learning rate를 천천히 낮춰 주어 수렴하도록 할 수 있다.
for i in range(nb_epochs):
np.random.shuffle(data)
for example in data:
params_grad = evaluate_gradient(loss_function, example, params)
params = params - learning_rate * params_grad
3. Mini-batch gradient descent
Mini-batch gradient descent는 n개의 training examples로 묶인 Mini-batch에 대하여 기울기를 계산하고 매개변수(파라미터)를 갱신한다.
이 방법으로 (a) 더 안정한 수렴을 이끌 수 있도록 매개변수 갱신의 분산을 감소시킨다. (b) mini-batch에 대해 고도로 최적화된 matrix를 사용하여 딥러닝 프레임워크를 사용할 수 있기 때문에 비용 함수의 기울기를 효율적으로 계산할 수 있다.
일반적인 미니 배치 크기는 50에서 256 사이이지만 애플리케이션에 따라 다를 수 있다.
미니 배치 경사 하강 법은 일반적으로 신경망을 훈련 할 때 선택하는 알고리즘이며 SGD라는 용어는 일반적으로 미니 배치를 사용할 때도 사용된다.
<크기가 50 인 미니 배치를 반복>
for i in range(nb_epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size=50):
params_grad = evaluate_gradient(loss_function, batch, params)
params = params - learning_rate * params_grad
우리는 batch_size 인자를 넘겨 mini-batch 사이즈를 결정하고, 최적화 알고리즘은 mini batch 사이즈의 데이터마다 손실함수를 만들고 gradient를 계산하여 파라미터를 업데이트한다. 당연히 batch GD보다 업데이트 속도가 빠르고, gradient의 크기도 들쭉날쭉하지 않다.
도전 과제(Challenges)
vanilla mini-batch gradient descent는 해결해야할 문제점들이 있다.
1. 적절한 learing rate를 선정하는 것은 어려울 수 있다.
learning rate가 너무 작으면, 수렴하는데 오랜 시간이 필요하다. 반대로 너무 크면, 최소값 근처에서 변동하거나 심지어 벗어날 수 있어 수렴을 방해한다.
2. Learning rate schedule을 사용하여 학습 도중 learning rate를 조정할 수 있다.
사전 정의된 스케줄에 따라 learning rate를 감소시키거나, 매 epoch마다 loss가 임계값 아래로 떨어지면 learning late를 감소시키는 방법이 있다. 하지만 이 두 방법은 스케줄과 임계값이 사전에 정의되어야 하며, dataset의 특성에 맞지 않는다.
3. 모든 파라미터에 대해 동일한 learning rate를 적용해준다.
만약 데이터가 sparse하고 features가 매우 다른 빈도수를 지니고 있으면, 이 모든 것들을 동일한 정도로 갱신하면 안된다. 드물게 발생하는 feature에 대해서는 큰 갱신을 수행해야 한다.
4. 최적이 아닌 (국소 극소값)local minima와 안장점(saddle point) 빠질 위험이 있다.
안장점은 평면으로 둘러싸여 있으므로 기울기가 0인 지점을 의미한다. 안장점이 최소값이 아니더라도 0의 기울기를 지니고 있으면, 파라미터는 갱신되지 않는다.
경사 하강법 최적화 알고리즘(Gradient descent optimization algorithms)
앞서 언급 한 과제를 해결하기 위해 널리 사용되는 몇 가지 알고리즘에 대해 설명한다.
1. Momentum 모멘텀
SGD는 기울기가 높은 평면에서 최적값을 향해 잘 찾아가지 못한다. 위의 그림처럼 경사도의 기울기를 따라 왔다갔다 하는 것을 확인할 수 있다. Momentum은 최적값의 방향으로 SGD가 가속하도록 도와주고 그림에서 보이는 진동을 완화시키는데 도움을 주는 방법이다. Momentum은 현재 파라미터를 업데이트해줄 때 이전 gradient들도 계산해 포함해주면서 문제를 해결한다.
SGD 수식에서 모멘텀 항인 $\gamma v_{t-1}$를 추가적으로 빼주는 것을 확인할 수 있다.
이 변수가 내리막길에서는 가속하도록 도와주고, 방향이 바뀌었을 때 파라미터가 갱신하는 양을 감소시켜준다.
는 보통 0과 1사이의 값이기 때문에 이런 식으로 점점 오래된 gradient의 영향력을 줄이며 모멘텀을 만든다. 값은 주로 0.9를 사용한다.
Momentum의 힘 덕분에 이제 SGD는 관성을 사용해서 낮은 언덕정도는 탈출할 수 있게 되었다. 이는 SGD가 낮은 local minimum에서 벗어나 손실함수를 더 탐험할 수 있게 만들어준다.
2. Nesterov accelerated gradient(NAG)
NAG는 멈춰야할 시기에 더 나아가지 않고 제동을 거는 방법이다.
NAG는 비용 함수의 기울기를 계산할 때, 매개변수에 이전 모멘텀을 빼주어 다음 위치를 근사화하여 비용함수의 기울기를 계산한다. 즉, 현재 파라미터로 기울기를 계산하는 것이 아니라 파라미터의 다음 위치의 근사치로 기울기를 계산하는 것이다. 그 말은 이전에 계산된 모멘텀항에서 다음 매개변수의 위치를 예측한다는 의미이다.
Momentum 방법과 비교하면,
Momentum은 현재 기울기를 계산하고 모멘텀을 적용시켜 그 방향으로 크게 이동한다. NAG는 Momentum 위치에서 다음 위치를 예측하여 파라미터를 갱신한다. 그림에서 보듯이 NAG는 Momentum과 비교하여 보면 상대적으로 느린 속도로 값이 갱신된다는 것을 확인할 수 있고, 너무 빠르게 기울기가 수정되는 것을 방지할 수 있다. 그리고 NAG는 RNN의 성능을 크게 증가시켰다.
3. Adagrad(Adaptive subgradients)
Adagrad는 빈번하게 등장하는 매개변수는 적게 갱신하고 드물게 등장하는 매개변수는 크게 갱신하는 그래디언트 기반 최적화를위한 알고리즘이다. 모든 매개변수가 동일하게 갱신되는 것이 아니라 매개변수의 빈도수에 따라 가중치를 부여하여 갱신한다. 이러한 이유로 sparse data를 다루기 위해 매우 적합하다. 또한 Adagrad가 SGD의 견고성을 크게 향상시켰다고 한다.
이전까지 모든 매개변수는 동일한 학습률(learning rate)을 사용하여 갱신했지만, Adagrad는 매번 각각의 매개변수에 서로 다른 학습률을 사용한다.
$g_{t,i}$는 시점에서 $\theta _{t,i}$에 대한 gradient 벡터이다.
SGD의 업데이트 식은 아래와 같다.
Adagrad는 다음과 같은 업데이트식을 사용한다.
는 대각 요소가 t시점 까지의 각 매개변수의 기울기의 제곱합이다.
$\varepsilon$은 분모가 0이 되는 것을 방지해주는 용도로 $10^{-8}$와 같이 아주 작은 값을 사용한다.
그리고 제곱근 연산이 없으면 알고리즘이 훨씬 더 나빠진다.
는 i번 째 대각원소로 시점까지의 $\theta _{i}$에 대한 gradient들의 제곱의 총합을 갖는 대각행렬이다. 그래서 elementwise matrix vector 곱을 이용하여 정리할 수 있다.
Adagrad의 주요 이점 중 하나는 학습률을 수동으로 조정할 필요가 없다는 것이다. 대부분의 구현은 기본값 0.01을 사용하고 그대로 두며, $G_{t}$가 자동으로 학습률을 조정해준다.
Adagrad의 단점은 분모에 제곱된 기울기가 계속 축적된다는 것이다. 추가 된 모든 항이 양수이므로 training 동안 계속 값이 커진다. 이것은 학습률이 점점 줄어들게 하고 결국 학습률은 매우 작아져 알고리즘이 더 이상 추가 지식을 획득 할 수없는 상황이 된다.
다음에 배울 Adadelta는 Adagrad의 단점을 보완한 방법이다.
4. Adadelta
Adadelta는 Adagrad의 확장된 버전이다.
해결하고자 한 문제점
1. Adagrad에서 발생한 iteration 마다 learning rate가 작아지는 문제
2. Hyperparameter인 learning rate($\eta $)의 필요
Adadelta는 을 해결하기 위해 크기 인 window를 사용한다.
- 즉, 지난 모든 gradient의 정보를 저장하는 것이 아니고 지난 w개의 gradient 정보만을 저장한다.
비효율적으로 이전의 제곱된 기울기를 저장하여 평균을 계산하지 않고, 이전에 제곱된 기울기의 이동 평균을 이용하여 평균을 계산한다. 가중 평균 $E[g^2]_{t}$ 는 t 시점에서 이전까지의 평균과 현재 기울기만을 이용한다.
$\gamma$는 보통 모멘텀항과 비슷한 0.9로 설정한다.
위 수식에서 볼 수 있듯이 이동 평균을 이용한다. 이전 시점까지의 평균값의 0.9비율과 갱신될 제곱된 기울기 0.1 비율을 더해주어 평균을 계산한다.
Adadelta에서는 매개변수의 변화량 을 이용하여 수식을 표현한다. 아래는 SGD에서의 수식을 매개변수 변화량으로 표기한 것이다.
Adagrad의 매개 변수 업데이트 벡터는 다음과 같다.
이동 평균을 이용하는 Adadelta에서 매개변수 변화량은 다음과 같다.
분모가 기울기의 root mean squared(RMS)이므로 다음과 같이 표현할 수 있다.
Adadelta 논문 저자는 SGD, Momentum, Adagrad, Adadelta에서 이 업데이트 단위가 일치하지 않는 다는 문제점이 있다고 말한다. 이를 해결하기 위해 또 다른 가중 평균을 정의한다.
제곱된 기울기가 아니라 제곱된 매개변수를 이용하여 갱신한다.
따라서 매개변수의 RMS(root mean squared)는 다음과 같이 정리된다.
최종적으로 매개변수의 변화량을 이용해서 Adadelta 식을 정리해보면 다음과 같다.
Adadelta를 사용하면 업데이트 규칙에서 제거되었으므로 기본 학습률을 설정할 필요 없다.
5. RMSprop
RMSprop은 Geoff Hinton이 Coursera Class 6e 강의 에서 제안된 방법 이다.
RMSprop와 Adadelta는 Adagrad의 학습률이 소실되는 문제를 해결하기 위해 발전되었다.
RMSprop는 Adadelta의 첫 번째 수식과 동일하다.
RMSprop는 학습률을 지수 적으로 감소하는 평균 제곱 기울기로 나눈다.
$\gamma$ = 0.9, 학습률($\eta $) = 0.001로 제안한다.
6. Adam(Adaptive Moment Estimation)
Adam(Adaptive Moment Estimation)은 각각의 매개변수에 학습률을 다르게 계산하는 또 다른 방법이다.
Adadelta와 RMSprop와 같이 과거의 제곱된 기울기 $v_{t}$ 의 지수적으로 감소하는 가중 평균을 적용할 뿐만 아니라, Momentum과 비슷하게 과거의 기울기 $m_{t}$ 의 지수적으로 감소하는 가중 평균을 적용한다.
$m_{t}$ 는 기울기의 1차 모멘트(평균)의 추정량이고 $v_{t}$는 기울기의 2차 모멘트(분산)의 추정량 입니다.
$m_{t}$ 와$v_{t}$ 는 0으로 초기화 되기 때문에, 학습 초기때와 decay rate($\beta_{1} , \beta_{2} $가 1에 가까울 때)가 매우 작을 때 이들은 0으로 편향되어 있다. 이를 해결하기 위해 편향이 수정된 1차 모멘트와 2차 모멘트의 추정값을 이용한다.
다음과 같이 수정함으로써 초기에 0으로 편향되어 있는 것을 예방할 수 있다.
Adam은 위 수식을 Adadelta와 RMSprop에서 보았던 매개변수 갱신에 사용된다.
논문에서는 $\beta_{1} $ = 0.9, $\beta_{2} $ = 0.999, $\epsilon $ = $10^{-8}$을 제안한다.
7. AdaMax
Adam에서 $v_{t}$ 를 계산할 때, $v_{t-1}$ 항과 현재 기울기의 $l_2$ norm을 이용한다.
$l_2$ norm을 norm으로 확장할 수 있다.
여기서 $\beta_{2}^p$는 $\beta_{2}$ 의 p제곱이 아니고 그냥 계수의 노테이션이다.
p가 큰 값을 가지면 수치적으로 불안정해지므로 보통 $l_1$ norm, $l_2$ norm을 이용한다.
하지만 p = $\infty $ 일때, $l_{\infty} $ norm은 좀 더 안정적으로 수렴한다고 한다.
Adam과 혼동을 피하기 위해 $v_{t}$ 대신 $u_{t}$를 사용하여 표기한다.
$u_{t}$ 는 max 연산에 의존하므로 Adamax라는 이름이 붙여졌고, max 연산이므로 $m_{t}$와 $v_{t}$가 0에 편향을 지니지 않는다.
최종적인 업데이트 식은 다음과 같다.
논문에서는 $\beta_{1} $ = 0.9, $\beta_{2} $ = 0.999, $\eta $ = 0.002 을 제안한다.
8. Nadam(Nesterov-accelerated Adaptive Moment Estimation)
Adam은 RMSprop와 momentum의 결합으로 볼 수 있다. RMSprop는 제곱된 기울기 $v_{t}$ 의 가중 평균을 이용하였고, momentum은 기울기 $m_{t}$의 가중 평균을 이용했다. Nesterov accelerated gradient(NAG)는 SGD보다 성능이 더 좋았다.
Nadam(Nesterov-accelerated Adaptive Moment Estimation)은 Adam과 NAG가 결합된 것이다. NAG를 Adam으로 통합시키기 위해서 momentum항인 $m_{t}$ 를 수정해야 한다.
첫 번째로, momentum update rule을 복습해보면 다음과 같다.
J는 비용함수이고, $\gamma$ 는 momentum decay term, $\eta$ 는 학습률 이다.
세번째 식을 확장해 보면 다음과 같다.
이 수식은 이전의 momentum vector와 현재 기울기의 방향을 고려한다.
NAG는 기울기를 계산하기 전에 momentum을 매개변수에 빼주어 $g_{t}$ 를 계산하기 때문에, 기울기 방향으로 더 정확하게 나아갈 수 있다. 따라서 NAG 처럼 $g_{t}$ 를 수정해주면 된다.
Dozat는 다음의 방법으로 NAG를 수정하는 것을 제안한다.
momentum step을 두 번 적용(한번은 기울기 $g_{t}$ 를 갱신할 때, 두 번째는 매개변수 $\theta _{t+1}$ 을 갱신할 때)하는 것보다 현재 매개변수를 갱신하기 위해 직접적으로 현재의 momentum vector를 적용할것이다.
매개변수를 갱신할 때 $m_{t-1}$이 아닌 $m_{t}$를 적용했다. Adam에 Nesterov momentum을 적용시키기 위해 이전 momentum vector를 현재 momentum vector로 바꿔주면 된다.
첫 번째로, Adam 업데이트 규칙은 다음과 같다.
세번째 식을 확장하면 다음과 같다.
$\frac{\beta _1 m_{t-1}}{1- \beta _1^t}$ 는 이전 시간 단계의 운동량 벡터에 대한 편향 보정 된 추정값이다. 이것을 $\hat{m}_{t-1}$로 대체 할 수 있다.
최종적으로 Nadam 식은 다음과 같다.
Visualization of algorithms
Adagrad, Adadelta 및 RMSprop는 거의 즉시 올바른 방향으로 향하고 비슷하게 빠르게 수렴하는 반면 Momentum과 NAG는 트랙을 벗어나 언덕을 따라 굴러 내려 오는 공의 이미지를 볼 수 있다. 그러나 NAG는 앞을 내다보고 최소한으로 향함으로써 반응성이 향상되어 신속하게 경로를 수정할 수 있다.
안장 지점에서 알고리즘의 동작을 보여준다. 한 차원이 양의 기울기를 갖는 반면 다른 차원은 음의 기울기를 가지므로 앞에서 언급했듯이 SGD에 어려움이 있다. SGD, Momentum 및 NAG는 대칭을 깨는 것이 어렵다는 것을 알 수 있다. Adagrad, RMSprop 및 Adadelta는 빠르게 음의 경사로 내려간다.
Adagrad, Adadelta, RMSprop 및 Adam이 가장 적합하며 이러한 시나리오에 가장 적합한 수렴을 제공한다.