위 논문에서는 ‘click’이나 ‘purchase’와 같은 implicit-feedback 하에서의 추천 문제를 다루고 있다. 기존의 Matrix Factorization(MF)나 K-Nearest-Neighbor(KNN)와 같은 아이템 추천 기법들이 있지만 랭킹 최적화(optimization)에 직접 사용할 수는 없다. 따라서 위 논문은 베이지안 추론에 기반한 최적화 (optimization) 기법인 BPR-Opt를 제시하여 아이템들에 대한 사용자의 선호 정도를 반영할 수 있도록 하였다.
Contents recommendation은 많은 정보 시스템에서 중요한 task로 온라인 쇼핑 웹사이트에서는 개별 고객들에게 개인 맞춤형 상품 추천을 제공할 수 있으며 은행이나 증권사들의 입장에서는 고객들에게 맞춤 금융 상품이나 서비스 등을 제공할 수 있도록 하는 효과를 가지고 있다. Individualization은 이처럼 product recommendation 및 contents를 제공하는 입장에서 매우 중요한 요소라고 할 수 있다. 위 논문에서는 item recommendation에 초점을 맞추어 사용자의 과거 interaction과 시스템을 이용하여 사용자 별 아이템 집합 랭킹을 만들고자 하였다. 실제 데이터들에서는 피드백의 대부분이 사용자가 명시적으로 관심은 표현하지 않아도 되는 implicit 형태(클릭 수, 조회 시간, 구매 여부)이기 때문에 수집에 있어 explicit 데이터와 비교하였을 때 훨씬 더 쉽다.
개인화 랭킹 task는 rank가 등록된 아이템 리스트를 사용자에게 제공하는 것으로 위 논문에서는 랭킹이 사용자들의 implicit 정보들을 통하여 추론할 수 있을 것이라고 가정하였다. Implicit 피드백은 positive한 정보만이 관측이 가능하며 관찰되지 않은 사용자-아이템 pair는 negative 피드백과 결측치(missing value)의 혼합물로 이루어져 있다.
Formalization
이때 관측 가능한 모든 (user,item)쌍 $s \in S$는 $S⊆U\times I$ 와 같이 표현이 가능하다. 위 논문에서는 각 사용자들의 personalized total ranking($>_u ⊂ I^2$)를 구하는 것으로 personalized total ranking은 다음과 같은 의미를 갖는다.
ex) personalized total ranking$(>_u ⊂ I^2)$의 의미
5개의 아이템 집단 $I =$ {$I_1, I_2, I_3, I_4, I_5$}이 있을 때 사용자가 선호할만한 아이템을 순서대로 예측한 것으로 선호 정도의 순위가 $I_4, I_1, I_3, I_5, I_2$와 같을 때, $I_4>_uI_1>_uI_3>_uI_5>_uI_4>_uI_2$와 같이 표현할 수 있으며 $I_4>_uI_3>_u$는 $>_u⊂I^2$의 하나의 예가 된다.($>_u는 {5}\mathrm{C}{2} = 10$개 만큼 존재)
$>_u$의 속성
위의 속성들은 아이템간의 order를 정의하기 위한 조건으로, antisymmetry는 어떤 사용자가 $item_i$를 $item_j$보다 선호함과 동시에 $item_j$를 $item_i$ 보다 선호한다면 두 $item$은 서로 같다는 것을 의미한다.
Analysis of the problem setting
implicit 피드백 시스템은 positive 한 정보만이 관측되기 때문에 결측값을 모두 negative하다고 가정하였기 때문에 사용자가 향후 선호할지 여부에 관계없이 모두 무시된다. 따라서 위 논문에서는 이러한 문제를 해결하기 위하여 다음과 같은 design matrix를 제시하였다.
위 matrix에서 사용자(user)는 관측된 아이템(item)들에 대해서 관측되지 않은 모든 아이템들보다 더 선호하며 관측된 아이템들 중에서는 선호 정도를 추론할 수 없다. 마찬가지로 관측되지 않은 아이템들에 대해서도 선호 정도를 추론할 수 없다.
$$ D_s := \left\{ (u,i,j)|i\in I^+_u \land j \in I \backslash I^+_u \right\} $$
사용자가 선호하는 아이템 집단의 훈련 데이터 $D_s:U \times I \times I$ 는 다음과 같으며 여기서 $(u,i,j) \in D_s$의 의미는 사용자 $u$ 가 사용자 $j$보다 $i$를 선호한다고 가정하는 것이며, $>_u$이 반대칭(Antisymmetric)이기 때문에, Negative인 경우는 implicit 케이스로 가정한다.
다음과 같은 접근법의 장점
BPR Optimization Criterion
사후 확률 추정(Maximum Posterior Estimation)은 사후 확률을 최대화 하는 파라미터($\theta)$를 찾는 것이며 다름과 같이 표현할 수 있다.
$$ p(\Theta|>_u) \propto p(>_u|\Theta)p(\Theta) \\ \because p(\Theta|>u)=\frac{p(\Theta\gamma >_u)}{p(>_u)}=\frac{p(>_u| \Theta)p(\Theta)}{p(>_u)} \propto p(>_u| \Theta)p(\Theta) $$
$\Theta$는 임의의 모델 클래스 파라미터 벡터이며 $>_u$는 사용자 $u$에 대한 잠재 선호도 구조를 의미한다. 여기서의 사후 확률은 사용자의 선호 정보$(>_u)$를 의미하며 사전 확률은 $p(\Theta)$로 파라미터에 대한 사전 정보이다. 사후 확률은 베이즈 정리에 의해 likelihood와 사전 확률의 곱으로 나타낼 수 있으며 각각 다음과 같이 정의할 수 있다.
Likelihood
BPR Optimization에서 likelihood는 $>_u$에 대한 확률 분포를 의미하며 $>_u$를 $(u, i, j) \in D_s$로 정의했을 때, $i>_u j$와 $j>_ui$ 두가지 경우만 존재하기 때문에 베르누이(bernoulli)분포를 따른다고 볼 수 있다. 모든 사용자들이 서로 독립이라고 가정하면 다음과 같이 표현이 가능하다.
$$
_u := (u, i, j) \in D_s \Rightarrow \delta((u, i, j) \in D_s) \overset{\underset{\mathrm{iid}}{}}{\sim} B(1, p(i >_u j))\\ where, \delta((u, i, j) \in D_s := \begin{cases} 1 \;\; if \;\; (u, i, j) \in D_s \\\\ 0 \;\; if \;\;(u, i, j) \notin D_s \end{cases} $$
베르누이(bernoulli) 분포의 likelihood function은 다음과 같다.
$$ p(>_u|\Theta)=p(i>_u j)^{\delta(u, i, j) \in D_s}(1-p(i>_uj))^{\delta((u, i, j) \notin D_s)} $$
$p(i>_uj)$를 사용자가 $item_i$보다 $item_j$를 선호할 확률이라고 할 때 다음과 같이 표현이 가능하다.
$$ \sigma :sigmoid \\ p(i>u j) := \sigma(\hat{x}{ij}), \sigma(x):=\frac{1}{1+e^{-x}} $$
모든 사용자들은 $iid$이기 때문에 모든 사용자들에 대한 likelihood function은 다음과 같다.
$$ \prod_{u \in U}p(>u|\Theta) = \prod{(u,i,j) \in D_x} p(ii>uj|\Theta) = \\\;\;\;\;\;\;\;\;\;\;\;\;\; \prod{(u,i,j) \in D_s} p(i>_uj)^{\delta((u,i,j) \in D_s)} (1-p(i>_uj))^{\delta((u,i,j) \notin D_s)} $$
사전 확률(Prior Probability)
사전 확률은 파라미터 $\Theta$에 대한 확률 분포를 가정하는 것으로 여기서는 normal distribution을 사용하였다.
$$ p(\Theta) \sim N(0, \lambda_{\Theta}I) \\ N(\Theta|\mu, \Sigma)=\frac{1}{(2\pi)^{d/2}|\Sigma|^{1/2}}exp(-\frac{1}{2}(\Theta-\mu)^T\Sigma^{-1}(\Theta-\mu)) \\ \propto exp(-\frac{1}{2}\Theta^T(\frac{1}{\lambda_\Theta}I)\Theta) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\ \;\;\; = exp(-\frac{1}{2\lambda_\Theta}\Theta^T\Theta \simeq exp(-\lambda_\Theta||\Theta||^2) $$
BPR-Opt
사후 확률을 최대화 하는 $\Theta$는 다음과 같이 구할 수 있다.
$$ BPR-Opt : argmax_\Theta p(\Theta|>_u) $$
Matrix Factorization에서 사용자와 아이템의 잠재 벡터를 예측하기 위하여 $p_u$와 $q_i$를 파라미터로 하고 사용자와 $item_i$, $item_j$ 사이의 관계인 $\hat{x}{uij}$는 사용자의 $item_i$에 대한 점수인 $\hat{x}{ui}$와 $item_j$에 대한 점수인 $\hat{x}_{uj}$의 차이로 정의된다. 이 차이가 클수록 $p(i>uj):=\sigma(\hat{x}{uij})$가 1에 가까워진다.
이를 바탕으로 하는 optimization function은 다음과 같다
$logp(\Theta|>_u)=logp(>_u|Theta)p(\Theta)$
$= log(\prod_{(u,i,j) \in D_x} \sigma(\hat{x}_{uij})p(\Theta))$
$= \sum_{u,i,j} log \sigma(\hat{x}_{uij}+logp(\Theta)$
$= \sum_{u,i,j} log\sigma(\hat{x}_{ui}-\hat{x}_{uj})-\lambda_\Theta||\Theta||^2$
$= \sum _{u,i,j}log\sigma(p_uq_i^T-p_uq_j^T)-\lambda_\Theta||p_u||^2-\lambda_\Theta||q_i||^2-\lambda_\Theta||q_j||^2$
$= \sum_{u,i,j} log(\frac{1}{1+e^{-(p_uq_i^T-p_uq_j^T)}}-\lambda_\Theta||p_u||^2-\lambda_\Theta||q_i||^2-\lambda_\Theta||q_j||^2$
BPR Learning Algorithm
gradient descent를 사용하여 파라미터 $\Theta$를 업데이트를 진행
$$ \Theta \leftarrow \Theta-\alpha\frac{\partial logp(\Theta|>_u)}{\partial \Theta} $$
$p_u$ 업데이트
$\frac{\partial logp(\Theta|>u)}{\partial p_u} = \frac{\partial log \sigma(\hat{x}{uij})}{\partial p_u} - \frac{\partial}{\partial p_u}(\lambda_\Theta||p_u||^2)$
$= \frac{\partial log \sigma(\hat{x}_{uij})}{\partial \hat{x}_{uij}}\frac{\partial\hat{x}_{uij}}{\partial\hat{x}_{uij}}\frac{\partial \hat{x}_{uij}}{\partial p_u} - \frac{\partial}{\partial p_u} (\lambda_\Theta||p_u||^2)$
$= \frac{1}{1+e^{p_uq_i^T-p_uq_j^T}}(q_i-q_j)-2\lambda_{p_u}p_u$
$q_i$ 업데이트
$\frac{\partial logp(\Theta|>u)}{\partial q_i} = \frac{\partial log \sigma(\hat{x}{uij})}{\partial q_i} - \frac{\partial}{\partial q_i}(\lambda_\Theta||q_i||^2)$
$= \frac{\partial log \sigma(\hat{x}_{uij})}{\partial \hat{x}_{uij}}\frac{\partial\hat{x}_{uij}}{\partial\hat{x}_{uij}}\frac{\partial \hat{x}_{uij}}{\partial q_i} - \frac{\partial}{\partial q_i} (\lambda_\Theta||q_i||^2)$
$= \frac{1}{1+e^{p_uq_i^T-p_uq_j^T}}(p_u)-2\lambda_{q_i}q_i$
$q_j$업데이트
$\frac{\partial logp(\Theta|>u)}{\partial q_j} = \frac{\partial log \sigma(\hat{x}{uij})}{\partial q_j} - \frac{\partial}{\partial q_j}(\lambda_\Theta||q_j||^2)$
$= \frac{\partial log \sigma(\hat{x}_{uij})}{\partial \hat{x}_{uij}}\frac{\partial\hat{x}_{uij}}{\partial\hat{x}_{uij}}\frac{\partial \hat{x}_{uij}}{\partial q_j} - \frac{\partial}{\partial q_j} (\lambda_\Theta||q_j||^2)$
$= \frac{1}{1+e^{p_uq_i^T-p_uq_j^T}}(-p_u)-2\lambda_{q_j}q_j$
위 논문에서는 personalized ranking의 최적화를 기법을 제안하였다. BPR-Opt를 최적화 기준으로 하여 베이지안 문제 분석을 통하여 최대 사후 확률을 추정하였다. bootstrap sampling을 통한 stochastic gradient descent를 사용하여 파라미터를 업데이트 하였으며 그 결과 기존의 optimization 기법들과 비교하여 더 우수한 성능을 보이는 것을 확인할 수 있었고 이러한 결과들을 통하여 BPR-Opt 기법이 personalized ranking task에 적절한 방법이라는 것을 알 수 있었다.