MINUIT Tutorial - Function Minimization (http://seal.web.cern.ch/seal/documents/minuit/mntutorial.pdf)

1 Introduction

1.1 The motivation

서로 다른 여러 연구 분야에서 다루어지는 문제들은 결과적으로 어떤 함수의 최소값을 찾는 것으로 정리되곤 한다. 좀 더 자세히 말하자면 1개 이상의 파라미터를 사용하는 함수에서, 가장 최소값과 그에 해당하는 파라미터 값을 찾는 문제라고 할 수 있다. 최소화(minimization)이라고 불리는 문제인 것이다.

1.2 Minimization, maximization and optimization

전통적으로 함수의 최소화라고 불리고 있기는 하지만, 연구 그룹이나 분야에 따라 어떤 사람들은 최대화(maximization)라 하기도 한다. 사실 이 두 가지는 완전히 같은 것으로 함수의 부호만 같으면 다른 하나가 되어버리기 때문이다. 나아가 요즘들어 최적화(optimization)이라고 불리는 것이 유행인 것 같기도 하다. 여기에 덧붙여 programming이나, extremization, hill-climbing 등의 용어 등이 쓰이고 있으나 이것들은 모두 같은 문제로 생각될 수 있다. 따라서 $ \chi^2 $의 최소화, 가능도(likelihood)의 최대화, 비용의 최소화, 효율의 최대화 등은 모두 최소화 문제로 바꾸어 생각하여도 무방하다.

1.3 Definition of the problem

최소화 문제에서 우리가 풀어야 할 문제는 보통, 함수 $ F(\mathbf{x}) $가 주어졌을 때 함수 $ F(\mathbf{x}) $의 값을 최소로 하는 파라미터 $ \mathbf{x} $를 찾는 것이다. 이 때 주어지는 조건은 아래와 같다.

1. $ F(\mathbf{x}) $은 수식이 어떤지, 모양새가 어떤지는 알 수 없으나 어느 한 $ \mathbf{x} $가 주어지면 그 값은 알 수 있다.
2. 파라미터 $ \mathbf{x} $는 특정 범위 내의 값으로 제한될 수 있다. 이런 경우 제한된 최소화(constrained minimizatino) 이라고 한다.
3. 때로는 함수 F에 대한 추가적인 정보를 활용할 수도 있다. 이를테면, 특정 $ \mathbf{x} $ 위치에서의 편미분 값 $ \partial F / \partial \mathbf{x} $ 같은 것이다.
4. 함수 $ F(\mathbf{x}) $ 는 $ \mathbf{x} $를 변화시키면서 반복적으로 그 값을 계산한다.

1.4 Definition of a minimum

미적분학의 관점에서 함수 $ F(\mathbf{x}) $의 최소 지점은 다음 특성을 갖는다.

1. 모든 편미분 값이 $ \partial F / \partial \mathbf{x} = 0$이거나(한 지점일 경우),
2. 어느 한 편미분 $ \partial F / \partial \mathbf{x} $이 존재하지 않거나(뾰족한 부분일 경우),
3. $ \mathbf{x} $ 가 허용된 영역의 경계에 있음(에지일 경우).

하지만 문제를 풀기에 이런 특성만 가지고는 충분하지가 않다. 따라서 문제를 조금 느슨하게 풀어보자. 모든 공간에서의 최소점(global minimum)을 찾는 것을 포기하고, 적당한 일부 공간에서의 지역적인 최소점(local minimum)을 찾는 문제로 생각해보자. 이 지역적 최소점에 대해 다시 말하자면, 어느 한 점 $ \mathbf{x}_0 $에서의 함수 값 $ F(\mathbf{x}_0) $가 그 주변의 다른 지점들의 함수 값 $ F(x) $ 보다 작은 지점이라 이야기 할 수 있다. 이제 조금 뭔가 할 수 있을 것만 같다. 지금부터 설명할 방법들은 이 지역 최소점을 찾는 방법으로 공통된 전략을 사용할 것이다. 그 전략이란, 함수 $ F $가 줄어드는 방향으로 $ \mathbf{x} $를 조금씩 변화시키다가 $ F $가 다시 커지기 시작하는 지점을 찾는 것이다. 아직 $ \mathbf{x} $를 어느 방향으로 얼마나 변화시킬 것인지에 대해서는 잘 모르겠지만, 최소값은 찾아질 것 같다.

1.5 The shape of the function - Taylor’s series

앞에서 언급했던 것과 같이 함수 $ F $를 정확히 모르지만 특정 위치에서 $F$의 값을 알 수 있다면 적당하게 떠오르는 것이 있다. 바로 Talyor series다. 이를 통해 함수를 어디로 이동시킬 것인지를 생각하여보자. $F$의 한 점 $ \mathbf{x}_1 $이 주어졌을 때의 함수 $ F$의 Taylor siries는 다음과 같다.

$$F(\mathbf{x}) = F(\mathbf{x}_1) + \mathbf{g}^T (\mathbf{x}- \mathbf{x}_1) + \frac{1}{2} (\mathbf{x} - \mathbf{x}_1)\mathbf{V}(\mathbf{x} - \mathbf{x}_1)^T + ...$$

이 때, $ \mathbf{g} $는 그래디언트 벡터 $ \mathbf{g}_i = \frac {\partial F} {\partial x_i} $이고, $ \mathbf{V} $는 $ \mathbf{V}_{ij} = \frac{\partial^2F}{\partial x_i \partial x_j} $ 를 성분으로 갖는 행렬이다.

위의 식에서 첫번째 항은 상수이기 때문에 최소점을 찾기 위해 조사할 지점을 어디로 이동시켜야 하는지에 대한 정보는 별로 가지고 있지 않다.

두번째 항은 그 지점에서 함수가 어느정도로 급격하게 낮아지고 있는지를 나타내는 그래디언트 값 $ \mathbf{g} $에 비례하게끔 값을 가지게 되나, 단순히 이 값은 그래디언트에 선형적이기만 할 뿐이므로 최저점을 예측하기 위해 얼마나 이동시켜야 하는지 알려주지 못한다.

세번째 항은 2차 식(quadratic) 모양으로 함수의 포무런 모양(parabolic)을 결정하는 역할을 한다. 이 항을 통하여 최저점을 예측할 수 있다. 두번째 항의 $ \mathbf{g} $와는 달리 $ \mathbf{V} $는 국소 영역에서 상수처럼 거의 변하지 않는다.

1.6 Non-existence of optimum in general

앞으로 여러가지 방법들을 살펴볼 것이지만, 어느 한 알고리즘이 모든 경우에서도 가장 좋다고 이야기하기는 불가능하다. 알고리즘의 성능은 보통 최소화하는 속도를 기준으로 하지만, 그 성능은 대상 함수가 어떤 것이냐 좌우되기 때문이다.