27.35 과결정 시스템(Overdetermined System)과 최소 제곱법(Least Squares)

1. 과결정 시스템의 정의

과결정 시스템(overdetermined system)은 방정식의 수 m이 미지수의 수 n보다 많은 연립 일차방정식 \mathbf{A}\mathbf{x} = \mathbf{b}이다 (m > n, \mathbf{A} \in \mathbb{R}^{m \times n}). 일반적으로 이러한 시스템은 모든 방정식을 정확히 만족하는 해가 존재하지 않는다. \mathbf{b}가 \mathbf{A}의 열 공간 \text{Col}(\mathbf{A})에 속하지 않을 확률이 매우 높기 때문이다.

실제 응용에서 과결정 시스템은 자연스럽게 등장한다. 측정 데이터로부터 모델의 매개변수를 추정할 때, 데이터 점의 수(m)가 매개변수의 수(n)보다 많으면 과결정 시스템이 된다. 정확한 해가 없으므로, “최선의 근사해“를 정의하고 구하는 체계가 필요하다.

2. 최소 제곱 문제의 정의

최소 제곱법(least squares method)은 잔차 벡터 \mathbf{r} = \mathbf{b} - \mathbf{A}\mathbf{x}의 유클리드 노름을 최소화하는 \mathbf{x}를 구하는 방법이다.

\hat{\mathbf{x}} = \arg\min_{\mathbf{x} \in \mathbb{R}^n} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2

목적함수를 전개하면 다음과 같다.

f(\mathbf{x}) = \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2 = (\mathbf{A}\mathbf{x} - \mathbf{b})^\top(\mathbf{A}\mathbf{x} - \mathbf{b}) = \mathbf{x}^\top\mathbf{A}^\top\mathbf{A}\mathbf{x} - 2\mathbf{b}^\top\mathbf{A}\mathbf{x} + \mathbf{b}^\top\mathbf{b}

이는 \mathbf{x}에 대한 2차 함수(이차형식)이며, \mathbf{A}^\top\mathbf{A}가 양의 준정부호이므로 볼록(convex)하다. 따라서 극솟값이 곧 전역 최솟값이다.

3. 정규 방정식의 유도

목적함수의 기울기를 0으로 놓으면 최적 조건을 얻는다.

\nabla_{\mathbf{x}} f(\mathbf{x}) = 2\mathbf{A}^\top\mathbf{A}\mathbf{x} - 2\mathbf{A}^\top\mathbf{b} = \mathbf{0}

이를 정리하면 정규 방정식(normal equations)을 얻는다.

\mathbf{A}^\top\mathbf{A}\hat{\mathbf{x}} = \mathbf{A}^\top\mathbf{b}

\mathbf{A}가 완전 열 계수(full column rank), 즉 \text{rank}(\mathbf{A}) = n이면, \mathbf{A}^\top\mathbf{A} \in \mathbb{R}^{n \times n}은 양의 정부호(positive definite)이므로 가역이다. 이 경우 유일한 최소 제곱 해가 존재한다.

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

행렬 \mathbf{A}^+ = (\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top을 \mathbf{A}의 왼쪽 의사역행렬(left pseudoinverse) 또는 무어-펜로즈 의사역행렬(Moore-Penrose pseudoinverse)의 특수한 경우라 한다.

4. 기하학적 해석: 직교 사영

최소 제곱 해의 기하학적 의미는 직교 사영(orthogonal projection)이다. \hat{\mathbf{x}}에 의한 \mathbf{A}\hat{\mathbf{x}}는 \mathbf{b}를 열 공간 \text{Col}(\mathbf{A})에 직교 사영한 것이다.

잔차 벡터 \mathbf{r} = \mathbf{b} - \mathbf{A}\hat{\mathbf{x}}는 열 공간에 직교한다. 정규 방정식 \mathbf{A}^\top(\mathbf{b} - \mathbf{A}\hat{\mathbf{x}}) = \mathbf{0}은 바로 이 직교 조건을 의미한다. \mathbf{A}^\top\mathbf{r} = \mathbf{0}이므로 \mathbf{r} \in \text{Null}(\mathbf{A}^\top) = \text{Col}(\mathbf{A})^\perp이다.

사영 행렬(projection matrix) \mathbf{P}는 다음과 같이 정의된다.

\mathbf{P} = \mathbf{A}(\mathbf{A}^\top\mathbf{A})^{-1}\mathbf{A}^\top

이 행렬은 다음 성질을 만족한다.

• \mathbf{P}^2 = \mathbf{P} (멱등성, idempotency)
• \mathbf{P}^\top = \mathbf{P} (대칭성)
• \mathbf{P}\mathbf{b} = \mathbf{A}\hat{\mathbf{x}} (사영된 벡터)

\mathbf{b}와 사영 \mathbf{P}\mathbf{b} 사이의 거리 \|\mathbf{b} - \mathbf{P}\mathbf{b}\|가 최소 잔차이며, 피타고라스 정리에 의하여 \|\mathbf{b}\|^2 = \|\mathbf{P}\mathbf{b}\|^2 + \|\mathbf{b} - \mathbf{P}\mathbf{b}\|^2이 성립한다.

5. 수치적 풀이 방법

정규 방정식을 직접 계산하는 것은 수치적으로 불안정할 수 있다. \mathbf{A}^\top\mathbf{A}의 조건수는 \mathbf{A}의 조건수의 제곱이므로, \kappa(\mathbf{A}^\top\mathbf{A}) = \kappa(\mathbf{A})^2이다. 이는 반올림 오차의 영향을 크게 증폭시킨다.

QR 분해를 이용한 풀이: \mathbf{A} = \mathbf{Q}\mathbf{R}로 분해하면 (\mathbf{Q} \in \mathbb{R}^{m \times n}, \mathbf{R} \in \mathbb{R}^{n \times n}),

\mathbf{A}^\top\mathbf{A}\hat{\mathbf{x}} = \mathbf{R}^\top\mathbf{Q}^\top\mathbf{Q}\mathbf{R}\hat{\mathbf{x}} = \mathbf{R}^\top\mathbf{R}\hat{\mathbf{x}} = \mathbf{A}^\top\mathbf{b} = \mathbf{R}^\top\mathbf{Q}^\top\mathbf{b}

\mathbf{R}^\top이 가역이면 양변을 소거하여 \mathbf{R}\hat{\mathbf{x}} = \mathbf{Q}^\top\mathbf{b}를 얻는다. 이 상삼각 시스템은 후방 대입으로 O(n^2)에 풀 수 있다. QR 분해의 복잡도는 O(mn^2)이며, \mathbf{A}^\top\mathbf{A}를 형성하지 않으므로 조건수가 보존되어 수치적으로 더 안정적이다.

SVD를 이용한 풀이: \mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top에서 최소 제곱 해는 \hat{\mathbf{x}} = \mathbf{V}\boldsymbol{\Sigma}^{-1}\mathbf{U}^\top\mathbf{b} = \sum_{i=1}^{r}\frac{\mathbf{u}_i^\top\mathbf{b}}{\sigma_i}\mathbf{v}_i이다. 이 방법은 계수 부족인 경우에도 적용 가능하며, 작은 특이값의 영향을 절단(truncation)하여 정규화 효과를 얻을 수 있다.

6. 정규화된 최소 제곱법

과적합(overfitting)을 방지하거나 악조건 시스템을 안정화하기 위해 정규화 항을 추가한다.

릿지 회귀(Ridge Regression, L2 정규화): 목적함수에 \lambda\|\mathbf{x}\|_2^2 항을 추가한다.

\hat{\mathbf{x}}_\lambda = \arg\min_{\mathbf{x}} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2 + \lambda\|\mathbf{x}\|_2^2

정규 방정식은 (\mathbf{A}^\top\mathbf{A} + \lambda\mathbf{I})\hat{\mathbf{x}}_\lambda = \mathbf{A}^\top\mathbf{b}이다. \lambda > 0이면 \mathbf{A}^\top\mathbf{A} + \lambda\mathbf{I}는 항상 양의 정부호이므로 해가 유일하게 존재한다. 조건수는 \kappa(\mathbf{A}^\top\mathbf{A} + \lambda\mathbf{I}) = \frac{\sigma_1^2 + \lambda}{\sigma_n^2 + \lambda}로 개선된다.

라소 회귀(Lasso Regression, L1 정규화): \lambda\|\mathbf{x}\|_1 항을 추가하면 해의 희소성(sparsity)을 유도한다. L1 노름은 미분 불가능한 점이 있으므로 닫힌 형태의 해가 존재하지 않으며, 근위 기울기법(proximal gradient method) 등의 반복 알고리즘으로 풀어야 한다.

7. 딥러닝에서의 최소 제곱법

최소 제곱법은 딥러닝의 수학적 기반을 이루는 핵심 기법이다.

손실 함수로서의 평균 제곱 오차(MSE): 회귀 문제에서 가장 기본적인 손실 함수 \mathcal{L} = \frac{1}{N}\sum_{i=1}^{N}\|f(\mathbf{x}_i; \boldsymbol{\theta}) - \mathbf{y}_i\|^2는 최소 제곱 목적함수의 확장이다. f가 선형이면 정규 방정식으로 닫힌 형태의 해를 구할 수 있고, 비선형이면 경사 하강법으로 반복적으로 최적화한다.

선형 계층의 최적 가중치: 단일 선형 계층 \hat{\mathbf{y}} = \mathbf{W}\mathbf{x} + \mathbf{b}의 MSE 최소화는 최소 제곱 문제와 정확히 동일하다. 다중 계층 선형 네트워크도 전체적으로는 단일 선형 변환으로 축약되므로, 비선형 활성화 함수가 없는 심층 네트워크의 최적해는 정규 방정식으로 구할 수 있다.

가중 최소 제곱법(Weighted Least Squares): 각 데이터 점에 가중치 w_i를 부여하여 \min_{\mathbf{x}} \sum_{i} w_i((\mathbf{A}\mathbf{x})_i - b_i)^2를 풀면, 정규 방정식은 \mathbf{A}^\top\mathbf{W}\mathbf{A}\hat{\mathbf{x}} = \mathbf{A}^\top\mathbf{W}\mathbf{b}가 된다 (\mathbf{W} = \text{diag}(w_1, \ldots, w_m)). 이는 이분산(heteroscedastic) 잡음 모델의 최대 우도 추정과 동등하며, 어텐션 메커니즘의 가중 평균과 개념적 유사성을 가진다.