선형대수학 - 최소제곱법

안녕하세요. 지난 포스팅의 선형대수학 - 수반연산자에서는 처음으로 내적공간 사이의 선형연산자를 다루었습니다. 이를 기반으로 새로운 연산자인 수반연산자와 그 성질에 대해 알아보았죠. 오늘은 이를 활용한 최소제곱법에 대해서 알아보도록 하겠습니다. 

 

 

기계학습이나 심층학습을 어느 정도 공부하신 분들이라면 가장 먼저 다루는 모델 중 하나가 바로 선형모델입니다. 간단하게 생각해 보면 위와 같은 그림을 생각해 볼 수 있죠. 기본적인 가정은 시간 $t_{1}, \dots, t_{m}$에 따라 어떤 실험 측정값 $y_{1}, \dots, y_{m}$을 얻었다고 하겠습니다. 그리고 시간과 측정값 $\{ (t_{1}, y_{1}), \dots, (t_{m}, y_{m}) \}$을 쌍으로 위 그림과 같이 2차원 좌표평면에 그릴 수 있습니다. 이때, 총 $m$개의 쌍을 가장 잘 설명할 수 있는 선형모델 $y = ct + d$이 존재할 것입니다. 즉, 저희가 원하는 것은 위 데이터 쌍이 주어졌을 때 선형모델 $y = ct + d$의 최적의 계수쌍인 $(c, d)$를 찾는 것입니다. 

 

일단, 문제가 정의되었으니 다음으로 생각해봐야 할 것은 "무엇"을 기준으로 최적의 모델을 찾아야 할지 선택해야 합니다. 가장 일반적인 방법은 실제 측정값 $y_{i}$와 추정한 모델을 기반으로 얻은 $i$번째 예측값 $\hat {y}_{i} = ct_{i} + d$ 사이의 차이를 계산하는 것입니다. 그렇다면 바로 $y_{i} - \hat {y}_{i}$를 계산하면 될까요? 이렇게 되면 해당 값의 범위가 $(-\infty, \infty)$가 되기 때문에 효율적이지 않습니다. 이를 위해 제곱값인 $(y_{i} - \hat {y}_{i})^{2}$을 사용하게 됩니다. 이러면 범위가 $(0, \infty)$이 되어 $y_{i} - \hat {y}_{i} = 0$이 되는 $c$와 $d$를 찾으면 됩니다. 하지만, 문제의 가정에 의해 총 $m$개의 데이터쌍이 존재하기 때문에 최종 식은 다음과 같습니다. 

 

$$E = \sum_{i}^{m} (y_{i} - \hat {y}_{i})^{2} = \sum_{i = 1}^{m} (y_{i} - ct_{i} - d)^{2}$$

 

따라서 저희가 원하는 문제는 $E$를 최소화하는 선형함수 $y = ct + d$의 계수 $c$와 $d$를 찾는 것이 됩니다. 이러한 이유로 제곱과 최솟값을 찾는 방법을 생각하기 때문에 선형함수 $y = ct + d$를 최소제곱선 (least square line)이라고 부르기도 합니다. 

 

하지만, 지금까지 저희가 선형대수학을 배우면서 행렬에 대해 다루었지만 위 수식에서는 전혀 찾아볼 수 없습니다. 이제 위 수식을 행렬의 형태로 바꾸어야 합니다. 이를 위해 $A, x, y$를 각각 다음과 같이 정의해 보겠습니다. 

 

$$A = \begin{pmatrix} t_{1} & 1 \\ \vdots & \vdots \\ t_{m} & 1 \end {pmatrix}, x = \begin {pmatrix} c \\ d \end {pmatrix}, y = \begin {pmatrix} y_{1} \\ \vdots \\ y_{m}  \end {pmatrix}$$

 

여기서, 행렬-벡터곱 $Ax = \begin {pmatrix} t_{1} & 1 \\ \vdots & \vdots \\ t_{m} & 1 \end {pmatrix} \begin{pmatrix} c \\ d \end {pmatrix} = ( ct_{1} + d ) + (ct_{2} + d) + \cdots + (ct_{m} + d) $인 것을 볼 수 있죠. 즉, $Ax$는 $E$의 두 번째 항을 의미하게 됩니다. 따라서, $y - Ax$라고 하면 각 행에 $y_{i} - ct_{i} - d$가 포함됩니다. 그런데 문제는 이를 전부 더하고 제곱하는 과정이 필요하겠죠? 이를 위해 $y - Ax$에 노름을 취한 뒤 제곱을 하면 됩니다. 

 

$$E = \sum_{i = 1}^{m} (y_{i} - ct_{i} - d)^{2} =  \lVert y - Ax \rVert^{2}$$

 

위 과정과 같이 일반적인 합형태를 행렬의 형태로 바꾸어 표현하는 경우가 굉장히 많기 때문에 알아두시면 최적화 및 기계학습 관련 공부 시 도움이 되실 겁니다. 위 수식을 보시면 결국 바뀌는 것은 벡터 $x$ 밖에 없습니다. 어차피 $A$와 $y$는 시간에 대한 실험 측정값으로 절대 바뀌지 않기 때문이죠. 따라서, 최적화된 벡터 $x_{0}$가 주어지면 임의의 벡터 $x$ 사이의 관계는 다음과 같습니다. 

 

$$\lVert y - Ax_{0} \rVert \le \lVert y - Ax \rVert $$

 

이제부터는 일반화를 위해 $x_{0} \in \mathbf {F}^{n}$이라고 생각하겠습니다. 그리고 $A \in \mathbf {F}^{m \times n}$이고 $y = \in mathbf {m}$이라고 하죠. 여기서 $n$차원을 고려하는 이유는 데이터의 속성이 하나만 있지 않고 여러 개가 있을 수도 있기 때문입니다. 대표적으로 kaggle의 타이타닉 생존자 분류 예측을 위해 사용하는 속성이 굉장히 여러 개가 있죠. 

 

다음으로 저희는 $x_{0}$를 명시적으로 (emplicitely) 얻기 위한 정리를 유도해야 합니다. 이를 위해 새로운 표기법과 2가지 보조정리 (Lemma)를 먼저 알아야 합니다. 이제부터 임의의 두 벡터 $x, y \in \mathbf {F}^{n}$에 대해서 $\langle x, y \rangle_{n}$을 내적공간 $\mathbf {F}^{n}$에서 정의된 두 벡터 $x$와 $y$ 사이의 표준 내적이라고 하겠습니다. 이때, 두 벡터 $x$와 $y$가 열벡터라면 $\langle x, y \rangle = y^{*} x$와 동일합니다. 이를 기반으로 저희는 2개의 보조정리를 생각합니다. 

 

 보조정리 1

행렬 $A \in M_{m \times n}(F)$과 두 벡터 $x \in \mathbf {F}^{n}$ 그리고 $y \in \mathbf {F}^{m}$이 주어졌다고 하자. 그러면 $\langle Ax, y \rangle_{m} = \langle x, A^{*} y \rangle_{n}$

 

설명

여기서 만약 선형대수학 - 수반연산자의 정리 2를 떠올리셨다면 아주 훌륭합니다. 쉽게 말해 보조정리 1은 선형대수학 - 수반연산자의 정리 2의 행렬 버전이라고 생각하시면 될 거 같습니다. 증명의 핵심은 선형대수학 - 수반연산자의 따름 정리 4-1.(c)를 활용하면 아주 쉽게 증명할 수 있습니다. 

 

Proof)

$$\begin {align*} \langle Ax, y \rangle_{m} &= y^{*} (Ax) \\ &= (y^{*} A) x \\ &= (A^{*} y)^{*} x = \langle x, A^{*} y \rangle_{n} \end {align*}$$

 

 보조정리 2

행렬 $A \in M_{m \times n}(\mathbf {F})$라고 하자. 그러면 $\text {rank} (A^{*}A) = \text {rank} (A)$이다. 

 

설명

여기서 $\text {rank}$는 선형대수학 - 선형변환, 영 공간, 치역의 정의 4를 의미합니다. 즉, 행렬의 열공간의 차원이라고 보면 될 거 같습니다. 증명의 핵심은 선형대수학 - 선형변환, 영 공간, 치역의 정리 3 (차원정리)를 활용합니다. 

 

Proof)

선형대수학 - 선형변환, 영 공간, 치역의 정리 3 (차원정리)에 의해 보조정리 2는 임의의 벡터 $x \in \mathbf {F}^{n}$에 대해 $A^{*} Ax = 0$ 인 것과 $Ax = 0$인 것이 동치임을 보이면 된다. 

 

1). $(\Rightarrow)$: $A^{*}Ax = 0$이라고 가정하자. 

 

$$\begin {align*} 0 &= \langle A^{*} Ax, x \rangle_{n} \\ &= \langle Ax, A^{**} x \rangle_{m} \\ &= \langle Ax, Ax \rangle_{m} \end {align*}$$

 

따라서, $Ax = 0$이다. 

 

2). $(\Leftarrow)$: $Ax = 0$이라고 가정하자. 

 

$$\begin {align*} A^{*} Ax &= A^{*} (Ax) \\ &= A^{*} 0 = 0 \end {align*}$$

 

 정리 1

행렬 $A \in M_{m \times n} (\mathbf {F})$과 벡터 $y \in \mathbf {F}^{m}$에 대해서 임의의 벡터 $x \in \mathbf {F}^{n}$에 대해서 $(A^{*} A) x_{0} = A^{*} y$와 $\lVert Ax_{0} - y \rVert \le \lVert Ax - y \rVert$를 만족하는 벡터 $x_{0} \in \mathbf {F}^{n}$이 존재한다. 또한, $\text {rank} (A) = n$이면 $x_{0} = (A^{*} A)^{-1} A^{*} y$이다. 

 

설명

정리 1은 저희의 목표를 달성하고 있습니다. 다만, $A$가 가역행렬이어야만 $x_{0}$를 명시적으로 구할 수 있죠. 만약, 비가역행렬이라면 다른 해근사법을 이용해서 구해야 합니다. 이제, 간단하게 증명해보도록 하죠. 핵심은 직교여공간과 앞에서 설명드린 보조정리를 적절하게 사용하면 됩니다. 

 

Proof)

행렬 $A \in M_{m \times n} (\mathbf {F})$과 벡터 $y \in \mathbf {F}^{m}$가 주어졌다고 하자. 그리고 $W = \{ Ax | x \in \mathbf {F}^{n} \}$이라고 하면 좌곱셈 변환의 정의에 의해 $W = R(L_{A})$이다. 이때, 선형대수학 - 직교여공간의 따름정리1-1에 의해 부분공간 $W$에 벡터 $y$와 최단거리의 유일한 벡터가 존재한다. 편의를 위해 임의의 벡터 $x_{0} \in \mathbf {F}^{m}$에 대해서 $Ax_{0}$라고 하자. 그러면 모든 $x \in \mathbf {F}^{m}$에 대해서 $\lVert Ax_{0} - y \rVert \le \lVert Ax - y \rVert$를 만족하기 때문에 $x_{0}$는 $E$를 최소화하는 조건을 가지게 된다. 

 

여기서 직교여공간의 정의에 의해 $Ax_{0} - y \in W^{\perp}$임을 주목하자. 따라서, 임의의 $x \in \mathbf {F}^{m}$에 대해서 $Ax \in W$이기 때문에 $\langle Ax, Ax_{0} - y \rangle_{n} = 0$이다. 이는 보조정리 1에 의해 $\langle x, A^{*} (Ax_{0} - y) \rangle_{n} = 0$과 동치이다. 따라서, $A^{*} (Ax_{0} - y) = 0$이다. 이러한 결과는 $(A^{*} A) x = A^{*} y$임을 증명한다. 

 

마지막으로 $\text {rank} (A) = n$이라고 하면 보조정리 2에 의해 $\text {rank} (A^{*} A) = n$이므로 $A^{*} A$는 가역행렬이다. 따라서 $x = (A^{*} A)^{-1} A^{*} y$임이 증명된다. 

 

오늘은 수반연산자의 성질을 이용해서 최소제곱법을 증명해 보는 시간을 가졌습니다. 주의하셔야 할 점은 최소제곱법을 증명하는 방법은 위 방법만 있는 것이 아니기 때문에 다른 방법도 찾아보시는 것을 추천드립니다. 저희는 아직 내적공간의 선형연산자의 특성에 대해서 많이 알지 못합니다. 현재 알고 있는 것은 수반연산 하나뿐이죠. 선형대수학에서 핵심적인 분야 중 하나은 선형연산자의 고유벡터에 대한 내용입니다. 하지만, 그 고유벡터들이 정규직교를 만족하는 조건은 무엇일까요? 다음 포스팅에서 보도록 하겠습니다.