논문

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

Line Search Methods (1)

http://pages.cs.wisc.edu/~ferris/cs730/chap3.pdf

Line search 방법은 매 반복마다 값이 최소인 지점으로 위치를 이동하기 위하여 탐색 방향 $ p_k $으로 얼마나 이동시켜야하는지를 결정하는 방법이다. 이를 수식으로 나타내면 아래와 같다.

$$x_{k+1} = x_k + \alpha_k p_k$$

여기서 $ \alpha_k $가 우리가 찾아야 할 값으로, step length 라고 부른다. 이를 제대로 찾으려면 일단 $p_k$가 값이 줄어드는 방향이어야 한다. 즉, $ p_k^T \nabla f_k \lt 0$ 이어야 한다.

종종 이 값은 $ p_k = -B_k^{-1} \nabla f_k $로 사용될 때가 많은데, 위의 조건을 만족하려면 $ B_k$는 정의에 따라 positive definite matrix이어야 한다. $B_k = I$인 경우에는 Steepest descent, $B_k = \text{Hessian } \nabla^2f(x_k) $ 일 때눈 Newton method이다. 또한, Hessian을 통하여 이 행렬의 근사값을 계산해낸다면 quasi-Newton 방법으로 불린다.

3.1 Step Length

Step length $ \alpha_k $를 계산해내야 하는 가운데 두가지 욕심이 있다. 비교적 정확하게 f를 감소시키면서도 최대한 시간을 적게 투자하고 싶은 것이다.

$$\min_{\alpha} \phi(\alpha) = f(x_k + \alpha p_k), \alpha \gt 0$$

정확한 값을 찾으려 한다면 시간이 너무나 많이 걸릴 것이다. 따라서 이 적당한 정확도로 찾도록 하여야 한다. 그 과정에서 함수 $ f$ 의 계산이나 그래디언트 $ \nabla f $가 필요할 수도 있다.

Line search 알고리즘은 대게 두가지 단계로 나눌 수 있는데, 먼저 적당한 step length가 있을 만한 범위를 좁히는 bracketing 단계와, 그 뒤 해당 영역 안에서 적당한 값을 찾는 bisection 또는 interpolation 단계로 나눌 수 있다. 이러한 단계에서 핵심적인 부분은 탐색 과정을 종료하고 적절한 값을 찾는 조건이라 할 수 있다.

가장 단순한 예로,

$$f(x_k + \alpha_k p_k) \lt f(x_k)$$

를 들 수 있다. 너무도 당연한 조건일 것이다.

The Wolfe Conditions

가장 많이 쓰이는 조건으로 Armijo condition이 있다.

$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \nabla f_k^T p_k, c_1 \in (0, 1)$$

이는 $\alpha_k$에 의해 위치가 이동했을 경우 함수 $f$가 충분히 낮아지는 지를 살펴보는 조건이다. 그 과정에서 진행 방향 $p_k$으로의 편미분 값 $\nabla f_k^T p_k$를 이용하여 조건을 추정하게 된다. 상수인 $c_1$은 주로 $10^{-4}$와 같은 아주 작은 값이 선택된다.

하지만 이 armijo condition만으로는 조금 부족하다. 이 조건은 매우 작은 $\alpha$값의 경우 거의 항상 만족하게 된다. 편미분 추정에 사용된 위치와 아주 가깝기 때문이다. 따라서 여기서 하나를 더 추가해보자. 바로 curvature condition 이다.

$$\nabla f(x_k + \alpha_k p_k)^T p_k \geq c_2 \nabla f_k^T p_k, c_2 \in (c_1, 1)$$

이 조건은 이동 후 위치의 변화율이 편미분 값보다 더 가파르게 낮아지는 것을 막고(값이 더 낮아질 수 있어보이므로), 완만한 부분이나 상승하는 부분이면 조건을 만족시켜 탐색을 종료하도록 한다. 일반적으로 newton 혹은 quasi-newton 방법에서는 $c_2 = 0.9 $를 사용하며, nonlinear conjugate gradient 방법에서는 0.1을 사용한다.

이 두 조건을 합쳐 Wolf condition이라고 부른다.

$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \nabla f_k^T p_k \\
\nabla f(x_k + \alpha_k p_k)^T p_k \geq c_2 \nabla f_k^T p_k$$

또한 변화율이 완만한 지점을 선택하도록 하도록 curvature condition를 변형한 strong Wolfe conditions도 있다.

$$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \nabla f_k^T p_k \\
| \nabla f(x_k + \alpha_k p_k)^T p_k | \leq c_2 \nabla f_k^T p_k$$

The Goldstein Conditions

또 널리 알려진 방법으로 Goldstein conditions이 있다.

$$f(x_k) + (1-c)\alpha_k \nabla f_k^T p_k \leq f(x_k + \alpha_k p_k) \leq f(x_k) + c \alpha_k \nabla f_k^T p_k , 0 \lt c \lt 0.5$$

이 방법의 단점으로 모든 영역의 $ \alpha $가 조건에서 제외되어버릴 수 있다는 점을 꼽을 수 있다. 이것은 Newton 방식의 알고리즘에서 주로 쓰이나, quasi-Newton 방법들에는 일반적으로 잘 맞지 않는다.

Sufficient Decrease and Backtracking

때로는 탐색 과정에서 이득을 볼 수도 있다. 바로 backtracking 방법이다. 이 방법은 적절한 $\alpha$를 선택하는 과정에서 그 후보 값들을 제시하는 역할을 한다. 잘만 이용한다면 때에 따라서 curvature condition을 생략할 수 있기도 하다.

$ \bar{\alpha} \gt 0, \rho, c \in (0, 1) ; set \alpha \leftarrow \bar{\alpha} $
repeat $ f(x_k + \alpha p_k) \leq f(x_k) + c \alpha \nabla f_k^T p_k $
$ \alpha \leftarrow \rho \alpha ;$
end (repeat)
Terminate with $\alpha_k = \alpha$

주로 Newton, quasi-newton 방법에서 초기 step length인 $\bar{\alpha}$로 1을 사용하지만 사용하는 알고리즘에 따라 다른 값을 사용하여도 된다. 매 반복마다 $alpha$를 얼마나 줄일지와 관련된 $ \rho $는 보통 상수를 사용하기도 하지만 매 반복마다 값을 변화시켜 사용할 수도 있다.


Add a Comment Trackback