BPR: Bayesian Personalized Ranking from Implicit Feedback은 Model-based Collaborative Filtering의 하나로,
Implicit Feedback 데이터를 활용해 Matrix Factorization를 학습할 수 있는 방법이다.
Bayesian 추론에 기반하고 있으며, Implicit data를 사용해 서로 다른 아이템에 대한 유저의 선호도를 반영하도록 모델링하고 추천하게 된다. 본 논문에서 추천이란, user가 선호할 만한 item 목록 (Personalized Ranking)를 예측하는 것을 말한다.
Personalized Ranking의 대표적인 방법으로는 Matrix Factorization과 k-Nearest Neighbor이 있다. 기존 방식에서는 모두 ranking은 고려하지 않는 방식이지만, 본 논문에서는 Bayesian 추론에 기반하여 BPR optimization을 제시하여 item에 대한 user의 선호도의 정도를 반영할 수 있게 한다.
1. Personalized Ranking
- Implicit Feedback의 문제점
1) 관측된 데이터만 존재함 / 부정적인 선호도의 데이터가 관측되지 않음
2) 관측되지 않은 데이터에 대해서는 실제로 user의 선호도가 어떤지 구분이 되지 않음
----> real negative feedback, missing value 둘다 고려하여 모델링
----> user의 item에 대한 선호도 랭킹을 생성 : MF 학습데이터로 사용
2. hypothesis
- 관측된 아이템을 관측되지 않은 아이템보다 선호한다.
- 관측된 아이템끼리, 관측되지 않은 아이템끼리는 선호도를 추론할 수 없다.
----> 관측되지 않은 아이템에 대해서도 정보(선호도)를 부여해서 학습하게 됨 : ranking 가능
3. Problem Analysis
위의 왼쪽 이미지에서 관측된 값은 +, 관측되지 않은 값은 ?이다. 이를 오른쪽 그림과 같이 +는 1, ?를 0으로 채웠다.
위와 같은 기존의 방식에서는 missing value을 negative feedback으로 간주한다. 즉, 관측되지 않아 비어있는 값을 0으로 채워넣어 사용했다는 것이다. 이럴 경우 미래에 user가 선호할 수 있을 가능성까지 무시한 것으로 볼 수 있어서 예측이 부정확해질 가능성이 있게 된다.
위와 같은 문제점에 대해 본 논문에서는 Personalized Total Ranking을 사용해 missing 데이터를 상대적인 값으로 채워넣는 방식을 제시한다. 전체 user에 대해서는 관측되지 않은 값일지라도 user 각각에 대해 Personalized Total Ranking을 사용하면 상대적인 선호도의 순서를 사용해 어느정도의 값들을 채워넣을 수 있다. 이렇게 생성된 user 각각의 user-item matrix에서 전체 embedding 데이터의 missing 데이터를 간접적으로 학습시킬 수 있도록 한다.
4. Train Dataset
모든 user와 item의 집단을 각각 U와 I라고 할 때, 관측 가능한 모든 user, item 쌍
Personalized Total Ranking(>_u)은 해당 user가 선호하는 item의 집단에 대하여 예측된 선호도 순서를 말한다. Personalized Total Ranking는 두 개의 item에 대한 선호도의 상대적 순서를 나타내므로, 개수는 전체 item 집단의 수에서 2개를 선택하는 조합의 수와 같다. 또, 다음과 같은 속성을 만족한다.
item 간의 순서를 정의하기 위한 조건이며, 집합적인 성격을 가지게 된다.
user u가 선호하는 아이템들의 집합을 I_u+라고 할때, 학습데이터는 다음과 같다.
5. Bayesian Personalized Ranking : BPR
위에서 정의된 Ds에 Bayesian 추론을 적용한다. 우선 Bayesian 추론은 사후확률(posterior)을 최대화하는 파라미터 Θ를 찾는 것이 목표이며, 이를 Maximum A Posterior (MAP : 최대사후확률추정)이라고 한다.
사후확률을 최대화한다는 것은 주어진 user의 선호도 정보(>_u)를 최대한 잘 나타내는 파라미터 Θ를 추정하는 것이다.
- likelihood
여기서 likelihood는 >_u에 대한 확률 분포이며, >_u를 (u,i,j)∈Ds로 정의할때, i와 j에 대한 경우 두 가지 경우가 존재하므로 베르누이 분포를 따른다고 할 수 있다. 이때 user가 서로 독립임을 가정하면 iid가 만족되므로 다음과 같이 표현할 수 있다.
또, user가 item j보다 item i를 선호할 확률은 아래와 같이 정의된다.
따라서 모든 user의 >_u에 대한 likelihood는 다음과 같다.
- prior
사전확률은 파라미터 Θ에 대한 확률분포를 가정한다. 특별한 사전 정보가 없으면 일반적으로 uniform이나, normal을 사용한다. 본 논문에서는 normal을 사용한다.
- BPR-OPT
앞서 계산한 prior(사전확률)과 likelihood를 사용하여 BPR-OPT을 구한다. 이때 학습 파라미터가 되는 Θ는 아래와 같다.
- Learning Algorithm
목적함수인 BPR-OPT는 미분 가능하므로 Gradient Descent를 통해 학습하게 된다. BPR-OPT을 Θ에 대해 미분하면 아래와 같이 정의된다.
그러나 일반적인 Gradient Descent 방법은 적절한 학습 방법이 아니다.
일반적인 GD를 사용하게 되면,
1) 보통 선호도를 알고 있는 item i 보다 선호도를 모르는 j가 많기 때문에 학습 데이터 상에서 비대칭이 발생하게 되며,
2) 상대적으로 수가 많은 user u와 item i에 대해 계속 업데이트가 iteration이 돌며 계속해서 업데이트가 되므로 학습과정이 수렴되지가 않게 된다.
그렇기 때문에 triples {u,i,j} 단위로 랜덤샘플링하는 bootstrap 기반의 SGD를 사용하게 된다면,
1) item i와 item j가 랜덤하게 페어가 되므로 비대칭을 해소할 수 있고,
2) 학습과정에서 동일한 user와 item i가 연속해서 등장하지 않게 되므로 학습이 원할해진다.
따라서, 이를 MF 모델에 적용해보면,
위와 같은 Gradient를 업데이트함으로써 학습하게 된다.
6. Conclusion
1) Implicit Feedback 데이터만을 활용해 user를 기준으로 item 간의 선호도 도출한다.
2) MAP(Maximum A Posterior) 방법을 통해 파라미터 Θ를 최적화한다.
3) BPR-OPT를 Bootstrap 기반의 SGD를 활용해 파라미터를 업데이트한다. -> LEARNBPR
4) MF(Matrix Factorization)에 BPR Optimization을 적용한 결과 우수한 성능을 보였다.