3.2 Normal Equation

---

이 글은 Edwith로 부터 제공되는 주재걸 교수님의 "인공지능을 위한 선형대수" 강의를 듣고 요약하였으며, 개인 공부를 위해 부족한 부분을 위해 필요한 개념들을 추가하여 작성하였습니다.

---

 

 이번 절(3.2)에서는 "Least Squares Problem" / "Normal Equation" 정의 및 개념을 알아보고, 예제를 직접 풀어면서 이해를 돕고자 한다.

 

 앞 절(3.1) 다룬 내용을 가볍게 살펴보고, Over-Determined System인 경우 해를 어떻게 찾을것인지, 더 나아가 "Normal Equation(정규 방정식)"이 무엇인지 살펴보자.

Back to Over-Determined System

---

[그림 1] 3x3 Matrix의 solution 찾는 과정

 

 Life-Span을 예측하기 위해 최적의 가중치(해)를 찾는 것이 목표이다. 우선 위 테이블에서는 변수 3개(Weight, Height, is_smoking)를 포함하고 있는 3명의 데이터(3개의 equation)가 존재한다. 이를 Matrix로 나타내면 3x3 모양이므로, 역행렬을 이용하여 쉽게 해를 찾을 수 있었다. 

 

 하지만, 3명이 아닌 그 이상의 사람들로부터 데이터를 얻어 최적의 가중치를 찾으려면 어떻게 해야할까? 이때는 Matrix가 m x 3 (m > 3, overdetermined system) 이므로 역행렬을 이용하여 해를 구할 수 없기 때문에, 3x3의 Matrix에서 구한 해를 가지고 Life-Span을 예측해보자. 그리고 그때의 Errors를 구하면 다음과 같다. 

 

[그림 2] 4x3 Matrix's Errors 

 

가중치는 3 x 3의 데이터에서만 최적이기 때문에 새로운 데이터(ID : 4에 해당)가 나타나게 되면 Total Errors가 -12 (0 + 0 + 0 -12)로 관측되었다. Total Error를 줄이기 위해 가중치를 약간 다르게 바꾸어 줄어드는지 확인해보자.

 

[그림 3] 가중치(해)를 바꿔서 Error를 계산

Which One is Better Solution?

---

 4 x 3 Matrix(overdetermined system)에 어떤 가중치가 Total Errors를 줄여주는지 비교해보면 다음과 같다.

 

[그림 4] Errors 비교

Least Squares: Best Approximation Criterion

---

overdetermined system에서 Errors 대신 SSE를 사용하여 비교하면 다음과 같다.

[그림 5] Sum of squared errors 비교

Least Squares Problem

---

 지금까지 내용을 정리하면, 대부분 Machine Learning의 문제들은 Data(Equation, m)가 입력 변수(Column, n)보다 많기 때문에, "해가 없다.", 그러나 현실에서는 단 하나의 답이 필요한 경우도 있기 때문에 다음 방안을 자주 사용한다.

 

• 해가 없다면 적어도 Ax 가 b에 최대한 "가까운' 것 같은 x를 구하자 (우리가 할 것!)
• 해 x가 많다면 그 중에서도 가장 "그럴듯한" 것을 고른다. (Skip)

위에서 '가까운', '그럴듯한'이 정의되지 않았음에 주의해야 하는데, 어떤 식으로 정의하는 것이 타당한가는 현실에서 풀 문제로 수학만으로 정해지지 않았다. 

 

실제로 자주 사용하는 기준은 다음과 같다.

 

• Ax - b 의 "길이"가 작으면 "가까운"
• x 의 "길이"가 작으면 "그럴 듯한" (Skip)

 이러한 기준을 사용하여 해를 구하는 것이 "최소제곱법(Least Squares Problem)"이다. 최소제곱법은 특이값 분해에서도 도구로 활용될 것이다. 

 

최소제곱법의 정의는 다음과 같다.

 

[그림 6] Least Squares Problem 정의

Geometric Interpretation of Least Squares

---

최소제곱법을 기하학 관점에서보면 다음과 같이 정리할 수 있다. A Matrix (Col A)로 부터 구성된 Span 안에서 b 와 가장 가까운 솔루션(x^)을 찾으면 b에서 Col A로 정사영(직교)시킨 Point b^이 가장 가까운 솔루션이다. 

[그림 7] 최소제곱법 기하학 관점 및 Orthgonal

 

직교 성질을 이용하여 전개하면 다음과 같이 정규방정식(Normal Equation)을 이끌어 내기 위한 절차다

 

[그림 8] 정규방정식 유도과정

Normal Equation

---

 

[그림 9] 정규방정식 (Normal Equation)

C 가 역행렬이 존재할 때 우리는 가장 거리가 가까운 솔루션을 구할 수 있다.

Another Derivation of Normal Equation

---

정규방정식을 도출하는 또 다른 방법으로 미분을 이용하여 도출 할 수 있다. (Skip)

 

[그림 10] 미분을 이용한 정규방정식 유도

Life-Span Example

---

[그림 11] Life-Span Example

 

정규방정식 꼴로 만들어주고 최종적으로 좌변의 첫번째 Matrix의 역행렬을 구해 양변에 곱해주면 솔루션을 구할 수 있다.

What If 𝑪 = 𝑨^T 𝑨 is NOT Invertible?

---

증명 필요..