[CS246] Dimensionality Reduction (3) - SVD

 

Singular Value Decomposition (SVD)

특이값분해(SVD)와 관련 용어를 잠시 복습하고 가자.

행렬 $M$을 SVD 분해하면 아래와 같이 3개의 행렬을 얻게 된다. 

The form of SVD (MMDS textbook)

$M_{m \times n}$: input data matrix

$U_{m \times r}$: left singular vector

$\Sigma_{r \times r}$: singular values. 대각행렬이고 각 성분($\sigma_i$)은 'concept'의 강도(strength)를 나타낸다. 

$V_{n \times r}$: right singular vector

$r$은 $r=\text{rank}(M)$ 이고, $U$와 $V$는 column-orthonormal이다.

\[ M \approx U \Sigma V^\top = \sum_{i=1}^{r} \sigma_i \mathbf{u}_i \mathbf{v}^\top_i \]

Vizualizing SVD (Stanford CS246)

SVD: Properties

실수를 원소로 갖는 임의의 행렬 $A$에 대하여 항상 SVD분해($A=U \Sigma V^\top$)가 가능하다.

• $U,\ \Sigma,\ V$는 유일하다. (증명 생략)
• $U$와 $V$는 column-orthonormal 이다. 즉 $U^\top U = I,\ V^\top V = I$ 이다.
  • $U$의 $i$번째 컬럼벡터를 $\mathbf{u}_i$라 하자. $\| \mathbf{u}_i \|=1$
  • $i = j$에 대하여 $\mathbf{u}_i^\top \mathbf{u}_j=1$이고 $i \neq j$ 에 대하여 $\mathbf{u}_i^\top \mathbf{u}_j=0$임을 이용하면 쉽게 이해 가능하다.
• $\Sigma$는 대각행렬이고, 각 원소는 음이아닌 실수이며 non-decreasing order이다.
  • $\sigma_1 \ge \sigma_2 \ge \dots \ge 0$

 

반응형

Example of SVD: Users-to-Movies

Ratings of movies by users (MMDS textbook)

위와 같이 7명의 user가 5개의 movie에 각자 별점을 매긴 데이터를 SVD분해한 것이다.

대체적으로 처음 4명(남자이름?)은 SF장르에, 나머지 3명(여자이름?)은 로맨스 장르에만 별점을 주는 경향이 있는데 Alien의 경우 약간의 noise(?)가 있다.

참고로 Matrix, Starwars가 독립이 아니고, Casablanca, Titanic이 선형독립이 아니기 때문에 $M$의 컬럼이 5개여도 rank는 3이다. 그래서 singular value는 3개뿐이다. (row관점으로는 Joe-Jim-John-Jack가 선형독립이 아니고, Jill-Jane이 선형독립이 아니다.)

SVD as a dimension reduction (Stanford CS246)

$U$ is User-to-concept Factor Matrix

$U$의 첫번째 컬럼 $\mathbf{u}_1 = [0.13, 0.41, 0.55, 0.68, 0.15, 0.07, 0.07]^\top$ 이다.

4개의 원소는 숫자가 크고, 나머지 뒤 3개 원소는 (절댓값) 크기가 거의 $0$이기 때문에(column-orthonormal) $\mathbf{u}_1$는 SF-concept로 해석할 수 있다. ($0.13$은 크기가 작은 이유가 첫번째 사람의 별점이 $1$로 작기 때문이다.)

 

$\mathbf{u}_2 = [0.02, 0.07, 0.09, 0.11, -0.59, -0.73, -0.29]^\top$는 앞 4개 원소는 거의 $0$이지만 뒤 3개의 원소는 (절댓값) 크기가 큰 것으로 보아 Romance-concept 이다.

 

$\mathbf{u}_3$도 Romance와 유사한 concept로 해석할 수 있지만 중요하지 않다(바로 아래 strength 관점에서 다시 설명)

 

※ (+), (-) 부호는 중요하지 않다. 단순히 벡터의 방향이 반대일 뿐이다. 그래서 부호(sign)는 해석하지 않는다.

User-to-concept factor matrix (Stanford CS246)

$\Sigma$ is a strength

singular values are strengths (Stanford CS246)

singular value는 해당 latent concept가 얼마나 중요한지(얼마나 강한지) 나타낸다.

$\sigma_1=12.4$와 $\sigma_2=9.5$는 상당히 큰 값을 갖지만, $\sigma_3=1.3$은 그렇지 못하다. 따라서 3번째 concept는 중요하지 않다고 해석할 수 있다.

이렇게 된 이유는 원래 데이터 $M$에 SF와 Romance 이렇게 2개의 타입이 매우 강하게 있는 것에 비해 Alien이 명확히 rating이 구분되지 않기 때문이다.

 

$V$ is Movie-concept Factor Matrix

Movie-to-concept factor matrix (Stanford CS246)

$\mathbf{v}^\top_i$는 $\mathbf{u}_i$ 와 $\sigma_i$와 곱해진다고 위 SVD 공식에서 확인했다.

 

$\mathbf{v}^\top_1=[0.56, 0.59, 0.56, 0.09, 0.09]$를 살펴보자. 이 벡터는 $\mathbf{u}_1$ 과 $\sigma_1$과 함께 곱해진다. 즉 SF-concept와 곱해지는 벡터다. 처음 3개 벡터의 값이 크고 나머지 2개의 값이 $0$이므로 앞의 3개 영화(Matrix, Alien, Serendipity)는 SF로 해석할 수 있다.

 

$\mathbf{v}^\top_2=[0.12, -0.02, 0.12, -0.69, -0.69]$를 살펴보면 뒤 2개 영화(Casablanca, Amelie)가 Romance임을 나타낸다.

 

$\mathbf{v}^\top_3=[0.40, -0.80, 0.40, 0.09, 0.09]$는 2번째 영화 Alien과 concept 간의 정보만 남아있다. 매우 weired concept이다. (그도 그럴 것이 로맨스 영화보는 사람 중 2명은 SF중에서 Alien만 rating 했기 때문이다.) 

 

※ SVD를 해석하는 방법은 정해져 있지 않다. 프로그래머가 직접 살펴보고 latent concept를 찾아야 한다.

 

Dimensionality Reduction with SVD

지금까지 SVD와 SVD 분해로 얻은 행렬 $U, \ \Sigma, \ V^\top$을 해석하는 방법을 설명했다.

그러나 세 행렬 여전히 크기가 크기 때문에 SVD 자체로는 차원축소가 아니다. 

이제 SVD를 이용한 차원 축소에 대해 설명할 것이다.

Idea of Dimensionality Reduction

Example of 2D data (Stanford CS246)

위 그림과 같이 2차원 데이터를 1차원으로 축소시킨다고 하자. (위의 User-Movie ratings와 다르다)

PCA와 같이, 분산이 가장 큰 방향을 axis로 삼고, 기존 데이터(검은색 점)를 그 위에 project할 것(초록색 점)이다. 물론 약간의 recontruction error가 존재한다.

 

Example: Users-to-Movies

$V$ become new axis (Stanford CS246)

$M = U \Sigma V^\top$ 에서, $V$의 각 컬럼($V^\top$의 row)이 새로운 차원의 축이 된다.

Singular values as variance (Stanford CS246)

그리고 $\Sigma$의 $\sigma_i$는 분산을 나타낸다.

$U \Sigma$ as a new projection (Stanford CS246)

$U$와 $\Sigma$를 곱하여 얻은 각 컬럼벡터는 $\mathbf{v}_i$에 project된 새로운 좌표(point)로 해석할 수 있다.

$U \Sigma$의 첫번째 컬럼은 SF-axis, 두번째 컬럼은 Romance-axis 등으로 말이다.

How exactly is dimension reduction done?

sigular value가 작은 값들을 $0$으로 한다.

여기서 원래 행렬의 rank는 3이었는데, 특이값 1개를 없애면 rank 2로 근사할 수 있다.

특이값을 2개 없애면 rank 1으로 근사할 수 있다. 

일반적으로 rank가 클 수록 원래 행렬의 값에 더 가까이 근사될 것이다.

Rank 2 Approximation (Stanford CS246)

Rank 2 Approximation (Stanford CS246)

$sigma_3$를 없애고 reconstructed matrix를 얻으면 다음과 같다.

Reconstructed Matrix (Stanford CS246)

Reconstruction Error: Frobenius norm

이렇게 재구성된 행렬이 얼마나 원래 행렬과 차이나는지를 평가하는 방법은 Frobenius norm을 이용하는 것이다.

regression error에서 RMSE와 거의 같은 컨셉으로 보면 된다.

\[ \| M \|_F = \sqrt{\sum_{ij} M_{ij}^2} \]

 

원래 행렬과 reconstructed 행렬을 각각 $A$, $B$라 하면 $ \| A - B \|_F = \sqrt{\sum_{ij} (A_{ij} - B_{ij})^2}$ 가 작도록 하면 된다. 

What is a good value for $r$ (# of latent factors) ?

그렇다면 어떤 $r$ 값이 적절한 rank의 개수일까?

특이값의 제곱의 합($\sum_i \sigma_i^2$)을 energy라 하면, energy의 90% 이상이 되도록 $r$을 선택한다.

 

위의 Users-to-Movies 예시에서 energy는 $245.7 = 12.4^2 + 9.5^2 + 1.3^2$이고, 특이값 한개를 삭제하여 얻은 새로운 행렬의 energy는 $244=12.4^2 + 9.5^2$이다. $244/245.7 \approx 0.99$ 이므로 99%의 energy를 보존한다고 할 수 있다.

 

Querying using Concepts

새로운 데이터가 주어졌을 때, 어떻게 차원축소된 데이터를 반영하는지 알아보자.

예를 들어, 위 Users-to-Movies 데이터 행렬에서 $\mathbf{q} = [5, 0, 0, 0, 0]$ 이 주어졌다고 하자. (Matrix에만 5점을 준 새로운 유저)

Projcet into concept-space (Stanford CS246)

Movies-concept 벡터 $V$에 projection하여 얻을 수 있다.

Project into concept-space (Stanford CS246)

이 새로운 유저는 SF-concept는 $2.8$, Romance-concept는 $0.6$이므로 SF 장르를 더 선호한다고 볼 수 있다.

Observation

querying을 이용하면, 새로운 유저가 기존 데이터 중 어떤 데이터와 유사한지 파악할 수도 있다.

Finding Similar User (Stanford CS246)

4번째 유저 $\mathbf{d}=[0, 4, 5, 0, 0]$과 신규 유저 $\mathbf{q}=[5,0,0,0,0]$은 rating 데이터에서는 전혀 공통점이 없다. 그러나 SVD querying을 통해 얻은 벡터는 각각 $[5.2, 0.4],\ [2.8, 0.6]$으로 둘 다 Romance-concept보다 SF-concept을 더 선호한다는 점을 찾을 수 있다.

 

SVD: Drawbacks

SVD를 이용한 차원축소는 optimal low rank approximation이 가능하다.

그러나 몇가지 단점이 있다.

첫번째 단점은 해석(interpretability problem)이다. 

 

두번째 단점은 희소성이 작다는 것이다. (lack of sparsity)

singular vector인 $U$와 $V$가 dense하기 때문에 여전히 사용하고 있는 데이터 메모리는 크다.

Singular Vectors are Dense (Stanford CS246)