how to solve it, ch3

 Exhaustive Search는 말 그대로 모든 탐색 영억을 고루 찾아보는 알고리즘이다. 그렇기 때문에 계산량과 시간이 엄청나게 소모되는 단점이 있다. 한가지 요구사항은 가능성이 있는 답을 어떻게 체계적으로 생성해낼 것인가이다. 이를 통하여 그나마 계산량과 시간을 줄일 수 있다. 뒤에서 그런 내용이 나온다고 하니 나중에 살펴보자.

 모든 탐색 공간을 찾는 것은 어려울 수 있다. 그러면 근처의 답을 찾아 나가는 것이 한 방법인데, 이를 local search라 한다. Local search는 다음의 방식으로 이루어진다.

1. 탐색 공간에서 하나의 답을 지정하고 이 답을 평가 한다. 이 답이 현재 답 이다.
2. 현재 답에서 새로운 답을 만들어내기 위해 현재 답을 변형한다.
3. 현재 답 보다 새로운 답이 나으면 현재 답을 새로운 답으로 대체하고, 아니면 새로운 답을 버린다.
4. 현재 답 보다 더 나은 답이 나오지 않을 때 까지 2-3을 반복한다.

 위의 단계에서 중요한 것은 ‘변형’의 방법이다. 현 답에서 새로운 답을 얻기 위한 방법이 적절하지 못할 경우 전혀 엉뚱한 영역의 답을 내놓는다든가, 계속 같은 답을 내놓을 수도 있다.

 비선형 문제의 최적화는 대부분 국소 탐색을 이용한 알고리즘을 이용한다. NLP문제는 다음의 답 $vec{x}$를 찾기 위함이다.
$$
optimize f(vec{x}), vec{x} = (x_1, ldots , x_n) in mathcal{R}^n
$$
 여기서 $vec{x} in mathcal{F} subseteq mathcal{S}$이며, 평가 함수 $f$는 탐색 공간 $mathcal{S} subseteq mathcal{R}^n$에서 정의된다. 그리고 $mathcal{F} subseteq mathcal{S}$는 실현 가능 영역을 정의한다. 일반적으로 탐색 공간 $mathcal{S}$는 $mathcal{R}^n$ 상의 $n$차원 정사각형 공간으로 정의할 수 있다. 변수의 영역은 다음의 하한과 상한으로 정의한다.
$$
l(i) leq x_i leq u(i), 1 leq i leq n
$$
 그리고 실현 가능 영억 $mathcal{F}$는 $m$개의 추가 제약사항으로 정의할 수 있다.
$$
g_j(vec{x}) leq 0, text{ for } j=1,ldots,q, text{ and }h_j(vec{x}) = 0, text{ for }j = q+1,ldots, m
$$

 NLP는 문제의 양상이 매우 다양하여 하나의 정해진 방법만 사용하지 않는다. 그래서 여러 가지의 알고리즘을 두고 문제마다 맞는 방법을 사용해야 한다.

 이 bracketing method 중 가장 잘 알려진 방법은 bisection search 방식이다. $f(x^{*}) = 0$을 만족하는 $x^{*}$를 찾는 문제가 있다고 하자.

 위의 그림에서 곡선이 $f(x)$이다. 만약 $f(a)f(b) < 0$이라면 $a$와 $b$ 사이에 찾는 답이 있는 것이므로, 이를 바탕으로 다음 순서대로 문제를 푼다.

1. $f(a)f(b) < 0$이 되도록 $a$와 $b$를 고른다.
2. $m leftarrow (a + b)/2$를 만든다.
3. $f(m)$이 0이 아니라면 $f(a)f(m) < 0$이거나, $f(m)f(b) < 0$이다. 만약 전자의 경우라면 $bleftarrow m$으로 하고, 후자의 경우라면 $a leftarrow m$으로 한다
4. 만약 $(b-a) < epsilon$이라면 멈추고, 아니라면 2번을 반복한다.

 Bracketing method가 훌륭하지만, 탐색 공간이 클 경우 수행 시간이 느릴 수 있다. 여기 소개하는 fixed points method는 앞의 방식보다 속도가 빠른 장점이 있다. 하지만 시작점을 잘못 고를 경우 답에 수렴 못할 가능성이 있다. 여기서 Newton’s method를 소개한다.

 위의 그림에서 $f(s)=0$인 $s$를 찾는다고 하자. 일단 처음 임의의 점을 선택한 후, 그 점에서 $f(x)$의 접선(tangent line)을 그린다. 그리고 그 접선이 0과 만나는 지점을 새로운 시작점으로 하여 앞의 내용을 반복한다. 새로운 점의 값은 다음의 식으로 찾는다.
$$
s_{n+1} = s_n - frac{f(s_n)}{f’(s_n)}
$$
 이렇게 반복 후 $f(s)$의 값이 원하는 결과 값과의 차이가 $epsilon$보다 작을 때까지 수행한다.

 평가 함수 $f(vec{x})$가 어떤 위치 $vec{x}$에서 충분히 부드럽다면, 그 점에서 미분 가능하다. 이 성질을 이용하여 이 함수의 극소, 극대 값을 구할 수 있다. 한 점에서의 미분 값(경사)가 가장 큰 부분으로 이동한다면 빠른 속도로 답을 향해 움직인다고 예상할 수 있다. 한 점에서의 기울기는 다음처럼 벡터 요소를 미분함으로써 얻을 수 있다.
$$
nabla f(vec{x}) =
left[ frac{partial f}{partial x_1}, frac{partial f}{partial x_2},…,frac{partial f}{partial x_n} right]
$$
 이를 이용하여 다음 위치 $vec{x}_{k+1}$은 다음과 같이 구한다.
$$
vec{x}_{k+1}=vec{x}_k - alpha_k nabla f(vec{x}_k)
$$
 여기서 $alpha_k$는 갱신률(learning rate)로서, 크기에 따라 갱신 속도를 조정한다. 사실 이 부분의 값을 어떻게 하느냐가 일종의 기술이라 볼 수 있다.
 다음 위치 값을 구할 때 평가 함수의 이차 미분을 사용할 수 있다. 이차 미분을 이용하여 다음 점을 찾는 방식도 Newton’s method이다.
$$
vec{x}_{k+1} = vec{x}_k - (H(f(vec{x}_k)))^{-1}nabla f(vec{x}_k)
$$
 여기서 $H(f(vec{x}_k))$는 $f$의 헤세(Hessian) 행렬로서, $vec{x}$의 각 요소를 이용한 이차 미분을 포함한다. 물론 교차항의 미분도 포함한다.
$$
H(f(vec{x}_k)) = begin{bmatrix}
frac{partial^2 f}{partial x_{1}^{2}} & frac{partial^2 f}{partial x_1 x_2} & cdots & frac{partial^2 f}{partial x_1 x_n} \
frac{partial^2 f}{partial x_2 x_1} & frac{partial^2 f}{partial x_{2}^{2}} & cdots & frac{partial^2 f}{partial x_2 x_n} \
vdots & vdots & vdots & vdots \
frac{partial^2 f}{partial x_n x_1} & frac{partial^2 f}{partial x_n x_2} & cdots & frac{partial^2 f}{partial x_{n}^{2}} \
end{bmatrix}
$$
 문제는 이 헤세 행렬의 역행렬을 쉽게 구할 수 있는 경우가 드물다는데 있다. 그래서 이를 위해 수치적 방법을 이용하여야 한다.(책에 소개되어 있지 않으니 여기서도 생략한다.)
 이 Newton’s method는 테일러 시리즈를 이용한 함수 추정에 바탕을 두고 있다. 한 점 $x_n$에서 충분히 부드러운 함수 $f(x_n)$를 정의할 수 있다면, $f(x_n +epsilon)$은 다음과 같이 추정할 수 있다.
$$
f(x_n +epsilon) = f(x_n) + f’(x_n)epsilon + frac{1}{2}f’’(x_n)epsilon^2
$$
 여기서 $x_n$이 시작점이므로, $x_n$에서 추정한 함수의 최대 또는 최소 값은 $epsilon$에 대해 미분했을 때 0이 되는 부분일 것이다. 이 추정을 바탕으로 위의 식을 $epsilon$에 대해 미분하면 다음과 같다.
$$
0 = f’(x_n) + f’’(x_n)epsilon
$$
 이를 $epsilon$에 대해 풀면 다음의 등식을 얻을 수 있다.
$$
epsilon = - frac{f’(x_n)}{f’’(x_n)}
$$
 이를 이용하여 다음 지점$x_{n+1} = x_n + epsilon$을 추정하면 다음과 같다.
$$
x_{n+1} = x_n + epsilon = x_n - frac{f’(x_n)}{f’’(x_n)}
$$
 위의 식에서 함수 $f$가 다차원 변수 $vec{x}$에 대한 함수라고 하자. 그러면 일차 미분 항이 $nabla f(vec{x})$이고, 이차 미분항이 $H(f(vec{x}))$가 된다.