Least Squares Problem (인공지능을 위한 선형대수, 20210513~20210514)

핵심키워드

Least Square를 알아보기 위해 아래의 개념을 이해하고 넘어가도록 한다.

• 내적(Inner Product, Dot Product)
• 벡터의 길이(Vector Norm)
• 단위벡터(Unit Vector)
• 직교벡터(Orthogonal Vectors)

 

Least Square를 다룰 때는 보통 방정식의 개수가 변수의 개수보다 많을 때이다. 중학교로 돌아가서 간단하게 이해해보자.

$$ 66 = 2x_1 + 3x_2 $$

$$ 34 = 3x_1 + 6x_2 $$

위의 두 식이 있다고, $x_1$과 $x_2$는 독립이라고 가정하면, 우리는 $x_1$과 $x_2$의 정확한 해를 구할 수 있다. 미지수의 개수가 2개, 식이 2개이기 때문이다. 그런데 만약 이런 상황은 어떻게 될까?

 

$$ 66 = 2x_1 + 3x_2 $$

$$ 34 = 3x_1 + 6x_2 $$

$$ 54 = 7x_1 + 2x_2 $$

$$ 12 = 9x_1 + 4x_2 $$

 

당연히 4개의 식을 다 표현할 수 있는 $x_1, x_2$는 존재하지 않는다. 이런 상황을 우리는 Over-determined라고 부르며 이런 경우에 해는 존재하지 않는다고 한다. 위의 식을 행렬로 나타내보자.

 

$ \begin{bmatrix} 66 \\ 34 \\ 54 \\ 12 \end{bmatrix} = $ $\begin{bmatrix} 2 \\ 3 \\ 7 \\ 9 \end{bmatrix}x_1 + $ $\begin{bmatrix} 3 \\ 6 \\ 2 \\ 4 \end{bmatrix}x_2$

 

혹은

 

$ \begin{bmatrix} 66 \\ 34 \\ 54 \\ 12 \end{bmatrix} = $ $\begin{bmatrix} 2 & 3 \\ 3 & 6 \\ 7 & 2 \\ 9 & 4 \end{bmatrix}$ $\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$

 

이렇게 표현할 수 있다. 해가 존재하지 않는, over-determined의 상황을 선형대수적으로 표현해보자.

   우리가 가지고 있는 재료벡터는 $x_1, x_2$가 있다. 해가 존재하기 위해서는 이 두 재료벡터의 $Span$안에 해가 포함되어야 한다. $Span \in {x_1, x_2}$의 차원이 $\mathbb{R}^2$라고 하더라도 equation이 늘어나 $x_1, x_2$가 가지고 있는 coefficient들이 많아져서 위와 같이 $\mathbb{R}^4$가 되면(equation이 4개니까), $\mathbb{R}^4$의 방대한 Space에 존재하는 값들이 2차원의 $Span$안에 fit이 될 확률은 극히 적어지게 된다. 즉, Solution을 나타낼 수 있는 재료벡터들의 $Span$은 고정되어 있는데 반해, equation이 증가할 수록 전체 공간은 넓어지기 때문에 Label이 $Span$에 포함될 확률이 희박해진다는 뜻이다. 그래서 equations > variables 의 상황에서는 보통 해가 존재하지 않게 된다.

해는 존재하지 않지만, 그럼에도 불구하고 근사적으로라도 해를 한 번 구해보자고 하는 것이 이 Least Square의 아이디어이다. 근사라는 것이 어떤 수학적의미를 가지는지, 그리고 어떤 것이 더 좋은 근사된 solution이냐를 알아보도록 하자.

이에 앞서 기본적인 개념들을 짚고 넘어가도록 한다.

• 내적(Inner Product, Dot Product)
• 벡터의 길이(Vector Norm)
• 단위벡터(Unit Vector)
• 직교벡터(Orthogonal Vectors)

내적이란 간단히 말해, 벡터들의 곱이 scala로 계산되는 계산 방법이다. 두 개의 $u, v$컬럼이 있을 때 하나를 Transpose한 후 곱하면 위와 같이 단일 scala값을 가지는 것을 확인할 수 있다.

내적이라고 하는 관계는, 점이라는 notation을 쓴다. 그리고 $u \cdot v = u^Tv$ 와 같다. 주의해야할 점은, $u^Tv$의 경우에는 $u^T \cdot v$로 표현할 수 없다. $\cdot$자체가 Transpose의 의미를 담고 있기 때문이다. 그리고 b, c를 묶어서 설명하는 부분이 아래에 있다.

$$(c_1u_1 + ... + c_pu_p) \cdot w = c_1(u_1 \cdot w ) + ... + c_p(u_p \cdot w )$$

왼쪽 식은 $p$개의 벡터 $u$들을 $p$개의 $c$와 선형결합한 후 $w$벡터와의 내적, 오른쪽 식은 $p$개의 벡터들 $u$와 $w$를 내적한 것들을 $p$개의 $c$와 선형결합한 것이며, 이 둘이 같다는 것을 묶어서 설명하고 있다.

 

마지막 d의 조건은, 벡터 $u$가 있을 때 자기 자신을 내적하는 경우 $u \cdot u = 0 $를 만족하는 것은 오직 $u$가 영벡터였을 때만 가능하다라는 것이다. ( 바꿔말하면 벡터의 길이가 0이 될 때는 오직 자기 자신이 0일때만 가능하다는 뜻이다 )

 

다음은 Vector Norm에 대해서 알아보자. Norm이란 Vector의 길이이다. Norm의 정의는 non-negative하며 벡터$v$를 내적한 후 square root를 한 값이다. 길이만을 나타내므로 Vector의 Norm은 언제나 scala값을 가진다. 이 벡터의 길이라는 것은 위에서 내적의 성질 d)에서 설명했던 것처럼 자기 자신의 내적에 square root를 취한 것과 같다.

$$ \| v \| = \sqrt{v \cdot v} = \sqrt{v_1^2 + v_2^2 + v_3^3 + .. + v_n^2} \quad and \; \| v \| ^2 = v \cdot v $$

아래의 그림처럼 2차원인 $(3,4)$의 경우에는 피타고라스 정의와 동일하다.

$$ v=\begin{bmatrix} 3 \\ 4 \end{bmatrix} $$

$$ \| v\| = \sqrt{v \cdot v} = \sqrt{ 3^2 + 4^2 } =  \sqrt{25} = 5 $$

 

3차원의 경우에는 

$$ v=\begin{bmatrix} 3 \\ 4 \\ 6 \end{bmatrix} $$

$$ \| v\| = \sqrt{v \cdot v} = \sqrt{3^2 + 4^2 + 6^2} =  \sqrt{61} $$

 

또한 벡터 $v$와 상수 $c$가 있을 때 $c$배를 한 벡터 $v$의 길이(norm)은 $c$배만큼 늘어나게 되며 아래와 같이 나타낼 수 있다. 즉 $c$상수배를 한 벡터 $v$의 norm을 구하는 식이다.

$$ \| c\textbf{v} \| $$

그리고 위의 식은, 벡터 $v$의 norm을 구한 후 상수 $c$의 절대값을 곱한 것과 동일하다. 즉, 아래가 성립한다.

$$ \| c\textbf{v} \|  =  |c| \| \textbf{v} \| $$

오른쪽 식의 상수 $c$에 절대값을 취하는 이유는, $ \| c\textbf{v} \| $에서 상수 $c$는 제곱되어 계산되기 때문에 negative값이 나오지 않는 것을 오른쪽 식에도 똑같이 적용해주기 위해서이다.

 

그리고 이런 성질을 이용해서 우리는 임의의 벡터 $v$을 normalization하여 방향은 바꾸지 않고 길이가 1인 벡터를 만들게 되면 이것을 Unit Vector 혹은 단위벡터로 통칭한다. 

$$ v = \begin{bmatrix} 3 \\ 4 \end{bmatrix}$$

$$ \| v \| = v \cdot v = \sqrt{3^2 + 4^2} = 5 $$

여기서 만약 길이가 1인 unit vector $u$를 만들고 싶다면 벡터$v$의 norm을 나눠준(여기에서는 5를) vector가 unit vector가 된다. 식은 아래와 같다.

$$ u = \frac{1}{\| v \|}v $$

위의 벡터 $v$를 예로 들어 Unit Vector $u$를 구해보면 아래와 같다.

$$ \| v \| = 5 $$

$$ u = \frac{1}{5}v = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} \frac{3}{5} \\ \frac{4}{5} \end{bmatrix} \; thus, \; u =  \begin{bmatrix} \frac{3}{5} \\ \frac{4}{5} \end{bmatrix} $$

 

그래서 두 벡터간의 거리를 구하는 방법은 위의 norm을 구하는 방법을 약간 응용하여, 두 벡터 $u, v$의 차이벡터를 내적하여 norm을 구할 수 있다. 물론 두 벡터의 유클리디안 거리 공식을 통해서도 길이를 알 수 있지만, 여기서는 내적을 통해 거리를 구하는 방법에 대해 조금 더 설명하도록 하겠다. 

두 벡터 $v, u$의 거리는 보다시피 원점에서 시작하지 않는다. 내적을 통해 거리를 구하기 위해서는 벡터가 원점에서 시작해야만 한다. 그래서 두 벡터를 빼면서 차이벡터를 구한다라는 것은 두 벡터 사이의 거리를 원점에서 출발하도록 만든 후, 해당 벡터의 norm을 구한다는 뜻이 된다.

 

다음으로는 두 개의 벡터들 간의 각도를 내적을 통해 구하는 방법에 대해서 알아보겠다. 먼저 식은 다음과 같다.

$$ \mathbb{u}\cdot\mathbb{v} = \|\mathbb{u}\| \|\mathbb{v}\|cos\theta$$

설명하자면,

벡터 $u$와 $v$의 내적값 = 벡터 $u$의 내적값*벡터 $v$의 내적값*$cos\theta$

$cos\theta$ = 벡터 u와 벡터v 의 내적값/벡터 u의 내적값*벡터v의 내적값

이를 통해 우리는 벡터 $u$와 벡터 $v$ 사이의 각도를 알 수 있다. 고등학교 수학을 떠올려 보면, 두 변의 길이를 알고 두 변 사이의 각을 알 때 나머지 한 변의 길이를 알 수 있다는 것과 같다. 

 

Orthogonal이란 수직이라는 뜻이다. Orthogonal Vector란, 두 벡터의 각도가 90도라는 뜻이다. 그리고 두 벡터의 각도가 90도라는 말은, $cos\theta = 0$이라는 말이다. 그래서 만약 두 벡터의 내적 $\mathbb{u} \cdot \mathbb{v} = 0$이고 $\mathbb{u}, \; \mathbb{v}$가 0이 아닐 때, 두 벡터 $\mathbb{u}, \; \mathbb{v}$는 수직이다.

$$if \; cos\theta=0 (= if \; \mathbb{u}, \mathbb{v}\; is\; Orthogonal ), \; \mathbb{u} \cdot \mathbb{v} = \|\mathbb{u}\| \|\mathbb{v}\|cos\theta = 0 $$

그래서 Orthogonal Vectors에 대한 Definition은 $\mathbb{R}^n$ 공간에 존재하는 벡터 $\mathbb{u}$와 $\mathbb{R}^m$ 공간에 존재하는 벡터 $\mathbb{v}$에 대해서 만약 $\mathbb{u} \cdot \mathbb{v}$가 0이라면 $\mathbb{u} \cdot \mathbb{v}$의 각도는 $90^{\circ}$이라는 것을 알 수 있다. 

 

여기까지 기본적인 것들을 알아보았고 다시 Over-Determined System으로 돌아와보자. 위의 식은 Over-Determined가 아니다. 3개의 equation과 3개의 variable이 있고 solution이 존재한다. 

 

이제 equation을 1개 더 늘려 Over-Determined System이 되었다. 

 

4개의 equation을 가진 식에 기존의 solution을 적용해보면, 앞서 3개는 완벽하게 예측하지만 4번째 값은 실제값이 72였던 것에 반해 예측값은 60이었다. 이 경우, Error는 총 12가 된다(-12는 오타)

 

그럼 두 번째로는 아까의 solution이 아닌 임의의값 $x=\begin{bmatrix} -0.12 \\ 16 \\ -9.5 \end{bmatrix}$를 사용해서 예측해보자. 그러면 $\begin{bmatrix} 71.3 \\ 72.2 \\ 79.9 \\ 64.5 \end{bmatrix}$가 나온다. 첫 번째 행으로 예를 들면, 나이가 60살이고 키가 5.5피트이고 흡연을 하는 사람의 기대수명은 71.3이라고 예측했는데 실제로는 66살에 사망했다는 것이다. 그렇다면 얼마나 잘못 예측했느냐(Error)에 대해서는 -5.3만큼 덜 예측했다라는 것을 알 수 있다.

 

그러면 첫 번째 경우와 두 번째 경우에서 어떤 것이 더 좋을까? 어떤 것이 더 좋을지에 대해 가장 간단한 방법은 아래처럼 Error값들에 대해 제곱을 하고 합한 결과에 square root를 취해주는 것이다. 결과는 다음과 같다.

위의 solution이 더 나은 Error를 보이므로 Better solution이라고 할 수 있다. 이러한 방식으로 무수히 많은 solution $x$를 바꿔가며 최소의 Error를 찾고 가장 나은 해로 근사하는 것이 Least Squares의 본질이라고 할 수 있다.

 

그래서 이것을 수학적인 목적함수로 설정한 식이 위와 같다.

- $b$ : 실제 관측된 값

- $A\mathbb{x}$ : 예측값

- $\| \mathbb{b} - A\mathbb{x}\|$ : 예측값에서 실제값을 뺀 값으로 구성된 벡터의 길이

 

그래서 위의 식 

$$\widehat{x} = arg\ \underset{x}{min}\ \| \mathbb{b} - A\mathbb{x}\|$$

이란, $ \| \mathbb{b} - A\mathbb{x}\| $를 최소화($min$)하는 solution $x$를 찾는 과정이며 그 $solution$이 바로 $\widehat{x}$가 되는 것이다.