Matrix Factorization

 

 

 

1. 협업 필터링 (Collaborative Filtering, CF)

• 많은 유저들로부터 얻은 선호 정보를 이용해 유저의 관심사 예측
• 최종 목적 : 유저 u가 아이템 i에 부여할 평점 예측
• 기본 구조
  • 주어진 데이터를 활용해 유저-아이템 행렬 생성
  • 유저가 평가하지 않은 아이템에 대한 평점 예측

 

 

2. 이웃 기반 협업 필터링 (Neighborhood Based CF, NBCF)

• 유저 기반
  • 유저 간 유사도를 구한 뒤 타겟 유저와 유사도가 높은 유저들이 선호하는 아이템 추천
• 아이템 기반
  • 아이템 간 유사도를 구한 뒤 타겟 아이템과 유사도가 높은 아이템 중 선호도가 높을 아이템 추천
• 유사한 하나의 유저/아이템이 아니라 k개 유저/아이템을 이용해 평점을 예측하기도 함 (KNN)
• 유저/아이템 간 유사도를 메모리에 저장했다가 사용하는 "메모리 기반" 접근 방식
• 단점
  • 희소성(Sparsity) 문제
    • 데이터가 충분하지 않으면 성능이 떨어짐
    • 데이터가 부족하거나 아예 없는 유저/아이템의 경우 추천 불가 (cold start)
  • 확장성(Scalability) 문제
    • 유저/아이템의 수가 많아지면 유사도 계산량이 늘어남

 

 

3. 모델 기반 협업 필터링 (Model Based CF, MBCF)

• 데이터에 내재한 특성을 학습
• 유저/아이템 벡터를 데이터를 통해 학습하고 업데이트
• NBCF와 비교한 장점
  • 학습 후 추천할 때는 유저/아이템 데이터를 사용하지 않고 학습된 모델만 사용하기 때문에 서빙 속도가 빠름
  • sparsity, scalability가 커져도 좋은 성능
  • 특정 이웃에 크게 영향을 받는 NBCF에 비해 전체 데이터의 특성을 학습해 overfitting 방지됨
  • 유사한 유저/아이템이 없는 경우 NBCF는 성능이 떨어짐
• 행렬 분해를 이용한 모델(SVD, MF 등), 딥러닝 활용한 모델 등 있음

 

 

4. Matrix Factorization

• 유저-아이템 행렬을 k차원의 유저와 아이템 잠재 요인(latent factor) 행렬의 곱으로 분해
• 기본 구조
  • 행렬 내의 모든 원소 값이 음수가 아님이 보장되면 다음과 같은 행렬 분해가 가능
    • Non-Negative Matrix Factorization 이라고도 함
  • R : n명의 유저와 m개의 아이템의 상호작용 데이터를 담은 크기 n × m 의 행렬
  • P : 유저에 대한 k차원 잠재 요인 행렬 (크기 n × k)
  • Q : 아이템에 대한 k차원 잠재 요인 행렬 (크기 m × k)
  $$ R \approx P \times Q^T = \hat R $$
  • 유저 u의 아이템 i에 대한 평점 예측값은 유저 u의 latent vector와 아이템 i의 latent vector의 내적으로 계산
  $$ \hat r_{ij} = p_u q_i^T $$
  • 따라서 실제 평점 $r_{ij}$와 예측값 $\hat r_{ij}$의 차이를 줄이는 방향으로 학습
• Objective Function
  • 정규화 term 추가
  $$ \min_{P, Q} \sum_{observed \space r_{ui}} (r_{ui} - p_u q_i^T)^2 + \lambda(||p_u||^2_2 + ||q_i||^2_2) $$
• 확률적 경사 하강법 (Stochastic Gradient Descent, SGD)
  • 목적함수를 최소화하기 위해 gradient를 계산해 $p_u$, $q_i$ 업데이트
  $$ p_u \leftarrow p_u + \eta (e_{ui} q_i - \lambda p_u) \\ q_i \leftarrow q_i + \eta (e_{ui} p_u - \lambda q_i) \\ \eta : \text {learning rate}, \space e_{ui} = r_{ui} - p_u q_i^T \space (\text {error}) $$

 

 

5. Matrix Factorization + $\alpha$

5-1. Adding Bias

• 유저/아이템의 평점 분포는 동일하지 않음
  • 어떤 유저는 기본적으로 평점이 후할 수도, 다른 유저는 기본적으로 평점이 박할 수도 있음
• bias를 학습 파라미터로 추가해 예측 성능 향상

$$ \hat r_{ui} = p_u q_i^T + \mu + b_u + b_i \\ \mu : \text {global mean}, \space b_u, b_i : \text{user bias, item bias} $$

• 목적 함수

$$ \min_{P, Q} \sum_{observed \space r_{ui}} (r_{ui} - \hat r_{ui})^2 + \lambda(||p_u||^2_2 + ||q_i||^2_2 + b_u^2 + b_i^2) $$

• 파라미터 업데이트

$$ b_u \leftarrow b_u + \eta(e_{ui} - \lambda b_u) \\ b_i \leftarrow b_i + \eta(e_{ui} - \lambda b_i) \\ p_u \leftarrow p_u + \eta(e_{ui}q_i - \lambda p_u) \\ q_i \leftarrow q_i + \eta(e_{ui}p_u - \lambda q_i) \\ \eta : \text {learning rate}, \space e_{ui} = r_{ui} - \hat r_{ui} (\text {error}) $$

 

 

5-2. Adding Confidence Level

• Confidence
  • 선호도를 상황에 따라 다르게 취급
    • ex) 물건 1개를 구매한 유저와 10개를 구매한 유저의 선호도가 같다고 볼 수 없음
  • $c_{ui}$ : 유저 u가 아이템 i를 선호하는 정도
  • $\alpha$ : positive feedback과 negative feedback 간의 상대적 중요도를 결정하는 하이퍼 파라미터
  $$ c_{ui} = 1 + \alpha r_{ui} $$
• confidence와 bias를 모두 반영한 목적함수

$$ \min_{P, Q} \sum_{observed \space r_{ui}} c_{ui} (r_{ui} - \hat r_{ui})^2 + \lambda(||p_u||^2_2 + ||q_i||^2_2 + b_u^2 + b_i^2) $$

 

 

5-3. For Implicit Feedback

• Explicit : 유저의 구체적인 평가가 있는 경우 (평점)
• Implicit : 유저의 구체적인 평가를 알 수 없는 경우
  • 유저의 선호도를 클릭 여부, 시청 여부 등 간접적으로 추측
  • 선호 여부 $f_{u,i}$를 binary 값으로 표현
  $$ f_{ui} = \left\{\begin{matrix} 1 \space r_{ui} > 0\\ 0 \space r_{ui} = 0 \end{matrix}\right. $$
• confidence까지 반영한 목적함수

$$ \min_{P, Q} \sum_{observed \space r_{ui}} c_{ui} (f_{ui} - \hat f_{ui})^2 + \lambda(||p_u||^2_2 + ||q_i||^2_2) \\ \hat f_{ui} = p_u q_i^T $$

 

 

5-4. Alternative Least Square (ALS)

• 기본 개념
  • 목적함수는 동일
  • 유저와 아이템 행렬을 번갈아 업데이트
  • $p_u$, $q_i$ 가운데 하나를 고정하고 다른 하나로 least-square 문제 해결
  • 유저/아이템 그룹을 나누어 병렬 처리가 가능하므로 SGD보다 연산이 더 빠름 (결과는 같음)
• 파라미터 업데이트

$$ p_u = (Q^T Q + \lambda I)^{-1} Q^T r_u \\ q_i = (P^T P + \lambda I)^{-1} P^T r_i $$

• confidence 반영했을 때
  • $C^u$ : 유저 u의 모든 아이템(m개)에 대한 feedback의 confidence level 값이 저장된 대각행렬
    • $C^u_{ii}$ : 유저 u의 아이템 i에 대한 feedbackd의 confidence level 값
  • $C^i$ : 아이템 i의 모든 유저(n개)에 대한 feedback의 confidence level 값이 저장된 대각 행렬

$$ p_u = {(Q^T C^{u}Q + {\lambda}I)^{-1}Q^T C^{u}f_{u}} \\ q_i = {(P^T C^{i}P + {\lambda}I)^{-1}P^T C^{i}f_{i}} $$