인공지능을 위한 선형대수 - CHAPTER 3.2 Least Squares와 그 기하학적 의미

https://www.boostcourse.org/ai251/lecture/540328?isDesc=false 

인공지능을 위한 선형대수

Geometric Interpretation of Least Squares

 

Least Squares는 $||\mathbf{b}-\hat{\mathbf{b}}||$를 최소화 할 수 있는 $\hat{x}$을 구하는 방법입니다. 여기서, $\mathbf{b}$는 우리가 피팅하고자 하는 Ground Truth 벡터이고 $\hat{\mathbf{b}}$는 우리의 모델 $A\hat{x}$로부터 예측되는 벡터입니다. $\hat{\mathbf{b}}$는 죽었다 깨어나도 Col(A) 를 벗어날 수 없습니다. 위 그림을 바탕으로 $\hat{\mathbf{b}}$ 를 Col A 상에서 요리 조리 움직여 봤을때,   $||\mathbf{b}-\hat{\mathbf{b}}||$는 $\mathbf{b}-\hat{\mathbf{b}}$가 Col(A)에 수직할때 최솟값을 가진다는 것을 파악할 수 있습니다. 

 

$\mathbf{b}-\hat{\mathbf{b}}$가 Col(A)에 수직하면, $\mathbf{b}-\hat{\mathbf{b}}$ 와 Col(A) 의 모든 벡터의 내적은 그 값이 0이 나와야 합니다. $A\mathbf{x}$ 에서 어떤 $\mathbf{x}$ 가 오든지간에 $A\mathbf{x}$ 와 $||\mathbf{b}-\hat{\mathbf{b}}||$ 의 내적이 0 이라는 의미입니다.

 

Column의 사이즈가 n 인 행렬 $A$ 의 Column vectors 를 ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, ... , ${\mathbf{a}}_n$ 라고 하고, Column Vector $\mathbf{x}$ 의 원소를 $x_1$, $x_2$, ... , $x_n$ 라고 정의하겠습니다.

 

그러면, $\mathbf{b}-\hat{\mathbf{b}}$와 Col(A)이 수직할때의 내적 값을 아래와 같이 표현할 수 있습니다.

 

$(\mathbf{b}-\hat{\mathbf{b}})\mathrm{\perp }A\mathbf{x}\Rightarrow (\mathbf{b}-\hat{\mathbf{b}})\cdot A\mathbf{x}=0$

 

여기서 $A\mathbf{x}$ 를 ${\mathbf{a}}_1{x}_1+{\mathbf{a}}_2{x}_2+\cdots +{\mathbf{a}}_n{x}_n$ 으로 전개할 수 있습니다.

 

$(\mathbf{b}-\hat{\mathbf{b}})\cdot ({\mathbf{a}}_1{x}_1+{\mathbf{a}}_2{x}_2+\cdots +{\mathbf{a}}_n{x}_n)=0$

 

 

$(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_1{x}_1=0$

$(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_2{x}_2=0$

...

$(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_n{x}_n=0$

 

위식에서 $x_1$, $x_2$, ... , $x_n$ 가 어떤 값이든 $(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_k{x}_k=0$ 가 0이 돼야하므로 $x_1$, $x_2$, ... , $x_n$ 들은 식에서 소거해줍시다.

 

$(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_1=0$

$(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_2=0$

...

$(\mathbf{b}-\hat{\mathbf{b}})\cdot {\mathbf{a}}_n=0$

 

여기서, 내적 연산(inner product 혹은 dot product)을 풀어쓰면 

 

${\mathbf{a}}_1^T(\mathbf{b}-\hat{\mathbf{b}})=0$

${\mathbf{a}}_2^T(\mathbf{b}-\hat{\mathbf{b}})=0$

...

${\mathbf{a}}_n^T(\mathbf{b}-\hat{\mathbf{b}})=0$

 

가 됩니다. 그리고! $\hat{\mathbf{b}}$ 을 $A\hat{\mathbf{x}}$ 로 풀어쓰면~

 

${\mathbf{a}}_1^T(\mathbf{b}-A\hat{\mathbf{x}})=0$ 

${\mathbf{a}}_2^T(\mathbf{b}-A\hat{\mathbf{x}})=0$ 

$⋮$ 

${\mathbf{a}}_n^T(\mathbf{b}-A\hat{\mathbf{x}})=0$

 

라는 식들을 구해낼 수 있습니다.

 

그리고 위식은 아래와 같이 행렬과 벡터간의 곱으로 나타낼 수 있습니다.

 

$A^T(\mathbf{b}-A\hat{\mathbf{x}})=0$

 

여기서 0은 스칼라 0이 아닌 벡터입니다!

 

Normal Equation

$A^T(\mathbf{b}-A\hat{\mathbf{x}})=0$를 전개하면 다음의 수식이 성립합니다.

$$A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$$

위 수식은 Normal Equation이라고 불립니다.

 

그리고, 위 수식은 새로운 Linear System으로 해석가능합니다. $C\mathbf{x}=\mathbf{d}$, 여기서 $C$는 $A^{T}A$ 이고 $\mathbf{d}$는 $A^T\mathbf{b}$입니다.

 

만약 $C=A^{T}A$가 Invertible 하다면, Solution은 다음과 같이 계산될 수 있습니다.

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

$\hat{\mathbf{x}}$이 Least Squares를 통해 구해지는 Solution입니다.

 

정리하면 Least Squares 방법은 $A\mathbf{x}\simeq \mathbf{b}$인 Linear System에 대하여 Solution $\hat{\mathbf{x}}$를 구함에 있어, $\mathbf{b}-A\hat{\mathbf{x}}$가 Col($A$)에 수직이되는 Solution을 찾는 방법입니다.