최적화의 여정은 하나의 근본적인 질문에서 시작된다: 주어진 데이터 이면에 숨겨진 패턴이나 법칙은 무엇인가? 우리는 종종 이 법칙을 수학적 ‘모델’로 표현하고자 한다. 예를 들어, 어떤 화학 반응의 시간에 따른 농도 변화나, 인구의 성장 곡선, 혹은 로봇 팔의 움직임을 설명하는 모델을 생각할 수 있다.1 이 모델들은 보통 여러 개의 ‘파라미터’를 포함하는데, 이 파라미터 값들이 모델의 구체적인 형태를 결정한다. 최적화의 본질은 바로 이 모델의 파라미터들을 조정하여, 모델의 예측이 실제 관측된 데이터와 가장 잘 부합하도록 만드는 과정이다.2
가장 흔한 최적화 문제 중 하나는 곡선 피팅(curve fitting) 또는 비선형 회귀(non-linear regression)이다.3 실험을 통해 얻은 한 쌍의 데이터 포인트 $(t_i, y_i)$들이 있다고 가정해보자. 우리의 목표는 이 데이터 포인트들을 가장 잘 설명하는 비선형 모델 함수 $y = f(t, \boldsymbol{\beta})$를 찾는 것이다. 여기서 $\boldsymbol{\beta}$는 우리가 찾아야 할 모델의 파라미터 벡터다.3 ‘가장 잘 설명한다’는 것은 보통 모델의 예측값 $f(t_i, \boldsymbol{\beta})$와 실제 측정값 $y_i$ 사이의 오차(error)를 최소화하는 것을 의미한다.
이해를 돕기 위해 선형 회귀와 비선형 회귀의 근본적인 차이를 짚고 넘어가자. 선형 회귀 모델, 예를 들어 $y = \beta_0 + \beta_1 x$에서는 파라미터 $\beta_1$이 1만큼 변할 때 $y$의 변화량은 항상 $x$로 일정하다. 즉, 파라미터의 영향력이 파라미터 자신의 값에 의존하지 않는다.5 이런 선형성 덕분에 우리는 해석적인 방법(closed-form solution)으로 오차를 최소화하는 파라미터를 한 번에 찾아낼 수 있다.
하지만 세상의 많은 현상은 비선형적이다. 예를 들어, 생물의 성장 곡선을 나타내는 지수 모델 $y = \theta_1 e^{\theta_2 x}$를 생각해보자.5 여기서 파라미터 $\theta_2$의 변화가 $y$에 미치는 영향은 입력 변수 $x$뿐만 아니라, 파라미터 $\theta_1$과 $\theta_2$의 현재 값에 따라서도 달라진다. 이처럼 파라미터에 대해 함수가 선형이 아닌 경우를 ‘비선형 모델’이라고 부른다.1 이러한 비선형성 때문에, 대부분의 비선형 문제에서는 최적의 파라미터를 한 번에 계산해내는 마법 같은 공식이 존재하지 않는다. 대신, 우리는 초기 추정치에서 시작하여 점진적으로 더 나은 해를 찾아가는 ‘반복적인(iterative)’ 최적화 알고리즘에 의존해야만 한다.1 레벤버그-마르쿼트 알고리즘은 바로 이 비선형 문제들을 풀기 위해 태어난 강력한 반복적 해법 중 하나다.
비선형 최적화 문제를 수학적으로 명확하게 정의하는 것부터 시작하자. 이것이 우리가 앞으로 다룰 모든 알고리즘의 출발점이다. 비선형 최소제곱법(NLLS)은 $m$개의 관측 데이터와 $n$개의 미지 파라미터($m \ge n$이라는 가정이 일반적이다)를 포함하는 모델을 다룬다.6
먼저 ‘잔차(residual)’라는 개념을 정의해야 한다. $i$번째 관측 데이터 쌍 $(x_i, y_i)$에 대해, 잔차 $r_i$는 실제 관측값 $y_i$와 현재 파라미터 $\boldsymbol{\beta}$를 사용한 모델의 예측값 $f(x_i, \boldsymbol{\beta})$ 사이의 차이로 정의된다.9 \(r_i(\boldsymbol{\beta}) = y_i - f(x_i, \boldsymbol{\beta})\) 우리가 가진 $m$개의 모든 관측치에 대해 이 잔차들을 계산하여 하나의 벡터, 즉 잔차 벡터 $\mathbf{r}(\boldsymbol{\beta})$를 만들 수 있다. \(\mathbf{r}(\boldsymbol{\beta}) = \begin{bmatrix} r_1(\boldsymbol{\beta}) \\ r_2(\boldsymbol{\beta}) \\ \vdots \\ r_m(\boldsymbol{\beta}) \end{bmatrix}\) NLLS의 목표는 이 잔차들의 크기를 종합적으로 최소화하는 것이다. 가장 널리 사용되는 방법은 ‘잔차 제곱의 합(Sum of Squared Residuals, SSR)’을 최소화하는 것이다. 이 값을 비용 함수(cost function) 또는 목적 함수(objective function) $S(\boldsymbol{\beta})$로 정의한다.3 \(S(\boldsymbol{\beta}) = \sum_{i=1}^{m} r_i(\boldsymbol{\beta})^2 = \mathbf{r}(\boldsymbol{\beta})^T \mathbf{r}(\boldsymbol{\beta}) = ||\mathbf{r}(\boldsymbol{\beta})||_2^2\) 이 공식은 각 잔차를 제곱하여 모두 더함으로써, 양수와 음수 잔차가 서로 상쇄되는 것을 막고 모든 오차를 동등하게 고려하는 역할을 한다.11 우리의 최종 목표는 이 비용 함수 $S(\boldsymbol{\beta})$를 최소로 만드는 파라미터 벡터 $\boldsymbol{\beta}^*$를 찾는 것이다.
미적분학의 기본 원리에 따르면, 어떤 함수의 최소값은 그 함수의 그래디언트(gradient)가 0이 되는 지점에서 나타난다. 따라서 우리는 $\nabla S(\boldsymbol{\beta}) = \mathbf{0}$ 방정식을 풀면 된다. 하지만 모델 함수 $f$가 파라미터 $\boldsymbol{\beta}$에 대해 비선형이기 때문에, 그래디언트 방정식 역시 복잡한 비선형 연립방정식이 되어 직접 풀기가 거의 불가능하다.6 이것이 바로 우리가 경사 하강법, 가우스-뉴턴법, 그리고 레벤버그-마르쿼트법과 같은 반복적 해법을 필요로 하는 근본적인 이유다.
여기서 한 가지 중요한 점을 짚고 넘어가야 한다. NLLS 문제는 일반적인 최적화 문제 $min f(x)$와는 다른, 매우 ‘구조화된(structured)’ 형태를 띤다. 비용 함수가 항상 ‘어떤 벡터의 $L_2$-norm 제곱’ 형태라는 점이다. 이 특별한 구조는 그냥 주어진 것이 아니다. 이 구조 덕분에 우리는 비용 함수의 2차 미분 정보(헤시안 행렬)를 단지 1차 미분 정보(자코비안 행렬)만으로 매우 효과적으로 ‘근사’할 수 있다. 이 근사야말로 가우스-뉴턴법과 레벤버그-마르쿼트 알고리즘의 심장과도 같은 핵심 아이디어다. 즉, NLLS 문제의 ‘구조’ 자체가 더 효율적이고 강력한 알고리즘의 탄생을 가능하게 한 것이다. 이 점을 이해하는 것은 왜 LM 알고리즘이 곡선 피팅이나 컴퓨터 비전의 번들 조정과 같은 특정 분야에서 절대적인 표준으로 자리 잡았는지를 이해하는 첫걸음이 될 것이다.
레벤버그-마르쿼트(LM) 알고리즘은 독창적인 발명이라기보다는, 기존에 존재하던 두 가지 강력한 최적화 방법론, 즉 ‘경사 하강법(Gradient Descent)’과 ‘가우스-뉴턴법(Gauss-Newton)’의 장점을 지능적으로 결합한 진화의 산물이다.2 LM의 정수를 이해하기 위해서는 먼저 그 부모 격인 두 알고리즘의 원리와 장단점을 명확히 파악해야 한다.
경사 하강법은 최적화 세계의 ‘아담’과도 같은 가장 근본적인 알고리즘이다. 그 원리는 놀라울 정도로 직관적이다. 짙은 안개가 낀 산 정상에서 길을 잃었다고 상상해보자. 가장 빨리 하산하는 방법은 무엇일까? 바로 현재 위치에서 발밑을 더듬어 가장 가파른 내리막길 방향을 찾고, 그 방향으로 조심스럽게 한 걸음 내딛는 것이다. 이 과정을 계속 반복하면 언젠가는 산 아래 계곡(최소점)에 도달할 것이다.13
이 비유를 수학적으로 옮겨보자. 비용 함수 $S(\boldsymbol{\beta})$라는 ‘지형’이 있을 때, 현재 위치 $\boldsymbol{\beta}_k$에서 가장 가파른 내리막 방향은 음의 그래디언트(negative gradient) 방향, 즉 $-\nabla S(\boldsymbol{\beta}_k)$이다.13 따라서 경사 하강법의 업데이트 규칙은 현재 위치에서 이 방향으로 학습률(learning rate) $\eta$만큼 이동하는 것이다.15 \(\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k - \eta \nabla S(\boldsymbol{\beta}_k)\) 비선형 최소제곱 문제에서 비용 함수의 그래디언트는 $\nabla S(\boldsymbol{\beta}) = 2\mathbf{J}^T\mathbf{r}$로 계산된다. 여기서 $\mathbf{J}$는 잔차 벡터 $\mathbf{r}$을 파라미터 $\boldsymbol{\beta}$로 미분한 자코비안 행렬(Jacobian matrix)이고, $\mathbf{r}$은 잔차 벡터다.2 따라서 NLLS 문제에 대한 경사 하강법 업데이트는 다음과 같이 표현할 수 있다. \(\boldsymbol{\beta}_{k+1} = \boldsymbol{\beta}_k - \alpha \mathbf{J}^T \mathbf{r}\) 여기서 $\alpha = 2\eta$는 스텝 크기를 조절하는 상수다.
장점:
단점:
경사 하강법은 느리지만 확실하게 나아가는 ‘거북이’와 같다. 안정적이지만, 때로는 답답할 정도로 느리다.
경사 하강법의 느린 속도에 대한 해답으로 등장한 것이 가우스-뉴턴법이다. 이 방법은 비선형 최소제곱 문제의 ‘구조’를 적극적으로 활용하여 더 과감하고 빠른 걸음을 내딛는다.
가우스-뉴턴법의 핵심 아이디어는 각 반복 단계에서 복잡한 비선형 함수를 다루기 쉬운 ‘선형 함수’로 근사하는 것이다.7 현재 파라미터 $\boldsymbol{\beta}k$ 근방에서 잔차 함수 $\mathbf{r}(\boldsymbol{\beta})$를 1차 테일러 전개를 이용해 선형으로 근사할 수 있다. \(\mathbf{r}(\boldsymbol{\beta}_k + \boldsymbol{\delta}) \approx \mathbf{r}(\boldsymbol{\beta}_k) + \mathbf{J}(\boldsymbol{\beta}_k)\boldsymbol{\delta}\) 여기서 $\mathbf{J}(\boldsymbol{\beta}_k)$는 현재 위치에서의 자코비안 행렬이고, $\boldsymbol{\delta}$는 우리가 찾아야 할 업데이트 스텝이다. 이제 이 선형 근사식을 원래의 비용 함수 $S(\boldsymbol{\beta}) = ||\mathbf{r}(\boldsymbol{\beta})||^2$에 대입하면, 비용 함수는 업데이트 스텝 $\boldsymbol{\delta}$에 대한 간단한 2차 함수(quadratic function)로 근사된다. \((\boldsymbol{\beta}_k + \boldsymbol{\delta}) \approx ||\mathbf{r}_k + \mathbf{J}_k\boldsymbol{\delta}||^2\) 이 2차 함수를 최소화하는 $\boldsymbol{\delta}$는 선형 최소제곱 문제를 푸는 것과 같으며, 그 해는 다음의 ‘정규방정식(Normal Equations)’을 만족한다.9 \((\mathbf{J}_k^T \mathbf{J}_k) \boldsymbol{\delta} = -\mathbf{J}_k^T \mathbf{r}_k\) 이 선형 연립방정식을 풀어서 얻은 $\boldsymbol{\delta}$를 이용해 파라미터를 업데이트한다: $\boldsymbol{\beta}{k+1} = \boldsymbol{\beta}_k + \boldsymbol{\delta}$.
장점:
단점:
가우스-뉴턴법은 빠르지만 무모한 ‘토끼’와 같다. 조건이 좋을 때는 눈 깜짝할 사이에 결승선에 도착하지만, 예상치 못한 장애물을 만나면 쉽게 넘어져 버린다.
경사 하강법과 가우스-뉴턴법은 마치 동전의 양면과 같다. 한쪽은 안정성을 얻는 대신 속도를 희생하고, 다른 한쪽은 속도를 얻는 대신 안정성을 포기한다.
| 특징 | 경사 하강법 (Gradient Descent) | 가우스-뉴턴법 (Gauss-Newton) |
|---|---|---|
| 기반 원리 | 1차 미분 (그래디언트) | 1차 미분 기반의 2차 근사 (자코비안) |
| 업데이트 방향 | 가장 가파른 하강 방향 | 선형화된 문제의 최소제곱 해 |
| 수렴 속도 | 선형 (느림) | 2차에 가까움 (빠름, 단 조건부) |
| 안정성 | 높음 (수렴 보장) | 낮음 (발산 위험) |
| 핵심 계산 | 그래디언트 계산 | 자코비안 및 선형 시스템 풀이 |
| 치명적 약점 | 지그재그 현상, 느린 수렴 | $\mathbf{J}^T \mathbf{J}$가 특이/ill-conditioned일 때 실패 |
| 적합한 상황 | 해에서 멀리 떨어져 있을 때 | 해에 가깝고 잔차가 작을 때 |
이 명백한 트레이드오프는 새로운 알고리즘의 필요성을 명확히 보여준다. 이상적인 최적화 알고리즘은 상황에 따라 자신의 모습을 바꿀 수 있어야 한다. 즉, 최적해에서 멀리 떨어져 있어 지형이 험난할 때는 경사 하강법처럼 조심스럽고 안정적인 걸음을 내딛고, 최적해 근처에 도달하여 지형이 부드러운 2차 함수와 비슷해지면 가우스-뉴턴법처럼 빠르고 과감한 도약을 하는 ‘적응형(adaptive)’ 전략이 필요하다.12
이것이 바로 레벤버그-마르쿼트 알고리즘이 해결하고자 하는 핵심 과제이며, 그 탄생의 배경이다. LM은 두 거인의 어깨 위에 서서 더 멀리, 더 정확하게 보려는 시도다.
레벤버그-마르쿼트(LM) 알고리즘은 경사 하강법의 안정성과 가우스-뉴턴법의 속도를 결합하려는 시도에서 탄생한, 비선형 최소제곱 문제 해결을 위한 정교한 해법이다. 이 알고리즘의 핵심은 두 방법 사이를 동적으로 ‘보간(interpolation)’하는 영리한 메커니즘에 있다.2
LM 알고리즘의 천재성은 가우스-뉴턴의 정규방정식에 단 하나의 항, ‘감쇠 항(damping term)’을 추가한 데서 비롯된다. 이 작은 변화가 알고리즘의 행동 전체를 극적으로 바꾼다.2
가우스-뉴턴법의 업데이트 스텝 $\boldsymbol{\delta}$는 $(\mathbf{J}^T \mathbf{J}) \boldsymbol{\delta} = -\mathbf{J}^T \mathbf{r}$을 풀어 구한다. LM은 여기에 감쇠 인자(damping parameter) $\lambda$ (람다)를 이용한 항을 추가하여 다음과 같은 ‘증강된 정규방정식(augmented normal equations)’을 사용한다.3 \((\mathbf{J}^T \mathbf{J} + \lambda \mathbf{I}) \boldsymbol{\delta} = -\mathbf{J}^T \mathbf{r}\) 여기서 $\mathbf{I}$는 단위 행렬(identity matrix)이다. 이 감쇠 인자 $\lambda$가 바로 LM 알고리즘의 조종간 역할을 한다. $\lambda$의 값에 따라 알고리즘은 경사 하강법과 가우스-뉴턴법 사이에서 자신의 정체성을 바꾼다.23
이러한 하이브리드 동작은 ‘신뢰 영역(Trust Region)’이라는 더 넓은 최적화 프레임워크 관점에서도 해석될 수 있다.26 각 반복 단계에서, 우리는 현재의 선형 근사 모델이 유효하다고 믿는 ‘신뢰 영역’이라는 가상의 반경(
$\Delta_k$)을 설정한다. 그리고 이 영역 내에서 비용 함수를 가장 많이 줄이는 스텝을 찾는다. 감쇠 인자 $\lambda$는 이 신뢰 영역의 크기와 간접적으로 연결되어 있다. 스텝이 성공적이면 모델을 더 신뢰할 수 있으므로 신뢰 영역을 넓히고($\lambda$를 줄이고), 스텝이 실패하면 모델을 덜 신뢰해야 하므로 신뢰 영역을 좁힌다($\lambda$를 늘린다). 이처럼 LM은 매 스텝마다 자신의 보폭과 방향을 데이터에 기반하여 스스로 조절하는 ‘지능형’ 알고리즘인 것이다.
LM 알고리즘의 발전 과정을 살펴보면, 실용적인 문제 해결에서 출발하여 점차 정교한 이론으로 발전해 나갔음을 알 수 있다. 이는 발견법(heuristic)과 이론(theory)의 절묘한 조화를 보여준다.
Levenberg의 제안 (1944): Kenneth Levenberg는 가우스-뉴턴법의 가장 큰 약점, 즉 $\mathbf{J}^T \mathbf{J}$ 행렬이 특이 행렬이 되어 스텝을 계산할 수 없는 문제를 해결하고자 했다.3 그의 아이디어는 간단했다. 행렬의 대각선에 작은 양수 값 $\lambda$를 더해주는 것이다. \((\mathbf{J}^T \mathbf{J} + \lambda \mathbf{I}) \boldsymbol{\delta} = -\mathbf{J}^T \mathbf{r}\) 수학적으로, 양의 준정부호(positive semi-definite) 행렬인 $\mathbf{J}^T \mathbf{J}$에 양의 정부호(positive definite) 행렬인 $\lambda \mathbf{I}$($\lambda > 0$)를 더하면, 그 결과인 $(\mathbf{J}^T \mathbf{J} + \lambda \mathbf{I})$는 항상 양의 정부호가 된다. 양의 정부호 행렬은 항상 역행렬이 존재하므로, 이 수정된 방정식은 언제나 유일한 해 $\boldsymbol{\delta}$를 보장한다.21 이는 가우스-뉴턴법이 실패하는 상황에 대한 실용적이고 강력한 ‘안전장치’를 마련한 것이다.
Marquardt의 개선 (1963): Donald Marquardt는 Levenberg의 아이디어를 한 단계 더 발전시켰다.27 그는 두 가지 중요한 기여를 했다. 첫째, 그는
$\lambda$ 값을 고정하지 않고, 매 반복마다 스텝의 성공 여부에 따라 동적으로 조절하는 전략을 제안했다. 성공하면 $\lambda$를 줄여 가우스-뉴턴에 가깝게 만들고, 실패하면 $\lambda$를 늘려 경사 하강법에 가깝게 만드는 이 발견적 규칙은 LM 알고리즘의 적응성의 핵심이 되었다.11 둘째, 그는 파라미터들의 스케일이 크게 다를 때 발생하는 문제를 해결하기 위해, 단위 행렬
$\mathbf{I}$ 대신 $\mathbf{J}^T \mathbf{J}$의 대각 성분으로 구성된 행렬 $\text{diag}(\mathbf{J}^T \mathbf{J})$을 사용하는 스케일링 기법을 제안했다.3 \((\mathbf{J}^T \mathbf{J} + \lambda \, \text{diag}(\mathbf{J}^T \mathbf{J})) \boldsymbol{\delta} = -\mathbf{J}^T \mathbf{r}\) 이 스케일링은 그래디언트가 작은 방향(비용 함수가 평평한 방향)으로 더 큰 스텝을 내딛도록 유도하여, 좁고 긴 계곡 형태의 비용 함수에서 수렴을 가속하는 효과를 가져온다.
이처럼 LM 알고리즘은 처음에는 실용적인 ‘땜질’처럼 보였던 아이디어에서 출발했지만, 나중에 신뢰 영역 방법론이라는 견고한 수학적 기반 위에서 설명될 수 있음이 밝혀졌다. 이는 잘 만들어진 발견법이 종종 깊은 이론적 통찰을 내포하고 있음을 보여주는 좋은 예다.
| $\lambda$ 값 | 알고리즘 행동 | 스텝의 특징 | 목적 |
|---|---|---|---|
| 크다 (e.g., $10^4$) | 경사 하강법(GD)에 가까움 | 방향: $-\nabla S$ / 크기: 작음 | 안정성 확보, 발산 방지 |
| 중간 | GD와 GN의 혼합 | - | 안정성과 속도의 균형 |
| 작다 (e.g., $10^{-3}$) | 가우스-뉴턴법(GN)에 가까움 | 방향: GN 스텝 / 크기: 큼 | 빠른 수렴 |
| 0 | 순수 가우스-뉴턴법 | GN 스텝 | 가장 빠른 수렴 (성공 시) |
LM 알고리즘의 전체 흐름을 의사 코드(pseudo-code) 형태로 정리하면 다음과 같다. 이 절차는 알고리즘의 핵심 로직을 명확하게 보여준다.2
| 그래디언트 크기가 매우 작을 때: $ | \mathbf{g}_k | _\infty \le \epsilon_1$. |
| 파라미터 변화량이 매우 작을 때: $ | \boldsymbol{\delta} | _2 \le \epsilon_2 ( | \boldsymbol{\beta}_k | _2 + \epsilon_2)$. |
이 단계별 절차는 LM 알고리즘이 어떻게 안정성과 속도 사이에서 외줄타기를 하는지를 구체적으로 보여준다. 성공과 실패의 피드백을 통해 감쇠 인자 $\lambda$를 끊임없이 조절하며, 문제의 지형에 가장 적합한 방식으로 최적해를 향해 나아가는 것이다.
이론적 원리를 이해했다면, 이제 레벤버그-마르쿼트(LM) 알고리즘이 실제 세계의 문제들을 어떻게 해결하는지 구체적인 사례를 통해 살펴볼 차례다. LM은 특히 비선형 회귀, 컴퓨터 비전, 인공신경망 학습과 같은 분야에서 그 진가를 발휘한다.
LM 알고리즘의 가장 고전적이고 직관적인 적용 분야는 데이터 피팅, 즉 비선형 회귀다.3 실험 데이터에 비선형 모델을 맞추는 과정은 LM의 작동 방식을 시각적으로 이해하는 데 매우 효과적이다.
문제 설정:
생화학에서 효소의 반응 속도를 모델링하는 데 널리 쓰이는 Michaelis-Menten 방정식을 예로 들어보자.5 이 모델은 기질 농도 $S$에 따른 반응 속도 $R$을 다음과 같이 설명한다. \(R = \frac{V_{max} S}{K_M + S}\) 여기서 우리가 찾아야 할 파라미터는 최대 반응 속도 $V_{max}$와 Michaelis 상수 $K_M$이다. 즉, 파라미터 벡터는 $\boldsymbol{\beta} = [V_{max}, K_M]^T$이다. 실험을 통해 여러 농도 $S_i$에 대한 반응 속도 $R_i$ 데이터를 얻었다고 가정하자. 우리의 목표는 이 데이터에 가장 잘 맞는 $V_{max}$와 $K_M$을 찾는 것이다.
구현 단계:
모델 및 잔차 함수 정의: 모델 함수 $f(\boldsymbol{\beta}, S_i) = \frac{\beta_1 S_i}{\beta_2 + S_i}$와 잔차 함수 $r_i(\boldsymbol{\beta}) = R_i - f(\boldsymbol{\beta}, S_i)$를 정의한다.29
자코비안 행렬 계산: 잔차 함수를 각 파라미터로 편미분하여 자코비안 행렬 $\mathbf{J}$를 구한다. \(\mathbf{J}_{i,1} = \frac{\partial r_i}{\partial \beta_1} = - \frac{S_i}{\beta_2 + S_i}\)
\[\mathbf{J}_{i,2} = \frac{\partial r_i}{\partial \beta_2} = \frac{\beta_1 S_i}{(\beta_2 + S_i)^2}\]초기 추정치 설정: LM과 같은 반복 알고리즘은 시작점이 매우 중요하다. 좋은 초기 추정치는 수렴 속도를 높이고, 나쁜 추정치는 알고리즘을 엉뚱한 지역 최소점(local minimum)으로 이끌거나 수렴에 실패하게 할 수 있다.1 문제에 대한 사전 지식을 활용하거나, 모델을 선형화하여 대략적인 값을 구하는 등의 방법으로 합리적인 초기 추정치
$\boldsymbol{\beta}_0$를 설정해야 한다.
LM 알고리즘 적용: 설정된 초기값과 데이터를 가지고 3.3절에서 설명한 LM 알고리즘을 반복적으로 적용한다. 각 반복마다 비용 함수 $S(\boldsymbol{\beta})$의 값과 감쇠 인자 $\lambda$의 변화를 관찰하면, 알고리즘이 어떻게 최적해를 찾아가는지 추적할 수 있다. 처음에는 $\lambda$가 비교적 큰 값을 유지하며 안정적으로 탐색하다가, 해에 가까워지면 $\lambda$가 급격히 작아지면서 가우스-뉴턴처럼 빠르게 수렴하는 전형적인 패턴을 관찰할 수 있다.2
LM 알고리즘이 단순한 곡선 피팅을 넘어, 복잡하고 거대한 실제 문제에서 어떻게 사용되는지를 보여주는 가장 대표적인 예가 바로 컴퓨터 비전 분야의 번들 조정(Bundle Adjustment)이다. BA는 Structure from Motion (SfM)이나 시각적 SLAM(Simultaneous Localization and Mapping)과 같은 기술의 핵심적인 마지막 단계로, LM은 이 분야에서 사실상의 표준(de facto standard) 알고리즘으로 통한다.31
번들 조정이란 무엇인가?
여러 장의 사진(혹은 비디오 프레임)에서 공통으로 나타나는 특징점들(feature points)의 2D 이미지 좌표를 입력으로 받아, 이 모든 특징점들의 3D 공간 좌표와 각 사진을 찍은 카메라의 위치 및 방향(pose)을 동시에 최적화하는 거대한 비선형 최소제곱 문제다.32 ‘번들(bundle)’이란 각 3D 점에서 각 카메라로 향하는 광선들의 묶음을 의미하며, 이 광선 묶음들을 조정하여 전체 모델을 일관성 있게 만든다는 뜻에서 ‘번들 조정’이라는 이름이 붙었다.
최적화의 목표는 추정된 3D 점들을 각 카메라 모델을 통해 이미지 평면에 다시 투영(reprojection)했을 때 계산되는 2D 좌표와, 실제 이미지에서 관측된 2D 특징점의 좌표 사이의 오차, 즉 ‘재투영 오차(reprojection error)’의 제곱 합을 최소화하는 것이다.32
왜 LM이 번들 조정에 최적인가?
BA는 수십만 개에서 수백만 개에 이르는 파라미터(모든 3D 점의 $x, y, z$ 좌표 + 모든 카메라의 위치 및 방향 파라미터)를 가질 수 있는 매우 큰 규모의 NLLS 문제다. 언뜻 보면 LM의 $O(n^3)$ 계산 복잡도 때문에 적용이 불가능해 보일 수 있다.
하지만 BA 문제의 자코비안 행렬에는 매우 특별하고 중요한 ‘구조’가 숨어있다. 바로 ‘희소성(sparsity)’이다.35 특정 3D 점은 전체 카메라 중 극히 일부에서만 관측된다. 마찬가지로, 특정 카메라는 전체 3D 점 중 일부만 촬영한다. 이로 인해 자코비안 행렬의 대부분의 원소는 0이 된다. LM 알고리즘을 이 희소 구조를 활용하도록 변형하면, 거대한
$\mathbf{J}^T \mathbf{J}$ 행렬 전체를 메모리에 올리거나 직접 계산할 필요 없이, Schur 보수(Schur complement)와 같은 기법을 사용하여 훨씬 효율적으로 업데이트 스텝을 계산할 수 있다.32
이처럼 알고리즘의 성공은 단순히 알고리즘 자체의 우수성뿐만 아니라, 문제의 ‘구조’를 얼마나 잘 파악하고 활용하느냐에 달려있다. BA의 희소 구조는 LM이 대규모 문제에서도 빛을 발할 수 있게 만든 핵심 열쇠다.
인공신경망(Artificial Neural Network, ANN)의 학습 과정 역시 비용 함수를 최소화하는 최적화 문제이므로, LM을 적용해 볼 수 있다. 특히 파라미터(가중치와 편향)의 수가 비교적 적은 소규모 및 중간 규모의 네트워크에서 LM은 강력한 성능을 보인다.23
문제 재구성:
신경망의 학습은 주어진 입력에 대한 네트워크의 출력과 실제 목표값(target) 사이의 오차 제곱합(mean squared error, MSE)을 최소화하는 과정으로 볼 수 있다. 이는 정확히 NLLS 문제의 형태를 띤다.
장점:
단점:
BA와 신경망 학습 사례의 대비는 중요한 교훈을 준다. 알고리즘의 우수성은 절대적인 것이 아니라 ‘문제의 구조와 규모’에 따라 상대적으로 결정된다. BA의 ‘희소성’이라는 구조는 LM의 약점을 보완해주었지만, 일반적인 신경망의 ‘밀집성(density)’은 LM의 약점을 그대로 노출시켰다. 따라서 실제 문제 해결사는 다양한 알고리즘의 장단점을 이해하고, 주어진 문제에 가장 적합한 도구를 선택할 수 있는 안목을 갖추어야 한다.
레벤버그-마르쿼트(LM) 알고리즘의 진정한 위치를 이해하려면, 이를 최적화라는 더 넓은 생태계 안에 놓고 다른 주요 알고리즘들과 비교해 보아야 한다. 특히 현대 머신러닝의 주역인 1차 최적화 방법(예: Adam)과, 또 다른 강력한 2차 정보 활용법인 유사-뉴턴법(예: BFGS)과의 비교는 LM의 특징과 장단점을 더욱 명확하게 부각시킨다.
현대 딥러닝의 성공은 대규모 데이터와 거대한 모델을 효율적으로 학습시킬 수 있는 1차 최적화 알고리즘, 특히 Adam의 등장과 궤를 같이한다.44 LM과 Adam의 비교는 ‘정보의 질’과 ‘계산 비용’ 사이의 근본적인 트레이드오프를 보여준다.
핵심 트레이드오프: ‘정보량’ vs. ‘계산 비용’
LM (2차 정보 활용): LM은 자코비안을 통해 비용 함수의 2차 곡률 정보(헤시안)를 근사하여 사용한다. 이 ‘고급 정보’ 덕분에 LM은 더 똑똑하고 직접적인 경로로 최소점을 찾아갈 수 있다. 마치 지형의 굴곡까지 파악하고 최단 경로를 계산하는 것과 같다. 하지만 이 정보를 얻고 활용하는 데는 막대한 계산 비용이 따른다. 각 스텝의 계산 복잡도는 파라미터 수 $n$에 대해 $O(n^3)$에 달한다.28
Adam (1차 정보 활용): Adam은 오직 1차 미분 정보인 그래디언트와, 과거 그래디언트의 이동 평균(모멘텀)만을 사용한다.44 이는 지형의 기울기만 보고 다음 걸음을 결정하는 것과 같다. 각 스텝에 필요한 정보가 단순하기 때문에 계산 비용이
$O(n)$으로 매우 낮다. 대신, 최적해에 도달하기까지 더 많은 스텝(반복)이 필요할 수 있다.45
왜 딥러닝에서는 Adam이 지배적인가?
답은 ‘규모(scale)’에 있다. 현대 딥러닝 모델의 파라미터 수 $n$은 수백만에서 수십억에 이른다. 이러한 규모에서 LM의 $O(n^3)$ 계산 비용과 $O(n^2)$ 메모리 요구량은 감당 불가능한 수준이다.37 반면, Adam의 계산 비용은
$n$에 선형적으로 비례하므로, 아무리 큰 모델이라도 학습을 진행할 수 있다.
성능 비교:
결론적으로 LM은 정밀 가공을 위한 ‘공작기계’와 같고, Adam은 대량 생산을 위한 ‘컨베이어 벨트’와 같다. 소량의 부품을 극도의 정밀도로 가공해야 할 때는 LM이 뛰어나지만, 수백만 개의 부품을 빠르게 생산해야 할 때는 Adam이 유일한 선택지다.
LM과 마찬가지로 2차 정보를 활용하지만, 다른 방식으로 접근하는 알고리즘 그룹이 있다. 바로 유사-뉴턴법이며, 그중 가장 대표적인 것이 BFGS(Broyden-Fletcher-Goldfarb-Shanno) 알고리즘이다.47
| LM (특화형): LM은 비용 함수가 잔차 제곱의 합, 즉 $S(\boldsymbol{\beta}) = | \mathbf{r}(\boldsymbol{\beta}) | ^2$ 형태인 비선형 최소제곱(NLLS) 문제에 ‘특화’된 알고리즘이다. 헤시안을 $\mathbf{J}^T \mathbf{J}$로 근사하는 핵심 아이디어는 오직 이 구조에서만 유효하다.30 |
BFGS는 다양한 도구를 갖춘 ‘만능 공구함’과 같고, LM은 특정 나사에 완벽하게 맞는 ‘전용 드라이버’와 같다. 풀어야 할 문제가 명확한 NLLS라면 전용 드라이버인 LM이 더 효율적이다.
지금까지 논의한 내용을 종합하여 주요 최적화 알고리즘들의 특징을 하나의 표로 정리하면 다음과 같다. 이 표는 각 알고리즘의 장단점과 적합한 사용처를 한눈에 파악하는 데 도움을 줄 것이다.
| 특징 | Levenberg-Marquardt (LM) | Adam | BFGS |
|---|---|---|---|
| 문제 유형 | 비선형 최소제곱 (NLLS) 특화 | 일반 최적화 (주로 확률적) | 일반 최적화 (주로 배치) |
| 사용 정보 | 1차 미분 (자코비안)으로 2차 정보 근사 | 1차 미분 (그래디언트) + 모멘텀 | 1차 미분 (그래디언트) 변화로 2차 정보 근사 |
| 계산 복잡도 (per-iteration) | 높음 ($O(n^3)$ 또는 희소성 활용 시 더 낮음) | 낮음 ($O(n)$) | 중간 ($O(n^2)$) |
| 수렴 속도 | 빠름 (2차에 가까움) | 느릴 수 있음 (1차) | 빠름 (초선형, Superlinear) |
| 메모리 요구량 | 높음 ($\mathbf{J}^T \mathbf{J}$ 저장) | 낮음 | 중간 (헤시안 근사 행렬 저장, L-BFGS로 개선) |
| 주요 장점 | NLLS 문제에서 매우 높은 정확도와 빠른 수렴 | 대규모 데이터/모델에 대한 확장성 | 일반 문제에 대한 견고하고 빠른 수렴 |
| 주요 단점 | 대규모 문제에 비실용적 | 하이퍼파라미터에 민감, 최적해의 질 논란 | NLLS 문제에 비특화 |
| Chapter 6 Non-Linear Regression | A Guide on Data Analysis, accessed July 24, 2025, https://bookdown.org/mike/data_analysis/non-linear-regression.html |
| Leveraging the Levenberg-Marquardt Method on Vanishing Point Estimation | by Oleg Boev, accessed July 24, 2025, https://medium.com/@olegboev/leveraging-the-levenberg-marquardt-method-on-vanishing-point-estimation-in-computer-vision-5b10668b1ad5 |