[개념 정리] 가우스-뉴턴 (Gauss-Newton) 최적화 기법

개요

입력 데이터($x$)와 모델 매개변수($\beta$)에 관한 함수 $f(x,\beta)$에 대해 관측된 데이터($y$)간의 차이의 제곱을 최소화하는 문제(Nonlinear Least Squares Problem, 아래 수식)를 해결 할 때 사용하는 방법 중에 하나입니다.  $$ S(\beta) = \sum_{i=1}^n (y_i - f(x_i, \beta))^2 $$찾고자하는 값은 모델 매개변수 변화량($\Delta \beta$)입니다. $$ S(\beta + \Delta \beta) = \sum_{i=1}^n (y_i - f(x_i, \beta + \Delta \beta))^2 $$

Gauss-Newton은 $\Delta \beta$ 를 미분해서 극소값을 찾는 방식으로 해를 찾게됩니다.

 

 

언제 사용하는가?

비선형 최소 제곱 문제 솔루션은 Gauss-newton외에도 Gradient-Descent, Levenberg-Marquardt이 있습니다. 이 중 Gauss-newton은 모델 매개변수의 수가 적고, Jacobian을 쉽게 계산 할 수 있는 경우에 잘 작동합니다. 또한 미분을 2번 수행(=Jacobian을 2번 계산)하기 때문에, 최적값 근처에서 선형적인 성질을 보일 때(=비선형성이 강하지 않을 때) 효과적이고, 초기 추정값이 실제 최적값에 근접할 경우 효율적으로 작동합니다.

 

 

Gauss-Newton 알고리즘

위 수식을 풀기 위해, 테일러 확장(Taylor Expansion)의 1차식으로 선형 근사를 합니다. $$f(x, \beta + \Delta \beta) \approx f(x, \beta) + J_f(x, \beta) \Delta \beta$$ J는 Jacobian이며 다변수 함수에 대한 편미분 값을 나타냅니다.

추가로 $ r_i = y_i - f(x_i, \beta)$ 로 보기 좋게 정리해줍니다.  $$S(\beta + \Delta \beta) \approx \sum_{i=1}^n \left( y_i - (f(x_i, \beta) + J_i \Delta \beta) \right)^2$$ $$ \approx \sum_{i=1}^n \left( r_i - J_i \Delta \beta \right)^2 $$ $\Delta \beta$에 관한 극소값을 찾기 위해 $\Delta \beta$로 미분을 해서 0이 되도록 정리를 해줍니다. $$ \frac{\partial S(\beta + \Delta \beta)}{\partial \Delta \beta} = 2 ( -J^T ) (r - J \Delta \beta) = -2 J^T r + 2 J^T J \Delta \beta = 0 $$

T는 행렬의 Transpose로써 Summation을 행렬연산으로 바꿔주면서 생긴 기호입니다.  최종적으로 찾고자하는 $\Delta \beta$에 관한 수식으로 정리하자면, 아래 수식이 됩니다. $$ \Delta \beta = (J^T J)^{-1} J^T r $$

이 개념을 사용한 예시로는  Bundle Adjustment 가 있습니다. "Gauss-Newton" 키워드를 찾아서 아래 부분에 Jacobian matrix모양만 참고만 하시길 바랍니다.