SGD with Momentum

$\bar x_t = \frac{x_1 + x_2 + ... + x_t}{t}$ 를 우리는 흔히 Average라고 한다.

How to write the average in a RECURSIVE FORM?
$\bar x_t =$ ◻$\bar x_{t-1} +$ ▵

⭐ 위 Normal Average 공식을 사용해서

$S_t = x_1 + x_2 + ... + x_t$ 라고 할 때,

$\bar x_t = \frac{S_t}{t}$

$\bar x_{t-1} = \frac{x_1 + x_2 + ... x_{t-1}}{t-1} = \frac {S_{t-1}}{t-1}$ → $S_{t-1} = (t-1)\bar x_{t-1}$

$S_t = x_1 + x_2 + ... +x_{t-1} + x_t = S_{t-1} + x_t$

$S_t = (t-1)\bar x_{t-1} + x_t$

⇒ $\bar x_t = \frac{(t-1)\bar x_{t-1} + x_t}{t}$ : Time step $t$ 까지의 평균

Recursive form of average: Memory efficient way

• 과거의 정보와 현재 정보를 어떤 비율로 섞을 것인가?

$\bar x_t = \beta_t\bar x_{t-1} + (1-\beta_t)x_t$ where $\beta_t = \frac{(t-1)}{t}$

• 이렇게 시간이 지날수록, 앞의 가중치가 더 커짐 (새로들어온 정보 무시당함)

Simple Moving Average (SMA)

• Specified period 상의 값들의 평균: 그냥 일반적인 평균이라는거

정확히 $n$개의 데이터를 더하기 위해서 $x_{t-n+1}$ 이 분자의 마지막 항

$\text{SMA}_t = \frac {x_t + x_{t-1} + ... + x_{t-n+1}}{n}$

Time step $t$에서의 SMA인데,

• $n$은 window size(평균 구하는 기간) ,
• $x_t$는 t시점에서의 Value

Exponential Moving Average (EMA)

EMA는 최근 데이터에 더 많은 가중치를 준다.

$\text{EMA}_t = \beta\text{EMA}_{t-1} + (1-\beta)x_t$

• $\beta$는 smoothing factor로, $0<\beta \le 1$ 사이의 값을 가진다.

$\text{EMA}_{t-1}과 x_t에 대한 \text{Convex Combination}$ 이다.

⭐ Recursive form of average 에서 $\beta$의 범위와 혼동 주의

최신 데이터를 반영하는 가중치가 시간에 따라 변하느냐, 고정되어 있느냐의 차이이다.

• 일반 평균: 과거 데이터가 많이 쌓일수록 새로 들어온 데이터는 무시
• EMA: 새로 들어온 데이터는 무조건 전체 평균의 일정 영향력 행사

Time	xt (sensor reading)	xˉt (EMA, β=0.5)
1	22.0	22.0 (initial)
2	22.5	$0.5 \cdot 22.0 + 0.5 \cdot 22.5 = 22.25$
3	23.0	$0.5 \cdot 22.25 + 0.5 \cdot 23.0 = 22.625$
4	22.8	$0.5 \cdot 22.625 + 0.5 \cdot 22.8 = 22.7125$

Recursive form of Average 랑 EMA랑 같은 식.

단지 $\beta$가 $\frac{t-1}{t}$ 인지, 0과 1 사이의 고정된 상수인지 따라 나뉜다.

Exponential decay in EMA

• 과거의 데이터가 어떻게 지수적으로 감소하며 잊혀지는가?

[일반적인 EMA 수식] : $v_t$ : 현재 $t$ 시점에서의 EMA 값

$v_t = \beta v_{t-1} + (1-\beta)x_t$

[ $t-1$ 시점에서의 EMA: $v_{t-1}$ ]

$v_{t-1} = \beta v_{t-2} + (1-\beta)x_{t-1}$

위 식 ($t-1$)시점을 현재 시점 수식에 집어넣어보자

$v_t = \beta (\beta v_{t-2} + (1-\beta)x_{t-1}) + (1-\beta)x_t$
$= \beta^2v_{t-2} + \beta (1-\beta)x_{t-1} + (1-\beta)x_t$

이런 식으로 $\beta$의 지수가 점점 커진다.

무한히 반복하게 되면

$v_t= \beta^tv_0 + (1-\beta)\sum\limits_{i=1}^t\beta^{t-i}x_i$

• $\beta^tv_0$: 맨 처음 초기값($v_0$)이 현재에 미치는 영향이다. 시간이 지나 $t$가 커지면 $\beta^t$는 거의 0이 되므로, 초기값의 영향력은 완전히 사라진다
• $\beta^{t-i}$: 과거 시점 $i$의 데이터 $x_i$에 곱해지는 가중치이다.

SGD with Momentum

• $\vec w_t$: $t$-step 에서의 최적화 변수
• $\vec g_t = \vec g(\vec w_t)$ : $t-$step 에서의 Gradient 추정치

$\vec m_t = \mu\ \vec m_{t-1} + \vec g_t$

• $*\eta$ 는 0~1 사이의 값이기 때문에 Gradient에 더 가중치가 쏠림*

$\vec w_{t+1} = \vec w_t -\eta \ \vec m_t$

---

• Higher $\mu$ : Smoother but slower to adapt
  → $\mu$가 크면 과거의 기억을 잘 가져간다. 노이즈를 다 무시해서 smooth하지만, 관성 때문에 코너를 크게 돈다. (Slower to adapt)
• lower $\mu$ : More responsive but more jittery
  → $\mu$가 작으면 새로운 기울기에 즉각 반응하여 방향을 휙휙 틈
  하지만 불필요 노이즈에도 반응해서 jittery함

$\mu$가 0이면 SGD랑 다를바가 없음

Exponential decay in Momentum update

$\vec m_t = \mu \ \vec m_{t-1} + \vec g_t$

$\sum \limits_{k=0}^t\mu^k \vec g_{t-k}$

• $\mu^k$는 $k$가 커지면 커질수록 0으로 가까워짐 ($\mu : (0, 1)$)
• $k$가 $t$일 때에는, $\mu^t \vec g_0$
  → 맨 처음 계산한 GD 효과를 죽이고, 최근 것에 가중치 올림

EMA랑 다를게 뭔데?

최근 데이터에 가중치 주고, 과거 데이터는 줄이는 아이디어는 동일

가중치 합을 1로 맞추는 정규화 여부에 따른 차이가 존재함

$v_t = (1-\mu)\sum \limits_{k=0}^t\mu^kg_{t-k}$ : EMA 수식

여기서는 앞에 $(1-\mu)$가 곱해져 있어서 가중치들의 총합이 1.
→ 과거 데이터를 많이 섞어도 결과값의 크기는 원래 데이터($g$)들의 평균적인 크기를 유지함 (1이 되는건 등비수열의 합 공식 생각하기)

$m_t = \sum \limits_{k=0}^t\mu^kg_{t-k}$ : SGD의 모멘텀

앞에 ($1-\mu$)가 없어서 가중치 총합은 $\frac{1}{1-\mu}$.
→ 단순 평균이 아니라 과거 값들의 누적이 되어 스케일이 커짐

Adaptive Optimizers

Noisy Quadratic model

$f(\vec w) = \frac{1}{2}(h_1w^2_1 + h_2w_2^2)$

• $h_1, h_2$는 곡률을 의미한다. (Hessian Matrix $H$ 의 고윳값)

AdaGrad

AdaGrad는 ‘과거의 기울기’를 모두 기억하는 방식을 선택했다.

$\vec h_t = \vec h_{t-1} + g_t \odot g_t$ :
→ 기울기 제곱의 누적 [매 스탭 $t$ 마다 현재 기울기 $g_t$ 구하고 제곱해서 과거 누적에 더하기

$\vec w_{t+1} = \vec w_t - \frac{\eta}{\sqrt{\vec h_t} + \epsilon} \odot \vec g_t$
→ 파라미터 업데이트: 누적값 $\vec h_t$를 사용해 파라미터 $\vec w$ 업데이트하기

---

$\vec g_t = \frac{1}{|B_t|} \sum_{i\in B_t} \nabla f_i(\vec w_t)$ : 이건 그냥 기울기 구하는거

GD 제곱을 계속 축적시켜서 $\vec h_t$가 무한히 커져서 실제 적용되는 학습률이 0에 수렴해버려서 멈춰버림

• AdaGrad는 Convex에서만 작동 잘 함
  • Non-Convex에서는 Local Minima에 빠짐

RMSProp

AdaGrad가 과거를 너무 다 기억해서 학습이 멈추는 문제가 있음
→ AdaGrad 수식에 EMA를 섞어서 옛 기울기는 잊도록 만든 것

$\vec h_t = \beta\vec h_{t-1} + (1-\beta)\vec g_t \odot \vec g_t$

$\vec w_{t+1} = \vec w_t - \frac{\eta}{\sqrt{\vec h_t} + \epsilon} \odot \vec g_t$

Adam: RMSProp + Momentum

$\vec m_t = \beta_1 \vec m_{t-1} + (1-\beta)\vec g_t$ : EMA of Gradients (1차 모멘트)

$\vec v_t = \beta_2\vec v_{t-1} + (1-\beta_2)(\vec g_t \odot \vec g_t)$
→ 2차 모멘트

$\hat{\vec m} = \frac{\vec m_t}{1 - \beta^t_1}, \hat{\vec v} = \frac{\vec v_t}{1-\beta^t_2}$ : 편향 조정

→ 학습 극초반, $t$가 작을 때 $m_t, v_t$가 0에 가깝게 계산되는 것을 막기 위함

$\vec w_{t+1} = \vec w_t - \frac{\eta}{\epsilon + \sqrt{\hat{\vec v}}} \odot \hat{\vec m}$ : Weight update

• 분자: 순수하게 요동치는 현재 기울기 $g_t$대신 모멘텀을 사용
• 분모: 무한히 커지는 누적합 대신, 2차 모멘트로 파라미터별로 $\eta$를 나눠줌
• $\epsilon$: 분모가 완전히 0이 되어 폭발 방지

Adam: Bias Correction

EMA에서 이전 시점의 평균값이 필요한데, 학습 막 시작한 단계($t=1$)일 때에는 과거 데이터가 없음

→ $m_0, v_0$을 0벡터로 초기화하고 시작함

• 문제는 이 ‘0’이라는 값이 비어있다는 것이 아닌, 수학적으로 “과거 평균 기울기가 0” 이라는 잘못된 정보로 작용함

실제 기울기는 $g_1$인데, 계산된 이동 평균 $m_1$은 실제의 10%의 값으로 되어버림

해결 방안: Bias correction

$\hat m:= \frac{m_t}{1-\beta^t_1}$

분모에 있는 $t$는 단순 변수가 아닌, 지수이다.

→ 학습 스텝이 진행될수록 $\beta_1$을 $t$번 거듭제곱 하는 것

• 학습 극초반 ($t=1$) 일 때: 분모는 $1-0.9^1 = 0.1$이 된다.
  따라서 보정된 값 $\hat m_1 = \frac{0.1g_1}{0.1} = g_1$이 된다.
  정확히 실제 기울기 $g_1$로 100% 복귀되었다.
  
• 학습 중반 이후($t=1000$)일 때: $\beta_1$은 1보다 작은 소수(0.9)이기 때문에, 1000번 거듭제곱을 하면 $0.9^{1000} \approx 0$으로 사실상 완전 소멸한다.
  분모는 $1-0 = 1$이 되고, 보정된 값 $\hat m_{1000} = \frac{m_{1000}}{1} = m_{1000}$ 이 된다.

  즉, 데이터가 부족해서 0의 영향을 강하게 받는 극초반에는 강제로 스케일을 키워주고, 데이터가 충분히 쌓인 0의 영향력이 희석된 후반부에는 스스로 사라지는 장치이다.