Optimization beyond SGD

Optimization beyond SGD

Mini batch로 Gradient를 Estimate하는 Stochastic Gradient Descent(SGD)은 Full batch로 Gradient Descent를 쓸 때보다 계산량이 줄어 속도가 빠르다는 장점이 있습니다. 하지만 SGD에는 아래와 같은 문제가 있어서, SGD를 개량한 Optimizer가 계속 제안되어왔습니다.

1. Jittering
   Gradient가 그때그때 가장 떨어지는 방향으로 움직이면서 생기는 현상으로, 아래 그림처럼 방향을 계속 바꿔가면서 움직이는 문제를 말합니다.
2. Local optimum
3. Inaccurate Gradient Estimation
   데이터가 크다면 mini-batch를 활용하여 estimate된 gradient는 부정확할 수 있습니다. 예를 들어 데이터 셋이 수백만개이면 batch size가 수천개라도 그 비율은 굉장히 작습니다.

jittering. 출처: cs231n

SGD + Momentum

SGD에 Momentum 개념을 도입한 Optimizer입니다. 사실 Momemtum 보다는 Ineritia(관성)에 더 가까운 것 같습니다. 즉 이전에 가던 방향들을 참고한다는 것이지요. 아래 코드에서 mu * v 가 관성에 해당합니다.

v = mu * v - learning_rate * dx
x += v

AdaGrad

안 가본 곳을 가보자라는 아이디어입니다. divider를 활용하여 과거에 gradient가 컸던 방향이면 완만하게 가도록 하고 작았던 방향이면 더 가보도록 해줍니다.
parameter 별로 gradient의 제곱합을 가지고, 이를 통해 -learning_rate * dx를 normalize해줍니다. eps은 0으로 나누는 것을 방지하기 위해 아주 작은 값으로 설정해줍니다.

divider += dx ** 2
x += -learning_rate * dx / np.sqrt(divider + eps)

RMSProp: Leaky AdaGrad

AdaGrad의 divider에는 squared gradient가 누적되어 들어가기 때문에 learning rate이 빨리 떨어집니다. 이를 개발자가 조절할 수 있도록 만든 Optimizer입니다.
divider를 구할 때 moving average를 하여 dx ** 2가 aggressive하게 반영되지 않도록 합니다. 보통 decay_rate을 0.9, 0.99, 0.999로 설정합니다.

divider = decay_rate * divider + (1 - decay_rate) * (dx ** 2)
x += -learning_rate * dx / np.sqrt(divider + eps)

Adam

Momentum과 AdaGrad를 적절히 합친 optimizer입니다.

v = mu * v + (1 - mu) * dx
divider = decay_rate * divider + (1 - decay_rate) * (dx**2)
x += -learning_rate * v / np.sqrt(divider + eps)

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

contours evaluation. 출처: https://ruder.io/optimizing-gradient-descent/

saddle point evaluation. 출처: https://ruder.io/optimizing-gradient-descent/