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

4 Gradient methods

4.1 Calculating derivatives

최소점을 탐색하기 위해 좀 더 나은 다음 지점을 선택하기 위해서 미분값과 같이 해당 지점과 그 바로 인접한 지점의 정보를 이용하는 방법을 그래디언트 기반의 방법으로 묶고 이 장에서 이야기해보도록 하자.

이미 수식이 알려진 함수의 그래디언트는 계산을 통하여 쉽게 구해지는 편이지만, 수식이 복잡할 때에는 그 계산이 간단하지만은 않고, 최소점에서의 미분이 불가능한 경우가 있기도 하다. 무엇보다 실제 수식이 주어지는 경우는 드물다. 따라서 보통 미분값이 필요할 때는, 근접한 두 지점의 값을 계산 한 뒤 이들을 이용하여 추정하는 것이 일반적이다.

1차 미분은 작은 간격 d에 의해서 다음과 같이 계산된다.

$$\frac{\partial F} {\partial x} \left. \right|_{x_0} \approx \frac{F(x_0 + d) - F(x_0)}{d}$$

이 때의 오차는 Taylor expansion에 의해,

$$\delta \approx \frac{d}{2} \dot{} \frac{\partial^2 F}{\partial x^2} \left.\right|_{x_0}$$

이다. 따라서 간격 d가 작으면 작을 수록 오차가 적어지겠지만, 일정 수준 이하가 되면 계산 상 rounding-off 오차가 $ \delta $ 보다 커져버리게 된다. 게다가 2차 미분 값을 알 수가 없으므로 최적의 간격 d는 오로지 사람이 정해주는 값에 의존할 수밖에 없다.

더 안전한 방법은 다음과 같이 지점의 양쪽 값을 사용하는 것이다.

$$\frac{\partial F} {\partial x} |_{x_0} \approx \frac{F(x_0 + d) - F(x_0 - d)}{2d}$$

이 때에는 오차가 3차 미분 값에 비례하게 되나, 이전 방법보다 함수 F의 계산을 한번 더 해야하므로 계산량이 2배로 늘어난다는 점이 단점이다. 그럼에도 이 방법은 2차 미분 값을 아래와 같이 게산할 수 있다는 장점이 있다.

$$\frac{\partial^2 F} {\partial x^2} \approx \frac{F(x_0 + d) - F(x_0 - d) + 2 F(x_0)}{d^2}$$

4.2 Steepest descent

함수의 1차 미분 값을 알 수 있게 되었다면, 자연스럽게 이 값의 반대 방향으로 이동하면서 최소값을 찾는 방법을 생각할 수 있다. One dimensional minimization 방법과 비슷하게 현재 위치에서 그래디언트를 계산한 뒤 이동하고, 다시 그래디언트를 계산한 뒤 다음 지점으로 진행하는 과정을 반복하다. 하지만 계산된 그래디언트는 현재 위치에서 국소적으로 계산되기 때문에 함수의 모양에 따라 그래디언트의 방향이 엉뚱한 방향을 가리키는 경우도 있어 비효율적인 탐색이 이루어질 수 있다.

4.3 Newton’s method

1차 미분 값과 2차 미분 값을 알 수 있다면, 2차 식으로 함수를 추정할 수 있다.

$$F(\underline{x}) = F(\underline{x}_0) + \underline{g}^T(\underline{x} - \underline{x}_0) + \frac{1}{2} (\underline{x} - \underline{x}_0)^T \mathbf{G} (\underline{x} - \underline{x}_0)$$

$ \underline{g} $, $ \mathbf{G} $ 는 각각 지점 $ \underline{x}_0 $에서의 그래디언트와, 2차 미분 행렬이다. 따라서 이 식의 최소점은,

$$\underline{x}_m = \underline{x}_0 - \mathbf{G}^{-1} \underline{g} = \underline{x}_0 - V\underline{g}$$

으로, 2차 미분 행렬의 역행렬인 공분산(covariance) 행렬 $ V $ 를 이용하여 표현된다.

이것은 앞에서 다루었던 quadratic interpolation과 같은 원리로 다음과 같은 장점이 있다.

1. 다음 지점으로 이동할 거리가 알고리즘에 의해 정해진다.
2. 다음 지점의 방향 또한 알고리즘에 의해 결정된다.

하지만, 이 방법은 앞에서의 quadratic interpolation과 같은 이유로 안정적이지 못한 방법이다. 특히 $ G $, $ V $가 positive-definite가 아닌 경우에 그런 모습을 보인다.

4.4 Positive-definite quadratic forms

앞으로 계속 이 quadratic 표현식을 사용할 것이기 때문에 잠시 설명을 멈추고 quadratic 표현에 대해 이야기해보자.

1차원의 quadratic 표현은 아래와 같다.

$$F(x) = a + gx + \frac{1}{2} G x^2$$

여기서 $ g = \partial F / \partial x $와 $ G = \partial ^2 F / \partial x^2 $는 각각 $ x = 0 $ 에서의 1차, 2차 미분 값이다. 이 함수는 오직 $ G \geq 0 $ 일때만 최소가 된다. $ G = 0 $이라면, 최소점은 $ x = -g/G $ 에 의해 무한대에 존재하게 된다. 따라서 이 quadratic 표현을 적용하여 함수를 최소화 시키려면, $ G \gt 0 $ 일 경우에만 다음 조사해볼 위치로 $ x = -g/G $를 사용할 수 있고, 그게 아니라면 최대점이나 무한대 방향으로 뻗어나가게 될 것이다.

이 식을 여러 파라미터를 갖는 함수로 확장시켜보면 다음 조사 위치는 $ \underline{x} = -G ^{-1} \underline{g} $ 는 오직 $ G $와 $ G^{-1} $가 positive-definite 일 때만 유효하다.

Positive-definite 행령은 몇가지 유용한 특성을 가지고 있다.

1. 대각 성분은 양수 값이다.
2. 비 대각 성분들은 $ G^2_{ij} \lt G_{ii} G_{jj} $ 를 만족한다.
3. 모든 아이겐밸류(eigenvalue)는 양수 값이다.
4. 왼쪽 위에서부터의 정방형 부분 행렬의 디터미넌트는 양수 값이다.
5. 모든 벡터 $ \underline{e}$ 에 대하여, $ \underline{e}^T G \underline{e} $는 양수이다.
6. 그 역행렬 $ G^{-1} = V $ 또한 positive-definite 이다.

만약 $ G^{-1} $가 positive-definite가 아닌 것으로 계산되었을 때는 가장 큰 음 아이겐밸류보다 큰 값 $ \lambda $를 선택하여 $ (G + \lambda I)^{-1} $를 대신 쓰는 등의 대안들이 존재한다.

이러한 뉴튼 방법에서 변화되어 뻗어나온 방법들을 quasi-Newton 방버이라고 부른다. 이러한 방법들은 2차 미분 행렬을 구하고 그 역행렬 또한 매 단계마다 반복하여 계산하여야 한다는 단점을 가지고 있다. 이제 설명할 방법들은 일일이 정확하게 $ G $의 계산을 하지 않는 방법을 사용하고 있는 것들이다.

4.5 Conjugate directions

positive definite 행렬 A 에 대해서 서로 다른 두 벡터에 대하여 $ \underline{d}_i \mathbf{A} \underline{d}_j = 0 $ 와 같다면 conjugate하다고 한다.

이것으로 A 에 대한 n개의 conjugate vector를 이용하여 확장된 공간을 이야기 할 수 있으며, 공간 상의 한 점은 이들 벡터의 선형 조합(linear combination)으로 나타낼 수 있다. 그 특성은 A에 따라 달라진다. 이러한 conjugate vector 집합들은 Gram-Schmidt orthogonalization와 비슷한 방법을 적용하여 계산해낼 수 있다.

Fletcher와 Reeves에 따르면, Hessian 행렬 $ \mathbf{G} $의 n개의 conjugate 벡터로 나타내지어지는 방향은 n개 파라미터를 갖는 일반 2차 함수를 최소화한다고 한다.

Quadratic 함수 표현에서 시작해보자.

$$F(\underline{x}) = F(\underline{0}) + \underline{g}^T\underline{x} + \frac{1}{2} \underline{x}^T \mathbf{G} \underline{x}$$

그리고 G에 대하여 n개 conjugate 방향을 구하자.

$$\underline{d}_i \mathbf{A} \underline{d}_j = 0$$

그렇다면, 벡터 $ \underline{x} $과, $ \underline{g} $는 이 conjugate 벡터들의 선형 조합으로 표현될 수 있다.

$$\underline{x} = \sum_{i}{y_i \underline{d}_i }$$

$$\underline{g} = \sum_{i}{c_i \underline{d}_i }$$

그렇다면, 본래 Quadratic 함수는,

$$F(\underline{x}) = F(\underline{0}) + \left(\sum_{i}\sum_{j}{c_i \underline{d}_i^T }{y_j \underline{d}_j }\right) + \frac{1}{2} \left(\sum_{i}{y_i \underline{d}_i^T }\right) \mathbf{G} \left(\sum_{j}{y_j \underline{d}_j }\right)$$

와 같이 변환할 수 잇다. 여기서 마지막 항은 conjugate 속성에 의해서 $ i \neq j $인 항은 모두 0이 되므로,

$$F(\underline{x}) = F(\underline{0}) + \left(\sum_{i}\sum_{j}{c_i \underline{d}_i^T }{y_j \underline{d}_j }\right) + \frac{1}{2} \sum_{j}{y^2_j\underline{d}^T_j \mathbf{G} \underline{d}_j \\
= F(\underline{0}) + \sum_j {b_j y_j + b'_j y^2_j}
}$$

으로 정리된다. 여기서 $ b_j = \sum_i {c_i \underline{d}^T_i \underline{d}_j } $와, $b'_j = \underline{d}^T_j \mathbf{G} \underline{d}_j $는 상수로 계산될 수 있다. 따라서 이렇게 정리된 식은, 기존의 각 파라미터에 x로 이루어지는 공간에서 최소화하던 것을 conjugate vector로 이루어진 공간에서의 문제로 변환하여 풀 수 있도록 해 준다. 이것은 각 conjugate 방향은 다른 것들과 비종속적(independent)이므로, 기존의 single-parameter-variation 방법이 왜 잘못되었는지를 잘 나타내기도 한다.

하지만 conjugate 벡터를 계산하려면 Hessian 행렬을 알고 있어야 하므로 실제 적용하기에는 어려운 방법이다.

4.6 Conjugate gradients

함수의 그래디언트를 계산할 수 있으면 더 그럴듯한 방법을 사용할 수 있다. 바로 conjugate gradients 방법이다.

먼저 두 위치의 함수 값과 그래디언트를 알아냈다고 하고,

$$\underline{\Delta x} = \underline{x}_1 - \underline{x}_0$$

$$\underline{\Delta g} = \underline{g}_1 - \underline{g}_0$$

를 계산하면, Hessian 행렬 G에 의해 $ \underline{\Delta g} = G \underline{\Delta x} $ 이다.

그렇다면, $ \underline{\Delta g} $ 에 직교(orthogonal)하는 벡터 $ \underline{d}_1 $ 는 $ \underline{\Delta x} $에 conjugate하다.

$$\underline{d}^T_1 \underline{\Delta g} = \underline{d}^T_1 G \underline{\Delta x} = 0$$

이전 장의 것과는 달리 이 방법을 이용하여 Hessian 행렬을 알지 않아도 conjugate 벡터의 방향을 구할 수 있다. conjugate gradients 방법에서는 매 반복마다 하나의 conjugate 방향에 대하여만 최소화가 진행된다. 알고리즘의 처음에는 초기 위치 $ \underline{x}_0 $에서 $ \underline{d}_0 = -\underline{g}_0 $으로 방향으로 steepest descent 방법을 적용하여 다음 지점 $ \underline{x}_1 $과 그래디언트 $ \underline{g}_1 $을 얻는다. 이를 이용하여, 기존 것과의 조합을 통해 다음 방향을 업데이트하는 식을 정의하여 보자.

$$\underline{d}_1 = -\underline{g}_1 + b \underline{d}_0$$

구하여야 하는 것은 b 이고, 이 때 조건은 conjugate 정의에 의해,

$$\underline{d}^T_1 G \underline{d}_0 = \underline{d}^T_1 G (\underline{x}_1 - \underline{x}_0) = 0$$

이다. 위의 식에 그 전 식을 치환하고 정리하면 $ b = \frac{\underline{g}^T_1\underline{g}_1}{\underline{g}^T_0\underline{g}_0} $ 으로, 최종적으로 다음 conjugate 방향은,

$$\underline{d}_1 = -\underline{g}_1 + \frac{\underline{g}^T_1\underline{g}_1}{\underline{g}^T_0\underline{g}_0} \underline{d}_0$$

이다. 이 식을 이용하여 반복적으로 다음 지점을 탐색해가며 최소화 과정을 진행한다.

---