Recommender System Theory : 행렬 분해(Matrix Factorization)

잠재 요인 모델(Latent Factor Model)

협업 필터링(Collaborative Filtering)의 이웃 기반 방법은 두 사용자가 함께 평가한 아이템이 있어야 둘을 비교할 수 있었습니다. 사용자-아이템 행렬의 대부분이 비어 있으므로, 이 조건은 생각보다 자주 깨집니다.

관점을 바꾸어 보겠습니다. 사람들이 영화를 좋아하는 이유는 무수히 많아 보이지만, 몇 가지 큰 성향으로 정리할 수 있습니다. 액션을 얼마나 좋아하는지, 진지한 영화와 가벼운 영화 중 어느 쪽을 좋아하는지, 최신 영화를 선호하는지와 같은 성향입니다. 영화 역시 이러한 축 위에서 어느 정도의 값을 가진다고 볼 수 있습니다. 사용자의 성향과 영화의 성질이 같은 축 위에서 잘 맞을수록 사용자는 그 영화를 좋아할 것입니다.

이처럼 관측된 데이터 뒤에 숨어 선호를 결정하는 요인을 잠재 요인(Latent Factor)이라 하고, 사용자와 아이템을 잠재 요인의 벡터로 표현하는 모델을 잠재 요인 모델(Latent Factor Model)이라 합니다. 사용자 \(u\)를 \(k\)차원 벡터 \(\mathbf{p}_u\)로, 아이템 \(i\)를 같은 \(k\)차원 벡터 \(\mathbf{q}_i\)로 나타내면, 사용자가 아이템에 줄 평점은 두 벡터의 내적으로 예측합니다.

콘텐츠 기반 필터링(Content-based Filtering)에서도 사용자와 아이템을 같은 공간의 벡터로 표현했지만, 그 축은 장르처럼 사람이 정한 속성이었습니다. 잠재 요인 모델에서는 축 자체를 사람이 정하지 않고, 관측된 평점을 가장 잘 설명하도록 데이터에서 학습합니다. 학습된 축이 장르와 비슷한 의미를 갖게 될 수도 있지만, 사람이 이름 붙이기 어려운 성향을 나타낼 수도 있습니다.

행렬 분해(Matrix Factorization)

모든 사용자의 벡터를 행으로 쌓은 행렬을 \(P\), 모든 아이템의 벡터를 행으로 쌓은 행렬을 \(Q\)라 하겠습니다. 사용자가 \(m\)명, 아이템이 \(n\)개라면 \(P\)는 \(m \times k\), \(Q\)는 \(n \times k\) 크기입니다. 모든 사용자와 모든 아이템의 예측 평점은 두 행렬의 곱으로 한 번에 나타낼 수 있습니다.

크기가 \(m \times n\)인 사용자-아이템 행렬을 두 개의 얇은 행렬의 곱으로 나누어 근사한다는 뜻에서 이 방법을 행렬 분해(Matrix Factorization)라 합니다. 잠재 요인의 수 \(k\)는 보통 수십에서 수백으로, 사용자와 아이템의 수보다 훨씬 작습니다.

이 구조가 희소성 문제를 해결하는 이유는 정보가 공유되기 때문입니다. 사용자 A와 C가 함께 평가한 아이템이 없더라도, A의 벡터는 A가 평가한 아이템들에 의해, C의 벡터는 C가 평가한 아이템들에 의해 학습됩니다. 그 아이템들의 벡터는 다시 다른 많은 사용자의 평가로 학습되므로, 결국 모든 사용자와 아이템이 하나의 잠재 공간에 놓이고, 직접 겹치는 평가가 없는 사용자끼리도 벡터를 비교할 수 있게 됩니다.

저장 공간도 크게 줄어듭니다. 사용자 1,000만 명과 아이템 100만 개가 있을 때, 행렬의 모든 칸은 \(10^{13}\)개이지만, \(k = 100\)인 행렬 분해의 매개변수는 \((10^7 + 10^6) \times 100 \approx 1.1 \times 10^9\)개입니다. 관측된 평점에서 학습한 이 매개변수만으로 비어 있는 모든 칸의 값을 예측할 수 있습니다.

특이값 분해의 한계

행렬을 낮은 차원의 행렬 곱으로 근사하는 방법은 선형대수에 이미 있습니다. 특이값 분해(Singular Value Decomposition, SVD)는 임의의 행렬 \(R\)을 세 행렬의 곱 \(U \Sigma V^{\top}\)로 분해하며, 큰 특이값 \(k\)개만 남긴 절단된 특이값 분해(Truncated SVD)는 오차의 제곱합이 가장 작은 계수 \(k\)의 근사 행렬을 만든다는 것이 알려져 있습니다.

문제는 특이값 분해가 모든 칸이 채워진 행렬에서만 정의된다는 점입니다. 사용자-아이템 행렬은 99% 이상이 비어 있으므로, 특이값 분해를 하려면 빈칸을 먼저 어떤 값으로 채워야 합니다. 빈칸을 0으로 채우면 “평가하지 않음”이 “0점”으로 바뀌어 대부분의 아이템을 싫어한다고 학습하게 되고, 평균값으로 채우면 관측되지 않은 값이 관측된 값보다 훨씬 많으므로 근사 결과가 채워 넣은 평균에 끌려갑니다. 또한 채워진 행렬은 더 이상 희소하지 않으므로 계산량과 저장 공간이 매우 커집니다.

그래서 추천 시스템의 행렬 분해는 특이값 분해를 그대로 쓰지 않고, 관측된 칸에서만 오차를 계산하도록 문제를 다시 정의합니다.

목적 함수

관측된 평점의 집합을 \(\mathcal{K}\)라 하면, 행렬 분해는 다음 목적 함수를 최소화하는 \(P\)와 \(Q\)를 찾습니다.

앞의 항은 관측된 평점과 예측 평점의 차이를 제곱해 더한 것으로, 손실 함수(Loss Function)에서 다룬 평균 제곱 오차와 같은 형태입니다. 비어 있는 칸은 합에 포함되지 않으므로, 빈칸을 어떤 값으로 가정할 필요가 없습니다.

뒤의 항은 벡터의 크기에 벌점을 주는 정칙화 항입니다. 매개변수의 수는 관측된 평점의 수에 비해 결코 적지 않으므로, 정칙화가 없으면 모델이 관측된 평점을 외워 버립니다. 평점을 두세 개만 남긴 사용자의 벡터는 그 평점을 완벽히 맞추도록 아주 큰 값을 가지게 되고, 다른 아이템에 대한 예측은 엉망이 됩니다. 과대적합과 정칙화(Overfitting & Regularization)에서 다룬 L2 정칙화가 이 문제를 막으며, \(\lambda\)는 정칙화의 강도를 정하는 하이퍼파라미터입니다.

이 방식은 넷플릭스 프라이즈 기간인 2006년 사이먼 펑크(Simon Funk)가 블로그에 공개하면서 널리 알려졌으며, 그의 이름을 따 Funk SVD라고도 부릅니다. 특이값 분해와 이름은 같지만 실제로는 특이값 분해가 아니라 관측된 값에 대한 최적화 문제라는 점에 주의해야 합니다.

학습 방법

목적 함수를 최소화하는 방법은 크게 두 가지가 쓰입니다.

확률적 경사 하강법(Stochastic Gradient Descent)

첫 번째는 최적화 알고리즘(Optimizer)에서 다룬 확률적 경사 하강법(Stochastic Gradient Descent, SGD)입니다. 관측된 평점을 하나씩 꺼내 예측 오차를 계산하고, 오차를 줄이는 방향으로 해당 사용자와 아이템의 벡터만 조금씩 수정합니다. 평점 \(r_{ui}\)에 대한 오차를 \(e_{ui} = r_{ui} - \mathbf{p}_u \cdot \mathbf{q}_i\)라 하면, 학습률 \(\eta\)로 두 벡터를 다음과 같이 갱신합니다.

오차가 양수이면, 즉 실제 평점이 예측보다 높으면 사용자 벡터는 아이템 벡터 쪽으로, 아이템 벡터는 사용자 벡터 쪽으로 움직여 내적이 커집니다. 오차가 음수이면 반대로 움직입니다. 정칙화 항은 두 벡터를 원점 쪽으로 조금씩 당깁니다.

\(k = 2\), \(\eta = 0.1\), \(\lambda = 0.02\)이고, 사용자 벡터가 \(\mathbf{p}_u = [0.5, 0.2]\), 아이템 벡터가 \(\mathbf{q}_i = [0.4, 0.6]\), 실제 평점이 4라고 하겠습니다. 현재 예측은 \(0.5 \times 0.4 + 0.2 \times 0.6 = 0.32\)이므로 오차는 \(e_{ui} = 4 - 0.32 = 3.68\)입니다. 두 벡터를 갱신하면 다음과 같습니다.

갱신된 벡터의 내적은 약 0.660으로, 한 번의 갱신으로 예측이 0.32에서 0.66으로 실제 평점 쪽에 가까워졌습니다. 아이템 벡터를 갱신할 때는 사용자 벡터의 갱신 전 값을 사용한다는 점에 주의합니다. 이 과정을 모든 관측된 평점에 대해 여러 번 반복하면 벡터들이 점차 목적 함수의 최솟값 근처로 수렴합니다.

교대 최소 제곱법(Alternating Least Squares)

목적 함수는 \(P\)와 \(Q\)의 곱을 포함하므로, 두 행렬을 동시에 최적화하는 문제는 볼록하지 않습니다. 그러나 한쪽을 고정하면 문제가 바뀝니다. 아이템 벡터 \(Q\)를 고정하면, 각 사용자 벡터 \(\mathbf{p}_u\)를 구하는 문제는 정칙화가 들어간 선형 회귀와 같아지고, 닫힌 형태의 해가 존재합니다.

\(Q_u\)는 사용자 \(u\)가 평가한 아이템들의 벡터만 모은 행렬이고, \(\mathbf{r}_u\)는 그 아이템들에 대한 사용자 \(u\)의 평점입니다. 교대 최소 제곱법(Alternating Least Squares, ALS)은 아이템 벡터를 고정하고 모든 사용자 벡터를 푼 다음, 사용자 벡터를 고정하고 모든 아이템 벡터를 푸는 과정을 번갈아 반복합니다. 매 단계에서 목적 함수가 줄어들거나 유지되므로 안정적으로 수렴합니다.

교대 최소 제곱법의 장점은 병렬화가 쉽다는 것입니다. 아이템 벡터를 고정하면 각 사용자 벡터는 다른 사용자 벡터와 무관하게 독립적으로 풀 수 있으므로, 수천만 명의 사용자를 여러 컴퓨터에 나누어 동시에 계산할 수 있습니다. 그래서 분산 처리 환경의 행렬 분해 구현은 대부분 교대 최소 제곱법을 사용합니다. 또한 암시적 피드백(Implicit Feedback)처럼 빈칸까지 모두 목적 함수에 포함해야 하는 경우에도 효율적으로 계산할 수 있습니다.

편향 항(Bias)

평점에는 사용자와 아이템의 상호작용과 무관한 개별적인 경향도 섞여 있습니다. 어떤 사용자는 모든 영화에 후하게 점수를 주고, 어떤 영화는 누가 보든 높은 점수를 받습니다. 이러한 경향까지 내적으로 설명하려 하면 잠재 요인의 일부가 낭비됩니다.

그래서 예측 평점을 전체 평균과 사용자 편향, 아이템 편향, 그리고 상호작용 항의 합으로 나누어 표현합니다.

\(\mu\)는 전체 평점의 평균, \(b_u\)는 사용자 \(u\)가 평균보다 얼마나 후하게 또는 박하게 평가하는지, \(b_i\)는 아이템 \(i\)가 평균보다 얼마나 높게 또는 낮게 평가받는지를 나타냅니다. 예를 들어 전체 평균이 3.7점이고, 어떤 영화가 평균보다 0.5점 높게 평가받으며, 어떤 사용자가 평균보다 0.3점 박하게 평가한다면, 이 사용자가 이 영화에 줄 평점의 기준값은 \(3.7 + 0.5 - 0.3 = 3.9\)점입니다. 내적 항은 이 기준값에서 개인의 취향에 따라 더하거나 빼는 부분만 설명하면 됩니다.

\(\mu + b_u + b_i\)만으로 이루어진 모델을 기준 예측기(Baseline Predictor)라 하며, 이것만으로도 상당한 예측 성능을 보입니다. 편향 항은 사용자 벡터, 아이템 벡터와 함께 학습되며, 마찬가지로 정칙화를 적용합니다.

넷플릭스 프라이즈 기간에 예후다 코렌(Yehuda Koren) 연구진은 여기에 더해, 사용자가 어떤 아이템을 평가했는지 자체를 정보로 활용하는 SVD++, 시간에 따라 변하는 사용자와 아이템의 편향을 반영하는 timeSVD++ 등을 발표했습니다. 평점의 값뿐 아니라 평점을 남겼다는 사실과 남긴 시점까지 모델에 넣은 것으로, 행렬 분해가 다양한 정보를 흡수할 수 있는 유연한 틀이라는 것을 보여 주었습니다.

• Tip : 평가 기준이 평점의 오차라면 편향 항은 큰 효과가 있습니다. 그러나 사용자별로 아이템의 순서만 중요한 Top-K 추천에서는 사용자 편향 \(b_u\)가 그 사용자의 모든 아이템에 똑같이 더해지므로 순서를 바꾸지 못합니다. 순서에 영향을 주는 것은 아이템 편향과 내적 항입니다.

잠재 공간의 의미

학습이 끝난 사용자 벡터와 아이템 벡터는 같은 공간에 놓여 있습니다. 내적이 크다는 것은 사용자가 아이템을 좋아할 것이라는 뜻이므로, 이 공간은 취향의 지도라 할 수 있습니다. 비슷한 사용자들이 좋아한 아이템들은 서로 가까운 방향에 모이고, 아이템 벡터끼리의 유사도를 계산하면 협업 필터링의 아이템 유사도와 비슷한 결과를 얻을 수 있습니다.

이 구조는 단어 임베딩(Word Embedding)과 매우 닮아 있습니다. 단어 임베딩이 함께 등장하는 단어들을 가까운 벡터로 학습했다면, 행렬 분해는 같은 사용자에게 함께 선호되는 아이템들을 가까운 벡터로 학습합니다. 실제로 2014년 오머 레비(Omer Levy)와 요아브 골드버그(Yoav Goldberg)는 네거티브 샘플링을 사용한 Skip-gram이 단어와 문맥 단어의 동시 등장 통계로 만든 행렬을 암묵적으로 분해하는 것과 같다는 것을 보였습니다. 추천 시스템에서 사용자와 아이템의 벡터를 흔히 사용자 임베딩(User Embedding), 아이템 임베딩(Item Embedding)이라 부르는 이유입니다.

벡터의 내적으로 점수를 계산하므로, 사용자 벡터 하나가 주어지면 내적이 가장 큰 아이템을 찾는 문제는 검색 증강 생성(Retrieval-Augmented Generation)에서 다룬 최근접 이웃 검색이 됩니다. 아이템이 수백만 개라도 근사 최근접 이웃 검색으로 빠르게 후보를 찾을 수 있으므로, 행렬 분해는 대규모 추천 시스템의 후보 생성 단계에 잘 맞습니다.

행렬 분해의 한계

행렬 분해는 넷플릭스 프라이즈 이후 협업 필터링의 표준이 되었지만, 다음과 같은 한계가 있습니다.

• 콜드 스타트 : 사용자와 아이템의 벡터는 관측된 상호작용에서만 학습되므로, 상호작용이 없는 새 사용자와 새 아이템에는 벡터가 없습니다. 이웃 기반 방법과 같은 문제를 그대로 가집니다.
• 속성 정보의 부재 : 기본적인 행렬 분해는 사용자의 나이나 아이템의 카테고리 같은 속성을 사용하지 않습니다. 속성을 함께 쓰려면 모델을 확장해야 합니다.
• 내적의 표현력 : 예측 값이 두 벡터의 내적, 즉 잠재 요인별 곱의 단순한 합이므로 요인 사이의 복잡한 상호작용을 표현하기 어렵습니다.
• 재학습 비용 : 새로운 상호작용이 생기거나 새로운 사용자가 가입하면 벡터를 다시 학습해야 합니다. 이웃 기반 방법이 새 상호작용을 바로 반영할 수 있는 것과 대조적입니다.

속성 정보의 부재와 내적의 표현력 문제는 이후 딥러닝 추천 모델이 등장한 주된 동기가 되었습니다. 사용자와 아이템을 벡터로 표현한다는 행렬 분해의 핵심은 그대로 두고, 벡터를 만드는 부분과 점수를 계산하는 부분을 신경망으로 바꾸는 방향으로 발전했습니다.

행렬 분해 정리

행렬 분해는 추천을 사용자와 아이템을 같은 공간에 배치하는 문제로 바꾸었습니다. 이웃 기반 방법이 관측된 평점을 그대로 비교했다면, 행렬 분해는 관측된 평점을 설명하는 저차원의 표현을 학습하고, 그 표현으로 관측되지 않은 칸을 채웁니다. 이 관점은 오늘날 딥러닝 기반 추천 모델에도 그대로 이어집니다.

지금까지는 사용자가 직접 남긴 평점, 즉 명시적 피드백을 가정했습니다. 그러나 실제 서비스에 쌓이는 데이터의 대부분은 클릭과 구매 같은 암시적 피드백이며, 이때는 관측되지 않은 칸을 무시하는 목적 함수가 더 이상 성립하지 않습니다. 다음 강좌에서는 암시적 피드백에서 행렬 분해를 학습하는 방법을 다룹니다.

• Writer by : 윤대희