MINUIT Tutorial – Function Minimization (2)
MINUIT Tutorial - Function Minimization (http://seal.web.cern.ch/seal/documents/minuit/mntutorial.pdf)
2 One-dimensional minimization
2.1 Usefulness in n-dimensional problems
먼저 파라미터가 1개인 1차원 함수를 예로 시작해보자. 아주 간단한 상황이긴 하지만, 여기서 언급된 내용들이 앞으로 여러 파라미터의 함수에서 작동하는 알고리즘에도 필요한 내용이니 다뤄보고자 한다.
2.2 Grid search
가장 기초적인 최소점 탐색 방법을 생각해보면 이것이 먼저 떠오를 것이다. 최소지점 x가 존재할만한 구간 내에서 동일한 간격을 갖는 k개 지점을 정한 다음, 이 지점들을 모두 조사해보는 것이다. 각 조사지점간의 간격이 $ \Delta x $라면, 이렇게 찾은 최저점은 실제 최저점과의 차이가 $ \Delta x /2$ 이내의 위치한다.
모든 구간을 다 보는 이 방법은 확실한 방법이긴 하지만, 보통의 경우 x는 거의 무한대로 넓은 공간내에서 찾아야 하며, 설령 적당한 범위가 정해졌다고 하더라도 구간 내에서 함수의 값을 너무도 많이 조사하여야 하는 단점이 존재한다. 그럼에도 이 방법은 아주 단순하고 확실한 방법이다. 적당한 조건이 주어진다면 항상 최소점을 찾을 수 있다.
2.3 Fibonacci and golden section searches
앞의 Grid search를 향상시켜보자. 함수의 값을 계산하는 수를 줄인다면 속도를 빠르게 할 수 있을 것이다. 일정 간격의 모든 지점을 전부 계산하는 것보다, 매 단계마다 적당한 비율 t로 간격을 줄여보도록 하자.
문서의 그림 1과 함께 보도록 하자. 최소점이 존재할 영역 내의 두 지점에 대한 함수의 값이 $ F(x_1) \lt F(x_2) $ 이라고 한다면, 우리가 찾는 최소점은 적어도 $ 0 \lt x \lt x_2 $ 구간 내의 어딘가에 존재한다고 생각할 수 있다. 이를 바탕으로 비율 t 만큼 구간을 줄여 새롭게 정의하도록 한다. 이미 우리는 $ x_2 $ 지점의 값을 알고 있으므로, $ x_2 $ 는 그대로 두고 반대편 구간의 끝이었던 0 위치를 미리 설정한 비율 t만큼 이동시켜 $ x_3 $만을 새로 조사해봄으로써 새로운 구간을 설정할 수 있다. 이제 새롭게 설정된 구간은 $ x_3 \lt x \lt x_2 $ 이 된다. 조사한 $ F(x_3) $의 결과에 따라 그대로 두어야 할 지점과 이동해야할 지점을 다르게 하며 구간이 충분히 작아질 때 까지 반복적으로 구간을 줄여나간다.
동일한 비율 t로 구간을 줄여나가기 때문에 이를 정리하면 $ t^2 = 1 - t $와 같은 수식으로 나타내어진다. 즉 이는 황금비의 식으로 golden section search로 불려지는 이유이기도 하다.
탐색하는 구간에 따라 몇번 반복할 것인지가 미리 정해진 상태라면, fibonacci search를 이용할 수도 있다.
2.4 Quadratic interpolation and extapolation
함수가 거의 2차 식에 가까운 모양이라고 생각된다면, 앞의 Taylor series로부터 quadratic interpolation을 적용해볼 수 있다. 함수의 세 지점에 대한 값 $ F_1 $, $ F_2 $, $ F_3 $을 알고 있다면 이것으로부터 곡선을 정의할 수가 있다. 이 곡선의 최소지점은 $ x_4 $는 아래와 같이 계산할 수 있다.
$$x_4 = \frac{\frac{(x_2 + x_3) F_1} { (x_1 - x_2) (x_1 - x_3)} + \frac{(x_1 + x_3) F_2}{(x_2 - x_1) (x_2 - x_3)} + \frac{(x_1 + x_2) F_3}{(x_3 - x_1) (x_3 - x_2)}} {2 \frac{F_1} { (x_1 + x_2) (x_1 - x_3)} + \frac{F_2}{(x_2 + x_1) (x_2 - x_3)} + \frac{F_3}{(x_3 + x_1) (x_3 - x_2)}}$$
그리고, 세 지점이 간격이 d로 같은 경우 이 식은,
$$x_4 = x_2 + \frac{d}{2} \frac{(F_1 - F_2)}{(F_1 + F_3 - 2F_2)}$$
로 간단히 정리된다.
새로운 지점이 계산되면, 그 지점에서의 실제 함수 값 $ F(x_4) $를 계산해보고, 다음 interpolation을 위한 세개의 점을 $ x_4 $를 포함하도록 갱신하여 계산을 방법한다. 이러한 과정을 원하는 최소값에 근접할 때까지 반복한다.
하지만, 이 방법은 다음과 같은 이유로 불안정하다.
- 3개의 점의 간격에 따라서 어떤 경우 parabola는 최소점이 아닌 최대점을 가리키기도 한다.
- 3개의 점이 거의 직선에 가깝게 되면 다음 지점의 위치가 직전 위치보다 매우 멀어진 지점을 기리킬 수 있다.
- 매 단계마다 이전에 사용되었던 3개의 지점 중 2개를 선택하여 다음 게산에 다시 이용하지만 이것이 문제점을 일으킬 수도 있다.
- 위의 3개의 문제를 제외하더라도, 새로운 지점이 최저점 주변에서 멤돌 수도 있다.
이러한 문제점들은 매 반복마다 검사하는 과정을 거침으로써 어느정도 완화될 수 있다.
2.5 The success-failure method
Grid search 방법과 quadratic interpolation 방법을 잘 합쳐서 만든 success-failure 방법도 있다.
시작 지점 $ x_0 $에서 d 만큼 떨어진 지점의 값을 조사하였을 때, $ F(x_0 + d) \lt F(x_0) $ 이라면 success, 반대의 경우 failure 상태라고 정의하여보자. 만약 failure 상태라면 $ d = -\beta d $ 로 갱신하고 조사를 반복한다. success 상태라면 $ x_0 $ 위치를 $ x_0 + d $ 로 바꾸고, $ d = \alpha d $ 로 갱신한 뒤 단계를 반복한다. 이러한 과정을 반복한다고 생각하였을 때, 최저점은 항상 failure 다음에 오는 success 지점으로 결정되는 구간들 사이에 존재하게 된다. 최근 조사된 3개의 succes 지점 중 가운데 있는 지점이 양쪽의 두개 지점보다 항상 작을 것이므로, 이 세 점을 이용하여 quadratic interpolation을 수행한다면 효과적으로 최저점을 찾을 수 있다.