[선형대수] 4.5.3 Eigenvalue Decomposition vs. Singular Value Decomposition

공부하는 단계에서 정리한 내용입니다.

잘못된 내용이 있다면 말씀해주시면 감사하겠습니다.

https://mml-book.github.io/book/mml-book.pdf

 

4.5.3 Eigenvalue Decomposition vs. Singular Value Decomposition

Eiegendecomposition $A = PDP^{-1}$과 SVD $A = U \Sigma V^{\top}$에 대해서 복습을 해보자.

 

[Existance]

• SVD는 항상 존재한다.

  하지만 eigendecomposition은 정사각행렬에만 적용할 수 있고, $\mathbb R^n$의 eigenvector들의 basis를 찾을 수 있을 때만 존재한다.

 

[Orthogonality]

• Eigendecomposition 행렬 $P$에 있는 벡터들은 항상 orthogonal하지는 않다. 즉, basis가 회전이나 스케일링되지 않는다는 것이다.

  하지만 SVD의 $U$와 $V$에 있는 벡터들은 서로 orthogonal하다. 즉, basis가 회전된다.

 

[3 linear mapping]

• Eigendecomposition과 SVD 모두 3개의 linear mapping으로 이루어져 있다.

  1. 기존 정의역 공간을 새로운 basis로 변경

  2. 새로운 basis에 있는 벡터를 각각 스케일링 & 정의역 $\rightarrow$ 공역 매핑

      (SVD에서는 정의역과 공역이 다른 차원을 가질 수 있지만 eigendecomposition은 같음.)

  3. 공역에서 새로운 basis로 변환

 

[Inverses]

• SVD에서는 행렬 $U$와 $V$가 서로 역행렬 관계가 아니지만, eigendecomposition에서는 $P$와 $P^{-1}$이 역행렬 관계이다.

 

[Diagonal matrix]

• SVD에서는 $\Sigma$가 모두 0보다 크거나 같은 값을 가지지만, eigendecomposition에의 diagonal matrix는 그렇지 않는다.

 

[Matrix projection]

• SVD와 eigendecomposition은 행렬의 projection 성질을 이용해서 계산되고, 서로 관련이 깊다.

  - $A$의 left-singular vector들은 $AA^{\top}$의 eigenvector들이다.

  - $A$의 right-singular vector들은 $A^{\top}A$의 eigenvector 들이다.

  - $A$의 0이 아닌 singular value들은 $AA^{\top}$와 $A^{\top}A$의 0이 아닌 eigenvalue들의 제곱근이다.

 

[Symmetric matrix]

• $A$가 대칭행렬일 때, eigenvalue decomposition과 SVD는 서로 같다.

 

 

 

Ex 4.14 (Finding Structure in Movie Ratings and Consumers)

개인별 추천 영화에 사용되는 SVD에 대해서 알아보자.

사용자 3명(Ali, Beatrix, Chandra)와 영화 4개(Star Wars, Blade Runner, Amelie, Delicatessen)가 있다고 하자.

각각의 평점은 0에서 5 사이이고, 데이터 행렬 $A$는 아래와 같다.

 

그리고 사용자 개인의 영화평점을 각각 $x_{Ali}, x_{Beatrix}, x_{Chandra}$라고 하자.

 

SVD를 통해 사람들이 어떻게 영화에 평점을 주는지, 그리고 특정 그룹의 사람들이 어떤 영화를 좋아하는지 알 수 있다.

데이터 행렬 $A$에 SVD를 적용하기 위해서 아래와 같은 가정을 한다.

  1. 모든 사람들은 같은 linear mapping을 이용해서 영화를 평가한다.

  2. 평점 데이터에는 오류나 노이즈가 없다.

  3. Left-singular vector $u_i$를 전형적인 영화로, right-singular vector $v_i$를 전형적인 관객으로 이해한다.

 

그리고 어떤 사용자의 특정 영화 선호도가 $v_j$의 선형결합으로 표현되고, 영화 자체의 선호도가 $u_i$들의 선형결합으로 표현된다고 가정한다.

따라서 SVD의 정의역에 있는 벡터는 특정 사용자의 취향을 대표(stereotypical viewers)하는 벡터, 공역에 있는 벡터는 영화 자체의 선호도를 대표(stereotypical movies)하는 벡터로 해석할 수 있다.

 

(★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★)

아래와 같이 이해했다.

 

+ 추가 설명)

- $\Sigma$의 행: $U$의 특징(영화의 주요 특징) 들과 연결됨

- $\Sigma$의 열: $V^{\top}$의 특징(사용자의 선호 패턴들)과 연결됨

 

(★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★)

 

후... 쉽지 않았다.

이런 추천시스템 만든 사람은 분명 천재일 것이다.

난 이해도 일케 어려웠는데..

 

 

 

SVD와 관련된 용어와 표기법 정리

SVD와 관련된 용어와 표기법에 대해서 정리할 필요가 있다. 다른 책들에서 다른 용어들이 사용되기도 하기 때문이다.

하지만 다른 용어를 사용한다고 해서 근본적인 수학 원리는 변하지 않는다.

 

• 우리는 SVD를 두 개의 정사각형 행렬 $U, V^{\top}$과 하나의 직사각형 행렬 $\Sigma$로 나타낸다. 이는 Full SVD라고도 불린다.

 

• 어떤 책에는 SVD를 아래와 같이 조금 다르게 정의하기도 한다.

$$A_{m \times n} = U_{m \times n} \Sigma_{n \times n} {V_{n \times n}}^{\top}$$

  이러한 SVD를 reduced SVD 또는 the SVD 라고 부른다.

  형식은 다르지만, SVD의 수학적 구조는 동일하다.

  SVD를 이렇게 쓰면 $\Sigma$가 eigendecomposition에서처럼 diagonal하다는 점에서 좋다. 

 

• Section 4.6에서는 SVD를 활용한 matrix approximation 기술에 대해서 배울 것이다. 이를 truncated SVD라고도 부른다.

 

• Rank가 $r$인 행렬 $A$의 SVD에서 $U$를 $m \times r$ 크기로, $\Sigma$를 $r \times r$ 크기로, 그리고 $V$를 $r \times n$ 크기로 설정하는 경우가 있다.

  $\Sigma$에 nonzero entries만 있는 SVD이다. 즉, $\Sigma$가 eigendecomposition처럼 대각행렬 형태를 띈다.

 

• 행렬 $A$의 SVD가 $m > n$ 일 때만 적용된다? -> NO!

  $m < n$ 일 때는 SVD decomposition의 $\Sigma$ 에서 0열이 행보다 많아져서 $\sigma_{m+1},

\cdots, \sigma_n$ 값이 0이 된다.

 

 

SVD는 curve fitting의 최소제곱 문제에서부터 linear equation의 해를 구하는 데까지 SVD의 중요한 성질들(행렬의 rank와의 관계, low-rank approximation)을 기반 다양한 머신러닝 과제에서 활용된다.

그리고 SVD를 활용하면 numerical rounding error가 줄어든다.

이는 머신러닝을 다양하게 활용할 수 있도록 했다. (e.g. dimensionality reduction, topic modeling)