Determinants and Eigenvectors

Determinants In-depth

Machine learning motivation

• Linear transform의 머신러닝 응용 중 하나인 PCA에 대해 알아보자.

  • 아래는 샌프란시스코의 유명한 한 지역을 여러 지점에서 사진을 찍어 나열한 것이다.
  • 이 지역을 가장 잘 설명하는 사진을 하나 꼽으라고 한다면 아마도 정면을 찍은 사진을 고르게 될 것이다.
    • 즉, 공간을 가장 잘 설명한다고 보는 관점은 2차원 평면으로의 전환이라 하더라도 실제와 가장 유사한 성질을 나타내는 시각을 의미한다.
    • 정보를 최대한 많이 캡쳐할 수 있는 사진을 고를 것이라는 뜻이다.

• 아래의 점들을 가장 잘 설명하는 선을 그어보고, 이를 1차원의 공간으로 선형 변환시켜 보자.

  • 2차원의 공간을 1차원의 공간으로 변형시켜 주는 작업은 해당 공간으로의 투영(projection)으로 그려질 수 있다.

• PCA가 하는 역할은 해당 dataset을 손실하지 않는 중복된 열을 제거하여 차원 축소를 하는 것이다.

  • 아래의 그림은 8차원의 열벡터를 3차원으로 축소시키면서 해당 분포가 span하는 공간은 그대로 유지할 수 있도록 하는 기법을 시각화 한 것이다.

Singularity and rank of linear transformations

• 기존에 보았던 Non-singular matrix의 경우 linear transform 이후의 상황은 아래 그림과 같았다.

  • 이는 basis의 구성은 바뀌었으나 span(확장)하면 전체 공간을 뒤덮을 수 있다는 점에 있어서는 동일하다.

• 만약 아래와 같은 Singular matrix, Redundant한 matrix일 때의 상황은 어떨까?

  • 어떠한 벡터를 곱해주더라도 해당 공간은 하나의 line으로 결정되어, 1차원 공간에서의 표현만 가능하다.

• 만약 0의 값만 갖는 Singular matrix라면?

  • 해당 공간은 (0, 0) 하나만 전체 공간으로 표현되어 있음을 알 수 있다.

• 정리하면, matrix의 Rank가 linear transform될 공간의 span 차원을 설명하는 Dimension을 결정지을 수 있다는 점을 알 수 있다.

Determinant as an area

• Determinant는 선형 변환된 공간 상의 벡터들로 만들 수 있는 area(면적)으로 정의내릴 수 있다.

  • 기존 unit 벡터 (1, 0), (0, 1)으로 만들 수 있는 평행 사변형의 면적이 1이라면, 선형 변환된 벡터가 만드는 공간 상의 면적은 아래와 같이 5로 달라진다.

• 아래와 같은 Singular matrix는 기저 벡터가 하나 존재하므로, 이를 가지고 만들 수 있는 평행 사변형은 무척 얇다.

  • 즉, 면적이 0에 가깝다.

• 0 벡터들로 이루어진 공간 또한 마찬가지다.

• 정리하면, Determinant는 기존 unit 벡터가 linear transform되어 만들어진 기저 벡터들로 이루어진 평행 사변형의 면적이다!

  • Non-singular matrix일 경우 면적이 존재하지만, Singular일 경우 존재하지 않는다는 점도 알아두자.

• 그렇다면 Determinant가 음수 값을 가질 때에는 어떻게 될까?

  • Determinant가 음수면 열벡터의 자리만 바꿈으로써 값을 양수로 아주 쉽게 바꿀 수 있다.

• 기존과 같이 계산했다면 면적이 -5가 되어 말이 되지 않는다.

• 이를 해석하는 일은 기존 벡터와의 clockwise / Counter-clockwise 방향을 보고 결정할 수 있다.

  • 만약 아래와 같이 기존 basis 벡터가 (0, 1), (1, 0) : clock-wise라면, 선형 변환 이후의 변형 벡터는 (3, 1), (1, 2) : Counter-clockwise로 결정된다.
  • 이 방향이 서로 반대된다면 determinant는 -로 결정나며, 큰 의미 없이 그냥 0인지 아닌지에 따라 Non-singular와 Singular 위주로 판명해주도록 하자.

Determinant of a product

• 두 행렬의 determinant 곱은 최종 행렬의 determinant와 같다.

  • 즉, $det(AB) = det(A) det(B)$ 수식이 성립한다.

• 첫 번째 matrix의 선형 변환이 determinant가 5인 넓이를 갖는다고 해보자.

• 두 번째 matrix를 기존 basis 벡터의 선형변환으로 표현하면 determinant가 3인 넓이가 만들어진다.

• 만약, 첫 번째 matrix의 선형 변환 basis 벡터들로 평행 사변형을 표현한다면 determinant가 15인 넓이가 완성된다.

• 다시 말해, 두 번의 선형 변환으로 분해할 수 있는 최종 선형 변환 matrix는 determinant 또한 독립적으로 곱하여 표현할 수 있다.

• Quiz

  • 하나의 Singular matrix와 Non-singular matrix를 곱한 선형 변환 matrix의 determinant가 얼마인지 추론해 보자.

• Solution

  • 해답은 당연하게도 determinant가 0이며, 최종 matrix는 Singular matrix다.

• 하나의 matrix가 0이면 곱해지는 matrix는 당연하게도 무조건 0이다.

• 기하학적으로 표현해 보자.

  • 최종 matrix의 span 공간이 line으로 결정되므로, 이 평행 사변형의 넓이는 0이며 Singular matrix라는 것을 알 수 있다.

Determinants of inverses

• 아래 두 matrix의 determinant를 구해보자.

• 사실 위의 matrix는 앞서 보았던 matrix들의 inverse matrix(역행렬)이었다.

  • 자세히 보면, 기존 matrix의 determinant와 역행렬의 determinant 또한 역수의 관계를 가진다.
  • 즉, $det(A^{-1}) = \displaystyle \frac{1}{det(A)}$의 수식을 만족한다.

• 어떻게 이런 일이 가능할까?

  • 이전의 정의에 의하면 $det(B)$ 자리에 $det(A^{-1})$ 항이 들어서는 것과 같다.

• 또 한가지 흥미로운 점은 $det(I)$가 정의된다는 점이다.

  • 이를 행렬로 표현하면 diagonal한 RREF matrix의 determinant와 같다.

Eigenvalues and Eigenvectors

Bases in Linear Algebra

• Bases는 평행 사변형을 이루는 네 점이 중요한게 아니라 평행 사변형을 이루는 두 벡터가 중요한 개념이다.

  • 아래 두 그림에서 두 번째 그림에 해당하는 벡터쌍이 bases다.

• Bases란 어떠한 점을 해당 벡터들로 움직여 표현할 수 있는 한 쌍의 벡터 모음을 말한다.

  • 아래 그림과 같이 여러 쌍의 bases가 존재할 수 있다.

• 그렇다면 어떤 벡터 쌍이 basis가 아닐까?

  • 아래 벡터 쌍은 하나의 점은 표현할 수 있지만 다른 하나의 점은 어떠한 선형 변환으로도 표현하는 것이 불가능하다.
  • 이러한 쌍이 basis가 아닌 집합에 해당하며 추가로 설명하면 그 공간의 평면 전체를 덮을 수 없다는 것을 의미한다. (현재 2차원)

Span in Linear Algebra

• Span이란 해당 벡터들의 선형 결합으로 표현할 수 있는 전체 집합을 의미한다.

  • 아래와 같이 두 개의 basis들로 이루어진 공간이라면 span의 형태가 2차원 평면이 된다.

• Basis가 아닌 두 벡터의 선형 조합으로는 1차원 직선으로만 전체 집합을 표현할 수 있다.

  • 따라서 basis냐 아니냐에 따라 해당 공간을 표현할 수 있는 공간의 범위(dimension)가 결정된다고 보면 된다.

• 아래의 두 벡터 쌍은 basis가 아니다.

  • 이 벡터들의 선형 조합으로 표현할 수 있는 공간은 오로지 1차원 직선뿐이기 때문이다.

• 아래의 벡터 하나는 어떤가? basis인가?

  • 맞다. 이유는 해당 벡터가 존재하는 공간을 최대로 표현할 수 있는 최소 스패닝 집합이기 때문이다.

• 정리하자면 이렇다.

  • 두 번째 그림의 오른쪽 not a basis가 의미하는 것은 세 벡터 중 하나는 반드시 두 벡터의 선형 조합으로 표현될 수 있기 때문에 최소 스패닝 셋이 되지 않는다는 것을 의미한다.

• 즉, basis의 개수는 해당 공간의 dimension을 의미한다.

Eigenbases

• 아래 그림과 같이 기존에 우리가 했던 방식을 보자.

  • 선형 변환을 하면 basis와 coordinate가 바뀐다.
  • 이는 정사각형이던 면적이 평행 사변형 면적으로 바뀌기도 한다는 것이다.

• 다음과 같이 해당 matrix에 (1. 0)과 (1, 1)을 곱하면 마찬가지로 선형 변환이 일어난다.

  • 선형 변환이 일어난 이후의 basis 벡터들이 이번엔 원래의 basis와 굉장히 유사해보인다.
  • 다시 말해, 원래의 basis를 살짝 stretch 해준 것과 비슷하다.

• 수치를 따져보면 기존 basis 벡터에 가로 방향으로 2만큼, 세로 방향으로 3만큼 곱해서 표현한 벡터로 변환되어 나온다.

  • (1, 0)의 2배 → (2, 0), (1, 1)의 3배 → (3, 3)이 되는 것이다!

• (3, 2)인 점 또한 기존의 basis로 표현하면 왼쪽과 같은 경로로 이어진다.

  • 선형 변환 시킨 이후의 basis들로 해당 좌표를 표현해보면 기존 basis vector (1, 0)의 2배, 기존 basis vector (1, 1)의 3배로 선형 조합됨을 알 수 있다.

Eigenvalues and eigenvectors

• 아래와 같은 두 행렬의 공간을 비교해보자.

  • 똑같은 8개의 점을 3의 값을 곱하여 여러 방향으로 stretch 한다고 할 때, 그려지는 벡터들은 다음과 같다.
  • 그런데 자세히 보니, 특정 어느 방향으로의 벡터가 공통된 벡터 쌍이 되었음을 알 수 있다.

• 이 말은 두 matrix의 공간이 무수히 많은 (x, y)로 이루어진 전체 점들에 대하여 같은 정답을 내포하고 있음을 의미한다.

  • 즉, 두 행렬의 차 matrix를 (x, y) 점에 mapping하면 똑같은 line 공간이 만들어지며, 정답은 (0, 0)의 영벡터를 이룬다.
  • 다시 말해, (x, y)라는 input data의 선형 변환이 해가 무수히 많이 존재함을 의미하며, 이는 Singular matrix로 mapping되었음을 뜻한다.
    • 이에 따라 해당 matrix의 determinant 값 또한 0이다.

• 또 다른 예제를 보자.

  • 아래 두 matrix 또한 특정 basis 후보 벡터 쌍을 2의 값으로 stretch 하였을 때, 일부 벡터의 크기와 방향이 완전히 같음을 알 수 있다.

• 따라서 두 행렬의 차를 선형 변환한 정답은 영벡터를 이룬다.

  • 모든 (x, y)에 대해 무수히 많은 해를 갖는 Singular matrix의 특징을 갖는다고 볼 수 있다.
    • 당연하게도 원점을 항상 지나며 determinant가 0이다.

• Eigenvalue의 계산은 다음과 같이 한다.

  • 고유값을 가진 diagonal matrix를 빼고, 이 행렬의 determinant가 0인 성질을 이용하여 $\lambda$를 찾는다.

• Eigenvector는 eigenvalue를 뺀 행렬에 (x, y)를 mapping하여 적당한 해의 조합을 찾는다.

• Quiz

• Solution

Principal Component Analysis

Calculating Eigenvalues and Eigenvectors

• 아래는 3x3 matix의 eigenvalue가 3개일 때의 예시다.

  • 구해진 eigenvalues로 eigenvectors를 찾는다면 세 개의 벡터가 span하는 공간은 3차원 공간이 될 수 있다.
    • 즉, eigenbasis가 될 수 있다.

• 추가적으로 eigenvalues와 eigenvectors를 구하는 방법은 determenant를 찾는 것으로부터 출발하기 때문에, square matrix가 아닌 상황에서는 계산되지 않는다.

On the Number of Eigenvectors

• 이번에는 3x3 matrix의 eigenvalue 개수가 중복되어 2개일 때의 상황을 보자.

  • $\lambda$가 2일 때를 계산해보니, eigenvectors가 서로 다른 2개의 방향으로 결정되어 3차원 공간을 전부 span할 수 있게 됐다.

• 그러나 위의 첫 번째 열벡터의 마지막 항이 4로만 변경되었을 때의 상황을 보자.

  • 마찬가지로 $\lambda$값이 4일 때는 위에서 찾은 eigenvector와 동일했으나 $\lambda$가 2일 때의 eigenvectors의 상황은 달라졌다.

  • 이번에는 어떠한 값을 찾아도 방향이 모두 동일한 vector만 나올 수 있었고, 그 결과 전체 eigenvectors의 개수는 2개로 한정되었다.

    • 즉, 2개의 벡터들로는 3차원 공간을 전부 span할 수 없다!

• 요약하자먼 이렇다.

  • NxN matrix의 eigenvalue $\lambda$의 개수와 이들이 중복되는지의 여부에 따라 eigenvector의 개수 또한 달라질 수 있다.
  • 최대 N개의 eigenvalues & eigenvectors를 가질 수 있으며 이는 해당 행렬의 성질에 따라 달라질 수 있다.

Dimensionality Reduction and Projection

• Dimensionality Reduction이란, data samples(행)과 features(열)로 이루어진 table의 columns 개수를 줄이는 작업이다.

  • Smaller table은 horizontal한 방향으로 shrink된다.

• 이러한 작업을 하는 이유는 크게 두 가지다.

  1. datasets의 size를 작게 만들기 위해서
  2. visualize하기 쉽기 때문에

• 몇몇 values가 사라짐으로써 정보가 줄어든다는 이면은 존재한다.

• 아래와 같은 점들을 2차원 좌표 평면에 나타내보자.

  • 만약, $y=x$ 1차원 그래프에 수직으로 투영(projection)시킨다고 하면 다음과 같이 점의 위치가 달라진다.

• 1차원 직선으로의 투영 이후 (1, 1)의 위치는 바뀌지 않았다.

  • 그러나 (1, 1)의 좌표는 현재 2차원 공간에서의 점 표현이므로 원점으로부터의 거리(segment)가 얼마인지를 계산해보면 $\sqrt{2}$다.

  • 이를 계산하는 방법은 $\displaystyle \frac{1+1}{\sqrt{2}}$를 계산하는 것과 같다.

    • 왜 이렇게 계산하는지에 대해서는 의문을 가질 수 있다.

• 계산 과정을 살펴보자.

  • 먼저, data인 (1, 1) 벡터와 $y=x$ 위의 점 (1, 1) 벡터를 dot product하면 $2$가 나온다.

  • 이를 더해서 좌표에 표현하면 길이가 $2$인 하나의 선분이 그려진다.

    • 다시 원래의 projection 점으로 보내기 위해 scale 조정해주는 작업이 필요한데, 이 과정이 $\displaystyle \frac{1}{\sqrt{2}}$를 곱해주는 과정이다.

  • 그리고 $\sqrt{2}$는 다름 아닌 곱해지는 벡터의 2-Norm 값과 같다.

    • 해당 eigenvector의 단위 벡터로 차원 축소 이후의 점의 scale과 좌표, 다시 말해 바뀐 계에서의 segment를 결정해주는 것이라고 볼 수 있다.

• 같은 방법으로 모든 점을 투영하면 아래와 같은 파란색 점들이 $y=x$ 직선에 그려진다.

  • 각각의 값을 계산해보면, 각 점들이 1차원 점 하나씩으로만 표현된다.

  • $y=x$ 직선을 눕혀 수직선으로 각 점을 표현하면, 원점으로부터 얼마나 떨어졌는지에 대한 값이 1차원 점 하나로만 표현이 가능해짐을 의미한다.

• Projection 로직은 다음과 같다.

  1. 해당 공간을 span할 수 있는 vector와의 dot product
  2. scale 조정을 위한 2-norm으로 dividing

• 맞춰주고 싶은 차원에 따라 행렬 $V$의 column 차원이 결정된다.

  • 결론적으로 data point가 담겨있는 행렬 $A$를 $V$ 공간으로 mapping하는 것이다.

  • $V$ 공간의 차원이 원래의 차원보다 작다면 차원 축소, 크다면 차원 확장 개념이 될 수도 있다.

Motivating PCA

• 아래와 같은 $x$, $y$ features로 이루어진 공간에 data points가 기록되어 있다.

• 위 data point들을 원점으로 이동시킨 형태는 다음과 같다.

  • 이러한 과정으로부터 PCA를 설명할 수 있다.

• $x$축과 $y$축으로 data point들을 각각 projection 내려보자.

  • 아래와 같은 수직선으로의 점의 분포가 기록되었다.
    • (1, 0), (0, 1)로 각각 투영내린 결과물이다.

• 이번에는 $x=-y$ 직선에 projection 내려 보자.

  • 벡터로 표현하면 (1, -1) 벡터로의 투영이다.

• 이번에는 $2x=y$ 직선에 projection 내려 보자.

  • 벡터로 표현하면 (1, 2) 벡터로의 투영이다.

• 여러가지 방법으로 projection 내리는 것이 가능하지만, 기존 데이터 분포 양상을 가장 잘 보존하는 직선은 아래와 같은 빨간색 직선이다.

  • 기존 데이터 분포 양상은 다시 말해 원점(기준점)으로부터의 spread 정도다.

"Preserving more spread, preserving more information"

• 위와 같은 의미로 데이터 spread 정도를 가장 잘 보존한 수직선 순위를 나열해 보면 아래와 같다.

• 차원 축소를 하면 dataset을 쉽게 관리할 수 있고 시각화하기 편하다.

  • PCA는 차원 축소를 하는 하나의 방법론으로써, 기존 데이터의 정보 손실을 최소화하기 위한 목적을 가진 방법론이라고 볼 수 있다.

Variance and Covariance

• Statistics에서 다루는 Mean(평균)과 Variance(분산)에 대해 알아보자.

  • 평균은 data의 중심점이며 수식으로 표현하면 $\displaystyle \frac{1}{n} \sum_{i=1}^{n} x_i$으로 표현할 수 있다.
    • 좌표가 2개 이상이라면 각각의 중심점 좌표가 평균 지점이다.

• Variance는 data의 spread 정도다.

  • x축과 y축을 기준 선으로 두면 x-variance가 y-variance보다 크다고 말할 수 있다.

• 수식으로는 $Variance(x) = \displaystyle \frac{1}{n-1} \sum_{i=1}^{n} (x_i - Mean(x))^2$로 표현한다.

  • 아래와 같은 table이 있다고 하면 $(x_i - Mean(x))^2$의 합을 (전체 데이터 개수 - 1)로 나누었다고 생각하면 된다.

  • $n$이 아닌 $n-1$로 나눠주는 이유는 불편추정량을 고려한 estimation이라고 생각하면 된다.

    • cf. 참고 블로그

• Variance의 정의는 "(평균으로부터 떨어진 거리)의 제곱의 평균"이라 할 수 있다.

  • 간편하게 $Var(x)$로 표현하며, $\displaystyle \sum_{i=1}^{n} (x_i - \mu_{i})^2$로 다시 쓸 수 있다.

• 마찬가지로, 2 이상의 좌표계라면 독립적으로 계산하여 표현한다.

Covariance Matrix

• 아래 두 데이터 분포를 다르게 설명할 수 있는 방법은 Covariance에 있다.

  • x축 변화량과 y축 변화량이 모두 +라면 positive covariance, x축 변화량은 + & y축 변화량은 -라면 negative covariance를 갖는다고 말한다.

• 기존 $Var(x)$의 정의에서 변수를 $x$, $y$ 두 개로 나누어 정의한 것이라고 봐도 무방하다.

• 아래와 같은 세 가지 분포에 대하여 covariance를 정의하면 다음과 같다.

  • 그리고 + zone과 - zone을 구분지어, data point가 어디에 주로 몰려있는지에 따라 결정된다고 봐도 된다.
    • Average를 취하는 것이다.

• 따라서 Covariance란, 두 변수간 관계의 방향을 +/-로 방향성을 정의내릴 수 있는 관계 함수다.

PCA - Overview

• 이제 PCA의 전체적인 과정에 대해 알아보자.

  • PCA는 아래의 모든 개념을 combine한다.

    1. Projections
    2. Covariance Matrix
    3. Eigenvalues / Eigenvectors

• x축, y축, xy축(?)의 Variance를 계산하여 Matrix 원소 자리에 집어 넣었다.

  • 이러한 행렬을 Covariance Matrix라 한다.

• Covariance는 x와 y에 대한 차이의 곱이 항상 같기 때문에 Symmetric Matrix를 구성한다.

  • 이는 Eigenvectors가 서로 orthogonal하다는 성질을 자연스럽게 가지며, 서로 수직 관계에 있음을 의미한다.

• 두 번째 eigenvalue는 첫 번째 eigenvalue보다 작아서 영향력이 작다.

  • 따라서 첫 번째 eigenvalue를 연장한 직선을 best line으로 선정하여, projection 내린 결과는 아래 두 번째 그림과 같다.

• 2차원 평면의 data points를 1차원 수직선에 projection한다는 것은 어떤 의미일까?

  • 2개의 features로 이루어진 dataset을 아우르는 하나의 feature map으로 매핑시키는 것이다.

• 9차원의 features를 갖는 n개의 관측된 dataset이 있다면, 상위 2개의 eigenvalues를 찾아 2차원 feature map으로 매핑시킬 수 있다.

• 각 eigenvector의 2-norm으로 나눈 정규화 벡터를 dot product 하는 것이다.

PCA - Why It Works

• 어떻게 eigenvalues와 eignevectors가 의미를 갖는 것일까?

  • 앞서 보았던 Covariance Matrix의 선형 변환을 basis : {(1, 0) (0, 1)}로 mapping 시켜보자.

• 두 점 뿐만 아니라 원을 구성하는 단위 벡터들로 선형 변환 이후의 점들을 표현해보자.

  • 아래 그림과 같이 타원형의 점들로 mapping되었다.

• 단위 벡터가 아니라 stretch한 벡터들로 확장해 보아도 같은 direction을 가리킨다.

• Covariance 행렬의 가장 큰 eigenvector와 이 벡터의 수직한 두 번째 eigenvector를 찾아보자.

  • 11 scale의 (2, 1), 1 scale의 (-1, 2) 벡터가 나왔다.

  • "Everythin is just stretches"

    • 선형 변환 이후의 공간을 표현하는 벡터들은 just 기존 벡터를 stretch하여 나타낸 것과 같다는 의미로 해석할 수 있다.

• 각 벡터의 scale은 벡터의 2-Norm 값과 동일하다.

  • 아래 그림에서는 stretch가 5인 벡터와 stretch가 9.85인 벡터의 예시를 추가적으로 나타내었다.

    • (0, 1)의 선형 변환 (4, 3)의 2-Norm : 5
    • (1, 0)의 선형 변환 (9, 4)의 2-Norm : 9.85

PCA - Mathematical formulation

• PCA의 전체적인 과정에 대해 정리해보자.

  1. 5개의 features를 갖는 n개의 관측된 dataset을 matrix로 표현한다.
  2. 평균값에 대한 영점 조절을 위해 각 $x_i$에 대하여 $\mu_i$를 뺀다.
  3. Covariance Matrix를 계산한다.
  4. Eigenvalues와 Eigenvectors를 찾아 eigenvalue의 크기가 큰 순부터 나열한다.
  5. 각 eigenvector에 2-norm 정규화를 진행하고, 열벡터로 concat한다.
  6. 기존 $(x_i - \mu_i)$ matrix에 eigenvectors V를 dot product하여 projection(사영) 내린다.

---

• 출처 : [Coursera] Mathmatics for Machine Learning and Data Science