[논문 리뷰] BPR: Bayesian Personalized Ranking from Implicit Feedback

 추천 시스템에서 사용하는 data는 explicit data와 implicit data로 나뉩니다.  explicit Data는 사용자가 직접 제공하는 피드백으로 사용자가 자신의 선호도를 명확하게 표현한 데이터를 의미합니다. 예시로는 사용자가 남긴 평점과 리뷰가 있습니다. 반대로 Implicit data는 사용자가 간접적으로 제공하는 데이터로 클릭, 해당 아이템을 본 시간 구매여부 등을 포함합니다.

 

 explcit data는 선호도가 명확하게 반영되므로 positive feed back인지 negative feed back인지 labeling을 할 수 있습니다.  반대로 implicit는 아이템의 클릭 여부나 구매 여부가 있으면 1을 아이템에 대한 interaction이 관측되지 않았다면 0으로 labeling을 진행합니다. 따라서 label이 0인 data에는 유저가 선호할 수 있지만 관측되지 않은 데이터(missing values)와 유저가 관심이 없어서 관측되지 않은 데이터(negative feed back)이 모두 포함되게 됩니다. 

 

implicit data로 학습된 모델이 실제 예측해야할 data는 non observed data인데 이에 대해서는 모두 label 0이 되도록 학습이 되었으므로 모델이 잘 학습이 되었다면 관측되지 않은 data에 대해서는 0으로 예측하게 될 것입니다. 저자는 모델이 data에 대해 적절한 label을 부여할 수 있게되는 것은 overfitting 방지를 위한 regularization 방법들 때문이라고 지적했습니다.

 

 data의 대다수를 이루는 Implicit data의 문제점을 극복하기 위해 본 논문은 BPR-opt를 제안합니다. BPR는 Bayesian Personalized Ranking는 user user 개인의 item에 대한 선호도(ranking)을 Maximum A Posterior(Bayesian Optimization)방식으로 추론하겠다는 의미를 담고 있습니다.  

 

Formalization

 이부분을 작성하는데 참고한 포스팅입니다. 

https://leehyejin91.github.io/post-bpr/

(좋은 포스팅 올려주셔서 감사합니다.)

 

$ U : 유저들의 집합 $

$ I  :  아이템들의 집합 $

 

$ S \subseteq U \times I$

S: 관측된 users와 item의 모든 조합 

 

 BPR opt는 user별 personalized total rankng을 $  \geq_u \subseteq I^2 $을 구하는 것이다.

$  \>_u \subseteq I^2 $ 는 $ I = \{I_1, I_2, I_3, I_4, I_5\} $ 이 있다고 할 때, user가 선호할만한 item을 순서대로 나열한 것이다. $ {I_4, I_2, I_1, I_3, I_5 $ 순서로 선호한다면  다음과 같이 $ I_4 >_u I_2 >_u I_1 >_u  I_4 >_u I_3 >_u I_5 $ 를 나타낼 수 있으며, 여기서 \[ I_4 >_u I_1 >_u I_5 \] 는 \( >_u \subseteq I^2 \)의 한 가지 예가 된다. 

 

 

 $  \geq_u $의 3 가지 조건입니다. 

 

totality

 totality의 의미는 user u의 item i에 대한 선호도가 item j에 대한 선호도 보다 높거나 혹은 j의 선호도가 i의 선호도보다 높은 상황에서 i와 j는 같은 항목이 아니다. 즉, 서로 다른 아이템의 선호도에는 무조건 높고 낮음이 존재한다. (v는 합집합을 의미합니다.)

antisymmetry

 i의 선호도가 j의 선호도보다 높으면서 또 j의 선호도가 i의 선호도 보다 높다는 것은 i와 j는 같은 품목이다. 

transitivity

 i의 선호도가 j의 선호도보다 높으면서 j의 선호도가 k의 선호도 보다 높다면 i의 선호도는 k의 선호도보다 높다.

 

 

 

Labeling

 

 

 

 기존 implicit data의 labeling 과정을 그림으로 나타낸 것입니다. +는 관측된 user와 item의 interaction을 나타내며 1로 labeling이된 것을 볼 수 있습니다. ?는 관측되지 않은 user와 item의 interaction을 나타내며 0으로 라벨링이 되었습니다. 0으로 라벨링된 interaction 중에 negative feed back들과 missing value들이 섞여 있으므로 학습에 있어 문제가 되는 것입니다. 또  user의 개인화된 순위를 매기지 않는 것도 기존 라벨링의 단점이라 할 수 있습니다.

 

 

 

 다음은 BPR 에서 제안한 Labeling 과정입니다. labeling 과정은 관측된 데이터와 관측되지 않은 데이터 간 비교를 통해서만 이뤄집니다. 논문에서 강조하는 추천 테스크의 본래 역할은 유저들의 선호도을 고려하여 추천할 아이템들의 순위를

 정하는 것입니다. 순위를 정해야 하는데 관측된 데이터 간에 정확한 순위를 알기는 어렵고 또 관측되지 않은 데이터 들 간의 순위는 파악할 수 없습니다. 반대로 관측된 데이터와 관측되지 않은 데이터 중에는 관측된 데이터의 선호도가 더 높을 것이므로 정확한 라벨링을 진행할 수 있습니다. 

 이런 방식으로 user의 선호도에 따른 item i와 item j의 비교를 통해 labeling이 진행됩니다. 열에 있는 $ item_i $ 들을 기준으로 $ item_i $의 선호도가 j보다 높다면 즉, i 만 관측되고 j는 관측되지 않았다면 +의 값을 갖고 반대의 상황이라면 - 를 가지게 됩니다. 또 두 가지 아이템 모두 관측되었거나 관측되지 않았을 때는 비교가 불가능 하므로 ? 라벨을 갖게 됩니다. 라벨링이 진행된 후에는 user마다 관측여부를 기준으로 아이템에 대한 선호도가 반영된 라벨링 테이블을 갖게되는 것입니다.

 

Dataset

 사용하는 dataset의 구조 역시 비교 가능한 item들의 조합으로 이루어집니다.

$ I^+_u := /{i \in I : (u,i) \in S/} $

$ U^+_i := /{u \in U : (u,i) \in S/} $

 

$ I^+_u $: user-item interaction이 관측된 item들의 집합

$ U^+_i $: user-item interaction이 관측된 user들의 집합

 

$ D_s := \{(u, i, j)|i \in I^+_u Λ j \in I\\ I^+_u \} $

 

dataset $ D_s $는 user u에 대해 intetaction interaction이 존재하는 item i와 존재하지 않는 item j로 만든 triple을 의미합니다.

 

BPR OPT는 MAP로 모델의 파라미터를 추정하는 방법입니다. 이에 대한 선수 지식으로 필요할 거 같은 MLE와 MAP에 대해 정리해 봤습니다.

MLE

 

 MLE는 Likelihood(어떤 모수의 분포에서 관측된 데이터가 나올 확률)을 최대화 하는 모수를 찾는다. Y가 관측된 data들 $ \theta $가 모수라면 Likelihood는 P(Y|$ \theta $)로 표현됩니다.

 

 

 파란색 분포와 빨간색 분포가 존재할 때 파란색 분포의 모수는 $ \theta_1 $ 빨간색 분포의 모수는 $ \theta_2 $라고 가정해보겠습니다. data point $x_1$이 파란색 분포에서 나왔을 확률은 $ p(X=x1|$ \theta = \theta_1) $ 빨간색 분포에서 나왔을 확률은 $ p(X=x_1|$ \theta = \theta_2) $ 라 할 수 있습니다. 그림에서 확인 가능하다 시피 $ p(X=x1|$ \theta = \theta_1) $ 이 더 높으므로 data point가 $ x_1 $은 파란색 분포의 Likelihood가 더 높고 반대로 $x_2$는 빨간색 분포에서의 Likelihood가 더 높을 것입니다. 

 MLE는 데이터 포인트 여러 개가 있을 때 데이터의 분포를 설정하고 어떤 모수가 Likelihood를 최대화 하는 지 찾아가는 방법입니다.  $ max_\theta p(X = x_1, x_2 ,....\mid \theta = ?) $

 

MAP

 

  MAP는 likelihood가 아닌 Posterior(사후 확률)를 최대화 하는 모수의 분포를 찾아내는 방법입니다.

MAP에서 사용되는 용어를 정리하고 가겠습니다. 먼저 x는 관측된 데이터, $\theta$는 모수 $ p(\theta \mid  x ) $는 사후확률 이라고 합니다. 사후 확률은 데이터 x가 관측 된 후의 확률을 의미합니다.  $ p(x \mid  \theta ) $는 likelihood  $ p(\theta) $는 prior라고 합니다.  MAP는 $p(\theta) $ 모수의 확률 분포에 대한 가정을 한 후 가정된 prior로 부터 데이터가 관측될 때 마다 likelihood에 의해 새로운 분포 $ \theta \mid x $를 추정해 나갑니다. 새로운 데이터가 발견 될 때마다 $ \theta \mid x $의 분포가 달라지게 됩니다. MLE의 경우에도 관측되는 데이터에 따라 모수의 추정값이 달라지지만 모수의 분포를 추정하는 것과는 다릅니다.

모수의 분포를 찾아낸다는 말은 MLE는 모수가 정해진 값 fixed value라고 보아서 $ \mu $ 에 대해 추정하는 $ hat{\mu} $  MAP는 모수를 확률 변수로 보므로 모수의 분포를 추정하는 것입니다.  $ max_\theta p(\theta \mid x) $

$  p(\theta | x) $는 Bayes Rule에 의해 아래와 같이 정리될 수 있습니다.

 

 

Bayes Rule에 의해 posterior의 형태가 바뀌게 되고 바뀌게 된 형태에서 $ \theta $에 대한 함수에서 상수 취급이 되는 p(x)를 제거하면 posterior를 최대화하는 문제는 $ p(x \mid  \theta )p(\theta) $ 를 최대화 하는 문제로 바뀌게 됩니다.

 

Likelihood

 

 

Likelihood는 item i의 선호도가 j의 선호도 보다 높거나 낮은 경우 밖에 없는 이진 분류의 성황이므로 bernoulli 분포를 따릅니다.  따라서 위와 같은 binary cross entropy의 형태를 띄는 것입니다. 

 

 

 

Prior

 

MAP의 prior는 평균이 0인 정규분포로 가정되었습니다. 

 

위에서 계산한 Likelihood와 prior를 함께 계산하면 위와 같은 식이 나오는데 prior의 결과가 어떻게 되는 지 정리해 봤습니다

 

일반적인 다변량 정규 분포의 확률함수는 아래와 같습니다.

 여러가지 변수와 펑균을 벡터로 표현하면 공분산 행렬과 행렬 곱으로 편하게 계산할 수 있습니다.

 

 

이러한 과정을 거쳐 최종 Loss가 정의되는 것입니다.