Factorization MachinesによるBayesian Personalized Ranking

　こんにちは、リブセンスでデータサイエンティストをしている北原です。今回と次回の２回にわたって暗黙的評価データを使ったコンテキスト対応レコメンデーションの紹介をしようと思います。具体的には、コンテキストを扱えるFactorization Machines(FM)をモデルとした、Bayesian Personalized Ranking(BPR)を紹介します。今回はアルゴリズムとモデル、次回は実装と実務での応用の話をします。

暗黙的評価データを使ったレコメンデーション

　まず暗黙的評価データとは何かについて説明し、暗黙的評価を使ったレコメンデーションの問題について説明します。

　レビューの点数のようなユーザー回答に基づくものは明示的評価、クリックや購入のようなユーザーが直接評価したわけではなく行動から推測されたものは暗黙的評価と呼ばれます。明示的評価はユーザーが意識してつけた点数なので比較的信頼性は高いものの、ユーザー負担が大きいのでデータ取得が難しいという問題があります。一方で、暗黙的評価はデータ取得は容易ですが扱いが難しいという問題があります。明示的評価データを使えるようにサービス設計したほうがレコメンデーションの効果は高くなるものの、違和感のない形で評価点数をつけてもらうためのユーザーインターフェースを設計、実装する必要もあるため、既存サービスに後から導入するのが難しいことも多いです。そのため、手軽にレコメンデーションを導入したい場合は、まず暗黙的評価を利用することが多いと思います。

　レコメンデーションで暗黙的評価データを扱う際の問題は、評価データの信頼性が低いこと、未評価データの扱いが難しいこと、未評価データの量が多いことの３つです。実務においてどの問題が影響するかは扱うデータに依存します。

　評価データの信頼性が低いというのは、クリックや購入があったからといってそれらがユーザーの好みに合っているとは限らないということです。購入促進を目的としたレコメンデーションであれば、購入行動を高評価扱いするのは問題ないでしょうが、クリックの扱いは難しいところです。商品タイトルや画像が魅力的だからクリックして詳細を見てみたらイマイチだったという経験は誰しもあるでしょう。クリックされたということは無関心ではないということなので高評価と考えることができますが、一方で購入されない致命的な理由があるのであれば低評価扱いするのが適切です。どちらがよいかはユーザー行動だけからはわかりません。

　未評価データの扱いが難しいというのは、未評価アイテムの評価を適切に定められないということです。なぜなら、未評価アイテムの中には興味のないものもあれば、本当は興味があるのに単に気が付かなかっただけのものもあり、好みにあうものと合わないものが混在しているためです。そのため、これらを一律に低評価扱いするのは適切ではありません。

　未評価データの量が多いというのは、ユーザーの評価済みアイテム数は全アイテム数に比べると極めて少ないケースが多く未評価データまで使って学習しようとすると計算量が膨大になることがあるということです。例えば、評価済みを1、未評価を0として単純に学習すると、ユーザー数×アイテム数に比例する計算量になってしまいます。SGDなどのオンライン学習を使う場合はランダムサンプリングすればよいですが、ALSなどのバッチ学習を使う場合は効率的なアルゴリズムが必要になります。また、データをランダムサンプリングすると詳細釣り合い条件が成立しなくなるのでMCMCなどを使うのも難しくなります。

Bayesian Personalized Ranking

　Bayesian Personalized Ranking(BPR)は、ユーザー別ランキング学習アルゴリズムのフレームワークです。なぜフレームワークなのかというと、微分可能であれば好みを表す関数の形状に依存せずに使えるためです。BPRは有名かつシンプルで実装しやすいため、検索すると関連記事がいろいろと見つかると思います。例えば、好みを表すスコア関数にMatrix Factorizationを使ったものはこちらで紹介されています。ここではポイントだけ説明します。

　BPRの学習データは、全ユーザー集合を$U$、全アイテム集合を$I$、ユーザー$u$の評価済みアイテム集合を$I^{+}_{u}$とすると、$D_S = \{ (u, i, j) | u \in U \and i \in I^{+}_{u} \and j \in I \setminus I^{+}_{u} \}$となります。学習ではアイテム$j$は毎回ランダムサンプリングしたものを使います。

　ユーザー$u$がアイテム$i$と$j$のどちらを好むかを表す関数を$\hat{y}^{u, i, j}$とし、モデルパラメータの集合を$\Theta$、正則化係数を$\lambda_{\Theta}$とすると、BPRでは

$$ \begin{eqnarray} L = \sum_{(u, i, j) \in D_S} \ln \frac{1}{1 + \exp(-\hat{y}^{u, i, j})} - \lambda_{\Theta} \|\Theta\|^2 \label{eq:bpr_opt} \end{eqnarray} $$

を最大化するように$\Theta$を学習します。これは代理損失としてシグモイド関数を導入したAUC最大化と同じになっています。名称に"Bayesian"とつけられていますが、非対角成分$0$の分散共分散行列を利用しMAP推定で導出されているので、過去記事で扱ったBayesian Probabilistic Matrix Factorizationのようなベイズモデル特有の利点はありません。

　勾配は

$$ \begin{eqnarray} \frac{\partial L}{\partial \Theta} = \sum_{(u, i, j) \in D_S} \frac{\exp(-\hat{y}^{u, i, j})}{1 + \exp(-\hat{y}^{u, i, j})} \frac{\partial \hat{y}^{u, i, j}}{\partial \Theta} - \lambda_{\Theta} \Theta \label{eq:diff_bpr_opt} \end{eqnarray} $$

となるので、SGDなどのオンライン学習を使ってモデルパラメータ$\Theta$を計算します。アルゴリズムは

BPR Algorithm

となります。基本的にランキング学習なので、段階評価に拡張することも容易です。求人レコメンデーションの場合だと、応募求人をページ閲覧求人より高評価として学習させたりします。

　BPRのポイントは、ユーザーごとにpairwiseランキング学習をするところと、ユーザーごとに未評価データをランダムサンプリングして学習するところにあります。ランキング問題ではpointwise学習よりpairwise学習のほうが精度が高い傾向があることが知られているので、ユーザーごとのランキング学習によって精度の向上が見込めます。pointwiseだと評価・未評価アイテムに付与するスコアをどうするかも問題になりますが、pairwiseだと気にしなくてよいという利点もあります。また、ランキング学習ではランダムサンプリングによって効率的な学習ができることも知られているので、未評価データが大量に存在する問題にも対処できます。

　一方で、評価データの信頼性や未評価データを低評価として扱うことによる問題が完全に解消されるわけではありません。そのため、手当たりしだいにクリックするユーザーが多かったり未評価データに高評価なアイテムが多かったりするとうまく機能しない可能性があるので注意が必要です。

Factorization Machinesを利用したBayesian Personalized Ranking

　BPRでは、解きたい問題に合わせて好みを表す関数を選択することができます。元論文では、Matrix FactorizationとAdaptive k-Nearest-Neighborの例が紹介されています。好みを表す関数にはMatrix Factorizationが使われることが多いようですが、libfmやlightfmでBPRが使われていることからわかるように、Factorization Machines(FM)を利用することもできます。また、検索すると同じような試みをされているブログ記事や論文が見つかりますが、弊社で運用しているモデルとは少し異なるので、ここでは別の定式化を行います。

　好みを表す関数にFactorization Machinesを使うことで、評価以外のデータも利用できるようになります。例えば、弊社で使われる求人レコメンデーションであれば、ユーザーの希望勤務地や希望職種などの情報、求人の勤務地や年収などの情報を利用できるようになるので、うまく機能すればよりよいレコメンドが可能になることが期待できます。

　まず、通常のFMから見ていきましょう。評価データ数を$s$、ユーザーIDなども含むコンテキスト数（特徴量数）を$n$、因子数を$k$とし、評価値$\mathbf{y} \in {\mathbb R}^{s}$、評価と対応するコンテキストデータ${\bf X} \in{\mathbb R}^{s \times n}$（１サンプルのコンテキストは$\bf{x}$と表記）、モデルパラメータ$w_0 \in {\mathbb R}$、${\bf w} \in {\mathbb R}^n$、${\bf V} \in {\mathbb R}^{n \times k}$を使って、通常のFMは次のように表されます。

$$ \begin{eqnarray} \hat{y}({\bf x}) &=& w_0 + \sum^n_{i=1}{w_i x_i} + \sum^n_{i=1}\sum^n_{j=i+1}{\hat{w}_{i, j} x_i x_j} \label{eq:fm_orig} \\ \hat{w}_{i, j} &=& \sum^k_{f=1}{v_{i,f} v_{j,f}} \label{eq:w} \end{eqnarray} $$

　次にBPRで使うFMのモデル式を決めましょう。BPRで使う場合はユーザーとアイテムを区別する必要があるので、($\ref{eq:fm_orig}$)を書き換えます。上付き添字を使って、ユーザー$u$、アイテム$i$、$j$のコンテキストをそれぞれ$x^u$、$x^i$、$x^j$と表記し、ユーザーとアイテムのコンテキストに対応するモデルパラメータをそれぞれ$w^u$、$v^u$、$w^i$、$v^i$とします。これらを使って、ユーザー$u$、アイテム$i$のスコア関数$\hat{y}({\bf x}^u, {\bf x}^i)$は

$$ \begin{eqnarray} \hat{y}({\bf x}^u, {\bf x}^i) = w_0 &+& \sum^{n^u}_{j=1}{w^u_j x^u_j} + \sum^{n^i}_{j=1}{w^i_j x^i_j} \nonumber \\ &+& \sum^{n^u}_{l=1}\sum^{n^u}_{j=l+1}{\hat{w}^{u}_{l, j} x^u_l x^u_j} + \sum^{n^i}_{l=1}\sum^{n^i}_{j=l+1}{\hat{w}^{i}_{l, j} x^i_l x^i_j} + \sum^{n^u}_{l=1}\sum^{n^i}_{j=1}{\hat{w}^{u,i}_{l, j} x^u_l x^i_j} \label{eq:fm_orig_uij} \\ \hat{w}^u_{l, j} = \sum^k_{f=1} &v^u_{l,f}& v^u_{j,f} \label{eq:w_u} \\ \hat{w}^i_{l, j} = \sum^k_{f=1} &v^i_{l,f}& v^i_{j,f} \label{eq:w_i} \\ \hat{w}^{u,i}_{l, j} =\sum^k_{f=1} &v^u_{l,f}& v^i_{j,f} \label{eq:w_ui} \end{eqnarray} $$

と書き換えられます。なお、$n^u$と$n^i$はそれぞれユーザーとアイテムのコンテキスト数で$n=n^u+n^i$です。好みを表す関数は$\hat{y}^{u, i, j}=\hat{y}({\bf x}^u, {\bf x}^i) - \hat{y}({\bf x}^u, {\bf x}^j)$とします。そうするとアイテムに関わらない項は消えてしまうので式($\ref{eq:fm_orig_uij}$)の右辺第１項、第２項、第４項はなくなり、BPRで使うFMは

$$ \begin{eqnarray} \hat{y}({\bf x}^u, {\bf x}^i) &=& \sum^{n^i}_{j=1}{w^i_j x^i_j} + \sum^{n^i}_{l=1}\sum^{n^i}_{j=l+1}{\hat{w}^{i}_{l, j} x^i_l x^i_j} + \sum^{n^u}_{l=1}\sum^{n^i}_{j=1}{\hat{w}^{u,i}_{l, j} x^u_l x^i_j} \label{eq:fm_bpr} \\ \hat{w}^i_{l, j} &=& \sum^k_{f=1}{v^i_{l,f} v^i_{j,f}} \\ \hat{w}^{u,i}_{l, j} &=& \sum^k_{f=1}{v^u_{l,f} v^i_{j,f}} \end{eqnarray} $$

となります。レコメンデーションでは($\ref{eq:fm_bpr}$)を使ってpreference scoreを計算し、ユーザーごとに値が大きいアイテムをレコメンドします。なお、以前の記事で紹介した評価推定値の計算も使えます。

　$\hat{y}^{u, i, j}$を整理すると

$$ \begin{eqnarray} \hat{y}^{u, i, j} &=& \sum^{n^i}_{j=1}{w^i_j (x^i_j - x^j_j)} \nonumber \\ &+& \frac{1}{2} \sum^{k}_{f = 1} \biggl\{ \biggl(\sum^{n^i}_{j = 1} v^{i}_{j,f} x^{i}_{j}\biggr)^2 - \biggl(\sum^{n^i}_{j = 1} v^{i}_{j,f} x^{j}_{j} \biggr)^2 - \sum^{n^i}_{j=1} (v^{i}_{j, f})^2 \bigl( (x^{i}_{j})^2 - (x^{j}_{j})^2 \bigr) \biggr\} \nonumber \\ &+& \sum^{k}_{f=1} \biggl( \sum^{n^u}_{j=1} v^{u}_{j,f} x^{u}_{j} \biggr) \biggl( \sum^{n^i}_{j = 1} v^{i}_{j, f} x^{i}_{j} - \sum^{n^i}_{j = 1} v^{i}_{j, f} x^{j}_{j} \biggr) \label{eq:bpr_fm} \end{eqnarray} $$

となります。さらに$\hat{y}_{u, i, j}$をモデルパラメータ$w^{i}_{j}$、$v^{i}_{j, f}$、$v^{u}_{j, f}$で微分すると

$$ \begin{eqnarray} \frac{\partial \hat{y}^{u, i, j}}{\partial w^{i}_{j}} &=& x^{i}_{j} - x^{j}_{j} \\ \frac{\partial \hat{y}^{u, i, j}}{\partial v^i_{j, f}} &=& x^{i}_{j} \biggl( \sum^{n^i}_{l = 1} v^{i}_{l, f} x^{i}_{l} + \sum^{n^u}_{l = 1} v^{u}_{l, f} x^{u}_{l} \biggr) - x^{j}_{j} \biggl( \sum^{n^i}_{l = 1} v^{i}_{l, f} x^{j}_{l} + \sum^{n^u}_{l = 1} v^{u}_{l, f} x^{u}_{l} \biggr) - v^{i}_{j, f} \bigl( (x^{i}_{j})^2 - (x^{j}_{j})^2 \bigr) \\ \frac{\partial \hat{y}^{u, i, j}}{\partial v^u_{j, f}} &=& x^{u}_{j} \biggl( \sum^{n^i}_{l = 1} v^{i}_{l, f} x^{i}_{l} - \sum^{n^i}_{l = 1} v^{i}_{l, f} x^{j}_{l} \biggr) \end{eqnarray} $$

となるので、($\ref{eq:diff_bpr_opt}$)を計算するのに必要なものは揃いました。後はBPRのアルゴリズムにしたがえば、各モデルパラメータを更新することができます。

　BPRで使うモデルを表す式($\ref{eq:fm_bpr}$)について少し考えてみましょう。式($\ref{eq:fm_bpr}$)の右辺第１項はアイテムコンテキストに比例する線形項、第２項はアイテムコンテキスト同士の交互作用項でアイテム単独での好まれやすさを表します。式($\ref{eq:fm_bpr}$)の右辺第３項はユーザーコンテキストとアイテムコンテキストの交互作用項で、ユーザーがアイテムを好むかを表す項です。レコメンデーションに利用する場合、ユーザーとアイテムの交互作用項は必須なのですが、他の項はデータや課題に合わせて採否を判断します。こちらのブログ記事ではアイテム同士の交互作用項を除いたモデルを考えているようですが、弊社ではモデルの表現能力を高めたいことと計算量への影響も小さいことからアイテム同士の交互作用項を入れたままにしています。過学習が強すぎるなどの理由でモデルをシンプルにしたい場合にはアイテム同士の交互作用項を除外するのもよい方法だと思います。

　アルゴリズムをまとめると

BPR-FM Algorithm

となります。このまま忠実に実装すればモデルパラメータを計算できるので、少量のサンプルデータなどを使って更新式が意図通り機能するかなどを確認するのに便利です。しかし、FMでは多くのケースでスパースなデータを扱うため、このままだと非常に冗長で計算に時間がかかってしまいます。そこで少し実装に工夫が必要になります。次回はその実装について紹介しようと思います。

まとめ

　今回はFMをモデルとしたBPRについて紹介しました。BPRは暗黙的評価データを使ったレコメンデーションに使われるアルゴリズムのフレームワークで、スコア関数にコンテキストを扱えるFMを利用することができます。FMをモデルとしたBPRを使うことで、暗黙的評価データでもコンテキストを利用したレコメンデーションができるので精度の向上が期待できます。次回は実装について紹介しようと思います。