Skip to content

Gradient descent

경사 하강법(gradient descent)은 1차 근삿값 발견용 최적화 알고리즘이다. 기본 아이디어는 함수의 기울기(경사)를 구하여 기울기가 낮은 쪽으로 계속 이동시켜서 극값에 이를 때까지 반복시키는 것이다.

한마디로 주어진 Cost function의 지역 최적해 (Maxima and minima) 값을 찾는 것을 말한다.

설명

최적화할 함수 \(f(\mathbf{x})\)에 대하여, 먼저 시작점 \(\mathbf{x}_0\)를 정한다. 현재 \(\mathbf{x}_i\)가 주어졌을 때, 그 다음으로 이동할 점인 \(\mathbf{x}_{i+1}\)은 다음과 같이 계산된다.

$$ \mathbf{x}_{i+1} = \mathbf{x}_i - \gamma_i \nabla f(\mathbf{x}_i) $$

이때 \(\gamma_i\)는 이동할 거리(알고리즘의 수렴속도)를 조절하는 매개변수이며, Step size 또는 Learning rate 라 불린다.

(참고로 \(\gamma\)는 그리스어 '감마' 이다)

이 알고리즘의 수렴 여부는 \(f\)의 성질과 \(\gamma_i\)의 선택에 따라 달라진다. 또한, 이 알고리즘은 지역 최적해 (Maxima and minima)로 수렴한다. 따라서 구한 값이 전역적인 최적해라는 것을 보장하지 않으며 시작점 \(\mathbf{x}_0\)의 선택에 따라서 달라진다. 이에 따라 다양한 시작점에 대해 여러 번 경사 하강법을 적용하여 그 중 가장 좋은 결과를 선택할 수도 있다.

In the Machine learning

Gradient Descent라는 것은 Gradient계산을 통해 함수의 Local minimum을 찾아가는 과정이다. 함수가 가장 빠르게 감소하는 방향으로 쭉 따라 내려가다보면 가장 낮은 지점까지 도달하고 그것이 바로 Local minimum이다. 산 위에서 가장 빠르게 아래로 내려가는 방향을 따라서 산을 내려가는 것이라고 생각하면 간단하다.

600px-Extrema_example_original.svg.png

그런데 문제가 하나 있는데, 산을 내려오더라도 우리는 지금 위치에서 가장 빠르게 내려가는 길을 구하는 것이지 전체에서 가장 낮은 지점으로 내려가는 것은 아니기 때문에 항상 전체 함수에서 가장 낮은 값으로 수렴하지는 않는 다는 것이다. 때문에 초기에 어느 지점에서부터 내려가느냐가 그 결과값에 영향을 크게 미치게 되는 것이다. 머신러닝에서는 상당히 자주 쓰이는 개념이고 이 Local minimum problem은 끝까지 성능에 있어서 치명적인 단점이 되는 경우가 많다.

from the Loss function

손실함수 (Loss function)부터 설명하겠다. Loss function이 가장 작은 값을 가지는 Hypothesis를 선택하면 된다. 그렇다면 그 값은 어떻게 찾을 것인가? 여러가지 방법이 있지만, 일반적으로는 Gradient desent라는 방법을 사용한다. Gradient descent란 쉽게 생각하면 긿을 잃은 상태에서 산을 내려가는 방법이라고 생각하면 된다.

  1. 산을 가장 빠르게 내려가기 위해서는 아마 현재 내가 서있는 지점에서 가장 경사가 가파른 지점을 향해서 내려가고,
  2. 움직인 위치에서 다시 한번 경사가 가장 가파른 지점을 향해서 내려가고,

이 과정을 반복하다보면 언젠가 가장 낮은 지점으로 이동할 수 있을 것이다.

Fff.png

위의 그림에서 볼 수 있듯 가장 경사가 가파른 지점을 따라 내려 걸어가다보면 가장 낮은 지점으로 도달할 수 있을 것이다. 그런데 여기에서 문제가 하나 발생한다. 만약에 Initial Condition이 작은 봉우리가 아니라 반대쪽 높은 봉우리였다면? 그렇다면 우리는 아마 Global minimum, 즉 전체에서 가장 낮은 지점이 아닌 Local minimum, 즉 주변에서 가장 낮은 지점으로 이동하게 될 것이다. 전체에서 가장 작은 값과 그 주변에서 가장 작은 값을 선택하는 것은 분명 큰 차이가 있다. 하지만 이런 단점에도 불구하고 gradient descent는 매우 많이 쓰이는 방법 중 하나이다. 그 이유는 아래와 같다.

  • 구현이 쉽다.
  • 모든 차원 및 공간으로 확대가 가능하다.

Gradient descent는 또한 내가 속도를 조절할 수 있다. 산을 내려갈 때 얼마나 움직인 다음 방향을 바꿀 것인가에 따라 수렴 속도가 급격하게 변한다. 너무 그 폭이 작으면 시간이 너무 오래걸리고, 폭이 너무 크면 최악의 경우에 한 지점에 수렴하지 못할 수도 있다. 그 뿐 아니라 경우에 따라서는 gradient descent가 끝이 나지 않을 수도 있다. 하지만 여러 방법으로 그 단점들을 보완할 수 있고 무엇보다 아래 코드에서도 확인할 수 있듯 구현이 너무 간단하기 때문에 상당히 많이 쓰이는 방법이다.

Linear regression example

간단한 Linear regression에서 아래와 같은 그래프가 출력되는데, 독립 변수(independent variable)가 두 개일 때 나타나는 등고선 그래프 이다.

Machine_learning_-_Comparison_of_a_few_optimization_methods.gif

좀더 이해하기 쉬운 이미지로, 아래의 그래프를 위에서(z축) 본다고 가정하면 된다. (y = ax + b에서 a와 b의 Cost 그래프라고 생각하면 된다)

Linear_Regression_-Gradient_descent-_3d_graph.jpg

Sample code 

# From calculation, we expect that the local minimum occurs at x=9/4

x_old = 0
x_new = 6 # The algorithm starts at x=6
gamma = 0.01 # step size
precision = 0.00001

def f_derivative(x):
    return 4 * x**3 - 9 * x**2

while abs(x_new - x_old) > precision:
    x_old = x_new
    x_new = x_old - gamma * f_derivative(x_old)

print("Local minimum occurs at", x_new)

Sample code 2

GradientDescent:Example항목을 참조.

See also

Favorite site

References

  1. Visualizing_the_gradient_descent_method.pdf ↩