일전에 최적화 기법에 대해 정리하는 글(기계학습 - 함수 최적화 기법 정리)을 썼었는데, 지금에 와서 보니 너무 수식만 가득한 글이었던 것 같습니다. 그래서 수식보다는 좀더 직관적으로 이해할 수 있으면 좋겠다 싶어서 다시 글을 적어 봅니다.

최적화 문제하면 언뜻 수학 문제로만 보이지만 영상처리를 비롯하여 다양한 분야에서 조금만 이론적으로 깊게 들어가도 최적화 문제로 귀결되는 경우가 많습니다. 한번쯤 알아두면 어딘가에는 도움이 되리라 생각합니다 ^^

1. 최적화 문제

먼저, 최적화(optimization) 문제란 어떤 목적함수(objective function)의 함수값을 최적화(최대화 또는 최소화)시키는 파라미터(변수) 조합을 찾는 문제를 말합니다.

예를 들어 카메라 캘리브레이션에서 카메라의 파라미터(초점거리 등)를 찾는 문제, 서로 다른 시점에서 찍은 두 카메라 영상에서 3D 정보를 복원하는 문제, 비디오 영상에서 비디오를 촬영할 당시의 카메라의 궤적을 복원하는 문제, 사람에 대한 비디오 영상에서 사람의 관절의 움직임을 스켈레톤(skeleton)으로 모델링하는 문제, 고저가 있는 지형에서 목적지까지의 차량의 에너지(연료) 소모를 최소화하는 이동 경로를 찾는 문제 등이 모두 최적화 문제에 해당됩니다.

이 때, 만일 목적함수가 f(x) = 2x + 1 등과 같이 하나의 파라미터(변수)로 되어 있다면 일변수 함수에 대한 최적화 문제가 되며 f(x,y) = xy - x + 5 등과 같이 여러 개의 파라미터(변수)로 되어 있다면 다변수 함수에 대한 최적화 문제가 됩니다.

또한 목적함수가 f(x₁,x₂,...,x_m) = b + a₁x₁ + a₂x₂ + ... + a_mx_m 과 같이 모든 파라미터(변수)에 대해 일차 이하의 다항식으로 구성되면 선형 최적화(linear optimization) 문제라 하고 f(x,y) = ysinx + x, f(x,y) = x² + y, f(x,y) = xy - 1 등과 같이 그 외의 경우를 비선형 최적화(nonlinear optimization) 문제라 부릅니다.

그리고 목적함수 외에 파라미터가 만족해야 할 별도의 제약조건이 있는 경우를 constrained optimization 문제, 별도의 제약조건이 없는 경우를 unconstrained optimization 문제라 부릅니다.

어찌 되었든 최적화(optimization) 문제란 우리가 원하는 어떤 조건(함수값을 최소화 또는 최대화)을 만족시키는 최적의 파라미터(변수) 값을 찾는 문제를 말하며 여기서 다루고자 하는 최적화 문제는 별도의 제약조건이 없는 일반적인 비선형 최적화(unconstrained nonlinear optimization) 문제입니다.

최적화(optimization) 문제는 크게 최대화(maximization) 문제와 최소화(minimization) 문제로 나눌 수 있는데, 목적함수가 이윤, 점수(score) 등인 경우에는 최대화 문제, 비용(cost), 손실(loss), 에러(error) 등인 경우에는 최소화 문제로 볼 수 있습니다. 그런데, f를 최대화시키는 것은 -f를 최소화시키는 것과 동일하므로 방법론 상으로는 최대화 문제와 최소화 문제를 모두 동일하게 볼 수 있습니다. 따라서 이 글에서는 편의상 최적화 문제를 최소화(minimization) 문제로 한정하겠습니다.

2. 최적화 원리

최적화 문제를 푸는 가장 기본적인 원리는 비교적 단순합니다. 그건, 현재 위치에서 함수값이 감소(최대화 문제라면 증가)하는 방향으로 조금씩 조금씩 파라미터 값을 이동해 나가는 것입니다. 즉, 한걸음을 내딛은 후 그 위치에서 어느 방향이 가장 내리막 길인지를 봐서 그 방향으로 한 걸음을 내딛고, 또 다시 그 위치에서 가장 내리막 방향을 찾고... 하는 과정을 더 이상 내려갈 수 없는 곳(local minima)에 다다를 때까지 반복합니다. 그리고 이런 과정을 반복하다 보면 언젠가는 (비록 local minimum일수도 있겠지만) 함수값이 최소화되는 지점을 발견할 수 있을 것이라는 원리입니다.

<그림 1> 그림출처: http://blog.datumbox.com/

이 때, 가장 중요한 이슈는 어느 방향으로 내려갈 것인지와 한번에 얼마큼씩 이동할 것인지를 결정하는 것입니다. 그리고 기존의 여러 최적화 기법들(뉴턴 방법, gradient descent 방법, Levenberg-Marquardt 방법 등)이 있지만 이들의 차이는 결국 이동할 방향과 이동할 양을 어떤 방식으로 결정하느냐의 차이일 뿐입니다.

그리고, 이동할 방향과 이동할 양을 결정할 때 사용되는 가장 기본적인 수학적 원리는 일차미분(기울기)과 이차미분(곡률)의 개념입니다.

3. 일차미분을 이용한 최적화

일차미분(f')을 이용한 함수 최적화 기법의 가장 단순한 형태는 다음 수식에 따라 임의의 시작점 x₀부터 시작하여 수렴할 때까지 x를 변화시키는 것입니다.

 --- (1)

여기서 λ는 한번에 얼마나 이동할지를 조절하는 step size 파라미터로서 일단은 고정된 상수(λ>0)로 가정합니다.

즉, 일차미분을 이용한 함수 최적화는 현재 지점에서 일차미분(기울기)이 양수(f'>0)이면 x를 감소시키고, 음수(f'<0)면 x를 증가시키는 방식으로 f가 극소(minima)가 되는 지점을 찾는 것입니다.

<그림 2> 일차미분을 이용한 최적화 원리

간단한 예로, f(x) = x⁴을 최소화시키는 x를 x₀ = 2부터 시작하여 구해보겠습니다. 스텝(step) 파라미터는 λ = 0.01로 설정하고 식 (1)의 탐색과정을 200회 반복한 결과는 아래와 같습니다.

<그림 3> 일차미분을 이용한 최적화 예

위 그림에서 볼 수 있듯이 일차미분 방법을 이용하면 f가 최소화되는 방향으로 x가 정상 이동함을 확인할 수 있습니다.

그런데, 한가지 문제는 극소점 근처에서는 수렴 속도가 급격히 떨어져서 200회나 진행했음에도 불구하고 실제 극소점(x = 0) 근처에 다다르지 못했다는 점입니다. 그 이유는 극소점에 다가갈수록 f'이 0에 가까워져서 식 (1)에서 스텝의 크기도 함께 줄어들기 때문입니다.

수렴속도의 문제를 해결하기 위하여 손쉽게 생각할 수 있는 방법은 스텝(step) 파라미터 λ의 값을 증가시키는 것입니다. 아래 그림은 스텝 파라미터를 λ = 0.03 (3배 증가)로 했을 때와 λ = 0.13 (13배 증가)로 했을 때의 결과입니다.

<그림 4>

여기서 우리는 흥미로운 점 2가지를 알 수 있습니다. 스텝 파라미터를 키우면 수렴 속도가 증가하긴 하나 극소점 근처에서는 그 차이가 크지 않다는 점(λ = 0.03 예), 그렇다고 스텝 파라미터를 너무 키우면 아예 발산해 버릴 수도 있다는 점(λ = 0.13 예)입니다.

앞서 최적화 기법의 핵심은 이동할 방향과 이동할 크기를 어떻게 정하느냐의 문제라고 했습니다. 지금까지 설명한 일차미분을 이용한 최적화 기법의 가장 큰 장점은 이동하고자 하는 방향이 항상 올바른 방향을 향한다는 점입니다. 하지만 step size에 대해서는 어떠한 해결책도 제시해 주지 못합니다. Step size가 너무 작으면 수렴 속도가 느리고 또 너무 크면 수렴을 하지 못하고 발산해 버릴 수도 있습니다. 그리고 적절한 step size의 크기는 함수마다 모두 달라질 수 있습니다.

☞ 지금까지 설명한 일차미분을 이용한 최적화 기법을 Gradient Descent 방법이라 부르며 그 특성 및 장단점 또한 동일합니다.

4. 이차미분을 이용한 최적화

앞서 설명한 일차미분을 이용한 최적화 기법의 문제점을 해결하기 위한 한 방법은 일차미분(f')과 함께 이차미분(f'')을 이용하는 것입니다.

 --- (2)

앞서 f(x) = x⁴ 예에 식 (2)를 적용하면 20번의 반복(iteration)만에 다음과 같은 수렴 결과를 보여줍니다 (x₀ = 2).

<그림 5> 이차미분을 이용한 최적화 예

그림 3과 그림 5의 결과를 확인하면 그 차이는 확연합니다. 일차미분을 이용한 경우(그림 3)에는 200회나 탐색을 진행했음에도 극소점에 다다르지 못한 반면 이차미분을 함께 이용한 경우(그림 5)에는 단 20 스텝만에 극소점에 거의 수렴함을 확인할 수 있습니다. 또한 식 (2)는 스텝 파라미터 λ를 요구하지 않는다는 특징도 있습니다 (f''을 이용하여 스텝의 크기를 스스로 결정).

☞ 우리가 알고 있는 뉴턴법(Newton's method), 가우스-뉴턴법(Gauss-Newton method), LM(Levenberg-Marquardt) 방법 등이 모두 이차 미분을 이용한 최적화 기법에 해당합니다.

얼핏 보면 모든 면에서 이차미분을 이용하는 것을 훨씬 효과적인 것처럼 보입니다. 하지만 이차미분을 이용한 방법은 크게 2가지 문제점을 갖고 있습니다. 그 한가지는 변곡점(f''=0) 근처에서 매우 불안정한 이동 특성을 보인다는 점입니다. 예를 들어, f(x) = x³ - 2x + 1라 하고 x₀ = 0인 경우 f''(0) = 0이기 때문에 식(2)가 아예 정의가 안되는 문제점이 발생합니다 (그림 6a). 또한 정확히 변곡점이 아니라 하더라도 변곡점 근처에서는 f'' = 0에 가까운 값을 갖기 때문에 스텝(step)의 크기가 너무 커져서 아에 엉뚱한 곳으로 발산해 버릴 수도 있습니다 (그림 6b). 하지만 일차미분을 이용한 방법의 경우에는 나누기가 없기 때문에 이러한 문제가 발생하지 않으며 변곡점에서 출발한 경우에도 정상적으로 해를 찾을 수 있습니다 (그림 6c).

<그림 6> 이차미분을 이용한 최적화 기법의 문제점 I

이차미분을 이용한 최적화 기법의 2번째 문제점은 이동할 방향을 결정할 때 극대, 극소를 구분하지 않는다는 점입니다. 앞서 f(x) = x³ - 2x + 1의 예에서 x₀ = -0.5라 하면 이차미분을 이용한 방법은 극소점이 아닌 극대점을 향해 수렴(그림 7a)해 버리는 반면 일차미분을 이용한 경우에는 정상적으로 극소점을 향해 수렴함(그림 7b)을 확인할 수 있습니다.

<그림 7> 이차미분을 이용한 최적화 기법의 문제점 II

정리해 보면 일차미분을 이용한 방법은 항상 옳은 방향을 향하지만 스텝(step)의 크기를 정하는데 어려움이 있고 이차미분을 이용한 방법은 보다 빠르게 해를 찾을 수 있지만 변곡점(f''=0) 근처에서 문제의 소지가 있으며 극대, 극소를 구분하지 못한다는 문제점이 있습니다. 그리고 그동안 연구되어온 다양한 최적화 기법들은 결국 이러한 단점을 극복하기 위한 여러 노력의 결과로 볼 수 있습니다. 구체적인 극복 방법들을 살펴보기 전에 먼저 이차미분을 이용한 최적화 기법의 기본 원리에 대해 살펴보겠습니다.

이차미분을 이용한 최적화 기법의 기본 원리는 현재 지점에서 구한 f'' 값을 다른 모든 구간으로 확대 적용하는데 있습니다. 앞서, f(x) = x⁴의 예에서 f''(2) = 48입니다. 그런데, x = 2뿐만 아니라 다른 모든 x에서도 f''(x) = 48라고 가정하면 이러한 f는 f(x) = 24x² + bx + c 꼴의 이차함수(포물선)가 됩니다. 그리고 f(2)와 f'(2)도 현재 지점과 같게 일치를 시키면 f(x) = 24x² - 64x + 48가 됩니다. 이와 같이 현재 지점에서의 함수의 변화를 이차 포물선으로 근사시킨 후 원래의 함수가 이 근사 포물선과 같을 것이라고 가정해 버립니다. 그러면 함수의 값을 최소화시키는 지점은 포물선의 극점일 것이므로 구해진 포물선의 극점으로 x를 이동시키는 것이 식 (2)의 원리입니다 (그림 8).

<그림 8> 이차미분을 이용한 최적화 원리

☞ 사실 이차미분을 이용한 최적화는 테일러 급수(Taylor series)와 밀접한 관련이 있습니다. 임의의 함수 f(x)에 대한 x = x_k에서의 이차 테일러 근사는 f(x) = f(x_k) + f'(x_k)*(x-x_k) + f''(x_k)/2*(x-x_k)² 로 주어집니다. 그리고 이 이차 다항식의 극점(f'=0인 지점)을 구해보면 x = x_k - f'(x_k)/f''(x_k)가 나옵니다. 따라서 식 (2)는 함수를 2차 테일러 다항식으로 근사한 후 x를 근사 다항식(포물선)의 극점으로 이동시키는 수식입니다.

5. Line Search 방법

Line search 방법은 최적화 기법에서 스텝(step)의 크기를 결정하는 방법에 관한 것으로서 앞서 설명한 최적화 기법들의 문제점을 효과적으로 극복할 수 있는 해법 중 하나입니다.

예를 들어 어떤 사람이 깜깜한 밤에 후레쉬 하나만 들고 산을 내려오고 있습니다. 그런데 그 사람은 바로 발밑의 지형만을 보고 어디로 내려갈지 그리고 얼마나 내려갈지를 정합니다. 그리고는 눈을 질끈 감고 점프를 합니다. 운이 좋으면 산을 많이 내려올 수 있지만 운이 나쁘면 건너편 언덕 위로 올라가 버릴 수도 있습니다. 여기까지가 기본적인 최적화 기법의 접근 방식입니다. 그런데, 좀더 현명한 사람이라면 뛰고자 하는 방향(라인)을 따라서 미리 후레쉬를 비춰보고 실제 지형을 살펴본 후에 얼마나 점프하면 좋을지를 결정할 것입니다.

앞서 일차미분을 이용한 최적화 기법은 항상 옳은 방향을 향하지만 스텝(step)의 크기를 정하는 것이 문제라고 했습니다. 즉, 스텝의 크기가 너무 크면 발산의 위험이 있고 또한 극점 근처에서는 수렴 속도가 느려지는 문제점이 있었습니다. 또한 이차미분을 이용한 경우에도 변곡점(f'') 근처에서는 탐색이 불안정해지는 문제점이 있었습니다. 그런데, 사실 이러한 문제의 원인은 스텝의 크기를 현재 지점에서의 국소적인 변화(f' 또는 f'')만을 보고 정하는데 있습니다. Line search 방법은 이동하고자 하는 방향을 따라서 실제 함수값(f)의 변화를 미리 살펴본 후에 (함수값을 최소화하도록) 이동할 양을 결정하는 방식입니다.

Line search 방법에도 여러 가지가 있는데 직관적으로 이해할 수 있는 방법으로는 backtracking line search 방법과 golden section search 방법이 있습니다. Backtracking line search 방법은 일단 이동하고자 하는 방향을 따라서 최대한 멀리 가봅니다. 그리고 해당 지점의 함수값이 현재의 함수값에 비해서 충분히 작아졌는지 검사합니다. 만일 충분히 작지 않다면 점차적으로(보통 1/2씩) 거리를 줄여가면서 다시 함수값을 비교합니다. 그래서 충분히 작아졌다고 판단이 되면 해당 지점으로 점프를 합니다. 그리고 점프한 지점에서 다시 이동할 방향을 잡고 line search 알고리즘을 적용하는 방식입니다 (그림 9a). Golden section search(황금분할탐색) 방법은 탐색구간의 내부를 황금비율인 1:1.618로 분할해 가면서 구간 내에서 함수값이 최소가 되는 지점을 탐색한 후 해당 지점으로 점프하는 방식입니다 (그림 9b).

<그림 9> line search 방법

☞ Backtracking line search 방법에서 충분히 작아졌는지 여부는 현재 지점에서의 함수값을 f(x_k), 이동하고자 하는 지점에서의 함수값을 f(x_k + △x)라 할 때 f(x_k + △x) - f(x_k) ≤ △x*cf'(x_k)를 만족하는지 여부로 결정하며(c는 0과 1 사이의 상수) 이 조건식을 Armijo–Goldstein 조건이라고 합니다.

☞ 일차미분을 이용한 최적화 기법은 항상 옳은 방향을 향하기에 line search 방법을 일차미분 최적화 방법과 결합하면(이동할 방향은 일차미분으로, 이동할 크기는 line search로 결정) 앞서 여러가지 문제점들을 극복할 수 있는 좋은 함수 최적화 방법이 됩니다.

6. Trust Region 방법

앞서 line search 방법이 주로 일차미분을 이용한 최적화 기법의 단점을 극복하기 위한 방법이라면 trust region(신뢰 영역) 방법은 이차미분을 이용한 최적화 기법의 단점을 극복하기 위한 방법입니다.

☞ 사실 trust region 방법은 복잡한 함수의 변화를 좀더 단순한 함수로 근사(approximation)할 경우에 근사 정확도를 보장하기 위해서 사용되는 일반적인 방법이지만 여기서는 이차함수로 근사하는 경우로 한정하여 설명하겠습니다.

앞서 설명했듯이 이차미분을 이용한 최적화 기법의 핵심 원리는 모든 구간에서 함수의 이차미분(f'') 값이 상수라고 가정하고 함수의 변화를 이차함수(quadratic function)로 근사한 후 근사 함수의 극점으로 이동하는데 있습니다. 그런데, 이 가정의 가장 큰 문제점은 실제 함수는 이차함수가 아니라는데 있습니다.

Trust region 방법은 근사 함수에 대한 신뢰 영역(trust region)을 정의한 후 이동할 목적지에 대한 탐색 범위를 이 영역 내부로만 제한하는 방법을 말합니다.

<그림 10> trust region 방법

실제 구현 측면에서, 최소화시키고자 하는 함수를 f(x), 현재 위치를 x = xk, 현재의 trust region을 |x - xk| ≤ rk라 하면 먼저 식 (2) 등을 이용하여 다음으로 이동할 지점을 추정합니다. 만일 이동할 지점이 trust region을 벗어날 경우에는 스텝의 크기를 줄여서 trust region를 벗어나지 않도록 (trust region의 경계와 만나는 지점으로) 위치를 수정합니다. 이와 같이 결정된 지점으로 이동한 후 다시 trust region 방식의 탐색을 반복하는 구조입니다. 이 때, trust region의 크기는 매 반복마다 조정될 수 있으며 근사 2차함수가 현재의 trust region 내에서 원래 함수를 얼마나 잘 근사하는지에 따라서 조정됩니다. 통상적으로 근사오차가 허용치 이하일 경우에는 trust region의 크기를 키우고 허용치 이상일 때에는 trust region의 크기를 줄이는 방법이 사용됩니다.

☞ Trust region의 크기를 조절할 때, 현재의 trust region 내의 모든 지점에서 근사 오차를 확인하는 것은 비효율적입니다. 따라서, 다음으로 이동할 지점에 대해서만 근사오차를 계산하여 trust region의 크기를 조정합니다. 그리고 필요하다면 trust region의 크기 조정에 따라 이동 지점도 같이 수정합니다.

☞ 비선형 최소자승(nonlinear least squares) 문제에 대한 최적화 기법으로 잘 알려진 Levenberg-Marquardt 방법도 기본적으로는 trust region 방법에 속합니다.

7. Damping & Saddle-free 방법

마지막으로 damping 방법은 앞서의 line search 방법, trust region 방법처럼 수렴의 안정성을 보장해주기 위한 방법입니다 (공식적인 용어는 아닙니다). 원래 damping 방법은 비선형 최소자승 문제(nonlinear least squares problem)에서의 대표적인 최적화 기법인 Levenberg-Marquardt 방법에서 사용된 기법을 일컫는 말입니다. 하지만 그 핵심 원리는 최소자승 문제뿐만 아니라 일반적인 최적화 문제에도 동일하게 적용될 수 있다고 생각합니다.

식 (2)의 이차미분을 이용한 최적화 방법에 damping 기법을 적용하면 아래와 같이 식을 보완할 수 있습니다.

 --- (3)

이 때, 식 (3)에서 상수 μ_k(μ_k>0)가 damping factor이며 영어로는 '제동하는', '진폭을 억제하는' 이라는 의미를 갖습니다. 즉, damping 방법은 변곡점(f''=0) 근처에서 발산하려고 하는 원래의 시스템에 제동(억제)을 가함으로써 모든 경우에 부드럽게 동작하도록 만든 것입니다.

식 (3)에서 μ_k가 큰 경우에는 상대적으로 f''의 영향이 작아지기 때문에 일차미분을 이용한 최적화 기법과 유사해지고, 반대로 μ_k가 작은 경우에는 이차미분을 이용한 최적화 기법과 유사한 특성을 가집니다.

식 (3)에서 또 하나 눈여겨 볼 점은 f''에 절대값이 붙은 점입니다. 원래 식 (2)로 주어지는 이차미분을 이용한 최적화 기법의 문제점 중의 하나는 극대, 극소를 구분하지 못한다는 점입니다. 하지만 식 (3)과 같이 f''에 절대값을 씌우면 일차미분(f')의 부호에 의해서만 탐색 방향이 결정되기 때문에 항상 함수값을 최소화시키는 방향으로만 탐색을 진행하게 됩니다.

서두에 언급했지만 식 (3)은 잘 알려져 있거나 또는 일반 문헌 등에 소개되어 있는 식은 아닙니다. 하지만 식 (3)을 사용하면 수렴 속도가 빠르다는 이차 미분의 장점을 유지하면서도 변곡점 근처에서의 불안정성과 극대, 극소를 구분하지 못하는 두 가지 문제를 모두 해결할 수 있습니다.

☞ Damping 방법은 일종의 trust region 방법으로 볼 수 있는데, 그 이유는 μ_k가 일종의 trust region의 크기를 결정하는 역할을 하기 때문입니다(μ_k가 클수록 trust region의 크기가 작아지고 μ_k가 작을수록 trust region의 크기가 커짐). 앞서 trust region 방법에서와 마찬가지로 μ_k의 값은 매 최적화 스텝(step)마다 조절할 수 있습니다. 가장 간단한 방법은 이동할 지점의 함수값이 현재의 함수값에 비해 충분히 작은지를 검사하여 만일 그렇지 않은 경우에는 μ_k를 증가시키고(예를 들어 2배씩) 충분히 작은 경우에는 다시 μ_k를 감소시키는(예를 들어 1/3씩, 또는 기본값으로 되돌리는) 방법입니다.

☞ 서두에서 '생각합니다'라는 표현을 사용한 이유는 식 (3)의 방법이 기존에 나와 있는 일반적인 방법이 아니기 때문입니다(물론 이미 발표되어 있는데 제가 아직 모르고 있을 수도 있습니다). 식 (3)은 Levenberg-Marquardt 방법에서 사용된 damping 기법이 일반적인 최적화 기법에도 적용될 것 같아서 식을 세워 본 것입니다. 그리고 참고로 f''에 절대값을 씌우는 것은 작년(2014년) Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization 논문에 발표된 아이디어로서 논문에서는 Saddle-free 방법이라는 명칭을 사용하였습니다.

8. 다변수 함수에서의 최적화

지금까지 설명한 최적화 원리 및 기법들은 모두 일변수 함수를 예로 들었지만 다변수 함수의 경우에도 그대로 확장 적용될 수 있으며 그 특성 및 장단점도 모두 동일합니다.

앞서 최적화 기법들을 다변수 함수로 확장 적용하기 위해서는 미분을 어떻게 구하느냐가 관건인데, 다변수 함수에서의 일차 미분은 그레디언트(gradient), 이차 미분은 헤시안(Hessian)이 됩니다. 그리고 그레디언트와 헤시안의 계산을 위해서는 편미분(partial differentiation)이 필요합니다.

먼저, 다변수 함수란 f(x₁, x₂, x₃) = x₁² + x₂x₃ 등과 같이 두개 이상의 변수에 의하여 함수값이 결정되는 함수를 말합니다. 이 때, 함수 f(x₁, x₂, x₃)가 점 p(p₁, p₂, p₃)에서 어떤 변화 특성을 갖는지 분석할 때, x₁만 변수로 놓고 나머지는 상수로 놓은 함수 f(x₁, p₂, p₃)를 생각해 보면 x₁ 값이 변할 때 f의 값이 어떤 변화를 갖는지 분석할 수 있을 것입니다. 마찬가지 방식으로 x₂, x₃에 대해서도 각각의 방향으로의 함수값 변화 특성을 분석할 수 있습니다. 이와 같이 어느 한 변수의 방향축에 대해서만 변화율을 구한 것을 편미분(partial derivative)이라 부르고 f의 x에 대한 편미분을 ∂f/∂x로 표기합니다(위 예에서 ∂f/∂x₁ = 2x₁, ∂f/∂x₂ = x₃, ∂f/∂x₃ = x₂). 그리고 다변수 함수 f(x₁, x₂, ..., x_n)에 대한 일차 미분은 다음과 같이 각 변수에 대한 일차 편미분으로 정의되며 이를 그레디언트(gradient)라 부릅니다.

 --- (4)

또한 다변수 함수의 이차 미분은 아래와 같은 헤시안(Hessian) 행렬로 정의됩니다.

 --- (5)

☞ 참고로, 자코비언(Jacobian)은 다변수 벡터 함수에 대한 일차 미분입니다. 다변수 벡터 함수란 F(x₁, ..., x_n) = (f₁(x₁, ..., x_n), ..., f_m(x₁, ..., x_n))과 같이 함수값이 벡터 형태로 나오는 함수를 말합니다. 이에 반해 함수값이 하나의 실수값(real value)으로 나오는 일반적인 다변수 함수는 다변수 스칼라(scalar) 함수라고 부릅니다. 그리고 다변수 벡터 함수에 대한 이차 미분은 따로 정의되지 않습니다.

이제 식 (1)의 일차 미분을 이용한 최적화 기법을 다변수 함수로 확장하면 잘 알려진 gradient descent 방법의 식이 됩니다 (단, x = (x₁, x₂, ..., x_n)).

 --- (6)

그리고 식 (2)의 2차 미분을 이용한 최적화 기법을 다변수 함수로 확장하면 일반적인 Newton 방법 식이 됩니다.

 --- (7)

또한 식 (3)의 damping 방법을 다변수 함수로 확장하면 아래와 같이 식을 세울 수 있습니다.

 --- (8)

단, |H|는 H를 고유값 분해한 후 고유값의 부호를 모두 +로 변경하여 얻은 행렬, I는 항등행렬을 나타냅니다.

☞ 앞서 설명한 바와 같이 식 (3)의 damping 방법은 일반적인 방법이 아니기 때문에 식 (8) 또한 기존의 알려진 방법이 아님을 참고하시기 바랍니다.

9. 비선형 최소자승 문제(nonlinear least squares problem)

마지막으로 비선형 최소자승 문제에 대한 최적화 기법에 대해 간략히 살펴보고 글을 마무리하고자 합니다. 지금까지 설명한 최적화 기법들은 임의의 함수에 적용 가능한 일반적인 최적화 방법들이었습니다. 하지만 목적함수(objective function)가 모델과 데이터 사이의 에러(error) 제곱합 형태로 주어지는 f(x) = Σe_i(x)² 형태의 최소자승(least squares) 문제에 대해서는 별도의 특화된 최적화 기법들을 존재합니다. 그리고 이러한 방법에는 가우스-뉴턴법(Gauss-Newton method), Levenberg-Marquardt 방법 등이 있습니다. 가우스-뉴턴법은 식 (7)과 유사한 형태이고 Levenberg-Marquardt 방법은 식 (8)과 유사한 형태입니다. 특성 및 장단점도 거의 동일합니다. 하지만 이들은 최소자승 문제의 최적화에만 적용할 수 있고, 일반적인 최적화 문제에는 적용할 수 없는 방법임에 유의하기 바랍니다. 하지만 우리가 풀고자 하는 대부분의 최적화 문제들이 최소자승 문제에 해당하기 때문에 이들에 대해서도 잘 알아둘 필요가 있습니다. 최소자승 문제에 대한 보다 자세한 내용에 대해서는 [기계학습] - 함수최적화 기법 정리 (Levenberg–Marquardt 방법 등) 글을 참고하시기 바랍니다.

10. Quasi-Newton 방법 (2015.6.20 추가된 내용)

앞서 설명한 최적화 기법들 중 일차미분의 gradient descent 방법은 수렴속도 면에서 효율성이 많이 떨어지기 때문에 실제 문제에서는 가급적 이차미분을 이용한 Newton 방법(trust region 또는 line search와 결합된)을 사용하는 것이 좋습니다. 그런데, Newton 방법을 적용하기 위해서는 Hessian 행렬을 계산하는 것이 가장 큰 문제입니다. Hessian 행렬을 계산하기 위해서는 목적함수에 대한 이차 도함수를 일일히 계산해야 하는데, 목적함수가 조금만 복잡해져도 이차 편미분을 종이 위에 직접 손으로 푸는 것을 거의 불가능하다고 볼 수 있습니다. 이러한 어려움으로 인해 이차 도함수를 직접 계산하는 대신에 근처의 함수값을 이용하여 근사적으로 계산하는 방법들이 실질적으로는 많이 사용되고 있습니다. 예를 들어, f(x) = x²의 x = 2에서의 일차미분값은 정확히 계산하면 f'(2) = 2*2 = 4이지만, 이를 근사적으로 계산하면 굉징히 작은 양의 상수 h(예를 들어, 0.0001)에 대해 f'(2) ≒ (f(2+h) - f(2-h))/(2*h) = (f(2.0001) - f(1.9999)) / 0.0002 = 4와 같이 미분을 하지 않고도 함수값만을 이용하여 근사할 수 있습니다. 또한 이차미분의 경우도 유사한 방식으로 근사적 계산이 가능합니다. 이와 같이 Newton 방법에서 Hessian의 계산을 근처 함수값을 이용하여 근사적으로 numeric하게 계산하여 사용하는 최적화 기법들을 Quasi-Newton (쿼지-뉴턴) 방법이라고 부릅니다. Hessian을 구체적으로 어떻게 근사하느냐에 따라서 여러 Quasi-Newton 방법들이 있으며 그중 가장 대표적으로 사용되는 방법이 BFGS(Broyden–Fletcher–Goldfarb–Shanno) 방법입니다. 구체적인 수식 등 보다 자세한 내용에 대해서는 위키피디아 등을 참고하시기 바랍니다.

11. 맺음말

근 3주에 걸쳐 짬짬히 썼던 글을 이제 슬슬 마무리할 때가 된 것 같습니다. 보통 최적화 관련 이론서나 위키피디아 설명 등을 보면 그 엄청난 수식과 이론들에 먼저 눈앞이 깜깜해짐을 느낍니다. 저도 그랬고 대부분 그럴 것이라고 생각합니다. 하지만 그 복잡한 수식들을 걷어내고 나면 그 이면에는 이들이 매우 단순한 원리에 의해 움직이고 있음을 알수 있습니다. 부족하나마 이 글이 현상의 이면을 볼 수 있는 작은 실마리가 될 수 있길 기대합니다.

by 다크 프로그래머

작년(2014년)에 local minima 문제에 대한 흥미로운 논문이 하나 발표되었다. 정식으로 출판된 논문은 아니고 arXiv(아카이브)에만 등록된 논문이다. => NIPS 2014에서 발표된 논문이라고 합니다.

[Dauphin14] Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, Y. Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.

Local minima 문제는 에러를 최소화시키는 최적의 파라미터를 찾는 문제에 있어서 아래 그림처럼 파라미터 공간에 수많은 지역적인 홀(hole)들이 존재하여 이러한 local minima에 빠질 경우 전역적인 해(global minimum)를 찾기 힘들게 되는 문제를 일컫는다.

<그림 1> local minima 문제

그리고 기존에 기계학습(machine learning)이 잘 안되거나 성능이 잘 안나오는 이유는 학습 도중 이러한 local minima에 빠졌기 때문이라는 게 일반적인 상식이었다.

하지만 이 논문은 기존의 상식을 깨고 local minima 문제가 사실은 고차원(high dimensional)의 공간에서는 발생하기 힘든 매우 희귀한 경우라고 주장한다.

그 이유는 예를 들어, local minimum이 형성되기 위해서는 함수의 변화 그래프가 모든 축의 방향으로 밥그릇처럼 오목한 형태가 되어야 하지만 아래 그림의 p처럼 어느 한 방향이라도 아래로 흘러내리면 local minima가 형성되지 않기 때문이다. 그리고 고차원의 공간에서 모든 축의 방향으로 오목한 형태가 형성될 확률은 거의 0에 가깝다는게 주장의 요지이다.

<그림 2> 그림출처: [Dauphin14]

함수 최적화 문제를 풀때 일차적으로는 미분값이 0인 즉, f' = 0인 지점을 찾는 것이 일반적이다. 그리고 일차 미분이 0인 지점을 critical point라 부른다. 어떤 critical point가 local minima가 되기 위해서는 모든 축의 방향으로 함수 그래프가 아래로 볼록(f''>0)이 되어야만 한다. 즉, n차원의 다변수 함수 f(x1, x2, ..., xn)이 있을 때 다음의 조건을 만족해야 한다.

 --- (1)

Critical point에서 모든 축 방향으로 곡률(이차미분)이 양수인 경우는 위로 볼록, 아래로 볼록이 랜덤하게 발생한다고 가정하면 차원이 증가할수록 확률적으로 매우 힘든 일이므로(1/2ⁿ) 대부분의 critical point는 local minima가 아니라는 것이다.

처음 이 내용을 접했을 때 꽤나 신선하고 재미있는 주장이라고 생각했다. 그러면서 정말 그럴까? 그렇다면 고차원의 최적화 문제에 대해서는 이제 더이상 local minima 문제를 걱정하지 않아도 되는 것일까? 하는 의구심도 들었다.

먼저, [Dauphin14] 논문의 내용을 그대로 옮겨보면 다음과 같다.

즉, 고차원의 공간에서 발생하는 critical point(일차 미분이 0인 지점)는 거의 대부분 saddle point이며 만일 saddle point가 아닌 경우는 global minimum이거나 또는 global minimum과 유사한 수준의 local minima라는 것이다.

잘 보면 이 내용에는 2가지 주장이 함께 섞여 있다. 하나는 고차원의 공간에서 대부분의 critical point는 local minima가 아니라 saddle point라는 점이다. 그리고 다른 한가지는 고차원의 공간에서 설령 local minima가 발생한다 하더라도 이는 global minimum이거나 또는 global minimum과 거의 유사한 수준의 에러 값을 갖는다는 것이다.

먼저 첫번째 주장은 비교적 직관적으로 쉽게 수긍할 수 있다. Critical point란 모든 축의 방향으로 일차 미분값이 0인 지점(f' = 0)으로서 다른 말로 stationary point라고도 한다. 그리고 이러한 critical point에는 크게 극대점(maxima), 극소점(minima), 그리고 saddle point가 있는데 saddle point란 극대 또는 극소가 아닌 모든 critical point로 정의된다. 따라서, 고차원의 공간에서 critical point는 대부분 확률적으로 saddle point인 것으로 볼 수 있다.

그런데 두 번째 주장 즉, 고차원의 공간에서 발생하는 local minima는 global minimum이거나 또는 global minimum과 거의 유사한 수준의 에러 값을 갖는다는 점에 대해서는 쉽게 수긍이 가지 않는다.

논문에서는 그 근거로서 실험적으로 critical point들에서 에러를 측정해 보니 critical point에 포함된 위로 볼록인 방향축의 비율이 크면 클수록 높은 에러를 가진다는 실험 결과를 예로 든다. 그리고 local minim는 위로 볼록인 경우가 하나도 없는 경우이기 때문에 결과적으로 매우 낮은 에러를 갖게 될 것이라는 게 이들의 주장이다.

하지만 차원이 증가할수록 만일 critical point 자체의 수도 같이 증가한다면 여전히 local minima도 다수 존재하게 되는 것은 아닐까 하는 의문이 든다. 그리고 고차원의 세계에서는 그만큼 어떤 예측하기 힘든 다양성들이 존재할텐데 global minimum 하나밖에 존재하지 않는다는 것은 그 자체로 상상하기 힘든 측면이 있다.

그리고 두 번째 주장에 대해서는 하나의 실험적 사례 외에는 별다른 논리적 근거가 제시되어 있지 않다. 그리고 그 실험적 사례 또한 local minima가 global minimum에 근접할 것이라는 직접적인 증거는 되지 못한다고 생각한다. 그건 하나의 실험 예에서 높은 에러를 가진 local minima를 발견하지 못했다고 해서 다른 문제에서도 나타나지 않을 것이라고 일반화하긴 힘들다고 생각하기 때문이다.

하지만 아직은 이들의 주장이 명확하게 증명되거나 반증된 것이 아니기 때문에 어떤 것이 사실인지는 알지 못한다.

☞ 이 글에서는 local minima의 존재 여부에만 초점을 맞추었지만 사실 [Dauphin14] 논문의 초점은 조금 다른데 있습니다. 이 논문의 핵심은 "Critical point 근처에서는 함수의 수렴속도가 느려지기 때문에 기존의 기계학습이나 최적화 기법에서 변화가 거의 없이 정체가 되는 현상이 발생하였는데 이를 기존에는 local minima 문제라고 착각하였다. 하지만 사실은 이들이 local minima가 아니라 실제로는 대부분 saddle point들이며 기존 기계학습 방법 또는 최적화 기법들이 잘 동작하지 않았던 이유는 기존 탐색 방법이 saddle point에서 벗어나지 못하는 문제가 있었기 때문이다. 그리고 우리는 이러한 saddle point 문제를 극복할 수 있는 새로운 탐색 방법을 제시한다"입니다. 이 논문에서 제시한 새로운 탐색 방법도 꽤 유용해 보이며 한번쯤 읽어볼 만한 좋은 논문으로 생각됩니다.

by 다크 프로그래머

얼마전 한 친구가 KDE라는 용어를 사용하기에 KDE가 뭐냐고 물어보니 Kernel Density Estimation이라 한다.

순간, Kernel Density Estimation이 뭐지? 하는 의구심이 생겨서 그 친구에게 물어보니 자기도 잘 모른단다. 그러면 공부를 해서 나한테도 좀 알려달라고 부탁을 했다.

얼마 후, 그 친구는 Kernel Density Estimation이란 히스토그램(histogram) 등을 smoothing(스무딩)하는 것을 말하는데 Parzen–Rosenblatt window 방법과 같은 말이라면서 Parzen window 방법의 과정에 대해 열심히 설명한다.

...

무슨 말인지.. Kernel Density Estimation(커널 밀도 추정)이 뭐냐고 물어봤는데 정작 KDE 자체(개념)에 대한 설명은 안해주고 자꾸 주변적인 알고리즘에 대한 얘기만 한다. 마치 집이 뭐냐고 물어봤는데 집이란 철골을 쌓은 다음에 콘크리트를 바른 것이다라고 설명하는 것과 같다.

안되겠다 싶어서, 질문을 바꾸어 밀도추정(density estimation)이 뭐냐고 물어보았다. 그리고 좀더 나아가서 밀도(density)가 무엇인지 커널(kernel)이 무엇인지 물어보았다. 그랬더니 이 친구가 대답을 못한다...

Kernel Density Estimation(KDE)이란 커널함수(kernel function)를 이용한 밀도추정 방법의 하나로서 KDE를 알기 위해서는 먼저 밀도추정(density estimation)이 무엇인지 알아야 한다.

밀도추정 (Density Estimation)

데이터는 어떤 변수가 가질 수 있는 다양한 가능성 중의 하나가 현실 세계에 구체화된 값이다. 그리고 우리는 이렇게 관측된 데이터들을 통해 그 변수(random variable)가 가지고 있는 본질적인 특성을 파악하고자 노력한다.

그러나 하나의 데이터는 변수의 일면에 불과하기 때문에 변수의 진면목을 파악하기 위해서는 많은 수의 데이터가 필요하다. 그리고 이렇게 얻어진(관측된) 데이터들의 분포로부터 원래 변수의 (확률) 분포 특성을 추정하고자 하는 것이 density estimation(밀도추정)이다.

예를 들어, 어떤 육교 밑을 통과하는 차량의 일일 교통량을 파악하는게 목적이라고 하자. 이 때의 변수(random variable)는 '일일 교통량'이다. 그리고 실제 육교 위에서 매일 매일 관찰한 값이 데이터이다. 어떤 날은 차가 500대 지나가고, 어떤 날은 300대, 450대, ... 매일 매일 서로 다른 데이터가 나올 수 있다. 하루, 이틀의 관측 결과만 가지고 이 육교의 '일일 교통량'이 무어라고 결론을 내리기는 힘들다. 하지만 이러한 데이터가 한달, 두달, 1년 넘게 쌓이게 되면 우리는 '일일 교통량'이란 변수가 어떤 값의 분포 특성을 갖는지 좀더 정확히 파악할 수 있게 된다. 그리고 어떤 변수가 가질 수 있는 값 및 그 값을 가질 가능성의 정도를 추정하는 것이 density estimation이다.

밀도(density)는 수학적으로는 mass/volume으로 정의되지만, 밀도추정(density estimation), 기계학습, 확률, 통계 등에서 말하는 밀도(density)는 확률밀도(probability density)를 의미한다 (확률밀도에서 확률을 생략하고 흔히 밀도라고 표현).

즉, 어떤 변수 x의 밀도(density)를 추정하는 것은 x의 확률밀도함수(pdf, probability density function)를 추정하는 것과 동일한 말이다. 어떤 변수 x의 확률밀도함수 f(x)가 아래 그림과 같다고 하자.

<그림 1>

이 때, f(a)는 x = a에서의 확률밀도(probability density) 즉, 변수 x가 a라는 값을 가질 상대적인 가능성(relative likelihood)을 나타낸다.

☞ 밀도(density)와 확률(probability)을 구분해 보면 위 그림에서 x = a일 확률은 0이지만 x = a에서의 density(밀도)는 f(a)로 0이 아니다. 그리고 x가 a, b 사이의 값을 가질 확률(probability)은 그 구간에서의 확률밀도함수의 적분값(면적)으로 계산된다. 즉, density(밀도)는 확률밀도함수의 함수값이며 density를 일정 구간에 대해 적분하면 확률이 나온다.

 --- (1)

어쨌든, 어떤 변수의 확률밀도함수(pdf)를 구할 수 있으면 그 변수가 가질 수 있는 값의 범위 및 확률분포, 특성을 모두 알수 있기 때문에 밀도추정(density estimation)은 확률, 통계, 기계학습, 파라미터 추정 등에서 가장 핵심적인 요소중의 하나이다.

Parametric vs. Non-parametric 밀도추정

밀도추정(density estimation) 방법은 크게 parametric 방법과 non-parametric 방법으로 구분할 수 있다.

Parametric 밀도추정은 미리 pdf(probability density function)에 대한 모델을 정해놓고 데이터들로부터 모델의 파라미터만 추정하는 방식이다. 예를 들어, '일일 교통량'이 정규분포를 따른다고 가정해 버리면 관측된 데이터들로부터 평균과 분산만 구하면 되기 때문에 밀도추정 문제가 비교적 간단한 문제가 되어 버린다.

그런데 현실 문제에서 이렇게 모델이 미리 주어지는 경우는 많지 않으며 분포의 모델을 미리 안다는 것은 너무나 강한 혹은 사치스러운 가정일 수 있다. 이 경우 어떠한 사전 정보나 지식 없이 순수하게 관측된 데이터만으로 확률밀도함수를 추정해야 하는데 이를 non-parametric density estimation라 부른다.

Non-parametric 밀도추정의 가장 간단한 형태가 바로 히스토그램(histogram)이다. 즉, 관측된 데이터들로부터 히스토그램을 구한 후 구해진 히스토그램을 정규화하여 확률밀도함수로 사용하는 것이다.

<그림 2> 히스토그램 밀도추정 (출처: 위키피디아)

Kernel Density Estimation (커널 밀도 추정)

앞서 non-parametric 밀도추정의 가장 단순한 형태가 히스토그램(histogram) 방법이라고 했는데, 히스토그램 방법은 bin의 경계에서 불연속성이 나타난다는 점, bin의 크기 및 시작 위치에 따라서 히스토그램이 달라진다는 점, 고차원(high dimension) 데이터에는 메모리 문제 등으로 사용하기 힘들다는 점 등의 문제점을 갖는다.

Kernel Density Estimation (커널 밀도 추정) 방법은 non-parametric 밀도추정 방법 중 하나로서 커널함수(kernel function)를 이용하여 히스토그램 방법의 문제점을 개선한 방법이다.

먼저, 커널함수(kernel function)에 대한 이해가 필요한데 수학적으로 커널함수는 원점을 중심으로 좌우 대칭이면서 적분값이 1인 non-negative 함수로 정의되며 가우시언(Gaussian), Epanechnikov, uniform 함수 등이 대표적인 커널 함수들이다.

 --- (2)

--- (3)

<그림 3> 다양한 커널 함수들 (출처: 위키피디아)

다시 KDE(Kernel Density Estimation, 커널 밀도 추정)로 돌아가서 x를 변수(random variable), x1, x2, ..., xn을 관측된 샘플 데이터, K를 커널 함수라 하자. 이 때 KDE에서는 랜덤 변수 x에 대한 pdf(확률밀도함수)를 다음과 같이 추정한다.

 --- (4)

식 (4)에서 h는 커널(kernel) 함수의 bandwidth 파라미터로서 커널이 뽀족한 형태(h가 작은 값)인지 완만한 형태(h가 큰 값)인지를 조절하는 파라미터이다. 수식적으로 보면 어렵지만 이를 직관적으로 이해하면 다음과 같다.

1. 관측된 데이터 각각마다 해당 데이터 값을 중심으로 하는 커널 함수를 생성한다: K(x-xi)

2. 이렇게 만들어진 커널 함수들을 모두 더한 후 전체 데이터 개수로 나눈다.

<그림 4> "Comparison of 1D histogram and KDE" by Drleft

히스토그램을 이용한 밀도추정 방법과 KDE 방법을 비교해 보면, 히스토그램 방법은 이산적(discrete)으로 각 데이터에 대응되는 bin의 값을 증가시킴으로써 불연속성이 발생하는 반면 KDE(커널밀도추정) 방법은 각 데이터를 커널 함수로 대치하여 더함으로써 그림 4 오른쪽 그래프와 같이 smooth한 확률밀도함수(pdf)를 얻을 수 있는 장점을 갖는다.

즉, KDE(Kernel Density Estimation)를 통해 얻은 확률밀도함수는 히스토그램 확률밀도함수를 스무딩(smoothing)한 것으로도 볼 수 있으며 이 때, 스무딩(smoothing) 정도는 아래 그림처럼 어떤 bandwidth 값의 커널 함수를 사용했으냐에 따라 달라진다.

<그림 5> Kernel density estimate (KDE) with different bandwidths of a random sample of 100 points from a standard normal distribution. Grey: true density (standard normal). Red: KDE with h=0.05. Black: KDE with h=0.337. Green: KDE with h=2 (출처: 위키피디아)

실제 KDE를 사용할 때, 중요한 이슈는 어떤 커널 함수를 사용할지와 커널 함수의 bandwidth 파라미터인 h 값을 어떻게 잡을지이다. 위키피디아에 의하면 가장 최적의 커널함수는 Epanechnikov 커널이며 계산의 편의상 Gaussian 커널함수도 많이 사용된다고 한다. 그리고 Gaussian 커널함수를 사용할 경우 최적의 bandwidth 파라미터 값은 다음과 같다고 한다.

 --- (5)

단, n은 샘플 데이터의 개수, σ는 샘플 데이터의 표준편차.

by 다크 프로그래머