推薦アイテムセットの多様性を考慮したBPR論文を実装・実験した

エンジニアリンググループ AIチームの金山 (@tkanayama_)です。2019年新卒でエムスリーに入社してから早くも1年経ってしまいました。

今回は、 "Bayesian Personalized Ranking for Novelty Enhancement" [Wasilewski and Hurley, UMAP'19] という論文を紹介します。Bayesian Personalized Ranking (BPR) のサンプリング方法を工夫することで、推薦するitemが多様になるようにした論文です。

f:id:tepppei:20200302205514j:plain:w400 — ワラビーです。

推薦システムでは、推薦されたitemセットが画一的になってしまうことが問題となる場合があります。

エムスリーでは医療系会員に対してニュース記事を配信していますが、似た内容のニュース記事が集中的に投稿される時期があります。例えば、3月は大学受験の記事、8月は東医体・西医体（医学生のスポーツの祭典）の記事が集中しますし、最近は新型コロナウイルス感染症（COVID-19）の記事がとても多くなっています。

単純に読まれる可能性が高そうな記事から順に推薦してしまうと、メルマガに掲載された記事の話題がほとんど同じになってしまう可能性があります*1。そこで、今回はこうした状況への対処策の1つとして表題論文を取り上げてみました。

この論文は前回記事 www.m3tech.blog

で扱ったBPRの派生形であり、アルゴリズム自体はとてもシンプルです。そこで今回は、擬似データを用いた追実験部分を詳しめに書きます。

Bayesian Personalized Ranking（BPR）の復習

詳細は前回記事などを参照してください。

BPRでは、「あるuserがクリックしたitemは、クリックしなかったitemに比べて興味がある」という仮定に基づいて推薦を行います。例えばMatrix Factorizationのようにuser uとitem iに対してscore $\hat{x}_{ui}$ を出力するモデルを用いる場合、user uにクリックされたitem iとクリックされなかったitem jのペアに対して下記を定義します。

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

ここで、 $\Theta$ はモデルのパラメータです。このとき、下記の式を最大化するような $\Theta$ を求めることで、 $\Theta$ を最適化します。

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

$\sigma$ はシグモイド関数、 $D_S$ は学習データに含まれる「クリックされたitem」と「クリックされなかったitem」のペアの集合です。

Bayesian Personalized Ranking for Novelty Enhancement

前述のBPRの場合、推薦対象のitemセットによっては、上位に推薦されるitemセットが画一的になってしまう可能性があるという問題がありました。そこでBayesian Personalized Ranking for Novelty Enhancementでは、itemセットの多様性を考慮した推薦を行います。

通常のBPRとの最大の違いはペアデータの作り方にあります。下記を満たすようなuser u, item i, item jの組を取得します。

$D^{dist}_{S} = \{(u, i, j)|(u, i) \in R \land j \in I \backslash I^+_u \land dist(i, j) \lt \tau \} \tag{3}$

$R$ はuser uとuがclickしたitemのペアの集合、 $I \backslash I^+_u$ はuser uがclickしていないitemの集合です。ここまでは普通のBPRと同じなのですが、追加条件として $dist(i, j) \lt \tau$ があります。これは、何らかの方法でitem iとitem jの距離を定義したとき、距離が閾値 $\tau$ より小さいitemだけをnegativeなitemとして扱うことを表します。これによって、clickされたitemと距離が近いitemを推薦されにくくする効果が期待されます。

ただし、 $D^{dist}_{S}$ だけからサンプリングすると性能が低下する場合があるので、実際には $D^{dist}_{S}$ と $D_S$ のどちらからサンプルするかを一定の確率で切り替える方法を提案しています。

擬似データを用いた追実験

以下、追実験について説明します。実験に用いたコードはこちらに置きました*2。この実験は、擬似データを用いて理想的な状況下におけるモデルの挙動を確認することを目的としています。

擬似データの生成

user, itemの潜在表現が、2次元の正規分布に従う同一空間上に存在するベクトルだとします。ただし、itemは4種類のitem type (item_type=A, B, C, D)が存在し、item typeによって従う正規分布が異なるとします。

具体的に、user, itemをサンプリングして平面上に可視化した結果が下記です。userは10000個サンプルし、itemはitem type Aから100個、item type B, C, Dから各50個サンプルしました。

f:id:tepppei:20200228224037p:plain — user, itemの潜在表現

黒のプロットがuser、色付きのプロットがitemを表しています。item type Aがもっともuserに近く、item type Dが最も遠くなっています。

ここで、user uがitem iをクリックしたことを表す確率変数 $Y_{u, i}$ が下記のようなベルヌーイ分布に従うとします。

$Y_{u, i} \thicksim Ber(Sigmoid(\frac{1}{||u_{u}-v_{i}||}) - 0.5) \tag{4}$

ここで、 $||u_{u}-v_{i}||$ はユークリッド距離です。距離が近ければ近いほどクリックしやすいということになります。この $Y_{u, i}$ を用いて擬似的にクリックを発生させ、item typeごとにclickしたuser数の平均を集計した結果が下記の図です。

f:id:tepppei:20200228224050p:plain — 各item typeの平均click数

item type Aに属するitemは平均700人/10000人以上のuserからclickされているのに対し、item type Dに属するitemは平均50人/10000人程度のuserからしかclickされていないということになります。このclick数分布は、潜在空間においてitem type Aがもっともuserに近く、item type Dが最も遠いという事実に矛盾しません。

推薦itemセットの多様性を考慮しない通常の推薦システムであれば、推薦順位の上位をほとんどitem type Aが占めてしまうことが予想されます。多様性を考慮することによって、item type B, Cも推薦itemセットに含めつつ、clickが極端に少ないitem type Dは推薦しないような挙動を期待します。

実装

今回は、通常のBPRと前述の"BPR for Novelty Enhancement"を比較します。計算時間を削減するために、学習時に逐次positive dataとnegative dataをサンプリングするのではなく、あらかじめpositive dataとnegative dataのペアにしたデータを用意しておいて、学習時にペアデータからランダムサンプリングする方法で実装を行いました。具体的に、ペアデータを生成するtaskは下記です。

import pandas as pd
import gokart
import luigi


class MakePairedData(gokart.TaskOnKart):
    task_namespace = 'novelty_enhanced_bpr'

    click_task = gokart.TaskInstanceParameter()
    positive_sample_weight: int = luigi.IntParameter()
    distance_threshold: float = luigi.FloatParameter()

    def requires(self):
        return self.click_task

    def run(self):
        clicks = self.load()['clicks_train']
        item_distance = self.load()['item_distance']
        paired_data = self._run(clicks, item_distance, self.positive_sample_weight, self.distance_threshold)
        self.dump(paired_data)

    @staticmethod
    def _run(clicks: pd.DataFrame, item_distance: pd.DataFrame, positive_sample_weight: int, distance_threshold: float) -> pd.DataFrame:
        clicked_data = clicks[clicks['click'].astype(bool)].rename(columns={'item_id': 'positive_item_id'})
        not_clicked_data = clicks[~clicks['click'].astype(bool)].rename(columns={'item_id': 'negative_item_id'})

        not_clicked_data = not_clicked_data.groupby('user_id').apply(
            lambda x: x.sample(positive_sample_weight)).reset_index(drop=True)

        paired_data = pd.merge(clicked_data[['user_id', 'positive_item_id']],
                               not_clicked_data[['user_id', 'negative_item_id']],
                               on='user_id', how='inner')

        paired_data = pd.merge(paired_data, item_distance, left_on=['positive_item_id', 'negative_item_id'], 
                               right_on=['item_id_x', 'item_id_y'], how='inner')
        if distance_threshold:
            paired_data = paired_data[paired_data['distance'] < distance_threshold]
        return paired_data[['user_id', 'positive_item_id', 'negative_item_id']]

下から3行めの条件分岐にて、距離が近いitemのみをnegative itemとして抽出する処理を入れています。

実験結果

f:id:tepppei:20200228224930p:plain — 各種評価指標*3のスコア

f:id:tepppei:20200228233715p:plain — BPR（左：推薦順位上位10件に含まれるitem type数の分布／右：各item typeを推薦順位上位10件に含むuser数）

f:id:tepppei:20200228233722p:plain — BPR（左：推薦順位上位10件に含まれるitem type数の分布／右：各item typeを推薦順位上位10件に含むuser数）

f:id:tepppei:20200228233654p:plain — BPR for Novelty Enhancement（左：推薦順位上位10件に含まれるitem type数の分布／右：各item typeを推薦順位上位10件に含むuser数）

f:id:tepppei:20200228233708p:plain — BPR for Novelty Enhancement（左：推薦順位上位10件に含まれるitem type数の分布／右：各item typeを推薦順位上位10件に含むuser数）

左側の棒グラフを見ると、推薦スコアが高い上位10件のitemを各userに推薦した場合、通常のBPRは8,000人/10,000人のuserに対して全て同じitem typeのitemを推薦してしまうのに対し、提案手法ではそのようなuserが4,000人/10,000人に抑えられることがわかります。また、右側の棒グラフを見ると、通常のBPRの場合はitem type B, Cに属するitemがそれぞれ1,000人程度にしか推薦されないのに対し、提案手法ではそれぞれ4,000人程度のuserに推薦されることがわかります。

このように推薦itemセットの多様性が大きく改善された一方で、各評価指標の値はあまり変化せず維持できていると言えそうです。

感想

サンプリング方法を変えるというシンプルな変更だけで、性能を保ちつつ推薦itemセットの分布を大きく変えることができる点がとても面白いです。

ただし、この手法はitemどうしの距離の測り方によって挙動が大きく変わるため、itemをどうembeddingして距離を測るかが重要になりそうです*4。

We are hiring!

私は入社して1年間推薦システムの開発に取り組んできました。推薦システムは機械学習の中でもユーザーの挙動と密接に関わりがある領域だと思います。ユーザーの挙動を理解するために想像力を働かせて分析を行い、それを数式やコードに落とし込んでモデルを構築し、実世界にリリースしてユーザーからフィードバックを受け、再度挙動を分析する、という一連のサイクルがとても楽しいです。私たちと一緒に、ユーザーの挙動を考えながら推薦システムを開発・改善してくれる方を募集しています！

エンジニアリンググループ募集一覧

jobs.m3.com

*1:そもそも、記事の内容が画一的になることはユーザーにとって本当に良くないことなのか？を考える必要がありますが、今回はそこには踏み込まず、画一的になることを回避する方法について焦点を当てています。

*2:実装にはgokartを用いました。

*3:一言で説明すると、Recallは「userがクリックしたitemをどれだけ推薦上位でカバーできているか」、MAPは「上位に推薦したitemがどれだけクリックされているか」を表す指標です。

*4:論文にはあいにくitem embeddingの方法に関しては明示されていませんでした。