플로라도의 data workout
딥러닝 optimizer정리 - An overview of gradient descent optimization algorithms 논문 리뷰 본문
딥러닝 optimizer정리 - An overview of gradient descent optimization algorithms 논문 리뷰
플로라도 2023. 11. 7. 22:27리뷰 논문 : https://arxiv.org/pdf/1609.04747.pdf
논문 내용 외에도, cs231n lecture 6,7 - Traning Neural Networks I,II 유튜브에 제공된 조경훈 교수님 딥러닝 강의 : https://www.youtube.com/watch?v=s8dzhdJ3fqg& 등을 다수 참고하였습니다.
1. Abstract
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 regard to the behaviour of different algorithms that will allow her to put them to use. In the course of this overview, we look at different variants of gradient descent, summarize challenges, introduce the most common optimization algorithms, review architectures in a parallel and distributed setting, and investigate additional strategies for optimizing gradient descents.
본 논문에서는 대중적인 인기를 끌고있는 서로 다른 optimizer에 대하여 black box로 사용될 뿐만 아니라, 강점과 약점에 대한 실용적인 설명을 알기 어렵다고 지적하며, 이에 대해 직관을 제공하고 , optimizer의 challenge와 parallel and distributed setting 아키텍쳐, 그리고 gradient descents를 최적화하는 추가적인 전략들에 대해서 다루며 전반적인 overview 제공에 목적이 있다고 밝힌다.
gradient descent를 최적화(optimization)하는 전략들
본 논문 리뷰를 본격적으로 시작하기 앞서, 위의 슬라이드를 먼저 소개하고자 한다.
옵타마이저들의 특징을 직관적으로 가장 잘 설명한 슬라이드라고 생각한다, 딥러닝 관련 자료 이곳 저곳에서 자주 등장하는 슬라이드기도 하다. 경사하강법(graident descent;:GD)을 시작으로 경사하강법의 변형들의 각 아이디어와 계보(taxanomy)에 대해 잘 나타내고 있다.
현재는 Adam이후에 AdamW(decoupled weight decay regularization, 2017) 이 등장하여 주로 AdamW와 SGD, SGD with Momentum을 주로 사용하는데, 각 옵티마이저의 Motivation은 무엇이고 어떤 문제 때문에 또 다음 옵티마이저가 등장한것일까.
본 논문, 'An overview of gradient descent optimization algorithms ' 을 리뷰하면서 천천히 살펴보도록 하자.
슬라이드가 보여주듯, Gradient Descent를 베이스로한 여러 다양한 변형들이 있고,
계보에서 보여지는 이러한 경사하강법의 변형들(Gradients Descent Varaints)은 이전보다 더 나은 optimizer로서 등장한 것일 것이다.
그런데 여기서 질문이 생긴다.
어떤게 더 나은 Optimizer라는 걸까?
'좋다' 라는것은 무어라는 걸까?
좋은 optimizer에 대하여 몇가지 사항을 정리하면 다음과 같다.
1. 수렴속도
모델을 언제까지고 학습을 시킬 순 없을것이다. 좋은 옵티마이저는 빠른 수렴속도를 보장해야 한다.
2. 수렴 안정성
weight의 초기값과 learning rate의 변화에도 불구하고, 안정적인 수렴이 가능해야 한다.
3. 일반화 성능
특정 상황에 국한되지 않고 여러 상황에도 잘 적용가능해야 한다.
4. 하이퍼 파라미터 튜닝의 용이성
gradient descent의 경우 step_size로 표현되는 learning rate 단 하나만 조정해주면 되어 튜닝이 용이했다.
이러한 하이퍼 파라미터가 튜닝하기 용이해야 좋은 옵티마이저라고 말할 수 있을것이다.
5. 연산 리소스 사용
옵티마이저의 연산은 적고 가벼울수록 리소스적인 측면에서 더 좋다라고 이야기할 수 있을것이다.
gradient descent 이후 개선된 버전의 optimizer들은 아마도 다음의 목적중 하나 이상을 달성하기 위해서 이전 optimizer들을 개선해 갔을 것이다. 각 optimizer들의 update 방법과 Motivation을 살펴보자.
2. Introduction
Gradient descent is a way to minimize an objective function J(θ) parameterized by a model’s parameters θ ∈ R d by updating the parameters in the opposite direction of the gradient of the objective function ∇θJ(θ) w.r.t. to the parameters. The learning rate η determines the size of the steps we take to reach a (local) minimum. In other words, we follow the direction of the slope of the surface created by the objective function downhill until we reach a valley.
Gradient descent(경사하강법)은 objective function(목적 함수)를 최소화시키는 방법으로, 목적 함수를 모델 파라미터에 대한 gradient 값을 계산해 파라미터를 gradient의 반대 방향으로 업데이트 시키는 방법이다. learning rate;: eta를 스텝사이즈로, 목적 함수를 downhill로, 이동방향을 slope of surface로 묘사하고 있다.
묘사를 충분히 따르고 있는 그림이다. 우리는 objective function downhill의 slope를 따라 minima를 찾아가고자 한다.
gradient의 반대방향으로만 가면 정말 minima를 찾아 갈 수 있을까?
그런데, gradient의 방향이라는 것은 무엇을 의미하는가? 어떤 방향이길래 반대방향으로 가면 minima를 찾아가는 것인가?
$time step = t$ 에서의 gradient는 다음과 쓸 수 있다.
$$g_t = \nabla_\theta f(\theta_t)$$
여기서 $f$는 objective function을 의미한다.
$$\nabla f = \left[ \frac{\partial f}{\partial \theta_1}, \frac{\partial f}{\partial \theta_2}, \ldots, \frac{\partial f}{\partial \theta_n} \right]^T$$
gradient, 경사도 벡터의 요소값들은 각 파라미터의 편미분 값들로 구성되어 있다.
다시 말해, 경사도벡터(gradeint)라는 것은 다변수 스칼라 함수의 편미분 계수를 요소로 가진다.
여기서 다변수 스칼라 함수 라는 것은, $X_i=[x_1,x_2... x_n]$과 같이 feature 여럿으로 훈련 샘플이 구성되고, 각 훈련 샘플을 통해 loss function의 loss값을 수치 하나로, 다시말해 scala 로 구할 수 있다는 일반적인 ML/DL의 상황과 같은 의미이다.
이러한 gradient는 특정 $time\,step$의 $\theta$에 대해서 함수 f가 최대로 증가하는 방향을 가르킨다. 그 gradient가 나타내는 방향은 loss surface에서 해당점에서 그은 접평면(hyper-plane)의 법선 벡터 방향과 같다.
gradient 반대방향으로 가서 minima에 도달하고자 하는 것은,
국소적인 변화에 대하여 이러한 방향(함수값이 최대로 증가하는 방향)의 반대로 감으로서 minima에 가고자 하는 것이다.
반대 방향으로 감으로써 함숫값이 줄어드는 것, 다시말해 손실함수 값이 줄어 드는 것은 다음의 테일러 전개를 이용하여 증명할 수 있다.
gradient descent의 update rule은 다음과 같고
$$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta \nabla f(\boldsymbol{\theta}_t)$$$$\boldsymbol{\theta}_{t+1} - \boldsymbol{\theta}_t = - \eta \nabla f(\boldsymbol{\theta}_t)$$
테일러 전개의 1차 근사식은 다음과 같다.
$$f(\boldsymbol{\theta} + \Delta\boldsymbol{\theta}) \approx f(\boldsymbol{\theta}) + \nabla f(\boldsymbol{\theta})^T \Delta\boldsymbol{\theta}$$
이때, ${\theta} + \Delta\boldsymbol{\theta}$를 다음time step의 파라미터 $\theta$라고 하면 $\theta_{t+1}$이라고 쓸 수 있다.
$$f(\boldsymbol{\theta}_{t+1}) \approx f(\boldsymbol{\theta}_t) + \nabla f(\boldsymbol{\theta}_t)^T (\boldsymbol{\theta}_{t+1} - \boldsymbol{\theta}_t)$$$$f(\boldsymbol{\theta}_{t+1}) \approx f(\boldsymbol{\theta}_t) + (\boldsymbol{\theta}_{t+1} - \boldsymbol{\theta}_t)\nabla f(\boldsymbol{\theta}_t)^T$$위의 gradient descent의 learning rule을 대입하면 다음과 같다.
$$f(\boldsymbol{\theta}_{t+1}) \approx f(\boldsymbol{\theta}_t) - \eta \|\nabla f(\boldsymbol{\theta}_t)\|^2$$
즉 gradient descent의 learning rule로 파라미터 업데이트를 하면 , objective function감소를 보장한다는 것을 테일러 전개로 설명할 수 있다. 벡터의 노름은 반드시 양수이고, 양수를 빼게 된다면
$f(\boldsymbol{\theta}_{t+1})$ 는 $f(\boldsymbol{\theta}_{t})$ 보다 반드시 작은값을 가지게 된다.
3. Gradient Descent Variants
gradient descent의 변형에는 세가지 종류가 있다.
이것은 objective function에 대한 gradient를 계산할 때, 데이터를 얼마나 사용할지에 따라 차이가 있다.
데이터의 양에 따라, 파라미터 업데이트의 속도와 정확도 사이의 trade-off관계가 발생한다.
아래의 분류에서는 일반적으로 (1)gradient descent(;:G.D) 라고 이야기하는 것을 (2)stochastic gradient descent와 (3)mini-batch gradientdescent와 구분하기 위하여 (1)Batch gradient descent라고 표기한다.
3-1. (Batch)Gradient Descent
$$\theta_{t+1} = \theta_t - \eta \nabla_\theta J(\theta)$$
Vanilla gradient descent / (Full) batch gradient descent는 parameter들을 업데이트할 때, 모든 train dataset의 데이터를 사용한다. (use whold dataset to perform just one update)
batch gradient descent를 사용하면 convex error surface에서 global minimum으로 무조건 수렴하고, non-convex surfaces에서는 local minimum으로 수렴 가능하다.
의사 코드(psuedo code)는 다음과 같다.
for i in range(epochs):
params_grad = evaluate_gradient(loss_function, data, params)
params = params - learning_rate * params_grad대부분의 딥러닝 라이브러리들은 자동 미분(automatic differentiation)을 제공한다. 대게는 evaluate_gradient라는 이름으로 gradient의 별도 계산 없이 다음과 같은 코드로 사용하게 된다.
(pytorch implementation)
for i in range(epochs):
# Forward pass: 데이터를 모델에 전달하여 예측을 수행하고 손실을 계산한다.
loss = model.forward(data)
# Backward pass: 자동미분을 사용하여 손실 함수에 대한 파라미터의 그래디언트를 계산한다.
loss.backward()
# 파라미터를 업데이트한다 (예: SGD, Adam 등의 옵티마이저를 사용).
optimizer.step()
# (옵션) 옵티마이저가 내부 상태를 가지고 있다면, 그래디언트를 0으로 초기화한다.
optimizer.zero_grad()
3-2 . Stochastic Gradient Descent
$$\theta_{t+1} = \theta_t - \eta \nabla_\theta J(\theta;x^(i);y^)(i))$$
Stochastic Gradient Descent는 하나의 데이터 마다 업데이트가 일어나기 때문에 학습이 굉장히 빠르다. 그러나 분산(variance)가 클 수 있기 때문에 objective function의 fluctuation(변동)이 아래 그림과 같이 심할 수 있다.
SGD의 fluctuation은 잠재적으로 더 나은 local minima로 향할 수 있다. 반면에 SGD는 계속 더 나아가기(overshooting) 때문에, 하나의 minimum으로 수렴하기 힘들다는 점도 있다. 하지만 learning rate를 점차 줄여나가면서 batch gradient descentd와 같은 수렴을 보일 수 있다고 한다.
3-3. Mini-Batch Gradient Descent
$$\theta_{t+1} = \theta_t - \eta \nabla_\theta J(\theta;x^(i:i+n);y^)(i:i+n))$$
파라미터의 업데이트를 n개의 training examples(mini-batch)마다 하는 방법이다.
파라미터 업데이트의 variance를 SGD보다 더 낮춤으로써, 더욱 안정적인 수렴을 보일 수 있다.
SGD라는 용어가 정의와는 다르게 주로 mini-batch gradient를 사용할때 주로 쓰인다.
#mini-batch GD psuedo code
for i in range(epochs):
np.random.shuffle(data)
for batch in get_batches(data, batch_size):
params_grad = evaluate_gradient(loss_function, batch, params)
params = params - learning_rate * params_gradmini-batch가 생김으로서 한번의 iteration(한번의 업데이트)가 1epoch과는 다른 의미를 갖게된다.
$$\# \text{Iterations per Epoch} = \left\lceil \frac{N}{k} \right\rceil \downarrow \\$$
$$\# \text{Iterations} = \left\lceil \frac{N}{k} \right\rceil \times \# \text{Epochs}$$
여기서 N은 전체 데이터셋의 크기, k는 배치 사이즈이고 이를 나눈것이 epoch당 iteration이 되며
epoch수를 곱해주면 전체 업데이트 횟수인 iteration횟수일 것이다.
이전까지는 gradient descent를 사용하기 위해서 데이터셋의 모든 샘플들(Full-batch)를 모델에 통과시킨후 loss function의 값을 계산했어야 했다.
그러나 mini-batch gradient descent는 그림과 같이 데이터셋의 전체 샘플이 아니라 k개의 일부 샘플만을 모델에 통과시켜 loss function의 값을 계산한다.
두번째 업데이트 부터는 이전 업데이트에서 사용되지 않은 샘플들만을 사용하여 (sampling without replacement) 비복원추출의 방식으로 또 다른 k개의 샘플을 통해 같은 과정을 반복한다. 이러한 한번의 과정을 1iteration이라고 부르고, 전체 데이터셋을 다 사용했을때 1epoch가 된다.
이러한 비복원 추출의 방식은
(1)동일한 데이터에 대해서 여러번 학습하는 것을 방지하여 일반화 성능을 꾀하고
(2)모두 한번씩, 정보를 공평하게 사용하는 효과를 갖게 된다.
4 . Challenges
mini-batch gradient descent는 항상 좋은 수렴을 보장하진 않는다.
- 적당한 learning rate를 고르기가 힘들다.
- learning rate를 adaptive하게 사용하기 위해서 learning rate schedule을 고려 할 수 있다, 그러나 learning rate schedule는 pre-defined 되기 때문에 데이터셋의 성격에 맞게 적용할 수 없다.
- 모든 parameter에 대해서 동일한 learning rate가 적용 된다. 데이터가 sparse하고, feature별 빈도가 매우 다르다면, 동일하게 update하는 것 보다는 rare한 feature를 더 업데이트 하는 것이 좋을 것이다.
- Non-convex error function을 minimize할 때, 수 많은 suboptimal local minima에 빠지지 않게 하는 것이 힘들다. 이러한 suboptimal local minima는 대게 local minima가 아니라 saddle point에 의한 영향이라는 의견이 다수 있다.
- Saddle point: slopes up/down한 dimensions이 존재하는 point (말 안장(saddle)과 같이 생김)
- Saddle point 주변에서 모든 차원의 gradient 값이 0에 가깝기 때문에 SGD를 통해 탈출하기 굉장히 힘들다고 한다.
batch_size는 어떻게 설정하는것이 좋은가?
local minima에 빠지지 않게 해야한다..! 이를 위해 batch-size를 줄여야하나..?
-> (1) 굳이 그러지 않아도 된다. learning rate의 조절에 따라 local minima는 충분히 탈출 할 수 있다.
-> (2)고차원에서는 사실, local minima에 빠지기도 쉽지 않다.
-> (3)local minima가 애초에 global minima 근처인 경우가 많다.
데이터가 noisy하다면 batch-size를 키우자. (요즘의 추세)
-> 수렴 속도가 빠르고, 그 방향도 정확할 확률이 높아지나, epoch당 업데이트 횟수는 줄어든다.
결정적인 정답은 없다. “batch-size” is hyper-parameter!
saddle point 같은 경우 그림에서 보듯 함수의 극대와 극소의 교차점을 말하고, 이는 모든 파라미터의 gradient가 0이면서 (편미분값) 두번 미분한 값 헤세 행렬의 부호가 음,양이 교차하는 경우다.
local minima의 경우 역시 모든 파라미터의 gradient가 0이지만, 두번 미분한 헤세 행렬의 부호가 모두 양수인 경우로
고차원의 공간에서 헤세행렬값이 모두 양수인경우보다, 음 양의 교차하는 경우가 많을것이라는, 다시말해 local minima보다 saddle point가 더 주요한 문제가 아니냐 라는 의견이 있다.
5 . Gradient Descent Optimization Algorithms
앞서 언급된 문제들을 해결하기 위해 사용되는 여러가지 optimization algoritm이 있다.
5-1 . Momentum
SGD는 너무 가파른 지점(주로 local optima 주변)에서 좋은 방향으로 나아가는데 문제를 겪는다. 이런 산골짜기(ravine) 같은 상황에서 oscillate(왔다 갔다하는)하며 좋은 progress를 보이지 않는다. batch-size가 작을수록 , data가 noisy할수록, 랜덤샘플링에 따른 optimal direction ;: graident의 평균;:기댓값과의 variance가 커지게 된다.
이 문제를 해결하기 위해 momentum을 사용한다. Oscillation을 줄이고 더 relevant한 방향으로 나아갈 수 있도록 한다.
$$v_{t+1} = \gamma v_t + \eta \nabla_\theta J(\theta)$$$$\theta_{t+1} = \theta_t - v_{t+1}$$
gradients가 같은 방향으로 간다면 더 빠르게, 방향이 바뀐다면 느리게 update하는 방식으로 진행된다. 결과적으로 더 빠르게 수렴하고 oscillation을 줄일 수 있다.
우리는 두개의 식을 통해, $v_t$를 통해 파라미터를 업데이트를 함으로서, 관성(momentum)과 같이 현재의 이동방향과 gradient를 고려한 업데이트를 진행하게 된다. $v_t$는 풀어서 써보면 accumulated gradient (그라디언트의 누적합)으로 표현될 수 있다.
$\nabla_\theta J(\theta)$ 를 $g$라고 하면
다음과 같이 일반화를 위하여 풀어 써보면
$v_{1} = 0.9 \cdot v_{0} + \eta \nabla g_1 \\ = \eta g_1$
$v_{2} = 0.9 \cdot v_{1} + \eta \nabla g_2 \\= 0.9 (\eta g_1) + \eta g_2)$
$v_{3} = 0.9 \cdot v_{2} + \eta g_3 \\
= 0.9 (0.9 \eta g_1 + \eta g_2) + \eta g_3 \\
= \eta g_3 + 0.9 \eta g_2 + (0.9)^2 \eta g_1$
이를 다시 일반화 하여 쓰면 다음과 같고
$$v_t = \eta \sum_{i=0}^{t} (0.9)^{t-i} g_i$$
위의 슬라이드와 같은 형태의 식으로 표현된다. ($v_t = \tilde{g_t}$)
의사 코드는 다음과 같다.
$$v_{t+1} = \gamma v_t + \eta \nabla_\theta J(\theta)$$$$\theta_{t+1} = \theta_t - v_{t+1}$$
#SGD with Momentum
vx = 0
while True:
dx = compute_gradient(x)
vx = rho * vx + dx
x += learning_rate * vx
그러나 모멘텀의 방식에는 단점이 존재하는데,
위와 같이 Sharp minima의 경우를 지나쳐버리게 된다.
(이러한 sharp minima는 overfitting된 상태로 데이터셋의 크기가 커질수록 사라지게 된다고 한다.)
그러나 우리의 목적은 이러한 상황에도 강건하고 더욱 일반적인(robust and generlaize)좋은 optimizer를 찾는 것이고,
Momentum은 이 상황에서 결국 dataset을 바꿔야만 해결이 될 것이다.
5-2 . Nesterov Accelerated Gradient (NAG)
$$v_{t+1} = \gamma v_t + \eta \nabla_\theta J(\theta - \gamma v_t)$$$$\theta_{t+1} = \theta_t - v_{t+1}$$
특이하게, 논문으로 발표된게 아니라 제프리 힌튼 교수의 코세라 강의중에 언급된 optimizer라고 한다.
공이 언덕을 내려갈 때, (a ball that rolls down a hill, blindly following the slope, is highly unsatisfactory) 공이 경사가 올라가는 부분 전에서 느려지는 더 똑똑한 공일순 없을까? NAG는 momentum term에 어느 정도의 prescience(예지)를 주는 방식이다.
딥러닝 컴퓨터 비전 강좌로 유명한 cs231n에서 Nesterov Momentum에 대해 설명하는 슬라이드이다.
좌측 Momentum의 방식처럼 actual step(파랑색 벡터)와 같이 다음 스텝의 파라미터 벡터를 구할때 $v_t$velocity vector(초록색 벡터)와
$g$ , gradient(빨강색 벡터)를 고려하여 결정되는것이 아니라,
우측 그림처럼 $g$ gradient(빨강색 벡터)를 구할때 $v_t$를 이동한지점에서의 $g$를 구하고
$v_t$와 $g$를 통해 다음 스텝의 벡터;, actual step($v_{t+1}$)을 구하게 된다.
그러나 Nesterov Momentum의 사용에 있어서는 문제가 발생하는데,
현재의 점(현재의 공의 위치) 아닌 모멘텀 스텝을 이동한점의 gardient를 신경망에서 구현하기 적합하지 않은 단점이 있다.
gradient descent의 변형은 좀 더 나은 optimizer를 찾는 과정인데, 임의로 이동한 점, ($x_{t^*}$)의 점이 추가적으로 고려되어,
역전파를 좀 더 효율적으로 계산하기 위한 그 목적에 부합하지 않아 버린다.
배보다 배꼽이 커져버리는 격이다.
그래서, 다른 방법으로 Nesterov Moemtum의 Motivation을 이용하는 벤지오의 근사적 접근 방법이 있다.
(1) NAG에서는 먼저, 예측된 위치에서 gradient를 계산했다
$\nabla_{\theta}J(\theta_t + \mu v_t)$
(2) 모멘텀과 파라미터 업데이트하고
$v_{t+1} = \mu v_t - \eta \nabla_{\theta}J(\theta_t + \mu v_t) \\$
(3) 그 다음 예측된 모멘텀을 이용해 파라미터를 업데이트 한다.
$\theta_{t+1} = \theta_t + v_{t+1}$
요슈아 벤지오(Yoshua Bengio)의 근사적 접근 방법
(1) 예측된 위치에서 gradient를 계산하지 않고, 현재 위치에서 gradient를 계산
$\nabla_{\theta}J(\theta_t)$
(2) 모멘텀을 먼저 업데이트
$v_{t+1} = \mu v_t - \eta \nabla_{\theta}J(\theta_t)$
(3) 예측된 모멘텀을 이용해 파라미터 업데이트
$\theta_{t+1} = \theta_t + (-\mu v_t + (1 + \mu)v_{t+1})$
5-3 . The Adaptive Gradient Algorithm(AdaGrad)
Adagrad는 velocity term 대신에 squared gradient term을 이용한다. 그리고 training동안 squred gradient term을 위해gradient를 keep한다.
parameter vector$\theta$를 update를 할때 앞서 계산한 gradient sqaured term(그라디언트 제곱항)으로 나눠준다.
위의 그림과 같이 loss surface가 종 방향으로는 경사가 급하고 횡 방향으로는 완만하다면
파라미터별로 적절한 learning rate는 다르다는 것을 쉽게 알 수 있다.
이러한 적절한 learning rate를 파라미터별로 다르게 설정해주고자 하는것이 AdaGrad의 Motivation이다.
$$G_{t+1} = G_t + \nabla_\theta J(\theta) \odot \nabla_\theta J(\theta)$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_{t+1} + \epsilon}} \odot \nabla_\theta J(\theta)$$
$\theta$ : 파라미터 벡터
$\eta$ : learning rate
$G_t$ : 과거 gradient의 제곱합이 누적된 대각행렬(diagonal matrix)
$epsilon$: divison by zero를 피하기 위한 smooting term
$\odot$ : 아다마르 곱 (element-wise multiplication)
수식의 정의상, 아다마르 곱은 $G_t$의 대각성분과 $g$ gradient의 곱으로 이루어진다.
그러나 실제구현에서는 대각행렬 $G_t$의 전체를 저장할 필요는 없다고 한다. 실제 대각행렬에 있는 원소만 추적하는 방식으로 메모리에 저장하고, 처리하는것이 메모리와 계산적으로 효율적일 것이다. (벡터간의 element wise multiplication)
흥미로운점은 분모의 제곱근 연산이 없으면 알고리즘의 성능은 매우 악화된다고 한다.
#AdaGrad
grad_squared = 0
while True = 0
dx = compute_gradient(x)
grad_squared += dx*dx
x -= learning_rate * dx / (np.sqrt(grad_squared) + 1e-7)
AdaGrad의 문제점은 무엇일까?
훈련동안 step이 점점 작아지게 되어, 나중엔 update를 잘 못하는 문제점이 발생한다. 훈련동안에 squared gradient term은 단조적으로 계속 증가해갈것이고, 이에 따라 Step size를 계속 계속해서, 더 작게 해줘야 할것이다. 이는 convex case에서는 수렴 가능한 좋은 특징이지만 non-convex case에서는 Adagrad 사용시 saddle point에 빠지게되어 어떠한 진척도 없어진다. 이는 좋은 특징이 아니다.
5-4 . Adadelta
Adadelta는 2012년에 발표된 논문(Adadelta: An adaptive learning mothod,2012)을 바탕으로한 optimizer로 AdaGrad의 확장판이다.
step size가 단조적으로 감소하는 문제를 적극적으로 해결하고자 한다.
모든 과거의 sqaured gradients를 더해나가는것 보다, 고정된 크기의 윈도우 사이즈 $w$로 past gradients를 더한다.
Instead of inefficiently storing w previous squared gradients, the sum of gradients is recursively defined as a decaying average of all past squared gradients. The running average $E[g2]_t$ at time step t then depends (as a fraction γ similarly to the Momentum term) only on the previous average and the current gradient:
$w$ , window 사이즈의 사용으로, 이전 squared gradients를 비효율적으로 저장하는것 대신에, gradients의 합은 모든 과거 gradients의 decaying average로서 재귀적으로 정의된다. 이동 평균 $E[g2]_t$ 의 fraction $\gamma$는 모멘텀의 term과 유사하게 작동한다. 이동 평균 $E[g2]_t$는 과거의 평균 gradient와 현재 time step의 gradient에 의해 계산된다.
$\gamma$는 모멘텀의 term처럼 대략 0.9로 설정한다.
위의 식은 AdaGrad의 update rule이고 아래의 식은 Adadelta의 update Rule이다.
간단히 diagnoal matrix $G_t$를 과거 gradient의 평균인 $E[g2]_t$ 로 대신하였다.
분모항이 root means squared(RMS) error criterion of the criterion이기 때문에, 간단히 아래 처럼 표현하기도 한다.
Adadelta의 저자들은 업데이트에 있어서 파라미터와 파라미터 변화량의 단위가 일치해야 한다고 지적한다. (SGD, Momentum, AdaGrad에서도 마찬가지다.) 그래서 저자들은 또다른 방법 exponentially decaying averaging을 제시한다. squared
squared gradient 대신에 parmeter의 업데이트에 squared term을 사용한다.
parameter update의 root mean sqaured error는 위와 같이 쓸 수 있고
RMS[∆θ]t를 알 수 없기 때문에, t-1까지의 파라미터 업데이트의 RMS로 근사화한다
learning rate η를 RMS[∆θ]t-1로 대체한다.
최종 Adadelta의 업데이트식은 다음과 같다.
Adadelta를 사용하면 이전 optimizer들과는 다르게 default learning rate를 필요로 하지 않는다. update rule에서 이미 제거 되었기 때문이다.
5-5 . RMSprop
$$E[g^2]_t = 0.9 E[g^2]_{t-1} + 0.1 g_t^2$$$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}} g_t$$
#RMS prop
grad_squared = 0
while True:
dx = compute_gradient(x)
grad_squared = decay_rate * grad_squared + (1-decay_rate) + dx + dx
x -= learning_rate * dx / (np.sqrt(grad_squared) + 1e-7)AdaGrad의 learning rate decay 문제를 다룬것이 RMSprop이다.
RMSprop은 AdaGrad의 변형 모델이다.
RMSProp에서는 AdaGrad의 gradient 제곱 항을 그대로 사용한다. 기존의 누적 값에 decay_rate를 곱해준다. 이 값은 기존의 momentum 수식과 유사하게 생겼지만, gradients의 제곱을 계속해서 누적해 나간다. RMSProp에서는 gradient 제곱 항에 쓰는 decay rate는 보통 0.9 또는 0.99정도를 자주 사용한다. 그리고 '현재의 timestep gradient의 제곱 , '${g_t}^2$은 (1 - decay rate) 를 곱해줘서 더해준다. RMSProp은 gradient 제곱을 계속 나눠준다는 점에서 AdaGrad와 유사하다. 이를 통해 step의 속도를 가속/감속 시킬 수 있다.
이러한 learning rate의 progress를 비교 분석해보면 SGD+Momentum은 local minima에 overshoot했다가 다시 돌아오는 성질이 있고, RMSprop같은 경우에는 모든 차원에 대해서 동일한 궤적을 보이는 경향이 있다. 그러나 AdaGrad를 plot하지는 않았다. AdaGrad를 동일한 learning rate를 사용하여 plot하는 것은 learning rate decay때문에 공평한 비교는 아닐 것이다. 게다가 현재 Neural Network를 학습시킬때 Adagrad를 자주 사용하지 않는다.
5-6. Adaptive Moment Estimation (Adam)
Momentum의 velocity벡터를 사용하는 아이디어와, AdaGrad와 RMSProp의 gradient제곱 항으로 나눠 주는 아이디어를 동시에 사용하는 것은 어떨까? Adam은 Momentum과 RMSProp을 합친 방식이다.
$$m_{t+1} = \beta_1 m_t + (1 - \beta_1) \nabla_\theta J(\theta)$$
$$v_{t+1} = \beta_2 v_t + (1 - \beta_2) \nabla_\theta J(\theta) \odot \nabla_\theta J(\theta)$$
$$\hat{m}_{t+1} = \frac{m_{t+1}}{1 - \beta_1^t}$$
$$\hat{v}_{t+1} = \frac{v_{t+1}}{1 - \beta_2^t}$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_{t+1}} + \epsilon} \odot \hat{m}_{t+1}$$
#vanila adam
first_moment = 0
second_moment = 0
while True:
dx = compute_gradient(x)
first_moment = beta1*first_moment + (1 - beta1) * dx #Momentum
second_moment = beta2 * second_moment + ( 1 - beta2) * dx *dx #AdaGrad/RMSprop
x -= learning_rate * first_moment / (np.sqrt(seond_moment) + 1e-7)그런데 이러한 방식에는 첫번째 time step의 계산에 있어서 분모로 나눠지는 second_moment가 0에 가깝게 계산되기 때문에 $x_{t+1}$이 상당히 큰 값으로 계산될것임을 안다. 이는 수렴에 지장을 초래한다.
#full form
first_moment = 0
second_moment = 0
while True:
dx = compute_gradient(x)
first_moment = beta1*first_moment + (1 - beta1) * dx #Momentum
second_moment = beta2 * second_moment + ( 1 - beta2) * dx *dx #AdaGrad/RMSprop
first_unbias = first_moment / (1-beta1**t)
seocnd_unbias = second_moment / (1-beta2 **t)
x -= learning_rate * first_unbias / (np.sqrt(seond_unbias) + 1e-7)first moment와 second moment가 zero에 가까운 값으로 추정되어 시작하는것때문에 Bias correction part가 추가 되었다.
Bias correction term으로 unbiased estimates를 얻을 수 있고, Adam은 원래의 first moment와 second moment를 사용하기 보다 이러한 수정된 unbiasaed estimiates를 사용한다.
beta1 = 0.9, beta2= 0.999 , learning_rate = 1e-3 or 5e-4가 많은 모델에 있어서 좋은 starting point가 된다고 한다.
Adam도 여전히 문제가 있을까?
만약 loss surface가 앞선 그림과 같은 종과 횡의 비율이 달랐던 타원형이라고 생각해보자. Adam을 이용하면 차원 축들에 따라 적절하게 learning rate가 조절되어 속도가 높아지고 줄어들면서 조절될 것이다. 그런데, loss surface의 타원이 기울어진 타원형(tillted taco shell)이라고 하면 이러한 tillted에 not alinged with axes하고 estimates들을 여전히 독립적인 차원에 대해서밖에 만들어내지 못한다. 즉, tillted의 방향이 아니라 여전히 종/횡의 방향으로 squuising할 뿐, 이러한 차원 방향에 대해서 회전하여 align하는 것은 불가능 하다고 말한다. 물론 이러한 문제는 모든 optimizer들에 해당하는 이야기다.
기본적으로 최적화 문제에서의 손실 함수(loss function)의 표면(loss surface)을 이해하는 것은 최적화 알고리즘의 동작을 파악하는 데 중요하다. 손실 함수의 표면(loss surface)은 모델 파라미터들에 대한 손실 값의 변화를 시각화한 것으로, 이 표면의 형태에 따라 최적화 알고리즘이 어떻게 동작하는지 결정된다.
손실 함수의 표면이 완전히 대칭적이고 모든 방향에서 기울기가 동일하다면, 최적화 알고리즘은 어느 방향으로 이동해도 같은 속도로 최적점에 도달할 수 있다. 그러나 실제로는 손실 함수의 표면이 복잡하고 비대칭적인 형태를 띨 수 있다. 이런 경우에는 일부 방향으로 이동할 때보다 다른 방향으로 이동할 때 더 빠르게 최소값을 찾을 수 있다.
Adam (Adaptive Moment Estimation)은 이런 복잡한 표면에서도 효과적으로 작동하는 최적화 알고리즘이다. Adam은 각 파라미터에 대해 개별적인 학습률(learning rate)을 조정함으로써 손실 함수의 표면이 다른 방향으로 스케일링(scaling)되어 있을 때 (즉, 한 방향은 긴 타원 형태이고 다른 방향은 짧은 타원 형태일 때) 더 효율적으로 최적점을 찾을 수 있다.
그런데 손실 함수의 표면이 기울어진 타원형(tilted taco shell)으로 되어 있으면 문제가 생긴다. 이런 경우에는 손실 함수의 등고선이 기울어져 있으므로, 단순히 각 차원의 스케일을 조정하는 것만으로는 충분하지 않다. 즉, 각 차원이 서로 독립적으로 조정되기 때문에, 기울어진 타원형 표면의 방향에 맞춰서 움직이지 못하고, 여전히 원래의 축을 따라 움직이려고 한다.
이 문제는 gradient의 방향을 적절히 회전시켜주지 못한다는 것과 관련이 있다. Adam과 같은 최적화 알고리즘은 각 차원에 대해 독립적으로 학습률을 조정하지만, 이러한 조정이 축에 정렬되지 않은(loss surface의 주축과 일치하지 않은) 기울기에 대해서는 회전(rotation)을 적용하지 않는다. 따라서, 손실 표면이 축에 정렬되지 않은 방향으로 기울어져 있다면, 이를 적절히 조정하지 못해 최적화 과정에서 비효율적인 경로를 따를 수 있다.
이러한 한계는 Adam 뿐만 아니라 대부분의 전통적인 최적화 알고리즘에서 공통적으로 나타난다. 최근의 연구에서는 이 문제를 극복하기 위해 선행하는 기울기 정보를 사용하거나, 이차 근사(second-order optimization)를 사용하여 손실 표면의 모양을 더 정확하게 모델링하는 방법들이 제안되고 있다.
5-7. Decoupled Weight Decay Regularization (AdamW,2017)
2014년 Adam의 발표이후 2017년도에 발표된 논문을 바탕으로한 optimizer다.
$$m_{t+1} = \beta_1 m_t + (1 - \beta_1) g_t$$
$$v_{t+1} = \beta_2 v_t + (1 - \beta_2) g_t^2$$
$$\hat{m}_{t+1} = \frac{m_{t+1}}{1 - \beta_1^t}$$
$$\hat{v}_{t+1} = \frac{v_{t+1}}{1 - \beta_2^t}$$
$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_{t+1}} + \epsilon} \hat{m}_{t+1} - \eta \lambda \theta_t$$
Adam = RMSprop + Momentum
AdamW (Decoupled Weight Decay Regularization)
앞선 Adam 옵티마이저는 RMSprop과 Momentum의 장점을 합친 옵티마이저이고AdamW는 논문 제목을 빌려 표현하면, Adam옵티마이저에 Weight Deacy Regularziation를 Decoupling한 것이다.
아래 의사 코드의 좌측 Adam같은 경우 $g_t$를 업데이트 할때 L2 Regularization term이 바로 더해지는데에 비해
우측 AdamW같은 경우에는 regularization term이 가중치 업데이트시에 직접적으로 weight decay를 하는 방식으로 작성되어 있다.
※ 참고
$g_t \leftarrow g_t+ \lambda\theta_{t-1}$이 L2 Regularization인 이유는 아래와 같다
L2 Regulariation의 목적함수 식은 다음과 같이 쓸 수 있는데.
$J(\theta) = \text{Loss}(\theta) + \frac{\lambda}{2} \|\theta\|^2$
이에 대한 gradient는 다음과 같이 계산되고
$\nabla_\theta J(\theta) = \nabla_\theta \text{Loss}(\theta) + \lambda \theta$좌측의 첫번째 밑줄과 동일한 형태의 수식임을 알 수 있다.
지금까지 경사하강법으로부터, 그의 변형들과 AdamW까지 살펴보았다.
앞으로 옵티마이저에 대한 벤치마크를 얻은 직관을 바탕으로 이해하며 할 수 있을것이다.
