Replay推定量を勉強する

先日こんなことをやっていました。

www.nogawanogawa.com

オフラインテストにはバイアスがつきもので、そのへんを考慮せずにオフライン評価しようとすると、ちょっと困ったことが発生することを確認した感じですね。

今回はそんなオフラインテストでバイアスを考慮しながら評価する方法について調べてみたのでそのメモです。

オフライン評価

なぜオフライン評価が必要？

素朴な疑問として、"そもそもオフライン評価やらなきゃいいのでは？"みたいな疑問もあるかと思うので、その点から整理します。

システムに対して何かしらの機能改善のためにアルゴリズムを修正した状況を考えます。 修正したつぎのステップとしては、実際にその施策がユーザーにとってメリットがあるかを確認する必要があります。 この評価のために、A/Bテストを始めとするオンラインテストを実施しても良いんですが、できればその前にある程度良し悪しがわかればそれに越したことはありませんね。

一応調べてみると、こんな感じで書いてある記事を見つけることができます。

Part 1で行った実験は, アルゴリズムを実際のシステムで走らせた時の性能評価を想定していましたが, 実際そのように理想的なアルゴリズムの性能評価を行うことが難しい場合が多い です. 何故ならば, あるアルゴリズムを一定期間実際のサービスで走らせた上で性能を評価したいと思っても, それが性能の悪いものであったら, ユーザー体験を害してしまったりサービスからの収入に影響があるかもしれないからです. Netflixを超えていけ！Contextual Banditアルゴリズムを徹底解説！（Part 2） - Qiita

上記のように、実際にオンラインテストをリリースする前に事前にそのリリースが良さそうか、確認しておきたくなります。 そんなこんなで、多くの場合オンラインテストの前にオフラインテストが行われるかと思います。

Counterfactual (反事実)の問題

次に、推薦や検索などのランキングアルゴリズムの機能改善を行う際に、オフラインテストでどんな問題が発生するか考えていきます。

今、実運用しているランキングアルゴリズムについて何らかの機能改善をしたとします。 そして、実運用しているランキングアルゴリズムに対するユーザーのリアクション（クリックや購入など）のログが取れているので、このログを使って機能改善の前後でのランキングを評価することを考えます。

さて、このままオフライン評価するとどうなるでしょうか？ ちょっと調べてみると下記のように書かれている記事を見つけることができました。

ただしこれだと実運用時にユーザが何を見せられているかによるバイアスがかかってしまいます。 例えばユーザが推薦ロジック X を見てアクションしたことにより得られたログであった場合、アクションのあったアイテム、つまり推薦で当てたいアイテムは当然 X の出力に含まれるアイテムとなり、おそらく X に近いロジックが良いロジックであると評価されやすくなります。 レコメンデーションシステムのオフライン評価、どうやるんですか - froglog

上記の説明のように、ユーザーに表示されるアイテムの候補はすべてがユーザーに見られるわけではありません。当然ランキング上位のアイテムはユーザーの目に触れやすく、クリックや購入などに繋がりやすいです。

一方、アルゴリズムの修正によって、新しく上位に出てきたアイテムがあった場合、そのアイテムはもともとランキングが低く、リアクションされたログが残っていない可能性が非常に高いです。 そのまま両者のランキングを評価してしまうと現行のランキングアルゴリズムに有利な評価となってしまい、本来なら優れたアルゴリズムに修正されていたとしてもその価値を誤って判断してしまいかねません。

Replay推定量

さて、問題意識が大体わかったところで、本題のReplay推定量について見ていきたいと思います。

Replay推定量自体はかなり昔からある手法で、WSDM 2011の"Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms"という論文*1で提案された手法のようです。

実際に導入している事例でいうと、Netflixのブログでも紹介されており、過去には実際に使用されていたようです。（今はどんな手法を使ってるのかはわかりません…）

考え方

※この辺の解釈、個人的な理解なので間違ってたらTwitterのDMとかで教えていただければと思います。

いま問題になっているのは、片方のアルゴリズムに対してはログデータが十分に残っていて、他方のアルゴリズムについてはログが存在しないことがある、という条件が不均衡になっていることが問題になっているわけです。

考え方としては、一方だけが有利な状況ではなく、互いに不十分なロギングがされている状況を作るようにします。

Netflixのブログの例では、部分的にログを採用しています。

Artwork Personalization at Netflixより

この例では、スロットが一つの状況を考えています。 上段は各ユーザーに対してスロットに表示されるアイテムをランダムに決定し、下段は各ユーザーに対してスロットに表示されるアイテムを推薦モデルによって決められています。

このとき、上段と下段で表示されていたアイテムが一致したときだけインタラクションを採用（図中では中段、赤丸が再生されなかった、緑丸が再生された事を意味する）し、異なっていた場合には無視します。

これにより、ランダムにログを間引くようになっているみたいです。（あんまり自信ない）

アルゴリズムの確認

こちらの書籍で確認すると、こんな感じで計算するらしいです。

1. t=1からTまで、レコードを取得し、以下を実行する
   1. hを使用して候補アイテムを選択する. すなわち. ここで, は選択されたアイテムである
   2. ならば, 報酬を含める. ここで, はレコードの重みであり、後で決定する
   3. の場合, このレコードは無視される
2. 獲得報酬の合計をTで割った値を返す

この手順でやってみることにします。

まずは何も考えずに失敗してみる

とりあえず、何も考えず失敗してみます。 わかり易い例として、アイテムを配信するスロットが1つある状況を考えます。 ここに10種類のアイテムを配信する状況を考えます。 ここに対して、ランダムにアイテムを配信することを考えます。

評価指標は適合率を使っています。 この場合、もとのログではprecision=0.2になっていたものが、新しく作ったモデル（中身は全く同じ）ではprecision=0.02になってしまっています。 同じ推薦アルゴリズム（ランダム）を使用しているのに、値が大きく変わってしまっています。

やってみる

次にreplay推定量をやってみたいと思います。

コードを書くとこんな感じ。

この例では、2回の適合率は大体似たような値（1回目:precision=0.19, 2回目:precision=0.21）になっていますので、正しくオフライン評価できていそうです。

やってみてわかる問題点

replay推定量で問題になってくるのは、アイテム数が大量にある状況ではそもそもシミュレーション自体が難しくなる点です。

• 本来得られているログの件数: 100000
• 実際に使用しているログの件数
  • 1回目：9962
  • 2回目：990

ここではランダムにアイテムをピックして作られたログと過去のログを突き合わせをしているんですが、アイテムの数が多くなるにつれて、2つのランキングでアイテムが合致する確率が低くなります。 すると、シミュレーションにおいてスコアの計算対象になる部分が少なくなるので、その分大量の過去のログデータと突き合わせる必要が出てきて計算量が膨大になってしまいます。

要するに、推薦されるアイテムプールがそこそこ大きな場合にはこの手法でオフライン評価をやるのは難しそうです。 逆にアイテムプールが小さい場合にはこれでも十分うまくいきそうです。

参考文献

推薦システム: 統計的機械学習の理論と実践

netflixtechblog.com

qiita.com

soonraah.hatenablog.com

感想

正直この辺については今でも様々な研究がされており、かつReply method自体10年ほど前の論文なので、今ではもうちょっと進んだ手法があったりします。

そのへんについては、勉強したらまた記事を書いてみたいと思います。(やるとはいってない)

*1:https://arxiv.org/abs/1003.5956