[LLMRec/개념] 추천 시스템에서 Matrix Factorization과 Indexing

1. Matrix Factorization (행렬 분해)이란?

Matrix Factorization은 하나의 큰 행렬을 두 개 이상의 작은 행렬로 분해하는 기법이다. 즉, 복잡한 데이터를 더 간단한 형태로 나누어 처리하기 쉽게 만드는 방법이라고 생각할 수 있다. 이를 수식으로 나타내면 다음과 같다 :

 

$$A=B\times C$$

• $A$: 원래의 행렬(입력 데이터)
• $B,C$: 분해된 작은 행렬(저차원 형태의 데이터)

 

행렬 분해를 통해 원래의 행렬보다 계산이 간단해지고, 데이터의 숨겨진 구조와 패턴을 파악할 수 있는 장점이 있다. 이러한 이유로 Matrix Factorization은 추천 시스템, 데이터 압축, 차원 축소 등 다양한 분야에서 널리 활용된다.

 

 

Matrix Factorization은 여러 방식으로 구현될 수 있으며, 그중 대표적인 기법들은 다음과 같다 . 

• SVD(Singular Value Decomposition) : 행렬을 고유 벡터와 고유 값으로 분해하여 특징을 추출하는 방식. 이는 학습(learning)을 수행하는 알고리즘은 아니고, 행렬을 수학적으로 분해하는 방법임.
• ALS(Alternating Least Squares) : 행렬 분해를 반복적인 최적화 방식으로 수행하여(교대 최소 제곱법) 사용자와 아이템 행렬을 학습

 

2. 추천 시스템에서의 MF

일반적으로 추천 시스템의 데이터는 사용자-아이템 상호작용을 나타내는 매우 고차원의 행렬로 표현된다. 이 행렬은 사용자가 아이템에 남긴 평점, 클릭 횟수, 구매 여부 등과 같은 정보를 포함하며, 사용자와 아이템 간의 관계를 나타내는 중요한 데이터 구조다.

 

$$R = \begin{bmatrix}
    5 & 3 & 0 & 1 \\
    4 & 0 & 0 & 1 \\
    1 & 1 & 0 & 5 \\
    0 & 0 & 5 & 4
    \end{bmatrix} $$

 

$$item (R_{ij}) : 사용자 i가 아이템 j에 남긴 평점$$

 

 

 

하지만 이러한 행렬은 희소(sparse) 행렬인 경우가 많다. 즉, 대부분의 값이 비어 있는 상태로, 직접적으로 계산하거나 분석하기에는 비효율적이다. MF는 이러한 고차원 행렬을 다루기 위해 사용되는 대표적인 기법으로, 사용자-아이템 행렬 $R$을 두 개의 저차원 행렬로 분해하는 역할을 한다.

 

$$R\approx U⋅V^T$$

 

그리고 이렇게 분해된 두 행렬은 각각 다음과 같은 의미를 가진다.

• $U (m\times d)$ : 각 사용자를 나타내는 벡터로, 사용자의 취향을 저차원 잠재 공간에서 수치적으로 표현
  • $m$ : 사용자 수
  • $d$ : 잠재 공간의 차원(latent dimension)
• $V (n\times d)$ : 각 아이템을 나타내는 벡터로, 아이템의 특징을 저차원 잠재 공간에서 수치적으로 표현
  • $n$ : 아이템 수
  • $d$ : 잠재 공간의 차원(latent dimension)

이 때, 잠재 공간(latent space)란 사용자와 아이템의 숨겨진 특성을 동일한 차원에서 나타내는 공간을 의미한다. 예를 들어, d-dim의 잠재 공간에서 사용자의 취향과 아이템의 특징은 각각 d-dim vector로 표현된다. 즉, Matrix Factorization은 사용자의 취향과 아이템의 특징을 동일한 차원의 잠재 공간에서 표현할 수 있게 해준다.

 

 

이렇게 사용자와 아이템이 동일한 잠재 공간에 투영했을 때의 장점이 있습니다.

• 소수의 차원(latent space의 dim)만으로도 사용자 및 아이템 데이터를 효과적으로 표현할 수 있음
• 벡터 간 연산을 통해 두 요소간의 관계를 분석할 수 있음

 

즉, 사용자와 아이템의 선호도를 두 벡터간의 연산을 통해 간단히 계산할 수 있음을 의미한다. 구체적으로 두 벡터 간의 내적 값이 클수록, 사용자가 해당 아이템을 더 선호한다고 판단할 수 있다.

 

R_{ij}\approx U_i\cdot V_j^T

 

 

 

 

하지만 MF는 새로운 사용자나 아이템에 대한 데이터가 없으면, 초기 잠재 벡터를 학습 할 수 없어 추천이 어렵다. 이러한 문제를 cold start라고 하며, 이를 해결하기 위해 추가적인 메타 데이터(예 : 사용자 프로필, 아이템의 텍스트 정보 등)을 활용하는 방식이 연구되고 있다. 

 

 

 

3. Matrix Factorization와 Index

 

Matrix Factorization(MF)은 추천 시스템에서 사용자와 아이템의 벡터를 생성하는 기법이다. 하지만 검색을 위한 인덱스를 직접 생성하지는 않는다. 대신, MF에서 생성한 사용자와 아이템 벡터를 ANN(Approximate Nearest Neighbor) 검색 기법과 결합하여 검색 속도를 최적화 할 수 있다.

 

 

 

📌 ANN(Approximate Nearest Neighbor)이란?

Nearest Neighbor란 주어진 벡터에 대해 가장 가까운(유사한) 벡터를 찾는 문제다. 가장 단순한 방법은 모든 벡터와 비교하여 거리(distance)를 측정하는 방식인데, 이는 데이터가 많아질수록 계산량이 기하급수적으로 증가하는 비효율성을 가지고 있다. 이를 해결하기 위해 등장한 것이 이에 ANN 알고리즘이다.

ANN은 완벽하게 가장 가까운 점을 찾는 대신, "거의" 가까운 점을 빠르게 찾는 알고리즘이다. 추천 시스템에서 ANN은 MF가 생성한 아이템 벡터들 중에서, 사용자 벡터와 꽤나 가까운(선호하는) 아이템 벡터를 검색해 사용자가 좋아할 만한 아이템을 빠르고 효율적으로 찾는다.

 

 

 

 

MF와 ANN이 결합하여 작동하는 과정은 다음과 같다.

1. MF로 모든 아이템 벡터 $V$를 모두 미리 계산하고 저장해둔다.
2. 사용자가 특정 시점에서 보여준 행동 데이터를 기반으로 해당 사용자의 벡터 $u_i$를 계산한다.
3. ANN 알고리즘을 사용하여 $u_i$와 가장 유사한 $v_j$를 빠르게 검색한다.
4. 이렇게 검색된  $v_j$ 벡터들 중에서 유사성이 높은 상위 NNN개의 아이템을 사용자에게 추천한다.

 

 

MF만 단독으로 사용하는 경우, 추천 아이템을 계산할 때 모든 아이템과 비교해야 하는 비효율성이 있다. 하지만 MF와 ANN을 결합하면 이러한 비교 과정을 최적화하여 빠르고 효율적인 검색을 통해 추천 결과를 더욱 빠르게 제공할 수 있다는 장점이 있다.