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

Myeonghyeon Ryu·2022년 10월 11일

논문리뷰

목록 보기

2/5

BPR: Bayesian Personalized Ranking from Implicit Feedback

Abstract

본 논문은 클릭, 구매와 같은 implicit feedback를 이용한다.
implicit을 최적화하는 방법으론 matrix factorization 또는 kNN등이 있지만 얘넨 랭킹을 최적화 할 순 없다.
그래서 우린 BPR-OPT라는 것을 제시해 ranking을 반영할 수 있도록 했다.
추가로 이것들을 MF와 kNN에 적용해 기존보다 더 나은 결과를 얻을 수 있었다.

Introduction

추천 분야의 데이터는 주로 explicit data와 implicit data로 나뉜다.

본 논문은 수집하기 쉬운 implicit data를 이용해 personalized ranking을 구하는 방법을 제시할 것이며 contribution은 다음과 같다.

최적의 랭킹을 구하기 위해 maximum posterior estimator에서 파생된 최적화 기법인 BPT-Opt를 제시한다. 이것은 ROC 커브 아래의 면적 즉, AUC를 최대화하는 문제와 동일한 것을 보여준다.
BPT-Opt를 최대화하기 위해 LearnBPR 알고리즘을 제시한다. 이 것은 부트스트랩 샘플링을 사용하는 SGD기반으로 만들어졌다.
2가지 최신(2009년기준..) 추천 모델에 LearnBPR을 적용하는 법을 보여준다. (MF와 kNN)
BPR로 모델을 학습하는 것이 다른 학습 방법을 능가하는 것을 보여줌.

Personalized Ranking

implicit feedback 데이터는 긍정적인 값만 존재한다. 따라서 부정적인 값을 잘 고려하는 게 중요(유저가 진짜 관심이 없는건지 있지만 아직 존재여부를 모르는건지 구분이 안됨)

Formalization

$U$ 를 모든 사용자의 집합이라고 하고 $I$ 를 모든 item의 집합이라 하면 implicit feedback는 $S ⊆ U ×I$ 로 표현할 수 있으며 본 논문의 목표는 각 user별 personlized total ranking $⊂I^2$ 를 구하는 것이다.

$>_u$ 의 특성

Analysis of the problem setting

implicit feedback은 positive만 관측되며 남은 값은 알 수없다. 그래서 이 문제를 대처하기 위한 가장 흔히 사용되는게 모든 결측치를 무시하는 건데 이 경우 일반적인 머신러닝모델은 두 가지를 구별할 수 없기 때문에 학습이 불가능하다.

그래서 본 논문은 기존 결측치의 문제를 해결한 새로운 matrix를 제시한다.

이 maxtrix 세 가지 조건으로 완성된다.

관측되지 않은 item은 무조건 관측된 item보다 랭킹이 낮다.
관측된 item들 끼리는 랭킹 추론 불가능
관측되지 않은 item들 끼리는 랭킹 추론 불가능

이를 공식화하기 위해 우린 다음과 같은 $D_s$ 를 정의

이런 접근법에는 두 가지 이점이 존재한다고 한다.

1) 우리의 훈련데이터는 Positive & Negative Pair와 결측치로 구성됨

즉 (u, i, j) 형태로 구성되어 있기 때문에 기존에 관측되지 않은 데이터를 negative로 정해버리고 학습해버리는 문제를 해결할 수 있다.

2) 실제 관측된 데이터인 $D_s$ 를 훈련데이터셋으로 사용한다.

Bayesian Personalized Ranking (BPR)

이 section에서는 BPT-Opt을 이용해 랭킹 태스크를 해결하는 방법을 도출할 것이다.

BPR-Opt은 $p(i >_u j|Θ)$ 에 대한 우도함수와 모델 파라미터 $p(Θ)$ 에 대한 사전 확률을 사용한 베이시안 분석에서 파생됐다.
학습을 위한 LearnBPR 알고리즘을 제안하며 LearnBPR을 MF와 kNN에 어떻게 적용되는지 보여준다.

BPR Optimization Criterion

일반적인 Baysian optimization이란 사후확률을 최대화 시키는 모델 파라미터 $Θ$ 를 찾는 것이다.

유저의 선호정보 $>_u$ 가 주어졌을 때 이를 가장 잘 나타내는 파라미터 $Θ$ 를 추정하는 것.

모든 유저들은 서로 독립
특정 유저에 대한 모든 아이템 Pair가 다른 모든 Pair와 독립이라고 가정

따라서 $p(Θ| >u)$ 은 다음과 같이 진행된다.

단일 밀도의 곱으로 다시 쓸 수 있다.
모든 유저 $u ∈ U$ 에 대해 결합할 수 있다.

totality, antisymmetry의 특성으로 인해 다음과 같이 정리된다.

파이 안에 있는 유저가 아이템 j보다 i를 선호할 확률을 살펴보면

이와 같이 정의할 수 있다.

$\hat{x}_{uij} (Θ)$ : 유저 u, item i, j 사이의 관계
$σ$ : sigmoid

지금까지 우린 우도함수만을 논해왔다. 베이지안 모델링 접근법을 완성하기 위해 평균이 0이고 분산이 공분산 행렬 $Σ_Θ$ 인 정규분포를 사전 밀도 함수 $p(Θ)$ 에 적용했다.

$p(Θ) ∼ N(0, Σ_Θ)$

여기에 알 수 없는 하이퍼파라미터 수를 줄이기 위해 $Σ_Θ = λ_ΘI$ 로 설정.

이제 최종적으로 다음과 같이 공식화 할 수 있습니다.

Analogies to AUC optimization

BPR 스키마 공식을 이용해 BPR과 AUC 사이의 유사점을 쉽게(?) 이해할 수 있다.

보통 유저별 AUC는 다음과 같이 정의된다.

따라서 평균 AUC는 다음과 같다.

여기에 우리의 데이터셋을 사용한다면 다시 작성할 수 있다.

$z_u$ : 정규화 상수

마지막 식 $AUC(u)$ 를 살펴보면 본 논문의 BPR-OPT와 유사점이 있다.

둘은 손실 함수만 다르다.
- AUC는 미분할 수 없는 손실 함수 $δ(x > 0)$ 를 사용
- BPT-Opt는 미분 가능한 손실 함수 $ln \;σ(x)$ 를 사용

보통의 경우 AUC를 최적화하기 위해 미분 불가능한 함수인 heaviside함수를 대체하는 것이 일반적인데 보통 시그모이드 함수를 사용된다.

BPT Learning Algorithm

이제 BPT가 어떻게 학습되는지 알아보자.

본 논문의 모델은 미분이 가능하기 때문에 경사하강법 기반의 알고리즘이 최대화에 대한 적절한 선택이어야 하지만 우리가 풀어야하는 문제에 대한 올바른 선택이 아니다.

이를 위해 부트스트랩 샘플링을 사용하는 SGD기반의 LearnBPR 알고리즘을 제안한다.

모델 매개변수에 대한 BPR-OPT의 기울기는 다음과 같다.

우선 전체 경사하강법을 먼저 살펴보자. 각 단계에서 모든 훈련 데이터에 대한 전체 기울기가 계산된 다음 모델 매개변수가 learning rate로 업데이트 된다.

해당 방법의 문제점
- 학습 속도가 느리다.
- 우린 $D_s$ 안에 $O(|S||I|)$ training triples를 갖고 있기 때문에 모든 단계에서 Full gradient를 계산하는 것은 불가능하다.
- 훈련 pair의 Skewness 수렴을 안 좋은 쪽으로 이끈다.
- 발산될 가능성이 높기 때문에 매우 작은 learning rate를 설정해야됨.

다음으로 SGD를 살펴보자.

일반적으로 이것은 전체 경사하강법에 비해 Skew 문제에 대한 접근법이다. 그러나 통과되는 훈련 Pair의 순서가 중요하다.
item별로 또는 user별로 데이터를 탐색하는 일반적인 접근 방식은 동일한 user-item 쌍에 대한 연속적인 업데이트가 너무 많기 때문에 수렴이 좋지 않다. (user u와 item i쌍 하나가 있다면 (u, i, j)가 너무 많다는 걸 뜻하는 듯)
이 것을 해결하기 위해 무작위로 Triples를 선택하는 SGD 알고리즘 사용
- 이를 사용하면 동일한 user-item 쌍을 선택할 확률이 매우 적음
- bootstrap 샘플링 기법을 사용할 것이다. 중간에 그만 둘 수 있게

Bootstrap 샘플링 기법을 사용한 LearnBPR이 효과가 굉장했다.

Learning models with BPR

이번엔 MF와 kNN에 어떻게 BPR을 적용하여 학습시켰는지 살펴볼 것이다.

두 모델은 모두 아이템에 대한 유저의 숨겨진 선호도를 예측한다.

예측값은 유저-아이템 Pair $(u, l)$ 의 실수 $\hat{x}_{ul}$ 이다.

우리가 정의한 데이터셋은 $(u, i, j) ∈ D_s$ 기 때문에 추정량 $\hat{x}_{uij}$ 을 분해하여 다음과 같이 정의한다.

이를 통해 우린 $\hat{x}_{ul}$ 를 예측하는 모든 CF모델에 이를 적용할 수 있다.
우린 $\hat{x}_{ul}$ 을 회귀하는 것이 아닌 두 예측 $\hat{x}_{ui}-\hat{x}_{uj}$ 의 차이를 분류하려고 한다.

Matrix Factorization

$\hat{x}_{ui}$ 를 예측하는 문제는 Matrix $X : U \times I$ 를 추정하는 task로 볼 수 있다.

타겟 행렬 X는 두 개의 low-rank 행렬들 $(W : |U| × k \;\;\;\; H : |I| × k)$ 의 내적으로 근사된다.

k는 근사치의 차원 / 순위 이다.
W의 각 행 $w_u$ 는 사용자 u를 설명하는 특정 벡터로 볼 수 있으며 동일하게 H의 $h_i$ 는 항목 $i$ 를 설명합니다.
따라서 다음과 같이 쓸 수 있다.

MF의 모델 파라미터는 $Θ = (W, H)$ 이다.
모델 파라미터는 또한 관찰되지 않은 유저 취향과 아이템 속성들을 모델링하는 latent variables로 볼 수도 있다.

일반적으로 최소 제곱에 대한 $\hat{X}\; to\; X$ 의 최고의 근사치는 SVD를 이용하여 달성된다. 하지만 역시 오버피팅을 유발하기 때문에 많은 다른 MF 방법들이 제시됐다.

랭킹 task의 경우 BPR-OPT에 따라 최적화하며 우리가 제시한 알고리즘인 LearnBPR을 사용하여 더 좋은 성능을 달성하였다. 이를 위해선 각 파라미터에 대한 $\hat{x}_{uij}$ 의 미분값만 알면된다.

또한 세 개의 regularization 상수를 사용한다.
1. user features W에 대한 λW
2. item features H의 긍정적인 업데이트에 사용되는 λH+
3. item features H의 부정적인 업데이트에 사용되는 λH−

Adaptive k-Nearest-Neighbor

kNN은 매우 인기있는 CF이며 item은 item끼리, user는 user끼리의 유사성 측정을 위해 사용됩니다.

item-base가 더 좋은 결과를 제공하기 때문에 이를 이용해보겠다. 먼저 kNN 모델 식을 살펴보자.

$C: I \times I$ : 아이템 유사도 행렬
모델 파라미터 $Θ = C$

C를 선택하는 일반적인 접근 방식으론 heuristic similarity 척도를 적용하는 것이다. 예를 들어 코사인 유사도와 같은..

더 나은 전략은 유사성 척도 C를 학습하여 문제에 적용하는 것이다.

아이템 개수가 너무 많은 경우 행렬 H를 factorization하여 학습할 수도 있지만 우린 전부 직접 학습해볼 것이다.

역시 MF에서와 같이 BPR-OPT를 적용하고 LearnBPR알고리즘을 사용할 것이다. 모델 파라미터 $C$ 에 대한 $\hat{x}_{uij}$ 의 미분값을 살펴보자.

item i에 대해선 +1, item j에 대해선 -1 그리고 나머진 0으로 학습한다.

여기서 우린 두 개의 Regularization 상수를 가진다.
- $λ_+$ : $c_{il}$ 를 학습
- $λ_-$ : $c_{jl}$ 를 학습

Evaluation

Datasets

평가에는 사용자의 item 구매 내역이 포함된 Rossmann 데이터셋과 netflix의 DVD 대여 데이터셋을 사용했다.

Rossmann 데이터셋
- 4000 item에 대한 10000명의 user가 구매한 내역 포함
- 총 426,612개
- 사용자가 다음에 구매하기를 원하는 품목을 예측
Netflix 데이터셋
- 사용자의 explicit feedback이 포함된 데이터셋이다.
- 영화에 대한 사용자의 평점이 포함돼어 있다.
- implicit feedback 작업을 위해 평가 점수를 제거
- 10000명의 사용자와 565738개의 평가가 포함된 5000개의 item으로 구성됐다.
- 사용자가 영화를 평가할 가능성이 있는지 예측