Gauss-Newton Method

Gauss-Newton Method

Gauss-Newton Method 정의

• Gauss-Newton은 뉴턴법(Newton’s Method)의 변형으로, 비선형 최소제곱 문제(Non-Linear Least Squares) 를 해결하기 위한 반복적 최적화 방법이다.
• 모델이 데이터에 얼마나 잘 맞는지 측정하는 잔차(Residuals)의 제곱합을 최소화하는 파라미터를 찾는 데 사용되며, 뉴턴법과 달리 Hessian을 직접 계산하는 대신 Jacobian을 사용하여 근사함으로써 계산 비용을 줄인다.
• 뉴턴법에서는 목적 함수 $f(\mathbf{x})$ 자체를 2차 테일러 급수로 근사하지만, 가우스-뉴턴에서는 목적 함수가 $||\mathbf{r}(\mathbf{\beta })|{|}^2$와 같은 잔차 제곱합 형태일 때, 뉴턴법의 아이디어를 적용하되, 잔차 함수 $\mathbf{r}(\mathbf{\beta })$를 선형 근사하는 것이 더 효율적이라는 접근이다.
• Least Squares 문제는 $n$개의 변수 $\mathbf{\beta }=({\beta }_1,{\beta }_2,\dots ,{\beta }_n)$와 $m$개의 데이터에 대한 잔차 벡터가 $\mathbf{r}=(r_1,r_2,\dots ,r_m)$ 일 때, 잔차의 제곱합을 최소화하는 $\mathbf{\beta }$를 찾는다.

$$\underset{\beta }{\min }\sum _{i=1}^m{r}_i(\mathbf{\beta }{)}^2=\underset{\beta }{\min }||\mathbf{r}(\mathbf{\beta })|{|}^2$$

Non-Linear Least Squares

• Least Squares 문제는 모델이 예측한 값과 실제 관측값의 차이인 Residual의 제곱합을 최소화하는 것 이다.
• Linear Least Squares는 Residual이 최적화 변수에 $\theta$ 에대해 선형인 문제이며 다음과 같다.

$$\underset{\theta }{\min }||\mathbf{r}(\theta )|{|}^2,\mathbf{r}=\mathbf{y}-\mathbf{X}\theta$$ $$\mathbf{y}\approx X\theta$$

• 이러한 Linear Least Squares 는 정규 방정식(Normal Equation) 등의 방법으로 최적 파라미터를 계산할 수 있다.

$$X^{T}X\theta =X^T\mathbf{y}$$ $$\theta =(X^{T}X{)}^{-1}{X}^T\mathbf{y}$$

• Non-Linear Least Squares는 Residual이 최적화 변수 $\theta$ 에 대해 비선형인 문제이다.
• 잔차 제곱합의 형태는 동일하지만 잔차 함수, 즉 구하고자 하는 함수 또는 Fitting하고자 하는 함수의 형태가 비선형인 경우를 말한다.

$$\underset{\theta }{\min }||\mathbf{r}(\theta )|{|}^2,\mathbf{r}=\text{Non-Linear Function}$$

• 예를 들어, 아래 지수함수의 최적 파라미터를 구하는 Least Squares는 다음과 같다.

$${\hat{y}}_i=a{e}^{b{x}_i}$$ $$r_i=y-a{e}^{b{x}_i},\theta =\left[\begin{array}{c}a\\ b\end{array}\right]$$ $$\underset{\theta }{\min }\sum _{i=1}^m(y-a{e}^{b{x}_i}{)}^2$$

• Gauss-Newton Method는 이러한 Non-Linear Least Squares를 반복적 계산을 통해 최적해를 구하는 방법이다.

---

Gauss-Newton Method 방법

목적함수와 잔차함수의 정의

• Non-Linear Least Squares 문제는 잔차들의 제곱합을 최소화하는 파라미터 $\beta$를 찾는 것이며 따라서, 목적함수는 다음과 같다.

$$\underset{\mathbf{\beta }}{\min }\sum _{i=1}^m{r}_i(\mathbf{\beta }{)}^2=\underset{\mathbf{\beta }}{\min }||\mathbf{r}(\mathbf{\beta })|{|}^2$$

• 여기서 $\mathbf{r}(\mathbf{\beta })$는 잔차 벡터이며, $m$개의 데이터에 대한 잔차 벡터는 다음과 같다.

$$\mathbf{r}(\mathbf{\beta })=\left[\begin{array}{c}{r}_1(\beta )\\ r_2(\beta )\\ ⋮\\ r_m(\beta )\end{array}\right]$$

• 잔차함수 $r_i(\mathbf{\beta })$는 다음과 같이 정의된다.

$$r_i(\mathbf{\beta })=f(x_i,\mathbf{\beta })-y_i$$

• 여기서 $f(x_i,\mathbf{\beta })$는 비선형이라 가정하며, $f(x_i,\mathbf{\beta })$가 비선형이라면 잔차 함수 $r_i(\mathbf{\beta })$ 역시 비선형이 된다.
• 이처럼 잔차 함수가 비선형이기 때문에, 잔차의 제곱합을 최소화하는 문제에서는 Least Square Method에서 사용되는 정규방정식처럼 직접적인 대수적 해를 구할 수 없다.

현재 추정값과 업데이트량 정의

• 현재 파라미터 추정값을 ${\mathbf{\beta }}_k$라고 할 때, 다음 스텝으로 이동할 변화량을 $\Delta \mathbf{\beta }$라고 할 수 있다.
• 다음 스텝의 파라미터 ${\mathbf{\beta }}_{k+1}$은 다음과 같이 표현할 수 있다.

$${\mathbf{\beta }}_{k+1}={\mathbf{\beta }}_k+\Delta \mathbf{\beta }$$

• Gauss-Newton Method는 반복적으로 $\Delta \beta$를 계산하고 파라미터를 업데이트해 나간다.

잔차 함수의 선형 근사

• Gauss-Newton Method는 현재 파라미터 추정치 ${\mathbf{\beta }}_k$에서 잔차 함수 $\mathbf{r}(\mathbf{\beta })$를 테일러 급수 (Taylor series)의 1차 항까지 선형 근사한다.
• 일변수 스칼라 함수 $f(x)$의 $x_k$ 위치에서 1차 테일러 전개의 표준은 다음과 같다.

$$f(x)\approx f(x_k)+f^{\prime }(x_k)(x-x_k)$$

• 이 테일러 전개를 현재점($x_k$) + 변화량($\Delta x$) 로 나타내면 아래와 같다.

$$\Delta x=x-x_k$$ $$f(x_k+\Delta x)\approx f(x_k)+f^{\prime }(x_k)\Delta x$$

• 즉, 현재 위치에서 $\Delta x$ 만큼 이동 했을 때의 변화량은 기울기 $f^{\prime }(x_k)$에 이동량 $\Delta x$를 곱한 것 정도로 본다.
• 현재 추정값에서 조금 이동한 ${\mathbf{\beta }}_k+\Delta \mathbf{\beta }$ 에서 잔차의 각 성분에 대해 1차 테일러 전개를 적용하면 다음과 같다.

$$r_i({\mathbf{\beta }}_k+\Delta \mathbf{\beta })\approx r_i({\mathbf{\beta }}_k)+\sum _{j=1}^n\frac{\partial r_i}{\partial {\beta }_j}\Delta {\beta }_j$$

• 여기서 두 번째 항은 다변수 함수의 테일러 전개의 일반화 형태이며 파라미터 벡터 $\mathbf{\beta }$ 의 각 요소 ${\beta }_j$에 대한 편미분을 모두 고려해야 한다.
• 이 식을 벡터 형태로 정리하면 다음과 같다.

$$\mathbf{r}({\mathbf{\beta }}_k+\Delta \mathbf{\beta })\approx \mathbf{r}({\mathbf{\beta }}_k)+J_k\Delta \mathbf{\beta }$$ $$\mathbf{r}(\mathbf{\beta })\approx \mathbf{r}({\mathbf{\beta }}_k)+J_k(\mathbf{\beta }-{\mathbf{\beta }}_k)$$ $$\mathbf{r}(\mathbf{\beta })\approx \mathbf{r}({\mathbf{\beta }}_k)+J_k\Delta \mathbf{\beta }$$

• 위 식들은 모두 같은 의미를 가지며, 현재 파라미터 ${\mathbf{\beta }}_k$에서 $\Delta \mathbf{\beta }$만큼 이동했을 때의 잔차를 계산하는 것이다.

Jacobian의 활용

• 잔차 함수를 1차 테일러 전개로 근사한 식에서 Jacobian은 잔차 벡터 $\mathbf{r}$을 파라미터 벡터 ${\mathbf{\beta }}_k$ 에 대해 미분한 행렬이다.

$$\mathbf{r}({\mathbf{\beta }}_k+\Delta \mathbf{\beta })\approx \mathbf{r}({\mathbf{\beta }}_k)+J_k\Delta \mathbf{\beta }$$ $$J({\mathbf{\beta }}_k)=J_k=\left[\begin{array}{cccc}\frac{\partial r_1}{\partial {\beta }_k^1}& \frac{\partial r_1}{\partial {\beta }_k^2}& \cdots & \frac{\partial r_1}{\partial {\beta }_k^n}\\ \frac{\partial r_2}{\partial {\beta }_k^1}& \frac{\partial r_2}{\partial {\beta }_k^2}& \cdots & \frac{\partial r_2}{\partial {\beta }_k^n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial r_m}{\partial {\beta }_k^1}& \frac{\partial r_m}{\partial {\beta }_k^2}& \cdots & \frac{\partial r_m}{\partial {\beta }_k^n}\end{array}\right]$$

• 데이터 수 : $m$
• 파라미터 수 : $n$
• 파라미터 벡터 : $\mathbf{\beta }=[{\beta }_1,{\beta }_2,\dots ,{\beta }_n{]}^T$
• 잔차 함수 : $r_i(\mathbf{\beta })=y_i-f(x_i,\mathbf{\beta })$
• 잔차 벡터 : $\mathbf{r}(\mathbf{\beta })=[r_1(\mathbf{\beta }),r_2(\mathbf{\beta }),\dots ,r_m(\mathbf{\beta }){]}^T$

선형 최소제곱 문제로의 변환

• 목표는 목적 함수 $||\mathbf{r}(\mathbf{\beta })|{|}^2$을 최소화하는 $\mathbf{\beta }$를 찾는 것이며, 현재 반복 단계 $k$에서 ${\mathbf{\beta }}_k$를 기준으로 잔차 함수를 선형 근사했으므로, 이제 이 선형 근사된 잔차 벡터의 제곱합을 최소화하는 $\Delta \mathbf{\beta }$를 찾아야 한다.
• 목적 함수에 현재 파라미터 ${\mathbf{\beta }}_k$에 대한 근사 식을 대입하면 다음과 같다. 편의상 $\mathbf{r}({\mathbf{\beta }}_k)$를 ${\mathbf{r}}_k$라고 한다.

$$S(\Delta \mathbf{\beta })=||{\mathbf{r}}_k+J_k\Delta \mathbf{\beta }|{|}^2$$

• 이 식은 선형 최소제곱 문제와 같은 형태이며, 선형 최소 제곱문제는 정규방정식(Normal Equation)을 통해 직접 구할 수 있다.
• 선형 최소제곱인 $||A\mathbf{x}-b|{|}^2$ 이 최소가되는 $\mathbf{x}$를 구하는 정규방정식은 다음과 같다.

$$A^{T}A\mathbf{x}=A^{T}b$$

• 정규방정식을 이용해 $||{\mathbf{r}}_k+J_k\Delta \mathbf{\beta }|{|}^2$ 가 최소가 되는 $\Delta \mathbf{\beta }$ 에 대한 표현은 다음과 같다.

$${J_k}^T{J}_k\Delta \mathbf{\beta }=-{J_k}^T{\mathbf{r}}_k$$

• 이 식이 Gauss-Newton의 정규방정식이 된다.

파라미터 업데이트

• 다음 스텝의 파라미터 ${\mathbf{\beta }}_{k+1}$는 현재 스텝의 파라미터와 파라미터 변화량을 더한 ${\mathbf{\beta }}_k+\Delta \mathbf{\beta }$ 로 표현할 수 있다.
• 정규방정식을 $\Delta \mathbf{\beta }$에 대해 정리하면 다음과 같다.

$$\Delta \mathbf{\beta }=-({J_k}^T{J}_k{)}^{-1}{J_k}^T{\mathbf{r}}_k$$

• 다음 스텝 파라미터의 최종 업데이트 식은 다음과 같다.

$${\mathbf{\beta }}_{k+1}={\mathbf{\beta }}_k-({J_k}^T{J}_k{)}^{-1}{J_k}^T{\mathbf{r}}_k$$

• 여기서, 실제 계산에서는 $({J_k}^T{J}_k{)}^{-1}$ 를 직접 계산하지 않고, QR 분해나 Cholesky 분해 등의 선형 시트템 풀이 방법을 사용한다.

---

Gauss-Newton을 이용한 Circle Fitting 예시

문제 정의

• 다음 5개의 데이터 $(x,y)$가 주어지고, 이 점들을 가장 잘 설명하는 원 방정식의 파라미터 $\mathbf{\beta }$를 구한다.

$$(8,5),(5,8),(2,5),(5,2),(7,7)$$

• 중심이 $(a,b)$이고 반지름이 $R$인 원의 방정식은 다음과 같다.

$$(x-a{)}^2+(y-b{)}^2=R^2$$

잔차함수 정의

• 원의 방정식은 $y=f(x,\beta )$ 형태가 아니기 때문에, 원의 방정식 자체를 0으로 만드는 형태로 잔차함수를 정의하여 Gauss-Newton 을 적용할 수 있다.
• 만약 데이터 포인트 $(x_i,y_i)$가 완벽하게 원 위에 있다면 다음 식이 성립해야 한다.

$$(x-a{)}^2+(y-b{)}^2-R^2=0$$

• 따라서 잔차함수 $r_i(\mathbf{\beta })$를 다음과 같이 나타내면 이 잔차는 $i$번째 데이터 포인트가 현재 파라미터 $\mathbf{\beta }$로 정의된 원의 방정식으로부터 얼마나 벗어나 있는지를 나타낸다.

$$r_i(\mathbf{\beta })=(x_i-a{)}^2+(y_i-b{)}^2-R^2$$

• 이때, 파라미터 벡터 $\mathbf{\beta }$ 와 잔차 벡터 $\mathbf{r}$은 다음과 같다.

$$\mathbf{\beta }=\left[\begin{array}{c}a\\ b\\ R\end{array}\right],\mathbf{r}(\mathbf{\beta })=\left[\begin{array}{c}{r}_1(\mathbf{\beta })\\ r_2(\mathbf{\beta })\\ r_3(\mathbf{\beta })\\ r_4(\mathbf{\beta })\\ r_5(\mathbf{\beta })\end{array}\right]$$

• 잔차 벡터의 제곱합을 최소화하기 위한 목적함수는 다음과 같다.

$$||\mathbf{r}(\mathbf{\beta })|{|}^2=\sum _{i=1}^5{r}_i(\mathbf{\beta }{)}^2$$

Jacobian 계산

• Jacobian은 잔차 벡터를 파라미터 벡터에 대해 미분한 행렬이므로, 잔차 5개 x 파라미터 3개로 $J_{5\times 3}$은 다음과 같다.

$$J_{5\times 3}(\mathbf{\beta })=\left[\begin{array}{ccc}\frac{\partial r_1}{\partial a}& \frac{\partial r_1}{\partial b}& \frac{\partial r_1}{\partial R}\\ \frac{\partial r_2}{\partial a}& \frac{\partial r_2}{\partial b}& \frac{\partial r_2}{\partial R}\\ ⋮& ⋮& ⋮\\ \frac{\partial r_5}{\partial a}& \frac{\partial r_5}{\partial b}& \frac{\partial r_5}{\partial R}\end{array}\right]$$

• 잔차함수를 $a,b,R$ 에 대해 각각 편미분한 것은 다음과 같다.

$$\frac{\partial r_i}{\partial a}=2(a-x_i)$$ $$\frac{\partial r_i}{\partial b}=2(b-x_i)$$ $$\frac{\partial r_i}{\partial R}=-2R$$

• 따라서, 전체 Jacobian은 다음과 같이 정리된다.

$$J(\mathbf{\beta })=\left[\begin{array}{ccc}2(a-x_1)& 2(b-x_1)& -2R\\ 2(a-x_2)& 2(b-x_2)& -2R\\ 2(a-x_3)& 2(b-x_3)& -2R\\ 2(a-x_4)& 2(b-x_4)& -2R\\ 2(a-x_5)& 2(b-x_5)& -2R\end{array}\right]$$

초기 파라미터 설정 및 계산

• 초기 파라미터 ${\mathbf{\beta }}_0$ 를 다음과 같이 설정한다.

$${\mathbf{\beta }}_0=\left[\begin{array}{c}6\\ 6\\ 5\end{array}\right]$$

• 즉, 초기 추정 원의 중심은 (6, 6)이고 반지름은 5이다.
• 초기 파라미터와 데이터를 이용해 대한 잔차 벡터를 계산하면 다음과 같다.

$$r_i=(x_i-6{)}^2+(y_i-6{)}^2-5^2$$ $$\mathbf{r}({\mathbf{\beta }}_0)=\left[\begin{array}{c}-20\\ -20\\ -8\\ -8\\ -23\end{array}\right]$$

• 초기 파라미터와 잔차 벡터에 대해 Jacobian을 계산하면 다음과 같다.

$$J({\mathbf{\beta }}_0)=\left[\begin{array}{ccc}2(6-x_1)& 2(6-x_1)& -10\\ 2(6-x_2)& 2(6-x_2)& -10\\ 2(6-x_3)& 2(6-x_3)& -10\\ 2(6-x_4)& 2(6-x_4)& -10\\ 2(6-x_5)& 2(6-x_5)& -10\end{array}\right]=\left[\begin{array}{ccc}-4& 2& -10\\ 2& -4& -10\\ 8& 2& -10\\ 2& 8& -10\\ -2& -2& -10\end{array}\right]$$

파라미터 업데이트

• Gauss-Newtom의 정규방정식을 이용해서 $\Delta {\mathbf{\beta }}_0$ 구하여 파라미터를 업데이트 한다.

$${J_0}^T{J}_0\Delta {\mathbf{\beta }}_0={-J_0}^T{\mathbf{r}}_0$$

• ${J_0}^T{J}_0$와 ${J_0}^T{\mathbf{r}}_0$을 계산하면 다음과 같다.

$${J_0}^T{J}_0=\left[\begin{array}{ccc}92& 20& -60\\ 20& 92& -60\\ -60& -60& 500\end{array}\right]$$ $${J_0}^T{\mathbf{r}}_0=\left[\begin{array}{c}6\\ 6\\ 790\end{array}\right]$$ $$\left[\begin{array}{ccc}92& 20& -60\\ 20& 92& -60\\ -60& -60& 500\end{array}\right]\Delta {\mathbf{\beta }}_0=\left[\begin{array}{c}-6\\ -6\\ -790\end{array}\right]$$

• 위 정규방정식을 연립방정식을 풀어 $\Delta {\mathbf{\beta }}_0$를 구하면 다음과 같다.

$$\Delta {\mathbf{\beta }}_0\approx \left[\begin{array}{c}-1.03\\ -1.03\\ -1.83\end{array}\right]$$

• 이 것을 이용하여 다음 스텝의 파라미터 ${\mathbf{\beta }}_1$을 구할 수 있다.

$${\mathbf{\beta }}_1={\mathbf{\beta }}_0+\Delta \mathbf{\beta }$$ $${\mathbf{\beta }}_1=\left[\begin{array}{c}4.97\\ 4.97\\ 3.17\end{array}\right]=\left[\begin{array}{c}6\\ 6\\ 5\end{array}\right]+\left[\begin{array}{c}-1.03\\ -1.03\\ -1.83\end{array}\right]$$

• 수렴 조건을 만족할 때 까지 이 과정을 반복하여 최적해에 접근하도록 업데이트 할 수 있다.
• 초기 파라미터 ${\mathbf{\beta }}_0$의 원과 한 번 업데이트한 ${\mathbf{\beta }}_1$의 원을 나타내면 다음과 같이 기존 데이터에 더 fitting됨을 알 수 있다.