Unbiased Offline Recommender Evaluation for Missing-Not-At-Random Implicit Feedback

[usaito]

0. 論文概要

Longqi Yang, Yin Cui, Yuan Xuan, Chenyang Wang, Serge Belongie, and Deborah Estrin. 2018. Unbiased Offline Recommender Evaluation for Missing-Not-At-Random Implicit Feedback. In Twelfth ACM Conference on Recom- mender Systems (RecSys’18)

** 図表は全て本論文からの引用です.

1. 要約

• Implict Recにおいてよく用いられているAverage-Over-All (AOA) はMAR環境ではunbiasedだが, MNAR環境でbiasを持つことを示した.
• 実データはMNARであることを実験パートで確認.（つまり, AOA使ったらほとんどの場合biasが発生することを確認.）
• AOAを代替するMNAR環境でUnbiasedなOffline評価指標を提案.
• 4つのデータセットを用いた実験で, 提案評価指標がAOAよりも小さいbiasで評価値を推定.

2. 背景

• Implict Feedbackに基づいたRecommendationアルゴリズムは多く提案されており, それらの評価はA/Bテストがハイコストであることから, Offlineで行われることが多い.

• これまで, Implicit RecにおけるOffline評価は, Missing-At-Random (MAR) を仮定した元で, 全てのログデータを等価に扱い評価値を計算するAOAが用いられてきた.

• しかし, ほとんどの実データは, popularity biasやpresentation bias, interaction biasによりMissing-Not-At-Randomであると想定される. （実際実験パートで確認している.）

• Explicit FeedbackにおけるMNAR環境下においてもUnbiasedなOffline評価指標は提案されているが, Implicit Feedbackに対応する手法は, 現在まで存在しない.

3. 手法

• Z_{u, i}をある方策が, ユーザーuにアイテムiを推薦する順位とする. この時, このランキングを入力とする評価関数をcとする. cは例えば, AUCとかなんとか@kのこと. この時, 真の評価値は以下のように定義される.

• しかし, この値は現実には計算不可能である. 何故ならば, ポジティブなinteractionが起こる全てのユーザーとアイテムの組み合わせが観測されるわけではないからである. ここで, ユーザーuとアイテムiのpositiveなinteractionが観測されるか否かを表すbinary確率変数をO_{u, i}としておく.

• これまでのImplicit Recの評価には, 以下のAOA evaluatorが用いられてきた. これは, 観測されているpositive interactionについて, 単純にcによる評価値を平均するものである.

• しかし, 後に実験パートで確認するように, popularity biasやpresentation bias, interaction biasといったbiasによって, 全てのpositive interactionが一様に観測されるという仮定は非現実的である.
  より現実的なO_{u, I} = 1となる確率 (propensity) がuやiに依存して変化するMNAR環境においては, AOAによる評価はbiasを持ってしまうことが示される.

• ここで, 因果推論でよく用いられる (IPS: Inverse Propensity Scoring) の考え方を用いると, 以下のようなUnbiasedな評価指標を作ることができる. P_{u, i}がuとiについてのpropensity.

不偏性の証明:

• しかし, 実際には分散を抑える目的で, 以下のSNIPSを用いると良いとされている.
  

• 以上の不偏性が成り立つのは, 真のpropensityがわかっているときのみである. しかし, 真のpropensityは一般に不明であり, なんらかの方法で推定してあげる必要がある. ここから, propensityを推定するための仮定のオンパレードになる. （この辺りが今後の研究の１つの焦点になるだろう.）

• propensity推定のための仮定たち

  • 仮定1: propensityはuserに非依存（え...）
  • 仮定2: user非依存のpropensityは, itemがレコメンドされる確率と, interactionが発生する確率に分解できる.
  • 仮定3: interactionが発生する確率は, itemの真のpopularityに依存する.
    （観測されないものも含めた全てのpositive interactionの数）
  • 仮定4: itemがレコメンドされる確率は, そのitemについてのpositive interactionが観測される数と\gammaに依存するべき乗分布に従う.

• 詳しくは, 論文を参照していただきたいが, これらの仮定の元で, データとアルゴリズムごとに仮定4でおいたべき乗分布のパラメータを推定する.

4. 実験

• 使用データセット
  • citeulike: 記事を保存するかどうか
  • tradesy:商品を買う or ほしい物リストに入れるかどうか
  • amazon book: 本の商品購入

1. popularity biasについての考察

• interaction bias（ユーザーはより人気のアイテムとinteractionしやすい, presentation bias（より人気のアイテムが推薦されやすい）が本当に存在するのかを実データを用いて検証する.

• fig2は, 左からpositive interactionが多いアイテムから順に並んでおり, 縦軸がそのinteractionの数を表している. 横軸はlog-scaleなので, どのデータセットも大きなpopularity biasが存在することがわかる. 例えば, citeulikeだと100回以上のinteractionが観測されるアイテムは全体の1%程度.

• fig3は, 4つのアルゴリズムで学習した際に, アイテムごとにレコメンドされる回数（全てのユーザーについてTop50のレコメンドに入る回数）をアイテムごとの観測回数の関数としてplotしたもの. これも横軸がlog-scaleになっていることから, 観測回数が多いアイテムほどたくさんレコメンドされる様子が見て取れ, presentation biasが存在することを示す.

2. SNIPSによるoffline評価の精度の検証

• AOAが性能を過大評価している可能性の検証
  1でも用いた3つのデータセットに対して, 4つのアルゴリズムの評価をofflineで推定.

全ての推定において, AOAが提案評価指標よりも大きな評価値を推定した. この結果から, AOAがアルゴリズムの性能を過大評価している可能性が示唆される.

• gold standardとの比較
  Yahoo music datasetを使って提案評価指標の精度を検証. このデータセットはランダムな推薦により集められたテストデータを有するため, Offline評価指標の精度評価のbiasを評価することができる.

全てのアルゴリズムの評価に関して, 提案手法を使うことによりbiasの小さい評価が可能となっている. また, \gammaの推定値にロバストであることも確認され, propensityの推定誤差はある程度許容可能である.

5. コメント

• 初見時は関連論文とやっていることが変わらないと思ったが, Implicitだとデータの観測とユーザーの認知は同値
  ではないため, propensityの推定がImplicit Recの方がより難しいという違いが大きいのではないかと感じた.

• 著者も書いているが, propensity推定のための仮定がとても多い. 今後この仮定が満たされない状況において, どれほど推定誤差が生じてしまうかは検証されるべき. （人工データなど使って）

6. 関連論文ピックアップ

• Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and
  Thorsten Joachims. 2016. Recommendations As Treatments: Debiasing Learning and Evaluation. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48 (ICML’16). 1670–1679.