[Recommender System / Paper review] #12 BPR: Bayesian Personalized Ranking from Implicit Feedback

• 논문 링크(5317회 인용)

Summary

• 개인화된 랭킹 자체를 output으로 만들기 위한 parameter learning 방법을 제시한다.
• explicit feedback이 아닌, implicit feedback을 이용하며 결측치를 단순히 negative feedback으로 간주하지 않고 유저별 아이템에 대한 선호도를 나타내는 새로운 행렬을 생성하여 학습을 진행한다.
• BPR에서 관심있는 파라미터는 아이템 i가 아이템 j보다 선호되는지 여부이다. 이를 확률로 정의하여 학습을 통해 추정하고, 추정된 확률을 기반으로 개인화된 랭킹을 제공하는 것이 목표이다.
• BPR은 새로운 optimization method으로써, 기존의 neighborhood 기반 방법이나 latent factor 기반 방법의 최적화 방법을 대체하여 사용할 수 있고 실험 결과 더 좋은 성능을 보여주었다.
• 또한 BPR 최적화를 위해 gradient descent가 아니라 더 효율적인 LearnBPR을 제시한다.

Motivation

• neighborhood 기반 방법이나 latent factor 기반 방법이 연구가 되었으나, 이들의 objective function은 점수를 예측하거나 아이템에 대한 행동을 할지 안 할지에 대한 task이다. 이 방법은 직접적으로 랭킹을 optimize하지 않는다.
• 즉, 파라미터를 업데이트하는데 아이템에 대한 랭킹을 잘 하는 방향이 아니라 점수를 잘 맞추는 방향으로 학습이 된다.
• 추천 시스템 분야에서는 결국 유저에게 적합한 아이템을 순서대로 나열해야하는데 기존의 방법들은 점수를 예측하고 이를 순서대로 나열하는 방식이다.
• 본 논문에서는 이런 한계점을 지적하고 개인화된 랭킹을 위한 BRP 최적화 방법을 제시한다.

Approach

개인화된 랭킹은 유저의 선호도에 따라 아이템을 순서대로 제공하는 task이다. 본 논문에서는 implicit feedback을 이용하여 개인화된 랭킹을 제공하는 방법에 대해 살펴본다.

Formalization

• $U, I$: 유저와 아이템
• $S \subseteq U \times I$: implicit feedback
• 풀고자하는 문제: 개인화된 total ranking $>_u \subset I^2$를 제공하는 것이다. 여기서 $>_u$는 아이템에 대한 유저의 개인화된 선호도를 나타내는 행렬로, 아래 조건을 충족한다. $i >_u j$는 유저가 아이템 $j$에 비해 아이템 $i$를 더 선호한다는 기호이다.
  • totality: $\forall i,j \in I: i \neq j \rightarrow i >_u j \lor j >_u i$ (서로 다른 아이템에 대해 하나의 아이템이 반드시 다른 아이템에 비해 더 선호된다)
  • antisymmetry: $\forall i,j \in I: i >_u j \land j >_u i \rightarrow i = j$ (아이템 i가 j에 비해 더 선호되고 그 역도 성립한다면 아이템 i와 아이템 j는 동일한 아이템이다)
  • transitivity: $\forall i,j,k \in I: i >_u j \land j >_u k \rightarrow i >_u k$ (아이템 j에 비해 아이템 i가 더 선호되고 아이템 k에 비해 아이템 j가 더 선호된다면, 아이템 k에 비해 아이템 i가 더 선호된다. 마치 피타고라스의 법칙 느낌)
• $I^+_u := \{ i \in I : (u,i) \in S \}$
• $U^+_i := \{ u \in U : (u,i) \in S \}$

Problem setting

• 기존에 풀고자 했던 문제
  • implicit feedback matrix가 주어지면 관측된 값을 positive, 결측값을 negative feedback으로 간주하여 학습을 진행한다.
  • 즉, 모델이 $S$에 있는 데이터를 1로, 그 이외의 데이터($U \times I \setminus S$)는 0으로 예측하도록 학습된다.
  • 여기서 학습에 사용되는 데이터는 $r_{ui}$로 유저 u가 아이템 i에 대해 implicit feedback을 했는지 여부이다.
• BPR이 풀고자 하는 문제
  • item pairs을 학습하는 데이터로 사용한다.
  • 유저 u가 아이템 i를 본적이 있다면, 유저 u는 보지 않은 모든 아이템에 비해 아이템 i를 좋아한다고 가정한다.
    • $\forall i \in S, \forall j \in U \times I \setminus S, i >_u j$
  • 유저 u가 아이템 j,k을 보두 본적이 있다면, 이 둘에 대한 선호도는 알 수 없다.
  • 비슷하게 유저 u가 아이템 j,k를 모두 본적이 없다면, 이 둘에 대한 선호도는 알 수 없다.
  • 이를 종합하면, implicit feedback $S$로부터 새로운 데이터 세트인 $D_S$를 만든다.
    • $D_S := \{ (u,i,j) | i \in I^+_u \land j \in I \setminus I^+_u \}$

• $u_1$의 선호 행렬
  • $i_1, i_4$은 본 적이 없고 $i_2,i_3$은 본 적이 있다.
  • 따라서 $u_1$가 $i_1, i_4$에 비해 $i_2,i_3$을 더 좋아한다고 가정한다.
  • 이를 행렬에 1행 2열은 +로, 2행 1열은 -로 표현한다.

BPR Optimization

개인화된 선호 행렬을 사용하여 결국 추정하고자 하는 파라미터는 무엇일까? 개인화 랭킹 문제는 유저 u가 아이템 i에 비해 아이템 j를 좋아하는지 찾는 게임이라고 생각해볼 수 있다. 유저별로 모든 아이템 pairs에 대한 선호도를 찾을 수 있다면, 모든 아이템에 대한 랭킹을 매길 수 있을 것이다. 즉, $p(i >_u j | \Theta)$의 확률을 추정하는 것이 최종 목표이다.

이를 해결하기 위해 아래의 베이지안 문제를 정의한다.

• $>_u$: 유저 u의 latent preference structure
• 각각의 유저는 서로 독립이라고 가정한다.
• 어떤 한 유저의 아이템 페어 (i,j)에 대한 순서는 서로 독립이라고 가정한다.

따라서 likelihood는 아래와 같이 다시 표현할 수 있다.

• BPR에서 학습에 사용하는 데이터는 item pair이다: $\prod_{(u,i,j) \in U \times I \times I}$
• $D_S$는 implicit feedback에 포함되는 데이터 쌍이다. 앞서 이런 데이터쌍 (i,j)에 대해 아이템 i가 j에 비해 더 선호될 확률을 다음과 같이 정의했다: $p(i >_u j | \Theta)$
• 일종의 베르누이 sample이 모든 implicit feedback에 대해 정의된 likelihood로 보면 된다.

그렇다면 $p(i >_u j | \Theta)$를 어떻게 정해야 개인화된 추천을 확실하게 할 수 있을까? 유저별로 아이템 쌍에 대한 선호도 확률이 모두 다르게 나와야 한다. 논문에서는 이를 위해 $p(i >_u j | \Theta)$을 아래와 같이 정의한다. 여기서 $\sigma(x) = \dfrac{1}{1 + e^{-x}}$이다.

여기서 중요한 것은 $\hat{x}_{uij}(\Theta)$는 유저 u가 아이템 i,j에 대해 가지는 어떤 실수 값이라는 것이다. neighborhood 기반 모델이든, latent factor 기반 모델이든 상관 없다. 어떤 실수 값으로만 나오면 된다. 그리고 이 실수 값을 sigmoid 함수에 태워서 확률 값으로 변환하는 것이다.

posterior, likelihood에 대해 얘기했으니, 마지막으로 $\Theta$에 대한 prior을 아래와 같이 정의한다.

여기서 $\Sigma_{\Theta} = \lambda_{\Theta}I$이다.

이제 준비는 모두 끝났다. 개인화된 랭킹인 BPR-OPT을 위한 posterior 분포는 아래와 같이 유도된다.

BPR Learning Algorithm

훈련 데이터를 bootstrap sampling하는 SGD에 기반한 LearnBPR 최적화 방법을 소개한다. 먼저, $\Theta$에 대한 gradient는 아래와 같다.

• full gradient descent: 데이터가 매우 많기 때문에 수렴이 느리다.
• stochastic gradient descent: 각 데이터별로 gradient가 업데이트 되는데 수렴이 잘 안 될 가능성이 있다.
• $(u,i,j)$를 랜덤하게 선택하여 sgd을 진행하는 방식을 택한다.

Learning models with BPR

BPR에서 유저 u가 아이템 j에 비해 아이템 i를 더 좋아할 확률을 아래와 같이 정의했다.

근데 기존의 방법들은 유저 u의 아이템 i에 대한 선호도를 모델링한다. 따라서 3개의 인덱스가 있는 $\hat{x}_{uij}$와는 형태가 조금 다른데, 이를 맞춰주기 위해 논문에서는 아래를 제시한다.

BPR은 하나의 단일 값인 $\hat{x}_{ui}$을 예측하는 것이 아니라 $\hat{x}_{uj}$와의 차이를 모델링하는 것이다.

Matrix Factorization with BPR

MF는 유저와 아이템에 대한 latent factor을 찾아서 이에 대한 내적으로 유저의 아이템에 대한 선호도를 표현한다.

$\hat{x}_{uij}$에 따라 다시 적어보면 아래와 같다.

\[ \hat{x}_{uij} = \hat{x}_{ui} - \hat{x}_{uj} = \sum^k_{f=1} w_{uf} \cdot h_{if} - \sum^k_{f=1} w_{uf} \cdot h_{jf} \]

derivatives는 아래와 같다.

Adaptive k-nearest neighbor with BPR

아이템에 기반한 k 이웃 prediction는 아래의 formulation을 사용한다.

여기서 $c_{il}$은 아이템 i와 l간의 유사도 metric이다. derivatives은 아래와 같다.

Results

• BPR을 활용한 MF, KNN이 다른 방법에 비해 월등히 좋은 결과를 보였다.
• 파라미터 최적화 방향을, 점수 예측이 아닌 랭킹으로 한 결과, 추천 품질이 훨씬 좋아졌다고 해석할 수 있다.

Conclusion

• 어떤 단편적인 방법을 제시한 것이 아니라 어떠한 방법 위에서 파라미터 최적화 방향을 개인화 랭킹으로 바꿀 수 있다는 점에서 굉장히 파워풀한 논문인 것 같다.
• 논문에서는 MF, KNN에 BPR을 얹었는데,, 이뿐만 아니라 SVD++, Asymmetric SVD 등 모든 추천 모델에 BPR을 얹을 수 있으니.. 개인화된 랭킹까지 확률로 나오는 BPR은 나중에 꼭 적용해봐야겠다는 생각이 들었다.