[개념 정리] Levenberg-Marquardt 알고리즘 : 최적화 기법

 

Levenberg-Marquardt 알고리즘은 1960년대초, 비선형 최소 제곱 문제(nonlinear least squares problems)를 해결하기 위해 개발되었습니다. 매개변수화된 수학 모델을 주어진 데이터에 맞게 fitting하는데 사용됩니다. 매개변수가 선형이 아닌 경우, 최소화를 위한 반복적인 접근 방식이 필요로 하게 됩니다.

 

Levenberg-Marquardt 알고리즘은 경사 하강(Gradient Descent)방법과 가우스-뉴턴(Gauss-Newton)방법을 결합하여, 현재 매개변수 추정치가 최적값에 가까울 때는 Gauss-Newton 방법처럼 작동하고, 멀리 있을 때는 Gradient Descent방법처럼 작동하는 최적화 기법입니다.

 

이해를 위해 필요한 개념들을 하나씩 파악하고, 마지막에 Levenberg-Marquardt알고리즘에 대해 소개하겠습니다.

 

 

비선형 최소 제곱 문제(nonlinear least squares problems)

측정된 데이터 포인트 $y(t_i)$와 모델 함수 $ \hat{y}(t_i; p)$ 간의 편차의 제곱의 합을 최소화하는 문제입니다. 각 편차는 해당 데이터 포인트의 표준 오차$\sigma_{y_i}$로 정규화됩니다. 함수는 다음과 같이 전개됩니다

$$\chi^2(p) = \sum_{i=1}^{m} \left( \frac{y(t_i) - \hat{y}(t_i; p)}{\sigma_{y_i}} \right)^2$$

• $\chi^2(p)$는 모델 매개변수 $p$에 대한 제곱 오차입니다.
• $m$은 데이터 포인트의 총 개수입니다.
• $y(t_i)$는 $i$번째 데이터 포인트의 측정값으로써 독립변수입니다.
• $\hat{y}(t_i; p)$는 모델에 의해 예측된 $i$번째 데이터 포인트의 값입니다.
• $\sigma_{y_i}$는 $i$번째 데이터 포인트의 측정 오차입니다. 측정 오차가 작은 데이터 포인트에 더 큰 가중치를 부여하기 위함입니다.

$\chi^2(p)$를 줄이는 것을 목표로 $p$에 perturbation(작은 변화값) $h$를 조금씩 더해가며 반복실행하면서 최적의 $p$를 찾게 됩니다. 이 비선형 최소 제곱 문제를 풀기 위해서는 매개변수 초기값 설정과 이를 업데이트하는 알고리즘이 매우 중요한 요소가 됩니다.

 

여기까지가 비선형 최소 제곱 문제 설명이며, 다음은 뒷부분 설명을 위해 필요한 내용입니다. 위 수식을 벡터와 행렬로 다시 표현하면 아래와 같습니다.

$$\chi^2(p) = (y - \hat{y}(p))^T W (y - \hat{y}(p))$$

• $y$는 측정된 데이터 벡터입니다.
• $\hat{y}(p)$는 매개변수 $p$에 대한 모델 예측 데이터 벡터입니다.
• $W$는 가중치 행렬로, 대각선 요소는 각 데이터 포인트의 오차 $\sigma_{y_i}$​​의 역수 제곱입니다.
  $$W = \begin{bmatrix}
  \frac{1}{{\sigma_{y_1}^2}} & 0 & \cdots & 0 \\
  0 & \frac{1}{{\sigma_{y_2}^2}} & \cdots & 0 \\
  \vdots & \vdots & \ddots & \vdots \\
  0 & 0 & \cdots & \frac{1}{{\sigma_{y_m}^2}}
  \end{bmatrix}$$

 

 

Gradient-Descent Method

딥러닝 분야에서 많이 볼 수 있는 이름입니다. Gradient는 매개변수 $p$ 공간에서 오차함수가 가장 빠르게 증가하는 방향을 나타냅니다. Gradient는 매개변수 $p$를 반복적으로 업데이트하여 오차 함수를 최소화 합니다. 구체적으로 보자면,

$$\frac{\partial \chi^2}{\partial p} = 2(y - \hat{y}(p))^T W \frac{\partial (y - \hat{y}(p))}{\partial p}$$

$\frac{\partial (y - \hat{y}(p))}{\partial p}$ 는 모델 예측값이 매개변수 $p$에 대해 어떻게 변화하는지 나타내는 자코비안(Jacobian) 행렬입니다. 각 매개변수 $p$에 대해 편미분한 행렬입니다.

$$ J = \begin{bmatrix}
\frac{\partial \hat{y}_1}{\partial p_1} & \frac{\partial \hat{y}_1}{\partial p_2} & \cdots & \frac{\partial \hat{y}_1}{\partial p_n} \\
\frac{\partial \hat{y}_2}{\partial p_1} & \frac{\partial \hat{y}_2}{\partial p_2} & \cdots & \frac{\partial \hat{y}_2}{\partial p_n} \\
\vdots & \vdots & \ddots & \vdots \\
\frac{\partial \hat{y}_m}{\partial p_1} & \frac{\partial \hat{y}_m}{\partial p_2} & \cdots & \frac{\partial \hat{y}_m}{\partial p_n}
\end{bmatrix} $$

이를 단순화하면 아래와 같습니다.

$$\frac{\partial \chi^2}{\partial p} = -2(y - \hat{y})^T W J$$

Gradient-Descent방법에서는 매개변수 $p$에서 gradient를 음의 방향으로 조금씩 이동시키면서 $\chi^2$를 감소시켜 최적의 매개변수 $p$를 찾습니다. 다음 step k+1의 $p$값은 이전 step k의 $p$와 $h$의 합으로 구성됩니다.

$$ p_{k+1} = p_k + \frac{\partial \chi^2}{\partial p_k}  = p_k + \Delta p_k = p_k + h_k $$

$h$는 최종적으로 계산하고자하는, 모델 패러미터p를 얼마나 업데이트 할지에 관한 값입니다. perturbation(작은 변화값)이라고도 하며, (크기를 나타내는 스칼라값 $\alpha$와 함께) 아래와 같이 정의됩니다.

$$ h_{\text{gd}} = \alpha J^T W (y - \hat{y})$$

 

 

 

Gauss-Newton Method

$p$가 아닌 $h$의 gradient을 계산해서 최적값을 구합니다. 매개변수 $p$가 최적값에 가까워지면 이차함수(=최고 차수가2)가 된다는 가정으로 설계되었습니다. p에 대해서는 1차 미분형태(=Jacobian)이고, h에 대해서는 2차미분형태(=Hessian)로 근사화 합니다. h 변화에 따른 모델 예측값을 추정하기 위해, 테일러 확장 1차식을 사용합니다.

$$\hat{y}(p + h) \approx \hat{y}(p) + Jh$$

풀고자 하는 문제 $\chi^2(p + h)$에  $\hat{y}$ 부분을 위 수식으로 대입하여 넣어 전개하면, 

$$ \chi^2(p + h) \approx y^T W y + \hat{y}^T W \hat{y} - 2y^T W \hat{y} - 2(y - \hat{y})^T W Jh + h^T J^T W Jh $$

위 수식이 나옵니다. 이 부분은 복잡하기만 하기에 넘어가셔도 되며 중요한 부분은 Gradient Descent에서는 $p$로 미분하였지만 Gauss-Newton에서는 아래와 같이 $h$에 대해 미분한다는 점입니다.

$$ \frac{\partial}{\partial h} \chi^2(p + h) \approx -2(y - \hat{y})^T W J + 2h^T J^T W J $$

h에 대해 극소값을 갖도록, 미분했을 때 0이 되도록 만들어야 합니다. 정리하면

$$ (J^T W J)h_{\text{gn}} = J^T W (y - \hat{y}) $$

다시 한번 더 정리하면, 아래와 같습니다.

$$ h_{\text{gn}} = (J^T W J)^{-1} J^T W (y - \hat{y}) $$

Gradient-Descent에 언급한 마지막 수식과 비교하면, $\alpha$ 대신에 $ (J^T W J)^{-1} $ 로 바뀐 것을 볼 수 있습니다.

 

 

 

 

Levenberg-Marquardt Method

Levenberg-Marquardt 방법론은 Gradient-Descent와 Gauss-Newton가 서로 보완하는 형태의 알고리즘입니다.

• Gradient-Descent 방식은 1차 미분으로 이동 방향을 잘 설정하지만, 이동 크기는 잘 설정하지 못합니다.
• Gauss-Newton 방식은 2차 미분으로 해 주변에서 크기를 잘 설정하지만, 극소점이 아닌 극대점으로도 수렴 할 수 있는 문제를 갖고 있습니다.

오차를 최소화하기 위해, 모델의 패러미터 $p$에 더해지는 perturbation(작은 변화값)을 $h$라고 정의하였고 Gradient-Descent 방법과 Gauss-Newton 방법 각각에 대한 $h$를 다음과 같이 정의 하였습니다. 

$$h_{\text{gd}} = \alpha J^T W (y - \hat{y})$$

$$h_{\text{gn}} = (J^T W J)^{-1} J^T W (y - \hat{y})$$

Levenberg-Marquardt 방법론은 이 두개가 아래와 같이 조합됩니다.

$$h_{lm} = (J^T W J + \lambda I)^{-1} J^T W (y - \hat{y})$$

위 수식은 단위 행렬I에 λ(=damping parameter)가 scale형태로 더해진 꼴로

• λ가 커지면, gd(gradient-descent) 방법론을 사용하게 되고,
• λ가 작아지면, gn(gauss-newton) 방법론을 사용하게 되는 형태가 됩니다.

다른 형태로 λ가 $J^T W J$의 대각요소(diag)을 사용하는 방식이 있는데, 이는 각 패러미터 $p$에 대해 다른 scale을 주게되는 형태입니다.

$$h_{lm} = (J^T W J + \lambda \text{diag}(J^T W J))^{-1} J^T W (y - \hat{y})$$

 

$ \chi^2(p + h_{lm}) > \chi^2(p) $ 가 되면 해에서 멀어졌다고 간주하고  λ를 크게하고, 반대의 경우에 해에 가까워졌다고 생각하며 λ를 작게하면서 λ값이 조절됩니다. 정리하자면,

• 패러미터 $p$가 해에서 멀어진 경우, Gradient-Descent방식이 사용되고
• 패러미터 $p$가 해에서 가까워진 경우, Gauss-Newton방식이 사용됩니다.

 

 

출처

https://darkpgmr.tistory.com/142

http://people.duke.edu/~hpgavin/ce281/lm.pdf