최적화 기법 정리(Gradient-Descent,Gauss-Newton, Levenberg-Marquardt)

Gradient descent

현재 state에서 cost function의 derivate(jacobian)를 구하고, 해당 방향의 반대 방향으로 step size를 곱한 만큼 state를 변화시킨다. 값이 수렴할 때까지 반복한다.

$x_{k+1}=x_{k}-\alpha \nabla f(x_i)$

• local minima에 빠지기 쉽고, 딥러닝 분야에서는 momentum을 이용한 optimizer를 사용하기도 한다.

Newton-Raphson

newton raphson 방식은 본래 함수의 해를 찾는 기법이다.
따라서 함수의 Jacobian의 해를 찾게 되면(기울기=0) minimum한 지점을 찾는 것이므로 엄밀히 말하면, cost function의 Jacobian에 대해 newton raphson 기법을 적용하는 것이다.
$f(x)$의 Jacobian을 $J(x)$, Hessian을 $H(x)$라 하면,
$J(x)$를 선형근사하면 아래와 같다.
$\tilde{J}(x)=J(x_k)+ H(x-x_k)$
$\tilde{J}(x_{k+1})=0$을 대입한 뒤 정리하면,
$x_{k+1}=x_k-H(x_k)^{-1}J(x_k)$

• Hessian이 0이 되는 지점에서 발산하는 문제가 있다.

Gauss-Newton

Gauss-Newton은 Newton-Raphson 방법에서 연립 방적식으로의 확장 + Hessian의 근사값 사용. 2가지 차이가 있다.
여기서의 cost function은 residual의 squared sum을 의미한다. 여기서 $r_i$는 non-linear function이어도 상관 없다.
cost function : $f(x)=\Sigma r_i(x)^2=||r(x)||^2$
이러한 squared sum에 대한 최적의 parameter를 찾는 것을 least squares problem이라 한다.

Jacobian

$\frac{\partial f}{\partial x_j}=2\Sigma_i\frac{\partial r_i}{\partial x_J}r_i$이므로,

$J=\nabla f=2(\nabla r)^Tr=2J_r^Tr$을 얻는다.

where $\nabla r(x)=J_r=\begin{pmatrix}\frac{\partial r_1}{\partial x_1} & \frac{\partial r_1}{\partial x_2}&...\\\frac{\partial r_2}{\partial x_1}& \frac{\partial r_2}{\partial x_2}&...\\...&...&...\end{pmatrix}$

Hessian
$\frac{\partial^2f}{\partial x_j \partial x_k}=\Sigma_i(2\frac{\partial r_i}{\partial x_j}\frac{\partial r_i}{\partial x_k} + 2r_i \frac{\partial^2 r_i}{\partial x_j \partial x_k})$ 이므로,
$\nabla^2f=2J_r^TJ_r+2Q$
where $Q=\Sigma_ir_i\nabla^2r_i$

$Q$ 텀을 무시하면 $H=\nabla^2f\approx 2J_r^TJ_r$ 즉, cost function의 Hessian에 대한 근사값을 얻었다.

Result

기존의 Newton-Raphson의 결과는 아래와 같다.
$x_{k+1}=x_k-H(x_k)^{-1}J(x_k)$

residual을 이용해 표현하면,
$x_{k+1}=x_k-(2J_r^TJ_r+2Q)^{-1}*2 *J_r^Tr$

Q를 생략하고 2를 약분하면 아래 식을 얻는다.
Gauss-Newton : $x_{k+1}=x_k-(J_r^TJ_r)^{-1}J_r^Tr(x_k)$

Levenberg-Marquardt

state가 minimum에 가까워지면 $J$ 또는 $J_r$이 0에 가까워진다.(singular)
그러면 Gauss-Newton 식에서 $(J_r^TJ_r)^{-1}$은 값이 발산할 수 있는 위험이 있다.
따라서, $\mu_kI$ 텀을 추가해 minimum에 멀 때는 Gauss-Newton, 가까울 때는 Gradient Descent와 유사하게 동작하도록 개선한 것이 Levenberg method이다.
Levenberg : $x_{k+1}=x_k-(J_r^TJ_r+\mu_kI)^{-1}J_r^Tr(x_k)$

Levenberg method의 수렴 속도를 개선한 것이 Levenberg-Marquardt method이고 식은 아래와 같다.
Levenberg-Marquardt : $x_{k+1}=x_k-(J_r^TJ_r+\mu_kdiag(J_r^TJ_r))^{-1}J_r^Tr(x_k)$

Weighted least squares

residual마다 가중치를 이용해 중요도를 반영시킬 수 있다.

cost function : $f(x)=\Sigma w_ir_i(x)^2=r^TWr$
where $W=diag(w_1,w_2,...)$

이 경우 weighted LM은 아래와 같다.
Weighted LM : $x_{k+1}=x_k-(J_r^TWJ_r+\mu_kdiag(J_r^TWJ_r))^{-1}J_r^TWr(x_k)$