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

1. ABSTRACT & INTRODUCTION

- 본 눈문은 implicit feedback을 활용해 personalized ranking을 예측하는 데 있어, Bayesian anaysis에 기반을 둔 최대사후확률(maximum posterior estimator)을 이용한 generic optimization criterion인 BPR-OPT를 제안한다.

- 또한 BPR-OPT를 보다 잘 활용할 수 있는, SGD 기법에 bootstrapping을 적용한 sampling 방법을 활용해 만든 learning method를 제안한다.

- 당시 추천 모델에서 state-of-the-art에 해당하는 MF와 kNN 기법에 BPR-OPT를 적용해 그 성능을 입증하고 있는데, 13년이나 지난 2022년 시점에서는 큰 의미를 가지지는 않을 것 같다는 생각이다. BPR-OPT이라는 criterion이 여러 모델에 범용적인 적용이 가능하다는 것 정도를 이해하고 넘어가면 될 것 같다.

- 대부분의 feedback은 explicit이 아닌 implicit feedback인 경우가 많으므로(클릭, view times, 구매 등), 이를 잘 활용하는 것이 중요함을 저자는 강조하고 있다.

 

본 논문이 주장하는 novelty는 아래의 네 가지다.

 

1. We present the generic optimization criterion BPR-Opt derived from the maximum posterior estimator for optimal personalized ranking. We show the analogies of BPR-Opt to maximization of the area under ROC curve.

→ maximum posterior estimator에 기반한 BPR-Opt 제안

2. For maximizing BPR-Opt, we propose the generic learning algorithm LearnBPR that is based on stochastic gradient descent with bootstrap sampling of training triples. We show that our algorithm is superior to standard gradient descent techniques for optimizing w.r.t. BPR-Opt.

→ BPR-Opt를 학습하기 위한 learning algorithm인 LearnBPR 제안. 일반적인 GD/SGD에 비해 우수하다.

 

3. We show how to apply LearnBPR to two state-of-the-art recommender model classes.

4. Our experiments empirically show that for the task of of personalized ranking, learning a model with BPR outperforms other learning methods. 

→ kNN과 MF에 LearnBPR을 적용해 성능이 개선됨을 보임. personalized ranking에는 BPR이 좋다.

 

2. PRELIMINARIES (기존 연구의 방향성)

논문이 쓰일 당시 추천 시스템에서 가장 성능이 우수했던 모델은 kNN과 MF의 과적합 문제를 극복하고자 한 WR-MF(regularized least-square optimization with case weights)였다. 이 두 방법론에 BPR을 적용해 성능이 향상됨을 보이고, maximum margin matrix factorization(MMMF)와의 유사성과 차이에 대해서도 뒤쪽에서 서술하고 있다.

 

해당 논문은 데이터가 시시각각 변하지 않는 offline learning에 한정해 연구를 진행했고, 이는 기존 연구에 의하면 online learning scenario에도 적용 가능하다고 밝히고 있다. 또한 item의 pair를 활용해 personalized ranking을 구하는 방식을 사용했다.

 

3. Personalized Ranking

implicit feedback system에서는 positive observation(보통 1로 표현)만 관측되며, 관측되지 않은 user-item pair의 경우 negative feedback(보통 0으로 표현)인지 missing value인지 알 길이 없다. 이를 잘 해결하는 것이 핵심인데, 기존의 방식은 이러한 관측되지 않은 pair가 곧 anking의 대상이 되는 target임에도 불구하고 그 전체 혹은 일부를 negative feedback으로 간주해버리기 때문에, 모델이 충분한 표현력을 가졌다면 정확한 예측이 불가능하다. (이미 정답을 다 '0'이라 정했기 때문이다.)

이러한 한계를 극복하기 위해 논문은 training data D_S를 생성한다. 위 Figure 2처럼 각 유저에 대해 I*I matrix를 생성했을 때 +로 표현되는 위치의 (u,i,j) 값들이 원소로 들어가게 된다(세 개의 값을 하나의 원소로 가져 training triples라 칭하기도 함). 이는 positive observation이 있었던 아이템은 그렇지 않은 아이템보다 선호될 것이며, positive observation이 있었던 아이템끼리 혹은 positive observation이 없었던 아이템 끼리는 선호도 비교를 할 수 없다는 것을 전제로 한다. 이는 아래의 장점을 가진다.

 

① training data D_S와 test data(target)이 disjoint

→ 예측하고자 하는 것은 Figure 2의 ?로 표현된 곳들이다. 각각의 +, -로 표현된 정보들(D_S)을 학습하여 나머지를 예측하기 때문에, 위에서 언급한 예측의 대상을 negative feedback이라 정해놓고 학습해버리는 문제를 해결할 수 있다.

② implicit feedback이 관측되지 않은 아이템에 대해서도 training data가 생성되는데, 이는 기존의 방식처럼 가정하거나 무작위로 선정하는 방식이 아닌 실제 관측에 근거한 데이터이다.

 

특정 유저 u의 아이템 간 선호 연산 >u은 위의 3가지 성질을 만족하기 때문에, 모든 유저에 대해 I*I martix의 ?들이 모두 채워진다면, 각 유저별 personalized ranking을 구할 수 있게 된다.

4. Bayesian Personalized Ranking(BPR)

4.1 BPR Optimization Criterion

Θ는 모델 파라미터를 의미하고, MF를 포함한 여러 모델이 사용될 수 있다. 정확한 personalized ranking을 찾는 것은 곧 위 좌측 수식의 사후 확률을 최대로 하는 Θ를 찾는 것이고, 이는 Bayesian formula에 의하면 우측의 수식과 같다. 우측 수식의 2가지 term을 각각 살펴보자.

먼저 첫 번째 term을 살펴보면 각 pair의 아이템에 대한 유저의 선호 여부가 독립적이라고 가정하면 위의 수식을 만족하게 되고, 모든 (u,i,j)의 값은 D_S에 속하거나 속하지 않기 때문에 아래와 같이 정리할 수 있다.

파이의 안쪽 수식은 다시 아래와 같이 생각할 수 있는데, 이때 sigmoid 안쪽의 term은 어떤 모델을 사용하느냐에 따라 그 수식 형태가 달라지게 된다.

MF 모델을 사용한다고 가정한다면, 유저 u가 아이템 i보다 아이템 j를 선호할 확률의 예측값 x_uij hat의 값은 아래와 같은 산식으로 구할 수 있을 것이다.

두 번째 term인 p(Θ)은 평균이 0인 정규분포를 따를 것이라 가정하였다고 한다.

이렇게 가정하여 수식을 정리해보면 람다의 값은 regularization parameters다.

4.2 BPR Learning Algorithm

 

Adam이 등장하기 이전의 논문이라 full gradient decent와 SGD에 대해서만 논한다. full gradient decent와 SGD 모두 BPR-OPT의 학습 방식으로는 문제가 있다. training triples 내에 하나의 유저 u와 선호 아이템 i의 쌍 (u, i)에 대해 너무 많은 (u,i,j)가 존재할 것이기 때문에(유저와의 interaction이 관측된 아이템보다 그렇지 않은 아이템이 훨씬 많을 것이다.) 이러한 training pairs의 skewness로 인해 전체를 학습하든 그 중 일부를 학습하든 간에 poor convergence를 보일 것이라는 것이 논문의 주장이다.

 

이를 해결하기 위해 저자는 training triples에서 중복을 허용해 ramdom sampling을 반복하는 bootstrap 기법을 적용한 SGD를 사용했으며, 아래와 같이 SGD에 비해 우수한 성능을 보였다고 주장한다.

이후 내용은 MF와 kNN 모델 사용시 BPR의 학습 적용 방법, WR-MF와 MMMF와의 비교 등을 다루는데, 크게 의미있다고 생각하지 않아 생략한다. 뭐 당연히 그렇겠지만, 더 우수한 성능을 보였다고 한다.

personalized ranking을 측정하는 다른 지표인 NDCG와 비교했을 때 구체적으로 어떤 차이가 있고, 얼마나 현재에도 활용 가치가 있는지는 더 공부해 볼 필요가 있어보인다.

 

[느낀점 / 소감]

 

1. MLE(최대 가능도 추정), MAP(최대 사후 확률 추정) 등 통계적 기법에 대한 이해가 부족하다.

2. 딥러닝이 힘을 얻기 시작한 2010년대 중반 이전의 기법들이 지금의 관점에서 어떤 의미를 가지며, 어떤 것들이 살아남고 살아남지 못했는지 이해하고 받아들이는 것이 중요할 것 같다.

3. 대충 봐도 읽고 이해하는 거랑 구현하는 것은 너무 갭이 크다,,