Least Squares Problem & Orthogonal Projection

Least Squares Problem

• 앞서 말했던 것과 같이 크기가 $ m \times n $ 행렬에 대해 $ Ax=b $를 푼다면, 풀려는 방정식의 개수가 미지수의 개수보다 많기 때문에 해가 존재하지 않게 된다. 우리가 분석하려는 데이터들은 대체로 이런 Over-determined된 형태일 것이다.

• 위의 Over-determined 형태의 feature matrix를 column vector들의 linear combination으로 나타내 주면, 다음과 같이 표현할 수 있을 것이다. Vector 각각의 column vector의 차원이 n차원일 때 column space가 Span하는 공간내에 상수 벡터 b가 포함되어 있을 확률은 매우 적다. 왜냐하면 m이 무한하게 늘어난다고 가정한다면 무한한 차원에서 3개의 column vector들의 linear combination으로 얻어지는 column space도 매우 얇은 초평면(hyperplane)이 될 것이기 때문이다. 이러한 매우 얇은 초평면에 상수 벡터 $ b $가 포함되어있을 확률은 크지 않다. 그러므로 해는 존재하지 않는다.

• 해당 Over-determined 행렬에 대해 해를 찾을 수 없다면, 대부분의 경우 이런 분석 데이터 행렬인데 포기해야만 하는 것일까? 아니다!!! 최대한 근사적인 해를 찾는 것이 가장 최적의 해일 것이다.

• Over-determined system에 대한 solution을 찾기 위해선 먼저, 벡터의 내적개념을 알고있어야 한다. 벡터의 내적은 말 그대로 두 벡터의 곱을 의미한다.

• 벡터의 Norm이란 쉽게 말해 벡터의 길이를 의미한다. 해당 벡터 자기자신을 내적한 뒤 제곱근을 취해주면 해당 벡터의 길이인 Norm을 구할 수 있다.

• 벡터의 길이를 의미하는 Norm은 아래와 같이 피타고라스 정리에 의해서도 확인할 수 있다. 맨 아래 식에 스칼라에 절대값이 붙는 이유는 해당 스칼라가 음수인 경우 길이는 음수 양수의 개념이 아닌 크기의 개념이기 때문이다.

• Unit Vector라는 것은 해당 벡터의 길이로 전체 벡터의 원소들을 나누어주어 길이가 1인 벡터를 의미한다.

• 두 벡터의 거리는 어떻게 구할 것인가? 해당 벡터들 간의 차에 대한 norm을 구하면 된다.

• 벡터간의 거리인 벡터 $ u $ 로부터 벡터 $ v $ 까지의 거리는 결국 편행사변형법으로 만들어진 $ u-v $ 벡터와 원점 사이의 거리 즉, $ u-v $ 벡터의 길이와 동일하다.

• 제 2코사인 법칙으로 부터 $ a^{T}b = |a||b| cos \theta $ 가 되는 것을 알고 있을 것이다. 만일 우리가 두 벡터를 알고있다면, 길이를 구해 해당 벡터사이의 사이각을 구할 수 있을 것이다. 또한 내적의 또 다른 의미는 만일 아래 그림에서 벡터 b가 unit vector인 경우 projection된 성분을 의미하기도 한다. 즉, 벡터 b의 성분을 벡터 a가 얼만큼 가지고 있느냐는 의미이다.

• If non-zero vectors, $ v_{1}, v_{2}, \ldots, v_{n} $ are orthogonal, $ v_{i}^{T} v_{j} = 0, ||v_{i}|| \neq 0 $ then the vectors are linearly independent!

• 위에서 linearly independent가 되는 이유는 vector들을 가지고 linear combination을 하여 0 벡터를 만들 수 있는 경우가 모든 계수가 0일 때만 가능하기 때문이다.

$$C_{1} v_{1} + C_{2} v_{2} + \cdots + C_{n} v_{n} = 0$$ $$\rightarrow v_{i}^{T} ( C_{1} v_{1} + C_{2} v_{2} + \cdots + C_{n} v_{n} ) = 0$$ $$\rightarrow C_{i} || V_{i} ||^{2} = 0 for \forall i$$ $$C_{i} = 0$$

• 두 벡터의 내적이 0을 갖는다면 두 벡터는 서로 직교한다는 의미이다. 왜냐하면 위의 식에서 $ cos 90 = 0$ 이기 때문이다. 참고로 두 벡터가 직교하며, 각각 Unit vector인 경우 Orthonormal하다고 한다.

  • Orthogonal한 경우 linearly independent한 벡터들이지만 linearly independent하다고 해서 Orthogonal 하진 않는다.
  • $ x^{T} y = 0 \rightarrow \text{angle} = 90^{\circ}$
  • $ x^{T} y > 0 \rightarrow \text{angle} < 90^{\circ}$
  • $ x^{T} y < 0 \rightarrow \text{angle} > 90^{\circ}$

• 이제 다시, Over-determined System으로 돌아가보면 아래 예시 처럼 정방행렬인 경우는 역행렬이 존재한다면 Unique한 solution을 찾을 수 있을 것이다.

• 허나, 아래 그림처럼 Over-determined System인 경우 위의 solution을 대입해 계산해보면 아래와 같은 error(또는 Residual) 값을 갖는다.

• 임의의 solution을 만들어 다시 계산해 error를 구해보면 다음과 같다.

• 위의 두 가지 경우를 비교하여, 어떤 것이 더 좋은 방법일지 확인해보자. 더 작은 error값을 갖는 2번째 방법이 더 좋은 방법이라고 할 수 있을 것이다. 여기에서 error는 결국 $ || b-Ax || $ 를 의미하는 것을 확인 할 수 있다.

• 이러한 error를 가장 작게 해주는 solution $ x $ 를 찾는 것이 우리의 objective function(cost function)이 될 것이다.

Least Squares Problem의 기하학적 측면

• 근사시킨 해 $ \hat{x} $ 는 기존의 $ Ax $ 즉, A의 column vector들의 linear combination인 column space에 모든 포인트 중에 가장 가까운 점을 의미한다. 가장 가까운 점을 찾는 것은 $ || b-Ax || \bot column space of A $ 이 성립된다.

• 아래와 같이 행렬 A와도 직교하는 것을 확인할 수 있다.

• $ Ax \simeq b $ 를 푸는 문제는 결국 $ A^{T} A \hat{x} = A^{T} b $ 를 푸는 것과 동일해 진다. 새로운 linear system을 푸는 문제가 되며, 우리는 이 식을 normal equation 이라고 부른다. $ A^{T} A $ 가 역행렬이 존재한다면, 맨 마지막 식과 동일하게 solution을 찾을 수 있다.

• 위에서 언급했던 것 처럼 우리가 목표로 삼았던 objective function은 $ \underset{ x }{ \arg \min } || b - Ax|| $ 에 대해서 찾게 되면 아래 그림에서와 같이 계산할 수 있다.

• 벡터의 미분이 잘 이해가 가지 않는다면 아래수식을 살펴보자. 먼저 아래 수식에서 x_{i} 에 대해 미분한다면 각각 3과 2를 갖는 열 벡터로 계산되어질 것이다.

$$\begin{align} a^{T} x \begin{bmatrix} 3 & 2 \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} = 3 x_{1} + 2 x_{2} \end{align}$$

• 아래에서와 같이 두 벡터의 내적은 스칼라이기 때문에 순서를 바꾸어도 상관이 없다. 이런 성질을 이용하여 미분을 풀어주면 된다.

$$a^{T} x = x^{T} a \Rightarrow \frac{d}{dx} (a^{T} x) = a$$

• $ x^{T} A^{T} A x $ 같은 경우에는 $ f(x)g(x) = f(x)^{‘} g(x) + f(x) g(x)^{‘} $ 로 생각하여 풀면 된다.

$$\frac{d}{dx} x^{T} A^{T} A x = \frac{d}{dx} x^{T} (A^{T} A x) + \frac{d}{dx} (x^{T} A^{T} A) x = A^{T} A x + A^{T} A x$$

• $ A^{T}A $ 의 역행렬이 존재하지 않는다면 우선 2가지 경우 중에 하나가 될 것이다. 1)해가 존재하지 않는다. 2) 무수히 많은 해를 가진다. 일반적으로 Normal equation의 경우에는 특수한 성질로 인해 해가 없는 경우는 없다. 직관적으로 설명해보자면, 해가 하나이상있는 이유는 무엇인지 생각해보면, 수선의 발인 $ \hat{x} $ 가 존재하지 않는 경우여야만 해가 존재하지 않을 텐데 공간 상 어느 지점에서도 수선의 발을 내려 columns space와의 접점이 생기지 않을 순 없다.

• 그렇다면 $ A^{T}A $ 가 어떤 경우에 역행렬이 존재하지 않는가에 대해 생각해보자. A의 행렬이 linearly independent한 column 벡터들로 이루어져 있다면 역행렬이 존재하고, 그렇지 않다면 역행렬이 존재하지 않을 것이다. 즉, 역행렬이 존재한다는 이야기는 결국 A의 행렬이 linearly independent한 column 벡터들로 이루어져 $ \hat{b} $ 를 만드는 linear combination이 unique해야만 하기 때문이다. 반대로, 역행렬이 존재하지 않은 경우 해는 무수히 많을 것이고 A 행렬의 column 벡터들이 linearly dependent하여 $ \hat{b} $ 를 만드는 linear combination이 여러가지 있다는 이야기가 되기 때문이다.

• 또한, 실제로 $ A^{T}A $ 의 역행렬이 존재하지 않는 경우는 거의 없다. 왜냐하면 column 별로 정확하게 비율이 맞추어지는 경우는 어렵기 때문이다.

Orthogonal Projection

• 이전에 구했던 $ \hat{x} = ( A^{T} A )^{-1} A^{T} b $ 를 대입하여 $ \hat{b} $ 를 살펴보면 아래와 같이 linear transformation을 이루는 것을 확인 할 수 있다. 아래의 밑줄친 행렬을 Projection matrix라고도 한다.

• If non-zero vectors, $ v_{1}, v_{2}, \ldots, v_{n} $ are orthogonal, $ v_{i}^{T} v_{j} = 0, ||v_{i}|| \neq 0 $ then the vectors are linearly independent!

• 두 벡터의 내적이 0을 갖는다면 두 벡터는 서로 직교한다는 의미이다. 왜냐하면 위의 식에서 $ cos 90 = 0$ 이기 때문이다. 참고로 두 벡터가 직교하며, 각각 Unit vector인 경우 Orthonormal하다고 한다.

  • Orthogonal한 경우 linearly independent한 벡터들이지만 linearly independent하다고 해서 Orthogonal 하진 않는다.
    • $ x^{T} y = 0 \rightarrow \text{angle} = 90^{\circ}$
    • $ x^{T} y > 0 \rightarrow \text{angle} < 90^{\circ}$
    • $ x^{T} y < 0 \rightarrow \text{angle} > 90^{\circ}$

• 첫번째 문장에서 처럼 p개의 column벡터를 갖는 행렬의 subspace W의 차원수가 p라는 의미는 행렬을 이루고 있는 모든 column 벡터가 linearly independent하다는 의미이다. 이러한 linearly independent한 벡터들을 orthogonal하게 만드는 것은 Gram-Schmidt process를 통해 가능하다.

Cosines and Projection onto line

• 아래 그림과 같이 projection한 지점으로 이동시켜주는 matrix를 우리는 Projection matrix라고 한다.

$$\begin{eqnarray} P = \hat{x} a = \frac{a^{T}b}{a^{T}a} a \\ &=& \frac{a a^{T}}{a^{T}a} b \text{vector의 내적은 순서를 바꾸어도 어차피 scalar값이므로 문제없음.} \\ &=& P b \end{eqnarray}$$ $$Projection matrix P = frac{a a^{T}}{a^{T} a}$$

• projection matrix의 성질

$$P^{T} = \{ frac{a a^{T}}{a^{T} a} \}^{T} = frac{a a^{T}}{a^{T} a} = P$$ $$P^{2} = frac{a a^{T}}{a^{T} a} frac{a a^{T}}{a^{T} a} = frac{ a (a^{T} a ) a^{T} }{ ( a^{T} a ) a^{T} a} = P$$ $$Projection matrix P = frac{a a^{T}}{a^{T} a}$$

• 위에서 했던 방법과 동일하게 아래 그림에서도 동일하게 Projection matrix를 구할 수 있으며, projection된 좌표의 벡터를 계산할 수 있다.

• 2-Dimensional subspace $ W $ 에 orthogonal projection한 $ \hat{y} $ 를 구하는 것은 두 orthogonal Basis vector들에 대해 projection하여 계산된 성분의 합으로 구할 수 있다. 각 orthogonal한 Basis vector에 대해 projection을 해도 직교되는 지는 삼수선의 정리에의해 보장되므로 걱정하지 않아도 된다.

• 위에서와 다르게 $ y $ 가 이미 subspace $ W $ 에 포함되어있다면, prjection을 해도 동일하게 y이기 때문에 아래와 같이 동일한 식을 풀어도 y값이 그대로 계산된다.

• 여기서 $ \hat{b} $을 orthonormal한 Basis vector들인 $ u_{1}, u_{2} $ 에 projection시킨다면 아래와 같이 각각의 projection 성분들의 합을 하나의 Projection matrix를 통한 선형변환적 측면으로 바라볼 수 있게 된다.

• 만약 행렬 A가 Orthogonal한 벡터들로 이루어져있다면, 아래와 같이 계산할 수 있다. 결국 우리가 찾는 solution은 기존의 column space에 포함되지 않았던 상수벡터 $ b $를 linear transformation하여 projection한 벡터에 관해 계산하는 것이라는 사실을 다시한번 확인할 수 있다.

• 예를 들어, 행렬 $A$가 orthonormal한 벡터들로 이루어져 있고, 행렬 $ B $ 는 orthonormal하지 않은 벡터들로 이루어져 있다고 가정해 보자. 아래와 같이 기하학적으로 살펴볼 수 있으며, 결국 행렬 B의 경우 행렬을 이루는 다른 벡터에 대해 projection 방향이 영향을 받기 때문에 영향을 주는 벡터가 가중치 또는 계수 x 값을 결정하게 된다. 그러나 Orthonormal한 경우 다른 벡터(feature)에 관계없이 독립적으로 Orthogonal Projection을 통해 계수를 계산할 수 있다.

• 또한, orthogonal하지 않는 column 벡터들이 유사한 형태로 이루어져 있다면, projection 성분들을 구할 때 다른 벡터와 평행한 방향으로 projection해야 하므로 아래와 같은 그림으로 projection 되어 질 것이다. 만약 벡터 $ b_{1} $ 이 약간 틀어지게 된다면, 그때의 projection된 성분 값은 더 멀어지거나 가까워질 것이다. 즉, orthogonal 하지 않는 유사한 벡터들의 projection은 다른 벡터에 영향을 많이 받게 되어 조금의 변동으로도 계수에 대한 큰 오차가 발생된다. 그러므로 이런 경우 적합된 회귀 모델에 입력이 조금 바뀐다면 계수 벡터가 굉장히 sensitive하게 바뀔 것이다. 이는 test 데이터에 대한 성능이 안좋아지게 되는 결과를 초래 할 수도 있다. 이러한 이유로 regularization term을 포함한 회귀계수를 축소한 모형들을 사용하는 것이다.

• 한가지 예로 Ridge regression은 아래와 같은 objective function을 갖는데 이는 아래 그림과 같이 벡터들을 수직하게 만들어 주는 의미를 갖는다. 회귀에서와 마찬가지로 선형 분류나 NN에서의 가중치 벡터도 동일하게 생각해보면 가중치 벡터들이 서로 Orthogonal하지 않게 되면 feature들의 의미를 중복해가지고 있는 feature들을 구성하게 될 것이다.

$$( A^{T} A + \lambda I ) x = A^{T} b$$