[ Introduction of Least Squares Problem ]
1. Over-determined Linear Systems
-An over-determined system is a set of linear equations where the number of equations ($m$) is much greater than the number of variables ($n$)
-In real-world data (ex_ predicting life-span based on weight, height, and smoking), we usually have far more data examples than features, leading to $m \gg n$
-Because there are too many constraints for only a few variables, such systems usually have no exact solution ($Ax \neq b$)
| 우리가 다루는 실제 데이터는 보통 변수(feature)의 개수보다 수집된 데이터의 양(행의 개수)이 훨씬 많음 이렇게 식의 개수가 미지수보다 훨씬 많은 상태가 Over-determined System 조건이 너무 많다 보니 모든 식을 동시에 만족하는 완벽한 정답 $x$를 찾는 것은 사실상 불가능하며, 이를 수학적으로는 "해가 존재하지 않는다"라고 표현 |
2. Least Squares: Finding the Best Approximation
-Since an exact solution does not exist, we aim to find an $x$ that makes $Ax$ as close to $b$ as possible
-This approach is called the Least Squares Problem, where we find $\hat{x}$ that minimizes the distance between $Ax$ and $b$
-The "closeness" is measured by the norm of the residual, $||b - Ax||$
| 완벽한 정답이 없다면, '최대한 정답에 가까운 값'이라도 찾아야 하는데, 이때 $Ax$와 정답 $b$ 사이의 거리를 최소로 만드는 $\hat{x}$를 찾는 것이 최소제곱법(Least Squares)의 핵심 여기서 '거리'는 수치적인 오차를 의미하며, 이 오차를 가장 작게 만드는 것이 목표 |
3. Best Approximation Criterion: Sum of Squared Errors
-The most common criterion for the "best" solution is to use the sum of squared errors
-We define the total error as the squared sum of the differences between each element of $Ax$ and $b$: $\sum (b_i - (Ax)_i)^2$
-Squaring the errors ensures that all discrepancies are positive and penalizes larger errors more heavily
| 어떤 값이 가장 좋은 근사치인지 판단하는 기준 : 각 데이터에서 발생하는 오차(= 정답과의 차이)를 단순히 더하면 (+)오차와 (-)오차가 서로 상쇄될 수 있기 때문에, 모든 오차를 제곱해서 합산하는 방식을 사용 이를 통해 모든 오차를 양수로 만들고, 특히 큰 오차에 대해 더 엄격한 페널티를 부여하여 전반적으로 가장 균형 잡힌 최적의 선을 찾을 수 있음 |
4. Why Use Least Squares in Machine Learning?
-Linear regression in machine learning is essentially a Least Squares problem.
-We try to find the weights ($W$) that minimize the loss function, which is often defined as the Mean Squared Error (MSE)
| 머신러닝의 가장 기초가 되는 '선형 회귀(Linear Regression)'가 바로 이 최소제곱법을 기반으로 하기 때문에, 모델이 예측한 값과 실제 데이터 사이의 오차 제곱합을 최소화하는 가중치를 찾아가는 과정이 곧 선형대수학의 Least Squares 문제를 푸는 것!! |
벡터의 기본 연산
1. Inner Product (내적): 두 벡터의 내적은 같은 위치의 성분끼리 곱해서 모두 더한 스칼라값. 교환법칙과 분배법칙이 성립하며, 자기 자신과의 내적은 항상 0보다 크거나 같음
2. Vector Norm (벡터의 길이): 벡터의 길이는 피타고라스 정리를 적용해 각 성분의 제곱합에 루트를 씌워 구함. 벡터에 스칼라(상수)를 곱하면, 길이는 그 상수의 절댓값만큼 배로 늘어남
3. Unit Vector (단위 벡터): 방향은 원래 벡터와 똑같이 유지하면서, 오직 길이만 1로 압축(정규화, Normalizing)한 벡터
4. Distance between Vectors (두 벡터 사이의 거리): 두 벡터(점) 사이의 거리를 구할 때는, 두 벡터를 뺀 '차이 벡터($u-v$)'를 구한 뒤 그 벡터의 길이를 계산
5. Inner Product and Angle (내적과 각도): 내적은 두 벡터의 길이와 두 벡터가 이루는 각도($\cos \theta$)의 곱으로도 표현할 수 있으며, 이 공식을 이용하면 두 벡터 사이의 끼인각을 알아낼 수 있음
6. Orthogonal Vectors (직교/수직 벡터): 기계학습과 선형대수에서 아주 중요한 성질. 만약 두 벡터의 내적을 계산했더니 0이 나왔다면, 두 벡터는 기하학적으로 완벽하게 $90^\circ$를 이루며 서로 수직(Orthogonal)
[ Least Squares Normal Equation 1]
1. Back to Over-Determined Systems
-A linear system $Ax = b$ is over-determined when the number of equations ($m$) is greater than the number of variables ($n$)
-In such cases, the vector $b$ is usually not in the Column Space of $A$, meaning there is no exact solution $x$ that satisfies $Ax = b$
| 데이터가 변수보다 훨씬 많은 'Over-determined' 상황에서는 모든 조건을 완벽히 만족하는 해($x$)가 존재하지 않는 경우가 대부분 = 이를 기하학적으로 보면, 결과 벡터 $b$가 행렬 $A$의 열들이 만들어내는 평면 위에 놓여 있지 않기 때문에 발생하는 현상임! |
2. Objective: Minimizing the Squared Sum of Errors
-Since an exact solution is unavailable, we seek an approximation $\hat{x}$ that minimizes the error
-The error (or residual) is defined as $e = b - Ax$. We want to minimize the Squared Sum of Errors (SSE): $$f(x) = \|b - Ax\|^2 = (b - Ax)^T(b - Ax)$$
| 완벽한 정답이 없으므로, 실제값($b$)과 예측값($Ax$) 사이의 거리(오차)를 가장 작게 만드는 $\hat{x}$를 찾아야 함 이는 최소제곱법의 본질로 이어지는데, 바로 오차를 제곱해서 더한 값인 $f(x)$를 최소화하는 최적화 문제를 푸는 것 |
3. Deriving the Normal Equation
-To find the minimum of $f(x)$, we take the derivative with respect to the vector $x$ and set it to zero: $\frac{\partial f}{\partial x} = 0$
-Expanding the expression: $f(x) = b^T b - b^T Ax - (Ax)^T b + (Ax)^T Ax = b^T b - 2b^T Ax + x^T A^T Ax$
-Taking the derivative leads to: $-2A^T b + 2A^T Ax = 0$, which simplifies to the Normal Equation: $$A^T A \hat{x} = A^T b$$
| **This equation projects the vector $b$ onto the subspace spanned by the columns of $A$ to find the closest point >> 정규 방정식은 벡터 $b$를 $A$의 열공간으로 수직 투영하여 가장 가까운 점을 찾는 과정과 같음 함수 $f(x)$가 최소가 되는 지점은 기울기가 0인 지점 벡터에 대해 미분을 수행하면 $A^T A \hat{x} = A^T b$라는 식을 얻게 되는데, 이것이 바로 정규 방정식(Normal Equation) 이 식은 복잡한 오차 함수를 풀기 쉬운 선형 방정식 형태로 변환해 주는 아주 강력한 도구 |
[ Least Squares Normal Equation 2]
1. The Normal Equation
-Given a least squares problem $Ax \simeq b$, we obtain the normal equation: $A^T A \hat{x} = A^T b$
-This can be viewed as solving a entirely new linear system, $Cx = d$
-the matrix $C = A^T A$ becomes a square matrix ($n \times n$), and $d = A^T b$ becomes an $n$-dimensional vector
| 해가 존재하지 않던 기존의 $Ax = b$ 방정식 양변에 행렬 $A$의 전치행렬인 $A^T$를 곱할 경우, 직사각형 모양이었던 행렬 $A$가 $A^T A$라는 정사각행렬(Square Matrix)로 변환됨 이는 풀 수 없었던 원래의 문제를 $Cx = d$라는 풀이 가능한 새로운 선형 시스템으로 바꿔주는 핵심 역할 |
2. Another Derivation Using Vector Calculus
-The objective of Least Squares is to find $\hat{x}$ that minimizes the squared sum of errors: $$\hat{x} = \text{arg min}_x ||b - Ax||^2$$
-Expanding the squared norm mathematically: $$(b - Ax)^T(b - Ax) = b^T b - x^T A^T b - b^T Ax + x^T A^T A x$$
-By computing the vector derivative with respect to $x$ and setting it to zero to find the minimum, we obtain: $$-2A^T b + 2A^T A x = 0 \iff A^T A x = A^T b$$
| 최소제곱법은 '오차의 제곱합이 최소가 되는 지점(기울기가 0인 지점)'을 찾는 최적화 문제 이를 수식으로 전개한 뒤 $x$라는 벡터에 대해 미분을 수행하는데, 이때 스칼라 미분과 유사하게 $a^T x$를 $x$로 미분하면 $a$가 남는 등의 벡터 미분 규칙이 적용됨 이 미분 과정을 거쳐 식을 0으로 놓고 정리하면, 정규 방정식 $A^T A x = A^T b$이 논리적으로 도출됨 |
3. The Final Solution
-If the newly formed square matrix $C = A^T A$ is invertible (meaning its inverse matrix exists), the unique optimal solution is computed simply as: $$\hat{x} = (A^T A)^{-1} A^T b$$
| 우리가 최종적으로 알고 싶은 것은 바로 최적의 가중치 집합인 $\hat{x}$ 앞서 $A^T A$를 '정사각행렬'로 만든 이유는 역행렬(Inverse Matrix)은 오직 정사각행렬에서만 존재할 수 있기 때문! 만약 $A^T A$의 역행렬이 존재한다면, 양변에 역행렬을 곱해주는 것만으로 가장 완벽한 근사해 $\hat{x}$를 수식으로 구해낼 수 있음 |