Table of Contents 이 문서는 아직 작성 중입니다.
minimize:
g ( x ) = ∑ i = 1 m f i ( x ) 2 = ∣ ∣ f ( x ) ∣ ∣ 2 2 g(x)=\sum_{i=1}^m{f_i(x)^2}=||f(x)||^2_2 g ( x ) = i = 1 ∑ m f i ( x ) 2 = ∣∣ f ( x ) ∣ ∣ 2 2 f : R n → R m f:R^n\rarr R^m f : R n → R m 가 미분가능한 n-벡터 x k x_k x k 로 이루어진 함수
f ( x ) = ( f 1 ( x ) , ⋯ , f m ( x ) ) f(x)=(f_1(x), \cdots, f_m(x)) f ( x ) = ( f 1 ( x ) , ⋯ , f m ( x )) 일반적으로 Non-convex 최적화 문제이다.
선형 least-square 문제는 A x = b Ax=b A x = b 문제의 특수한 경우이다.
x = ( A T A ) − 1 A T b x=(A^TA)^{-1}A^Tb x = ( A T A ) − 1 A T b 관측값 : ( x i , y i ) , i = 1 , ⋯ , n (x_i, y_i), \ i=1,\cdots,n ( x i , y i ) , i = 1 , ⋯ , n
모델 파라미터 : p = ( p 1 , p 2 , ⋯ , p , ) p=(p_1, p_2, \cdots, p_,) p = ( p 1 , p 2 , ⋯ , p , )
모델 : y = f ( x , p ) y=f(x,p) y = f ( x , p )
Residual : r i ( p ) = y i − f ( x i , p ) r_i(p)=y_i-f(x_i,p) r i ( p ) = y i − f ( x i , p )
Target function
E ( p ) = ∑ i = 1 n r i ( p ) 2 = [ r 1 ( p ) ⋯ r n ( p ) ] [ r 1 ( p ) ⋯ r n ( p ) ] = r T r E(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 E ( p ) = i = 1 ∑ n r i ( p ) 2 = [ r 1 ( p ) ⋯ r n ( p ) ] r 1 ( p ) ⋯ r n ( p ) = r T r 이때 Target function을 최소화하는 해는 초기값 p 0 p_0 p 0 에서부터 시작해 반복 갱신을 통해 얻을 수 있다. 초기값으로부터 다음 step의 p값을 얻는 수식은
p k + 1 = p k − ( J r T J r ) − 1 J T r p_{k+1}=p_k-(J^T_rJ_r)^{-1}J^Tr p k + 1 = p k − ( J r T J r ) − 1 J T r 이때 r r r 은 Residual, J J J 는 r r r 의 Jacobian이다. 따라서 다음 step의 p p p 는 이전 스텝에서
r = J δ r=J\delta r = J δ 를 만족하는 δ \delta δ 를 만큼 이동한 것과 동일하다. 위의 업데이트 식은 사실 Gradient descent의
x k + 1 = x k − λ r x_{k+1}=x_k-\lambda r x k + 1 = x k − λ r 와 동일하다는 것을 알 수 있다. 이때 Jacobian은
J = [ ∂ r 1 ( p ) ∂ p 1 ⋯ ∂ r 1 ( p ) ∂ p m ⋮ ⋱ ⋮ ∂ r n ( p ) ∂ p 1 ⋯ ∂ r n ( p ) ∂ p m ] 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} J = ∂ p 1 ∂ r 1 ( p ) ⋮ ∂ p 1 ∂ r n ( p ) ⋯ ⋱ ⋯ ∂ p m ∂ r 1 ( p ) ⋮ ∂ p m ∂ r n ( p ) 와 같이 계산된다.
만일 Weighted least-square를 구해야 한다면
p k + 1 = p k − ( J r T W J r ) − 1 J T W r p_{k+1}=p_k-(J^T_rWJ_r)^{-1}J^TWr p k + 1 = p k − ( J r T W J r ) − 1 J T W r 와 같이 풀 수 있다.
우리가 풀고자 하는 문제는 어떤 파라미터가 포함된 Residual vector의 Squared-sum, 즉 Target function을 최소화하는 것이다. 이를 위해서는 초기값이 필요하고 이를 이용해 특정 포인트 근방에서 Target function을 선형화한다. 선형화된 식을 이용해 Least-square를 풀어 step size를 구한다. 그리고 step만큼 이동하며 Local minima를 찾아가는 과정이 바로 Gauss-Newton 방법의 아이디어인 것이다.