문득 생각나서 찾아보니 작년 8월 말 경에 블로그 10만명 방문을 자축하는 글을 올린 적이 있습니다.

그리고 사랑하는 마나님께서 누적 방문객 20만이 되면 마나님배 이벤트를 연다고 공언하셨는데, 실제 20만 됐을 때는 그냥 유야무야 지나가 버렸습니다. ㅠ.ㅠ

그리고 벌써 며칠전에 방문객 수가 30만이 넘었습니다.

사실 20만이 되었을 때 기억을 못해낸 것은 아닌데, 막상 좋은 방법이 떠오르지 않았습니다. 만일 책이라도 냈다면 책을 보내드렸을 터인데 그런것도 아니고, 그렇다고 도서 상품권 같은 것을 보내기도 그렇고... 어쨌든 20만 때는 그냥 지나가 버렸지만 늦게라도 약속을 지켜야 할텐데 걱정입니다..

by 다크 프로그래머

기본적인 함수 최적화(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 다크 프로그래머

Gradient(그레디언트), Jacobian(야코비언) 행렬, Hessian(헤시안) 행렬, Laplacian(라플라시안) ...

문득 정리의 필요성을 느껴서 적어봅니다.

이들을 함께 보는 이유는? 그냥 왠지 이들은 세트로 함께 봐야 할 것 같은..

참고한 자료는 제가 항상 애용하는 위키피디아입니다.

- Gradient(그레디언트): http://en.wikipedia.org/wiki/Gradient

- Jacobian(야코비언) 행렬: http://en.wikipedia.org/wiki/Jacobian_matrix

- Hessian(헤시안) 행렬: http://en.wikipedia.org/wiki/Hessian_matrix

- Laplacian(라플라시안): http://en.wikipedia.org/wiki/Laplace_operator

1. Gradient, Jacobian, Hessian, Laplacian 요약

- Gradient(그레디언트)

- Jacobian(야코비언) 행렬

- Hessian(헤시안) 행렬

- Laplacian(라플라시안)

2. Gradient(그레디언트)

어떤 다변수 함수 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값이 가장 가파르게 감소하는 방향을 나타내게 됩니다.

이러한 gradient의 특성은 어떤 함수를 지역적으로 선형근사(linear approximation)하거나 혹은 gradient descent 방법(Gradient Descent 탐색 방법 글 참조)처럼 함수의 극점(최대값, 최소값 지점)을 찾는 용도로 활용될 수 있습니다.

Gradient를 이용한 다변수 scalar 함수 f의 점 p 근처에서의 선형 근사식은 다음과 같습니다 (first order Taylor expansion).

 --- (3)

영상처리에서 gradient(그레디언트)는 영상의 edge 및 edge 방향을 찾는 용도로 활용될 수 있습니다. 이미지 I(x,y)를 (x,y)에서의 픽셀의 밝기를 나타내는 함수로 보고 각 픽셀 위치에서 gradient의 크기와 방향을 구하면 해당 픽셀이 얼마나 edge에 가까운지, 그리고 edge의 방향이 어디인지 쉽게 알 수 있습니다.

 --- (4)

<그림 2> gradient를 이용한 영상 edge 검출

3. Jacobian(야코비언) 행렬

어떤 F:Rⁿ→R^m 함수 F(x1,...,xn) = (f1(x1,...,xn), ..., fm(x1,...,xn))에 대한 Jacobian(야코비언) 행렬은

 --- (5)

로 정의됩니다.

예를 들어, F(x,y) = (2x+y, xy) 인 F:R²→R² 함수라면

 --- (6)

가 됩니다.

즉, Jacobian(야코비언)은 어떤 다변수 벡터함수(vector-valued function of multiple variables)에 대한 일차 미분(first derivative)으로 볼 수 있습니다.

☞ 앞서 나온 gradient(그레디언트)나 Jacobian(야코비언)이나 모두 함수에 대한 일차 미분(first derivative)을 나타낸다는 점에서는 동일합니다. 다만, 그레디언트는 다변수 스칼라 함수(scalar-valued function of multiple variables)에 대한 일차 미분인 반면 Jacobian(야코비언)은 다변수 벡터 함수(vector-valued function of multiple variables)에 대한 일차미분입니다. 즉, 그레디언트는 통상적인 일변수 함수의 일차미분을 다변수 함수로 확장한 것이고, Jacobian(야코비언)은 이를 다시 다변수 벡터함수로 확장한 것입니다.

Jacobian(야코비언)이나 그레디언트나 모두 함수에 대한 일차미분이기 때문에 미분이 가지고 있는 의미나 성질은 모두 동일하게 적용됩니다. 즉, 어떤 함수의 지역적인 변화특성을 파악할 때, 지역적인 함수의 변화를 선형근사할 때 또는 함수의 극대(극소)를 찾을 때 활용될 수 있습니다.

예를 들어, 점 p∈Rⁿ 근처에서 F를 선형근사할 때 Jacobian(야코비언)을 다음과 같이 활용할 수 있습니다 (first order Taylor expansion).

 --- (7)

Jacobian(야코비언)이 비선형 연립방정식의 해를 구하는 목적으로 활용되는 예에 대해서는 [기계학습] - 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method) 글을 참조하기 바랍니다.

4. Hessian(헤시안) 행렬

어떤 다변수 함수 f(x1,x2,...,xn)가 있을 때, f의 Hessian 행렬은

 --- (8)

와 같이 정의됩니다.

앞서 설명한 gradient(그레디언트), Jacobian(야코비언)이 모두 함수에 대한 일차미분(first derivative)를 나타내는 반면 Hessian은 함수의 이차미분(second derivative)를 나타낸다는 점에서 차이가 있습니다.

즉, Hessian은 함수의 곡률(curvature) 특성을 나타내는 행렬로서 최적화 문제에 적용할 경우 Hessian을 이용하면 다음 식과 같이 p 근처에서 함수를 2차 항까지 근사시킬 수 있습니다 (second-order Taylor expansion)

$f(x)\simeq f(p)+\triangledown f(p)(x-p)+\frac{1}{2}(x-p)^TH(p)(x-p)$ --- (9)

또한 Hessian은 critical point의 종류를 판별하는데 활용될 수 있습니다. 어떤 함수의 일차미분이 0이 되는 되는 점을 critical point (또는 stationary point)라 부르는데 함수의 극점(극대, 극소), saddle point 등이 여기에 해당됩니다 (쉽게 생각하면, 고교수학 미분에서 f'(x) = 0이 되는 지점).

어떤 (다변수) 함수를 최적화시키기 위해 극점(극대, 극소)을 찾기 위해서는 먼저 그 함수의 일차미분인 gradient(그레디언트)가 0이 되는 지점(critical point)을 찾습니다. 그런데, 이렇게 찾은 critical point가 극대점인지 극소점인지, 아니면 saddle point(말안장처럼 방향에 따라서 극대, 극소가 바뀌는 점)인지 구분하기 위해서는 이차미분값을 조사해야 하는데 이 때 바로 Hessian을 사용할 수 있습니다.

그 구체적인 방법은, 어떤 함수의 critical point에서 계산한 Hessian 행렬의 모든 고유값(eigenvalue)이 양수(positive)이면 해당 지점에서 함수는 극소, 모든 고유값이 음수이면 극대, 음의 고유값과 양의 고유값을 모두 가지면 saddle point인 것으로 판단합니다 (고교수학에서 f''(x)의 부호에 따라서 아래로 볼록, 위로 볼록 여부를 구분하는 것과 같은 이치).

이러한 구분의 핵심에는 Hessian 행렬의 고유벡터(eigenvector)는 함수의 곡률이 큰 방향벡터를 나타내고 고유값(eigenvalue)은 해당 고유벡터(eigenvector) 방향으로의 함수의 곡률(curvature, 이차미분값)을 나타낸다는 점에 있습니다.

☞ Hessian 행렬은 대칭행렬(symmetric matrix)이므로 [선형대수학 #3] 고유값과 고유벡터 (eigenvalue & eigenvector) 글에서 설명한 바와 같이 항상 고유값 분해가 가능하며 서로 수직인 n개의 고유벡터를 가집니다 (단, Hessian이 대칭행렬이 되기 위해서는∂x∂y = ∂y∂x와 같이 편미분의 순서가 바뀌어도 그 결과가 동일해야 하는데 그러려면 f가 해당 지점에서 2차 미분이 가능하고 또한 2차 미분한 함수가 연속이어야 한다고 합니다: https://en.wikipedia.org/wiki/Symmetry_of_second_derivatives 참조)

참고로 이미지에서의 Hessian은 그레디언트의 경우와 마찬가지로 이미지 I(x,y)를 (x,y)에서의 픽셀의 밝기를 나타내는 함수로 보고 다음과 같이 계산할 수 있습니다.

 --- (10)

5. Laplacian(라플라시안)

어떤 다변수 함수 f(x1,x2,...,xn)가 있을 때, f의 Laplacian(라플라시안)은

 --- (11)

와 같이 각 변수로의 2차 편미분 값의 합으로 정의됩니다.

Laplacian은 여러 물리적 의미를 담고 있다고 합니다만 제가 물리에 대해서는 아는 바가 없으니 영상처리 쪽에서의 응용에 대해서만 살펴보겠습니다.

이미지에서의 Laplacian은 I(x,y)를 (x,y)에서의 픽셀의 밝기를 나타내는 함수로 보고 다음과 같이 계산할 수 있습니다.

 --- (12)

<그림 3> Laplacian (가운데)과 |gradient| (오른쪽) 비교

☞ Laplacian은 +,- 값을 갖기 때문에 0 ~ 255 사이로 스케일을 맞추어 이미지로 표시하면 <그림 3>의 가운데 그림처럼 보여집니다.

Gradient의 크기(그레디언트 벡터의 크기)와 Laplacian이 언뜻 서로 비슷해 보이지만 둘 사이에는 큰 차이가 있습니다.

--- (13)

|Gradient|는 영상의 밝기 변화가 급격할수록 큰 값을 가집니다. 하지만 Laplacian은 영상의 밝기변화의 변화가 심할수록 큰 값을 가집니다. 즉, 아무리 밝기 변화가 크더라도 그 변화속도가 일정하다면 Laplacian은 0에 가까운 값을 갖습니다.

이미지 관점에서 보면 이미지 내의 두 영역의 경계(edge)에서는 급격한 밝기 변화가 일어나기 때문에 |gradient|나 Laplacian 모두 큰 값을 나타냅니다. 하지만 동일한 영역 내부에서 점진적인 밝기 변화가 일어날 때는 그 밝기변화 정도에 따라서 |gradient|는 큰 값을 가질 수 있지만 Laplacian은 작은 값을 나타내는 차이가 있습니다.

즉, Laplacian은 영상의 밝기 변화가 평면형(planar)을 이룰 때 최소의 절대값을 가지고 극대, 극소점처럼 모든 방향으로 밝기 변화가 심할 때 최대의 절대값을 가집니다. 따라서, Laplacian은 영상에서 blob을 찾거나 코너점(corner point)를 찾는 용도로 활용될 수 있습니다.

☞ 이상으로 gradient, Hessian, Jacobian, Laplacian에 대한 글을 마무리합니다. 원래 영상 특징점 추출 방법을 정리하다 보니 gradient, Hessian, Laplacian 등의 개념이 필요하여 같이 정리하게 되었습니다. 하면 할수록 할게 많아지고.. 꼬리에 꼬리를 무는게 공부인것 같습니다..

by 다크 프로그래머