Gradient descent
global minimum이나 global maximum이 아닌 가까운 local minumum이나 maximum을 찾는 방법입니다. 초기값에 따라 찾는 솔루션이 달라집니다. 복잡한 함수인 경우에는 초기값에 따라서 global minimum을 찾을 수 도 있습니다. convex function이라면 어느 점이든 상관이 없습니다.
동작 방식은 지금 내 위치에서 비용이 작아지는 방향으로 이동합니다. 이동하는 정도는 사용자가 정해줘야합니다. 그래서 알아야 하는 것들이
1. 기울기를 통해서 비용이 가파르게 내려가는 방향을 알아야 합니다.
2. 얼마나 내려갈 것인지 (step size)
방향은 단순하게 미분만 해도 알 수 있습니다.
초기값 $x_k$가 존재할 때 다음 지점은 $x_{k+1} = x_k - \alpha \frac {df}{dx}$를 통해서 구합니다. 초기화 과정을 제외하고 반복하여 local minimum을 찾으면 됩니다.
이때 적절한 학습률(learning rate)을 찾아야합니다. 너무 큰 학습률이면 global minimum에 도달하지 못할 수 있고 너무 작은 학습률이면 시간이 오래 걸립니다. 학습률을 효율적으로 사용하기 위해서 처음에 학습률을 어느 정도 크게 설정하고 매 스탭마다 조금씩 줄어주는 방법을 사용하기도 합니다.
Error function
현재 지점에서 얼만큼의 오차가 존재하는지 알 수 있게 해주는 함수입니다.
$z = x+n$ 여기서 n은 noise를 의미합니다. 최적의 해가 x일 때, 주어진 z를 통해서 x를 찾으면 됩니다. (z는 측정값, x에 노이즈가 낀 값)
$f = (z - x)^2$ 만약 벡터라면 $(z - x)^T(z - x)$를 통해서 제곱을 만들어주면 됩니다.
여기서 우리가 알고 싶은 x값에 어떤 노이즈가 더해진 측정값 z를 얻는다고 해봅시다. $z = Ax + n$ 여기서 A라는 행렬을 곱해준 형태가 우리가 많이 접하는 형태입니다.
- x에 선형변환 후 거기다 노이즈를 더한 다음 측정이 됩니다.
즉 $f = (z - Ax)^T (z - Ax) $ 형태로 나오게 됩니다. 이 error function이 최소화되는 x값을 찾으면 됩니다.
error function의 값은 스칼라 값이 나와 대소 구분이 가능합니다.
이 error function을 미분할 시 아래와 같이 정리가 됩니다.
$df = \frac {df}{dx^T}dx$
$= (-Adx)^T(z - Ax) - (z-Ax)^TAdx$
$= - 2(z - Ax)^TAdx$
위에서 전치된 벡터(행 벡터) 곱하기 열 벡터이므로 내적이 이루어져 스칼라 값이 나옵니다. 즉 스칼라 값이라서 전치를 하더라도 그 상태가 유지됩니다. 그래서 $(-Adx)^T(z - Ax) = - (z-Ax)^TAdx$ 가 같기 때문에 묶어줄 수 있습니다.
Newton's method
뉴턴법도 위에와 동일한 문제에 대해서 진행해 보겠습니다.
$(z = Ax + n)$, object function: $(z - Ax)^T(z - Ax)$
뉴턴법은 방향을 알고 있을 때 어느 정도 이동할지 정하는 방법입니다. 그러기 위해서 zero finding을 진행합니다.
zero finding이란 어떤 함수 $f(x)$가 존재할 때 $f(x) = 0$을 만드는 x값을 찾는 것을 말합니다.
다음과 같은 곡선함수에서 0이 되는 지점을 찾으려고 할 때 뉴턴법을 적용해보겠습니다. 우리가의 시작 지점은 $x_0$입니다. 이때 $x_0$에서 곡선과 접하는 노란색 접선을 이용해서 $x_1$을 구할 수 있습니다. 그 다음 $x_1$에서 곡선과 접하는 분홍색 접선을 통해서 $x_2$를 찾을 수 있습니다. 이렇게 최종적으로 0이 되는 지점을 찾으면 됩니다.
$x_0$ 지점에서 어떻게 $x_1$ 으로 이동할 수 있을까요?: 두 점 사이의 거리를 구해야 합니다.
$x_0$ 지점에서 접선의 기울기는 $\frac {높이} {밑변}$, 여기서 높이는 $f(x_0)$
$\frac {밑변} {높이} \times f(x_0) = \frac {밑변} {높이} \times 높이$
이 방법으로 $x_{k+1}$ 지점을 찾으면
$x_{k+1} = x_k - \frac 1 {f'(x_k)} \times f(x_k)$
이 방법을 사용하면 어떤 지점에서 시작하던지 상관없이 진행하면 됩니다. 다른 방향에서 시작하더라도 그 지점에서 접선을 보내 x축과 만나는 부분을 찾고 또 그 부분에서 접선을 보내는 작업을 반복하면 됩니다.
함수가 직선일 경우 한 번에 찾을 수 있고 convex여도 몇 번안에 갈 수 있어서 빠르게 원하는 값을 찾을 수 있습니다.
왜 zero finding을 사용할까?
zero finding은 함수값이 0이 되는 지점을 찾기 수월합니다. object function이 존재할 때 global minimum은 미분이 0이 되는 지점입니다.
다음과 같은 convex function을 미분했을 때 0이 되는 지점을 찾으면 즉 비용함수를 어떤 변수로 미분한 뒤 0되는 지점을 찾으면 비용을 최소화하는 변수를 얻을 수 있게 됩니다.
직선이므로 한 번에 비용을 최소화시키는 점을 찾을 수 있습니다. (속도가 빠르다.)
이제 뉴턴법과 경사하강법 두 최적화 방법들이 어떤 관계를 가지고 있는지 알아보겠습니다.
$x_k + 2A^T(z-Ax_k) \ times \alpha$
$x_{k+1} = x_k - \frac 1 {f''(x_k)} \times f'(x_k)$
경사하강법은 $2A^T(z - Ax)$라는 $f'(x)$을 가지고 있고 뉴턴법은 $f'(x)$를 가지고 있습니다. 그리고 경사하강법은 $\alpha$를 가지고 뉴턴법은 $\frac 1 {f''(x_k)}$를 가집니다. 즉 두 방법 모두 기울기 부분을 가지고 있으며 그 기울기에 어떤 값을 곱해준다는 공통점을 가지고 있습니다.
$\alpha$를 $\frac 1 {f''(x_k)}$ 다음과 같은 방법으로 계산하면 적절한 $\alpha$ 값을 찾을 수 있을 것입니다. 이때 $f(x)$의 출력이 행렬이라면 $\frac 1 {f''(x)}$는 hessian matrix가 됩니다.
object function: $(z - Ax)^T(z - Ax)$이고 $x_{k+1} = x_k 2A^T(z - Ax_k) \alpha$
$\frac {df} {dx^T} = -2(z - Ax)^TA $
$\frac {d} {dx^T} ( \frac {df}{dx^T})^T = 2A^TA$, (이제 이 값을 역수 취하면 $\alpha$ 값이 됩니다.)
$x_{k+1} = x_k + (2A^TA)^{-1}2A^T(z - Ax_k)$
$= x_k + (A^TA)^{-1}A^T(z - Ax_k)$
결과적으로 다음과 같이 풀어집니다. 여기서 $(A^TA)^{-1}$은 얼마만큼 이동하는지를 알려주고 나머지는 방향을 알려줍니다. 만약 A가 가역행렬이라면 또 한 번 정리가 가능합니다. $(A^TA)^{-1}$와 $A^TA$가 지워지므로 아래와 같이 됩니다.
$x_{k+1} = (A^TA)^{-1}A^Tz$
이 형태는 최소제곱법(least square)과 같습니다. 즉 global minimum 값이 최소제곱법으로 구해진다는 것입니다.
정리하면 3가지 방법으로 convex problem 문제를 해결할 수 있습니다.
1. 경사하강법(Gradient descent)
2. 뉴턴법(Newton's method)
3. 최소제곱법(Least square)
'수학 > 최적화 공부' 카테고리의 다른 글
| 1. convex optimization 란? (0) | 2022.05.22 |
|---|