Offline Evaluation of Ranked Lists using Parametric Estimation of Propensities

[nogawanogawa]

論文URL

https://arxiv.org/abs/2206.02470

著者

Vishwa Vinay, Manoj Kilaru, David Arbour

会議

SIGIR 2022

背景

ランキングシステムの評価では、ランカーへの変更の効果を検証したい際のデファクトスタンダードとして採用されてきた。しかし、システムの変更がユーザーエクスペリエンスを低下させ、その結果、変更にさらされたユーザーにマイナスの影響を与える危険性がある。

そのような懸念から、ユーザーの過去のインタラクションデータを使用したオフラインA/Bテストが研究されてきた。しかし、オフラインテストでは変更の効果について、偏りのない推定値を偏った過去のデータを使って得る必要がある。 収集されたデータは、以前に決定されたランク位置に提示されたアイテムに対するユーザーのインタラクションのみであるため、偏りがある。 さらに、ユーザーは上位のアイテムをより好むなど、固有のバイアスがあることも知られている。

目的

• 既存手法であるIPWよりロバスト（低分散）かつ正確（低バイアス）な評価を可能にする

アプローチ

• learning-to-rankをサブルーチンとして利用するオフライン評価
  • 過去のクリックスルーデータで観測されたランキングを模倣する模倣ランカー(Imitation ranker)を訓練する
  • 与えられたクエリに対してある文書がある順位で観測される確率を使用してパラメトリックに指標を推定

[nogawanogawa]

背景

ランキングシステムの評価では、ランカーへの変更の効果を検証したい際のデファクトスタンダードとして採用されてきた。しかし、システムの変更がユーザーエクスペリエンスを低下させ、その結果、変更にさらされたユーザーにマイナスの影響を与える危険性がある。

そのような懸念から、ユーザーの過去のインタラクションデータを使用したオフラインA/Bテストが研究されてきた。しかし、オフラインテストでは変更の効果について、偏りのない推定値を偏った過去のデータを使って得る必要がある。 収集されたデータは、以前に決定されたランク位置に提示されたアイテムに対するユーザーのインタラクションのみであるため、偏りがある。 さらに、ユーザーは上位のアイテムをより好むなど、固有のバイアスがあることも知られている。

[nogawanogawa]

目的

• 既存手法であるIPWよりロバスト（低分散）かつ正確（低バイアス）な評価を可能にする

アプローチ

• learning-to-rankをサブルーチンとして利用するオフライン評価
  • 過去のクリックスルーデータで観測されたランキングを模倣する模倣ランカー(Imitation ranker)を訓練する
  • 与えられたクエリに対してある文書がある順位で観測される確率を使用してパラメトリックに指標を推定

[nogawanogawa]

IPWとその拡張

List一致

ログデータセットを使用した新旧のランキングの評価を行う1つの方法に、よく研究されている逆性向重み付け（IPW）を使用する方法がある。 IPWを適用した場合の推定値は下記のようになる。

この式では新旧のランキングが出力したリストが同じ場合にのみメトリクスの計算対象となるようになっており、使用可能なログが非常に少なくなってしまう。

document一致

List一致の方法では、出力するランキングが一致する場合のみを使用するため、使用可能なログが減ることで分散が大きくなってしまう。 これに対応するために、同一のクエリq・ランクkに同じドキュメントdを含むタプル{d, k, q}が含まれるものをすべて評価対象とする。 ※同じクエリであってもk番目に位置するドキュメントd'は、FBループによって変化する可能性がある。1度でもd=d'となっていたら、その{d, k, q}は使用するものとする。

ただし、このやり方は、すべてのドキュメントがすべてのランクに同じ確率で配置されうることを前提に考えられている。 しかし、それは一般的には発生し得ない。

提案手法

提案手法では、クエリqが与えられたとき, ドキュメントdがランクkに位置する確率を考える。（下図右端）

この出現確率を使用して、document一致のIPWを適用することで、ドキュメントのランク別での出現確率を考慮した状態でランキング自体の性能を評価する。

[nogawanogawa]

模倣ランカー

模倣ランカーはクエリqとドキュメントdを入力にスコアを出力する関数で、ここではRankNetを使用してこれを実現することを考える。 このときの目的関数は下記のようになっている。

これを学習したランカーを用いて、K x Kのマトリクスを作成する。

クエリごとに行列を作成し、行方向にドキュメント、列方向に順位を表し、要素は傾向(propensity)を表す。 このとき、各ログデータに対して、下記の式によって、値の更新を行う。

ドキュメントの数だけ更新を行い、先頭から, 1つ順位がt-1のときに順位がひとつ下のWの値とpを用いた加重平均によって更新していく。

※やり方はこれだけではないし、あくまで一例に過ぎない。LTRのscoreを使用してより分散の少ない評価を行うのがこの論文の主題

[nogawanogawa]

評価

• Yahooデータセットに含まれる明示的な関連性ラベルを2値ラベルに変換して使用
  • 3以上の評価を1に、それ以外を0に置き換え

ground truthに近い値を推定できているので、良いとしている。