Slam 2강 (Least Squares - An Informal Introduction) 요약

Cyrill 교수님의 SLAM 강의를 듣고 정리해보자!

0. Today’s Goal

• Least Squares란?
• Gauss-Newton Method
• Least Squares와 Probabilistic State Estimation의 관계

1. 강의 및 강의 자료

강의 List는 SLAM KR의 SLAM DUNK seson 2에서 정해준 강의를 따라 정리를 할 것이다.

SLAM DUNK season 2의 Reference는 여기서 확인해 볼 수 있다.

SLAM KR에서 이 강의를 듣고 요약을 세미나 형식으로 준비를 해준다!

이번 포스팅은 다음의 강의들을 참고하여 요약을 해보았다.

• Least Squares - An Informal Introduction (Cyrill Stachniss)
• SLAM DUNK Season 2 - An Informal Introduction to Least Squares

Cyrill Stachniss의 강의 자료는 pdf로 다운 받을 수 있다.

2. Least Squares란?

Least Squares란 무엇일까?

우리가 배우는 SLAM system은 “Graph-based SLAM system” 인데,
SLAM system 중 backend에서 최적화를 수행하는 도구로 사용하는 것이 Least Squares이다.

좀 더 일반적인 관점에서 Least Squares를 정의하자면,

우리가 어떤 식에서 구해야 할 parameter보다 더 많은 관찰값(Observations)가 존재할 때, 그 관찰값들은 매번 Noise가 존재할 수 있다. 이런 경우 정확한 parameter값을 구하는데 error가 최소화되도록 구하는 방법이다. 그 error는 보통 관찰값과 추정값의 제곱으로 표현한다.

다시 말하면, 어떤 식에서 구해야할 parameter가 4개일 때, 이 parameter를 구하기 위해 실험을 진행할 것이고, 이 때 실험을 5번 진행되어 관찰되는 값이 parameter보다 많을 때 정확한 parameter 값을 구하기 위하여 사용하는 최적화 방법이 바로 Least Squares 이다.

Least Squares에 대한 자세한 설명이 필요하다면 최소자승법 이해와 다양한 활용예 (Least Square Method) - 다크프로그래머 포스팅을 참고하면 될 것이다.

Least Squares는 선형화를 가정하여 error의 최소화를 구하는 방법인데,
만약 Non-linear한 모델일 경우, 사용하는 방법 중 하나가 Gauss-Newton Method이다.

그럼 강의에서는 Least Squares의 예를 어떻게 들었는지 Least Squqres를 통해 구하려는 것이 무엇인지 또한 필요한 가정에는 어떤 것이 있는지 설명을 해보도록 하겠다.

위 강의 자료를 통해 알 수 있듯이, Observation function $ {f_i (x)}_{i=1:n} $ 이라고 주어졌을 때,

$z_{1:n}$ 에는 Noise가 존재하고, 최종적으로 $x$ 의 상태를 추정하는 것이 목표이다.

Least Squqres에서는 error의 값을 예측값과 관찰값의 차이의 제곱으로 설정을 한다.

이 예제에서는 $i$번째 관찰을 했을 때 예측값이 $\hat{z_i} = f_i (x)$ 그리고 실제 관찰값이 $z_i$이므로 이 두 값의 차에 의해 Error function을 만들 수 있다.

따라서 error function은 $e_i(x) = z_i - f_i (x)$ 로 쓸 수 있고, 이 때 $e_i(x)$ 는 Vector 이다.

좌측에 있는 $e_i (x)$의 경우 Scalar 값 으로 $i$번째 error function의 값이고,
우측에 있는 $e_i (x)$의 경우 이전에 정의한 Vector 값 이다.

위 식에서 $\Omega_i$는 information matrix를 표현한 것인데, 관찰 값에도 노이즈가 존재하여 이를 평균이 0이고, 정규 분포를 따르는 가우시안 확률로 error가 있다고 가정하기 때문에 이를 표현하기 위해서다.

Information matrix 같은 경우, Heteroskedasticity (이분산성)이다.
쉽게 말해, SLAM system에서 여러 개의 sensor를 사용하는데, sensor간에 영향을 안준다고 가정하고 각각 센서마다 서로 다른 독립적인 분산을 따른다는 의미이다.

Error function을 이용해 우리가 구해야 할 것은 error를 최소화 하는 x 값 이다.

아래의 식에서는 $x^{*}$ 라고 표현했다.

argmin을 구할 때는 수식적인 방법으로 Iterative하게 접근을 하여 구한다.

단, 이 과정으로 최적의 해를 찾을 때는 중요한 가정 (Assumption) 이 존재한다.

• 초기에 setting한 값이 좋은 값이라는 가정
• Error function을 이용하여 반드시 최적의 해를 찾는 것은 아니므로, 이를 이용하면 Global minima를 구할 수 있다는 믿음

그렇다면 지금까지 구한 식을 이용하여 어떻게 최적의 state $x^{*}$ 를 찾을 수 있는지 그 중 한가지 방법인 Gauss-Newton method에 대해서 알아보자.

3. Gauss-Newton Method

Gauss-Newton Method는 앞서 설명했다시피 Non-linear한 모델에서 최적의 Parameter를 구하는 방법 중 하나이다.

위 예제에서 Gauss-Newton Method의 전체적인 과정은 다음과 같다.

1. Taylor 급수와 전개를 활용하여 Non-linear한 식을 Linear하게 만든다.
2. Squared Error이기 때문에 식을 정리하면 이차 식(Qudaratoc Form)이 나오는데,
   최솟값을 찾기 위해 편미분을 한다.
3. 편미분을 통해 구한 새로운 x값을 구한다.
4. 새로운 x값을 이용하여 초기값을 다시 구한다.
5. 최적의 해를 구할 때까지 반복한다.

강의 자료에 식을 풀어서 잘 설명해 놓았기 때문에 이를 활용해보겠다.

3-1. Error Function 선형화

이전에 구했던 $e_i(x) = e_i (x + \Delta x) $ 로 다시 식을 쓴다.
이 때 $x$는 상수로 취급하고 변화량 ($\Delta x$)만 변수로 취급한다.

강의 슬라이드에 식을 가져와보면

다시 풀어 쓴 식은 다음과 같다.

모든 $i$ 에 대해서 Error를 구하고 그 합을 통해 Global Error를 구한다.

3-2. 이차식 편미분

행렬의 편미분이 살짝 어렵게 느껴질 수도 있는데 아래 강의 슬라이드를 참고하면 쉽게 이해할 수 있다.

3-3 편미분 식을 활용한 새로운 x 찾기

고등학교, 아니 중학교에서 볼 법한 식이다. 미분 값이 0이 되는 x 값을 찾으면 된다.

단, 모든 식이 행렬이라는 것에 주의하자.

3-4 새로운 x를 이용한 Initial State Update

반복을 하기 전에 새로 찾은 값인 $\Delta x^{*}$ 를 이용하여 새로운 Inital State 값을 찾자.

기존의 $x$ (Old initial guess) 대신 새로운 $x = x + \Delta x^{*}$ 를 구하자.

그리고 구한 x 값을 이용하여 3-1 ~ 3-4 과정을 반복 하여 최적의 State $x$ 를 찾는다.

3-5. Linear System 효과적으로 풀기

3-3 과정에서 Linear system을 풀 때, 보통 역행렬을 구해서 $\Delta x^{*}$ 를 구하려고 하기 마련이다.

실제로 역행렬을 구하려고 할 때, 조금 더 효율적으로 구하기 위해 Cholesky factorization을 여기서 알려준다.

행렬 $A$ 에 대해 $Ax = b$ 를 구할 때, $A = LL^{T}$ 로 분해하여 구하면 조금 더 수월하게 답을 찾을 수 있다.
여기서, $L$은 하삼각행렬이다.

지금까지 정리한 Gauss-Newton 방법을 한 슬라이드로 정리하면 다음과 같다.

4. Least Squares와 Probabilistic State Estimation의 관계

결론적으로 말하면 Least Squares를 활용하여 해를 구하는 방법과 Probabilistic State Estimation을 활용하여 해를 구하는 방법 모두 같은 해를 구하는 방법이다.

State Estimation을 할 때, Bayes Rule을 적용하고 Markov assumtion을 따른다고 가정한다.
구한 식을 Log likelihood를 이용한다. 이 때 확률 값은 모두 가우시안 분포를 가정한다면, Maximum likelihood를 구하는 것과 Squared Error를 Minimize하는 방법은 결국 같다.

---

이렇게 Least Squqres에 대한 포스팅을 마무리 해보겠다. SLAM system 뿐만 아니라 다른 공학적인 문제에서도 유용하게 사용하는 방법이니 잘 알아두면 좋을 것 같다.