13장. 직교성, 사영, 최소제곱

측정 데이터에 오차가 있으면 모든 점을 지나는 직선은 없습니다. 그러면 '가장 가까운' 직선은 무엇일까요? 이 장에서는 직교(수직)와 사영(그림자)을 이용해 그 답인 최소제곱법을 유도합니다. 통계의 선형회귀와 머신러닝의 가장 기본적인 학습 문제가 바로 이 계산입니다.

13.1 풀 수 없는 연립방정식을 풀기

질문. 실험에서 시간 $t = 0, 1, 2$에 측정값 $6, 0, 0$을 얻었습니다. 이 점들이 직선 $b = C + Dt$ 위에 있다고 믿고 $C$, $D$를 구하려 합니다. 점이 세 개, 미지수가 두 개라 연립방정식

은 해가 없습니다. 그래도 “가장 그럴듯한” 직선을 고를 수 있을까요?

실제 데이터에는 언제나 오차가 있어서, 식이 미지수보다 많은 $A\mathbf{x} = \mathbf{b}$는 대부분 해가 없습니다. $\mathbf{b}$가 $C(A)$ 밖에 있기 때문입니다. 이때 할 수 있는 최선은 $C(A)$ 안에서 $\mathbf{b}$에 가장 가까운 점 $\mathbf{p}$를 찾고 $A\hat{\mathbf{x}} = \mathbf{p}$를 푸는 것입니다. 가장 가까운 점은 수선의 발, 즉 사영입니다. 그래서 이 장은 수직(직교)에서 시작합니다.

13.2 직교하는 부분공간

정의 13.1 (직교하는 부분공간). $\mathbb{R}^n$의 두 부분공간 $S$, $T$에서 $S$의 모든 벡터가 $T$의 모든 벡터와 수직이면, 즉

이면 $S$와 $T$가 직교한다(orthogonal)고 하고 $S \perp T$로 씁니다.

$\mathbb{R}^3$에서 $x$축과 $y$축은 직교합니다. $xy$ 평면과 $z$축도 직교합니다. 그러나 $xy$ 평면과 $yz$ 평면은 직교하지 않습니다. 둘 다 $y$축을 포함하는데, $\mathbf{e}_2$는 자기 자신과 수직이 아니기 때문입니다. 직교하는 두 부분공간은 $\mathbf{0}$ 외에 공통 원소가 없습니다($\mathbf{v}^T\mathbf{v} = 0$이면 $\mathbf{v} = \mathbf{0}$).

정리 13.2 (영공간과 행공간은 직교합니다). $A \in \mathbb{R}^{m \times n}$이면 $N(A) \perp C(A^T)$이고 $N(A^T) \perp C(A)$입니다.

증명. $A\mathbf{x} = \mathbf{0}$을 행 그림으로 쓰면

즉 $\mathbf{x}$는 $A$의 모든 행과 수직입니다. 따라서 행들의 모든 일차결합, 즉 행공간 전체와 수직입니다. 둘째 주장은 첫째를 $A^T$에 적용한 것입니다. ■

정의 13.3 (직교여공간). 부분공간 $S$에 수직인 모든 벡터의 집합 $S^\perp = \{\mathbf{v} \in \mathbb{R}^n : \mathbf{v}^T\mathbf{s} = 0\ \forall \mathbf{s} \in S\}$를 $S$의 직교여공간(orthogonal complement)이라 합니다.

정리 13.4 (기본정리, 2부). $A \in \mathbb{R}^{m \times n}$에 대하여

증명. 정리 13.2의 증명은 사실 “$\mathbf{x} \in N(A) \iff \mathbf{x}$가 모든 행과 수직”입니다. 모든 행과 수직인 것은 행공간 전체와 수직인 것과 같으므로 $N(A) = C(A^T)^\perp$. 둘째는 $A^T$에 적용. ■

12장의 차원과 합치면 $\dim C(A^T) + \dim N(A) = r + (n - r) = n$입니다. 즉 $\mathbb{R}^n$은 서로 직교하는 행공간과 영공간으로 나뉩니다. 그림 12.2에서 두 공간을 직각으로 그린 이유가 이것입니다.

정리 13.5 (직교 분해). 모든 $\mathbf{x} \in \mathbb{R}^n$은 $\mathbf{x} = \mathbf{x}_r + \mathbf{x}_n$ ($\mathbf{x}_r \in C(A^T)$, $\mathbf{x}_n \in N(A)$)으로 유일하게 쓰입니다.

증명. 행공간의 기저 $r$개와 영공간의 기저 $n - r$개를 합치면 $n$개입니다. 이들이 독립임을 보입시다. $\sum a_i\mathbf{u}_i + \sum b_j\mathbf{w}_j = \mathbf{0}$ ($\mathbf{u}_i$는 행공간, $\mathbf{w}_j$는 영공간의 기저)이면 $\mathbf{y} = \sum a_i\mathbf{u}_i = -\sum b_j\mathbf{w}_j$는 두 공간에 모두 속하므로 자기 자신과 수직, 즉 $\mathbf{y} = \mathbf{0}$입니다. 각 기저의 독립성에서 모든 계수가 0. 따라서 $n$개의 독립 벡터는 $\mathbb{R}^n$의 기저이고(정리 12.14), 모든 $\mathbf{x}$가 유일한 방법으로 이들의 일차결합으로 쓰입니다. 행공간 기저 부분을 $\mathbf{x}_r$, 나머지를 $\mathbf{x}_n$이라 하면 됩니다. ■

$A\mathbf{x} = A\mathbf{x}_r + A\mathbf{x}_n = A\mathbf{x}_r$입니다. 영공간 성분은 지워지고, 행공간 성분만 출력에 기여합니다. 게다가 $A$는 행공간을 열공간으로 일대일로 보냅니다(문제 13.4). 모든 행렬은, 영공간을 잘라 내고 나면, $r$차원 공간 사이의 가역 변환입니다. 이 관점이 18장의 SVD로 이어집니다.

▶ 문제 13.1–13.4

13.3 코시–슈바르츠 부등식

2.7절에서 $\mathbb{R}^n$의 두 벡터 사이의 각을 $\cos\theta = \dfrac{\mathbf{v}^T\mathbf{w}}{\lVert \mathbf{v} \rVert\,\lVert \mathbf{w} \rVert}$로 정의하면서, 이 값이 $[-1, 1]$에 있다는 증명을 미뤘습니다.

정리 13.6 (코시–슈바르츠 부등식). $\mathbf{v}, \mathbf{w} \in \mathbb{R}^n$이면

등호는 한 벡터가 다른 벡터의 스칼라배일 때만 성립합니다.

증명. $\mathbf{w} = \mathbf{0}$이면 양변이 0입니다. $\mathbf{w} \ne \mathbf{0}$이라 합시다. 모든 실수 $t$에 대해

우변은 $t$에 대한 이차식이고 항상 0 이상이므로 판별식이 0 이하입니다.

정리하면 원하는 부등식입니다. 등호는 이차식이 0이 되는 $t$, 즉 $\mathbf{v} = t\mathbf{w}$인 $t$가 있을 때입니다. ■

따름정리 13.7 (삼각부등식). $\lVert \mathbf{v} + \mathbf{w} \rVert \le \lVert \mathbf{v} \rVert + \lVert \mathbf{w} \rVert$.

증명. $\lVert \mathbf{v} + \mathbf{w} \rVert^2 = \lVert \mathbf{v} \rVert^2 + 2\mathbf{v}^T\mathbf{w} + \lVert \mathbf{w} \rVert^2 \le \lVert \mathbf{v} \rVert^2 + 2\lVert \mathbf{v} \rVert\lVert \mathbf{w} \rVert + \lVert \mathbf{w} \rVert^2 = (\lVert \mathbf{v} \rVert + \lVert \mathbf{w} \rVert)^2$. ■

삼각형의 한 변은 나머지 두 변의 합보다 짧습니다. 2차원에서는 당연한 사실이 $n$차원에서도 성립한다는 것을 내적만으로 증명했습니다.

▶ 문제 13.5–13.6

13.4 직선 위로의 사영

그림 13.1. $\mathbf{b}$를 $\mathbf{a}$ 방향 직선 위로 사영합니다. 오차 $\mathbf{e}$는 직선과 수직입니다.

$\mathbf{b}$에서 $\mathbf{a}$를 지나는 직선에 수선을 내린 발이 $\mathbf{p} = \hat{x}\mathbf{a}$입니다. 오차 $\mathbf{e} = \mathbf{b} - \hat{x}\mathbf{a}$가 $\mathbf{a}$와 수직이라는 조건에서

예제 13.8. $\mathbf{a} = (1, 1, 1)$, $\mathbf{b} = (1, 2, 6)$이면 $\hat{x} = \frac93 = 3$, $\mathbf{p} = (3, 3, 3)$, $\mathbf{e} = (-2, -1, 3)$. 확인: $\mathbf{e}^T\mathbf{a} = 0$. $\mathbf{p}$는 $\mathbf{b}$의 성분들의 평균을 모든 성분에 넣은 벡터입니다(문제 13.8).

13.4.1 사영행렬

$\mathbf{p} = \mathbf{a}\dfrac{\mathbf{a}^T\mathbf{b}}{\mathbf{a}^T\mathbf{a}} = \dfrac{\mathbf{a}\mathbf{a}^T}{\mathbf{a}^T\mathbf{a}}\mathbf{b}$이므로 사영은 행렬

를 곱하는 것입니다. $\mathbf{a}\mathbf{a}^T$는 열×행이므로 $P$는 랭크 1 행렬이고, 열공간은 $\mathbf{a}$를 지나는 직선입니다. 사영행렬은 두 성질을 갖습니다.

둘째 식은 “이미 직선 위에 있는 점을 다시 사영하면 그대로”라는 뜻입니다. 7장에서 본 대로 사영의 고윳값은 1(직선 방향)과 0(수직 방향)입니다.

▶ 문제 13.7–13.8

13.5 부분공간 위로의 사영

질문. $\mathbf{b}$를 직선이 아니라 평면(또는 더 높은 차원의 부분공간) 위로 사영하려면?

부분공간이 $A$의 열공간 $C(A)$라 하고, $A$의 열 $\mathbf{a}_1, \ldots, \mathbf{a}_n$이 독립이라 합시다. 사영 $\mathbf{p}$는 $C(A)$ 안에 있으므로 $\mathbf{p} = A\hat{\mathbf{x}}$입니다. 오차 $\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}}$는 부분공간에 수직이어야 합니다. 즉 모든 열과 수직입니다.

정리 13.4의 말로는 $\mathbf{e} \in N(A^T) = C(A)^\perp$입니다. 정리하면

정규방정식(normal equations) $\quad A^TA\,\hat{\mathbf{x}} = A^T\mathbf{b}$

정리 13.9 ($A^TA$의 가역성). $A^TA$가 가역인 것은 $A$의 열들이 일차독립인 것과 동치입니다.

증명. $A^TA$는 정사각이므로 $N(A^TA) = N(A)$를 보이면 됩니다. $A\mathbf{x} = \mathbf{0}$이면 $A^TA\mathbf{x} = \mathbf{0}$. 거꾸로 $A^TA\mathbf{x} = \mathbf{0}$이면 $\mathbf{x}^TA^TA\mathbf{x} = \lVert A\mathbf{x} \rVert^2 = 0$이므로 $A\mathbf{x} = \mathbf{0}$. ■

증명의 마지막 단계, “$\mathbf{x}^T$를 곱해 길이의 제곱으로 만듭니다”는 기법은 17장과 25장에서 거듭 쓰입니다.

열이 독립이면

$A$가 열 하나 $\mathbf{a}$이면 앞 절의 공식이 됩니다. $P$를 $A(A^TA)^{-1}A^T$보다 더 간단히 쓸 수는 없습니다. $A$가 정사각이 아니므로 $(A^TA)^{-1} = A^{-1}(A^T)^{-1}$로 쪼갤 수 없기 때문입니다. (만약 $A$가 가역이면 $P = I$가 됩니다. 열공간이 $\mathbb{R}^m$ 전체이므로 사영할 것이 없습니다.)

예제 13.10. $A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}$, $\mathbf{b} = (6, 0, 0)$.

$3\hat{x}_1 + 3\hat{x}_2 = 6$, $3\hat{x}_1 + 5\hat{x}_2 = 0$에서 $\hat{x}_2 = -3$, $\hat{x}_1 = 5$. 따라서

확인: $\mathbf{e}^T(1, 1, 1) = 0$, $\mathbf{e}^T(0, 1, 2) = 0$.

▶ 문제 13.9–13.11

13.6 최소제곱

13.1절의 질문으로 돌아갑시다. 직선 $b = C + Dt$가 세 점 $(0, 6)$, $(1, 0)$, $(2, 0)$을 지나려면

이어야 합니다. 정확히 예제 13.10의 $A$와 $\mathbf{b}$입니다. 해는 없지만 $A^TA\hat{\mathbf{x}} = A^T\mathbf{b}$의 해 $\hat{C} = 5$, $\hat{D} = -3$이 “가장 좋은” 직선 $b = 5 - 3t$를 줍니다.

그림 13.2. 최소제곱 직선. 검은 점은 데이터, 흰 점은 직선 위의 값 $\mathbf{p}$. 세로 오차의 제곱합 $1 + 4 + 1 = 6$이 가능한 최소입니다.

“가장 좋습니다”의 정확한 뜻은 다음 정리가 말해 줍니다.

정리 13.11 (최소제곱). $\hat{\mathbf{x}}$가 $A^TA\hat{\mathbf{x}} = A^T\mathbf{b}$를 만족하면, 모든 $\mathbf{x}$에 대해

즉 $\hat{\mathbf{x}}$는 오차의 제곱합 $\lVert A\mathbf{x} - \mathbf{b} \rVert^2$을 최소로 만듭니다.

증명. $A\mathbf{x} - \mathbf{b} = A(\mathbf{x} - \hat{\mathbf{x}}) + (A\hat{\mathbf{x}} - \mathbf{b})$입니다. 첫째 항은 $C(A)$에 있고, 둘째 항 $-\mathbf{e}$는 정규방정식에 의해 $C(A)$와 수직입니다. 수직인 두 벡터의 합이므로 피타고라스 정리(문제 2.13)에 의해 제곱 길이가 더해집니다. ■

그림 13.2의 세로 오차 $e_1, e_2, e_3$은 예제 13.10의 $\mathbf{e} = (1, -2, 1)$의 성분입니다. 이 방법을 최소제곱법(method of least squares)이라 하며, 1800년대 초 가우스와 르장드르가 천체의 궤도를 구하는 데 썼습니다. 오늘날 데이터에 직선, 곡선, 평면을 맞추는 거의 모든 방법의 기초입니다.

직관. 두 가지 그림이 같은 계산을 합니다.

• $\mathbb{R}^2$ ($t$–$b$ 평면): 점 세 개에 가장 가까운 직선. 세로 오차의 제곱합을 최소로.
• $\mathbb{R}^3$ (데이터 공간): 벡터 $\mathbf{b}$를 $C(A)$라는 평면 위로 사영. 수선의 길이를 최소로.

첫째 그림은 보기 쉽고, 둘째 그림은 왜 정규방정식이 나오는지 설명합니다.

직선이 아니라 포물선 $b = C + Dt + Et^2$을 맞추고 싶으면 $A$에 $t_i^2$로 된 열을 하나 추가하면 됩니다. 미지수가 $C, D, E$로 늘어날 뿐 방법은 똑같습니다. 맞추는 함수는 곡선이어도, 미지수에 대해서는 선형이기 때문입니다.

▶ 문제 13.12–13.14

쓰이는 곳. 선형회귀 $\hat\beta = (X^TX)^{-1}X^Ty$는 이 장의 정규방정식 그 자체입니다. 실험 데이터에 곡선을 맞추는 일, GPS의 위치 추정, 머신러닝의 평균제곱오차 손실이 모두 최소제곱 문제입니다.

이 장의 요약

• $N(A) \perp C(A^T)$, $N(A^T) \perp C(A)$. 더 정확히 $N(A) = C(A^T)^\perp$이고 $\mathbb{R}^n$ = 행공간 $\oplus$ 영공간(직교 분해).
• 코시–슈바르츠 $\lvert \mathbf{v}^T\mathbf{w} \rvert \le \lVert \mathbf{v} \rVert\lVert \mathbf{w} \rVert$, 삼각부등식.
• 직선 위로의 사영: $\mathbf{p} = \dfrac{\mathbf{a}^T\mathbf{b}}{\mathbf{a}^T\mathbf{a}}\mathbf{a}$, $P = \dfrac{\mathbf{a}\mathbf{a}^T}{\mathbf{a}^T\mathbf{a}}$. $P^T = P = P^2$.
• 부분공간 $C(A)$ 위로의 사영: $A^TA\hat{\mathbf{x}} = A^T\mathbf{b}$, $P = A(A^TA)^{-1}A^T$. $A^TA$는 열이 독립일 때 가역.
• 최소제곱: $A\mathbf{x} = \mathbf{b}$의 해가 없으면 정규방정식의 해 $\hat{\mathbf{x}}$가 $\lVert A\mathbf{x} - \mathbf{b} \rVert^2$을 최소화합니다. 오차 $\mathbf{e}$는 $C(A)$와 수직.

문제

2/3
1/3
-1/3
1/3
-1/3
1/3

11
3
5
11/15

3/5
6/5
1/5
2/5
4/5

11/3
4/3
7/3
-5/3
5/3
5/3

1.3
1.4