선형 최소 제곱법(Linear Least Squares)

[경고] 아래 글을 읽지 않고 "선형 최소 제곱법"을 보면 바보로 느껴질 수 있습니다.

1. QR 분해

2. 행렬의 고유치와 고유 벡터

3. 양의 정부호 행렬

함수의 최대값 혹은 최소값을 구하는 문제는 현실에서도 매우 중요하다. 예를 들면 [그림 1]에 있는 2차 함수(quadratic function)를 본다.

[그림 1] 아래로 볼록한 2차 함수(출처: wikipedia.org)

[그림 1]의 2차 함수는 아래로 볼록하기 때문에 최소값을 가진다. 직관적으로는 최소값이 있다고 바로 알 수 있지만, 수학적으로 [그림 1]의 함수가 최소값이 있다는 사실은 어떻게 알 수 있을까? 함수 $f(x)$를 두 번 미분하면 함수가 아래로 볼록한지 알 수 있다. 즉 1차 미분이 $0$이 되는 점이 존재하고[$f^{\prime }(x)$ = $0$], 이 점에서 2차 미분이 $0$보다 크면[$f^{″}(x)>0$] $f(x)$는 아래로 볼록하다. [그림 1]에 사용한 2차 함수는 $x^2-x-2$이다. 이 함수에 적용한 평행 이동을 제거하고 보면, 일반형은 $f(x)$ = $a{x}^2$이 된다. 따라서 $a>0$이면 간단하게 아래로 볼록이라고 할 수 있다. 이 경우 모든 $x$에 대해 $f(x)\ge 0$가 성립하므로, $f(x)$는 양의 준정부호(陽의 準正符號, positive semi-definiteness)를 가진다고 한다. 비슷하게 모든 $x$에 대해 $f(x)>0$라면 $f(x)$는 양의 정부호(陽의 正符號, positive definiteness)를 가진다고 한다.

아래로 볼록한 2차 함수의 특성을 기억하면서 다음과 같은 벡터 크기[정확히는 벡터 노름(vector norm) $\Vert \cdot {\Vert }_2$ 혹은 유클리드 노름(Euclidean norm)]의 제곱을 고려한다.

                  (1)

여기서 $\mathbf{A}$는 행렬(matrix), $\mathbf{x}$와 $\mathbf{b}$는 열 벡터(column vector), $(\cdot {)}^T$는 전치 행렬(transpose)이다. 식 (1)은 행렬을 포함하고 있지만 제곱 형태이며 아래로 볼록하기 때문에 양의 준정부호를 가진다. 또한 $\mathbf{x}$가 다음 조건을 만족하는 위치에서 식 (1)은 최소값을 가진다.

                  (2)

따라서 식 (1)의 최소값을 구하면 자연스럽게 1차 연립 방정식인 식 (2)를 풀게 된다. [그림 1]처럼 식 (1)은 $\mathbf{x}$에 대해 아래로 볼록함은 명확하다. 그래서 $\mathbf{x}$의 원소인 $x_i$에 대해 식 (1)을 편미분해서 $0$으로 둔다.

             (3)

식 (3)에 의해 원소 $x_i$에 관계없이 만족해야 하는 행렬 방정식은 다음과 같다.

                  (4)

행렬 $\mathbf{A}$가 정방 행렬이며 역행렬이 있다면 통상적인 방정식의 해법과 동일하다.

                  (5)

식 (4)의 강점은 $\mathbf{A}$가 정방 행렬이 아닐 때 드러난다. 1차 연립 방정식에서 미지수의 개수와 방정식의 개수는 반드시 같아야 한다. 하지만 식 (4)는 미지수보다 방정식의 개수가 클 때에도 미지수를 식 (1)과 같은 제곱 형태로 추정하도록 해준다. 그래서 식 (4)를 최소 제곱 근사(least squares approximation)의 범주에 있는 선형 최소 제곱법(linear least squares)이라 부른다. 통계(statistics) 분야에서는 식 (4)를 정규 방정식(normal equation)이라고도 한다. 최소 제곱 근사에 등장하는 행렬과 전치 행렬의 곱 ${\mathbf{A}}^T\mathbf{A}$는 최소 제곱 행렬(least squares matrix)로 정의한다.

[그림 2] 줄자로 동전의 직경을 재는 모습(출처: wikipedia.org)

하지만 굳이 미지수보다 방정식을 더 만들어서 식 (4)처럼 복잡하게 계산할 필요가 있을까? [그림 2]와 같은 측정 과정을 생각한다. 측정에는 반드시 잡음(noise)이나 불확도(uncertainty)가 생겨서 동일한 측정을 하더라도 결과는 다르게 나온다. 이 경우 측정으로부터 참값을 추정할 효과적인 방법은 무엇일까? 이 질문에 대한 해답이 제곱의 합을 활용하는 최소 제곱 근사이다. 통계에서 제곱의 합은 우리가 잘 아는 분산(分散, variance)에 쓰인다. 측정의 예를 들면, 원래는 $ax$ = $b$이지만, 잡음이 생겨서 $ax$ = $b+{\nu }_i$가 된다고 가정한다. 여기서 ${\nu }_i$는 $i$번째 측정에 생긴 잡음이다. 동일한 측정을 $n$번 반복한 경우, $x$를 추정하기 위한 최소 제곱 근사는 다음과 같다.

                  (6)

여기서 $E(\nu )$는 잡음 $\nu$의 기대값(expectation or expected value)이다. 보통 잡음의 기대값 혹은 평균은 $0$이므로, 측정 회수 $n$을 늘리면 참값은 $x$ = $b/a$에 수렴한다.

[그림 3] 최소 제곱 근사를 이용한 곡선 맞춤(출처: wikipedia.org)

식 (6)은 매우 간단한 경우를 가정해 얻지만, 식 (4)를 참값 추정에 쓰면 측정에 따라 계수 $a,b$가 바뀌고 $x$가 벡터이더라도 최소 제곱법(least squares) 기반으로 $x$를 잘 추정할 수 있다. 대표적인 예가 직선으로 곡선 맞춤(curve fitting)이다. 측정 결과의 경향성을 직선으로 가정한 경우, 이 직선의 방정식을 찾는 가장 좋은 방법은 최소 제곱법이다. 여러 $(x,y)$ 쌍을 많이 모을수록 식 (6)에 따라 최적인 $a,b$가 도출된다.

[그림 4] 여러 가지 모양의 진주(출처: wikipedia.org)

기대값 혹은 평균(mean or average) 개념은 우연처럼 식 (6)에 갑자기 등장한다. 우리는 당연히 정확한 값을 어림하기 위한 최적의 도구로 통계적 평균을 쓰고 있다. 하지만 원래부터 이런 방식이 통용되지는 않았다. 예를 들어, 보일의 법칙(Boyle's law)으로 유명한 보일Robert Boyle(1627–1691)은 여러 번 측정으로 한 값을 딱 결정하는 방식을 혐오했다[5]. 진주를 예시로 들면서 작은 싸구려 진주 여러 개 보다는 아름답고 큰 진주 하나의 가치가 더 큰 것처럼 한 번 측정을 아주 정확하게 하는 방식이 최선이라고 주장했다.

[그림 5] 균형을 맞춘 지렛대(출처: wikipedia.org)

같은 영국 수학자인 코츠Roger Cotes(1682–1716)는 다르게 생각했다. 아르키메데스Archimedes of Syracuse(대략 기원전 287–212)의 지렛대(lever)에서 착안하여, 초보적인 선형 최소 제곱법으로서의 평균을 제안했다. [그림 5]처럼 양쪽에 물건을 두고 균형을 맞추려면 파란색 쐐기가 균형점에 있어야 한다. 이 균형점은 각 위치 $x_i$의 평균 $\mu$가 된다.

                  (7a)

여기서 무게에 해당하는 $w_i$는 0이거나 양수인 가중치(weight)이다. 모든 가중치의 합을 1로 맞춘 경우, 식 (7a)는 확률 $w_i$에 대응하는 기대값 $E[X]$가 된다. 여기에 더해 각 $w_i$를 표본수의 역수인 $1/n$으로 일치시킨 식 (7a)는 평균이 된다. 지렛대 원리를 쓰지 않고 식 (1)에 나온 제곱의 최소값을 구해도 식 (7)과 동일한 결과를 얻는다.

                  (7b)

여기서 $f^{″}(x)$ = $2\sum _i{w}_i$ $>$ $0$이므로 최소값은 $f^{\prime }(x)$ = $0$인 지점에서 생긴다. 만약 $w_i$를 확률이라 가정하면, 식 (7b)의 왼쪽 식은 분산(variance)이 된다. 즉, 평균은 분산 관계인 식 (7b)를 최소로 만드는 값이다.

최소 제곱 근사의 핵심인 최소 제곱 행렬 ${\mathbf{A}}^T\mathbf{A}$와 $\mathbf{A}{\mathbf{A}}^T$의 다양한 성질을 소개한다.

   1. 기본(basics)   

[대칭 행렬(symmetric matrix)]

최소 제곱 행렬은 대칭 행렬이다.

                  (1.1)

[증명]

식 (1.1)의 첫째식에 전치 행렬(transpose)을 적용하면 다음과 같다.

                  (1.2)

마찬가지로 전치 행렬의 특성에 의해, $\mathbf{A}{\mathbf{A}}^T$도 대칭 행렬이다.

______________________________

식 (1.1)을 다른 관점으로 보면, 행렬 $\mathbf{A}$의 대칭성에 관계없이 행렬을 ${\mathbf{A}}^T\mathbf{A}$ 혹은 $\mathbf{A}{\mathbf{A}}^T$로 만들면 항상 대칭 행렬이 된다. 대칭 행렬의 장점은 고유 벡터(eigenvector)와 결합될 때 나타난다. 대칭 행렬의 고유 벡터는 항상 직교하기 때문에, 고유 벡터로 만든 행렬은 직교 행렬(orthogonal matrix)이 될 수 있다.

[행렬의 계수 혹은 계급수(rank)]

                  (1.3)

[증명]

식 (1.3)은 원래 행렬과 최소 제곱 행렬의 계수(階數, rank)가 같다는 뜻이다. 즉 식 (2), (4)에 있는 1차 연립 방정식의 좌변인 $\mathbf{A}\mathbf{x}$와 ${\mathbf{A}}^T\mathbf{A}\mathbf{x}$의 독립적인 방정식 수가 같음을 의미한다. 따라서 행렬의 계수는 독립적인 방정식의 수를 의미하므로, $\mathbf{A}\mathbf{x}$ = $0$과 ${\mathbf{A}}^T\mathbf{A}\mathbf{x}$ = $0$을 만족하는 $\mathbf{x}$가 같음을 보임으로써 $\mathrm{rank}(\mathbf{A})$ = $\mathrm{rank}({\mathbf{A}}^T\mathbf{A})$를 증명할 수 있다[2]. 먼저 다음 관계식을 살펴본다.

                  (1.4)

여기서 $||\cdot ||$는 행렬식 $|\cdot |$과 구별되는 벡터의 크기[정확히는 벡터 노름(vector norm) $\Vert \cdot {\Vert }_2$ 혹은 유클리드 노름(Euclidean norm)]를 의미한다. 식 (1.4)의 역도 쉽게 증명할 수 있다. 식 $\mathbf{A}\mathbf{x}$ = $0$에 ${\mathbf{A}}^T$를 곱하면 ${\mathbf{A}}^T\mathbf{A}\mathbf{x}$ = $0$이 성립한다. 따라서 다음 두 행렬에 대한 1차 연립 방정식의 해 $\mathbf{x}$는 서로 같다.

                  (1.5)

예를 들어 $\mathbf{A}\mathbf{x}$를 구성하는 모든 방정식이 독립적이면, 역행렬 ${\mathbf{A}}^{-1}$이 존재해서 $\mathbf{x}$는 영 벡터가 된다. 이 결과는 선형 독립(linear independence)의 조건과 동일하다. 일부 방정식이 종속이면, 가우스 소거법(Gaussian elimination)으로 독립인 방정식만 연립해서 정리하면 계수 $\mathrm{rank}(\mathbf{A})$를 계산할 수 있다. 그러면 식 (1.5)에 의해 $\mathrm{rank}({\mathbf{A}}^T\mathbf{A})$도 정해지므로, $\mathrm{rank}(\mathbf{A})$ = $\mathrm{rank}({\mathbf{A}}^T\mathbf{A})$임을 알 수 있다. 이번에는 ${\mathbf{A}}^T\mathbf{y}$ = $0$을 고려한다. 식 (1.5)와 비슷하게 이 식은 $\mathbf{A}{\mathbf{A}}^T\mathbf{y}$ = $0$과 동치(同値, equivalence)이다. 그러면 동일한 방식으로 $\mathrm{rank}(\mathbf{A})$ = $\mathrm{rank}(\mathbf{A}{\mathbf{A}}^T)$를 증명할 수 있다.

______________________________

[양의 준정부호(positive semi-definiteness)]

                  (1.6)

[증명]

식 (1.4)에 의해 항상 식 (1.6)이 성립한다.

______________________________

[고유치(eigenvalue)]

(a) 최소 제곱 행렬의 고유치는 음수가 아니다.

(b) 두 최소 제곱 행렬의 고유치는 서로 같다.

                  (1.7)

여기서 ${\mathbf{A}}^T\mathbf{A}$와 $\mathbf{A}{\mathbf{A}}^T$에 대한 고유 벡터(eigenvector)는 각각 $\mathbf{v}$와 $\mathbf{u}$이다.

[명제 (a)의 증명]

식 (1.6)의 열 벡터를 최소 제곱 행렬 ${\mathbf{A}}^T\mathbf{A}$에 대한 고유 벡터(eigenvector) $\mathbf{v}$로 생각하면 다음과 같다.

                  (1.7)

따라서 좌변이 항상 $0$보다 크거나 같기 때문에, 고유치도 $0$이거나 양수가 되어야 한다. 마찬가지로 $\mathbf{A}{\mathbf{A}}^T$의 고유치도 음수가 아니다.

[명제 (b)의 증명]

식 (1.7)의 첫째식에서 양변에 $\mathbf{A}$를 곱하여 서로 비교해보자[3].

                  (1.8)

그러면 식 (1.7)의 둘째식과 동일한 결과를 얻어서 두 최소 제곱 행렬의 고유치는 같다. 식 (1.7)의 둘째식부터 출발하면 다음 식도 얻을 수 있다.

                  (1.9)

______________________________

식 (1.8), (1.9)를 조합하면 $k_u{k}_v$ = $\lambda$가 된다. 스칼라(scalar) $k_u,k_v$는 임의로 선택할 수 있어서 $k_u$ = $k_v$라 두면, 음수가 아닌 새로운 상수를 $\sigma$ = $k_u$ = $k_v$ = $\sqrt{\lambda }$로 정할 수 있다. 이 경우 $\sigma$를 행렬 $\mathbf{A}$의 특이값(singular value)이라 한다. 특이값의 영어 알파벳이 s로 시작하므로, 특이값의 알파벳은 $\sigma$가 된다. 특이값은 고유치(eigenvalue)와 비슷하지만 서로 구별되도록 다른 이름으로 부른다.[특이값의 원래 이름이 고유치였다.] 특이값 $\sigma$를 이용해서 식 (1.8), (1.9)를 다시 쓰면 다음과 같다.

                  (1.10)

여기서 $\sigma \ge 0$, $\mathbf{u}$와 $\mathbf{v}$는 $\mathbf{A}$ 기준으로 왼쪽과 오른쪽에 위치해서 각각 좌특이 벡터(left-singular vector), 우특이 벡터(right-singular vector)라 부른다.

[벡터 노름(vector norm)]

행렬 $\mathbf{A}\mathbf{x}$에 대한 벡터 노름의 최대값은 최대 특이값이다.

                  (1.11)

여기서 벡터 노름은 유클리드 노름(Euclidean norm), 행렬 $\mathbf{A}$의 차원은 $m\times n$, 열 벡터 $\mathbf{x}$의 크기는 $1$이다.

[증명]

식 (1.11)의 좌변을 제곱해서 식 (1.7)을 대입하면 다음과 같다[4].

                  (1.12)

여기서 $\mathbf{x}$는 정규 직교 기저이며 우특이 벡터인 ${\mathbf{v}}_i$의 선형 결합(linear combination)으로 표현, ${\mathbf{v}}_i$의 특이값은 ${\sigma }_i$, $r$ = $\mathrm{rank}(\mathbf{A})$이다. 열 벡터 $\mathbf{x}$를 정규 직교 기저의 선형 결합으로 표현할 때, 특이값이 $0$인 기저까지 사용할 수도 있다. 하지만 식 (1.12)의 마지막식에 의해, 이 기저는 벡터 노름에 기여하지 않으므로 선형 결합에서 제외한다. 만약 ${\sigma }_1$이 특이값 중에서 최대값이라면, 다음 부등식이 성립한다.

                  (1.13)

따라서 식 (1.13)에 의해 식 (1.11)이 증명된다.

______________________________

식 (1.13)을 보면, 식 (1.11)이 성립하는 경우는 $\mathbf{x}$ = ${\mathbf{v}}_{\text{max}}$일 때이다.

[참고문헌]

[1] G. Strang, Linear Algebra and its Applications, 4th ed., Brooks/Cole, 2006.

[2] G. Gundersen, "Proof of the singular value decomposition," Blog, 2018. (방문일 2020-08-03)

[3] 다크 프로그래머, [선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용, 수학 이야기, 2013. (방문일 2020-08-03)

[4] M. Hutchings, "Notes on singular value decomposition for Math 54," Linear Algebra and Differential Equations, UC Berkeley, 2017. (방문일 2020-08-04)

[5] S. Stahl, "The evolution of the normal distribution", Math. Mag., vol. 79, no. 2, pp. 96–113, Apr. 2006.