Offline Evaluation of Ranking Policies with Click Models

[usaito]

0. 論文概要

Shuai Li, Yasin Abbasi-Yadkori, Branislav Kveton, S. Muthukrishnan, Vishwa Vinay, and Zheng Wen. 2018. Offline Evaluation of Ranking Policies with Click Models. In KDD ’18: The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, August 19–23, 2018, London, United Kingdom.

1. 要約

• ランキングアルゴリズムの性能をofflineで推定するための推定量の統計的性質について考察
• ユーザーがクリックに至る過程にclick modelと呼ばれる構造仮定を導入し, モデルを導入することでより効率的な推定量を構築

2. 背景

• 推薦ランキング方策の性能を測るためのgold standardはA/Bテストだが, これはユーザー体験を大きく害するため望ましくない
• ランキング方策の既存のoffline推定量は, ユーザーのクリック過程に仮定を置かないため, 良い推定性能を発揮するためには大量のログデータが必要.
• click modelが成り立つという仮定の元で, より良いoffline推定量を構築できる可能性がある

3. 手法

Notation

以上を用いて, 次のような過程でinteractionが起こるとします.

この時, コンテクストxに対する推薦ランキングAの性能を以下のように定義します.

本論文の目的は, 過去に走っていた何れかの方策πによって生まれたログデータSを用いて, 新たな方策hの性能を推定することです. 方策hの性能は, 先ほど定義したxごとの性能について, xの分布で期待値を取ったものとします.

Estimators

ここでは, 異なる仮定に基づいたいくつかのpolicy valueの推定量を紹介しています.

1. List Estimator
   List Estimatorはclick modelを導入しないbaseline推定量で, 任意のリストに対するimportance weightの推定を通して, hのpolicy valueを推定する方法です. ただ, importance weightが大きくなりすぎると, 推定量の分散が大きくなってしまうので, Mでclippingしています.

2. Item-Position (IP) Click Estimator
   IP Estimatorは, k番目にランキングされたアイテムaをクリックする確率が, そのアイテムとランキングにしか依存しないという仮定を置きます. （つまり, 推薦ランキングの他の構成要素と独立）

List Estimatorよりも, importance weightの数が少なく, logging policyとtarget policyで完全にリストが一致していないリストの情報も推定に寄与させることができるため, varianceを抑えることができると考えられます.

3. Random Click Model (RCM) & Rank-Based Click Model (RBCM)
   RCMは, クリックがアイテムにもそのランキングにも依存しないという（自己否定的な？）モデル化です.
   RCBMは, クリックがランキングのみに依存するというモデル化です.　これら仮定が成り立つならば, 任意のpolicyについて, ログデータの平均クリック率を計算することで簡単にその性能を推定することができます.

4. Position-Based Click Model (PBM)
   PBMは, click modelの中でも標準的なモデル化で, クリック確率が以下のように分解できるとします.

ここで, μはxが与えられた時にaをクリックする確率で, pはxが与えられた時にk番目のアイテムを認知する確率です. ここで全てのpositionについて認知確率が既知とすると, PBMによる推定量は以下のようにして得られます.

この推定量は, IPよりもimportance weightの数のオーダーが小さいため, varianceが小さくなると考えられますが, より厳しいPBMの仮定が成り立っていなければなりません．

5. Document-Based Click Model (DCTR)
   DCTRでは, クリック確率がpositionごとの認知確率と独立であるという条件をPBMに追加したモデル化になります. つまり, 何を推薦するかのみによって, 推薦のvalueが決定することになります. DCTRに基づいた推定量は, PBM推定量で用いられている認知確率pを全て一定にすることにより得ることができます.

・まとめ
たくさんの推定量を見てきましたが, ログデータSの大きさが小さい時は, より厳しい仮定に基づいた推定量が汎化しますが, Sが一定の大きさを持つならば, より現実的な仮定をおく方がbiasを小さくできます.

Analysis

理論分析の結果が多いので, 重要な結果のみ絞ってまとめます.

• 各仮定のもとで, 任意のコンテクストxと推薦リストAについて, importance weightがMでclipされないような方策の集合について, 仮定がきついものの集合にゆるいもののそれが包含される. 例えば,

• logging policy πが既知でありかつ, それぞれのestimatorが要求する仮定が満たされるとき, きつい仮定に基づいたestimatorの方が任意の方策のpolicy valueを推定する際のbiasが小さい. 例えば,

• logging policy πが既知であるとき, List EstimatorとIP Estimatorを最大化するような新しいpolicyを考えた時, IP Estimator最大化によって得られたpolicyの真のpolicy value下界の方が大きい.

4. 実験

Yandex datasetというものを使って性能評価していますが, このデータセットにはコンテクスト情報が含まれないため, コンテクストが全て同一であるというきつい仮定を置いています.

実験手順（あまりよくわからなかったので、間違えているかもしれません。）

• Yandexのtraining dataである27日分のデータについて, あるday dのデータを抜き出してそのデータをevaluation set, それ以外の26日分のデータをproduction setとする.
• evaluation set, production setそれぞれの推薦結果から方策を推定する（それぞれevaluation policy, production policyと呼ぶ）
• evaluation policyの性能を, production setを使って各推定量で推定する
• evaluation setで発生したクリック率をgold standardとして, 推定精度を評価する

結果は以下の通り. それぞれの図はログデータの数やKの大きさが異なる状況での結果を表している.
IP, PBM, Itemなど適度な仮定に基づく推定量がList EstimatorやRCMよりもよい推定精度を見せた.

5. コメント

• ここでは詳しく紹介していないが, 4章の不等式評価などは押さえておきたいので, 今後証明を追う
• conclusionで著者自身も触れているが, Yandexデータセットは今回の設定における推定量の評価には適さないと感じた。がしかし、publicデータセットがあまりないらしい。

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