0021 Gradient Descent & Momentum

Gradient Descent

어떤 함수값을 최대 혹은 최소로 하는 점은 어떻게 찾으면 좋을까요? 일단 최소값을 찾는 경우를 생각해 보겠습니다. 우리가 이미 그 함수를 알고 있다면 문제는 쉽습니다. 하지만 그 함수를 잘 모를 경우, 아니면 알아도 너무 복잡해서 최소가 어딘지 찾을 수 없을 경우는 문제가 됩니다. 이 때 가장 많이 사용되는 방법 중 하나가 경사 하강법(gradient descent, GD)입니다. 반대로 경사 상승법(gradient ascent)도 있지만, 사실 함수의 부호만 바꾸면 경사 상승법도 경사 하강법으로 풀 수 있습니다. GD는 가끔 가파른 하강법(steepest descent algorithm)이라고 불리기도 합니다.

GD의 기본은 간단합니다. 일단 아무 점이나 하나 잡고 시작해서, 그 점에서의 함수값보다 계속 조금씩 조금씩 값이 작아지는 점으로 옮겨가는 것입니다. 그러면 언젠가는 최소값에 도달할 것이라고 생각할 수 있습니다. 실제로, GD 방식으로는 반드시 극소값(local minimum)에 도달할 수 있다는 것이 증명되어 있습니다. 하지만 전체 최소값(global minimum)으로 갈 수 있다는 보장은 없습니다.

gradient_descent

함수의 기울기(gradient)는 그 함수가 지금 증가중인지 감소중인지를 나타냅니다. 따라서, 기울기를 잘 보면 어느 방향으로 움직여야 하는지 알 수 있습니다. 다음 식을 이용해 GD를 사용할 수 있습니다. 처음에는 기울기를 더해야 하는지 빼야 하는지 헷갈릴 수 있는데, 언제나 기울기에 해당하는 값을 빼는 방향으로 움직여야 하강합니다.

$\theta' = \theta - \epsilon\frac{df(\theta; x)}{d\theta}$

여기서 $ \epsilon $은 그 방향으로 얼마나 움직일 지를 나타냅니다. 이 $ \epsilon $은 학습속도(learning rate)라고 합니다. $x$가 얼마나 변할 지는 $ \epsilon $과 기울기의 크기 $ ||\frac{df(x)}{dx}||$에 따라 결정됩니다. $ \epsilon $을 상수로 두어도, 기울기가 크면 많이 움직이고 기울기가 작으면 적게 움직이게 됩니다. 즉, 더 이상 $x$가 변하지 않는 점은 미분한 값이 0이 되는 점입니다. 이 점에 도달했을 때는 $x$가 거의 바뀌지 않는 것으로 극소값에 도달했다는 것을 알 수 있습니다. 보통 $ \epsilon $으로는 0.01, 0.005, 0.001 정도의 값을 사용합니다.

def GradientDescent(loss, vars, lr=0.001):
    grads = tf.gradients(loss, vars)
    var_updates = []
    for grad, var in zip(grads, vars):
        var_updates.append(var.assign_sub(lr * grad))
    train_op = tf.group(*var_updates)
    return train_op  # sess.run(train_op)

주의: 이 문서의 코드들은 아직 확인되지 않았습니다. TF는 아예 최적화 도구(optimizer)들을 제공하기 때문에, 위와 같은 방식으로 TF 프로그래밍을 통해 SGD 등을 구현할 일은 거의 없습니다. 식과 코드가 어떻게 연결되는지 보는 정도로 생각해 주세요.

Nonconvex optimization

어떤 함수가 모든 정의역에서 볼록하면 볼록 함수(convex function), 오목하면 오목 함수(concave function)이라고 합니다. 이런 함수들은 전체 최대값/최소값이 곧 극대값/극소값이 됩니다. 이런 함수들에서는 GD가 아주 잘 작동하기 때문에 GD만 계속 반복해서 수행하더라도 무조건 우리가 원하는 최소값에 도달할 수 있습니다. 하지만 이런 함수는 아주 드물고, 딥러닝에서 우리가 다루는 함수는 늘 비볼록 함수(nonconvex function)입니다. 따라서 우리가 인공신경망을 GD로 훈련하는 이상, 전체 최소값에에 도달하기는 거의 불가능합니다. 사실 전체 최소값에 도달했는지조차 알 수 없습니다. 그럼에도 불구하고, 비볼록 함수에서도 GD가 잘 동작하도록 하기 위해 할 수 있는 일들이 있습니다.

다양한 시작점에서 시작해보기. 어차피 극소값까지밖에 못 갈 거라면 이왕이면 좋은 출발점에서 시작하는 것이 무조건 좋습니다. 어디가 좋은 출발점인지는 훈련하고 결과를 봐야 알 수 있긴 합니다.
학습 속도 변경해보기. 계속 큼지막하게 이동하다가는 세밀하게 움직여야 도달할 수 있는 조금 더 성능 좋은 점을 발견하지 못할 수도 있기 때문에, 어느 정도 성능이 수렴하면 학습 속도를 낮춰 좀 더 촘촘히 움직여 보는 것도 좋습니다.

Saddle point problem

기울기가 0이 되는 점은 크게 세 가지입니다. 극대, 극소, 안장점(saddle point) 입니다. 극대/극소에 빠지면 기울기가 0이 되기 때문에 일반적인 GD로는 벗어날 수 없고, 주변에도 이보다 더 좋은 점은 없습니다. 하지만 안장점에 빠지면 더 나은 점들이 옆에 있음에도 불구하고 기울기가 0이라 움직이지 못합니다.

최근 딥러닝 연구들은 딥러닝에서 기울기가 0인 점들은 거의 대부분이 안장점이기 때문에 탈출 방법만 잘 만들면 탈출할 수 있다고 이야기하고 있습니다. 또한 엄청나게 많은 극소값들이 존재하지만, 대부분 극소값에서의 성능이 전체 최소값에서의 성능과 거의 비슷할 것이기 때문에 GD가 큰 문제가 되지 않는다고 이야기하고 있습니다. 간략히 생각하면 이렇습니다. 딥러닝에서 한 표현 벡터는 수백 차원이 넘습니다. 그 모든 차원에서 기울기가 0인 일은 거의 불가능하기 때문에, 꾸준히 움직이면 적어도 어느 한 차원에서는 계속 값이 작아지게 되고 그러다 보면 안장점을 통과하게 됩니다. 사실, 위 식처럼 일차 미분을 사용하는 것이 아니라 헤시안(Hessian) 행렬을 사용하는 2차 미분 및 뉴턴 하강법(Newton's method) 등을 사용하면 안장점도 전혀 문제없이 최소가 되는 방향으로 이동할 수 있습니다. 하지만 2차 미분을 구하는 것은 훨씬 복잡합니다. 어떻게 해야 GD 기반으로 하면서도 안장점을 잘 통과할 수 있을까요?

Lipschitz Assumption

생각해 보면 GD가 이상하게 느껴질 수도 있습니다. 변수들의 상태 A를 기준으로 해서 성능을 측정하고 그 성능이 좋아지도록 변수들을 바꾸면 그 순간 상태 B가 될 텐데(새로운 형태의 변수공간), 거기서도 성능이 이전보다 좋아질 것이라고 말할 수 있는 걸까요? 네. 됩니다. 우리가 만든 인공신경망은 거의 언제나 Lipschitz 가정을 만족하는 함수라고 할 수 있기 때문입니다. Lipschitz 가정이란, 입력의 아주 작은 변화가 출력의 아주 작은 변화로 나타난다는 것, 즉 출력이 나비효과로 엄청나게 변하지 않는다는 가정입니다. 그래도 계속 훈련을 하다 보면 언제나 성능이 좋아지지는 않고, 가끔 성능이 거꾸로 나빠지는 것을 보게 됩니다. 너무 당황하지 마세요! 곧 다시 제자리를 찾을 겁니다.

Stochastic Gradient Descent

GD는 기본적으로 기울기를 하강시키면 좋은 결과로 갈 수 있다는 알고리즘입니다. 그런데, 이 기울기를 구하는 데이터에 따라 GD의 종류가 약간 바뀔 수 있습니다. 가장 많이 사용되는 확률적 경사 하강법(Stochastic GD, SGD)은 한 번에 전체 데이터가 아닌 $B$개 씩을 계산하고 그 정보로 훈련을 진행합니다. 그리고 매번 어떤 데이터들을 쓸 지 전체 데이터 중 무작위로 뽑아 사용합니다. 그래서 확률적이라고 이야기합니다. 예를 들어, 10만 개의 데이터가 있고 100개씩 뽑아 훈련하는데 사용한다면 1000번 훈련하면 한 번 데이터 전체를 다 본 것이 됩니다. 이렇게 한 번 데이터 전체를 다 보는 것을 1 에포크(epoch)가 지났다고 하고, 보통 수십~수백 번의 에포크를 거쳐 훈련이 이루어집니다. 매 에포크마다 미니배치를 만드는 순서는 반드시 섞어(shuffle) 줘야 합니다!

데이터 전체는 배치(Batch, Full batch)라고 합니다. 데이터의 일부, 즉 $B$개는 미니배치(mini-batch)라고 하고, $B$의 크기를 배치 크기(batch size)라고 합니다. 데이터를 일부만 보는 데는 이유가 있습니다. 전체 데이터를 한 번에 보고 훈련하면 우선 계산량이 너무 많고, 너무 훈련 속도가 느리고, 기울기가 이도저도 아닌 방향으로 만들어질 수 있습니다. 반면, 일부 데이터씩 보고 훈련하면 계산량을 적절히 조절할 수 있고, 그 데이터에 대해 우선적으로 최적화하니 훈련 속도도 빠릅니다. 아무리 데이터가 많아도 배치 크기를 같게 사용한다면 매 업데이트마다 비슷하게 동작하도록 할 수 있습니다. 어차피 일부 데이터라고 해도 전체 데이터의 프록시(proxy)로 잘 동작하기 때문에 미니배치를 쓴다고 해도 충분히 수렴할 수 있습니다. 다만, 배치 크기가 클 수록 전체 데이터를 보는 것에 가까워지고, 최종 수렴 성능이 더 좋을 수 있습니다.(만약 수렴한다면) 그리고 너무 작은 배치 크기는 데이터를 잘 반영하지 못하고 너무 업데이트가 잦아 오히려 훈련도 안 되고 시간도 오래 걸릴 수 있습니다.

SGD를 사용할 때는 여러 개의 데이터에 대해 얻은 기울기의 합 또는 평균으로 기울기를 사용합니다. 보통 배치 크기에 영향을 받지 않도록 평균을 사용합니다. 식으로 쓰면 다음과 같습니다. 앞으로는 $B$를 쓰는 것이 번거롭기 때문에 생략할 수도 있지만, 기본적으로 다 적용되어 있다고 생각해 주세요.

$\theta' = \theta - \epsilon\times\frac{1}{B}\sum_{i=1}^{B}\frac{df(\theta; x_i)}{d\theta}$

Momentum

GD 알고리즘의 단점은 기울기 0인 점을 잘 탈출하지 못한다는 것 외에도 너무 훈련이 느리다는 점입니다. 이를 해결하기 위해서 보편적으로 사용되는 방법이 관성(momentum)을 적용하는 것입니다. 관성이란, 변수가 가던 방향으로 계속 가도록 하는 속도(velocity) 항을 추가하는 것입니다. 지금 상태의 기울기에도 당연히 영향을 받지만, 지금의 기울기는 가던 방향을 약간씩만 바꿔 주는 역할을 하게 됩니다. 바른 방향으로 가고 있다면 점점 더 속도가 빨라지게 되어 더 빨리 훈련이 될 수도 있고, 현재 기울기가 0인 안장점이더라도 속도가 있으니 계속 이동해 안장점을 더 잘 탈출할 수 있게 됩니다.

새로운 속도는 이전 속도와의 지수평균(exponential average)를 통해 계산됩니다. 학습속도 $\epsilon$처럼, 지수평균에 사용되는 모멘텀 상수(momentum rate) $\alpha$가 있습니다. 모멘텀 상수가 클수록 이전 속도를 더 따르게 됩니다.

$v' = \alpha v - \epsilon\frac{\partial f(\theta;x)}{\partial \theta} \\ \theta' = \theta + v'$

모멘텀 상수는 0.5 정도로 시작해서 어느 정도 감소 추세가 안정화되면 0.9로 늘려 사용합니다. 다양한 안정화 기법이 나온 요즘에는 시작부터 0.9로 진행하기도 합니다. 같은 방향으로 많이 움직일 수록 속도도 빨라지게 됩니다. 언제 속도가 일정해지는지는 $v=v'$일 때를 보면 알 수 있습니다.

$(1-\alpha)v = -\epsilon\frac{\partial f(\theta;x)}{\partial \theta} \\ v = -\frac{\epsilon}{1-\alpha}\frac{\partial f(\theta;x)}{\partial \theta}$

즉, 모멘텀을 사용한다는 것은 학습 속도를 $\frac{1}{1-\alpha}$ 만큼으로 보정하는 것이라고 해석할 수 있습니다. $\alpha$를 0.9로 한다는 것은, 기존 대비 약 10배 정도의 속도로 움직이도록 한다고 볼 수 있습니다.

def Momentum(loss, vars, velocity_vars, lr=0.001, alpha=0.9):
    grads = tf.gradients(loss, vars)
    var_updates = []
    velocity_updates = []
    for grad, var, velocity in zip(grads, vars, velocity_vars):
        new_velocity = alpha * velocity - lr * grad
        var_updates.append(var.assign_add(new_velocity))
        velocity_updates.append(velocity.assign(new_velocity))
    updates = var_updates + velocity_updates
    train_op = tf.group(*updates)
    return train_op  # sess.run(train_op)

Nesterov Momentum

앞서 Lipschitz 아이디어처럼, 위의 관성 알고리즘에서도 비슷한 질문을 할 수 있습니다. 왜냐하면, 관성으로 달려가는 방향은 결국 예전 상태(들)이 만든 방향이기 때문입니다. Nesterov가 이런 문제의식으로 만든 Nesterov 가속 관성(Nesterov Accelerated Momentum, NAG)알고리즘은 특히 많이 사용되고 있습니다. 기존 알고리즘과 달라진 점은, 이전의 $\theta$ 대신 '바뀔' $\theta$를 근사해서 사용한다는 점입니다. 즉, 지금의 속도로 달려갔을 때 '도달할' 점에서의 기울기를 계산해 더합니다.

nesterov

$v' = \alpha v - \epsilon\frac{\partial f(\theta+\alpha v;x)}{\partial \theta} \\ \theta' = \theta + v'$

하지만 아직 업데이트도 하지 않았는데 바뀐 변수의 값을 넣어 기울기를 계산하기는 힘듭니다. 보통은 현재 변수만으로 계산할 수 있도록 아래처럼 근사해 구현합니다.

$v' = \alpha v - \epsilon\frac{\partial f(\theta;x)}{\partial \theta} \\ \theta' = \theta + \alpha v' -\epsilon\frac{\partial}{\partial x}f(x)$

def Nesterov(loss, vars, velocity_vars, lr=0.001, alpha=0.9):
    grads = tf.gradients(loss, vars)
    var_updates = []
    velocity_updates = []
    for grad, var, velocity in zip(grads, vars, velocity_vars):
        new_velocity = alpha * velocity - lr * grad
        var_updates.append(var.assign_add(alpha * new_velocity - lr * grad))
        velocity_updates.append(velocity.assign(new_velocity))
    updates = var_updates + velocity_updates
    train_op = tf.group(*updates)
    return train_op  # sess.run(train_op)