Bayesian Personalized Rankingとは
第2回と第3回で説明した行列分解の方法（SVD、WMF）は行列\(R\)の近似を直接見つけにいく手法でした。これらのアプローチでは、接触のない組み合わせ\(R_{ui}=0\)について \(\vec{p}_u \cdot \vec{q}_i\)で近似した時の精度が低すぎても高すぎても良い推薦結果とならず、ちょうどバランス良い精度で近似する必要がありました。これは「接触がない」ということが必ずしも「対象のアイテムがユーザーにとって興味がない」ということを意味していないためです。
今回紹介するBayesian personalized ranking（BPR）では、\(R_{ui}\)が0や1を取るのは、そのユーザーにとってのアイテムに対する興味の順序関係を示唆しているだけで、予測値が精緻に0や1になるように予測することを考えない、という違った見方をします。すなわち、ユーザー\(u\)を固定した時、あるアイテム\(i\)については\(R_{ui} = 1\)であり、また別アイテム\(j\)については\(R_{uj}=0\)となっているのは、ユーザー \(u\)にとってはアイテム \(i\) が \(j\) より重要であったからだ、と考えます。このことをアイテムの比較の記号 \(>_u\) を使って \(i >_u j\)と書くことにします。
例として、行がユーザー、列がアイテムに対応する接触履歴の行列 \(R\) が、
\[ R = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ & \cdots & \end{array}\right) \]
と与えられた場合、BPRで\(R\)を以下のように読み替えます:- ユーザー1はアイテム1をアイテム2より好む：\(1 >_1 2\)
- ユーザー1はアイテム1をアイテム3より好む：\(1 >_1 3\)
- ユーザー1がアイテム2とアイテム3のどちらをより好むかは未知（これを決定して推薦する必要がある）
- ユーザー2はアイテム1をアイテム3より好む：\(1 >_2 3\)
- ユーザー2はアイテム2をアイテム3より好む：\(2 >_2 3\) ...
その上で、より好むアイテムの方が、そうでないアイテムよりもユーザー／アイテムのベクトルの内積が大きくなる確率モデルを考えることが、BPRの考え方の基本となります。具体的には、ユーザー\(u\)に対する2つのアイテム\(i,j\)の好みについて\(i>_u j\)（つまりアイテム\(j\)より\(i\)の方を好む）という関係が成り立つかどうかの確率\(p(i>_u j)\)が、次のように\(\vec{p}_u, \vec{q}_i, \vec{q}_j\)の3つのベクトルを用いて、求められると考えます。
\[ p(i>_u j) = \sigma(s_{ui} - s_{uj})= \sigma( \vec{p_u}\cdot\vec{q}_i - \vec{p_u}\cdot\vec{q}_j) \]
ここで\(\sigma\)はシグモイド関数であり、\(s_{ui} - s_{uj}\)の値が正に大きいほど確率は1に近づき、負に大きいほど確率は0に近づきます。つまりアイテム\(j\)より\(i\)のスコアが大きいほどこの確率値が1となります。このようにBPRはSVD、WMFが1人のユーザーと1つのアイテムの関係からベクトルを構成するのとは異なり、1人のユーザーと、そのユーザが接触したアイテム、接触しなかったアイテムの3つ組の関係からベクトルを再構成するスタンスをとります。
この前提から、BPRの場合の誤差関数は、実際に\(i >_u j\)が観測されている組み合わせについての対数尤度\(\log p(i>_u j)\)を大きくするという方針に基づいて、
\[ L_{\mathrm{BPR}} = - \sum_{u} \sum_{i \in I_u ^+} \sum_{j \in I_u ^-}\log \sigma( s_{ui} - s_{uj} ) + \frac{\lambda_{\mathrm{user}}}{2} \sum_{u=1} ^U | \vec{p}_u | ^ 2 + \frac{\lambda _{\mathrm{item}}}{2}\sum_{i=1} ^I |\vec{q}_i|^2 \]
と書かれます。ここで、\(I _u ^+\) はユーザ\(u\)に対して \(R_{ui}=1\) となる \(i\) の集合（つまりユーザー\(u\)が接触したアイテムの集合）、\(I _u ^-\) は \(R_{uj}=0\) となる集合（ユーザー\(u\) が接触しなかったアイテムの集合）をそれぞれ表します。そのため、\(\sum_{i \in I_u ^+} \sum_{j \in I_u ^-}\) は \(i >_u j\) となる全ての組み合わせ \((i,j)\) についての和になります。第2項・第3項は正則化のために導入されるものです。
\(P\), \(Q\)の導出
\(L_{\mathrm{BPR}}\)の最小化は\(L_{\mathrm{WMF}}\)のそれよりも複雑になります。というのも、\(u\) を固定する時、\(L_{\mathrm{BPR}}\)の第1項に存在する和\(\sum_{i \in I_u ^+} \sum_{j \in I_u ^-}\)は \(N_u \times (I - N_u)\)項の足し合わせたものになっています。\(N_u = |I^+_u|\)は\(u\)の接触済みアイテム数です。多くの場合、各ユーザーが接触したアイテム数は全アイテムのごく一部に限られることから\(I\gg N_u\)となるので、和の組み合わせはほぼ\(N_u I\)個となります。ここから全ユーザー\(u\)で和を取ると、組み合わせ数は \((\sum_u N_u) \times I = \mathrm{NNZ} \times I\)となります。ここで、\(\mathrm{NNZ}\)は\(R\)の非ゼロ要素数、すなわち全接触数となります。
この和の計算に必要な計算量は\(O(\mathrm{NNZ} \times I)\)であって、最適なパラメータを得るためにはこの計算を反復させる必要があり、非常に時間がかかります。そこで、原論文では確率的勾配降下法（以下、SGD）を用いた最適化が提案されています。この方法では、和\(\sum_u \sum_{i \in I_u ^+} \sum_{j \in I_u ^-} \log \sigma(s_{ui} - s_{uj})\)を計算する代わりに、
- \(R_{ui} = 1\)となる\((u, i)\)をランダムに抽出する
- 1.の\((u, i)\)に対して、\(j_{s} \in I_u ^-\) をランダムに抽出する。これを負例サンプリング（negative sampling）という。
- \(L _ {\mathrm{BPR}}\)を (定数) \( \times \log \sigma(s _ {ui} - s _ {uj})\)と近似する。
- 3.の勾配に基づいて\(\vec{p}\), \(\vec{q}\)を更新
という近似を行います。なお、多くの実装では、全てのユーザーについて必ずパラメータを更新したい、という目的のため、1.でランダム抽出は行わず、\(R_{ui}\)で接触のあった\(R_{ui}=1\)となるユーザー／アイテムの組み合わせを順番に選び出すロジックになっています。
このようにSGDの実装にはさまざまなバリエーションがありますが、パラメータ更新の対象が抽出されたユーザー／アイテムに限定されることから、SGDによる最適化は理論上の計算量オーダーがWMFよりも少ないという利点があります。その一方で、SGDを採用することによってチューニングが必要なパラメータが新たに導入されるため、パラメータの数がWMFと比較して増加します。\(L_{\mathrm{BPR}}\)に存在するパラメータ\(n\),\(\lambda_{\mathrm{user}}\),\(\lambda_{\mathrm{item}}\)に加えてSGDに関連するパラメータの探索も必要となり、探索対象が広くなるため、optunaなどのフレームワークによる最適化にはある程度の試行回数が必要です。このため、例えば近年の網羅的なサーベイでは、全体としての精度はWMFに見劣りするようです。
BPRと関連する手法
BPRが実施するのと同様に、負例サンプリングとSGDによるパラメータ更新を用いて行列分解を計算する方法には、他にも以下のようなバリエーションがあります。
-
WARP （Weighted Approximate-Rank Pairwise）：WARPはBPRとは独立した文脈で導入された手法ですが、負例サンプリングとSGDによるパラメータ更新という点では同じものです。ただし、以下の二つの工夫を負例サンプリングとSGD更新について施しており、より効率的な学習ができる（場合がある）と期待されます。
- \((u,i) \in I_u^+\) に対して\(j_{s} \in I_u ^-\) を負例サンプリングする際、\(I_u^-\)から完全にランダムにサンプルするのではなく、ある程度「惜しい」アイテムのみを有効な負例と認める。ここでアイテム\(j\)が「惜しい」とは、\(s_{ui} - s_{uj} < 1\)、すなわち\(i\)に対するスコア差が1未満であると定義されます。
- 負例に対するスコア値\(\left\{s_{uj}\right\}_{j \in I_u^-}\)と比較して、より後ろに来てしまう\((u,i)\)ほどSGDの更新を強くする。これは「多くの負例アイテムに負けてしまう、弱い正例ほどなるべく強く救済する」という意味合いを持ちます。
-
SGD-MF：2020年に出た論文です。この論文で強力なベースラインとして紹介されたのは、BPRとよく似た以下のような最適化手続きで行列分解を行うモデルです。
- 正例 \((u,i)\) に対し、一度に\(m\)個の負例 \(\left\{j_k\right\}_{k=1}^{m}\)を一様にサンプリングする
- \(L = \log \sigma(s_{ui}) - \sum_{k=1}^m \log(1 - \sigma(s_{uj_k}))\) + (正則化項)から勾配を計算してパラメータ更新
