appricot’s diary

日々の勉強のメモ

Offline Evaluation to Make Decision About Playlist Recommendations Algorithms ==> 読後メモ

論文メモ 企業事例 因果推論 機械学習 Recommender System Off-Plicy Evaluation

論文

https://pchandar.github.io/files/papers/Gruson2019.pdf

Spotifyの中の人による、オフラインでのレコメンドエンジン評価方法に関する論文。

Off-policy Evaluationの実例を勉強したいな・・と思い、選択。

 

背景

  • オフライン評価の問題点は、オンライン評価(ABテスト等)と、結果が異なる場合があること。
  • なぜなら、過去データには、様々なバイアスが含まれているため。
    • Position Bias、Popularity Bias、Selection Biasなど
    • 既存のレコメンドエンジンの影響
  • この論文では、オンラインでのABテスト結果を予測できるようなオフライン評価方法を提案・検証。

 

問題設定

  • X: Context
    • レコメンドにアクセスしたユーザのデモグラ、アクセスタイミング、そのユーザの過去の閲覧作品など
  • C: レコメンドされる作品
  • f(c, x): Reward
    • Impression-to-stream
    • レコメンド結果をユーザが見て、かつ、レコメンドされた作品をユーザが30秒以上再生したら1。さくなくば0。
    • 論文内では、rとも表記。
  • π(c, x): Policy
    • ユーザXに、作品Cをレコメンドする確率。
    • Xに対して、πが最大であるような作品Cをレコメンドすることが、Action。
  • Total reward V = Σ_i f(c_i, x_i) π(c_i | x_i) を最大化するようなPolicy πを決定したい。

 

提案手法

  • 過去n期間のログを用いて、Total reward Vを求めたい。この過去ログは、既存のPolicy μ(c, x)を回すことで、得られたもの。その上で、既存Policy μに代わり、Total reward Vを最大化するような新たなPolicy πを決定したい。
  • しかし、過去ログは、既存のPolicy μによるBiasがかかっているので、このBiasを除いたVを計算する方法として、３つの方法を提案。
  • IS: The inverse propensity score estimate / Importance sampling estimate
    • V = (1/n) Σ_i r_i * π (c_i | x_i) / μ (c_i | x_i)
    • π (c_i | x_i) / μ (c_i | x_i)は、Propensity weight。
    •  推定されたVは、既存Policy-μでのレコメンド確率と新Policy-πでのレコメンド確率の比を、Rewardにかけたもの。
    • 既存エンジンがレコメンドする可能性が高い作品では、Rewardを低く評価。これにより、既存エンジンが過去データに与えている影響を除く。逆に、新エンジンがレコメンドする可能性が高い作品では、Rewardを高く評価。
    • Varianceが高い。
  • CIS: Capped importance sampling estimate
    • Propensity weightを、最大値でキャップする。
    • 例えば、あるユーザに、ある作品をレコメンドする確率が、既存エンジンで0.001で、新エンジンで0.5の場合、Propensity weightは500と、とても大きな値になってしまう。そうなると、Dataがスパースな場合に、Propensity weightがかなり低い作品が、想定以上に、Vに影響を与えてしまう可能性がある。これを防ぐのが目的。
    • Varianceを低く抑える効果。
  • NCIS: Normalized and capped importance sampling estimate
    • CISで計算したReward-Vを、Propensity weightの平均値で割る。これはNormalizationに相当。
    • Varianceを低く抑える効果。

 

評価実験の方法

  • 12個のレコメンドエンジンπを用意。その上で、以下３種類のデータを用意。
    • これら12個のエンジンを、オンラインで走らせた結果を用意。
    • 既存のレコメンドエンジンμを、オンラインで走らせた結果。
    • (Shuffled Data) ランダムに作品をユーザに提示した場合の結果。
  • オンライン実験の結果
    • 12個のエンジンを、Impression-to-stream rate (CTRのようなもの。レコメンドエンジンを見た人に占める、レコメンドされた作品を再生した人の割合）の優劣で、ランク付け。
  • オフライン実験の結果
    • 12個のエンジンを、Total reward Vで、ランク付け。

 

評価実験の結果

  • オフライン実験で、Total reward Vを、CISとした場合。かつ、オフライン評価に用いる過去データを、既存のエンジンをまわした場合とした場合。
    • Propensity weightのキャップ値が100万の場合
      • オンライン評価とオフライン評価の相関は、0.424
    • Propensity weightのキャップ値が100の場合
      • オンライン評価とオフライン評価の相関は、0.33
  • オフライン実験で、Total reward Vを、NCISとした場合。かつ、オフライン評価に用いる過去データを、既存のエンジンをまわした場合とした場合。
    • Propensity weightのキャップ値は10万の場合 
      • オンライン評価とオフライン評価の相関は、0.636
  • オフライン実験で、Total reward Vを、ISとした場合。かつ、オフライン評価に用いる過去データを、Shuffled Data とした場合。
    • オンライン評価とオフライン評価の相関は、0.394
  • NCISが最良。つまりNormalizationが大事。また、Propensity weightのキャップは小さくしすぎると、オフライン評価の精度を下げてしまうので、ある程度、大きく保つ必要がある。

 

レコメンドエンジンπの作り方に関する考察

  • πをつくる際、(1)のパフォーマンス (Impression-to-stream ratio)が最良。
    • (1) 過去データからNCISを用いてBiasを除去したデータで訓練
    • (2) Shuffle Dataを用いて訓練
    • (3) 過去データをBias除去しないままのデータで訓練

 

Impression

  • 「過去のエンジンなり施策の影響がある過去データしか手元にない状況で、新エンジン・施策のオフライン評価をしないといけない・・」というのは、現実的に、よくある状況。その場合の対応策が具体的にまとめられていて、勉強になった。
  • 単にPropensity Weightを考慮したのみ(IS)で、かつ、既存エンジンのログデータを用いた場合の結果（最も単純なケース）がどうなるのか、論文内で見つけられず。その場合のオフライン評価の精度がどうなるのか、気になる。
  • CISやNCISにおいて、キャップとなる値をいくつに設定すべきか・・は疑問が残る。おそらく実用上、悩むことになりそう。
  • Shuffled Dataでオフライン評価をしたり、レコメンドエンジンを訓練した場合の結果があまりよくなかったのは、意外。これは、Shuffled Dataのサンプル数が小さいことが、関係しているか・・