내가 보려고 만든 Normal equation부터 AdamW까지 optimizer 총정리

들어가며

출처:https://www.slideshare.net/yongho/ss-79607172

딥러닝을 공부하며 Optimizer에 대해 알아갈 때 쯤 위에 보이는 그림을 보게됩니다. 저 또한 SGD를 배우기 시작하며 위 그림을 봤고, Adam을 이용하면서 한번 더 보게 됐던 것 같습니다. 당시에는 Optimizer를 제외 하고도 배울게 너무 많았기 때문에 SGD와 Adam 사이의 여러 방법론들은 무시한 채 넘어갔었는데 이번 기회에 전체적인 흐름을 공부하면서 최근에 많이 쓰이는 AdamW까지 정리해보려고 합니다. 본 포스팅은 AdamW까지 가는 흐름을 설명하기 위해 작성하기 때문에 AdaDelta와 Nadam은 포스팅에서 제외하도록 하겠습니다.

---

Normal equation

Normal equation이란 regression을 진행할 때 오차를 최소화하는 파라미터 $\theta$를 찾아내는 방법 중 하나입니다. MSE를 통해 오차를 최소화 한다고 하면 다음과 같은 식으로 표현할 수 있습니다.

$$ \arg\min_{\theta} \frac{1}{2m}\sum_{i=1}^m(h_{\theta}(x^{(i)}) - y^{(i)})^2 $$

 

예시

하나의 feature를 갖는 데이터가 m개 있다고 가정해보면 다음과 같이 표현할 수 있습니다.

위 식을 matrix로 표현한다면 다음과 같이 나타낼 수 있습니다.

$$ X = \begin{bmatrix}
1 & x^{(1)} \\
1 & x^{(2)} \\
1 & x^{(3)} \\
\vdots & \vdots \\
1 & x^{(m)}
\end{bmatrix} w = \begin{bmatrix}
w_0 \\
w_1 \\
\end{bmatrix} y = \begin{bmatrix}
y^{(1)} \\
y^{(2)} \\
y^{(3)} \\
\vdots \\
y^{(m)}
\end{bmatrix} $$

 

$$ Xw = y $$

 

위의 식을 MSE로 표현한다면 다음과 같이 나타낼 수 있습니다.

$$ J = \frac{1}{2} \sum_{i=1}^m(w_0 + w_1x^{(i)} - y^{(i)})^2 $$

 

위의 식에서 J를 최소화 하는 $ w_0, w_1 $을 찾기 위해서 각각에 대해 편미분을 하면,

$$ \frac{\partial J}{\partial w_0} = \sum_{i=0}^m(w_0 + w_1x^{(i)}-y^{(i)}) = 0 $$

$$ \frac{\partial J}{\partial w_1} = \sum_{i=0}^m(w_0 + w_1x^{(i)}-y^{(i)})x^{(i)} = 0 $$

 

위의 식을 정리해서 써보면,

$$ \begin{bmatrix}
\sum_{i=0}^mw_0 + \sum_{i=0}^mw_1x^{(i)} = \sum_{i=0}^my^{(i)} \\
\sum_{i=0}^mw_0x^{(i)} + \sum_{i=0}^mw_1(x^{(i)})^2 = \sum_{i=0}^my^{(i)}x^{(i)}
\end{bmatrix} $$

로 표현할 수 있고 이 식은 $$ (X^TX)w = X^Ty $$ 와 같습니다.

 

 

이제 $ X^TXw = X^Ty $를 w에 대한 식으로 변환하면,

$$ w = (X^TX)^{-1}X^Ty $$로 나타낼 수 있습니다. 이 식을 이용하면 여러 iteration을 반복하지 않고도 최적의 w를 구해낼 수 있게됩니다. 그렇다면 왜 Gradient Descent 기반의 알고리즘이 딥러닝에 사용될까요? 가장 큰 이유는 normal equation은 역행렬을 구해야 한다는 점입니다.

역행렬이 존재하지 않는 경우는 두가지로

1. redundant feature가 있을 때 (예를 들어 한 데이터의 미터와 제곱미터가 feature로 같이 존재 할 때)
2. data의 갯수보다 feature의 수가 많을 때

입니다. 이 경우 역행렬을 구할 수 없게되고 normal equation으로는 w를 구하지 못합니다.

또한 역행렬을 구하는 연산 자체가 엄청난 overhead가 있습니다. $ O(n^3) $ 의 시간이 사용되며 따라서 feature가 많아질수록 overhead가 더 심해지게 됩니다. 따라서 방대한 feature와 data가 필요한 ML/DL에서는 normal equation을 사용하는데 한계가 생깁니다.

 

Gradient Descent

normal equation은 사용하지 못하기 때문에 Gradient Descent가 한가지 방법이 됩니다. Gradient Descent는 Loss function의 기울기를 이용하여 기울기의 반대방향으로 천천히 이동하여 Loss를 최소화 시키는 방법입니다.

 

출처: https://www.javatpoint.com/gradient-descent-in-machine-learning

위에서 했던 notation으로 설명을 계속하겠습니다. 우리는 Loss fuction J를 최소화하는 $ w_0, w_1 $을 찾아야 합니다. 이 때 기울기를 이용하여 $ w $를 업데이트 하게됩니다. :=는 대입 연산자입니다.

$$ w_0 := w_0 - \alpha\frac{\partial J}{\partial w_0} $$

$$ w_1 := w_1 - \alpha\frac{\partial J}{\partial w_1} $$

 

위의 식에서 J를 MSE로 풀어서 다시 써보면

$$ w_0 := w_0 - \alpha\frac{1}{m}\sum_{i=0}^m(h_{\theta}(x^{(i)}) - y^{(i)}) $$

$$ w_1 := w_1 - \alpha\frac{1}{m}\sum_{i=0}^m(h_{\theta}(x^{(i)}) - y^{(i)})x^{(i)} $$

로 표현되는데, $ \sum_{i=0}^m $으로 인해 모든 데이터를 사용하여 한번의 업데이트를 진행하게 됩니다. 이 연산을 Loss가 수렴할 때 까지 진행하게 되는데 이는 학습이 굉장히 오래걸리게 되고 많은 메모리를 요구하게 됩니다. 또한 local minima에 빠질 위험이 있습니다.

 

Stochastic Gradient Descent

Gradient Descent는 굉장히 효과적인 알고리즘이지만 학습이 오래걸리고 많은 메모리가 요구된다는 단점이 있었습니다. Stochastic Gradient Descent(SGD)는 이를 해결하기 위해 모든 데이터가 아니라 random sampling된 데이터 하나에 대해서 gradient descent를 수행합니다. 이러한 방법은 빠른 학습이 가능하고 아주 작은 메모리를 요구합니다. 하지만 당연히 Data 전체를 보는게 아니기 때문에 Noise가 생기게 됩니다. 따라서 데이터1개가 아니라 Batch단위로 GD를 수행하게 됩니다. Batch는 보통 2의 배수로 설정하며 GPU 메모리가 허락하는 선에서 128,256 ... 1024 등등의 갯수를 결정합니다.

출처: https://www.nomidl.com/machine-learning/what-is-gradient-descent-batch-gradient-descent-stochastic-gradient-descent-mini-batch-gradient-descent/

Mini-Batch GD, SGD는 데이터의 일부만을 보고 GD를 수행하기 때문에 Noise가 섞이게 되지만 오히려 이를 통해 local minima를 빠져나올 수 있는 부수적인 효과도 얻게됩니다.

 

여기까지가 ML/DL에 기본이 되는 SGD까지의 설명입니다. 이 이후로는 GD를 발전시킨 방법론들을 설명하도록 하겠습니다. 

 

먼저 스텝 방향을 이용하는 momentum 기반 방법론을 설명하고 스텝 크기를 이용하는 adagrad 기반 방법론을 그다음으로 설명하고 마지막으로 이 둘을 합친, 지금 가장 많이 쓰이는 Adam과 AdamW에 대해 설명하겠습니다.

 

Momentum

momentum은 local minima에서 빠져나가기 위해 가속도를 이용합니다. 쇠구슬을 예로 들어보면 쇠구슬이 경사를 내려올 때 얕은 경사는 가속도로 인해 쉽게 뛰어 넘을 수 있게됩니다. 마찬가지로 momentum을 이용했을 때 local minima에 수렴하지 않고 global minima를 향해 내려갈 수 있게 됩니다.

출처: https://medium.com/analytics-vidhya/momentum-rmsprop-and-adam-optimizer-5769721b4b19

위의 그림에서 가장 오른쪽 쇠구슬은 왼쪽방향의 gradient를 갖지만, 현재까지의 momentum으로 인해 실제로는 오른쪽으로 움직이게 됩니다.

 

수식적으로 표현하면 다음과 같습니다.

$$ V_{dw_0(t)} = \beta_1V_{dw_0(t-1)} + (1-\beta_1)dw_0(t) $$

$$  V_{dw_1(t)} = \beta_1V_{dw_1(t-1)} + (1-\beta_1)dw_1(t) $$

$ V $ 는 각 $ w_0,w_1$의 gradient를 지수 이동평균으로 누적하는 변수입니다. 처음에는 0으로 초기화되며 이전 시점의 값을 $ \beta_1 $만큼, 지금 시점의 gradient를 $ (1-\beta_1) $만큼 이용하여 누적합니다.

 

그리고 실제 $ w $의 업데이트는 $ V $를 이용합니다.

$$ w_0 := w_0 -\alpha V_{dw_0(t)} $$

$$ w_1 := w_1 -\alpha V_{dw_1(t)} $$

보통 $ \beta_1 $의 값은 0.9로 설정합니다. 이는 이전 $ \frac{1}{(1-\beta_1)} $시점 만큼의 값을 참고하는 것과 같습니다.

 

Nesterov Accelrated Gradient (NAG)

momentum은 가속도를 통해 local minima를 넘어갈 수 있었지만 오히려 이러한 가속도로 인해 최적 지점 또한 지나갈 수 있다는 단점이 존재합니다. NAG는 이러한 문제를 해결하기 위해 현재의 gradient를 바로 V에 누적하는 것이 아니라 현재의 momentum으로 한 step이동 한 곳에서의 gradient를 계산합니다. 말로 설명하면 어렵기 때문에 수식으로 보겠습니다.

기존 momentum은 앞서 설명했듯이

$$ V_{dw_0(t)} = \beta_1V_{dw_0(t-1)} + (1-\beta_1)dw_0(t) $$ 와 같이 나타낼 수 있습니다. 이 식을 모든 w에 대해서 Loss function의 gradient를 구하는 형식으로 바꾸면

$$ V_t = \beta_1V_{t-1} - (1 - \beta_1)\nabla_w J(w_t) $$이 됩니다.

현재시점 t에서의 V는 t-1시점의 V에 Loss function J를 w에 대해서 미분한 gradient를 누적한 값이 되는 것입니다.

 

NAG에서는 위의 식을 아래와 같이 바꿉니다.

$$ V_t = \beta_1V_{t-1} - (1 - \beta_1)\nabla_w J(w_t - \beta_1V_{t-1}) $$

위 식을 보면 J 안의 식이 바뀐 것을 볼 수 있습니다. 기존에는 현재시점 파라미터 $ w $의 gradient를 구했지만, NAG에서는 현재 시점 파라미터 $ w $에서 현재의 momentum으로 한 step 더 간 곳에서의 $ w $ gradient를 구합니다. 이러한 방식은 위의 그림에서 볼 수 있듯이 가속도를 이용해서 움직이는 장점을 갖으면서도 멈춰야 할 곳에서는 멈출 수 있게 됩니다.

 

NAG의 더 자세한 구현내용은 밑의 링크에서 보실 수 있습니다.

https://tensorflow.blog/2017/03/22/momentum-nesterov-momentum/

Momentum & Nesterov momentum

 

Adagrad

Adagrad는 Adaptive Gradient의 약자로 Learning rate를 Adaptive하게 변화 시킬 수 있는 방법론입니다.  위에서 봤던 방법론들이 step의 방향을 이용했다면 Adagrad는 step의 사이즈를 이용합니다. 즉, learning rate를 adaptive하게 변경합니다. 이 때 하나의 learning rate를 변경하는 것이 아니라 각 weight별로 adaptive하게 lr을 변경하게 됩니다.

 

식으로 표현해보면

$$ g_t = g_{t-1} + (\nabla_w J(w_t))^2 $$

$$ w_{t+1} := w_t - \frac{\alpha }{\sqrt{g_t + \epsilon }} \nabla_w J(w_t) $$

 

Adagrad의 기본 가정은 기존에 큰 gradient를 통해 update가 많이 된 weight는 최적값에 가까울 가능성이 높기 때문에 lr을 감소시키고 작은 gradient를 통해 update가 적게 된 weight는 최적값과 멀 가능성이 높기 때문에 lr을 증가시킵니다.

 

위의 식에서 $ g_t $는 계속 누적되어 learning rate $ \alpha $의 분모로 들어가는데, $ g_t $는 커질 수록 $ \alpha $가 작아지기 때문에 위의 가정에 맞는 식이 됩니다.

 

$ g_t $는 초기에 0으로 초기화 되며 weight 만큼의 size를 가지는 vector가 되게 됩니다.(weight 각각의 gradient를 보고 lr을 조정해야하기 때문에)

 

practical한 이야기를 하자면, Adagrad를 위해서는 기존 $ \alpha $보다 큰 값을 learning rate로 주어야 학습이 잘 일어납니다. 제가 봤던 Adagrad를 쓰는 연구에서는 lr을 1로 주는 경우를 많이 봤습니다.

 

Adagrad는 효과적인 방법론이지만, Non-Convex 할 경우 학습이 힘들다는 단점과, 학습이 오래될수록 학습률이 점점 작아지기 때문에 모델의 학습이 잘 일어나지 않는다는 단점을 갖고 있습니다.

RMSProp

RMSProp은 간단히 말하면 Adagrad에 지수 가중 이동 평균을 적용한 방법론입니다. 위의 Adagrad에서 딱 한가지 달라집니다.

 

$$ g_t = {\color{Red} {\beta_1}}g_{t-1} + (1-{\color{Red} {\beta_1}})(\nabla_w J(w_t))^2 $$

$$ w_{t+1} := w_t - \frac{\alpha }{\sqrt{g_t + \epsilon }} \dot \nabla_w J(w_t) $$

 

즉, 기존 Adagrad의 g_t는 계속해서 누적되었던 것에 반해 RMSProp에서는 g를 decay 시키게 됩니다.

 

RMSProp은 Adagrad와 다르게 학습이 오래될 수록 모델 학습이 진행되지 않는 문제가 발생하지 않습니다.

 

ADAM

드디어 현재 optimizer라고하면 de-facto로 사용되는 ADAM에 도착했습니다. 앞의 흐름을 따라왔다면 ADAM은 단순히 RMSProp과 Momentum을 같이 사용한 방법론입니다. 

 

먼저 식을 보겠습니다. 앞의 흐름을 알고 있다면 식을 보고 바로 이해될 것이라고 생각합니다.

$$ m_t = \beta_1m_{t-1} + (1-\beta_1)(\nabla_w J(w_t)) $$

$$ v_t = \beta_2v_{t-1} + (1-\beta_2)(\nabla_w J(w_t))^2 $$

 

위에서 많이 봤던 수식입니다. $ m_t $는 momentum이고 $ v_t $는 RMSProp입니다.

 

하지만 ADAM에서는 추가적으로 $ m_t $와 $ v_t $를 보정해주는 작업을 합니다. $ m_t $와 $ v_t $는 처음에 0으로 초기화 되기 때문에 $ m_t, v_t $는 0에 편향되게 됩니다.(기존 값이 아닌 0으로 부터 시작하기 때문에) 따라서 초기 몇번의 iteration에서는 이를 보정해주는 작업을 하게 됩니다.

수식으로 표현하면

 

$$ \hat{m_t} = \frac{m_t}{1-\beta_1^t} $$

$$ \hat{v_t} = \frac{v_t}{1-\beta_2^t} $$

가 되고, 초기 몇번의 iteration에서만 보정을 수행합니다.

 

마지막으로 weight의 업데이트는 다음과 같이 수행됩니다.

 

$$ w_{t+1} := w_t - \frac{\alpha }{\sqrt{\hat{v_t} + \epsilon }} \hat{m_t} $$

결국 momentum 처럼 업데이트가 되면서, learning rate가 RMSProp처럼 weight마다 Adaptive하게 변하는 것입니다.

일반적으로 $ beta_1 $은 0.9, $ beta_2 $는 0.999가 사용됩니다.

 

AdamW

최근 Adam보다 AdamW를 사용한 코드가 많이 보이고 있습니다. Hugging Face의 트랜스포머나 몇몇 모델을 보면 Adam이 아닌 AdamW를 사용합니다. Adam은 특정 task에서 SGD with momentum보다 generalization성능이 낮은 경우가 존재하는데, 그 이유가 Adam에 적용하는 L2 regularization이 SGD보다 효과적이지 않기 때문이라고 주장하며 AdamW가 제시되었습니다. 따라서 AdamW와 Adam은 L2 regularization을 적용하는 방식에서 차이가 있습니다.

 

L2 Regularization = Weight decay?

흔히 L2 Regularization은 Weight decay와 같은 개념이라고 생각합니다. 하지만 이는 SGD에서만 해당되는 사항입니다.

SGD에서 L2 Regularization을 적용한 식을 보면, (여기서 부터 parameter를 $ \theta $ 로 표현하겠습니다.)

$$ \theta_{t+1} = \theta_t - \alpha \nabla f_t^{reg}(\theta_t) $$

로 표현할 수 있습니다. 여기서 $ f^{reg}(\theta_t) $는 L2 regularization을 포함한 식으로 표현될 수 있습니다.

$$ f_t^{reg}(\theta_t) = f_t(\theta) + \frac{\lambda '}{2}\sum_i \theta_i^2 $$

이 식을 미분하면

$$ \nabla f_t^{reg}(\theta_t) = \nabla f_t(\theta) + \lambda ' \theta $$

로 표현할 수 있습니다. 

 

다시 정리하면

$$ \theta_{t+1} = \theta_t - \alpha (\nabla f_t(\theta) + \lambda ' \theta) = (1 - \alpha \lambda ' )\theta_t - \alpha \nabla f_t(\theta) $$ 

이 되고, 만약 $ \lambda ' = \frac{\lambda}{\alpha} $ 면 SGD에서 L2 Regularization은 SGD에서 weight decay의 역할을 수행하게 됩니다.

Adam에서는?

Adam은 다음과 같은 방식으로 parameter를 업데이트 합니다.

출처: https://hiddenbeginner.github.io/deeplearning/paperreview/2019/12/29/paper_review_AdamW.html

 

Adam에 L2 Regularization을 추가했을 때의 식을 간단하게 표현하면 

출처: https://hiddenbeginner.github.io/deeplearning/paperreview/2019/12/29/paper_review_AdamW.html

위와 같이 나타낼 수 있습니다.

1. Adam의 $ \nabla f_t^{reg}(\theta_t) $를 제외한 부분을 모두 $ M_t $로 나타냄
2. $ \nabla f_t^{reg}(\theta_t) $를 $ \nabla f_t^{reg}(\theta_t) = \nabla f_t(\theta) + \lambda ' \theta $ 를 이용하여 식에 넣음

반면에 Weight decay만 적용한 식은

$$ \theta_{t+1} = (1-\lambda)\theta_t - \alpha M_t \nabla f_t(\theta_t) $$

로 표현할 수 있습니다.

 

결국 L2 Regularization과 Weight decay는 Adam에서 $ M_t = kI $가 아닌 이상 다르게 됩니다. 하지만 $ M_t $가 $ I $가 될 가능성은.. 거의 없을 것 입니다. 더해서 $ \lambda ' $ 뒤에 $ M_t $가 붙어서 SGD보다 더 작은 decay rate로 wieght decay가 수행되기 때문에 일반화 성능이 잘 나오지 않는다고 합니다.

 

AdamW에서는 이러한 문제를 해결하기 위해 L2 regularization의 $ \lambda \theta_{t-1} $을 분리(decouple)하여 업데이트 식에 넣어주게 됩니다.

위 알고리즘에서 초록색 부분이 Weight decay를 직접적으로 추가한 부분입니다. 이 때 보라색 부분은 사용되지 않습니다.

Adam과의 차이를 살펴보면 다음과 같습니다.

• $ m_t, v_t $즉, momentum과 RMSProp을 구할 때는 L2 Regularization이 사용되지 않은 gradient를 이용한다.
• parameter를 업데이트 할 때는 L2 regularization에서 decouple된 weight decay term을 직접 넣어준다( 초록색 부분 )

논문에서는 초록색 부분을 직접 추가해줌으로써 weight decay효과를 본다고 주장합니다.