최소 자승법

드디어 선형 대수의 첫 고비인 최소 자승법(Least Squares)이다!

학교에서 처음으로 선대를 배웠을 때 이게 무슨 말인지 이해가 안 갔었지만 이젠 다르다. 크하하

어차피 앞으로 배울 내용들에서도 계속 최소 자승법이랑 연관 지어서 나오기도 하고 생각보다 간단하니 이번에 포스트 하나를 사용해 제대로 정리를 해서 최소자승법을 익혀보도록 하자.

본 장에서는 아래 내용들을 배운다.

1. 최소 자승법 문제 소개
2. 최소 자승법
3. 최소 자승법이 사용되는 예시

 

문제 소개

최소자승법(Least Squares)이 먼저 어떤 문제를 푸는데 사용되는 방법인지 파악 하는 것이 중요하다.

최소 자승… 즉, 제곱(자승)을 최소화 한다는 말인데, 어떤 제곱을 최소화 하냐는 것을 먼저 알아야 한다.

먼저 행렬 $A$의 column space와 임의의 벡터 $\textbf b$가 위와 같이 존재한다 생각해보자.

행렬 $A$에 어떤 벡터 $\textbf x$를 곱하면 결과 벡터 $A\textbf x$를 얻게 된다. 우리의 목표는 $\textbf b$와 최대한 가까운 $A\textbf x$를 얻는 것으로 이를 위해선 $\textbf b$와 $A\textbf x$ 사이의 차이, 오차벡터 $e = \textbf b - A\textbf x$의 크기가 최소가 되어야한다.

이때 $e$의 제곱, 즉 $||e||^2$을 최소로 하는 벡터 $\hat{\textbf x}$를 찾는 것이 최소자승법의 목적이다.

문제 자체는 우리가 수학을 배우며 자주 하던 그냥 미지수 $\textbf x$를 찾는 것으로 간단한 것을 확인할 수 있지만 어떡해야 $\hat{\textbf x}$를 찾을 수 있을까?

 

최소자승법

위 문제에서 먼저 어떤 상황이 $A\textbf x$와 $\textbf b$ 사이의 차이가 가장 작은지를 알 필요가 있다.

고등학교에서 우리는 직선과 점 사이의 최단 거리를 구한 적이 있다. 기억을 되새겨보면 점과 직선 사이의 최단 거리는 점에서 직선까지 수직으로 내린 거리라는 것을 알 수 있다. 이를 3차원으로 확장시키면 평면과 점 사이의 최단 거리는 점에서 평면으로 내린 수직선이라는 것은 자명하다.

이때 벡터는 점이라는 것을 다시 생각해보면 어떤 상황이 $A\textbf x$와 $\textbf b$ 사이의 차이가 가장 작은지에 대해 알 수 있다.

한마디로 벡터 $\textbf b$와 $A\textbf x$를 뺸 벡터가 $A$와 수직하다는 것이다. ($\textbf b$를 평면 $A$에 정사영 내린 것이라고 생각해도 된다.) 이 정보를 이용하면 오차 벡터 $e$는 $A$와 수직하다는 것으로 아래 식이 성립한다.

$$
e^TA\textbf x = (\textbf b - A\textbf x)^TA\textbf x = 0
$$

이제 우리가 평소에 방정식을 풀 때처럼 미지 벡터 $\textbf x$에 대한 식으로 만들어주면 된다.

$$
(\textbf b - A\textbf x)^TA\textbf x = (\textbf b^TA - \textbf x^TA^TA)\textbf x = 0
$$

위 식에서 $(\textbf b^TA - \textbf x^TA^TA)\textbf x = 0$ 이므로 단순히 $\textbf x$가 0 벡터인 경우 0이 된다. 하지만 이는 Trivial Solution이고 $(\textbf b^TA - \textbf x^TA^TA) = 0$ 를 만족하는 $\textbf x$가 우리가 찾는 $\textbf x$이다.

$$
\begin{align}
\textbf b^TA - \textbf x^TA^TA &= 0 \\
\textbf b^TA &=\textbf x^TA^TA \\
A^T\textbf b &= A^TA\textbf x \\
(A^TA)^{-1}A^T\textbf b &= \textbf x
\end{align}
$$

최종적으로 우리가 찾던 $\textbf x$는 $(A^TA)^{-1}A^T\textbf b$가 되는 과정이 바로 최소 자승법이다.

최종 식인 $\textbf x = (A^TA)^{-1}A^T\textbf b$가 너무 복잡해서 당황스럽지만 구하는 과정은 그냥 우리가 중학교때부터 지금까지 해왔던 과정이라는 것을 알 수 있다.

먼저 최소 자승법 식 중 $\textbf b^TA =\textbf x^TA^TA$ 는 Normal Equation이라 부른다. 단순히 식을 정리한 것임에도 이름이 붙었으나 다른 블로그들에서 자주 언급되니 기억만 해두자.

또 위 전개식 중 $A\textbf x$에 대해서 정리를 하면 $A\textbf x = A(A^TA)^{-1}A^T\textbf b$가 된다.

이때 $A(A^TA)^{-1}A^T$와 $\textbf b$를 곱해 $A\textbf x$가 나왔으므로 $A(A^TA)^{-1}A^T$를 $\textbf b$를 $A$로 정사영 시키는 행렬이라 하여, Projection Matrix라 부른다.

 

여기서 재미있게도 풀이 수식에서는 $e$의 제곱이 나오지 않는다. 당연하게도 e의 제곱을 최소화 하는 풀이법도 존재하는데 이 경우 미분을 사용해 e의 제곱을 최소화 하는 지점의 $\textbf x$를 구하게 된다.

미분을 사용한 최소자승법 풀이

위 문제에서 언급한 것처럼 우리의 목적 함수는 $e^Te$로 주어지고 이를 최소화 하는 것이 우리의 목표다.

목적 함수는 $J(\textbf x) = e^Te = (\textbf b - A\textbf x)^T(\textbf b - A\textbf x)$로 나타낼 수 있다. 이제 이를 $\textbf x$에 대해서 미분하여 0이 되는 지점을 찾으면 된다. (제곱 형태이기에 convex하여 미분이 0인 지점이 최소)

$$
\begin{matrix}
\frac{\partial J(\textbf x)}{\partial x} = -2A^T(\textbf b - A\textbf x) = 0 \\
A^T(\textbf b - A\textbf x) = 0 \\
A^T\textbf b - A^TA\textbf x = 0 \\
A^T\textbf b = A^TA\textbf x
\end{matrix}
$$

마지막 결과는 위에서 말한 Normal Equation이므로 미분을 이용해서도 구할 수 있다는 것이 증명되었다.

최소 자승법은 끝이지만 최소 자승법 과정 중 짚고 넘어가야할 부분들이 존재한다.

 

최소 자승법이 사용되는 예시

최소 자승법은 선형 회귀에서 대체로 사용된다.

선형 회귀란 주어진 데이터 포인트들을 가장 잘 설명하는 직선을 찾는 과정으로 2차원 공간에서 아래 과정을 거친다.

먼저 우리가 찾는 모델은 $y = \beta_0 + \beta_1x$이다. 우리는 주어진 데이터 포인트들을 잘 설명하는 $\beta_0, \beta_1$를 찾는 것이다.

선형대수적으로 표현하면 다음과 같다.

$$
\textbf y = X {\beta}
$$

이때 $\textbf y, X, \beta$는 다음과 같다.

$$
\textbf y = \begin{bmatrix}
y_1 \\
y_2 \\
\vdots \\
y_n
\end{bmatrix},
X = \begin{bmatrix}
1 & x_1 \\
1 & x_2 \\
\vdots & \vdots \\
1 & x_n
\end{bmatrix},
\beta = \begin{bmatrix}
\beta_0 \\
\beta_1
\end{bmatrix}
$$

이때 $x_i$는 주어진 데이터 포인트들의 $x$ 좌표이고, $y_i$는 주어진 데이터 포인트들의 $y$ 좌표이므로 위에서 했던 방식을 적용하면 구할 수 있다.

 

이외에도 혁펜하임 유튜브에서는 노이지한 정보가 추가된 신호에서 원본을 복원하는 예시에 대해서도 얘기했다.

$$
b = Ax + \epsilon
$$

위와 같이 원래 송신한 결과는 $Ax$인데, 노이즈가 섞여 A의 column vector들로는 표현 불가능한 $\textbf b$를 얻었을 때 최소 제곱법을 통해 원본 $A\textbf x$를 얻을 수 있다는 것이다.

 

드디어 선형 대수의 첫번째 고비인 최소자승법에 대해서 끝마쳤다. 하지만 곧바로 더 큰 두번째 고비인 고윳값 분해가 있네... 8ㅅ8

Reference

• Deeplearning Ch.2 Linear Algebra
• 유튜브 혁펜하임