[2019] A General Framework for Counterfactual Learning-to-Rank

[IkokObi]

ざっくり言うと

• 反実仮想的ランク学習の一般的な理論的枠組みを示した
• 表示バイアスも考慮した上で目的関数の不偏推定量を示し，その最適化として定式化
• SVMの場合の理論及び，DNNの場合のアプローチを紹介
• ベンチマークデータセットで提案手法の有効性，頑健性を示した

キーワード

• IR
• Learn-to-rank
• counterfactual

1. 情報

論文リンク

https://dl.acm.org/citation.cfm?id=3331202

著者

Aman Agarwal, Kenta Takatsu, Ivan Zaitsev, Thorsten Joachims

投稿日付

2019/7/21-25 (SIGIR 2019)

2. 先行研究と比べてどこがすごい？

• 反実仮想的学習の逆傾向スコアに関して，平均ランク値の場合の理論を他の指標(DCG等)にも拡張して理論を展開
• SVMだけでなく，DNNでも有効性を実証

3. 技術や手法のキモはどこ？

• ランク学習で用いられる代表的指標を考慮して，様々な指標を含むような形で不偏推定量の定式化を行なった点
• 学習時に目的関数を直接最適化することを可能にした

4. どうやって有効だと検証した？

• Yahoo Learning to Rank Challenge及びLETOR4.0で検証
• 他のランク学習手法よりも高い精度を達成

5. 議論はある？

• 微分不可能な木モデルにも対応させられるかどうか

6. 次に読むべき論文は？

• Unbiased Learning-to-Rank with Biased Feedback
  • Thorsten Joachims, Adith Swaminathan, Tobias Schnabel
  • 2016/8/16 (WSDM 2017)
  • https://arxiv.org/abs/1608.04468
  • メインとなる先行研究で平均スコア値の場合の理論を導出した論文

[IkokObi]

7. 実装の詳細

1. 最適化の目的関数について

1. ランク学習の目的関数の一般的な表現

   

2. λ(rank)が評価指標に対応する関数で，次のような対応関係にある

   

3. ポイントは，次の値が式(1)の不偏推定量になっているということ． 式中のr_i(y)=1はクエリx_iに対して表示した文書yがクリックされたことを表し，o_i(y)=1はクエリx_iに対して文書yがユーザからのフィードバックを受けたか否かを表す（例えばページの下方まで見られていない場合o_i(y)=0となる）．

4. 分母に来ている関数Qは傾向スコアを表しており，これはモデル化や推定する必要がある．ランクに依存した傾向スコアとして，論文中では次の関数が使われている．

   

5. 最終的な目的関数は次の式(5)

   

2. 目的関数の上限について

1. 文書の表示順位について，次のようにして上限を与えることが出来る． 具体的に4番目に表示された文書等を当てはめると分かるが，結構上手い変形だと感じた．

   

2. 上の上限を用いてλ(rank)関数の中のrank部分を上から押さえ，かつ関数λ(rank)が単調増加関数であることを用いて(表1の中の関数は全てそうなっている)，次の上限を最小化する問題に置き換える．

   

3. SVMとNNの最適化について

• SVMの場合については厳密に最適化の手順を導出している
• NNの場合には検索クエリに対する表示結果全部を1セットとし最適化することで不偏推定量が崩れない，ということを用いて最適化することを提案している
  • ListNet的な学習に近いと思われる

[IkokObi]

8. データセット

• 上のデータセットは全表示文書に対してフィードバックが与えられているため，表示バイアスをモデル化してtoyデータを作成し，検証している

[IkokObi]

9. 結果の詳細

• データ数や表示バイアスのモデル化関数のパラメータを変化させての解析等も行なっている
• SVM PropRankよりもSVM PropDCGの方が精度及び頑健性で優れている
• クリックデータ数が多い場合にはSVMよりもDeepの方が良い結果に

[IkokObi]

雑感&メモ

• ランクの最適化するという目的は変わらないが，DCGを直接最適化出来るというのは嬉しい