Published on

Gauss-Newton Method 정리

Authors
  • avatar
    Name
    Indo Yoon
    Twitter
Table of Contents

이 문서는 아직 작성 중입니다.

Nonlinear least squares

주어진 문제

minimize:

g(x)=i=1mfi(x)2=f(x)22g(x)=\sum_{i=1}^m{f_i(x)^2}=||f(x)||^2_2

f:RnRmf:R^n\rarr R^m가 미분가능한 n-벡터 xkx_k로 이루어진 함수

f(x)=(f1(x),,fm(x))f(x)=(f_1(x), \cdots, f_m(x))

일반적으로 Non-convex 최적화 문제이다.

선형 least-square 문제는 Ax=bAx=b 문제의 특수한 경우이다.

x=(ATA)1ATbx=(A^TA)^{-1}A^Tb

Gauss-Raphson

Gauss-Newton

관측값 : (xi,yi), i=1,,n(x_i, y_i), \ i=1,\cdots,n

모델 파라미터 : p=(p1,p2,,p,)p=(p_1, p_2, \cdots, p_,)

모델 : y=f(x,p)y=f(x,p)

Residual : ri(p)=yif(xi,p)r_i(p)=y_i-f(x_i,p)

Target function

E(p)=i=1nri(p)2=[r1(p)rn(p)][r1(p)rn(p)]=rTrE(p)=\sum_{i=1}^{n}r_i(p)^2=\begin{bmatrix}r_1(p) & \cdots & r_n(p)\end{bmatrix} \begin{bmatrix} r_1(p) \\\\\\ \cdots\\\\\\ r_n(p)\end{bmatrix}=r^Tr

이때 Target function을 최소화하는 해는 초기값 p0p_0에서부터 시작해 반복 갱신을 통해 얻을 수 있다. 초기값으로부터 다음 step의 p값을 얻는 수식은

pk+1=pk(JrTJr)1JTrp_{k+1}=p_k-(J^T_rJ_r)^{-1}J^Tr

이때 rr은 Residual, JJrr의 Jacobian이다. 따라서 다음 step의 pp는 이전 스텝에서

r=Jδr=J\delta

를 만족하는 δ\delta를 만큼 이동한 것과 동일하다. 위의 업데이트 식은 사실 Gradient descent의

xk+1=xkλrx_{k+1}=x_k-\lambda r

와 동일하다는 것을 알 수 있다. 이때 Jacobian은

J=[r1(p)p1r1(p)pmrn(p)p1rn(p)pm]J=\begin{bmatrix} \dfrac{\partial r_1(p)}{\partial p_1} & \cdots & \dfrac{\partial r_1(p)}{\partial p_m} \\\\\\ \vdots & \ddots & \vdots \\\\\\ \dfrac{\partial r_n(p)}{\partial p_1} & \cdots & \dfrac{\partial r_n(p)}{\partial p_m} \end{bmatrix}

와 같이 계산된다.

만일 Weighted least-square를 구해야 한다면

pk+1=pk(JrTWJr)1JTWrp_{k+1}=p_k-(J^T_rWJ_r)^{-1}J^TWr

와 같이 풀 수 있다.

우리가 풀고자 하는 문제는 어떤 파라미터가 포함된 Residual vector의 Squared-sum, 즉 Target function을 최소화하는 것이다. 이를 위해서는 초기값이 필요하고 이를 이용해 특정 포인트 근방에서 Target function을 선형화한다. 선형화된 식을 이용해 Least-square를 풀어 step size를 구한다. 그리고 step만큼 이동하며 Local minima를 찾아가는 과정이 바로 Gauss-Newton 방법의 아이디어인 것이다.

Reference