SLAM 비선형 최적화 기법

출처 : https://darkpgmr.tistory.com/142

함수최적화 기법 정리 (Levenberg–Marquardt 방법 등)

 

1. 최소자승법

관측값을 x, 모델 파라미터를 p, 모델을 y=f(x,p), 관측값과 모델의 오차를 r이라고 할 때,

오차 제곱합이 최소화 되도록 모델 파라미터 p를 정하는 방법을 최소자승법(least square method)이라 한다.

 

2. Gradient Descent

Gradient Descent 방법은 아래 식과 같이 어떤 초기값 x0으로부터 시작하여 

그레디언트의 반대 방향으로 계속 내려가다 보면 함수의 최소값을 찾을 수 있다는 방법이다.

 

* 어떤 다변수 함수의 그레디언트는

로 정의되며, 함수값이 가장 가파르게 증가하는 방향을 나타낸다

 

[ 최소자승 문제에의 적용 ]

r(x,p) = y-f(xp) 라하면 최소화시키고자 하는 목적함수는 다음과 같다.

따라서, 비선형 최소자승 문제에 대한 gradient descent의 해는 모델 파라미터 p에 대한 초기 추정값 p0에서 시작하여

p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다. (람다는 step size이다.)

 

아래의 참고 글에서 일차미분을 이용한 최적화에 해당한다.

https://darkpgmr.tistory.com/149

최적화 기법의 직관적 이해

 

3. 뉴턴법 

어떤 함수 E(x)=0의 해를 찾기 위해

임의의 초기값 x0으로부터 시작하여 다음 수식에 따라 x를 반복적으로 갱신함으로써 해를 찾아가는 방법니다.

 

그 원리는 미분이 접선의 기울기임을 이용하여 

현재의 x에서 E(x)의 부호와 기울기 E'(x)의 부호에 따라 x를  증가시킬지 감소시킬지를 결정하고

그 기울기의 크기에 따라서 x를 얼마나 많이 증가(감소)시킬지를 결정하는 방식이다.

 

만일 뉴턴법을 함수 E(x)의 최소(최대)값을 찾는 최적화 문제에 적용할 경우에는

다음과 같이 E'(x)=0의 해를 찾는 문제로 식을 변형하여 적용할 수 있다.

 

또한, 뉴턴법을 다변수 함수의 최적화 문제로 확장하면 식을 아래와 같이 수정하여 적용할 수 있다.

(단, H는 E''(x)로써 헤시안 값을 나타낸다.)

 

[최소자승 문제에의 적용]

뉴턴법의 식을 적용하면 비선형 최소자승 문제에 직접 적용하는 것도 가능은 하다.

하지만, E(p)에 두 번 미분해야 하는 부담이 존재한다.

따라서, 비선형 최소자승 문제의 경우에는 뉴턴법 대신에 일차 미분만으로 해의 계산이 가능한 가우스-뉴턴법이 사용된다.

 

아래의 참고 글에서 이차미분을 이용한 최적화에 해당한다.

https://darkpgmr.tistory.com/149

최적화 기법의 직관적 이해

 

 

 

4. 가우스-뉴턴법

뉴턴법의 변형된 형태로서 비선형 최소자승 문제에 대한 대표적인 최적화 방법 중 하나이다.

앞서 뉴턴법을 최적화 문제에 적용할 경우에는 2차 미분이 필요하지만,

가우스-뉴턴법을 이용하면 1차 미분만으로 해를 찾을 수 있다.

 

비선형 최소자승 문제에서의 E(p)의 정의이다.

 

이 때, E(p)를 최소화시키는 즉, E'(p)=0으로 만드는 가우스-뉴턴 해는 모델 파라미터 p에 대해

초기 추정값 p0에서 시작하여 p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다.

(JrTJr)-1JrT는 사실 Jr의 pseudo inverse이다. 따라서 식을 좀 더 간략히 표현하면 다음과 같다.

 

 

 

5. Levenberg-Marquardt 방법

LM 방법은 가우스-뉴턴과 gradient descent 방법이 결합된 형태로서

해로부터 멀리 떨어져 있을 떄는 gradient descent 방식으로 동작하고,

해 근처에서는 가우스-뉴턴 방식으로 해를 찾는다. 

 

빠른 비교 및 참조를 위해 지금까지 배운 방식들을 함께 적어보면 다음과 같다.

 

가우스-뉴턴법을 살펴보면 계산 과정에 (JrT Jr)의 역행렬 계산을 필요로 한다.

따라서 (JrT Jr)가 singular 행렬(역행렬이 존재하지 않는 행렬)에 근접한 경우에는 계산된 역행렬이 수치적으로 불안정하여 해가 발산할 수 있는 문제점이 있다.

 

Levenberg 방법은 가우스-뉴턴법을 개선하여 JrTJr에 항등행렬의 상수배 ml을 더함으로써 발산의 위험을 낮추고 보다 안정적으로 해를 찾을 수 있도록 한 방법이다.

상수 m(m>0)을 damping factor라 부르는데, m값이 작으면 Levenberg 방법은 가우스-뉴턴법과 유사해지고, m값이 크면 gradient descent 방법과 유사해진다. 

그런데, damping factor m은 고정된 값이 아니라 매 iteration마다 바뀌는 값으로서 현재 안정적으로 해에 수렴하고 있을 경우에는

작은 값을 주고 해를 잘 찾지 못하고 있을 경우에는 큰 값을 주는 방법을 사용한다.

 

Levenberg-Marquardt 방법은 기존의 Levenberg의 방법을 Marquadt가 좀 더 개선시킨 방법을 말한다.

원래의 Levenberg 방법은 m이 큰 경우에 step size가 1/m인 gradient descent 방법과 유사해짐은 앞서 설명한 바 있다.

하지만, 이 경우 수렴 속도가 느린 문제점이 있다. Marquardt는 이러한 문제를 보완하기 위해 항등행렬 I 대신에 diag(JrTJr)을 더해주는 방식을 제안하였다. (diag(A)는 A의 대각원소는 유지하고, 나머지 원소들의 값을 0으로 만든 대각행렬을 나타냄)

JrTJr은 원래 헤시안에 대한 근사행렬의 의미를 갖기 때문에 JrTJr의 대각 원소들은 각 파라미터 성분(pi)에 대한 곡률을 나타낸다.

즉, Levenberg-Marquardt 방법은 가우스-뉴턴법의 singular 문제를 피하면서도 m이 큰 경우에도 곡률을 반영하여 효과적으로 해를 찾을 수 있도록 한 방법이다.