Gradient Descent 탐색 방법

기본적인 함수 최적화(optimization) 방법 중 하나인 gradient descent 방법에 관한 글입니다.

Gradient descent 방법은 미분의 개념을 최적화 문제에 적용한 대표적 방법 중 하나로서 함수의 local minimum을 찾는 방법 중 하나입니다. Gradient descent 방법을 다른 말로 steepest descent 방법이라고도 부릅니다.

1. Gradient descent 방법의 직관적 이해

자신이 한치앞도 잘 안보이는 울창한 밀림에 있을 때 산 정상으로 가기 위한 방법은 간단합니다. 비록 실제 산 정상이 어디에 있는지는 모르지만 현재 위치에서 가장 경사가 가파른 방향으로 산을 오르다 보면 언젠가는 산 정상에 다다르게 될 것입니다.

또는 이와 반대로 깊은 골짜기를 찾고 싶을 때에는 가장 가파른 내리막 방향으로 산을 내려가면 될 것입니다.

이와 같이 어떤 함수의 극대점을 찾기 위해 현재 위치에서의 gradient 방향으로 이동해 가는 방법을 gradient ascent 방법, 극소점을 찾기 위해 gradient 반대 방향으로 이동해 가는 방법을 gradient descent 방법이라 부릅니다.

2. Gradient(그레디언트)

(gradient의 개념에 대해서는 Gradient, Jacobian 행렬, Hessian 행렬, Laplacian 글에서 설명한 바 있지만 설명의 연속성을 위해서 이곳에 다시 관련 내용을 적습니다)

어떤 다변수 함수 f(x1,x2,...,xn)이 있을 때, f의 그레디언트(gradient)는

 --- (1)

와 같이 정의됩니다. 즉, 그레디언트(gradient)는 위 식과 같이 각 변수로의 일차 편미분 값으로 구성되는 벡터입니다. 그리고 이 벡터는 f의 값이 가장 가파르게 증가하는 방향을 나타냅니다. 또한 벡터의 크기는 그 증가의 가파른 정도(기울기)를 나타냅니다.

예를 들어, f(x,y) = x² + y²의 그레디언트(gradient)를 구해보면

--- (2)

이므로, (1,1)에서 f값이 최대로 증가하는 방향은 (2,2), 그 기울기는 ∥(2,2)∥= sqrt(8) 입니다.

<그림 1> f(x,y) = x² + y² 그래프

또한 반대로 그레디언트(gradient)에 음수를 취하면 즉, -▽f는 f값이 가장 가파르게 감소하는 방향을 나타내게 됩니다.

이러한 그레디언트의 특성은 어떤 함수를 지역적으로 선형근사(linear approximation)하거나 혹은 함수의 극점(최대값, 최소값 지점)을 찾는 용도로 활용될 수 있습니다.

3. Gradient descent 방법

최적화 알고리즘 중 하나로 널리 알려진 gradient descent 방법은 이러한 그레디언트의 특성을 이용하여 어떤 비용함수의 값을 최소화시키기 위한 파라미터 값을 아래와 같이 점진적으로 찾는 방법입니다.

 --- (3)

즉, 어떤 초기값 x₀ = (x1₀,...,xn₀)부터 시작하여 위 식에 따라 gradient 반대 방향으로 x를 조금씩 이동시키면 f(x)가 극소가 되는 x를 찾을 수 있다는 방법이 gradient descent 방법입니다.

☞ 만일 함수의 극소점이 아니라 극대점을 찾는 것이 목적이라면 식 (3) 대신에 아래의 식 (4)를 이용하여 x를 업데이트합니다 (gradient ascent 방법)

 --- (4)

<그림 2> gradient descent 방법 (그림출처: 위키피디아)

식 (3)에서 λ는 알고리즘의 수렴속도를 조절하는 파라미터로서 step size 또는 learning rate라 불립니다.

Gradient descent 방법의 문제점은 쉽게 생각할 수 있듯이 local minimum에 빠지는 것입니다. 즉, 이쪽이 산 정상인줄 알고 열심히 올라갔더니 막상 여기는 작은 언덕 정도이고 바로 옆에 훨씬 높은 산이 있는 경우입니다.

Gradient descent 방법의 또 하나의 문제점은 해에 근접할수록 |∇f|가 0에 가까워지기 때문에 수렴속도가 느려진다는 것입니다. 그렇다고 수렴속도를 조절하는 step size 파라미터 λ를 너무 크게 하면 알고리즘이 발산할 수 있는 문제점이 있습니다 (step size를 자동으로 adaptive하게 조절하는 방법도 있는 것 같습니다).

4. Gradient descent 방법의 이해와 활용

Gradient descent 방법에 대해서는 그 기본적인 개념만 이해하고 있으면 된다고 생각합니다. 그 핵심은 함수의 극대값 또는 극소값을 구하기 위해 현재 위치에서 함수값의 변화가 가장 큰 방향으로 이동한다는 것이므로 함수값의 변화가 가장 큰 방향을 구할 수만 있다면 다양한 문제에 똑같은 개념을 적용할 수 있습니다.

[일변수 스칼라 함수의 극대, 극소 구하기]

즉, 다변수 스칼라 함수(scalar-valued function of multiple variables)의 경우에는 gradient(그레디언트)를 이용하여 최대 증가 방향을 찾았지만 일변수 함수의 경우에는 통상적인 일차 미분값 f'(x)을 이용하면 될 것입니다. 예를 들어, f(x) = x² + 3x + 1가 극소가 되는 점 및 극소값을 구하고 싶다면 식을 다음과 같이 세울 수 있습니다.

--- (5)

[비선형 연립방정식의 풀이]

선형연립방정식으로 주어지는 Least Square 문제는 [선형대수학 #5] 선형연립방정식 풀이 글에서 설명한 바와 같이 SVD나 Pseudo-inverse를 이용하여 계산할 수 있습니다. 그리고 비선형연립방정식으로 주어지는 Least Square 문제는 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method) 글에서 설명한 Gauss-Newton 법으로 풀 수 있습니다. 여기서는 비선형연립방정식으로 주어지는 Least Square 문제를 gradient descent 방법으로 푸는 방법에 대해 살펴보겠습니다.

 --- (6)

식 (6)을 동시에 만족시키는 x = (x1,...,xn)을 구하는 문제는 결국 아래의 E를 최소화시키는 x를 구하는 LS(Least Square) 문제로 볼 수 있습니다.

--- (7)

단, F = [f1 ... fm]^T는 F:Rⁿ→R^m인 다변수 벡터 함수.

어떤 초기값(식 (7)의 E를 극소로 만드는 x에 대한 초기 추정값) x₀ = (x1₀,...,xn₀)부터 시작하여 아래와 같은 gradient descent 탐색을 반복하면 E의 극소점을 근사적으로 찾을 수 있습니다.

 --- (8)

그런데 ▽E를 직접 구하여 식 (8)을 적용해도 되지만, E = F^TF 로부터 ▽E = 2J_F^TF 이므로 아래 식과 같이 F의 Jacobian인 J_F를 이용하여 해를 탐색해도 됩니다.

--- (9)

5. 뉴턴 방법과 비교

Newton 방법은 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method) 글에서 설명한 바 있습니다만, 방정식(f = 0)의 해를 점진적으로 찾는 방법입니다. 즉, gradient descent 방법은 함수의 극대, 극소를 찾는 방법이고 Newton 방법은 함수값이 0이 되는 해를 찾는 방법입니다. 하지만 그 내부의 원리는 거의 유사하며(일차미분의 원리가 사용됨) 함수 f의 극대, 극소를 구하기 위해 gradient descent 방법을 직접 적용해도 되지만, f가 극대, 극소인 점은 f' = 0인 점이기도 하므로 뉴턴법으로 f' = 0인 점을 구해도 됩니다.

정리해 보면, 똑같은 함수 최적화 문제를 gradient descent 방법으로도 풀 수 있고, 뉴텁법(Newton's method)이나 가우스-뉴턴법(Gauss-Newton method)으로도 풀 수 있음을 알수 있습니다. 어떤 방법이 더 효율적인지는 저도 잘 모릅니다. 다만, 한가지 gradient descent 방식과 가우스-뉴턴법의 차이를 살펴보면 gradient descent 방법은 step size 파리미터 λ가 필요한 반면에 뉴턴법(뉴턴-랩슨법)이나 가우스-뉴턴법의 경우는 step size 파라미터가 필요 없다는 점입니다. 그 이유는 뉴턴법 계열에서는 현재의 함수값과 미분값(기울기)으로부터 step size를 자동으로 결정하기 때문입니다. 또한, 뉴턴법 또는 가우스-뉴턴법은 해를 찾는 수렴속도가 빠르고 해 근처에서 수렴속도가 급격히 느려지는 문제점도 없습니다. 따라서, 개인적인 생각으로는 (확실치는 않지만) 함수 최적화 문제에 있어서 gradient descent 방법보다는 뉴턴법 계열이 좀더 효율적이지 않나 생각됩니다. 하지만 뉴턴법으로는 f'(x) = 0인 x를 구하기 때문에 극대, 극소를 구분하여 찾을 수 없고, 또한  f'(x) = 0이라 해서 반드시 f가 해당 지점에서 극점인 것은 아니므로 Hessian 테스트 등과 결합하여 사용해야 할 것입니다.

☞ Hessian 테스트는 f'(x)=0인 지점에서 Hessian 행렬의 고유값들을 구한 후 고유값들의 부호를 조사하여 극대, 극소 여부를 판별하는 테스트임. 자세한 내용은 Gradient, Jacobian 행렬, Hessian 행렬, Laplacian 글을 참조하기 바랍니다.

by 다크 프로그래머