가우스-뉴턴 알고리즘

가우스-뉴턴 알고리즘()은 비선형 최소제곱법 문제를 해결하는 데 사용되며, 이는 함수 값의 제곱합을 최소화하는 것과 같다. 이 알고리즘은 비선형 함수의 최솟값을 찾기 위한 뉴턴 방법의 확장이다. 제곱합은 반드시 비음수여야 하므로, 이 알고리즘은 뉴턴 방법을 사용하여 합의 각 성분의 근을 반복적으로 근사함으로써 합을 최소화하는 것으로 볼 수 있다. 이런 의미에서 이 알고리즘은 과결정 연립방정식을 푸는 데에도 효과적인 방법이다. 계산하기 어려울 수 있는 2계 도함수가 필요하지 않다는 장점이 있다.

비선형 최소제곱 문제는 예를 들어 비선형 회귀에서 발생하는데, 여기서는 모델이 가용 관측치와 잘 일치하도록 모델의 매개변수를 찾는다.

이 방법은 수학자 카를 프리드리히 가우스와 아이작 뉴턴의 이름을 따서 명명되었으며, 가우스의 1809년 저작인 《Theoria motus corporum coelestium in sectionibus conicis solem ambientum》에 처음 등장했다.

 설명 
개의 변수 를 가진 개의 함수 (흔히 잔차라고 함)가 주어지고 일 때, 가우스-뉴턴 알고리즘은 제곱합을 최소화하는 의 값을 반복법으로 찾는다.Björck (1996)

최솟값에 대한 초기 추측치 에서 시작하여, 이 방법은 다음과 같은 반복을 거친다.

여기서 r과 β가 열벡터라면, 야코비 행렬의 성분은 다음과 같다.

그리고 기호 는 행렬 전치를 나타낸다.

매 반복마다 업데이트 는 이전 방정식을 다음 두 단계로 재배열하여 찾을 수 있다.

, , 로 치환하면, 이는  형태의 전형적인 행렬 방정식이 되며, 다양한 방법으로 풀 수 있다(내용주 참조).

만약 이라면, 이 반복은 다음과 같이 단순화된다.

이는 1차원에서의 뉴턴 방법을 직접적으로 일반화한 것이다.

주어진 모델 함수 가 일부 데이터 포인트 에 가장 잘 맞도록 매개변수 를 찾는 데이터 피팅에서, 함수 는 잔차이다.

그러면 가우스-뉴턴 방법은 함수 의 야코비 행렬 을 사용하여 다음과 같이 표현될 수 있다.

여기서 는 의 왼쪽 무어-펜로즈 유사역행렬이다.

 내용주 
알고리즘 설명에서 이라는 가정은 필수적인데, 그렇지 않으면 행렬 의 역행렬이 존재하지 않아 정규 방정식을 (적어도 유일하게) 풀 수 없기 때문이다.

가우스-뉴턴 알고리즘은 함수 벡터 ri를 선형 근사하여 유도할 수 있다. 테일러 정리를 사용하면 매 반복마다 다음과 같이 쓸 수 있다.

여기서 이다. 우변의 제곱합을 최소화하는 를 찾는 작업, 즉

은 선형 최소제곱 문제이며, 이를 명시적으로 풀면 알고리즘의 정규 방정식이 도출된다.

정규 방정식은 미지수 증분 에 대한 n개의 연립 선형 방정식이다. 이는 숄레스키 분해를 사용하거나, 더 좋게는 의 QR 분해를 사용하여 한 단계 만에 풀 수 있다. 대규모 시스템의 경우 켤레기울기법과 같은 반복법이 더 효율적일 수 있다. 만약 Jr의 열 사이에 선형 종속성이 있으면 이 특이 행렬이 되므로 반복이 실패한다.

이 복소수 인 경우 켤레 형태인 를 사용해야 한다.

 예시 
이 예시에서는 가우스-뉴턴 알고리즘을 사용하여 데이터와 모델 예측값 사이의 오차 제곱합을 최소화함으로써 모델을 데이터에 피팅한다.

효소 매개 반응에서 기질 농도 와 반응 속도 사이의 관계를 연구하는 생물학 실험에서 다음 표의 데이터를 얻었다.
  1  2  3  4  5  6  7  0.038  0.194  0.425  0.626   1.253   2.500   3.740 속도 0.050  0.127  0.094  0.2122  0.2729  0.2665  0.3317

최소제곱 의미에서 데이터에 가장 잘 맞는 다음과 같은 형태의 곡선(모델 함수)을 찾고자 한다.

여기서 매개변수 와 을 결정해야 한다.

에 대해 와 속도의 값을 각각 와 로 나타내자. 이고 이라 하자. 잔차의 제곱합

이 최소화되도록 하는 과 를 찾을 것이다.

미지수 에 대한 잔차 벡터 의 야코비 행렬 은 번째 행이 다음과 같은 성분을 갖는  행렬이다.

 및 라는 초기 추측값으로 시작하여, 가우스-뉴턴 알고리즘을 5번 반복한 후 최적값 와 을 얻는다. 잔차 제곱합은 초기값 1.445에서 5번의 반복 후 0.00784로 감소했다. 오른쪽 그림의 그래프는 최적 매개변수로 결정된 모델 곡선과 관측 데이터를 보여준다.

 수렴 특성 
가우스-뉴턴 반복은 다음 4가지 조건 하에서 국소 최솟값 로 수렴함이 보장된다. 함수 이 열린 볼록 집합 에서 2회 연속 미분 가능하고, 야코비 행렬 이 풀 컬럼 랭크(full column rank)를 가지며, 초기 반복값 이 에 가깝고, 국소 최솟값 이 작아야 한다. 만약 이면 수렴은 2차 수렴(quadratic)이다.

증분 Δ가 에 대한 하강 방향이며, 알고리즘이 수렴한다면 그 극한은 의 임계점임을 보일 수 있다.Björck (1996), p. 260. 그러나 최솟값 이 큰 경우에는 수렴이 보장되지 않으며, 뉴턴 방법과 같은 국소 수렴이나 통상적인 울프 조건(Wolfe conditions) 하에서의 수렴도 보장되지 않는다.

가우스-뉴턴 알고리즘의 수렴 속도는 2차 수렴에 가까워질 수 있다.Björck (1996), p. 341, 342. 초기 추측치가 최솟값에서 멀거나 행렬 의 상태가 나쁘면(ill-conditioned) 알고리즘이 느리게 수렴하거나 전혀 수렴하지 않을 수 있다. 예를 들어 개의 방정식과 개의 변수를 가진 다음 문제를 고려해 보자.

일 때 은 국소 최적점이다. 만약 이면 문제는 실제로 선형이며 방법은 한 번의 반복으로 최적점을 찾는다. |λ| < 1이면 방법은 선형적으로 수렴하고 오차는 매 반복마다 점진적으로 요인 |λ|만큼 감소한다. 그러나 |λ| > 1이면 방법은 국소적으로조차 수렴하지 않는다.Fletcher (1987), p. 113.

 과결정 연립방정식 풀기 
가우스-뉴턴 반복

은  형태의  과결정 연립방정식을 푸는 효과적인 방법이다. 여기서 이고 는 의 야코비 행렬 의 무어-펜로즈 유사역행렬이다.
이는 뉴턴 방법의 확장으로 간주될 수 있으며 격리된 정규해에 대해 동일한 국소 2차 수렴을 누린다.

해는 존재하지 않지만 초기 반복값 이 제곱합 이 작은 국소 최솟값에 도달하는 점  근처에 있다면, 가우스-뉴턴 반복은 로 선형적으로 수렴한다. 점 는 종종 과결정 시스템의 최소제곱 해라고 불린다.

 뉴턴 방법으로부터의 유도 

다음에서는 근사를 통해 함수 최적화를 위한 뉴턴 방법으로부터 가우스-뉴턴 알고리즘을 유도한다. 그 결과 가우스-뉴턴 알고리즘의 수렴 속도는 특정 정칙성 조건 하에서 2차 수렴이 될 수 있다. 일반적인 경우(더 약한 조건 하에서) 수렴 속도는 선형적이다.

매개변수 의 함수 S를 최소화하기 위한 뉴턴 방법의 점화식은 다음과 같다.

여기서 g는 S의 기울기 벡터를 나타내고, H는 S의 헤세 행렬을 나타낸다.

이므로 기울기는 다음과 같이 주어진다.

헤세 행렬의 원소는 기울기 원소 를 에 대해 미분하여 계산한다.

가우스-뉴턴 방법은 2계 도함수 항(이 식의 두 번째 항)을 무시함으로써 얻어진다. 즉, 헤세 행렬은 다음과 같이 근사된다.

여기서 는 야코비 행렬 Jr의 성분이다. 정확한 피팅 근처에서 정확한 헤세를 평가할 때 가 거의 0이 되므로 두 번째 항도 거의 0이 되어 이 근사가 정당화된다. 기울기와 근사된 헤세 행렬은 행렬 표기법으로 다음과 같이 쓸 수 있다.

이러한 표현을 위의 점화식에 대입하여 다음과 같은 연산 방정식을 얻는다.

가우스-뉴턴 방법의 수렴이 모든 경우에 보장되는 것은 아니다. 2계 도함수 항을 무시할 수 있기 위해 성립해야 하는 근사치

는 다음과 같은 두 가지 경우에 유효할 수 있으며, 이 경우 수렴이 기대된다.Nocedal (1999), p. 259.
 함수 값 가 적어도 최솟값 주변에서 크기가 작을 때.
 함수가 "약하게" 비선형적이어서 가 상대적으로 크기가 작을 때.

 개선된 버전 
가우스-뉴턴 방법을 사용하면 잔차 제곱합 S가 매 반복마다 감소하지 않을 수도 있다. 그러나 Δ가 하강 방향이므로 가 임계점이 아닌 한, 충분히 작은 모든 에 대해 가 성립한다. 따라서 발산이 발생하는 경우 한 가지 해결책은 업데이트 공식에서 증분 벡터 Δ의 일부인 를 사용하는 것이다.

즉, 증분 벡터가 너무 길지만 여전히 "내리막"을 가리키고 있으므로 그 길의 일부만 가면 목적 함수 S를 줄일 수 있다. 에 대한 최적값은 직선 탐색 알고리즘을 사용하여 찾을 수 있다. 즉, 의 크기는 보통  구간에서의 직접 탐색법이나 아르미호(Armijo) 직선 탐색과 같은 백트래킹 직선 탐색을 사용하여 S를 최소화하는 값을 찾아 결정된다. 일반적으로 는 울프 조건이나 골드슈타인(Goldstein) 조건을 만족하도록 선택해야 한다.

이동 벡터의 방향 때문에 최적 분율 α가 0에 가까운 경우, 발산을 처리하기 위한 대안적인 방법은 신뢰 영역 방법인 레벤버그-마쿼트 알고리즘(Levenberg–Marquardt algorithm)을 사용하는 것이다. 정규 방정식은 증분 벡터가 최속 하강 방향으로 회전하도록 다음과 같이 수정된다.

여기서 D는 양의 대각 행렬이다. D가 단위 행렬 I이고 일 때, 이 되므로, Δ의 방향은 음의 기울기 방향인 에 가까워진다.

소위 마쿼트 매개변수 도 직선 탐색에 의해 최적화될 수 있지만, 이는 가 바뀔 때마다 이동 벡터를 다시 계산해야 하므로 비효율적이다. 더 효율적인 전략은 발산이 발생하면 S가 감소할 때까지 마쿼트 매개변수를 늘리는 것이다. 그런 다음 한 반복에서 다음 반복까지 그 값을 유지하되, 컷오프 값에 도달할 때까지 가능하면 줄여서 마쿼트 매개변수를 0으로 설정할 수 있게 한다. 그러면 S의 최소화는 표준 가우스-뉴턴 최소화가 된다.

 대규모 최적화 
대규모 최적화에서 가우스-뉴턴 방법은 특별히 관심을 받는데, 왜냐하면 (항상은 아니지만) 행렬 이 근사 헤세 행렬 보다 더 성긴 경우가 많기 때문이다. 이러한 경우 단계 계산 자체는 일반적으로 켤레기울기법과 같이 크고 성긴 문제에 적합한 근사 반복법으로 수행해야 한다.

이러한 접근 방식이 작동하게 하려면 적어도 다음과 같은 곱을 계산하는 효율적인 방법이 필요하다.

어떤 벡터 p에 대해서 말이다. 성긴 행렬 저장 방식에서는 일반적으로 의 행을 압축된 형태(예: 0이 아닌 원소만)로 저장하는 것이 실용적인데, 전치로 인해 위의 곱을 직접 계산하는 것이 까다로울 수 있다. 그러나 ci를 행렬 의 행 i로 정의하면 다음과 같은 간단한 관계가 성립한다.

따라서 모든 행은 곱에 가산적이고 독립적으로 기여한다. 실용적인 성긴 저장 구조를 존중하는 것 외에도, 이 표현식은 병렬 컴퓨팅에 매우 적합하다. 모든 행 ci는 해당 잔차 ri의 기울기라는 점에 유의하라. 이를 염두에 두면 위의 공식은 잔차가 서로 독립적으로 문제에 기여한다는 사실을 강조한다.

 관련 알고리즘 
다비돈(Davidon), 플레처(Fletcher), 파월(Powell)에 의한 방법이나 브로이든-플레처-골드파브-샤노(BFGS 방법)와 같은 준뉴턴 방법에서는 1계 도함수 만을 사용하여 전체 헤세 행렬 의 추정치를 수치적으로 구축하여 n번의 정교화 사이클 후에 성능 면에서 뉴턴 방법에 가깝게 근사한다. 준뉴턴 방법은 일반적인 실숫값 함수를 최소화할 수 있는 반면 가우스-뉴턴, 레벤버그-마쿼트 등은 비선형 최소제곱 문제에만 적합하다는 점에 유의하라.

1계 도함수만을 사용하여 최소화 문제를 해결하는 또 다른 방법은 경사 하강법이다. 그러나 이 방법은 2계 도함수를 근사적으로도 고려하지 않는다. 결과적으로 많은 함수에서, 특히 매개변수 간의 상호작용이 강한 경우 매우 비효율적이다.

 구현 예시 
 줄리아 
줄리아의 다음 구현은 제공된 야코비 행렬을 사용하는 방법과 자동 미분을 사용하여 계산하는 방법을 제공한다.
"""
    gaussnewton(r, J, β₀, maxiter, tol)

야코비 J가 있는 잔차 함수 r을 최소화하기 위해 β₀에서 시작하여 가우스-뉴턴 최적화를 수행한다. 단계의 노름이 tol보다 작거나 maxiter번 반복한 후 알고리즘이 종료된다.
"""
function gaussnewton(r, J, β₀, maxiter, tol)
    β = copy(β₀)
    for _ in 1:maxiter
        Jβ = J(β);
        Δ  = -(Jβ' * Jβ) \ (Jβ' * r(β))
        β += Δ
        if sqrt(sum(abs2, Δ)) < tol
            break
        end
    end
    return β
end

import AbstractDifferentiation as AD, Zygote
backend = AD.ZygoteBackend() # 다른 백엔드도 사용 가능

"""
    gaussnewton(r, β₀, maxiter, tol)

β₀에서 시작하여 잔차 함수 r을 최소화하기 위해 가우스-뉴턴 최적화를 수행한다. 관련 야코비 행렬은 자동 미분을 사용하여 계산된다. 단계의 노름이 tol보다 작거나 maxiter번 반복한 후 알고리즘이 종료된다.
"""
function gaussnewton(r, β₀, maxiter, tol)
    β = copy(β₀)
    for _ in 1:maxiter
        rβ, Jβ = AD.value_and_jacobian(backend, r, β)
        Δ  = -(Jβ[1]' * Jβ[1]) \ (Jβ[1]' * rβ)
        β += Δ
        if sqrt(sum(abs2, Δ)) < tol
            break
        end
    end
    return β
end

 각주 

 참고 문헌 

 .

 외부 링크 
 Probability, Statistics and Estimation 이 알고리즘이 자세히 설명되어 있으며 이 문서에서 예시로 논의된 생물학 실험에 적용되었다 (추정값의 불확실성과 함께 84페이지).

 구현 
 Artelys Knitro는 가우스-뉴턴 방법이 구현된 비선형 솔버이다. C로 작성되었으며 C++/C#/Java/Python/MATLAB/R용 인터페이스가 있다.

분류:통계 알고리즘
분류:최소제곱법
분류:최적화 알고리즘 및 방법