乐胖代购免代理版

この記事はエムスリーAdvent Calendar 2019 2日目の記事です。

エンジニアリンググループ AIチームの金山 (@tkanayama_)です。普段の業務では、医療従事者向けWebサイト m3.com のための推薦システムの開発・運用を担当しています。

今回は、 "Sampler Design for Bayesian Personalized Ranking by Leveraging View Data" [Ding et al., 2018] という論文を紹介します。これは、implicit feedbackの代表的な推薦システムBayesian Personalized Rankingを拡張して、「itemが表示されたがclickされなかった」という情報をうまく活用してitemの推薦ができるようにした論文です。

f:id:tepppei:20191128192306j:plain:w300 — リスの画像です。

この記事の流れ

まず、今回紹介したい論文の先行研究である "Bayesian Personalized Ranking from Implicit Feedback [Rendle et al., UAI 2009]" を紹介し、次いで表題論文への拡張を説明します。そして、実装および簡単な実験を行ったので説明します（※この記事における実験は explicit feedbackのdatasetをもとにしてimplicitに変換したものを用いています。実際のpageview情報を使ったimplicitなデータに対してはこの記事では扱っていませんが、うまくいったら次回記事にします！）。

用語の整理

推薦システムの学習に利用するログデータは、大きく分けてexplicit feedbackとimplicit feedbackの2種類が存在します。explicit feedbackは、ユーザーの興味が明示的に与えられているデータを指します（例：ECサイトやレストランレビューサイトなどにおいてユーザーが星1〜星5の5段階で評価を行うような状況）。一方、implicit feedbackは逆にユーザーの興味が明示的に与えられていないデータを指します（例：ニュースサイトにおける記事のクリックや、ECサイトにおける購入など）。

今回の記事では、implicit feedbackを用いた推薦システムを対象にしています。また、以下ではニュースサイトにおける記事のレコメンドを前提として話を進めます。

また、user-item間のインタラクションとして、clickとviewという2種類の用語を用います。あるユーザーがニュースサイトのトップページを訪問したとします。トップページには、記事のタイトルがいくつか表示されています。このとき、ユーザーは記事をviewしたと見なします。その後、ユーザーは気になる記事があればタイトルをクリックし、その記事の詳細ページに遷移します。これをclickと呼んでいます。したがって、user-itemのインタラクションとしては、「clickした」「viewしたがclickしなかった」「viewしなかった」の3種類が定義されます。

Bayesian Personalized Ranking from Implicit Feedback

まず、Matrix Factorizationをimplicit feedbackのdatasetに適用するための代表的な手法である、Bayesian Personalized Ranking（BPR）について説明します。BPRでは、上で説明した「clickした」「viewしたがclickしなかった」「viewしなかった」の3種類のうち、「clickした」「clickしなかった」の2種類のみ使って学習します。

核となるアイデア

implicit feedbackの難しい点は、「クリックしなかった」という情報の中に、「興味がない（negative）からクリックしなかった」と「興味はある（positive）が、目に入らなかったからクリックしなかった」の2つが混ざっている点にあります。これに対処する方法として、「クリックがあったuser-itemの組だけを用いて学習を行う」「クリックがなかったuser-itemの組は全てnegativeと見なして学習を行う」などの方法も考えられますが、BPRでは「あるuserがクリックしたitemは、クリックしなかったitemに比べて興味がある」という仮定のもと学習を行います。

言葉だけだとわかりにくいので具体例を挙げます。あるuser uが、item 1, item 2をクリックし、item 3, item 4をクリックしなかったとします。このとき、user uの興味は以下のような順序になっていると見なします。

item 1 > item 3
item 1 > item 4
item 2 > item 3
item 2 > item 4

一方、上記以外の順序は不明とします（例えば、クリックがあったitem 1とitem 2はどちらが興味があるかはわからない）。BPRでは、user-item間のクリックデータを順序データに変換し、学習を行います。

目的関数の導出

user $u = 1, \cdots ,U$ に item $i = 1, \cdots ,I$ を推薦する問題を考えます。あるuser uにおける、itemの順序の集合を $>_{u}$ とします。例えば上の例なら、 $>_{u} = \{i_1 > i_3, i_1 > i_4, i_2 > i_3, i_2 > i_4 \}$ です。また、 $>_{u}$ を生成するモデルのパラメータを $\Theta$ とすると、 $\Theta$ のMAP推定の目的関数は下記のようになります。

${\rm argmax}_{\Theta} \ {\rm ln} \ p(>_{u_1}, \cdots ,>_{u_U}|\Theta) + {\rm ln} \ p(\Theta)$

次に、尤度 $p(>_{u_1}, \cdots ,>_{u_U}|\Theta)$ を書き下します。いま、2種類の独立性を仮定します。

仮定1: 各userのitemへの順序は、他のuserに対して独立である。
仮定2: 各userの各itemペアに対する順序は、他のitemペアに対する順序に対して独立である。

これらの仮定を用いて、尤度 $p(>_{u}|\Theta)$ は下記のように書き直せます。

$p(>_{u_1}, \cdots ,>_{u_U}|\Theta) = \Pi_{(u, i, j)\in{D_S}} \ p(i >_{u} j|\Theta)$

$D_S$ は学習データの順序集合全体とします。

最後に、確率 $p(i >_{u} j|\Theta)$ を $\sigma(\hat{x}_{uij}(\Theta))$ でモデル化し、事前分布 $p(\Theta)$ に平均0, 分散 $\lambda_{\Theta}I$ の正規分布を仮定することで、下記の目的関数を得ることができます。

${\rm argmax}_{\Theta} \ \Sigma_{(u, i, j)\in{D_S}} \ {\rm ln} \ \sigma(\hat{x}_{uij}(\Theta)) - \lambda_{\Theta}||\Theta||^2 \tag{1}$

ここで、 $\sigma$ はシグモイド関数、 $\hat{x}_{uij}(\Theta)$ は u, i, jの組に対してスコアをつけることができる任意のモデルです。

例えばモデルとしてMatrix Factorizationを用いる場合は、下記のように $\hat{x}_{uij}(\Theta)$ を定義します。

$\hat{x}_{uij}(\Theta) = \hat{x}_{ui}(\Theta) - \hat{x}_{uj}(\Theta)$

これで、u, i, jの組に対してスコアを与えることができるようになりました。式1の最適化は、学習データから u, i, jの組をランダムにサンプリングし、SGDを用いて行われます*1。

Sampler Design for Bayesian Personalized Ranking by Leveraging View Data

ここまでが先行研究であるBPRの説明でした。"Sampler Design for Bayesian Personalized Ranking by Leveraging View Data"では、上記のデータに加えて、「viewしたがクリックしなかった」という情報も与えられている状況を考えます。すなわち、「clickした」「viewしたがclickしなかった」「viewしなかった」の3種類を用いて学習します。これをBPRのloss関数に組み込みます。*2

BPRでは、userの興味度が

「clickされたitem」>「clickされなかったitem」

であることを仮定していましたが、この論文ではこれを拡張して、

「clickされたitem」>「viewされたがclickされなかったitem」>「viewされなかったitem」

という順序を仮定しています。ここまで仮定してしまえばあとはBPRの目的関数を少し改変して、

${\rm argmax}_{\Theta} \ \Sigma_{(u, i, v, j)\in{D_S}} \ ({\rm ln} \ \sigma(\hat{x}_{ui}(\Theta) - \hat{x}_{uj}(\Theta)) + \alpha {\rm ln} \ \ \sigma(\hat{x}_{ui}(\Theta) - \hat{x}_{uv}(\Theta)) + (1 - \alpha) \ {\rm ln} \ \sigma(\hat{x}_{uv}(\Theta) - \hat{x}_{uj}(\Theta))) \tag{2}$

とすることで目的関数を得ます。ここで、 $i$ は「clickされたitem」、 $v$ は「viewされたがclickされなかったitem」、 $j$ は「viewされなかったitem」をそれぞれ表します。

実装

PyTorchを用いて実装を行いました。以下、モデルとlossの部分は以下のようになっています。

class MatrixFactorization(nn.Module):
    def __init__(self, n_items, n_users, embedding_dim):
        super(MatrixFactorization, self).__init__()
        self.user_embedding_layer = nn.Embedding(num_embeddings=n_users, embedding_dim=embedding_dim)
        self.item_embedding_layer = nn.Embedding(num_embeddings=n_items, embedding_dim=embedding_dim)

    def forward(self, user, item):
        user = self.user_embedding_layer(user)
        item = self.item_embedding_layer(item)
        return (user * item).sum(axis=1)

def view_enhanced_bpr_loss(xi, xv, xj, alpha=0.5):
    return (-LogSigmoid()(xi - xj) - alpha * LogSigmoid()(xi - xv) - (1 - alpha) * LogSigmoid()(xv - xj)).mean()

実験

データセット

各user-itemの組の一部に対して1~5の5段階の評価がついたデータセットである MovieLens 100Kを用いて実験を行いました。今回のlossを適用するためにはデータを3つのグループに分ける必要があるため、以下のような変換を行いました。

評価4以上のitem → clickされたitem
評価3以下のitem → viewされたがclickされていないitem
評価がついていないitem → viewされていないitem

テストセットは、スコアが付いているuser-itemのペアから約10%を切り出して作成しました。また、潜在ベクトルの次元数は10とし、最適化手法にはAdamを用いました。式2の $\alpha$ は1.0としました。*3

実験結果

f:id:tepppei:20191201124334p:plain

実験結果はこのようになりました。おおむねどの評価指標でも、view情報を考慮したBPRのほうが性能が良くなっていることがわかります。

最後に

今回の実験では実際のviewデータを用いたわけではないため、実データでうまくいくかどうかは別途検証する必要があります。また、「viewされたがclickされていないitemのほうが、viewされていないitemよりも興味度が高い」という今回の論文の仮定は、データセットによって大きく異なると考えられます。例えば、ECサイトの場合は「商品詳細ページが閲覧されたが購入はされていないitem」より「商品詳細ページさえ閲覧されていないitem」のほうがuserの興味度が高いと言えるかもしれません。一方Webサイト上での記事表示の場合は、「タイトルが目に入っているのにクリックされなかった記事」のほうが「タイトルが見られていない記事」よりも興味度が高いとは考えにくいです。このあたりは、事前に各item群とuserのclick傾向との関係性をあらかじめ分析しておく必要がありそうです。幸いエムスリーでは、Webサイト上でのユーザー行動（viewおよびclick）がデータとして取得できるため、今回の論文が実際に性能を発揮できるかどうかを試してみようと思います。