경사 하강법

경사 하강법을 실행하는 모습. $x_{0}$에서 시작하여, 경사가 낮아지는 쪽으로 이동하여 차례대로 $x_{1},x_{2},x_{3},x_{4}$를 얻는다.

경사 하강법(傾斜下降法, Gradient descent)은 1차 근삿값 발견용 최적화 알고리즘이다. 기본 개념은 함수의 기울기(경사)를 구하고 경사의 반대 방향으로 계속 이동시켜 극값에 이를 때까지 반복시키는 것이다.

설명

최적화할 함수 $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}$는 이동할 거리를 조절하는 매개변수이다.

이 알고리즘의 수렴 여부는 f의 성질과 $\gamma _{i}$의 선택에 따라 달라진다. 또한, 이 알고리즘은 지역 최적해로 수렴한다.

따라서 구한 값이 전역적인 최적해라는 것을 보장하지 않으며 시작점 $\mathbf {x} _{0}$의 선택에 따라서 달라진다.

이에 따라 다양한 시작점에 대해 하강법을 적용하여 그 중 가장 좋은 결과를 선택할 수도 있다.

평가 및 장단점

경사 하강법은 모든 차원과 모든 공간에서의 적용이 가능하다. 심지어 무한 차원상에서도 쓰일 수 있다. (이 경우 해당 차원이 만들어내는 공간을 함수 공간이라고 한다.)

정확성을 위해서 극값으로 이동함에 있어 매우 많은 단계를 거쳐야하며, 주어진 함수에서의 곡률에 따라서 거의 같은 위치에서 시작했음에도 불구하고 완전히 다른 결과로 이어질 수도 있다.

프로그램 코드 예제

다음은 파이썬 언어로 작성한 경사 하강법 알고리즘으로, f(x)=x⁴−3x³+2 함수의 극값을 미분값인 f′(x)=4x³−9x²를 통해 찾는 예를 보여준다.

# 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
eps = 0.01 # step size
precision = 0.00001

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

while abs(x_new - x_old) > precision:
    x_old = x_new
    x_new = x_old - eps * f_prime(x_old)

print(f"Local minimum occurs at: {x_new}")

이는 x 값 하나에 대해서만 극값을 파악한다. 실제로는 여러 개의 특징값(feature)들이 있으므로 해당 값들마다 병행적으로 결과 값을 구하면서 반복해야 한다.