乐胖代购免代理版

こんにちは、エムスリーエンジニアリンググループ AIチーム新卒エンジニアの金山 (@tkanayama_)です。普段の業務では、医師・薬剤師向けプラットフォーム m3.com にて、個々のユーザーにとって最適なニュース記事を配信するための推薦システムの開発・運用を担当しています。そこで今回は推薦システムに関連して、推薦システムのオフライン評価時にアイテム側のバイアスを除去して評価する手法を提案した論文で、RecSys 2018に採択されているUnbiased Offline Recommender Evaluation for Missing-Not-At-Random Implicit Feedback を実装・実験してみました。

問題設定

ユーザー A~Eに、ニュース記事 a~eを推薦するという問題を考えます。さて、user-item間の真の嗜好性は表1のようになっているとします。

f:id:tepppei:20190919172418p:plain:w300 — 表1. user-item間の嗜好性（○が好き、×が嫌いを表す）

ここで、userがitemに対して取れる行動は「クリックするか否か」のみで、例えば高評価ボタンやレーティングシステムなどは無いものとします*1。したがって、実際には上記の嗜好性の全てを観測することはできません。そこで、表1の嗜好性に基づいて表2のようなクリックログが得られたとします。

f:id:tepppei:20190919172701p:plain:w300 — 表2. 実際に観測されたクリックログ（○がクリックあり、＊がクリックなし）

ただし、○が「クリックした」、＊が「クリックしなかった」とします。このクリックログの例は、「ユーザーが好きな記事に対してのみクリックが発生するが、必ずしも好きな記事全てをクリックするわけではない」という仮定に基づいています*2。この仮定は、例えば記事が目につく場所に表示されていなかった状況などを考えると自然な仮定と考えられます。したがって、クリックしていたらそのユーザーがその記事を好きだということがわかるが、クリックしていないからといって嫌いとは限らない、ということになります*3。例えば、Aさんは記事cを好きですが、今回はクリックしていません。

また、この例では記事a, bのクリック数が恣意的に多くなるようにしました。これは例えば、記事a, bがトップページの一番目立つ場所に置かれていたなどの状況を考えてください。

何が問題となるか？

さて、ここで推薦システムXと推薦システムYを実装したとします。X, Yはそれぞれ、下記のような順位づけで記事を推薦します。

f:id:tepppei:20190919172706p:plain:w300 — 表3: 推薦システムXの推薦順位

f:id:tepppei:20190919172712p:plain:w300 — 表4: 推薦システムYの推薦順位

ここで表中の数字は、推薦システムがユーザーにアイテムを推薦する順位を表します。（表1におけるユーザーが好きな記事を、表3, 4では赤字にしてあります。）

表3を見ると、推薦システムXは全ユーザーに同じ順位でアイテムを推薦していることが分かります。一方、推薦システムYはユーザーごとに個別化された順位づけで記事を推薦しています。表1と表4を見比べると、推薦システムYが1位・2位指定しているアイテムは全て各ユーザーが好きな記事になっています。これは良さそうです。

これらの推薦システムの性能を、user-item間の嗜好性（表1）データを用いて評価してみます。ここでは、「ユーザーが好きな記事が、推薦システムで2位までに指定された割合」をもとに評価します*4。明確化のために式で表すと下記のようになります。

$R(\hat{Z}) = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} \frac{1}{|\mathcal{S_u}|} \sum_{i \in \mathcal{S_u}} \bf{1} \{\hat{Z}_{u, i} \leq 2 \} \tag{1}$

ここで、 $\mathcal{U}$ は userの集合、 $\mathcal{S_u}$ はuser uが好きなitemの集合、 $\hat{Z}_{u, i}$ はuser u, item iに対して推薦システムが付けた順位、 $\bf{1} \{\}$ は $\{\}$ 内が成り立つ時1を返す関数とします。さて、この評価方法で推薦システムX, Yを評価すると、以下のようになります。

推薦システムX $(2/3 + 1/3 + 0/3 + 1/3 + 2/3) / 5 = 0.60 \tag{2}$

推薦システムY $(2/3 + 2/3 + 2/3 + 2/3 + 2/3) / 5 = 0.67 \tag{3}$

たしかに推薦システムYの方が性能が良いことがわかります。

しかしながら、user-item間の嗜好性（表1）は実際には観測できず、実際の評価に使えるのは実際に観測されたクリックログ（表2）だけです。そこで、表2のクリックログを使って推薦システムX, Yの性能を評価してみます。式1と同様に、下記のような式で評価を行います。

$R(\hat{Z}) = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} \frac{1}{|\mathcal{S_u^*}|} \sum_{i \in \mathcal{S_u^*}} \bf{1} \{\hat{Z}_{u, i} \leq 2 \} \tag{4}$

ここで、 $\mathcal{S_u^*}$ はuser uがクリックしたitemの集合です。さて、この評価方法で推薦システムX, Yを評価すると、以下のようになります。

推薦システムX $(2/2 + 1/1 + 0/1 + 1/1 + 2/3) / 5 = 0.73 \tag{5}$

推薦システムY $(1/2 + 0/1 + 0/1 + 0/1 + 2/3) / 5 = 0.23 \tag{6}$

なんとXの方が良いスコアが出てしまい、真のユーザーの嗜好性を用いて評価した場合の結果と逆転してしまいます。したがって、手元にあるクリックデータだけから推薦システムを評価してしまうと、使用する推薦システムに関して誤った意思決定をしてしまう可能性があります。

なぜこのようになってしまうかというと、大きな原因として記事によってクリックされやすさが異なるということが挙げられます。前述の通り、記事a, bは露出機会が多くクリックされやすい状況だったため、記事a, bをたくさん推薦している推薦システムXが高く評価されてしまったということです。

解決方法

上記の問題点を解決するため、論文中では（式1）を下記のように改変する手法を提案しています。

$R(\hat{Z}) = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} \frac{1}{|\mathcal{S_u}|} \sum_{i \in \mathcal{S_u^*}} \frac{c(\hat{Z}_{u, i})}{P_{u, i}} \tag{7}$

ここで、 $P_{u,i}$ は真の嗜好性が観測される確率で、propensity scoreと呼ばれます。感覚としては、「クリックログ中で露出が少ない記事に対する重み付けを大きくすることにより、露出機会により生じる不均衡を解消しよう」という発想です。*5

$P_{u,i}$ は次のように推定します。まず、

$P_{u,i}$ がuserに依存しないこと
クリックは「アイテムが推薦システムに選択される→ユーザーがアイテムをクリックする」という2段階で発生すること
ユーザーの嗜好性は推薦システムが何を推薦するかによらないこと

を仮定し、

$P_{*, i} = P_{*, i}^{select} \cdot P_{*, i}^{interact}$

を得ます。ここで、 $P_{*, i}^{select}$ はitem iが推薦システムに選択される確率、 $P_{*, i}^{interact}$ はuserがitem iを（全itemを見た上で）クリックする確率です。

次に、

$P_{*, i}^{interact}$ はitem iの真の人気度 $n_i$ （図1のように全ての嗜好性が観測されていた場合のクリック数の合計）に比例すること
クリックログ上で人気なitemほど推薦システムに選ばれやすく、 $P_{*, i}^{select}$ がクリックログ上での人気度 $n^*_i$ の指数乗に比例すること

を仮定して、

$\hat{P}^{interact}_{*, i} \propto n_i$

$\hat{P}^{select}_{*, i} \propto (n_{i}^{*})^{\gamma}$

を得ます。最後に、 $n_{i}^{*}$ が二項分布 $\mathcal{B}(n_i, P_{*, i})$ からサンプリングされたと仮定することにより、 $\hat{P}_{*, i} = \frac{n_{i}^{*}}{n_i}$ を得ます。上記で得られた式を全て統合することにより、結果として $P_{u,i}$ は

$\hat{P}_{*, i} \propto (n_{i}^{*})^{\frac{\gamma + 1}{2}}$

で推定されます。

（補足ですが、式4における $|\mathcal{S_u}|$ は user uが真に好きなitem数を表します。この値も直接は得ることができないので、論文中では $\sum_{i \in \mathcal{S_u^*}} \frac{1}{P_{u, i}}$ で推定されています。）

実験

さて、上記の提案手法で実際にバイアスが取り除かれるのかどうか実験してみます。今回は、explicit feedbackのデータセットであるMovieLensをもとにimplicit feedbackの人工データを生成し、実験を行いました*6。人工データは、trainingデータがアイテムの人気度によるバイアスを持ったようなデータになるよう生成しました。各アイテムのクリック数を多い順に並べたグラフ示します。

f:id:tepppei:20190913004236p:plain — 図1: 各アイテムのクリック数の分布

一方で、testデータは真の嗜好情報が含まれるためモデルの真の性能を測ることができます。実験では、training用データの一部からvalidation用データを切り出します。次に、training用データを使って推薦モデルを学習し、validation用データ・test用データそれぞれで評価を行います。test用データでの評価を真の評価値とみなし、論文の手法を用いることによりvalidation用データでの評価がどれだけtest用データでの評価に近づくかを確認します。

モデルはLightFMで実装されたbayesian personalized rankingを用いました。また、指標としてDCGスコアを用いました。

結果

f:id:tepppei:20190919174028p:plain — 表5: 実験結果

実験結果はこのようになりました。単純なAOAスコア（式1によるスコア）ではtest用データで評価した場合に比べて過大評価されてしまっているのに対し、論文で提案されている手法を用いることにより過大評価の具合が抑えられ、より真の評価値に近づいていることがわかります。

まとめ

この記事では、クリックされやすさの異なるアイテムのバイアスを考慮した評価指標を用いることにより、推薦システムのより正確な性能評価を行う論文について解説しました。今回は評価段階におけるimplicit feedbackの問題設定を扱いましたが、学習段階におけるdebiasや、explicit feedbackのdebiasについての研究も存在するので、興味を持たれた方は是非調べてみてください。また、こうした推薦システムにおけるdebiasの研究に関する日本語ブログとしては、「Counterfactualを知りたい」がとても参考になります。

We are hiring!

このような記事を書いた後で言うのもなんですが、やはりオフライン評価は限界があります。（上記の $P_{u, i}$ の推定で多くの仮定を置いていることからもわかると思います。）より正確なモデルの評価を行うためにはABテストが非常に有効です。

私はまだ入社半年ですが、これまでに何度もABテストにトライする機会をもらっています*7。これは、自社で推薦システムの系を持っていて迅速にABテストを回せる環境が整っており、なおかつ私のような新卒にも大きな裁量を与える企業だからこそできることだと思います。推薦システムに興味がある方、是非一緒に働きましょう！

open.talentio.com

jobs.m3.com

*1:いわゆるimplicit feedbackの問題設定です

*2:「好き」かつ「目に入った」が満たされた時にクリックが発生するという仮定を置いたモデルをposition based modelと呼びます。click行動をモデル化する方法はposition based model以外にも数多く提案されていますが、それに関しては後の記事でまとめたいと思います。

*3:現実問題では、そもそもクリックが発生してているからと言ってその記事が好きだと決めつけることはできません（例えば誤クリックや、本文の内容と大きく異なるタイトルに釣られてしまった場合など）。そうした状況をモデルに組み込む研究もなされていますが、今回の記事では対象外とします。

*4:Recall@2のAverage-over-all (AOA) evaluatorです。

*5:実際、不偏推定量となることも論文中で示されています。

*6:人工データ生成の詳細に関しては後日公開しようと思います。

*7:そして毎回、現実世界でうまく機能する推薦システムを作るのは難しいことだと思い知らされます…