Singular Decomposition(2)

SVD가 실제로 어떤 application에 사용되는지 예제를 통해 살펴보자. 

추천시스템 설계의 기본적인 알고리즘으로 사용된다.

 

아래의 예시는 user x movie 행렬을 $A$ (4x3) 이라 할 때, 각 컬럼이 특정 유저가 4개의 영화에 대해 선호도를 rating한 행렬이다. 먼저 SVD에서의 $U, V^{T}$의 singularvector들이 어떤 의미를 갖는지부터 살펴보자. 주어진 (4x3)행렬은 $\Phi : \mathbb{R}^{3} \rightarrow \mathbb{R}^{4}$ 와 같은 linearmapping을 표현한다고 볼 수 있다. 3dim을 user space라 보고, 4dim 을 movie space라 볼 수 있다. 아래의 그림은 SVD한 결과이다. 

 가장 우변인 $V^{T}$에 대해 살펴보도록 하자. $V = [v_{1} \ v_{2} ] v_{3}]$이라는 basis하의 구성이 되어있고, $V$가 orthogonal이기 때문에 $V^{T} = V^{-1}$이라는 것을 알 수 있다. 원래 $V$의 의미를 생각해보면 이 행렬은 $v_{i}$ basis하에서의 coordinate을 stadardbasis 하의 coordinate으로 변환해주는 trasformation matrix가 된다. $V^{-1}$는 반대역할을 하게 된다. stadardbasis 하의 coordinate을 $v_{i}$ basis하에서의 coordinate으로변환해주는trasformation matrix 가 된다.

 Ali라는 유저의 특징이 $Ali = -0.7367 v_{1} + 0.0852 v_{2} + 0.6708 v_{3} $으로 표현된다는 것이다. 여기서 $v_{i}$들은 전형적인 유저의 스타일을 나타낸다. $v_{i}$에 대한 정의를 할 수 없기 때문에 latent feature가 된다.  만약에 $v_{1}$이 액션장르라는 latent feature라고 가정한다면, $V^{T}$의 첫 row 즉 $v_{1}$은 액션 장르라고 다시 맵핑이 되어 유저들이 액션에 대해 내린 rating이라고 할 수 있다. 마찬가지로 노란 부분에서는 Chandra가 선호하는 또 어떤 장르에 대한 선호도가 크다는 것을 의미한다. 

주어진 행렬을 SVD해서 $V$ 행렬에서 성향을 통해 유저군을 그룹핑을 할 수 있다. 같은 고객군으로 묶을 수 있다는 말이다. 

 $U$ 행렬은 어떻게 해석할 수 있을까. $A$를 전치하여 SVD로 나타내보면은 $A^{T} = V \Sigma U^{T}$로 직관적으로 보면 유저를 같은 고객군으로 묶은 것처럼 영화를 그룹핑할 수 있게 된다. Star Wars와 같은 경우에는 $-0.6710u_{1} + 0.0236u_{2} + 0.4647u_{3} - 0.5774u_{4}$ 로 보아 $u_{i}$ basis하에서 표현된다. 뭐 StarWars와 BladeRunner와 같은 경우는 1번째에 대해 가중치가 높은걸로 보아 그룹으로 묶어 볼 수있는데, $V$를 볼 때와 마찬가지로 마찬가지로 값이 비슷한 것들끼리 묶을 수 있되 interpret이 불가능하다.

 

$\Sigma$행렬을 볼 때, 특잇값이 좌상우하로 하여 값이 내림차순이 되는데, 이것은 그룹을 나누기에 그만큼 가중치가 높은 기준이라는 것을 확인할 수 있다.

 

 

 

주어진 행렬을 근사화하는 matrix approximation에 대해 알아보자.

$A$라는 (m x n)행렬을 간단한 형태의 행렬(low-rank)들의 linear combination으로 나타낼수 있는데, 여기

서 $rank \ r < m, n$ 이다. 오른쪽 필기처럼 특잇값들을 low-rank 만큼 자르고 왼쪽,오른쪽 특이벡터행렬도 그만큼으로 자르겠다는 말이다. 그것을 풀어서 설명한 것이 (4.91)이다. 그리고 $u_{i}v_{i}^{T}$는 outer product는 항상 rank가 1이다(전부 선형결합으로 이뤄진 행렬이므로). 이를 $A_{i}$라 표현한다.

 

 

 

그리하여 rank k approximation은 원래 행렬의 정보를 최대한 유지하면서 더 적은 rank를 가지는 행렬을 사용해서 approximation하겠다는 것이다.

아래의 그림은 근사화의 이해를 돕기위해 이미지 어플리케이션에 대한 데이터이다. 이미지 데이터는 (1432 x 1910)의 크기를 가지고 있다. (b)의 경우는 $\sigma_{1}u_{1}v_{1}$이고, (c)의 경우는 $\sigma_{1}u_{1}v_{1}^{T} + \sigma_{2}u_{2}v_{2}^{T}$ 가된다. k가 올라갈수록 알아보기 쉬워진다.

 

  모든 singularvalue를 다 사용하면 1432 x 1910 으로 대략 270만번의 계산량이 나오지만 (f)의 계산량은 5(1 + 1432 +1910)로 약 16000개니까 0.6%정도의 계산량으로 대략적인 original data를 설명할 수 있다는 것이다.