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

기계학습 2014.09.02 16:55

※ 참고로, 아래 글 보다는 최근에 올린 [기계학습] - 최적화 기법의 직관적 이해를 먼저 읽어볼 것을 추천합니다. 그 이후에 아래 글을 읽어보시면 좋을 것 같습니다.


----------


원래는 Levenberg-Marquardt 방법에 대한 내용을 쓰고자 했는데 글을 쓰다 보니 함수 최적화 기법들을 총 정리하는 글이 되고 말았습니다.


Levenberg–Marquardt 방법은 비선형 최소 자승(nonlinear least squares) 문제를 푸는 가장 대표적인 방법입니다.


그동안 뉴턴-랩슨법(Newton–Raphson method), 가우스-뉴턴법(Gauss–Newton method), Gradient descent 방법 등 여러 함수 최적화 기법들을 소개한 바 있지만 사실 비선형 함수 최적화 문제에 있어서 가장 널리 쓰이는 방법은 Levenberg–Marquardt 방법입니다.


그런데 Levenberg–Marquardt 방법을 이해하기 위해서는 먼저 가우스-뉴턴법(Gauss–Newton method)과 Gradient descent 방법에 대한 이해가 필요합니다. 왜냐하면 Levenberg–Marquardt 방법은 가우스-뉴턴법(Gauss–Newton method)과 Gradient descent 방법이 결합된 형태로 볼 수 있기 때문입니다. 그리고 당연히 최소자승법에 대한 이해도 필요합니다.


관련하여 먼저 아래의 글들을 읽어보면 도움이 되리라 생각합니다.


[기계학습] - 최소자승법 이해와 다양한 활용예 (Least Square Method)

[기계학습] - 뉴턴법/뉴턴-랩슨법의 이해와 활용(Newton's method)

[기계학습] - Gradient Descent 탐색 방법


이 글에서는 먼저 위 내용들을 포함하여 관련 내용들을 전반적으로 정리한 후 Levenberg-Marquardt 방법에 대해 살펴보도록 하겠습니다.


1. 최소자승법 & 가중최소자승법

2. Gradient Descent 탐색 방법

3. 뉴턴법 (뉴턴-랩슨법)

4. 가우스-뉴턴법

5. Levenberg-Marquardt 방법

6. 마무리하며



1. 최소자승법 & 가중최소자승법


관측값을 (xi, yi), i=1,...,n, 모델 파라미터를 p = ( p1, p2, ..., pm) , 모델을 y = f(x, p), 관측값과 모델과의 오차(residual)를 ri라 할때, 오차 제곱합이 최소화 되도록 모델 파라미터 p를 정하는 방법을 최소자승법(least square method)이라 한다.


 --- (1)


만일 관측값의 신뢰도(중요도)가 서로 다를 경우에는 각각의 오차 제곱에 가중치 wi를 곱해서 최소화시키는 방법을 사용하는데 이러한 문제를 가중최소자승(weighted least squares, WLS)문제라 부른다 (통계 쪽에서는 보통 wi = 1/σi2로 잡음. 단, σi2은 yi의 분산).


 --- (2)


이 때 식 (1), 식 (2)의 에러합 부분을 행렬 형태로 표현하면 다음과 같다.


 --- (3)


 --- (4)


단, r = [r1, ..., rn]T, W는 wi를 대각원소로 갖는 대각행렬 (W = diag(w1, ..., wn)).


최소자승법은 결국 식 (3) 또는 식 (4)에 의해 주어지는 에러 함수를 최소화시키는 p를 구하는 문제로 볼 수 있으며 이는 p에 대한 미분이 E'(p) = 0, Ew'(p) = 0인 p를 구함으로써 얻어진다. 그런데 선형(linear) 최소자승문제의 경우에는 벡터미분을 이용하여 이러한 해를 직접적으로 구할 수 있다 (closed-form solution이 존재).


☞ 최소자승 문제에 있어서 모델 f(x,p)가 모델 파라미터에 대해 선형인 경우 선형 최소자승 문제(linear least squares problem)라 부르고 그렇지 않은 경우 비선형 최소자승문제(non-linear least squares problem)라 부른다. 예를 들어 f(x,p) = p1*sinx + p2*cosx라면 f(x,p) 자체는 비선형 함수이지만 파라미터 p = (p1,p2)에 대해서는 선형이므로 f(x,p)에 대한 최소자승 문제는 선형(linear) 문제가 된다.


만일 f(x,p)가 p에 대해 선형인 경우에는 f(x,p)를 아래와 같이 p에 대한 일차 결합 형태로 표현할 수 있다.


 --- (5)


따라서, 선형 최소자승문제의 경우에는 아래와 같은 행렬 표현이 가능해진다.


 --- (3)'


 ---(4)'


단,


 --- (6)


벡터미분을 이용하여 E(p), Ew(p)를 p로 미분한 후 0으로 놓으면 


 --- (7)


 --- (8)


가 된다(식 (7), (8)의 양변에 transpose를 취한 후 p에 대해 정리, W는 대각행렬이므로 WT=W, 벡터미분에 대해서는 벡터미분과 행렬미분 글 참조).


따라서, 선형 최소자승문제와 선형 가중최소자승문제의 해는 다음과 같이 closed-form 형태로 구해진다.


 --- (9)


--- (10)


[적용예제] 예를 하나 들어보면, 세점 (x1,y1), (x2,y2), (x3.y3)를 삼각함수 f(x) = p1*sin(x) + p2로 근사시키고자 할 때 최소자승 해는 다음과 같이 구해진다.


--- (11)


[음함수 최소자승법] 만일 모델이 양함수(explicit function) 형태가 아니라 f(x,p) = 0와 같은 음함수(implicit function) 형태일 경우에는 최소자승 문제의 형태 및 풀이방법이 조금 달라진다. 이 경우 ri = f(xi,p)이며, f(x,p)가 p에 대해 선형이면 최소자승문제를 ∑ri2 = ∥Ap∥2와 같이 표현할 수 있다. 그리고, ∑ri2 = ∥Ap∥2를 최소화시키는 p는 A의 SVD(singular value decomposition)을 A = U∑VT라 할 때 최소 특이값(singular value)에 대응하는 V의 열벡터가 된다. 자세한 내용은 [선형대수학 #5] 선형연립방정식 풀이 글 참조.


이상과 같이 선형(linear) 최소자승 문제의 경우에는 pseudo inverse나 SVD(singular value decomposition)을 이용하면 해를 손쉽게 구할 수 있다. 하지만 비선형(non-linear) 최소자승 문제의 경우에는 closed-form solution이 없기 때문에 점진적으로 해를 찾는 방법(iterative minimization)을 사용해야 한다. 즉, 어떤 초기값 p0에서 시작해서 점차적으로 E(p)를 최소화시키는 방향으로 p를 갱신하는 방법을 사용해야 한다. 그리고 이러한 iterative minimization 기법으로는 아래에 설명할 gradient descent 방법, 가우스-뉴턴법, Levenberg-Marquardt 방법 등이 있다.



2. Gradient Descent 탐색 방법


어떤 다변수 함수 E(x1,x2,...,xn)의 그레디언트(gradient)는


 --- (12)


로 정의되며 함수값이 가장 가파르게 증가하는 방향을 나타낸다. 그리고 그레디언트의 크기는 그 증가의 가파른 정도를 나타낸다.


☞ 여기서 다변수 함수라는 말을 어렵게 생각할 필요는 없으며 예를 들어 사람의 외적인 아름다움이 키와 팔의 길이, 다리의 길이로 결정된다고 했을 때, '아름다움 = f(키,팔길이,다리길이)'와 같이 함수값이 여러 요인에 의해 결정된다는 의미이다. 키, 팔다리 길이와 아름다움의 관계를 실제 구하는 것은 어렵겠지만 만일 그 관계가 예를 들어 'f(키,팔길이,다리길이) = 키^3 - 팔길이^2 + 다리길이^2'라 한다면 f의 그레디언트는 ∇f = (3*키^2, -2*팔길이, 2*다리길이)가 된다. 따라서 어떤 사람 A의 키, 팔길이, 다리길이가 키 = 1, 팔길이 = 0.5, 다리길이 = 0.7과 같다면 A 위치에서의 그레디언트 값은 (3, -1, 1.4)이므로 현 시점에서 이 사람이 가장 아름다워지는 방향은 3:1:1.4의 비율로 키는 증가하고 팔길이는 감소, 다리길이는 증가하는 방향이다.


Gradient descent 방법은 아래 식과 같이 어떤 초기값 x0 = (x10,...,xn0)부터 시작하여 그레디언트의 반대 방향으로 계속 내려가다 보면 함수의 최소값을 찾을 수 있다는 방법이다 (자세한 내용은 Gradient Descent 탐색 방법 글 참조).


 --- (13)


만일 함수의 최대값을 찾고 싶을 경우에는 xk+1 = xk + λk∇E(xk) 형태의 gradient ascent 방법을 사용한다.


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

이제 gradient descent 방법을 앞서 설명한 최소자승 문제에 적용해 보자. 선형 최소자승 문제의 경우에는 gradient descent 방법과 같은 근사적 방법을 사용할 필요가 없이 직접 해를 구할 수 있으므로 여기서는 비선형 최소자승 문제에 한해 생각한다. 관측값을 (xi, yi), i=1,...,n, 모델 파라미터를 p = ( p1, p2, ..., pm) , 모델을 y = f(x, p), 오차(residual)를 r(x,p) = y - f(x,p)라 하면 최소화시키고자 하는 목적함수는 다음과 같다.


 --- (14)



 --- (15)


따라서, 비선형 최소자승 문제에 대한 gradient descent 해는 모델 파라미터 p에 대한 초기 추정값 p0=(p10,...,pm0)에서 시작하여 p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다.


 --- (16)


단, Jr은 r의 야코비언(Jacobian) 행렬.


참고로 비선형 가중최소자승(weighted least squares) 문제의 경우에 gradient descent 해는 다음 수식에 의해 구해진다.


 --- (17)



3. 뉴턴법 (뉴턴-랩슨법)


뉴턴법(뉴턴-랩슨법)은 어떤 함수 E(x) = 0의 해를 찾기 위해 임의의 초기값 x0로부터 시작하여 다음 수식에 따라 x를 반복적으로(iterative) 갱신함으로써 해를 찾아가는 방법이다.


 --- (18)


그 원리는 미분이 접선의 기울기임을 이용하여 현재의 x에서 E(x)의 부호와 기울기 E'(x)의 부호에 따라 x를 증가시킬지 감소시킬지를 결정하고 그 기울기의 크기에 따라서 x를 얼마나 많이 증가(감소)시킬지를 결정하는 방식이다.


만일 뉴턴법을 함수 E(x)의 최소(최대)값을 찾는 최적화(optimization) 문제에 적용할 경우에는 다음과 같이 E'(x) = 0의 해를 찾는 문제로 식을 변형하여 적용할 수 있다.


 --- (19)


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


 --- (20)


또는 아래와 같이 수렴속도를 조절하기 위한 step size를 포함하는 형태도 가능하다 (ν>0).


 --- (21)


단, xk=(x1k,...,xnk), ∇E(xk)는 x = xk에서의 E의 그레디언트(gradient) 값, HE(xk)는 x = xk에서의 E의 헤시안(Hessian) 값을 나타낸다.


 --- (22)


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

식 (20) 또는 식 (21)을 이용하면 뉴턴법을 비선형 최소자승 문제에 직접 적용하는 것도 가능은 하다. 하지만 E(p) = ∑ri(p)2가 두 번 미분가능해야 하며 E(p)의 2차 미분까지 계산해야 하는 부담이 존재한다. 따라서 비선형 최소자승 문제의 경우에는 뉴턴법 대신에 일차 미분만으로 해의 계산이 가능한 가우스-뉴턴법이 사용된다.



4. 가우스-뉴턴법


가우스-뉴턴법은 일종의 뉴턴법의 변형된 형태로서 비선형 최소자승 문제에 대한 대표적인 최적화 방법 중 하나이다. 앞서 뉴턴법을 최적화 문제에 적용할 경우에는 2차 미분이 필요하지만 가우스-뉴턴법을 이용하면 1차 미분만으로 해를 찾을 수 있다.


앞서와 같이 관측값을 (xi, yi), i=1,...,n, 모델 파라미터를 p = ( p1, p2, ..., pm) , 모델을 y = f(x, p), 오차(residual)를 ri(p) = yi - f(xi,p)라 하고 최소화시키고자 하는 목적함수를 E(p)라 하자.


 --- (23)


이 때, E(p)를 최소화시키는 즉, E'(p) = 0으로 만드는 가우스-뉴턴 해는 모델 파라미터 p에 대한 초기 추정값 p0=(p10,...,pm0)에서 시작하여 p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다.


 --- (24)


단, Jr은 Jr(pk)를 간략히 표현한 것으로서 pk에서의 r의 야코비언(Jacobian) 행렬값을 나타낸다.


 --- (25)


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


 --- (26)


여기서 가우스-뉴턴법의 식 (26)를 잘 보면 뉴턴법의 식 (18)을 다변수 벡터함수의 경우로 일반화시킨 형태임을 알 수 있다.


참고로, 비선형 가중최소자승(weighted least squares) 문제의 경우에 가우스-뉴턴 해는 다음 수식에 의해 구해진다.


 --- (27)


[가우스-뉴턴법의 원리] 가우스-뉴턴법의 핵심 원리는 비선형 함수를 지역적으로 선형함수로 근사하여 해를 구하는데 있다. 오차벡터 r(p) = [r1(p) ... rn(p)]T를 테일러 전개를 이용하여 pk 근처에서 선형함수로 근사하면 r(p) ~ r(pk) + Jr(pk)(p - pk)가 된다(2차 이상의 항은 무시). 그런데, 선형근사된 오차에 대해 오차 제곱합 ∥r(pk)+Jr(pk)(p-pk)∥2을 최소화시키는 p를 구해보면 식 (26)의 p = pk - pinv(Jr(pk))r(pk)가 나옴을 알 수 있다. 즉, 가우스-뉴턴법은 현재의 파라미터 추정값(pk) 근처에서 에러함수를 선형근사하여 최소자승 해(pk+1)를 구하고, 구해진 해 근처에서 다시 에러 함수를 선형근사하여 최소자승 해를 구하는 방식으로 점진적으로 해를 찾아간다.


[적용예제] 예를 들어 세 점 (x1,y1), (x2,y2), (x3,y3)를 삼각함수 y = cos(ax + b)로 근사시키는 문제를 가우스-뉴턴법으로 풀어보자. 이 경우 모델 파라미터는 p = (a, b)이며 먼저 r(p)과 Jr(p)를 구해보면 다음과 같다.


 --- (28)


이제 적절한 초기 추정값 p0 = (a0, b0)부터 시작하여 다음 식에 따라 p를 수렴할 때까지 갱신함으로써 해를 찾는다.


 --- (29)



5. Levenberg-Marquardt 방법


앞서 언급한 바와 같이 Levenberg–Marquardt 방법은 가우스-뉴턴법(Gauss–Newton method)과 gradient descent 방법이 결합된 형태로서 해로부터 멀리 떨어져 있을 때는 gradient descent 방식으로 동작하고 해 근처에서는 가우스-뉴턴 방식으로 해를 찾는다. 그런데 Levenberg–Marquardt 방법은 가우스-뉴턴법보다 안정적으로 해를 찾을 수 있으며(초기값이 해로부터 멀리 떨어진 경우에도 해를 찾을 확률이 높음) 비교적 빠르게 해에 수렴하기 때문에 비선형 최소자승문제에 있어서는 대부분 Levenberg–Marquardt 방법이 사용된다.


Levenberg-Marquardt 방법은 Levenberg 알고리즘(1944년)을 1963년에 Marquardt가 보완한 것이다. 빠른 비교 및 참조를 위해 gradient descent 방법, 가우스-뉴턴법, Levenberg 방법, Levenberg-Marquardt 방법의 업데이트 식을 함께 적어보면 다음과 같다.


[Gradient descent 방법]

 --- (16)'


[가우스-뉴턴법]

 --- (24)'


[Levenberg 방법]

 --- (30)


[Levenberg-Marquardt 방법]

 --- (31)


단,

 --- (32)


먼저 gradient descent 방법은 그레디언트의 반대방향으로 이동하되 그레디언트의 크기에 비례한 step size 만큼씩 이동하면서 해(에러함수를 최소화시키는 극소점)를 찾아가는 방법이다.


반면에 가우스-뉴턴법은 함수의 그레디언트와 곡률(curvature)을 같이 고려하면서 해를 찾아가는 방식이다(식에서 JrTJr는 이차미분인 Hessian의 의미를 가지며(Hessian에 대한 근사행렬) 함수의 곡률을 나타낸다). 즉, 이동할 step size를 (그레디언트의 크기)/(곡률의 크기)로 결정하는 방식인데, 기울기(그레디언트)가 크더라도 곡률이 크면(기울기의 변화가 급격하면) 조금만 이동하고, 곡률이 작다면(기울기의 변화가 거의 없으면) 좀더 크게 이동함으로써 극소점을 찾아가는 방식이다. 따라서, 가우스-뉴턴법은 gradient descent 방법보다 훨씬 정확하고 빠르게 해를 찾을 수 있다는 장점을 갖는다. 그런데, 가우스-뉴턴법을 살펴보면 계산 과정에 (JrTJr)의 역행렬 계산을 필요로 한다. 따라서 (JrTJr)가 singular 행렬(역행렬이 존재하지 않는 행렬)에 근접한 경우에는 계산된 역행렬이 수치적으로 불안정하여 해가 발산할 수 있는 문제점이 있다.


Levenberg 방법은 가우스-뉴턴법을 개선하여 JrTJr에 항등행렬(identity matrix)의 상수배 μI를 더함으로써 발산의 위험성을 낮추고 보다 안정적으로 해를 찾을 수 있도록 한 방법이다. 상수 μ(μ>0)를 damping factor라 부르는데 μ값이 작으면 Levenberg 방법은 가우스-뉴턴법과 유사해지고 μ값이 크면 gradient descent 방법과 유사해진다. 수식에서 μ→∞ 면 (JrTJr+μI)-1→1/μI이므로 μ가 커지면 Levenberg 방법은 스텝의 크기가 1/μ인 gradient descent 방법과 유사해짐을 알 수 있다. 그런데, Levenberg 방법에서 damping factor μ는 고정된 값이 아니라 매 iteration마다 바뀌는 값으로서 현재 안정적으로 해에 수렴하고 있을 경우에는 작은 값을 주고 해를 잘 찾지 못하고 있을 경우에는 큰 값을 주는 방법을 사용한다. 좀더 구체적으로 설명하면, 현재 단계에서 계산된 에러 E(pk)가 이전의 에러 E(pk-1)에 비해 잘 감소하고 있으면 μk에 작은 값을 사용하여 가우스-뉴턴 방식으로 해를 찾고 오히려 에러가 증가하거나 에러 감소가 충분치 않은 경우에는 μk를 증가시켜서 gradient descent 방식으로 해를 찾는 방식이다.


Levenberg-Marquardt 방법은 기존의 Levenberg의 방법을 1963년에 Marquardt가 좀더 개선시킨 방법을 일컫는다. 원래의 Levenberg 방법은 μ가 큰 경우에 step size가 1/μ인 gradient descent 방법과 유사해짐은 앞서 설명한 바 있다. 하지만 이 경우 수렴 속도가 느린 문제점이 있다. Marquardt는 이러한 문제를 보완하기 위해 항등행렬 I 대신에 diag(JrTJr) 더해주는 방식을 제안하였다(diag(A)는 A의 대각원소는 유지하고 나머지 원소들의 값을 0으로 만든 대각행렬을 나타냄). JrTJr은 원래 헤시안(Hessian)에 대한 근사행렬의 의미를 갖기 때문에 JrTJr의 대각 원소들은 각 파라미터 성분(pi)에 대한 곡률(curvature)를 나타낸다. 즉, Levenberg-Marquardt 방법은 가우스-뉴턴법의 singular 문제를 피하면서도 μ가 큰 경우에도 곡률(curvature)을 반영하여 효과적으로 해를 찾을 수 있도록 한 방법이다.


☞ Levenberg-Marquardt 방법은 가우스-뉴턴법의 damped version으로서 다른 말로 damped least-squares (DLS) 방법이라고도 불린다.


마지막으로 다시 한번 Levenberg-Marquardt 방법을 정리해 보면 아래와 같다.


[Levenberg-Marquardt 알고리즘]

관측값을 (xi, yi), i=1,...,n, 모델 파라미터를 p = ( p1, p2, ..., pm) , 모델을 y = f(x, p), 오차(residual)를 ri(p) = yi - f(xi,p)라 하고 최소화시키고자 하는 목적함수를 E(p) = ∑ri(p)2라 하자. E(p)를 최소화시키는 해는 모델 파라미터 p에 대한 초기 추정값 p0=(p10,...,pm0)에서 시작하여 p를 다음 수식에 의해 반복적으로 갱신함으로써 얻어진다.


 --- (33)


만일 목적함수가 E(p) = ∑wi*ri(p)2 형태인 경우 즉, 가중최소자승(weighted least squares) 문제의 경우에는 업데이트 식이 다음과 같다.


 --- (34)


단, W = diag(w1,...,wn), r=[r1,...,rn]T, p=[p1,...,pm]T, Jr은 rp로 미분한 야코비언(Jacobian) 행렬


 --- (35)


식 (33), (34)에서 μ는 매 iteration마다 변하는 damping factor로서 μ를 어떻게 계산하느냐에 따라서 다양한 방식의 Levenbarg-Marquardt 알고리즘 구현이 가능하다. 구체적인 방법은 조금씩 다르겠지만 그 기본적인 원리는 현재의 μ값을 가지고 p를 갱신했을 때 E(p)가 증가했다면 E(p)가 감소할 때까지 μ를 계속 증가시키고, E(p)가 감소하면 μ를 원래의 기본적으로 설정된 값(최소값)으로 낮추는 원리이다.


실제 구체적인 구현 알고리즘, Matlab 코드 및 C/C++ 구현 코드에 대해서는 아래 자료들을 참조한다 (제가 직접 돌려보거나 그런 것은 아니니 저한테 사용법은 묻지 마시길..).



6. 마무리하며


마지막으로 초기값에 대한 얘기를 하고 글을 마무리합니다. 앞서 나온 gradient descent 방법, Gauss-Newton 방법, Levenberg-Marquardt 방법 등은 공통적으로 파라미터(p)에 대한 초기 추정값을 필요로 합니다. 그리고 기본적으로 이러한 방법들은 local 해를 찾는 방법들이기 때문에 초기값을 어떻게 주느냐에 따라서 그 결과가 달라질 수 있습니다. 따라서 초기값은 가능한 한 실제 해에 가까운 값을 줄수록 좋은 결과를 얻을 수 있습니다. 즉, 정확도는 떨어지더라도 대략적이나마 해를 구할 수 있는 방법이 있다면 먼저 그 방법으로 해를 찾은 후에 그 해를 초기값으로 해서 앞서의 최적화 기법들을 적용하는 것이 효과적입니다. 정 초기값에 대한 정보가 없다면 파라미터 공간을 일정한 간격으로 샘플링한 후 그 중 목적함수를 최소화시키는 파라미터 값을 초기값으로 설정할 수도 있을 것입니다.


☞ 위에 설명한 여러 함수 최적화 기법들의 실제 적용예에 대해서는 [기계학습] - 대수적 에러와 기하학적 에러(Algebraic & Geometric Error) 글을 참조하시기 바랍니다.


☞ 막상 글을 써 놓고 보니 수식만 잔뜩 있는 글이 되고 말았습니다 ㅠㅠ. 그림도 넣고 실제 예제도 돌려보면서 결과를 비교해 보면 더 좋았을 텐데요.. 하지만 글이 너무 길어지고 또 기력이 다한 관계로 이쯤에서 마무리합니다. 너무 이론적인 내용이라 읽기가 쉽지는 않겠지만 공부하는 학생이나 알고리즘 개발자, 연구자 등에게는 알아두면 도움이 되리라 생각합니다.



by 다크 프로그래머


  • 밥버러지 2014.09.04 11:07 신고 ADDR 수정/삭제 답글

    선리플 후감상!! ^^ 항상 좋은 글 감사합니다..
    BA를 돌릴 때 LM 방법이 자주 사용된다고 맨날 논문에 나와있지만, 정작 어떻게 동작하는지 아무리 읽어봐도 애매모호하고... 그냥 Gauss-Newton과 gradient method의 짬뽕(?)이다 라는 것만 알고 넘어갔었는데 이번 기회에 확실하게 이해할 수 있을 것 같네요!! 감사합니다!
    아, 그리고 알고 계실수도 있지만...
    http://ceres-solver.org/
    구글느님들도 사용하는 비선형 최적화 툴인 Ceres solver가 아마 위의 설명을 구현해논 것이겠죠?? 저도 잘은 모르지만 아마 공개된 비선형 최적화 툴중에 최고의 성능이 아닐까... 생각합니다.

    • BlogIcon 다크pgmr 2014.09.04 12:03 신고 수정/삭제

      관련 링크에 추가하였습니다 ^^ 감사합니다

  • BlogIcon deepcujay 2014.10.01 11:00 신고 ADDR 수정/삭제 답글

    올리신 글 잘 보고 있어요~ 3. Gauss Method에 대해 설명할 때 f 대신 r로 표기하는 게 r=y-f(p)를 최소화하는 것이 목표기 때문에 맞는 게 아닌가 생각이 드네요~ 아님 제가 잘못 이해한 건지ㅜ 표기가 갑자기 달라져서 헷갈렸던 것 같아요~

    • BlogIcon 다크pgmr 2014.10.01 21:04 신고 수정/삭제

      안녕하세요. 말씀하신 부분이 어느 곳인지 좀더 정확히 알려주시면 좋을 것 같습니다. 3.은 뉴턴법이고, 가우스는 4.라서.. 어느 곳인지 ㅠ.ㅠ

    • BlogIcon deepcujay 2014.10.02 11:02 신고 수정/삭제

      아 순간 착각을;;ㅎㅎ 3. 뉴턴법, 그리고 2. gradient descent에서의 f의 정의가 1. 최소자승법 & 가중최소자승법를 설명할 때하고 달라져서 헷갈렸던 것 같아요.

    • BlogIcon 다크pgmr 2014.10.04 07:03 신고 수정/삭제

      네 이제 말씀하신 내용을 이해했습니다. ^^
      말씀하신데로 r로 바꾸다 보니 E가 좀더 낳을 것 같아서 E로 내용을 수정했습니다. 감사합니다.

  • deepblue 2014.11.17 18:25 신고 ADDR 수정/삭제 답글

    최적화에 대해서 잘배우고 갑니다~
    한가지 궁금한게 있습니다~ 식 (23) 아래 단락 첫번째 줄에
    E(p)를 최소화시키는 즉, E(p) = 0 라고 하셨는데
    E(p)를 최소화시키는 즉, E'(p) = 0 가 아닌지 여쭤보고 싶습니다~

    • BlogIcon 다크pgmr 2014.11.17 22:39 신고 수정/삭제

      네, 말씀하신 내용이 맞는 것 같습니다.
      좋은 지적 감사합니다. 내용도 수정하였습니다.

  • apple 2014.12.18 00:48 신고 ADDR 수정/삭제 답글

    LM알고리즘은 Jacobian matrix를 구하는데 상당히 많은 메모리를 필요로 합니다.
    (P*M)*N (P는 Number of training pattern, M은 Number of output, N은 Number of weight)
    Jacobian matrix를 연산하기 위해 위에 해당하는 만큼 메모리가 필요합니다.
    MNIST 데이터셋의 경우 784차원으로 이루어진 6만개의 데이터로 이루어져 있으니 35GB가 필요합니다. 때문에 Matrix Algebra를 이용해 N*N만큼의 메모리를 요구하는 연산을 적용해야 큰 데이터셋을 학습 시킬 수 있습니다. 최근 참고한 논문에서 이런 내용이 있었습니다. 구현해내려면 시간이 좀 걸릴것 같습니다.
    Reference : Wilamowski, Bogdan M., and Hao Yu. "Improved computation for Levenberg–Marquardt training." Neural Networks, IEEE Transactions on 21.6 (2010): 930-937.

  • 초기값질문 2015.02.12 17:52 신고 ADDR 수정/삭제 답글

    좋은 글 잘 보았습니다! 마지막에 초기값에 대한 정보가 없을때 해결하는 방법을 제시해 주셧는데, 초기값이 여러개면 어떻게 해야할까요? 예를 들어 패러미터가 3개면, 각각패터미처를 10등분한다쳐도 처음에 어림짐작해야할 초기값만 10*10*10 으로 너무 많아지는데....

    • BlogIcon 다크pgmr 2015.02.13 10:36 신고 수정/삭제

      10*10*10 = 1,000 번 정도면 대입해 볼만 하다고 생각됩니다만.. 저는 잘 모르지만 이론적으로 초기값 문제를 접근하는 방법도 있는 것 같습니다. http://www.researchgate.net/post/How_can_I_find_a_good_initial_guess_for_thin_film_optimization_process 글을 참조해 보시면 도움이 될 것 같습니다.

  • 초보자 2015.03.23 14:23 신고 ADDR 수정/삭제 답글

    Levenberg-Marquardt 과 Broyden's method의 차이를 알고 싶습니다.

    • BlogIcon 다크pgmr 2015.03.24 06:24 신고 수정/삭제

      Broyden 방법은 일종의 Quasi-Newton 방법으로 알고 있습니다. 자세한 내용은 http://en.wikipedia.org/wiki/Broyden's_method를 참조하시기 바랍니다.

  • BlogIcon 다크사랑 2015.06.06 21:44 신고 ADDR 수정/삭제 답글

    사랑합니다 다크님.
    이번에도 많이 배우고 갑니다.
    LM algorithm에 대한 설명 및 친절한 예제코드가
    http://people.duke.edu/~hpgavin/ce281/lm.pdf
    에 있네여

  • 공돌이 2015.12.03 08:51 신고 ADDR 수정/삭제 답글

    식 (28)은 y = cos(ax + b)에 근사시키는 것 같은데... 아닌가용??

    • BlogIcon 다크pgmr 2015.12.03 09:19 신고 수정/삭제

      그렇네요. 수정하였습니다. 감사합니다 ^^

  • SH 2015.12.09 12:18 신고 ADDR 수정/삭제 답글

    많이 배우고 갑니다
    좋은 글 정말 감사합니다 ^^

  • BlogIcon 공동 2016.07.25 11:02 신고 ADDR 수정/삭제 답글

    잘 정리 되어있어서, 알기 쉬웠습니다 ㅇ
    솔직히 말해서 이쪽 분야가 아니라 심층있게 공부하기엔 좀 시간이 필요해서, 염치불구하고 여쭈어보고봅니다...
    Gradient descent 법이랑, reduced gradient법이랑 다른건가요?
    어떤 책에는 전자는 탐색 방법이고 후자는 무슨 경계조건을 두어서 푸는거라 하던데, 정확하게 어떠한 차이랑 알고리즘의 차이가 있는지 궁금합니다 ;

    • BlogIcon 다크pgmr 2016.07.27 22:50 신고 수정/삭제

      저도 reduced gradient 방법에 대해서는 잘 알지 못합니다..

  • niceyeop 2017.03.29 09:48 신고 ADDR 수정/삭제 답글

    좋은글 너무 감사드립니다~

  • cbbak 2017.11.27 20:36 신고 ADDR 수정/삭제 답글

    Levenberg-Marquardt algorithm을 공부하다가 방문하게 되었습니다. 식 1번을 보면 arg min 이라고 앞에 쓰여 있는데 이부분이 의미하는게 수학적으로 어떤건지 설명해주시면 감사하겠습니다.

    • BlogIcon 다크pgmr 2017.11.28 08:22 신고 수정/삭제

      arg는 argument의 약자입니다. 그래서 arg min f(x)은 f(x) 값을 최소로 만드는 x값을 반환합니다. 반면에, min f(x)는 f(x)의 최소값을 반환합니다. 식 (1)에서는 argument가 p이기 때문에 수식을 최소로 만드는 p 값을 p*로 한다는 의미입니다.

  • okssi 2017.12.26 17:54 신고 ADDR 수정/삭제 답글

    (31), (33) 식이 뭔지 알수 있을까요? ㅡㅡ; 요즘 식이 안뜨는 곳이 많아졌네요..

    • BlogIcon 다크pgmr 2017.12.27 13:27 신고 수정/삭제

      특별히 그 수식만 다르게 한 건 없습니다.. 크롬(chrome)에서도 잘 안보이나요? 블로그의 수식은 LaTex로 입력하면 서버가 이미지로 변환해서 페이지에 보여주는 방식인데, 입력한 Latex 식은 p_{ k+1 }=p_{ k }-(J_{ r }^{ T }J_{ r }+\mu _{ k }diag(J_{ r }^{ T }J_{ r }))^{ -1 }J_{ r }^{ T }r(p_{ k }),\quad k\ge 0 입니다.

  • okssi 2017.12.27 16:44 신고 ADDR 수정/삭제 답글

    핸드폰으로 보면 보이는군요..ㅡㅡ; 회사 네트워크에서 뭘 막는가 봅니다..
    어쨋든 정보 감사합니다~ 여기 사이트를 완전 정독 하고 있는데 이해하는데 너무 많은 도움이 됩니다. 감사합니다~~!!

  • JS 2018.04.25 13:37 신고 ADDR 수정/삭제 답글

    안녕하세요 !! 존경하는 다크프로그래머님 학부생부터 계속 다크프로그래머님 글 보면서 많은 도움을 받고 있는데요. 제가 궁금한 내용이 있어서 질문 합니다..
    현재 가우스-뉴턴법을 만들고 있는데요. 가우스-뉴턴법에서 (J_transpose * J)의 역행렬 부분이 있잖아요. 역행렬이 존재하지 않는 경우가 발생하면 어떻게 처리를 해야 할까요? 조언 해주시면 정말 감사하겠습니다 ㅠ

    • BlogIcon 다크pgmr 2018.04.25 14:11 신고 수정/삭제

      안녕하세요. J^TJ가 singular하게 되는 경우는 가우스-뉴턴법의 최대 문제점으로서 가우스-뉴턴법으로는 해결이 안됩니다. 가우스-뉴턴법의 이런 단점을 해결하기 위해서 나온 방법이 LM(Levenverg-Marquardz) 방법이니 그러한 경우에는 LM 방법을 적용해 보시면 좋을 것 같습니다. LM 방법은 JTJ 대신에 (JTJ + lambda*diag(JTJ))^-1를 사용해서 역행렬이 존재하지 않는 경우를 방지한 방법입니다. LM 적용이 힘드시면, 간단하게는 (JTJ + lambda*I) (I: 항등행렬)와 같이 역행렬이 존재하지 않는 경우에 한해서 적당한 양수 lambda에 대해 JTJ에 lambda*I를 더해주는 방법을 써보면 어떨까 싶습니다.

    • JS 2018.04.25 14:37 신고 수정/삭제

      답변 정말정말 감사합니다 !! ㅠㅠ

    • JS 2018.06.25 02:28 신고 수정/삭제

      안녕하세요. 이전에 글을 올렸는데 궁금하게 있었다가, 잘 몰라서 다크프로그래머님께 다시한번 궁금증을 여쭤봅니다. 혹시 lambda의 크기가 어느정도가 좋은지 알수 있을까요?? 처음에 저는 단순히 매우작은 값이 좋다고 생각하긴했는데.. 이게 맞는지... 너무 작으면 오히려 안좋을수도 있을까라는 생각이 들기도해서 글을 올립니다. 제가 지식이 낮아서 모르는 것이 많네요ㅠㅠ. lambda는 어느정도의 크기가 좋을지 조언좀 해주실 수 있으신가요?

    • BlogIcon 다크pgmr 2018.06.26 00:50 신고 수정/삭제

      lambda는 고정된 값이라기 보다는 상황에 따라 변하는 값입니다. 기본적으로는 현재 스텝에서 에러가 잘 줄어들면 값을 줄여주고, 에러가 증가하면 lambda도 키워줍니다. 구체적인 구현이나 샘플코드에 대해서는 위키피디아(https://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm)나 구글링을 해 보면 좋을 것 같습니다.

    • JS 2018.06.26 10:17 신고 수정/삭제

      답변 감사합니다