usaito/CFML-papers

Position Bias Estimation for Unbiased Learning to Rank in Personal Search

usaito opened this issue · 0 comments

usaito commented

0. 論文概要

Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, Marc
Najork. 2018. Position Bias Estimation for Unbiased Learning to Rank in
Personal Search. In WSDM 2018: WSDM 2018: The Eleventh ACM International
Conference on Web Search and Data Mining , February 5–9, 2018, Marina Del
Rey, CA, USA. ACM, New York, NY, USA

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

1. 要約

  • Unbiased LTRにおけるpropensityの新たな推定方法regression-based EMを提案.

  • regression-based EMは, Result Randomization（RCTのようなもの）に頼る必要なくlogデータのみを必要とするためユーザー体験を害する心配がない.

  • 実験では, Result Randomizationがどれほどnegativeなユーザー体験をもたらすかを示した後で, regression-EMが精度よくpropensityを推定できることを示した.

2. 背景

  • 既存のUnbiased LTR手法（関連研究を参照）は, propensityの推定によりpresentation biasをdebiasできるが, propensityの推定はresult randomizationに頼っていた.

  • result randomizationは, 一定期間, 上位N個の枠をランダムに表示することでpropensity（の比）を推定することができる方法である. しかし, 上位N個の枠をランダムに表示することは明らかにユーザー体験を害する. よって、randomizationなしでpropensityを精度よく推定できる方法が望まれる.

3. 手法

まず, 以下のようにPosition Bias Modelを仮定する. つまり, あるqueryに対して, あるdocumentがk番目に表示された時にクリックされる確率は, k番目に表示されたdocumentが認知される確率と, そのquery-documentのペアが関連している確率の積で表されるというもの.

2018-12-15 18 23 45 2

ただし, 以降はEの期待値とRの期待値について以下の表記を使う.
2018-12-15 18 36 11 2

一旦整理すると, 論文の主題はrandomizationなしで\theta_kを推定したいというものだった. ここで,
(click, query, document, position)の形で蓄積されているログデータの対数尤度は以下のように表せる.

2018-12-15 18 36 20 2

この対数尤度を最大化するパラメータを推定するためのEMアルゴリズムは以下のように表せる. (少し考えたらやってることはすぐわかる.) ちなみに, この辺の計算は, C=1ならばE=1かつR=1という仮定に基づいている.

  • Eステップ
    2018-12-15 18 36 29 2

  • Mステップ
    2018-12-15 18 36 34 2

しかしquery-documentペアを特定するのは, プライバシー云々の理由で難しいため, Mステップの2番目の式を計算するのは難しいという話がここでいきなり出てくる.（あまりよくわからなかった.）

よって, Mステップの\gamma_{q, d}をGBDTで予測する方法をregerssion-based EMとして提案している.
アルゴリズムは以下の通り. EMアルゴリズムの前のステップのGBDTの予測値を次のステップのGBDTの入力の一部として使うことでことで, 急激なrelevanceパラメータ推定の変化を防ぐ.

2018-12-15 18 36 40 2

4. 実験

主に以下の3つの点について, EMailとFile Storageの検索データログを使った実験.

  1. Result Randomizationを使った時のユーザー体験の損失について
  • production trafficのMRRからのRandomizationを使った時のMRRの相対改善度. マイナスが大きいとユーザー体験を害していることになる.

2018-12-15 18 50 31 2

  1. regression-EMを使った時のpropensity推定精度
  • Result RandomizationをGold Standardとして, 他のナイーブな推定方法とregression-EMを比較した. regression-EMによる推定の精度がほとんど全てのpositionで良かった.

2018-12-15 18 51 08 2

  1. regression-EMを使った時のrelevance推定精度
  • IPWによる補正を用いない予測(NoCorrection), Randomizationを用いたIPWによる予測(RandPair), regression-based EMによるIPWによる予測(EM)の精度比較. 評価指標はWeightedMRR.
  • File Storageデータでは全て横並びだったが, EmailデータではIPWによる補正が大きく効いた. また, EMによる補正はRandomizationによる補正に近い精度を示した.

2018-12-15 19 04 42 2

5. コメント

  • この辺の実務事情を知らないため, query-documentペアを特定するのが難しいのかよくわからなかった. これがデータとして使えるならば, 通常のEMを回せば良いので.

  • regression-EMでやっているrelevanceパラメータをGBDTで予測するパートだけど, それがそもそもUnbiased LTRでやりたいことなので, regression-EMのアルゴリズムで精度よくpropensity推定できるならそもそもpropensity推定のこと考える必要ないのでは？という本末転倒な感じがした...

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

  • Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017. Unbiased
    Learning-to-Rank with Biased Feedback. In Proc. of the 10th ACM International
    Conference on Web Search and Data Mining (WSDM). 781–789