[선형대수] 벡터공간과 최소제곱법

벡터공간과 최소 제곱법

들어가며

공간 (Space)

공간(Space)는 다음의 두 연산에 닫혀 있는 집합 입니다.

1. 덧셈 연산에 닫혀 있다.
2. 스칼라 곱 연산에 닫혀 있다.

다음과 같이 n-벡터의 집합은 모두 공간 입니다.

$$\mathbb{R}^{n}=\left\{\mathbf{x} \mid \mathbf{x}=\left(x_{1}, x_{2}, \cdots, x_{n}\right), \quad\left(\text { 단, } x_{i} \in \mathbb{R}\right)\right\}$$

앞으로, 모든 n-벡터 집합 $\mathbb{R}^n$은 n차원 벡터 공간(vector space)라고 부를 수 있게 됩니다.

Column Space (열공간)

행렬 A의 열벡터들에 대한 가능한 모든 선형조합의 결과를 모아 집합으로 구성 할 수 있다. 이런 집합을 Column space(열공간)이라고 하고 다음과 같이 표기한다.

Consisient Linear System

선형시스템 $Ax=b$가 해를 가지면(consistent), 다음을 만족한다.

$$\mathbf{b} \in \operatorname{col}(A)$$

Inconsistent Linear System

선형시스템 $Ax=b$가 해가 없으면(inconsistent), 다음을 만족한다.

$$\mathbf{b} \notin \operatorname{col}(A)$$

다시 말하면, b의 위치가 col(A)를 벚어나게 된다면, 아무리 아무리 A의 column vector를 조합해도 b를 만들어 낼 수 가 없습니다.

만약, 이렇게 b가 column space로 만들어 낼 수 없는 경우는 어떻게 해를 구할 수 있을까? 그냥 못풀어야 할 까? 이를 해결 해주는 것이 바로 최소 제곱법이다.

최소제곱법 (Least Squares Method)

열공간(column space)으로 투영

선형시스템 $Ax=b$에 대한 해가 없음에도 불구하고, 우리가 할 수 있는 최선이 무엇인가를 생각 해보자.

행렬 $A$가 정의하는 열공간에서 우리의 목표 $b$와 가장 가장 가까운 지점은 $b$를 열공간에 투영(projection)한 지점일 것이다. 즉, 달성가능한 최선의 목표 $proj_wb$ (=column space로 투영한 $b$)를 생각 할 수 있다.

최소제곱법

최소 제곱법은 선형시스템 Ax=b에 대한 해 x가 없음에도 불구하고, 할 수 있는 최선의 대한 $\bar{x}$ 을 내놓는 기법이다. 최소제곱법은 원래 선형시스템 Ax=b가 아닌 다음의 선형시스템을 해결 한다.

$$A \overline{\mathbf{x}}=\overline{\mathbf{b}} \quad\left(\text { 단 }, \overline{\mathbf{b}}=\operatorname{proj}_{W} \mathbf{b}\right)$$

주어진 선형시스템의 양변에 전치 행렬 $A^T$를 곱하면 최소제곱법의 해를 구할 수 있다.

$$\begin{aligned} & A \mathbf{x}=\mathbf{b} \\ \Rightarrow & A^{T} A \overline{\mathbf{x}}=A^{T} \mathbf{b} \\ \Rightarrow & \overline{\mathbf{x}}=\left(A^{T} A\right)^{-1} A^{T} \mathbf{b} \end{aligned}$$

최소제곱법으로 구한 해 $\bar{x}$는 원래 선형시스템을 만족하는 해는 아니다.

$$A \overline{\mathrm{x}} \neq \mathbf{b}$$

최소제곱법으로 구한 $\bar{x}$ 는 다음을 만족하는 근사해(approximate solution)이다.

$$A \overline{\mathbf{x}}=\operatorname{proj}_{W} \mathbf{b}$$

Note

이 방법은 목표 b와 달성 가능한 목표 $\bar{b}$의 차이를 나타내는 벡터 $(\mathbf{b}-\overline{\mathbf{b}})$의 제곱길이를 최소화 시기는 의미를 가지기 때문에 최소제곱법(least squares method)이라고 불린다.

응용: 선형회귀 (Linear Regression)

2차원 공간에 m개의 정 $x_{i=1}^{m}$이 그림과 같이 있을 때, 이를 잘 설명 할 수 있는 직선 $y=m x+b$ 를 구하는 문제를 생각해 보자. 이를 선형 회귀(linear regression) 문제라 한다.

해법

선형 회귀 문제는 다음과 같이 최소제곱법으로 풀 수 있다.

1. 선형 시스템으로 구성된 직선이 각 정점을 모두 자나간다고 가정하고 선형시스템 $A \mathbf{x}=\mathbf{b}$ 구성 (단, 주어진 모든 정점을 지나가는 직선은 존재하지 않으므로 선형시스템의 해는 존재하지 않음.)

$$\left[\begin{array}{cc} -3 & 1 \\ -1 & 1 \\ 1 & 1 \\ 3 & 1 \end{array}\right]\left[\begin{array}{l} m \\ b \end{array}\right]=\left[\begin{array}{c} -1 \\ -1 \\ 3 \\ 3 \end{array}\right]$$

​ 즉, [-3, 1]이 $y=m x+b$ 를 지난다고 가정한다. 그러면 $-1=m \cdot (-3)+b$ 로 식이 구성되고 동일한 방식으로 그림의 좌표를 정리하면 위 선형시스템이 완성 된다.

1. 최소제곱법 적용: 위 선형시스템의 해가 존재 하지 않기 때문에 근사치를 구하는 방식인 최소제곱법을 적용한다. $A^{T} A \overline{\mathbf{x}}=A^{T} \mathbf{b}$ 를 생각하고, $\overline{\mathbf{x}}=\left[\begin{array}{c} \bar{m} \bar{b} \end{array}\right]$를 구한다.

기하학적 해석

위에서 설명한 최소제곱법을 기하학적으로 해석 하면 다음과 같다. 우리가 관심있는 대상은 $\mathbf{b}-A \hat{\mathbf{x}}$이다. 이 식에 대한 관계식을 다음과 같이 정리 할 수 있다.

$$\mathbf{b}-A \hat{\mathbf{x}} \perp\left(x_{1} \mathbf{a}_{1}+x_{2} \mathbf{a}_{2} \cdots+x_{p} \mathbf{a}_{n}\right) \; \text{for any vector }x$$

$\mathbf{b}-A \hat{\mathbf{x}}$ 이 col(A)와 직교 한다는 의미는 col(A)의 모든 벡터들과 직교한다는 것이 성립니다. 이를 식으로 정리하면 다음과 같다.

$$\begin{aligned} &(\mathbf{b}-A \hat{\mathbf{x}}) \perp \mathbf{a}_{1} \quad \mathbf{a}_{1}^{T}(\mathbf{b}-A \hat{\mathbf{x}})=0\\ &(\mathbf{b}-A \hat{\mathbf{x}}) \perp \mathbf{a}_{2} \Rightarrow \mathbf{a}_{2}^{T}(\mathbf{b}-A \hat{\mathbf{x}})=0 \quad \Rightarrow \quad A^{T}(\mathbf{b}-A \hat{\mathbf{x}})=0\\ &(\mathbf{b}-A \hat{\mathbf{x}}) \perp \mathbf{a}_{m} \quad \mathbf{a}_{m}^{T}(\mathbf{b}-A \hat{\mathbf{x}})=0 \end{aligned}$$

위 식의 정리를 통해 $A^{T}(\mathbf{b}-A \hat{\mathbf{x}})=0$을 얻게 되었다.

Normal Equation

위에서 식을 정리 하여 얻은 $A^{T}(\mathbf{b}-A \hat{\mathbf{x}})=0$을 정리하면 다음과 같다

$$A^{T} A \hat{\mathbf{x}}=A^{T} \mathbf{b} \\ \text{(단, } \hat{\mathbf{x}}=\arg \min _{\mathbf{x}}\|\mathbf{b}-A \mathbf{x}\|)$$

위식을 Normal Equation(정규식)이라고 한다. 위의 정규식을 $C \mathbf{x}=\mathbf{d}$ 형태의 선형시스템으로 바라 볼 수있으며 다음과 같이 정리가 가능하다.

$$C=A^{T} A \in \mathbb{R}^{n \times n}, \text { and } \mathbf{d}=A^{T} \mathbf{b} \in \mathbb{R}^{n}$$

만약 $C=A^{T} A$이 역행렬이 존재한다면(invertible) 해는 다음과 같이 계산 되어 진다.

$$\hat{\mathbf{x}}=\left(A^{T} A\right)^{-1}A^{T}{\mathbf{b}}$$

혹은, 다음과 같은 방법으로도 x를 구할 수 있다.

$$\begin{aligned} \hat{\mathbf{x}} &=\arg \min _{\mathbf{x}}\|\mathbf{b}-A \mathbf{x}\|=\arg \min _{\mathbf{x}}\|\mathbf{b}-A \mathbf{x}\|^{2} \\ &=\arg \min _{\mathbf{x}}(\mathbf{b}-A \mathbf{x})^{\mathrm{T}}(\mathbf{b}-A \mathbf{x})=\mathbf{b}^{\mathrm{T}} \mathbf{b}-\mathbf{x}^{\mathrm{T}} A^{\mathrm{T}} \mathbf{b}-\mathbf{b}^{\mathrm{T}} A \mathbf{x}+\mathbf{x}^{\mathrm{T}} A^{\mathrm{T}} A \mathbf{x} \end{aligned}$$

위 식을 계산하여 다음과 같이 쓸 수 있다.

$$-A^{\mathrm{T}} \mathbf{b}-A^{\mathrm{T}} \mathbf{b}+2 A^{\mathrm{T}} A \mathbf{x}=\mathbf{0} \Leftrightarrow A^{\mathrm{T}} A \mathbf{x}=A^{\mathrm{T}} \mathbf{b}$$

따라서, $C=A^{T} A$이 역행렬이 존재한다면(invertible) 해는 다음과 같이 계산 되어 진다.

$$\mathbf{x}=\left(A^{T} A\right)^{-1} A^{T} \mathbf{b}$$