Gauss・뉴턴법

Gauss・뉴턴법(Gauss・뉴턴 편, 영: Gauss-Newton method)은, 비선형 최소 이승법을 푸는 방법의 하나이다.이것은 함수의 최대・최소치를 찾아내는 뉴턴법의 수정으로 간주할 수 있다.뉴턴법과는 달라, Gauss・뉴턴법은 제곱화의 최소화 밖에 이용할 수 없지만, 계산하는 것이 곤란한 2층 미분이 불요라고 하는 장점이 있다.

비선형 최소 이승법은 비선형 회귀(영문판)등에서, 관측 데이터를 잘 나타내도록(듯이) 모델의 파라미터를 조정하기 위해서 필요하다.

이 수법의 명칭은 컬・프리드리히・Gauss와 아이작크・뉴턴에 연관된다.

목차

개요

데이터 fitting에 대하고, 주어진 모델 함수 y = f (x ,β)가 m개의 데이터점{(x_i , y_i ); i = 1, ... , m }에 가장 자주(잘) 피트하는 n (□m ) 개[¹]의 파라미터β= (β₁ , ... ,β_n )를 찾아내는 것이 목적이다.

이 때, 잔차를

${\displaystyle r_{i}({\boldsymbol {\beta }})=y_{i}-f(x_{i},{\boldsymbol {\beta }})}$ 

(으)로 한다.

이 때, Gauss・뉴턴법은 잔차의 평방화

${\displaystyle S({\boldsymbol {\beta }})=\sum _{i=1}^{m}(r_{i}({\boldsymbol {\beta }}))^{2}}$ 

의 최소치를 반복 계산으로 요구하는[²].초기 추측치β^(0)로부터 처음으로, 이 방법은 이하의 계산을 반복한다.

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-({J_{r}}^{\mathrm {T} }{J_{r}})^{-1}{J_{r}}^{\mathrm {T} }{\boldsymbol {r}}({\boldsymbol {\beta }}^{(s)}),\quad (s=0,1,2,\dots ).}$ 

여기서

${\displaystyle J_{r}={\frac {\partial r_{i}({\boldsymbol {\beta }}^{(s)})}{\partial \beta _{j}}}}$ 

(은)는β^{(s )에} 있어서의 r의 야코비안, J_r^T는 행렬 J_r의 전치를 나타낸다.

m = n라면, 이 반복 계산은

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-J_{r}^{-1}{\boldsymbol {r}}({\boldsymbol {\beta }}^{(s)})}$ 

(와)과 같이 간략화된다.이것은 1 차원 뉴턴법의 직접적인 일반화이다.

Gauss・뉴턴법은 함수 f의 야코비안 J_f를 이용해 다음 같게 나타낼 수도 있다：

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+({J_{f}}^{\mathrm {T} }{J_{f}})^{-1}{J_{f}}^{\mathrm {T} }{\boldsymbol {r}}({\boldsymbol {\beta }}^{(s)}).}$ 

주석

Gauss・뉴턴법은 함수 r_i를 늘어놓은 벡터의 선형 근사로 주어진다.테일러의 정리를 이용하면, 각 반복에 대하고 차식이 성립된다：

${\displaystyle {\boldsymbol {r}}({\boldsymbol {\beta }})\approx {\boldsymbol {r}}({\boldsymbol {\beta }}^{s})+J_{r}({\boldsymbol {\beta }}^{s}){\boldsymbol {\Delta }}.}$ 

여기서Δ=β-β^s이다.우변의 잔차평방화를 최소화하는Δ을 찾아내는 것, 즉

${\displaystyle \operatorname {min} \left[{{\boldsymbol {r}}({\boldsymbol {\beta }}^{s})+J_{r}({\boldsymbol {\beta }}^{s}){\boldsymbol {\Delta }}_{2}}^{2}\right]}$ 

(은)는 선형 최소 이승법의 문제이기 위해, 햇빛적으로 풀 수 있어 정규 방정식을 준다.여기서 ||*||₂는2-법칙(Euclid 법칙)이다.

정규 방정식은 미지의 증분Δ에 대한 m책의 선형 동다음 방정식이다.이것은 코레 스키 분해를 이용하는 것으로, 또는 보다 좋은 방법으로서는 J_r의 QR분해를 이용하는 것으로, 1 스텝에서 풀 수 있다.큰 계에 대해서는, 공역구배법과 같은 반복 해법이 유효하다.J_r의 열이 선형 종속인 경우, J_r^TJ_r가 비마사노리가 되기 위해 반복 해법은 실패한다.

예

 

이 예로 얻어지고 있는 데이터(낙제점)와${\displaystyle {\hat {\beta }}_{1}=0.362,{\hat {\beta }}_{2}=0.556}$ (으)로부터 계산된 모델 곡선(푸른 선)

여기에서는 예로서 Gauss・뉴턴법을 사용해 데이터와 모델에 의한 예측치의 사이의 잔차평방화를 최소화해, 데이터에 모델을 피트시킨다.

생물 실험에 대하고, 효소 매개 반응에 있어서의 기질 농도[S]와 반응율 v의 관계로서 다음에 있는 표와 같은 데이터를 얻을 수 있었다고 한다(우도의 낙제점).

i	1	2	3	4	5	6	7
[S]	0.038	0.194	0.425	0.626	1.253	2.500	3.740
v	0.050	0.127	0.094	0.2122	0.2729	0.2665	0.3317

이러한 데이터에 대해, 다음 형태의 모델 곡선(미카에리스・멘텐식)의 파라미터 V_max와 K_M를, 최소 제곱의 의미로 가장 자주(잘) 피트하도록(듯이) 결정하고 싶은[³]：

${\displaystyle v={\frac {V_{\mathrm {max} }[\mathrm {S} ]}{K_{\mathrm {M} }+[\mathrm {S} ]}}}$ 

x_i와 y_i (i = 1, ... , 7)으로[S]와 v의 데이터를 나타낸다.또,β₁ = V_max,β₂ = K_M로 한다.잔차

${\displaystyle r_{i}=y_{i}-{\frac {\beta _{1}x_{i}}{\beta _{2}+x_{i}}}\quad (i=1,\dots ,7)}$ 

의 평방화를 최소화하는β₁으로β₂를 찾아내는 것이 목적이 된다.

미지 파라미터β에 관한 잔차벡터 r의 야코비안 J_r는 7×2의 행렬로, i번째의 행은 다음 요소를 가진다：

${\displaystyle {\begin{pmatrix}{\frac {\partial r_{i}}{\partial \beta _{1}}},&{\frac {\partial r_{i}}{\partial \beta _{2}}}\end{pmatrix}}={\begin{pmatrix}-{\frac {x_{i}}{\beta _{2}+x_{i}}},&{\frac {\beta _{1}x_{i}}{\left(\beta _{2}+x_{i}\right)^{2}}}\end{pmatrix}}.}$ 

초기 추정치로서β₁ = 0.9,β₂ = 0.2로부터 시작해 Gauss・뉴턴법에 따르는 5회의 반복 계산을 실시하면, 최적치 ${\displaystyle {\hat {\beta }}_{1}=0.362,{\hat {\beta }}_{2}=0.556}$  하지만 얻을 수 있다.잔차평방화는 5회의 반복 계산으로 초기의 1.445에서 0.00784까지 감소한다.우도는 이러한 최적 파라미터를 이용한 모델로 정해지는 곡선과 실험 데이터라는 비교를 나타낸다.

수습성

증분Δ이 S의 감소 방향을 향하고 있는 것은 증명되고 있는[⁴].만약 이 알고리즘이 수습하면, 그 극한은 S의 정류점이다.그러나 수습에 대해서는, 뉴턴법으로는 보증되고 있는 국소 수습마저도 보증되어 있지 않다.

Gauss・뉴턴법의 수습의 속도(영문판)는 2차인[⁵].만약 초기 추측치가 최소치로부터 먼지, 또는 행렬 J_r^T J_r가 악조건이면 수습은 늦은지, 전혀 하지 않게 된다.예를 들면, m = 2개의 방정식과 n = 1개의 변수가 있는 다음 문제를 생각한다：

${\displaystyle {\begin{aligned}r_{1}(\beta )&=\beta +1\\r_{2}(\beta )&=\lambda \beta ^{2}+\beta -1.\end{aligned}}}$ 

이 문제의 최적치는β= 0이다.만약λ= 0이라면 실질적으로 선형 문제이며, 최적치는 1회의 계산으로 발견된다.만약|λ| < 1이라면, 이 수법은 선형에 수습해 잔차는 계수|λ|그리고 반복 마다 점근적으로 감소한다.그러나|λ| > 1이라면, 이 방법은 이미 국소적으로도 수습하지 않는[⁶].

뉴턴법으로부터의 도출

후에 나타내도록(듯이), Gauss・뉴턴법은 근사 함수의 최적화에 이용되는 뉴턴법으로부터 주어진다.그 결과, Gauss・뉴턴법의 수습의 속도는 거의 2차이다.

파라미터β를 가지는 함수 S의 최소화를 할 때, 뉴턴법에 따르는 점화식은

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}-H^{-1}{\boldsymbol {g}}\,}$ 

이다.여기서 g는 S의 구배 벡터, H는 S의 헷시안이다.${\displaystyle S=\sum _{i=1}^{m}r_{i}^{2}}$ 이기 때문에, 구배 g는 다음으로 주어진다：

${\displaystyle {\boldsymbol {g}}=2{J_{r}}^{\mathrm {T} }{\boldsymbol {r}},\quad {\text{or,}}\quad g_{j}=2\sum _{i=1}^{m}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}.}$ 

헷시안 H는 구배 g를β로 미분 하는 것으로 계산된다：

${\displaystyle H_{jk}=2\sum _{i=1}^{m}\left({\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}+r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right).}$ 

2층 미분항(우변 제 2항)을 무시하는 것으로 Gauss・뉴턴법을 얻는다.즉, 헷시안은

${\displaystyle H\approx 2{J_{r}}^{\mathrm {T} }J_{r},\quad {\text{or,}}\quad H_{jk}\approx 2\sum _{i=1}^{m}{\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}=2\sum _{i=1}^{m}J_{ij}J_{ik}}$ 

(와)과 근사 된다.여기서

${\displaystyle J_{ij}={\frac {\partial r_{i}}{\partial \beta _{j}}}}$ 

(은)는 야코비안 J_r의 성분이다.

이러한 표현을 상술의 점화식에 대입하고, 차식을 얻는다：

${\displaystyle {\boldsymbol {\beta }}^{(s+1)}={\boldsymbol {\beta }}^{(s)}+{\boldsymbol {\Delta }};\quad {\boldsymbol {\Delta }}=-({J_{r}}^{\mathrm {T} }J_{r})^{-1}{J_{r}}^{\mathrm {T} }{\boldsymbol {r}}.}$ 

Gauss・뉴턴법의 수습은 항상 보증되고 있는 것은 아니다.2층 미분항을 무시한다고 하는 근사, 즉

${\displaystyle \left|r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}}\right|\ll \left|{\frac {\partial r_{i}}{\partial \beta _{j}}}{\frac {\partial r_{i}}{\partial \beta _{k}}}\right|}$ 

에 정당성이 있는 것은 다음 2개의 조건아래이며, 이것들이 성립되는 경우에는 수습이 기대되는[⁷]：

1. r_i는 충분히 작다.적어도 최소치 부근.
2. 함수의 비선형성은 온화하고,${\displaystyle {\partial ^{2}r_{i}}/{\partial \beta _{j}\partial \beta _{k}}}$  하지만 비교적 작아진다.

개선 버전

Gauss・뉴턴법은, 초기 추정치가 진정한 해로부터 크게 떨어져 있거나, 모델 함수의 비선형성이 큰 경우에는 안정성이 나쁘다.또, 잔차평방화S는 반복 마다 반드시 감소하는 것은 아니다.그 때문에, 실용상은 안정화가 필요한[⁸].

S는 반복 마다 반드시 감소하는 것은 아니지만, 증분 벡터Δ는 S가 감소할 방향을 향하고 있기 때문에, S (β^s)가 정류점에 없는 한, 임의의 충분히 작은α> 0에 대해서 S (β^s +αΔ) < S (β^s)가 성립된다.따라서, 발산했을 때에, 갱신 방정식에 축소 인자[⁹]α를 도입해

${\displaystyle {\boldsymbol {\beta }}^{s+1}={\boldsymbol {\beta }}^{s}+\alpha {\boldsymbol {\Delta }}}$ 

(으)로 하는 것이 해결법의 하나가 된다.

바꾸어 말하면, 증분 벡터Δ는 목적 함수 S의 하행 방향을 가리키고는 있지만 너무 길므로, 그 길의 아주 일부를 가는 것으로, S를 감소시키려는 아이디어이다.축소 인자α의 최적치는 직선 탐색으로 찾아낼 수 있다.즉, 직접 탐색법을(통상 0 <α□1의 구간에서) 이용하고, S를 최소화하는 값을 찾는 것으로α의 크기는 결정할 수 있다.

최적인 축소 인자α가 0에 가까운 듯한 경우, 발산을 회피하는 다른 방법은 Levenberg-Marquardt 알고리즘(영문판)(신뢰 범위(영문판) 법)를 사용하는 것이다[²].증분 벡터가 최급강하 방향으로 향하도록(듯이) 정규 방정식은 수정된다.

${\displaystyle (J^{\mathrm {T} }J+\lambda D)\Delta =J^{\mathrm {T} }{\boldsymbol {r}},}$ 

여기서 D는 정정치 대 일본 장기 말열이다.λ하지만 0으로부터 증대하는 것에 따라 증분 벡터Δ는 길이가 단조롭게 감소해, 한편 방향은 최급강하 방향으로 가까워지기 위해,λ를 충분히 크게 하면 반드시보다 작은 S의 값을 찾아낼 수 있는 것이 보증되고 있는[¹⁰].

이른바 Marquardt 파라미터λ는 직선 탐색에 의해 최적화되지만,λ이 바뀔 때마다 매회 시프트 벡터의 재계산을 해야 하기 때문에 비효율적이다.보다 효율적인 방법은, 발산이 일어났을 때에λ를 S가 감소할 때까지 증가시킨다.그리고 그 값을 1회의 반복으로부터 다음까지 유지한다, 그러나λ를 0으로 설정할 수 있을 때 만약 컷 오프치에 닿을 때까지 가능하면 감소시킨다.이 때 S의 최소치는 표준의 Gauss・뉴턴법의 최소화가 된다.

관련하는 알고리즘

DFP법(영문판)이나 BFGS법(영문판)과 같은 준뉴턴법으로는, 헷시안${\displaystyle {\partial ^{2}S}/{\partial \beta _{j}\partial \beta _{k}}}$ 의 추정은 1층 미분${\displaystyle {\partial r_{i}}/{\partial \beta _{j}}}$ 만을 이용해 수치적으로 된다.따라서 n회의 반복 계산에 의한 수정의 뒤, 이 방법은 퍼포먼스에 대해 뉴턴법을 근사 한다.Gauss・뉴턴법이나 Levenberg-Marquardt법 등은 비선형 최소 제곱 문제에게만 적용할 수 있는데 대하고, 준뉴턴법은 일반적인 실수치 함수를 최소화할 수 있는 것에 주의한다.

1층 미분만을 사용해 최소화 문제를 푸는 다른 방법은, 최급강하법이다.그러나, 이 방법은 2층 미분을 근사적으로도 고려하고 있지 않고, 그 결과, 이 방법은 많은 함수에 대해서, 특히 파라미터가 강한 상호작용을 가지고 있는 경우는 매우 비효율적이다.

각주

1. ^알고리즘내의 m□n라고 하는 가정은 필요하다.그렇지 않으면, 행렬 J_r^TJ_r의 역행열을 계산하지 못하고, 정규 방정식의 해(적어도 유일해)를 요구할 수 없다.
2. ^ ^{a b} Bjorck (1996)
3. ^미카에리스・멘텐식#실험에 의한 파라미터의 결정으로 설명하도록(듯이), 실제는 변수에[S]^-1으로 v^-1을 선택하는 것으로, 이 문제는 선형 최소 이승법으로서 풀 수 있다.
4. ^ Bjorck (1996) p260
5. ^ Bjorck (1996) p341, 342
6. ^ Fletcher (1987) p.113
7. ^ Nocedal (1997) [^{요점 페이지 번호}]
8. ^나카가와, 코야나기(1982) p. 98
9. ^나카가와, 코야나기(1982) p. 98
10. ^나카가와, 코야나기(1982) p. 102

참고 문헌

• Bjorck, A. (1996). Numerical methods for least squares problems. SIAM, Philadelphia. ISBN 0-89871-360-9. 
• Fletcher, Roger (1987). Practical methods of optimization (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-471-91547-8. .
• Nocedal, Jorge; Wright, Stephen (1999). Numerical optimization. New York: Springer. ISBN 0-387-98793-2. 
• 나카가와 토오루; 코야나기 요시오 「최소 이승법에 따르는 실험 데이터 해석」도쿄대학 출판회, 1982년.ISBN 4-13-064067-4。 

「https://ja.wikipedia.org/w/index.php? title=Gauss・뉴턴법&oldid=57619916」으로부터 취득

This article is taken from the Japanese Wikipedia Gauss・뉴턴법

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.