추천 시스템

추천 알고리즘 - SVD (Singular Value Decomposition)

망나 2019. 11. 12. 13:43

SVD, wikipedia

추천 시스템에 사용되는 알고리즘 중 하나인 SVD에 대해서 알아보겠습니다

 

 

- Matrix Factorization

먼저 실제로 우리가 풀어야 하는 문제인 Matrix Factorization에 대해서 알아보겠습니다. Matrix Factorization은 추천 시스템에서 주로 사용되는데, \(m\) 명의 사용자와 \(n\) 개의 아이템이 있고 이를 \(m * n\) 형태의 벡터 \(R\)로 나타냈을 때, 다 오차 함수를 최소화하는 k 요인 벡터를 찾는 것입니다.

 

\(R \approx PQ^{T}\)

 

\(R\) : \(m\)명의 사용자들의 \(n\) 개의 아이템에 대한 평점 행렬

\(P\) : \(m\)명의 사용자와 \(k\) 요인에 대한 관계 행렬

\(Q\) : \(n\)개의 아이템과 \(k\) 요인에 대한 관계 행렬

 

모든 사용자들이 모든 상품들에 대해서 평점을 매기는 것은 불가능하기 때문에 실제 행렬\(R\)은 대부분 희소 행렬(sparse matrix)이 됩니다.

 

 

- SVD (singular value decomposition)

SVD는 위에서 설명한 matrix factorization 문제를 푸는 방법 중 하나입니다. 이를 위해서 SVD는 행렬 \(R\)을 3개의 행렬 곱인 \(U\Sigma V^{T}\)으로 나타내어 문제를 해결합니다.

 

SVD에도 아래와 같은 여러 가지 방식이 있습니다. 그중 가장 기본적인 SVD의 구조는 아래와 같습니다.

 

singular value decomposition

 

 

\(U\) : 역행렬이 대칭 행렬인 \(m\) x \(m\)크기의 행렬

\(\Sigma\) : 비 대각 성분이 0인 \(m\) x \(n\)크기의 행렬

\(V^{T}\) : 역행렬이 대칭 행렬인 \(n\) x \(n\)크기의 행렬

 

위 그림에서 비 대각 성분이 0인 행렬 \(\Sigma\)의 대각 성분을 특이치라고 하며 이 특이치를 활용하여 특이치 분해를 하게 됩니다. k값은 하이퍼 파라미터로 사용자가 정해주게 됩니다.

 

\(\hat {U}\) : \(U\)에서 k개의 대표 특이치에 대응하는 k개의 성분만  남긴 \(m\) x \(k\) 크기의 행렬

\(\hat {\Sigma}\) : 대푯값으로 쓰일 k개의 특이치 성분만을 남긴 \(k\) x \(k\) 크기의 행렬

\(\hat {V^{T}}\) : \(V\)에서 k개의 대표 특이치에 대응하는 k개의 성분만 남긴 \(k\) x \(n\) 크기의 행렬

 

각 행렬의 역할에 대해서 설명하자면, \(U\)는 left singular matrix로서 User와 latent factor 간의 관계를 나타냅니다. \(\Sigma\)는 diagonal matrix로 각 latent factor의 중요도를 나타낸다고 할 수 있고, \(V^{T}\)는 right singular matrix로 Item과 latent matrix 간의 관계를 나타냅니다. 여기서 말하는 latent factor는 User와 Item이 갖는 특성을 뜻 합니다. 영화라는 도메인을 예로 들자면 latent factor는 장르, 주연배우 등이 될 수 있는데, 여기서 우리는 실제 계산 과정에서 얻어지는 각 latent factor가 무엇을 뜻하는지 유추할 수는 있겠지만 정확히 어떤 특성을 나타내는지는 알지 못합니다. 이러한 이유 때문에 추천 시스템에 활용할 때, 추천에 대한 어떠한 구체적인 설명이나 이유가 없다는 것이 SVD를 활용한 추천 시스템의 가장 큰 단점이라고 할 수 있습니다.

 

 

- Python example code

 

Surprise라는 python 기반의 추천시스템 라이브러리가 있습니다. 사용하기 쉽고 강력한 기능을 갖고 있기 때문에 활용하며 공부하기에 좋습니다.

 

 

아래 코드는 SVD에 필요한 여러가지 하이퍼 파라미터를 최적화 하기 위해 간단하게 사용했던 Bayesian optimization 코드 일부입니다. 다양한 최적화 기법을 활용해서 하이퍼 파라미터를 튜닝함으로써 추천시스템의 전반적인 성능을 향상시킬 수 있습니다.

 

Bayesian optimization을 활용한 하이퍼 파라미터 튜닝
결과

 

- Reference

 

https://www.youtube.com/watch?v=rYz83XPxiZo

MIT OpenCourseWare, MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018

 

- 추천 시스템 들어가기 (Collaborative Filtering, Singualr Value Decompositoin)

- 추천 시스템 - SVD

'추천 시스템' 카테고리의 다른 글

Multi-Armed Bandits  (0) 2019.11.07
LaTeX 활용해서 논문쓰장  (6) 2018.09.18
Collaborative Filtering  (0) 2018.09.15