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

4.7 Variable metric methods (VMM)

함수 $ F(\mathbf{x}) $를 파라미터 x에 대한 어떤 공간으로 생각하여보자. 그러한 공간 상에서 두 지점 사이의 거리는 $ \Delta \mathbf{s}^2 = \Delta \mathbf{x}^T \mathbf{A} \Delta \mathbf{x} $ 로 계산하곤 하다. 이 때 A는 공간의 특성을 결정짓는 covariant metric tensor이다. $ \mathbf{A = I} $ 라면 일반적으로 생각하는 유클리디언 공간에서의 L2 Norm의 거리가 되고, 비대각 행렬이 음수가 된다면 비 유클리디언 공간인 경우가 된다. 함수 $ F(\mathbf{x}) $의 Hessian matrix $ \mathbf{G} $는 우리가 다루는 이 공간의 covariant tensor와 같은 역할을 한다. 그리고 그 역행렬 $ \mathbf{V = G}^{-1} $은 contravariant tensor와 같이 작용한다. 따라서 한 점 $ \mathbf{x} $와 $ \mathbf{x} + \Delta \mathbf{x} $사이의 거리는 $ \Delta \mathbf{s}^2 = \Delta \mathbf{x}^T \mathbf{G} \Delta \mathbf{x} $ 와 같이 계산된다.

그리고

$$\rho = \mathbf{g}^T \mathbf{V} \mathbf{g}$$

는 위 식이 계산된 지점(V와 g)과 G를 만들어낸 quadratic form의 최소 지점간 거리의 2배가 된다. 즉, 함수 F가 quadratic form이라면, 현 위치에서 최소 지점까지의 거리는 $ \rho / 2 $라는 것을 의미한다.

함수 F가 완벽한 quadratic 형태라면 G는 어느 위치에서든 상수로 같은 값을 가지겠지만, 실제 비선형 함수에서는 높은 차수에 있던 항들이 작게나마 그대로 살아있게 된다. 따라서 이것들을 공간에서 천천히 변하는 matrix tensor로 간주해보자.

위의 것들을 이용하여 최소점을 찾는 방법을 variable metric methods라고 한다. Newton-Raphson 방법과 다른 점은, Hessian 행렬 G를 매번 다시 계산하지 않고 이전에 사용했던 G와 현재 지점의 정보를 이용한 추정 식에 따라 갱신하여 사용한다는 점이다. 이 추정 식을 어떤 것으로 사용하느냐에 따라 여러 방법들이 존재한다.

Variable metric methods는 아래와 같이 진행된다.

1. 주어진 $ \mathbf{x}_0 $에서 시작, 그래디언트 $ \mathbf{g}_0) $와 $ \mathbf{G}^{-1} = \mathbf{V}_0 $의 초기값을 계산해놓는다. $ \mathbf{G}^{-1} $는 단위행렬이나 실제 Hessian 행렬이 사용되는 경우도 있다.
2. 다음 위치 $ \mathbf{x}_1 = \mathbf{x}_0 - \mathbf{V}_0 \mathbf{g}_0 $를 계산한다. 이상적인 경우 이 위치는 최소점이 될 수 있지만, 이 방향으로 linear search를 이용하여 최소점을 탐색($ \mathbf{x}_0 - \alpha \mathbf{V}_0\mathbf{x}_0 $)하는 것이 유용할 수 있다. 그리고 새로운 지점에서의 그래디언트 $ \mathbf{g}_1 $ 또한 계산한다.
3. 행렬 $ \mathbf{V} $를 추정 식에 따라 갱신한다.

   $$\mathbf{V}_1 = \mathbf{V}_0 + f(\mathbf{V}_0, \mathbf{x}_0, \mathbf{x}_1, \mathbf{g}_0, \mathbf{g}_1)$$

4. 위의 2, 3 단계를 최소값에 수렴할 때 까지 반복한다.

4.8 Davidon’s rank-two formular

Davidon의 다음과 같이 V를 갱신하였다.

$$\mathbf{V_1 = V_0 + \frac{\delta\delta^T}{\delta^t \gamma} - \frac{V_0 \gamma \gamma^T V_0}{\gamma^T V_0 \gamma}}$$

$$\mathbf{ \delta = x_1 - x_0 }$$

$$\mathbf{ \gamma = g_1 - g_0 }$$

이 식의 필요조건은 $ \mathbf{ V_1 \gamma = \delta } $인데, 이것은 $ \mathbf{ \gamma = G \delta } $에서 나온 것이다.

이 방법의 단점은 매 반복마다 Newton step으로 주어진 $ \mathbf{-Vg} $ 방향으로의 linear search를 꼭 수행해야 한다는 점이다. 이 과정은 일반 비선형 함수에서 수렴하기 위해서는 꼭 필요한 과정이다 .또한 Fletcher와 Powell은 자신의 논문에서 초기 V가 positive-definite하다면 그 뒤에 갱신되는 V들도 모두 positive-definite하다는 것을 보였다.

4.9 The rank-one formula

위의 추정 식을 정리하여 다음을 얻을 수 있다.

$$\mathbf{V_1 = V_0 + \frac{(\delta - V_0 \gamma)(\delta - V_0\gamma)^T}{\gamma^T(\delta - V_0\gamma)}}$$

이 식은 이전의 rank-two의 조건에 추가하여, 이전 단계의 모든 $ \gamma_i $, $ \delta_i $ 쌍에 대해서도 $ \mathbf{ V_1 \gamma_i = \delta_i } $를 만족해야한다. 이것을 hereditary property라고 한다.

이 방법은 linaer search 과정 없이 수렴한다고 알려져 있으며, 또한 V는 대칭행렬이다. 하지만 만약 $ \gamma $가 $ (\mathbf{\delta - V_0 \gamma}) $에 orthogonal한 상황이 오면 분자 부분의 항의 0이 되어버리면서 계산을 할 수 없게 되는 단점이 있다. 또한 V가 넓게 변화하는 함수의 경우, 매 반복마다 오히려 갱신된 V가 좋지않은 값을 가지게 되는 경우도 생긴다.

4.10 Fletcher’s unified approach to VMM

Fletcher는 rank-two와 rank-one, 두 식을 통합하여 사용하는 방법을 제안하였다.

먼저 기존의 rank-two 식에서 유도하여 dual formula를 정의한다.

$$\mathbf{ v_1 = (I - \frac{\delta \gamma^T}{\delta^T \gamma}) V_0 (I - \frac{\delta \gamma^T}{\delta^T \gamma})^T + \frac{\delta \delta^T}{\delta^T \gamma} }$$

기존의 rank-two 식을 $ \mathbf{ V_1 = T(V_0)}, $ dual formula를 $ \mathbf{V_1 = D(V_0)} $라고 표현한다면,

새로운 추정 식은,

$$\mathbf{ V_{\phi} = (1 - \phi)T + \phi D}$$

와 같이 사용한다.

이 때, $ \phi $는 추정 식의 정확도를 결정짓는 파라미터로,

$$\mathbf{ \phi(rank-one) = \frac{\delta^T \gamma}{\delta^T \gamma - \gamma^T V_0 \gamma} }$$

를 사용한다.

이러한 식을 사용하면 갱신되는 V가 monotonic 하게 실제 cavariance 행렬에 가깝도록 수렴하는 특정이 있다. 이는 매 반복마다 추정된 V의 질이 향상됨을 의미한다.