Levenberg-Marquardt Method

Levenberg-Marquardt Method

Levenberg-Marquardt 정의

• Levenberg-Marquardt 방법은 Gauss-Newton과 Gradient Descent가 결합된 형태로서 현재 매개변수 값이 최적해로부터 멀리 떨어져 있을때 Gradient Descent방식으로 동작하고 최적해 근처에서는 Gauss-Newton 방식으로 동작한다.
• 이러한 특성 덕분에 Levenberg-Marquardt는 초기 추정값이 좋지 않더라도 안정적으로 수렴하며, 최적해 근처에서는 빠른 수렴 속도를 유지할 수 있어 비선형 최고제곱 문제 해결에 널리 사용된다.
• 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$$

---

Levenberg-Marquardt 알고리즘

Gradient Descent

• Levenberg-Marquardt 방법은 Gauss-Newton과 Gradient Descent을 결합한 알고리즘으로, 각 방법의 파라미터 업데이트 수식은 다음과 같다.
• 현재 파라미터 ${\mathbf{\beta }}_k$에 대한 비선형 최소제곱 문제에서 Gradinet Descent 업데이트 식은 다음과 같다.

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

• $\alpha$ : Step Size, Learning Rate
• $J_k$ : 현재 위치에서의 Jacobian
• ${\mathbf{r}}_k$ : 현재 잔차 벡터

Gauss-Newton

• 현재 파라미터 ${\mathbf{\beta }}_k$에 대한 Gauss-Newton 선형 근사 정규방정식과 업데이트 식은 다음과 같다.

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

Levenberg-Marquardt

• 감쇠 계수(damping parameter) 항을 추가하여 Gradient Descent와 Gauss-Newton 중 어느 방식에 더 가깝게 동작할지를 조절한다.

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

• $\lambda >0$ : 감쇠 계수 (Damping Parameter)
• $I$ : 항등 행렬 (Identity Matrix)

감쇠계수 $\lambda$의 역할

• Levenberg-Marquardt의 핵심은 $\lambda$의 크기 변화에 따라 성격이 바뀐다는 점이다.
• $\lambda$가 작을 때는 Levenberg-Marquardt이 Gauss-Newton과 거의 같아진다.

$$\lambda \to 0$$ $$({J_k}^T{J}_k+\lambda I)\Delta \mathbf{\beta }\approx {J_k}^T{J}_k\Delta \mathbf{\beta }$$ $${J_k}^T{J}_k\Delta \mathbf{\beta }=-{J_k}^T{\mathbf{r}}_k$$

• $\lambda$가 클 때는 Levenberg-Marquardt이 Gradient Descent와 거의 같아진다.

$$\lambda \to \infty$$ $$({J_k}^T{J}_k+\lambda I)\approx \lambda I$$ $$\lambda \Delta \mathbf{\beta }\approx -{J_k}^T{\mathbf{r}}_k$$ $$\Delta \mathbf{\beta }\approx -\frac{1}{\lambda }{J_k}^T{\mathbf{r}}_k$$

감쇠계수 $\lambda$의 조절 전략

• 감쇠계수 $\lambda$가 작을 때는 최적해 근처에서 Gauss-Newton의 빠른 수렴 속도를 활용하고, 클 때에는 최적해로부터 멀리 떨어져 있을 때 Gradient Descent의 안정적인 수렴 특성을 활용하여 발산을 방지 할 수 있다.
• Levenberg-Marquardt 알고리즘은 각 반복 단계에서 $\lambda$ 값을 동적으로 조절한다.

1. 새로운 파라미터 ${\mathbf{\beta }}_{k+1}$을 계산한 후, 잔차 제곱합 $||\mathbf{r}({\mathbf{\beta }}_{k+1})|{|}^2$을 평가한다.
2. 만약 기존 파라미터 ${\mathbf{\beta }}_k$의 잔차보다 더 작으면 $\lambda$를 감소시켜 Gauss-Newton에 가깝게 동작하도록 한다.
   • $\lambda \leftarrow \lambda /\nu$, 여기서 $\nu >1$
3. 만약 기존 파라미터 ${\mathbf{\beta }}_k$의 잔차보다 더 크면 $\lambda$를 증가시켜 Gradient Descent에 가깝게 동작하도록 한다.
   • $\lambda \leftarrow \lambda \cdot \nu$
   • 기존 파라미터 ${\mathbf{\beta }}_k$는 유지하고, 증가시킨 $\lambda$ 값으로 다시 $\Delta \mathbf{\beta }$를 계산한다.

---