[딥러닝] Optimization (최적화)

What is Optimization? 

Optimization(최적화)란 해결해고자 하는 문제를 정해진 제약조건 내에서 최적의 결과로 결정하는 것을 의미한다. 즉, 어떠한 상황 속에서 최대의 성능을 내도록 문제를 푸는 과정을 최적화라고 한다. 딥러닝에서의 최적화 역시 모델이 최적의 성능을 발휘할 수 있도록 파라미터들을 조정하는 것을 의미한다.

 

이전에 최적화 기법으로 "Full - Batch", "Stochastic", "Mini-Batch-Stochastic" Gradient Descent 에 대해서 배운 적이 있다. 이번 포스팅에서는 이 기법들 외에 모델이 더 안정적으로 수렴할 수 있도록 하는 최적화 기법들에 대해서 다룰 생각이다.

 

Momentum (관성)

모델에 입력될 데이터의 initialize 지점을 정했을 때, 우리는 Gradient Descent를 통해서 Local Minimum에 도달할 수 있는 방법에 대해 알고 있다. 그러나 이 지점이 반드시 Global Minimum이 아니라는 한계가 있었다. 이를 가능하게 만드는 방법 중에 Momentum을 활용하는 방법이 있다.

 

Momentum은 관성이라는 뜻으로, 물리학에서는 원래 이동하려던 방향으로 이동한다는 성질이다.

 

i번째 mini-batch에 대한 식은 다음과 같다.

$$g_i = \frac{\partial L(y_i, \hat{y_i}}{\partial w}$$

 

Momentum을 적용할 시 weight에 대한 update는 다음과 같다.

$$\tilde{g}_{t+1} = \mu_i \times \tilde{g_t} + \lambda_i \times {g_i}$$

$$w_{i+1} = w_i - \tilde{g}_{i+1}$$

 

• $g_i$ : $i$ 시점에서의 Gradient 값
• $\lambda$ : 학습률 (learning rate)
• $\mu_i$ : $i$ 시점 Gradient에 가중되는 Momentum Parameter
  • 해당 값이 작을수록 최근의 Gradient에 비중을 더 많이 둔다
  • 해당 값이 클수록 이전 Loss Gradient를 더 많이 반영하고, 원래 이동하는 방향으로 계속 나아가려는 경향

위의 첫번째 식에 계속 Recursion을 적용하다 보면 

$$\tilde{g}_{t+1} = \lambda_i \cdot {g_i} + \lambda_i \cdot \mu_i \cdot {g_i} + \lambda_i \cdot \mu_i \cdot \mu_{i-1} \cdot {g_i} + \cdots$$

 

모멘텀의 효과:

1. 학습의 수렴 속도를 줄일 수 있다. 

2. 학습의 진동폭을 줄일 수 있다.

3. 관성은 Gradient가 Noisy한 경우에 효과적이다.

• minimum에 가까워지면서 Gradient의 크기가 줄어들어 GD의 학습속도가 줄어든다.
• 관성은 이전의 Gradient들의 평균 크기를 반영하여 학습 속도가 줄어드는 것을 완화시켜준다.  
• Learning Rate가 너무 크면 GD는 oscilate 할 수 있다.
• 관성은 이전의 Gradient들의 평균 방향을 반영하여 진동폭을 줄여줄 수 있다.
• 관성은 이전의 Gradient들의 평균을 반영하여 noise 평균화되어 noise들끼리 서로 상쇄되어 줄어드는 효과를 줄어드는 효과를 볼 수 있다. 

 

Nesterov's Accelerated Gradient (NAG):

$$\tilde{g}_{i+1} = \mu_i \cdot \tilde{g}_i + \lambda \cdot g(w_i - \mu_i\tilde{g}_i)$$

 

위의 Momentum 식과 비교를 해보면 $\lambda$에 곱해진 부분에서 차이가 남을 볼 수 있다.

• Momentum에서의 $g_i$의 의미는 현재 지점의 Gradient의 의미
• NAG에서 $g(w_i - \mu_i\tilde{g}_i)$의 의미는 'weight parameter'가 모멘텀에 의해 이동한 지점인 $w_i - \mu_i\tilde{g}_i$ 에서의 gradient

Momentum Step

 

NAG

 

NAG의 Momentum보다 나은 점: 

 

Momentum의 경우 Momentum step이 충분히 작지 않은 경우, minimum을 넘어버리는 overshoot 문제가 발생할 수 있다. 그럴 경우 Gradient가 minimum 주변을 oscilate하는 경우가 생길 수 있다.

 

그러나 NAG는 Momentum Step으로 이동한 지점에서의 Gradient 사용. NAG가 계산한 Gradient은 더 작은 값을 가짐. 따라서 Overshoot 문제를 완화할 수 있다.

AdaGrad

AdaGrad는 Weight Parameter 별로 gradient의 학습률을 다르게 주는 방식이다. 이는 Parameter들의 update가 균일하도록 해주고, 많이 update되는 parameter일수록 learning rate를 작게 설정하고, 조금 update되는 parameter일수록 learning rate를 작게 설정한다.

$$w_{t+1, i} = w_{t,i} - \frac{\lambda}{\sqrt{G_{t,ii} + \epsilon}} \cdot g_{t,i}$$

• $w_{t,i}$ : $t$번째 GD step 후 weight parameter인 $w_t$의 $i$번째 component
• $G_{t,ii} = \sum_{t' = 0}^{t} g_{t', t}^{2}$ : $G_t$의 diagonal (row $i$, column $i$)에 해당되는 요소  
• $G_t = \sum_{t' = 0}^{t} g_{t'}g_{t'}^{T}$ : (diagonal 요소들은 $i$번째 gradient component의 제곱의 합이다)

 

따라서 $ G_{t,ii}$가 크다는 의미는 $w_i$에 대한 gradient의 magnitude가 평균적으로 크다는 의미이고, 따라서 이것에 반비례하게 learning rate을 조정한다.

 

AdaGrad의 문제점:

 

1. $\displaystyle \lim_{ t \to 0} \frac{\lambda}{\sqrt{G_{t,ii} + \epsilon}} = 0$ 이므로 시간이 지나면서 Model이 더 이상 업데이트되지 않는 상태에 빠진다.

 

2. $ \frac{\lambda}{\sqrt{G_{t,ii} + \epsilon}}$의 scale이 [constant]/[gradient]의 unit을 가진다. (원래 learning rate은 [constant]의 unit을 가져야 한다)

 

AdaDelta

AdaDelta는 위와 같은 AdaGrad의 문제점들을 보완하기 위해 만들어졌다.

 

AdaDelta에서는 gradient의 제곱의 "moving average"를 사용한다. 그리고, learning rate의 unit을 [constant]로 맞춰준다. 

$$w_{t+1} = w_{t} - \frac{\sqrt{MA[\Delta w^2]_{t-1} + \epsilon}}{\sqrt{MA[g^2]_t + \epsilon}} \cdot g_t$$

$$MA[\theta]_t = \gamma \cdot MA[\theta]_{t-1} + (1 - \gamma) \cdot \theta_t$$

 

Moving Average:

어떤 일련의 값 $(\theta_0, \theta_1, \theta_2, \cdots , \theta_N)$들이 있을 때, 해당 값들의 이동평균 따라서 위 식을 풀엇 전개해보면

$$MA[\theta]_t = (1 - \gamma)(\theta_t + \gamma\theta_{t-1} + \cdots + \gamma^{t - t'}\theta_{t'} + \cdots + \gamma^t\theta_0), \quad (0 < \gamma < 1)$$

 

$\gamma$의 범위에 의해 t'이 과거의 값일수록 현재에 기여하는 바는 작아진다. 또한 $\gamma$의 값이 커질수록 이전 $t$값을 많이 더 반영한다.

 

AdaDelta의 식의 구조를 살펴보면, $g_t$에 곱해진 부분이 실질적인 learning rate이며, $0 < \gamma < 1$이기 때문에 분모가 무한히 커지지 않는다. 즉, effective learning rate가 0이 되지 않아 AdaGrad의 첫번째 문제점이 해결된다. 분자의 값은 이전 GD Step의 업데이트 값이다. 즉, 이전 step의 $\Delta w_t = \lambda \cdot g_t$의 제곱의 Moving Average이다.

 

분자의 unit은 $\Delta w^2$에 제곱근을 취한 형태이기 때문에 [$w$]이다. 분모의 unit은 $g^2$에 제곱근을 취한 형태이기 때문에 unit이 [$wt^{-1}$]이다. 따라서 분수 전체에 해당하는 unit은 [$t$]이고, 이것이 unit이 [$wt^{-1}$] 인 $g_t$에 곱해져 있는 형태이므로 전체 unit이 weight의 unit이 된다. 이로써 AdaGrad의 2번째 문제점이 해결된다

 

ADAM

ADAM은 $\text{E}[g^2]$와 $\text{E}[g]$을 Moving Average로 estimate하여 이를 adaptive한 learning rate 계산에 사용한다

$$w_{t + 1} = w_t - \frac{\lambda}{\sqrt{\hat{v}_t + \epsilon}} \hat{m}_t$$

여기서 $\hat{m}_t$는 $\text{E}[g]$에 해당하고, $\hat{v}_t$는 $\text{E}[g^2]$에 해당하는 부분이다.  

 

$\hat{m}_t = \frac{m_t}{1 - \beta_{1}^t}$ ,  $\beta_1$은 상수 (default = 0.9), 즉 $t$가 늘어날수록 $m_t$에 수렴한다.

$\hat{v}_t = \frac{v_t}{1 - \beta_{2}^t}$ ,  $\beta_2$은 상수 (default = 0.999), 즉 $t$가 늘어날수록 $v_t$에 수렴한다.

 

$m_t = \beta_1m_{t-1} + (1 - \beta_1)g_t$ 즉, $g_t$에 대한 이동평균

$v_t = \beta_2v_{t-1} + (1 - \beta_2)g_t^2$ 즉, $g_t^2$에 대한 이동평균