[Optimization]Adagrad(Adaptive Gradient), RMSProp(Root Mean Squared Propagation), Adadelta(Adaptive delta)

앞선 글에서는 Gradient Descent의 운동량(Momentum)을 조정하여 수렴속도를 빠르게 하는 방법인 Momentum, Nesterov Accelerated Gradient(NAG) Optimizer를 살펴보았습니다

 

[Optimization]Momentum, Nesterov Accelerated Gradient(NAG)

 

이번 글에서는 Gradient Descent의 속도(Velocity)를 조정하여 수렴속도를 빠르게하는 Optimizer들을 살펴보도록 하겠습니다

 

Adagrad(Adaptive gradient)

일반적으로 모든 parameter에 대해 학습률을 일정하게 유지하는 SGD나 Momentum과 달리 각 parameter 마다 서로 다른 학습률을 적용하는 방법

과거의 Gradient 값을 저장해두었다가 이를 사용하여 learning rate를 조정한다

조정하는 방법 : 많이 변화하지 않은 parameter들은 학습률을 크게하고 많이 변화한 parameter들에 대해서는 학습률을 작게 하는 방법이다(많이 변화한 parameter는 최적값에 근접했을 것이라는 가정하에 작은 크기로 이동)

각 parameter 마다 서로 다른 학습률을 사용하므로, 전체 parameter의 학습률을 조정하는 것 보다 미세한 조정이 가능하다

그럼 수식을 통해 Adagrad를 알아보도록 하겠습니다 

 

parameter 마다 다른 learning rate를 주기 위해 이전 Gradient의 누적 값을 가지고 있는 함수 G를 추가합니다

 

$$
\begin{aligned}
&w_{t+1} = w_t - \frac{\eta}{\sqrt{G(t) + \epsilon}} \nabla{L(w_t)}\\
&G(t) = G(t-1) + (\nabla{L(w_t)})^2 = \sum \limits_{i=0}^{t}(\nabla{L(w_i)})^2
\end{aligned}
$$

 

$G(t)$ : 현재 시점 t 까지의 모든 Gradient의 제곱합

    여기서 $G(t)$가 크면 $\frac{\eta}{\sqrt{G(t) + \epsilon}}$이 작아져 learning rate가 작아진다

$\epsilon$ : $\frac{\eta}{\sqrt{G(t) + \epsilon}}$에서 divide by 0를 방지하지 위한 매우 작은 값

 

※ $G(t)$와 $(\nabla{L(w_t)})^2)$ 는 벡터 연산으로, 각 parameter마다 개별적으로 계산된기 떄문에 각 parameter 별 다른 learning rate 적용이 가능하다

 

하지만 $G(t)$가 누적해서 증가함에 따라 learning rater가 0에 수렴하여 더 이상 parameter가 update 되지 않을 수도 있다는 단점이 존재한다

---

RMSProp(Root Mean Squared Propagation)

Adagrad의 문제점인 $G(t)$ 값이 증가하여 학습을 진행할수록 learning rate가 너무 작아져 학습이 멈출 수도 있다는 점을 해결하기 위해 Exponential Moving Average(지수 이동 평균,EMA)를 사용하는 방법(과거의 값을 더 적게 반영)

 

$G(t)$함수에 $\alpha$값을 추가하여 학습률 크기를 비율로 조정한다

 

그럼 이제 수식을 통해 RMSProp를 알아보도록 하겠습니다

 

$$
\begin{aligned}
&w_{t+1} = w_t - \frac{\eta}{\sqrt{G(t) + \epsilon}}\nabla{L(w_t)}\\
&G(t) = \alpha G(t-1) + (1-\alpha)(\nabla{L(w_t)})^2\\
\end{aligned}
$$

 

Adagrad와 마찬가지로 $G(t)$를 통해 이전 기울기의 제곱 값의 누적을 통해 각 parameter 별로 다른 learning rate를 적용합니다

이때 $G(t)$를 구하는 과정에서 지수 이동 평균(EMA)을 사용하여 최근 기울기 제곱값들에 더 많은 가중치를 주고, 과거 기울기 제곱 값들에 더 적은 가중치를 주기 때문에 희소한 기울기에 대해 학습률이 너무 빨리 감소하는 문제를 완화한다

---

Adadelta(Adaptive delta)

Adagrad, RMSProp, Momentum을 모두 합친 Gradient Descent 방법이다

1. Adagrad의 특징인 모든 Step의 Gradient 제곱 합을 사용하는 것이 아닌 window size를 두어 window size 만큼의 합으로 변경,
   이후 RMSProp과 같이 Exponential Moving Average(EMA)를 적용
2. Hessian Approximation을 이용한 Unit(단위) 수정

알고리즘

1. Gradient 제곱의 이동 평균

$$E[g^2]_t = \rho E[g^2]_{t-1} + (1 - \rho) (\nabla{L(W_t)})^2$$

여기서 $ E[g^2]_t$ 는 시점 t에서의 gradient 제곱의 이동 평균입니다

 

2. 이전 단계에서의 Parameter 변화량 제곱의 이동 평균

$$E[\Delta w^2]_t = \rho E[ \Delta w^2 ]_{t-1} + (1 - \rho) ( \Delta w_{t-1} )^2$$

여기서 $ E[\Delta w^2]_t $ 는 t 시점 이전 단계에서의 parameter 변화량 제곱의 이동 평균입니다

 

3. 현재 단계에서의 Parameter 변화량 계산

$$ \Delta w_t = \frac{\sqrt{ E[\Delta w^2]_t  + \epsilon}}{\sqrt{ E[g^2]_t + \epsilon}} \nabla{L(W_t)} $$

여기서 현재 단계에서의 Parameter 변화량을 계산합니다

$\Delta w_t$ 는 현재 gradient($\nabla{L(W_t)}$)와 이전 단계의 parameter 변화량($ E[\Delta w^2]_t$) 및 이전 단계의 gradient 정보($E[g^2]_t$)를 결합하여 계산된다

 

4. Parameter Update

$$ W_{t+1} = W_t - \Delta w_t$$  

※ Newton's Method, Hessian Approximation

Newton's Method를 통한 parameter update는 아래와 같이 수행합니다

$$ {\large x_{t+1} = x_t - H^{-1} \nabla f(x_t) }$$

Hessian Matrix는 함수의 곡률 정보를 담고 있으며, 이는 Parameter 공간에서 Loss Function의 곡률을 반영합니다

따라서 Hessian Matrix를 사용하면 학습률이 자동으로 조정되며, 이는 곡률 정보에 따라 Parameter를 더욱 효율적으로 Update할 수 있게 됩니다

 

하지만 Hessian Matrix를 직접 구하는 것은 매우 복잡하므로 Adadelta에서는 Hessian 근사치을 사용하여 Parameter를 update하였습니다( 알고리즘 3번 )

 

여기서 어떻게 gradient 제곱의 이동평균 $E[g^2]_t $과 parameter 변화량 제곱의 이동평균 $E[\Delta w^2]_{t-1}$​를 Hessian 근사치로 사용하였는지 설명 드리도록 하겠습니다

• Gradient 제곱의 이동평균 $E[g^2]_t $ : Loss function의 기울기 크기를 반영(기울기가 커지는 곳은 learning rate 줄임)하기 때문에 간접적으로 Loss function의 곡률정보를 반영한다고 할 수 있습니다
• Parameter 변화량 제곱의 이동평균 $E[\Delta w^2]_{t-1}$ : 이전 단계에서의 parameter 변화량을 반영(변화가 큰 Parameter의 learning rate를 줄임)

결론적으로 Hessian 행렬의 곡률 정보를 직접적으로 사용하진 않지만, Parameter 변화와 Gradient 크기를 반영하여 Learning rate를 자동으로 조정하는 방식은 Hessian Matrix의 역행렬을 이용한 Update 규칙과 유사한 효과를 가져옵니다