최소제곱법

1. 최소제곱법(least squares solution)

■ 시각 \( t \)에 대해 얻어진 데이터를 \( f(t) \)라고 할 때, 좌표평면에 유한 개의 데이터를 유한 개의 점 \( (t, f(t)) \)로 나타낸 것이 다음과 같다고 하자.

■ 데이터(유한 개의 점 \( (t, f(t)) \))의 분포를 오차가 최소가 되도록 일차함수 \( y = g(x) \)의 그래프로 근사시키는 방법 중에 '잔차(실제 값과 예측 값의 차)에 대한 제곱'으로 최소가 되도록 하는 방법을 '최소제곱법'이라 한다.

\( \displaystyle \sum_{k=1}^{10} \left[ f(k) - g(k) \right]^2 = \displaystyle \sum_{k=1}^{10} \left[ f(k) - ax - b \right]^2 \)

오차가 최소가 되도록 일차함수로 근사

■ 즉, 최소제곱법이란 주어진 데이터와 오차를 최소화하는 직선을 구하는 방법이다. 위의 예시에서는 그 직선을 찾기 위해 \( a, b \)값을 찾아야 한다.

■ \( a, b \)는 벡터 공간의 개념과 부분 공간 위로의 정사영을 이용하여 찾을 수 있다.

■ \( \displaystyle \sum_{k=1}^{10} \left[ f(k) - g(k) \right]^2 \)는 \( M_{10, 1} \)의 두 벡터 \( \mathbf{f} = (f(1), f(2), \cdots, f(10))^T \)과 \( \mathbf{g} = (g(1), g(2), \cdots, g(10))^T \)에 대해 \( || \mathbf{f} - \mathbf{g} ||^2 \)으로 볼 수 있다.

■ 그리고 일차 함수 \( g(x) = ax + b \)에 대해 벡터 \( \mathbf{g} \)는 \( 10 \times 2 \) 행렬 \( G \)에 \( \mathbf{a} = (a, b)^T \)를 곱한 것으로 볼 수 있다.

- 일차함수 \( y = ax + b \)에서 \( a, b \)는 기울기와 절편(intercept)이며 위의 그림에 있는 \( g(x) = ax + b \)를 \( G \cdot a \)로 다음과 같이 나타낼 수 있다.

■ 이때 행렬 \( G \)의 열벡터는 기울기와 절편에 대한 값으로, \( G \)의 열벡터들은 선형 독립이 된다. 

- 두 열벡터는 서로 스칼라배로 표현할 수 없으므로 선형 독립이다.

■ 그러므로 \( a, b \) 값에 무관하게 \( \mathbf{g} \)는 \( G \)의 두 열벡터로 생성되는 \( M_{10, 2} \)의 부분 공간 \( W = \text{span}\left( \left\{ G_1^C, G_2^C \right\} \right) \)에 속하는 벡터가 된다.

■ 만약, \( \mathbf{f} = (f(1), f(2), \cdots, f(10))^T \)가 \( W \)에 속한다면, 정확하게 \( \mathbf{f} = G \mathbf{a} \)가 되는 \( \mathbf{a} \)가 존재하게 된다. 이는 모든 데이터 점 \( k, f(k) \)가 \( \mathbf{a} = (a, b)^T \)로 결정되는 함수 \( g(x) = ax + b \) 위의 점이 됨을 의미한다.

- \( \mathbf{f} \in W \)라는 것은 벡터 \( \mathbf{f} \)가 \( W \)의 기저 \( \left\{ G_1^C, G_2^C \right\} \)의 선형 결합으로 표현될 수 있다(생성된다)는 의미이다. 

- 즉, 벡터 \( \mathbf{f} \)가 \( G \)의 열공간에 있다는 의미이므로 \( \mathbf{f} = G \mathbf{a} \)가 성립하니, \( (a, b) \)를 알 수 있다.

■ \( \mathbf{a} \)가 부분 공간 \( W \)에 속하지 않는 경우에는 \( W \) 위에 내린 \( \mathbf{f} \)의 정사영 \( \mathbf{w} = \text{proj}_W ( \mathbf{f} ) \)와 \( \mathbf{w}^{\perp} \in W^{\perp} \)에 대해 \( \mathbf{f} = \mathbf{w} + \mathbf{w}^{\perp} \)로 표현할 수 있으므로, \( || \mathbf{f} - \mathbf{g} ||^2 = || \mathbf{w} + \mathbf{w}^\perp - \mathbf{g} ||^2 = || \mathbf{w} - \mathbf{g} ||^2 + || \mathbf{w}^\perp ||^2 \)가 성립한다.

- \( \mathbf{f} \)가 \( W \) 바깥에 있더라도 \( \mathbf{f} \)를 \( W \)에 정사영한 벡터 \( \mathbf{w} \)가 \( \mathbf{f} \)와의 거리(오차)를 가장 작게 해주는 벡터가 된다.

- 그리고 \( W \)가 내적 공간 \( V \) 의 유한차원 부분공간이면, \( V \)의 모든 벡터 \( \mathbf{u} \)는 \( \mathbf{u} = \mathbf{w} + \mathbf{w}^{\perp} \)로 표현할 수 있다. \( \mathbf{w} \)는 \( W \)안의 벡터이고, \( \mathbf{w}^{\perp} \)는 \( W^{\perp} \) 안의 벡터이다.

- 예를 들어 부분 공간 \( W \)를 2차원(평면)이라고 생각해 보자. 그러면 \( W \)와 수직인 공간 \( W^{\perp} \)의 벡터들은 \( W \)라는 평면의 법선 벡터들(법선 벡터와 법선 벡터에 실수배가 곱해진 벡터들)이다.

- \( \mathbf{u} \)가 부분 공간 \( W \)에 속하지 않는 경우,  \( \mathbf{u} \)는 다음과 같이 \( W \)위에 내린 정사영 벡터와 \( W^{\perp} \)의 벡터 \( \mathbf{w}^{\perp} \)에 의해 정의될 수 있다.

- 그러므로,  \( \mathbf{f} = \mathbf{w} + \mathbf{w}^{\perp} \)로 표현할 수 있는 것이다.

■ 여기서 \( || \mathbf{w}^\perp || \)는 고정된 상수이므로, 오차(잔차)가 최소가 될 조건은 \( || \mathbf{w} - \mathbf{g} ||^2 = 0 \)이 되는 것이다.

■ 그리고 \( \left\{ G_1^C, G_2^C \right\} \)가 \( W \)의 기저이고 \( \mathbf{w} \in W \)이므로 \( \mathbf{w} = G \mathbf{a} \Leftrightarrow a G_1^C + b G_2^C \)를 만족하는 \( a, b \)가 유일하게 존재한다. 즉, 오차가 최소가 되는 근사식을 구할 수 있다.

1.1 다항식으로의 근사

■ 위의 예시 내용을 일반화하면, \( m \)개의 데이터 \( (x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m) ⊂ \mathbb{R}^2 \)가 주어졌을 때,

■ 이 \( m \)개 데이터의 분포를 근사적으로 나타내는 \( n ( n < m) \)차 다항식 \( y = f(x) \)를 구하는 방법은 다음과 같이 입력값 \( x_i \)에 대해 함수값 \( f(x_i) \)와 실제값 \( y_i \)의 오차의 합이 최소가 되도록 만드는 것이다.

\( \displaystyle \sum_{i=1}^{m} \left( y_i - f(x_i) \right)^2 \)

이때,  \( \displaystyle \sum_{i=1}^{m} \left( y_i - f(x_i) \right)^2 \)값이 최소가 되는 다항함수 \( f \)를 구하는 방법을 '최소제곱법'이라고 한다.

■ \( \displaystyle \sum_{i=1}^{m} \left( y_i - f(x_i) \right)^2 \)를 벡터로 나타내면 \( || \mathbf{y} - \mathbf{f} ||^2 = < \mathbf{y} - \mathbf{f}, \mathbf{y} - \mathbf{f} > \)이며, 내적 \( < a, b > \)는 \( b^T a \)이므로 \( || \mathbf{y} - \mathbf{f} ||^2 \)를 다음과 같이 나타낼 수 있다.

\( || \mathbf{y} - \mathbf{f} ||^2 = \langle \mathbf{y} - \mathbf{f}, \mathbf{y} - \mathbf{f} \rangle = 
\begin{pmatrix}
y_1 - f(x_1) & y_2 - f(x_2) & \cdots & y_m - f(x_m)
\end{pmatrix}
\begin{pmatrix}
y_1 - f(x_1) \\
y_2 - f(x_2) \\
\vdots \\
y_m - f(x_m)
\end{pmatrix} \)

- \( \mathbf{y} = (y_1, y_2, \cdots, y_m)^T, \quad \mathbf{f} = (f(x_1), f(x_2), \cdots, f(x_m))^T \)

■ \( n(m > n) \)차 다항함수 \( f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n \)에 대해서는 \( \mathbf{f} \)를 다음과 같이 \( m \times (n+1) \)행렬 \( B \)와 \( (n+1) \times 1 \) 열벡터 \( \mathbf{a} \)의 곱으로 나타낼 수 있다.

\( \mathbf{f} =
\begin{pmatrix}
f(x_1) \\
f(x_2) \\
\vdots \\
f(x_m)
\end{pmatrix}
=
\begin{pmatrix}
a_0 + a_1 x_1 + \cdots + a_n x_1^n \\
a_0 + a_1 x_2 + \cdots + a_n x_2^n \\
\vdots \\
a_0 + a_1 x_m + \cdots + a_n x_m^n
\end{pmatrix}
=
\begin{pmatrix}
1 & x_1 & x_1^2 & \cdots & x_1^n \\
1 & x_2 & x_2^2 & \cdots & x_2^n \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & x_m & x_m^2 & \cdots & x_m^n
\end{pmatrix}
\begin{pmatrix}
a_0 \\
a_1 \\
\vdots \\
a_n
\end{pmatrix}
= B \mathbf{a} \)

■ 여기서 행렬 \( B \)의 열벡터 \( B_1^C, B_2^C, \cdots, B_{n+1}^C \)로 생성되는 열공간 \( C(B) \)를 부분 공간 \( W \)라고 하면, \( B \)는 \( W \)의 기저가 된다.

- \( B \)의 각 열벡터가 선형 독립인 이유는 1은 '숫자' \( x \)는 '문자'이기 때문이다.

- 1과 \( x_1 \)에 '숫자'를 곱해서 \( x^2 \)를 만들어 낼 수 없고, 1에 '숫자'를 곱해서 '문자' \( x \)를 만들어 낼 수 없다. 그러므로 행렬 \( B \)의 열벡터는 선형 독립이다.

- 만약, \( \left\{ 1, x, 2+x \right\} \)라면, 2(숫자) X 1 + 1(숫자) X \( x \) = \( 2 + x \)를 만들어 낼 수 있으므로 이 경우는 종속이 된다.

■ \( \mathbf{y} \)는 \( W \)에 내린 정사영 벡터 \( \mathbf{w} = \text{proj}_W (y) \)와 \( \mathbf{w}^{\perp} = \mathbf{y} = \mathbf{w} \in W^{\perp} \)로 분해할 수 있다.

■ 그리고 \( \mathbf{f} = B \mathbf{a} \in W \)이므로, \( || \mathbf{y} - \mathbf{f} ||^2 \)을 다음과 같이 나타낼 수 있다.

\( || \mathbf{y} - \mathbf{f} ||^2 
= || (\mathbf{w} - \mathbf{f}) + \mathbf{w}^\perp ||^2 \\
= \langle (\mathbf{w} - \mathbf{f}) + \mathbf{w}^\perp, (\mathbf{w} - \mathbf{f}) + \mathbf{w}^\perp \rangle \\
= || \mathbf{w} - \mathbf{f} ||^2 + || \mathbf{w}^\perp ||^2 \\
= || \mathbf{w} - \mathbf{B}\mathbf{a} ||^2 + || \mathbf{w}^\perp ||^2 \)

■ 그러므로 \( || \mathbf{y} - \mathbf{f} || \)가 최소가 되도록 하는 함수 \( f \)를 결정하는 것은 \( || \mathbf{w} - \mathbf{f} || = || \mathbf{w} - B \mathbf{a} || \)가 최소가 되도록 하는 \( f \)의 계수 벡터인 \( \mathbf{a} = (a_0, a_1, \cdots, a_n)^T \)를 결정하는 것과 같다.

■ 그리고 \( \mathbf{w} \in W = C(B) \)이고, 행렬 \( B \)의 열벡터 \( B_1^C, B_2^C, \cdots, B_{n+1}^C \)가 \( C(B) \)의 기저이므로 \( || \mathbf{w} - B \mathbf{a} || = 0 \Leftrightarrow \mathbf{w} = B \mathbf{a} = \mathbf{f} \)가 성립한다.

- \( \mathbf{w} \in W \)는 행렬 \( B \)의 열벡터들의 선형 결합 \( B \mathbf{a} \)로 표현할 수 있기 때문이다. (여기서 \( \mathbf{a} \)는 계수. 즉, 스칼라)

■ \( \mathbf{w} = B \mathbf{a} = \mathbf{f} \)가 되는 \( \mathbf{a} \)가 유일하게 존재한다. 

■ 그리고 행렬의 각 성분이 실수일 때, 정사영 벡터는 다음과 같이 나타낼 수 있다.

 \( \text{proj}_W \mathbf{(a)} = B(B^TB)^{-1} B^T \mathbf{a} \)

- \( B \)는 부분 공간 \( W \)의 기저를 모아 놓은 집합

■ 그러므로 \( y \)를 \( W \)에 내린 정사영 벡터는 \( \mathbf{w} = \text{proj}_W \mathbf{(y)} = B(B^TB)^{-1} B^T \mathbf{y} \)로 나타낼 수 있다.

■ \( \mathbf{w} = B \mathbf{a} \)이므로 \( \mathbf{a} = (B^TB)^{-1} B^T \mathbf{y} \)가 된다. 이 벡터 \( \mathbf{a} = (a_0, a_1, a_2, \cdots, a_n) \)이 \( \displaystyle \sum_{i=1}^{m} \left( y_i - f(x_i) \right)^2 \)값이 최소가 되는 \( n \)차 다항함수 \( f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n \)의 계수 \( (a_0, a_1, a_2, \cdots, a_n) \)이다.

 

참고) \( \text{proj}_W \mathbf{(a)} = B(B^TB)^{-1} B^T \mathbf{a} \)

■ 최소가 되는 \( \mathbf{a} \)를 구하는 문제를 그림으로 나타내면 다음과 같다.

■ 목적은 실제값 \( \mathbf{y} \)와 거리를 최소화하는 \( B \)의 열에 가중치를 부여하는 계수 \( \mathbf{a} = (a_0, a_1, \cdots, a_n) \)을 찾는 것이다.

■ 그러기 위해서 \( \mathbf{y} \)를 \( W \)에 내린 정사영 벡터를 구하는 것이다. 이 정사영 벡터는 실제값과 함수값(예측값)의 최소 거리이기 때문이다. 

■ 이 정사영 벡터는 평면과 수직 관계이므로 최소 거리가 된다. 이 정사영 벡터를 \( \text{proj}_W \mathbf{(a)} \)라 하고 해보자. 그러면 \( \text{proj}_W \mathbf{(a)} \) 가 의미하는 것은 최소 거리 \( \mathbf{y} - B \mathbf{a} \)이다.

■ 이때, 정사영 벡터는 \( B \)의 열벡터가 만든 열공간 \( C(B) \)와 수직이므로 행렬 \( B \)와 \( \mathbf{y} - B \mathbf{a} \)의 내적값은 0이 된다. 

■ 내적은 다음과 같이 전치로 나타낼 수 있으며, 이 식을 구해야 하는 계수의 집합 \( \mathbf{a} \)에 대한 식으로 정리하면,

\( \mathbf{a} = (B^TB)^{-1} B^T \mathbf{y} \)가 성립하는 것을 확인할 수 있다.

 

■ 예를 들어, 최소제곱법을 이용하여 \( (x_i, y_i) = \left\{ (-2, 4), (-1, 2), (0, -1), (1, 0), (2, 0) \right\} \)에 대해 \( (x_i, y_i) \)의 분포를 근사적으로 나타내는 일차 함수 \( f(x) = a_0 + a_1 x \)와 이차 함수 \( g(x) = b_0 + b_1 x + b_2 x^2 \)을 구해보자.

1.2 최소제곱법을 이용한 근사해

■ \( m \times n \) 행렬 \( A \)에 대한 연립방정식 \( A \mathbf{x} = b \)가 주어질 때, \( m > n \)이면. 즉 변수의 개수보다 식의 개수가 많으면 일반적으로 해가 존재하지 않는다.

■ 이러한 경우에 근사해를 구하기 위해 최소제곱법을 이용할 수 있다. 근사해를 최소제곱법으로 구한다는 것은 \( A \mathbf{x} - b = 0 \)이므로 \( || A \mathbf{x} - b || \)가 최소(오차의 제곱합이 최소)가 되는 근사해를 찾는 문제로 바뀌게 된다.

- 여기서 \( A \)는 \( B \), \( \mathbf{x} \)는 \( \mathbf{a} \), \( b \)는 \( mathbf{y} \)와 의미가 같다.

■ 근사해를 \( \hat{\mathbf{x}} \)라고 했을 때, 1.1의 근사다항식처럼 \( \hat{\mathbf{x}} = (A^TA)^{-1} A^Tb \)로 나타낼 수 있다.

■ 행렬 \( A \)가 열충족계수를 가질 때, 즉 \( \text{rank}(A) = n \)일 때 \( A \)의 열벡터들은 열공간 \( C(A) \)의 기저가 된다.

■ 즉, \( m \times n \) 행렬 \( A \)의 \( \text{rank}(A) = n \)라면, \( \text{rank}(A^TA) = n \)가 된다. 

■ \( A^TA \)는 크기가 \( n \times n \)인 정방행렬인데, \( \text{rank}(A^TA) = n \)라는 것은 \( A^TA \)가 풀랭크를 갖는 정방행렬이라는 뜻이므로, \( A^TA \)의 열벡터들은 선형 독립이다. 그러므로 \( A^TA \)는 가역행렬이다.

■ \( A \mathbf{x} = b \)의 양변에 \( A^T \)를 곱하면 \( A^TA \mathbf{x} = A^Tb \)가 된다. 이때, \( A^TA \)는 가역행렬이므로 근사해 \( \hat{\mathbf{x}} \)는 \( \hat{\mathbf{x}} = (A^TA)^{-1}A^Tb \)가 성립한다.

 

2. QR 분해를 이용한 최소제곱법

■ \( m \times n, \quad ( m > n ) \)인 행렬 \( A \)의 계수가 \( n \)일 때, \( A \mathbf{x} = b \)의 근사해를 구하는 \( \hat{\mathbf{x}} = (A^TA)^{-1}A^Tb \) 방식은 이론적으로는 타당하지만, 역행렬을 계산해야 하기 때문에 계산의 수치적 안정성이 떨어질 수 있다.

- 특히 행렬이 최대계수(풀랭크) 행렬인 경우 반올림에 대한 정밀도, 누적된 계산 오차로 발생하는 잡음 등

■ 행렬의 QR 분해를 알면, 이 근사해를 더 쉽게 그리고 안정적으로 구할 수 있다.

■ \( A = QR \)에서 행렬 \( Q \)는 정규직교집합을 이룬다. 즉 \( Q^TQ = I \)가 성립한다. 

■ \( Q^TQ = I \)룰 이용하면 \( \hat{\mathbf{x}} = (A^TA)^{-1}A^Tb \)는 다음과 같이 나타낼 수 있다.

\( \mathbf{\hat{x}} = ( (QR)^T(QR) )^{-1} (QR)^T \mathbf{b} = ( R^T Q^T QR)^{-1} R^T Q^T \mathbf{b} = R^{-1} (R^T)^{-1} R^T Q^T \mathbf{b} = R^{-1}Q^T \mathbf{b} \)

■ 정리하면, \( \mathbf{\hat{x}} = R^{-1}Q^T \mathbf{b} \)가 성립한다. \( R \)은 상삼각행렬로 대각선 아래 부분이 모두 0이기 때문에 \( R^{-1} \)을 계산하기도 쉽고 \( Q^T \mathbf{b} \)과의 곱에서 0으로  \( Q^T \mathbf{b} \)의 일부 원소를 무시할 수도 있다.