[Linear Algebra] SVD(Singular Value Decomposition)

기존의 이웃 기반 협업 필터링(Neighbor Based Collaborative Filtering, NBCF)이 가지고 있는 희소성(Sparsity), 확장성(Scalarbility) 문제를 해결하기 위해 모델 기반 협업 필터링(Model Based Collaborative Filtering, MBCF)이 등장했다. MBCF의 종류는 엄청나게 다양하지만 여기서는 행렬 분해(Matrix Factorization) 중 대표적인 기법인 SVD(Singular Value Decomposition)에 대해서만 다룰 것이다. 이전에 다룬 고윳값 분해와는 조금 다른 방식으로 접근한다. 

 

SVD는 특이값 분해라고 부른다. SVD는 행렬을 고윳값과 고유벡터가 아닌, 특이벡터(Singular vector)들과 특이값(singular value)들로 분해한다. 얻을 수 있는 정보는 고윳값 분해와 동일하지만, SVD는 조금 더 일반적인 행렬들에 적용이 가능하다는 장점이 존재한다. 고윳값 분해는 고유벡터로 이루어진 직교행렬을 통해 계산이 되기 때문에, 정방행렬이 아닐 경우 계산이 불가능하다. 일반적으로 우리가 실제로 접하는 변수들의 경우 정방행렬이 거의 없기 때문에 이 경우에는 특이값 분해 방식을 적용해야 한다. 추천시스템에서의 SVD는 기존 사용자의 평점 행렬을 분해하는 개념으로 보면 된다. 선형 대수에서 잘 알려진 사실 중 하나는 모든 행렬은 인수분해 될 수 있다는 점이다. 우리는 사용자의 평점 행렬을 분해해 보다 좋은 예측 알고리즘을 구축하기 위해 SVD를 사용한다. 

 

$R=U\mathrm{\Sigma }{V}^T$ 

 

여기서 $R_{m\times n}$은 평점 행렬을 의미하고, $U_{m\times m}$는 $R{R}^T$의 m 정규직교(orthonormal eigen vector)를 포함하는 열이 있는 행렬($R{R}^T$의 고유벡터)이며, $U$의 열을 좌특이벡터(left-singular vector)라고 부른다. $V_{n\times n}$은 $R^{T}R$의 n 정규직교를 포함하는 컬럼이 있는 행렬($R^{T}R$의 고유벡터)이며, $V$의 열을 우특이벡터(right-singular vector)라고 부른다. ${\mathrm{\Sigma }}_{m\times n}$는 대각선 항목만 0이 아닌 대각행렬이며 특이값(Singular Value)라고 부른다. $R$의 0이 아닌 특이값은 $R^{T}R$의 고유값의 제곱근을 의미한다. $d\le min\{m,n\}$ 로 잠재 벡터(Latent vector)를 구성하고, 행렬을 대략적으로 인수분해 할 수 있으며, SVD는 다음과 같이 계산된다. 

 

$R\approx U_d{\mathrm{\Sigma }}_d{V}_d^T$

 

여기서 $U_{m\times d},{\mathrm{\Sigma }}_{d\times d},V_{n\times d}$의 차원을 가진다. 우리는 위와 같은 식으로 평점 행렬을 근사하고(명확한 해를 찾을 수 있지만, 그 계산과정이 매우 복잡하고 시간이 오래 걸리는 문제로 인해 평점 행렬을 근사하는 것이다), 최적화 알고리즘으로는 SGD(Stochastic Gradient Descent) 혹은 ALS(Alternative Least Square)를 사용하여  평점을 근사해 사용자 예측 평점을 도출한다. 

 

기존의 평점 행렬은 다차원 공간에서 사용자-아이템 간 상호작용을 표현했다. 하지만 Sparse Matrix 의 한계로 복잡한 사용자-아이템 상호작용을 표현하는데에는 한계가 존재했다. 그러한 이유로 SVD를 사용하게 되었고, SVD는 다차원 행렬을 저차원 행렬로 변환시켜 보다 복잡한 사용자-아이템 간 상호작용을 표현할 수 있게 되었다.