이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

최소제곱(모델 피팅) 알고리즘

최소제곱 정의

일반적으로 최소제곱은 제곱의 합인 함수의 국소 최소점인 벡터 x를 구하는 문제이며, 일부 제약 조건이 적용될 수 있습니다.

minxF(x)22=minxiFi2(x)

적용되는 조건은 A·x ≤ b, Aeq·x = beq, lb ≤ x ≤ ub입니다.

다양한 유형의 F(x)와 다양한 유형의 제약 조건에 대해 여러 Optimization Toolbox™ 솔버를 사용할 수 있습니다.

솔버F(x)제약 조건
mldivideC·x – d없음
lsqnonnegC·x – dx ≥ 0
lsqlinC·x – d범위, 선형
lsqnonlin일반 F(x)범위
lsqcurvefitF(x, xdata) – ydata범위

Optimization Toolbox 솔버에는 mldivide에서 사용되는 알고리즘 외에 다음과 같은 네 가지 최소제곱 알고리즘이 있습니다.

  • Trust-region-reflective

  • Levenberg-Marquardt

  • lsqlin의 interior-point

  • lsqnonneg에서 사용하는 알고리즘

모든 알고리즘은 대규모입니다. 대규모 알고리즘과 중간 규모 알고리즘 비교 항목을 참조하십시오. 비선형 최소제곱 방법에 대한 일반적인 설문 조사는 데니스(Dennis)의 문헌 [8]을 참조하십시오. Levenberg-Marquardt 방법에 대한 구체적인 세부 사항은 모레(Moré)의 문헌 [28]에서 확인할 수 있습니다.

Trust-Region-Reflective 최소제곱

Trust-Region-Reflective 최소제곱 알고리즘

Optimization Toolbox 솔버에 사용되는 대부분의 방법이 최적화의 단순하지만 강력한 개념인 신뢰 영역을 기반으로 합니다.

최적화에 대한 trust-region 접근법을 이해하기 위해 제약 조건이 없는 최소화 문제를 살펴보고, f(x)를 최소화해 보겠습니다. 여기서 함수는 벡터 인수를 받고 스칼라를 반환합니다. n 공간에서 점 x에 있고 향상, 즉 더 낮은 함수 값을 가지는 점으로 이동하기를 원한다고 가정해 보겠습니다. 기본적인 발상은 점 x 주위에 있는 이웃 N에서 함수 f의 동작을 잘 반영하는 더 간단한 함수 q를 사용하여 f를 근사하는 것입니다. 이 이웃을 신뢰 영역이라고 합니다. 시행 스텝 s는 N에 대한 최소화(또는 근사 최소화)를 수행하여 계산됩니다. 이를 trust-region 하위 문제라고 하며, 다음과 같습니다.

mins{q(s), sN}.(1)

현재 점은 f(x + s) < f(x)인 경우 x + s가 되도록 업데이트됩니다. 그렇지 않은 경우 현재 점은 변경되지 않고 그대로 유지되며 신뢰 영역 N은 축소되고 시행 스텝 계산이 반복됩니다.

f(x)를 최소화하기 위한 특정 trust-region 접근법을 정의할 때 고려해야 할 핵심 질문은 근삿값 q(현재 점 x에서 정의됨)를 선택하고 계산하는 방법은 무엇인가, 신뢰 영역 N을 선택하고 수정하는 방법은 무엇인가, 그리고 trust-region 하위 문제를 얼마나 정확하게 풀 수 있는가입니다. 이 섹션에서는 제약 조건이 없는 문제를 집중적으로 설명합니다. 뒷부분에 나오는 섹션에서는 변수에 대한 제약 조건이 존재함으로 인해 복잡성이 얼마나 가중되는지에 대해 설명합니다.

표준 trust-region 방법([48])에서는 2차 근삿값 q가 x에서 F에 대한 테일러 근사의 처음 두 항으로 정의되며, 이웃 N은 일반적으로 구면 또는 타원 형태입니다. 수학적으로 trust-region 하위 문제는 대개 다음과 같이 표기됩니다.

min{12sTHs+sTg  such that  DsΔ},(2)

여기서 g는 현재 점 x에서 f의 기울기이고, H는 헤세 행렬(2계 도함수의 대칭 행렬)이고, D는 대각 스케일링 행렬이고, Δ는 양의 스칼라이며, ∥ . ∥는 2-노름입니다. 수식 2를 푸는 데 사용할 수 있는 좋은 알고리즘이 있습니다([48] 참조). 이러한 알고리즘은 일반적으로 다음과 같은 고유방정식에 적용되는 뉴턴 과정 및 비희소(Full) 고유 시스템에 대한 계산을 포함합니다.

1Δ1s=0.

이러한 알고리즘은 수식 2에 대한 정확한 해를 제공합니다. 하지만, 이 알고리즘을 사용하려면 H에 대한 여러 행렬 분해에 비례하는 시간이 필요합니다. 따라서, trust-region 문제에 대해서는 다른 접근법이 필요합니다. 참고 문서([42][50])에서 여러 근사법과 발견법(Heuristic) 전략(수식 2 기반)이 제안되었습니다. Optimization Toolbox 솔버에서 따르는 근사 접근법은 trust-region 하위 문제를 2차원 부분공간 S([39][42])로 제한하는 것입니다. 부분공간 S가 계산되고 나면 수식 2를 푸는 방법은 간단합니다. 비희소 고유값/고유벡터 정보가 필요한 경우에도 마찬가지입니다. 그 이유는 부분공간에서는 문제가 2차원뿐이기 때문입니다. 이제 수행해야 하는 주된 작업은 부분공간을 결정하는 것입니다.

2차원 부분공간 S는 아래에 설명되어 있는 선조건 적용 켤레 기울기법 과정의 도움을 받아 결정됩니다. 솔버는 S를 s1 및 s2에 의해 생성되는 선형 공간으로 정의합니다. 여기서 s1은 기울기 g의 방향이고 s2는 근사 뉴턴 방향, 즉 다음 수식에 대한 해를 말합니다.

Hs2=g,(3)

또는 다음과 같은 음의 곡률의 방향입니다.

s2THs2<0.(4)

이러한 S 선택의 바탕이 되는 철학은 (최속강하법 방향 또는 음의 곡률 방향을 통해) 전역 수렴을 강제 적용하고 (존재하는 경우 뉴턴 스텝을 통해) 신속하게 국소 수렴을 달성한다는 것입니다.

trust-region 알고리즘을 사용한 제약 조건이 없는 최소화 과정은 이제 다음과 같이 간단하게 요약할 수 있습니다.

  1. 2차원 trust-region 하위 문제를 정식화합니다.

  2. 수식 2를 풀어서 시행 스텝 s를 결정합니다.

  3. f(x + s) < f(x)이면 x = x + s입니다.

  4. Δ를 조정합니다.

이 네 단계는 수렴할 때까지 반복됩니다. trust-region 차원 Δ는 표준 규칙에 따라 조정됩니다. 특히, 시행 스텝이 받아들여지지 않은 경우, 즉 f(x + s) ≥ f(x)인 경우에는 trust-region 차원이 축소됩니다. 이 사항에 대한 자세한 내용은 [46] 항목과 [49] 항목을 참조하십시오.

Optimization Toolbox 솔버는 비선형 최소제곱, 2차 함수, 선형 최소제곱 등의 특화된 함수를 사용하여 f에 대한 몇 가지 중요한 특수 사례를 처리합니다. 하지만, 기반이 되는 알고리즘적 발상은 일반적인 사례와 동일합니다. 이러한 특수 사례에 대해서는 뒷부분에 나오는 섹션에서 설명합니다.

대규모 비선형 최소제곱

f(x)의 중요한 특수 사례는 다음과 같은 비선형 최소제곱 문제입니다.

minxifi2(x)=minxF(x)22,(5)

여기서 F(x)는 F(x)의 성분 i가 fi(x)와 동일한 벡터 값 함수입니다. 이 문제를 푸는 데 사용되는 기본 방법은 비선형 최소화를 위한 Trust-Region 방법에 설명되어 있는 일반적인 사례와 동일합니다. 그러나, 효율성을 높이기 위해 비선형 최소제곱 문제의 구조가 이용됩니다. 특히, 근사 가우스-뉴턴 방향, 즉 다음에 대한 해 s가

minJs+F22,(6)

(여기서 J는 F(x)의 야코비 행렬임) 2차원 부분공간 S를 정의하는 데 도움이 되도록 사용됩니다. 성분 함수 fi(x)의 2계 도함수는 사용되지 않습니다.

각 반복마다 선조건 적용 켤레 기울기 방법이 정규 방정식, 즉 다음에 대한 근사해를 구하기 위해 사용됩니다.

JTJs=JTF,

정규 방정식이 명시적으로 구성되지 않은 경우에도 마찬가지입니다.

대규모 선형 최소제곱

이 사례에서 풀려는 함수 f(x)는 다음과 같습니다.

f(x)=Cx+d22,

여기에는 선형 제약 조건이 적용될 수 있습니다. 이 알고리즘은 제한 내에서 국소해로 수렴하는 엄밀히 실현 가능한 반복을 생성합니다. 각 반복에는 대규모 선형 시스템(차수가 n, 여기서 n은 x의 길이)의 근사해가 포함됩니다. 반복 행렬은 행렬 C의 구조를 갖습니다. 특히, 선조건 적용 켤레 기울기법은 정규 방정식, 즉 다음에 대한 근사해를 구하기 위해 사용됩니다.

CTCx=CTd,

정규 방정식이 명시적으로 구성되지 않은 경우에도 마찬가지입니다.

부분공간 trust-region 방법은 탐색 방향을 결정하는 데 사용됩니다. 하지만, 비선형 최소화 사례에서처럼 스텝을 (가능한) 하나의 반사 스텝으로 제한하는 대신 2차 문제의 사례에서와 마찬가지로 각 반복마다 구간별 반사 직선 탐색이 수행됩니다. 직선 탐색에 대한 자세한 내용은 [45] 항목을 참조하십시오. 궁극적으로, 선형 시스템은 해에서의 1차 최적성 조건을 포착하는 뉴턴 접근법을 나타내며, 그 결과 강한 국소 수렴 속도가 실현됩니다.

야코비 행렬의 곱셈 함수.  lsqlin은 행렬 C를 명시적으로 사용하지 않고 선형 제약 조건이 있는 최소제곱 문제를 풀 수 있습니다. 대신, 다음과 같이 야코비 행렬의 곱셈 함수 jmfun을 사용합니다.

W = jmfun(Jinfo,Y,flag)

이 함수는 사용자가 직접 제공합니다. 이 함수는 행렬 Y에 대해 다음 곱을 계산해야 합니다.

  • flag == 0이면 W = C'*(C*Y)입니다.

  • flag > 0이면 W = C*Y입니다.

  • flag < 0이면 W = C'*Y입니다.

이는 C가 크지만 그 구조가 C를 명시적으로 구성하지 않고 jmfun을 작성하는 것으로 충분한 경우에 유용할 수 있습니다. 예제는 Jacobian Multiply Function with Linear Least Squares 항목을 참조하십시오.

Interior-Point 선형 최소제곱

lsqlin'interior-point' 알고리즘은 quadprog의 interior-point-convex 알고리즘을 사용합니다. quadprog 문제 정의는 다음과 같이 2차 함수를 최소화하는 것입니다.

minx12xTHx+cTx

여기에는 선형 제약 조건과 범위 제약 조건이 적용됩니다. lsqlin 함수는 벡터 Cx – d에 대한 2-노름의 제곱 값을 최소화하며, 여기에는 선형 제약 조건과 범위 제약 조건이 적용됩니다. 다시 말해서, lsqlin은 다음을 최소화합니다.

Cxd22=(Cxd)T(Cxd)=(xTCTdT)(Cxd)=(xTCTCx)(xTCTddTCx)+dTd=12xT(2CTC)x+(2CTd)Tx+dTd.

이는 H 행렬을 2CTC로 설정하고 c 벡터를 (–2CTd)로 설정하면 quadprog 프레임워크에 잘 맞습니다. 부가 항 dTd는 최솟값의 위치에 아무런 영향도 미치지 않습니다. 이렇게 lsqlin 문제를 다시 정식화한 후, quadprog'interior-point-convex' 알고리즘은 해를 계산합니다.

참고

quadprog'interior-point-convex' 알고리즘에는 두 개의 코드 경로가 있습니다. 하나는 헤세 행렬 H가 double형으로 구성된 일반(비희소) 행렬인 경우 실행하고, 다른 하나는 H가 희소 행렬인 경우 실행합니다. 희소 데이터형에 대한 자세한 내용은 희소 행렬 (MATLAB) 항목을 참조하십시오. 일반적으로, 이 알고리즘은 H를 sparse로 지정하는 경우 0이 아닌 항이 상대적으로 적은 큰 문제에서 더 빠릅니다. 이와 유사하게, 이 알고리즘은 H를 full로 지정하는 경우 상대적으로 조밀한 문제 또는 작은 문제에서 더 빠릅니다.

Levenberg-Marquardt 방법

최소제곱 문제에서는 제곱의 합인 함수 f(x)가 최소화됩니다.

minxf(x)=F(x)22=iFi2(x).(7)

이 유형의 문제는 다수의 실제 응용 사례에서 나타나며, 특히 모델 함수를 데이터에 피팅할 때, 즉 비선형 파라미터 추정 시 나타납니다. 이러한 문제는 또한 출력값 y(x,t)가 벡터 x와 스칼라 t에 대해 어떤 연속(continuous) 모델 궤적 φ(t)를 따르기를 원하는 경우 이를 제어하는 데에도 많이 나타납니다. 이 문제는 다음으로 표현할 수 있습니다.

minxnt1t2(y(x,t)φ(t))2dt,(8)

여기서 y(x,t)와 φ(t)는 스칼라 함수입니다.

적절한 구적법 식을 사용하여 적분이 이산화되면 위 문제는 최소제곱 문제로 정식화될 수 있습니다.

minxnf(x)=i=1m(y¯(x,ti)φ¯(ti))2,(9)

여기서 y¯φ¯는 구적법 규칙의 가중치를 포함합니다. 참고로, 이 문제에서 벡터 F(x)는 다음과 같습니다.

F(x)=[y¯(x,t1)φ¯(t1)y¯(x,t2)φ¯(t2)...y¯(x,tm)φ¯(tm)].

이러한 유형의 문제에서는 현실적으로 실현 가능한 목표 궤적을 설정하는 것이 보통이므로 잔차 ∥F(x)∥는 최적해에서 작은 값이 될 가능성이 큽니다. 제약 조건이 없는 최적화 관련 기본 사항의 설명에 나와 있듯이, LS의 함수는 제약 조건이 없는 일반적인 최소화 기법을 사용하여 최소화할 수 있지만 문제의 특정한 특성은 풀이 절차의 반복 효율성을 향상시키는 데 종종 이용될 수 있습니다. LS의 기울기와 헤세 행렬은 특수한 구조를 가집니다.

F(x)의 mxn 야코비 행렬을 J(x)로 나타내고, f(x)의 기울기 벡터를 G(x)로 나타내고, f(x)의 헤세 행렬을 H(x)로 나타내고, 각 Fi(x)의 헤세 행렬을 Hi(x)로 나타내면 다음을 얻게 됩니다.

G(x)=2J(x)TF(x)H(x)=2J(x)TJ(x)+2Q(x),(10)

여기서는 다음이 성립합니다.

Q(x)=i=1mFi(x)Hi(x).

행렬 Q(x)는 xk가 해에 접근함에 따라 잔차 ∥F(x)∥가 0에 가까워지는 경향이 있을 때 Q(x)도 0에 가까워지는 경향이 있다는 속성을 가집니다. 따라서 ∥F(x)∥가 해에서 작은 값을 갖는 경우, 최적화 절차의 근간으로 가우스-뉴턴 방향을 사용하는 것이 매우 효과적입니다.

가우스-뉴턴 방법에서 탐색 방향 dk는 다음과 같은 선형 최소제곱 문제의 해인 각각의 주 반복 k에서 구해집니다.

minxnJ(xk)F(xk)22.(11)

이 방법에서 도출된 방향은 Q(x)의 항이 무시될 수 있는 경우 뉴턴 방향과 동일합니다. 탐색 방향 dk를 직선 탐색 전략의 일부로 사용하여 각 반복마다 함수 f(x)가 감소하도록 할 수 있습니다.

2차 항 Q(x)가 유의미한 경우 가우스-뉴턴 방법에서 종종 문제가 발생할 수 있습니다. 이 문제를 해결하는 방법은 Levenberg-Marquardt 방법입니다.

Levenberg-Marquardt [25][27] 방법은 다음과 같은 선형 방정식 세트

(J(xk)TJ(xk)+λkI)dk=J(xk)TF(xk),(12)

또는, 선택적으로 다음 방정식의 해인 탐색 방향을 사용합니다.

(J(xk)TJ(xk)+λkdiag(J(xk)TJ(xk)))dk=J(xk)TF(xk),(13)

여기서 스칼라 λk는 dk의 크기와 방향을 모두 제어합니다. 옵션 ScaleProblem'none'으로 설정하여 수식 12를 선택하고 ScaleProblem'Jacobian'으로 설정하여 수식 13을 선택합니다.

InitDamping 옵션을 사용하여 파라미터 λ0의 초기값을 설정할 수 있습니다. 경우에 따라, 이 옵션의 디폴트 값 0.01이 적합하지 않을 수 있습니다. Levenberg-Marquardt 알고리즘이 초기에 거의 진척이 없는 것으로 확인되면 InitDamping을 디폴트 값이 아닌 다른 값, 1e2 등으로 설정해 보십시오.

λk가 0이면 방향 dk는 가우스-뉴턴 방법의 방향과 동일합니다. λk가 무한대로 가려 함에 따라 dk는 최속강하법 방향을 향하려 하며, 크기는 0에 가까워지려 합니다. 이는 충분히 큰 어떤 λk에 대해 항 F(xk + dk) <  F(xk)이 성립한다는 것을 의미합니다. 따라서 가우스-뉴턴 방법의 효율성을 제한하는 2차 항이 발생한 경우에도 하강을 계속하도록 항 λk를 제어할 수 있습니다. 스텝이 성공적(낮은 함수 값을 제공함)일 경우 알고리즘은 λk+1 = λk/10을 설정합니다. 스텝이 성공적이지 않을 경우 알고리즘은 λk+1 = λk*10을 설정합니다.

내부적으로, Levenberg-Marquardt 알고리즘은 최적성 허용오차(중지 기준) 1e-4에 함수 허용오차를 곱한 값을 사용합니다.

따라서 Levenberg-Marquardt 방법은 가우스-뉴턴 방향과 최속강하법 방향을 번갈아 이용하는 탐색 방향을 사용합니다. 이에 대해서는 그림 11-1. 로젠브록 함수에 대해 실행된 Levenberg-Marquardt 방법에 설명되어 있습니다. 로젠브록 함수(Rosenbrock Function)의 해는 가우스-뉴턴 방법을 사용하는 경우의 48회에 비해 90회의 함수 실행 후에 수렴합니다. 이렇게 효율성이 더 낮은 이유 중 하나는 잔차가 해에서 0인 경우 가우스-뉴턴 방법이 일반적으로 더 효과적이기 때문입니다. 하지만 이러한 정보를 항상 미리 알 수는 없으며, Levenberg-Marquardt 방법의 더 높은 견고성이 가끔 발생하는 낮은 효율성을 보상해 줍니다.

그림 11-1. 로젠브록 함수에 대해 실행된 Levenberg-Marquardt 방법

반복 점을 생성하는 스크립트를 포함하여 위 그림에 대한 더 자세한 설명을 보려면 Banana Function Minimization 항목을 참조하십시오.