[Linear algebra] SVD

Intro

---

지난글에서는 고윳값과 고유벡터, 고윳값분해(eigenvalue decomposition)까지 정리했는데요,

이번글에서는 고윳값분해의 조금 더 일반화된 형태인 SVD(Singular Value Decomposition)에 대해서 정리하겠습니다.

SVD

---

고윳값분해는 주로 대칭행렬의 직교대각화를 통해 수행했습니다. ($A = PDP^{-1}$)

SVD는 이런 분해를 $n \times p$ 행렬 ($p$차원 벡터 $n$개)에도 적용할 수 있는 일반화된 방법입니다.

$B=U\Sigma V^T$

$U: n \times n 직교행렬$

$\Sigma: n \times p 직사각 대각행렬$

$V: p \times p 직교행렬$

직사각 대각행렬은 왼쪽 위부터 최대 $min(n, p)$번째 대각성분 까지만 값이 있고, 나머지는 0인 행렬입니다.

앞에서 고윳값분해를 할 때 분해 대상 행렬이 대칭행렬이면 계산이 수월하다고 했습니다.

따라서 $n \times p$ 모양을 갖는 행렬 $B$를 분해하기 위해서 $BB^T,B^TB$를 활용합니다.

이들은 각각 $n \times n, p \times p$ 모양을 갖는 대칭행렬이 됩니다.

1. $B^TB$의 고윳값 $\lambda_1,\dots,\lambda_p$과 고유벡터를 구합니다.

이때, $\sigma_1=\sqrt{\lambda_1},\dots,\sigma_p=\sqrt{\lambda_p}$들을 $B$의 특이값(singular value)고 합니다.

이 특이값들을 $\Sigma$행렬의 대각성분으로 사용합니다. 이때, 구해지는 고윳값과 특이값들은 모두 0 이상의 값을 갖습니다.

또한, 각 고윳값에 대응하는 고유벡터들을 $B$의 right singular vector ($V$)로 사용합니다.

2. $BB^T$에 대해서도 고윳값과 고유벡터를 구합니다.

이때 각 고윳값에 대응하는 고유벡터들을 $B$의 left singular vector ($U$)로 사용합니다.

SVD의 활용: 추천 시스템

---

SVD가 활용되는 대표적인 분야는 추천 시스템입니다. 추천 시스템은 사용자의 취향에 어울리는 적절한 상품을 선택하는 문제입니다.

추천 시스템은 크게 사용자와 상품사이의 feedback정보를 사용하는 Collaborative Filtering(CF),

사용자와 상품의 콘텐츠 정보를 활용하는 Content-Based Filtering(CB) 방법이 있습니다.

SVD는 그 중 CF방법에 속합니다.

SVD를 이용해서 분해할 행렬은 rating matrix ($R$)라고 하는, 사용자와 상품 사이의 평점 정보를 기록한 행렬입니다.

행의 수는 사용자의 수, 열의 수는 상품의 수와 같고, 사용자 $u$가 상품 $v$를 구매했을 때, rating matrix $R$의 $(u,v)$칸에는 사용자가 상품에 부여한 평점이 기록되어있습니다. 평점이 없는 칸은 비어있습니다.

SVD를 이용한 추천은 $R$을 SVD를 통해 $U\Sigma V^T$로 분해한 뒤, $U\Sigma (=\hat{U})$를 사용자의 latent vector, $\Sigma V^T (=\hat{V}^T)$을 상품의 latent vector로 사용합니다.

이때, $\Sigma$의 모든 대각원소를 사용하지 않고, $d(<=min(n,p))$개의 대각원소만 사용합니다. 이에 따라 $U, V$도 $d$개 만큼의 고유벡터만 사용하죠. 이때 적절한 $d$를 선택하는 것도 중요합니다.

$\hat{U}$은 $n \times d$으로, $n$명의 고객이 각각 $d$차원 벡터로 표현됐다고 볼 수 있습니다. $\hat{V}$도 마찬가지로 $p$개의 상품이 $d$차원 벡터로 표현됐다고 볼 수 있습니다.

$\hat{U}$과 $\hat{V}$를 행렬 곱하면 우리는 원래 rating matrix $R$을 근사한 $\hat{R}$을 얻게 되고, 비어져있던 값들이 채워지게 됩니다.

우리는 채워진 값을 통해 각 사용자가 상품에게 부여할 예측 평점을 알 수 있게 되고, 이 점수가 높은 상품을 추천하게 됩니다.

하지만 실제로는 SVD보다는 ALS가 더 많이 사용됩니다. ALS는 병렬 연산을 통해 더 빠르게 사용자, 상품의 latent vector를 학습할 수 있는 장점이 있습니다.

마무리

---

이 글에서는 SVD에 대해서 정리했습니다.

읽어주셔서 감사합니다!

References

선형대수와 통계학으로 배우는 머신러닝 with 파이썬

다크 프로그래머님 블로그

삶은 달걀님 블로그