집밖은 위험해

LM 방법

- LM 방법은 레벤버그, 마퀴트가 제안한 감쇄 가우스 뉴턴 방법

- 컴퓨터 비전에서 번들 조정 bundle adjustment에서 주로 사용

- 방향 벡터 h_lm을 구하기 위해 가우스 뉴턴 방법에 감쇄 인자를 추가함

LM 방법에서 방향 벡터 h_lm

- 위 감쇄 인자가 추가된 식을 정리하면

- 감쇄인자 mu가 큰 경우

- 감쇄 인자 mu가 작은 경우

- mu를 조절하기 위해 이득 비율을 이용

LM 방법에서의 정지 조건

가우스 뉴턴 방법 개요

- 비선형 최소 자승법으로 근사 해를 구하기 위해 레벤버그-마퀴트 뉴턴 방법. 즉 LM 방법을 사용할 예정

- LM 방법은 가우스 뉴턴 방법을 기반으로 함

- 가우스 뉴턴 방법은 테일러 전개 2차식에서 시작

자코비안과 그라디언트, 헤시안

- 자코비안의 요소들은 함수 f의 미분들

- 함수 F의 그라디언트

- 함수 F의 헤시안

가우스-뉴턴 방법

- 함수 f(x + h)를 l(h)로 근사화 하면

- F(x+h)에 대한 근사식은 아래와 같다.

- L(h)를 정리하면

- L(h)가 최소가 되는 h를 구하기 위해

- 이 식을 정리하면 가우스 뉴턴 알고리즘을 정리 할 수 있다.

근사해 구하기

- 다음의 다변수 함수 f와 해 q가 주어질때, 근사해 x를 구해야함

제곱의 사용

- ||f(x)||는 미분 시 잘못될수 있으므로 ||f(x)||의 제곱을 주로 사용

- 다음의 식을 주로 사용

비선형 최소자승법

- 다음의 식 F(x)을 최소로 하는 근사해 x*를 구하는 방법

 => 최소자를 구하기 위해 경사 하강법이나 뉴턴 방법이 사용됨

비선형 최소자승법 non-linear least squares 개요

- 앞서 살펴본 경사 하강법과 뉴턴 방법의 함수는 다음과 같음

- 아래의 함수 f인 다변수 함수에서는 어떻게 최소자로 찾아갈까?

다변수 함수 지역선형성 local linear

- 다음의 다변수 함수가 있을때

- 미분 가능 함수는 지역 선형으로, 자코비안 J(x)와 극소 증감벡터 h가 주어질때 아래와 같다.

국소 증감 벡터 h에 대한 식으로 정리하기

- 초기값 x0, 종료조건 eta0 등 아래의 조건이 주어질때

- h에 대해 정리하면

 => 정규 방정식 normal equation으로 구할 수 있음

정규 방정식으로 선형 최소 자승 구하기

- 선형 시스템 Ax = b가 주어질때 ||Ax - b||를 최소로 하는 벡터 x를 구하려면

 => 최소(0)인 x를 구하기 위해선 Ax - b와 A의 전치행렬에 직교해야함

- 아래와 같이 정규 방정식으로 정리할 수 있음

- 정규방정식의 좌항에 역행렬이 존재하면

- 우리의 경우. 다음의 값을 최소로 하는 지역 증감 벡터 h를 구해야하는데

- 이를 정규 방정식으로 정리하면

쿼시 뉴턴 방법 개요

- 레벤버그 마쿼트 감쇄 뉴턴 방법의 단점(매번 헤시안 행렬 계산하는)을 보완

=> Hf(x)를 근사화된 양의 확정 행렬 B로 대신함.

쿼시 뉴턴 방법

1. 쿼시뉴턴해 h_qn를 구함

2. 직선 알고리즘으로 alpha 계산

감쇄 뉴턴 방법 알고리즘 damped newton

- 경사 하강 방향으로 조금씩 이동

- 감쇄 뉴턴 알고리즘 의사 코드

LMD-Newton 방법

- Levenberg-Marquardt Type Damped Newton Method

- 최소자에서 먼 곳에서는 경사 하강법, 최소자 근처에서는 속도가 빠른 뉴턴 방법을 사용.

 -> 경사 하강법과 뉴턴 방법의 혼합

- 위 기본 감쇄 뉴턴 탐색 방법에서 이득 비율 rho에 따라 mu가 갱신됨.

 -> rho가 1에 가까우면 mu는 줄이고, rho가 멀면 mu를 키움

태일러 급수를 이용해 2차까지 정리하면

L(h)를 최소화 하는 h가 뉴턴 방법의 해

뉴턴 방법 정리

- 아래의 이차 함수에서 A가 양 확정 행렬이면 반복 1회만에 최저점에 도달

 * 양 확정 행렬 positive definite matrix은 역행렬이 존재

뉴턴 방법으로 최저점 찾기

경사하강 방법과 뉴턴 방법의 차이

- 경사 하강 방법에서 여러번 반복이 수행됨

- 뉴턴 방법에는 1번만에 최소자에 도착

* 뉴턴 방법은 시작 점에 따라서 잘 수렴되지 않을 수 있음.

테일러 전개에를 통한 함수 근사화 정리

- 이차 형태(이차 함수)를 반복하여 최소자를 구함

2차 형태 정리

- 집합 S^n은 n x n의 대칭 행렬, f가 컨벡스 함수려면 A는 양 확정행렬이면 됨.

- 최소자는?

경사 하강 방법 gradient descent과 켤래 경사 방법 conjugate gradient의 차이

직선 탐색 알고리즘 line search algorithm

- 하강 방향 벡터 h를 구한 뒤, 하강 뱡향으로 얼마나 이동할지 보폭 크기 step size(alpha)를 결정하는 알고리즘

직선 탐색 알고리즘 예시

- 다음의 식과 초기값이 주어질 때

- 보폭 alpha에 대한 식 구하기

- alpha에 대한 그래프

- alpha = 0.5일때, x1 구하기

- x2에 대한 alpha 구하기

- x2 구하는데 필요한 alpha에 대한 그래프

- alpha = 1/10 일때, x2

=> 정리

직선 탐색 line search의 종류

1. 정확 직선 탐색 exact line search

 - 위 예시 처럼 x + alpha h에서 f(x)의 최소자 계산

2. 완만 직선 탐색 sort line search

 - f(x + alpha h) < f(x)를 만족하는 적당한 alpha를 선택하는 방법

1. 하강 방향

- 경사에 따라 내려가기 위해서 다음을 만족하는 값을 찾아야 함

- alpha가 충분히 작다면 아래와 같이 근사시킬수 있으며 여기서 h는 하강 방향 descent direction

- alpha는 보폭 크기 step size

2. 종료 조건 stopping criteria

- 반복 과정을 종료하기 위해서 다음의 종료 조건 중 선택하여 종료

3. 경사 하강 방법 gradient descent method

- 미분 가능한 함수 f가 초기값 x0에서 최소자 x*를 찾는 과정

- 정리

4. 경사 하강 예제