(선형대수학) 8-1. Least-Squares Method

이번 시간에는 다시 Ax=b를 푸는 방법으로 다시 돌아와보자...

A가 정사각행렬일 때는 이미 앞에서 여러챕터들을 통해서 푸는 방법을 알아보았었다.

그러면, 이번에는 A가 정사각행렬이 "아닌" 경우에 대해서 살펴보자.

 

---

1. 좌우로 길쭉한 경우 -> 부정형 연립방정식!

(선형대수학) 4-2. Ax=b 풀어봅시다! (선형사상과 일반해, 특수해): https://0418cshyun.tistory.com/151

(선형대수학) 4-2. Ax=b 풀어봅시다! (선형사상과 일반해, 특수해)

 

일반해와 특수해 개념을 이용하면, "유일하지는 않지만" 해를 구할 수 있다!

 

---

2. 위아래로 길쭉한 경우

 

예시를 하나 들어보자.

위의 예시를 보면 알겠지만,

식이 변수에 비해서 너무 많다고 느껴질 것이고, 그로 인해서, 모든 식을 만족시키기 어렵다는 것을 알 것이다.

=> 정리하면, 동일한 식이 존재하지 않는 가정하에서 해가 존재하지는 않는다.

 

그러면, 이 경우에는 해가 없으니, 그냥 끝나는 것인가???

=> 그건 아니고, 해와 최대한 "비슷한" 가짜 해(Pseudo Solution)를 만들어 낼 수 있다!

=> 이러한 가짜 해를 Least-Squares Solution 혹은 Estimated Solution이라고 한다.

 

해와 최대한 비슷하다는 얘기는 무슨 얘기일까???

=> 해와 동일한 모양(위의 예시에서는 2차원 벡터가 될 것이다.)을 가지고, 최대한 b와 "가까운 값"을 만들어 낸다!

=> 최대한 b와 "가까운 값"이라는 개념은 NORM 관점에서 가깝다는 말!

=> 즉, 앞에서 본 여러 Norm들 (Lp-norm) 또한 사용가능하다.

=> 물론, 여기서는 따로 언급이 없다면, "L2-norm"을 사용한다.

=> 그리고 이렇게 Pseudo Solution을 구하는 과정을 "Least Square Method(최소자승법)"이라고 한다!

---

여기까지, 개념적인 내용까지는 알겠는데, 어떻게 "Pseudo Solution"을 구할까??

최적화 문제(Optimization Problem)을 다뤄본 적도 없고 말이다...

 

사실, 이 문제 자체는 여러가지 방법으로 접근할 수 있다!!

 

1. 미분 이용!

2. 기하학적 의미 이용! ~ Projection Matrix 이용!

 

---

1. 미분 이용...

저 Squared Error를 "최소화"시키는 것이 목표이므로, 최솟값 찾는 가장 심플한 방법인 미분을 이용하면 된다!

=> 게다가 저 Squared Error가 "2차식(Quadratic Form)"이므로, 미분도 쉽고, "유일한 해"를 가진다!

 

(벡터미분 이용)

여기서 저 "역행렬"의 존재성에 대해서는 조금 있다가 살펴보기로 한다.

 

(추가) -> 위에서 쓴 벡터미분에 대한 내용!

먼저 1차항(내적)에 대해서

또한, 2차항에 대해서는

 

---

(벡터미분에 어려움이 있다면, 성분으로 다 쪼개야 하는데, 상당히 복잡해진다...)

 

역시, 역행렬에 대한 존재성은 뒤에서 다루기로 하자.

---

2. 기하학적 의미 이용 -> Projection Matrix 이용

 

Ax=b의 해가 없다는 것은 b가 A의 Column Space에 없다는 말이다.

그렇다면, Pseudo Solution (x_hat)을 구한다는 것은 여기서는 무슨 말일까? -> Projection Matrix를 생각해보자.

 

어차피, x_hat에 의해서 나오는 Ax_hat은 A의 Column Space에 존재하므로, 이 값이 b와 가장 가깝다는 것은

=> b를 Column Space에 사영시킨 것이 Ax_hat이 되어야 한다!!

 

왜냐하면, 가장 가깝다는 말이, 결국 "수직거리 -> Squared Error"를 최소화 시킨다는 말이기 때문이다.

여기에서

파란 면은 -> A의 Column Space(C(A))

빨간 선을 -> b라고 한다면

=> b가 C(A)에 존재하지 않는다!! -> 해가 없다!

=> C(A)에서 가장 b와 가까운 값은 => 사영시킨 벡터 b_hat! => 즉, 녹색 선이 될 것이다.

=> 보라색 선의 길이가 Squared Error가 될 것이다!

 

그러면, 이제 Column Space로 Projection을 시키는 Matrix에 대해서 생각해보자.

7-2에서 Projection Matrix를 구하는 방법과 동일하다! (그때는 한 방향 벡터, 지금은 공간!)

그런데, 여기서 약간 Trick을 이용해서...

위에서 e는 Ax_hat하고만 수직은 아니고, C(A) 전체와 수직이다...

 

1. 

=> e는 C(A)를 대표하는 벡터들 모두와 수직이라고 해도 상관없다!

=> C(A)의 Basis들과 모두 수직!

=> C(A)의 가장 간단한 Basis... => A의 Column Vector!

 

2.

=> e는 Left Null Space

---

자, 어떤 방법을 이용했던간에... 결국 다음과 같은 식을 얻는다.

아마 가장 궁금해질 것이 저 "역행렬"의 존재성인데, 한번 살펴보자! (A의 모양은 "위아래로 길쭉"이라는 점을 다시 한 번 생각하자!)

 

여기서 사용할 성질은...

두 개의 Null Space가 동일하다는 것이다!!

 

(증명)

 

2번에서 (Ax)(Ax)로 내적하는 것이 있는데...

=> 자신과는 영벡터가 아닌 이상 Orthogonal이 아니기 때문에, 그냥 Ax=0이 된다! 

 

이 두 개의 Null Space가 동일하다는 것은

A가 m by n 행렬일 때(m>n), A가 Full-rank인 경우 (즉, rank(A)=n)

=> Ax=0의 해가 x=0 밖에 존재하지 않는다!!

(증명)

Full rank인 경우, A의 모든 Column Vector가 Linearly Independent이라는 말과 동일하다.

일단, Ax=0의 해에 x=0이 포함된다는 것은 자명한데, 만일, 다른 해가 있다면

=> 그 해로 인해서, linearly independent 조건이 깨진다.

=> Null Space가 동일하므로, A^TA의 경우도 해가 x=0 밖에 없다!

=> 게다가, A^TA는 정사각행렬(n by n 행렬)이다!

=> 그러므로, "역행렬"이 존재한다!! (Invertible!)

 

---

더 나아가서, Column Space로 Projection 되는 Matrix도 구할 수 있다.

여기서 주의해야 할 것은

=> A가 "정사각행렬이 아니라는 것!"

=> 그러므로, 다음과 같은 것은 애초에 말이 안된다!

=> 이렇게 되어서, P=I라고 생각하면 절대 안된다!

---

만일, A가 정사각행렬이고 역행렬이 존재한다면...

=> 위에서 말이 안된다고 했던 것이 된다!!

그러므로, P=I가 된다!!

=> Least Square Method 자체도, 그냥 역행렬 곱한 것과 동일해진다!

---

정리해보자면...

=> Least Square Method는 b와 가장 비슷한 값을 Estimate하는 값을 Space 내부에서 찾는 방법

=> 정사영(Projection) -> 수직 이용!

=> Square Error 최소화!