논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

MINUIT Tutorial – Function Minimization (3)

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

3 Stepping methods in many variables

3.1 Grid search and random searches

이제 여러 파라미터를 갖는 함수의 경우를 생각하여보자. 앞의 파라미터가 1개인 경우 Grid search 방법으로 전체 구간 중 1% 의 정확도로 최저점을 탐색하기 위해서는 100번의 함수 값 계산이 필요하다. 이를 10개의 파라미터를 갖는 경우로 확장시키면 총 $ 10^{20} $번의 계산이 필요하게 된다. 이와 같이 파라미터의 수가 늘어 계산 공간의 차원이 증가할 때마다 grid search는 사용하기 힘들 정도로 급격하게 계산 수가 늘어나게 되므로 현실적으로 1, 2개의 파라미터를 갖는 경우 외에는 사용하기가 힘들다.

3.2 Single-parameter variation

최저점이 각 파라미터에 대하여 $ \partial F / \partial x_i$ 방향으로 낮아질 것이라고 생각한다면, 각 파라미터의 편미분 값을 따로 떼어내어 각 파라미터에 대하여 하나씩 차례로 계산하는 방법을 생각할 수 있다.

실제로는 한 파라미터 $ x_2 $에 대하여 낮아지는 방향으로 이동시키고 나면, 그 지점은 더 이상 이전의 파라미터 $ x_1 $에 대해서는 작은 지점이라고 이야기 할 수 없다. 그럼에도 이 방법은 대체로 잘 작동하는 편이다.

때때로 문서의 그림 5와 같이 함수가 얕은 계곡의 형태로 길죽한 모양을 갖고 있을 경우, 진동하면서 아주 천천히 수렴하는 형태를 보이기도 한다.

3.3 The Rosenbrock’s method

이 방법은 위의 Single-parameter 방법에서 뻗어나온다. 일단 한번 모든 파라미터에 대해 계산을 마치고 나서, 원래 시작햇던 지점과 마지막 파라미터까지 계산을 마친 지점과의 벡터에 대한 orthogonal한 축들을 계산한다. 이 새로운 축들을 기준으로 다시 Single-parameter 계산 방법을 반복한다.

이 방법은 어떤 함수에서의 진동하는 현상을 극복하였으나, 변수의 수가 늘어남에 따라 효율성이 떨어지게 된다.

3.4 The simplex method

Simplex 방법은 n개의 변수가 있을 경우 n + 1개의 지점의 값이 필요하다. 먼저 n + 1개 지점의 값을 조사한 뒤, 그 중 값이 가장 높은 지점을 $ P_H $, 낮은 지점을 $ P_L $ 이라고 하자. 이 때, $ P_H $ 를 제외한 나머지 지점들로 이루어지는 도형의 중점 $ \bar{P} $ 는,

$$\bar{P} = \frac{1}{n} \sum^{n+1}_{i=1} {P_i - P_H}$$

로 게산할 수 있다.

이제 이를 바탕으로 $ P_H $ 를 새로운 점 $ P^{**} $ 로 갱신하여 도형을 줄여나가도록 하자. 점 $ P^* = \bar{P} + (\bar{P} - P_H) $를 계산해본 뒤에, 이 점의 값이 $ F(P^*) \lt F(P_L) $ 이라면 새로운 점은 $ P^{**} = \bar{P} + 2(\bar{P} - P_H) $로, 반대의 경우 $ P^{**} = \bar{P} + -1/2(\bar{P} - P_H) $로 계산된다. 이러한 과정을 $ F(P_H) - F(P_L) $ 이 어느 수준 이하가 될 때 까지 반복한다.


Tags:
Add a Comment Trackback