경사 하강법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
경사 하강법을 실행하는 모습. x_0에서 시작하여, 경사가 낮아지는 쪽으로 이동하여 차례대로 x_1, x_2, x_3, x_4를 얻는다.

경사 하강법(gradient descent)은 1차 근삿값 발견용 최적화알고리즘이다. 기본 아이디어는 함수의 기울기(경사)를 구하여 기울기가 낮은 쪽으로 계속 이동시켜서 극값에 이를 때까지 반복시키는 것이다.[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)=x4−3x3+2 함수의 극값을 미분값인 f'(x)=4x3−9x2 를 통해 찾는 예를 보여준다.[2]

# 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 "Local minimum occurs at ", x_new

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

확장[편집]

관련 주제[편집]

주석[편집]

  1. 기울기가 높은 곳으로 이동하는 것은 경사 상승법이라고 한다.
  2. 미분을 통해 계수를 유도하는 이유는 기울기를 구하기 위해서이다. 함수의 그래프에서 미분값은 특정 지점에서의 접선기울기를 의미한다. 좀 더 빨리 값을 얻기 위해서 기울기에 학습 비율(learning rate)을 곱하는 것이 일반적이다.