---
lang: ja-jp
tags: Survey
title: Bayesian Personalized Ranking
---
# Bayesian Personalized Ranking
[Paper](https://arxiv.org/pdf/1205.2618.pdf)

- [Learning models with BPR](/w-xVxxFAS2K4bWEgzH5Fdg)

## Intro.
- **Implicit Feedback** : The non-observed user-item pairs are a mixture of real negative feedback and missing value.
- 負例についてのフィードバックが存在しない
- Matrix Factorization, kNNはPersonalized Rankingの問題設定に設計されているものの、ランキングそのものを最適化している訳ではない
- `BPR-Opt`と呼ばれる最適化基準を利用してPersonalized Ranking問題をランキングに最適化する
- `BPR-Opt`の枠組みにおいてモデルを最適化する手法について論じる
- SGDにより最適化できれば利用可能（論文ではMFとkNNを利用している）
- **Personalized Ranking** : One individual ranking per user
- ユーザにランク付けされたアイテムのリストを返す問題設定
- この論文ではオフラインな問題設定を扱う

## Terms
- Feedback : ユーザがアイテムに与える（明示的な）スコア・評価点数
- 食べログの5段階評価みたいなイメージ
- Implicit Feedback : 「ユーザが必ずしもアイテムを購入・使用したものの評価を与えているとは限らない」という状況で得られた評価の集合を意味する
- （食べログの例で言えば）お店にはいったもののサイトに点数を登録しない場合もあるよね、というイメージ
- Positive | Negative Feedback : 読んで字の如く「良い」と思ったか「悪い」と思ったか
- 1点だと悪くて5点だと良いみたいなイメージ

### BPR-Opt
- 事後確率分布においてランクが得られる確率を最大化する枠組み
- AUROC(Area under the ROC curve)を最適化している

### LearnBPR
- 学習データから**Training Triplet**をBooststrap sampling
- Stochastic Gradient Descentで最適化する枠組み
- `BPR-Opt`を最適化するにあたり通常のSGDを利用するよりも優れている

## Fomalization
- $U$ : ユーザ集合
- $I$ : アイテム集合
- $S \subseteq U \times I$ : ユーザのアイテムについてのImplicit Feedbackの行列（厳密には単に集合であり、行列ではないが。）
- $\gt_{u} \subset I^{2}$ : 全アイテムについてのユーザ個人$u$へのランキングで、以下のような性質を仮定する
- $\forall i, j \in I : i \neq j \Rightarrow i \gt_{u} j \lor j \gt_{u} i$
- アイテムが同じでなければ、何らかユーザはアイテムについての選好を持つ
- $\forall i, j \in I : i \gt_{u} j \land j \gt_{u} i \Rightarrow i = j$
- アイテムを比較した時に甲乙つけがたいケースはアイテムが同じ場合のみ
- $\forall i, j, k \in I :i \gt_{u} j \land j \gt_{u} k \Rightarrow i \gt_{u} k$
- アイテムの選好について、推移律が成り立つ
- $I_{u}^{+} := \{ i \in I : \left( u, i \right) \in S \}$
- あるユーザ$u$についてFeedbackが得られているアイテム集合
- ここでの$+$はPositiveという意味ではなく、**Explicit**に評価が得られたもの、という意味
- $U_{i}^{+} := \{ u \in U : \left( u, i \right) \in S \}$
- あるアイテム$i$についてFeedbackが得られているユーザ集合

## Problem Settings

* * *

（既存のMatrix Factorizationをランキング学習で利用しようと思った場合の問題点）

- $S$が持つ情報は上の図において$+$が埋まっている$u$と$i$の要素だけ
- `?`の要素はNegative Feedbackなのか、それともPositiveだがフィードバックが得られていないのかわからないもの
- 単純に$0$で埋めることは、全てNegativeなものとして扱うことを意味する
- この状況下でモデルを学習させると、フィードバックが得られているものに1を、得られていないものに0をラベルづけするような結果を得ることになる
- それゆえに正則化の手法が必要になる

というところまでが、普通の考え方で、BPRでは**トレーニングデータの作成方法に異なったアプローチを取る**。単に0-fillingして正則化する訳ではないのが特徴的。

### Create Training Data
- $(u, i) \in S$であれば、ユーザ$u$はこのアイテム$i$を他の全てのアイテムよりも選好するとみなす（仮定する）
- $(u, i_{1}) \in S \land (u, i_{2}) \in S$であれば、$i_{1}$と$i_{2}$についていかなる順序性の推論を行うことはない
- また、$(u, i_{3}) \notin S \land (u, i_{4}) \notin S$についても順序性の推論は行わない

上述の性質を満たすデータセット$D_{S} : U \times I \times I$を次のように定義する。

$$
D_{S} := \{ \left(u, i, j \right) | i \in I_{u}^{+} \land j \in I \setminus I_{u}^{+} \}
$$

「ユーザ$u$はアイテム$i$をアイテム$j$よりも選好する」という推察を束ねるイメージ。

1. 通常の問題設定では、アイテムどうしの比較結果がデータに含まれているわけではなかったが、このようにデータセットを作成すると、アイテムどうしのペアワイズな比較が得られる
- User-Item行列の要素を0埋めした場合には、明示的にユーザがそのアイテムに対してNegative Feedbackを与えたとして解釈されることになる。一方で、Item-Item行列として分解した場合、ユーザがそのアイテムにNegative Feedbackを与えるかどうかはわからないが、少なくともすでにPositive Feedbackが与えられているものよりは劣るものとして扱うことがになる。
2. ランキングそのものの問題設定を扱っていることになる


## Datasets & Evaluation

### Netflix
10000 users, 5000 items, 565738 rating actions
各ユーザが少なくとも10以上のアイテムにPositive Feedbackが与えられ、各アイテムが少なくとも10以上のユーザからPositive Feedbackを受けているようにデータセットをサンプリング

### Methodology
Leave-one-out交差検証法のスキーマを利用する。
各ユーザについて、ランダムに1つの動作を履歴から削除する。
$I_{u}^{+}$から各ユーザ$i$について1つの$i$をランダムに取り除いたということ。

取り除かれた$\left(u, i\right)$でテスト事例を作成する。$S_{\text{train}}$と$S_{\text{test}}$とそれぞれ呼ぶことにする。

$S_{\text{test}}$についてのAUCの平均を統計量としてモデルの評価を行う。

$$
\text{AUC} = \frac{1}{|U|} \sum_{u} \frac{1}{E\left(u\right)} \sum_{\left(i, j\right)E\left(u\right)} \delta\left(\hat{x}_{ui} \gt \hat{x}_{uj}\right)
$$

ただし、$E\left(u\right)$の定義は次の通り：

$$
E\left(u\right) := \{\left(i, j\right)\|\left(u,i\right) \in S_{\text{test}} \land \left(u, j\right) \notin \left(S_{\text{test}} \cup S_{\text{train}}\right)
$$

LOO Cross ValidationでSubsample集合から取り除かれた集合に含まれているものが、それ以外の残りのデータセットに対してどれほど正しく評価できたのかをAUCで表現する。

train/test分割を10回繰り返して評価を行った。ハイパーパラメータについては、最初の1回目のデータセットに対してチューニングを行い、以降は同じ値を利用した。

## Optimization Criterion
`BPR-Opt`の説明。ベイズの枠組みで考える。

- $p\left( i \gt_{u} j | \Theta \right)$ : 尤度
- $p\left( \Theta \right)$ : モデルパラメータの事前分布

事後確率と尤度・事前分布の間には、ベイズの定理から次のような関係性がある。

$$
p \left( \Theta | \gt_{u} \right) \propto p \left( \gt_{u} | \Theta \right) p \left( \Theta \right)
$$

これは一人のユーザ$u$について、選好が得られた時のモデルパラメータが得られる事後確率分布を表現している。ユーザは違いに独立に選好を表現するとし、あるユーザについてのアイテム間の選好関係$(i, j)$がどのような$i$と$j$についても独立に決まることを仮定すると、次が導出される。

$$
\prod_{u \in U} p \left( \gt_{u} | \Theta \right) = \prod_{\left( u, i, j \right) \in U \times I \times I} p \left(i \gt_{u} j | \Theta \right)^{\delta \left( \left( u, i, j \right) \in D_{S} \right)} \cdot \left( 1 - p \left( i \gt_{u} j | \Theta \right) \right)^{\delta \left( \left( u, i, j \right) \notin D_{S} \right)}
$$

$\delta$は引数の条件が真であれば$1$、そうでなければ$0$を返すような関数。ユーザのアイテムについての選好が$S$から定義されることを考えれば、次の関係も成立する。

$$
\prod_{u \in U} p\left( \gt_{u} | \Theta \right) = \prod_{\left( u, i, j \right) \in D_{S}} p \left(i \gt_{u} j | \Theta \right)
$$

ユーザ$u$のアイテム$i$と$j$に対する選好関係が成立する確率はシグモイド関数を利用してモデリングする。

$$p \left( i \gt_{u} j | \Theta \right) := \sigma \left( \hat{x}_{uij} \left( \Theta \right) \right)$$

モデルのパラメータ$\Theta$の事前分布については、平均が$0$、分散共分散行列が$\Sigma_{\Theta}$の多次元正規分布から得られると仮定する。

$$
p \left( \Theta \right) \sim N \left( 0, \Sigma_{\Theta} \right)
$$

この事前分布の分散共分散行列は未知である（ことが多い）ので、$\lambda_{\Theta}$というスカラーをハイパーパラメータとして$\Sigma_{\Theta} = \lambda_{\Theta}I$を設定する。

これらの設定から`BPR-Opt`は次のような基準として表現される。

$$
\begin{aligned} \text{BPR-Opt} :&=\ln p\left(\Theta |>_{u}\right) \\ &=\ln p\left(>_{u} | \Theta\right) p(\Theta) \\ &=\ln \prod_{(u, i, j) \in D_{S}} \sigma\left(\hat{x}_{u i j}\right) p(\Theta) \\ &=\sum_{(u, i, j) \in D_{S}} \ln \sigma\left(\hat{x}_{u i j}\right)+\ln p(\Theta) \\ &=\sum_{(u, i, j) \in D_{S}} \ln \sigma\left(\hat{x}_{u i j}\right)-\lambda_{\Theta}\|\Theta\|^{2} \end{aligned}
$$

最後の行への変換には、正規分布の確率密度関数について平均$0$を代入して、係数部分を適切に$\lambda_{\Theta}$に置き換えることで得られる。

### AUCとの関係性
ヒントはユーザ一人についてのAUCの計算式を導出すること。あとは$\delta$を$\sigma$に置き換えてやれば良い。

### BPR-Optに基づく学習方法
`BPR-Opt`は$\Theta$について微分可能であるので、偏微微分の結果を利用してSGDで最適化していく。

Triplet単位でモデルパラメータを最適化していく。

$$
\begin{aligned} \frac{\partial \text{BPR-Opt}}{\partial \Theta} &=\sum_{(u, i, j) \in D_{S}} \frac{\partial}{\partial \Theta} \ln \sigma\left(\hat{x}_{u i j}\right)-\lambda_{\Theta} \frac{\partial}{\partial \Theta}\|\Theta\|^{2} \\ & \propto \sum_{(u, i, j) \in D_{S}} \frac{-e^{-\hat{x}_{u i j}}}{1+e^{-\hat{x}_{u i j}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{u i j}-\lambda_{\Theta} \Theta \end{aligned}
$$

これだと最急降下法なので、SGDに改めると次のようになる。

$$
\Theta \leftarrow \Theta+\alpha\left(\frac{e^{-\hat{x}_{u i j}}}{1+e^{-\hat{x}_{u i j}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{u i j}+\lambda_{\Theta} \Theta\right)
$$

> In general this is a good approach for our skew problem but the order in which the training pairs are traversed is crucial. A typical approach that traverses the data item-wise or user-wise will lead to poor convergence as there are so many consecutive updates on the same user-item pair

という問題があるので、Tripletを一様分布からサンプリングする手段が考えられる。が、同じTripletを抽出してしまい、収束が遅くなる可能性があるので、Bootstrap samplingを使うことを提案している。

Booststrap Samplingについては[この記事](https://qiita.com/tjmnmn/items/3aed6fb85f75446f74ca)を参考にすれば良い。

SGDの1ステップのたびに一様分布からサンプリングするのではなく、複数ステップをまとめてBootstrapによってTripletをサンプリングするということ。以下のように、Rossmannデータセットでは普通のSGDを利用するよりも収束が速いことがわかっているらしい。