[2019] Variance Reduction in Gradient Exploration for Online Learning to Rank

[IkokObi]

ざっくり言うと

• ランク学習をオンラインで行う場合にパラメータ更新の勾配の分散を小さく抑えるという内容
• オンライン学習は"dueling bandit"という，ランダムなアップデートによりモデルが改善するかどうかを判断しながら学習していく方法を用いる
• 1回のアップデート時に用いた文書が張る空間にアップデートの勾配を制限することで，分散を小さく抑える(Document Space Projection)
• 注意事項として，本論文で述べられている理論は線形予測モデルに対するものである

キーワード

• Online learning to rank
• dueling bandit
• variance reduction

1. 情報

論文リンク

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

著者

Huazheng Wang, Sonwoo Kim, Eric McCord-Snook, Qingyun Wu, Hongning Wang

投稿日付

2019/7/21-25 (SIGIR 2019, best paper)

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

• ランク学習を"dueling bandit"でオンライン学習する方法は，勾配のアップデートの分散が大きい
• 分散を抑える方法は提案されているが，期待値が真の勾配に一致しない手法になっていた
• 本手法は分散を抑えつつ，期待値が真の勾配に一致する

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

• 1度の検索セッションでユーザが調べる文書の数は限られているので(例えばm個)，勾配として意味のある次元はm個の基底で張れるという考え
• 勾配への制限を，"interleave test"(ユーザからのフィードバックを受ける部分)の前ではなく後につけることで，不偏推定を実現している

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

• 理論の証明
• 5つのデータセットを用いた数値実験

5. 議論はある？

• クリックのモデル化(ユーザが調べた文書のモデル化)をより洗練されたものにする

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

• Interactively Optimizing Information Retrieval Systems as a Dueling Bandits Problem
  • Yisong Yue and Thorsten Joachims
  • 2009/6/14-18 (ICML 2009)
  • https://dl.acm.org/citation.cfm?id=1553527
  • dueling banditをIRに適用した論文

[IkokObi]

7. 実装の詳細

重みパラメータwとする．特徴量はd次元で，線形モデルを考えている．

通常のDueling Bandit Gradient Descent(DBGD)

1. d次元単位球面上から更新の勾配ベクトルuを取り，w' = w + δ * uを候補とする
2. 新しい検索クエリを受けて，重みwとw'でそれぞれ検索を行い，検索結果を合わせて表示する(Interleaving methodという方法を用いる)
3. ユーザのクリック情報を用いて，wとw'のどちらがより適していたか(クリックされた文書の表示に寄与したか)を判断し，w'が勝った場合には，次の重みをw <--- w + α * uとアップデートする

Document Space Projected Dueling Bandit Gradient Descent

• 基本的には上のDBGDと同じ．
• ユーザが調べた文書を{x_1, x_2, ..., x_m}とし，調べた文書が張る空間をS=span{x_1, ..., x_m}とする．
• 上の3番目のアップデートにおいて，勾配uをSに射影した成分gを用いてw <--- w + α * gと更新する
• 射影空間Sへの射影は，調べた文書のベクトルを縦に並べたd * m次元の行列を特異値分解し，直交基底行列を用いて射影行列を作る

DSP-DGBTの特徴

• 特徴量の次元に対して，ユーザが1回に調べる文書数が圧倒的に少ないということを利用している
• 線形モデルであるがため，アップデートに有効な空間を制限することができる
• 論文内では，上記の制限した勾配が期待値として真の勾配に一致することなどを示している

[IkokObi]

8. データセット

1. MQ2007
   • 約1,700個のクエリ
   • 46次元の特徴量
2. MQ2008
   • 約800個のクエリ
   • 46次元の特徴量
3. NP2003
   • 約150個のクエリ
   • クエリに対して1000以上の文書が評価されている
   • 64次元の特徴量
4. MSLR-WEB10K
   • 10,000個のクエリ
   • 136次元の特徴量
5. Yahoo! Learning to Rank Challenge dataset
   • 約36,000個のクエリ
   • 約883,000個の文書が評価されている
   • 700次元の特徴量

Onlineのシミュレーションモデルについて

• 全文書調べるperfect user，最初の関連文書を見つけたら終わるようなnavigational user，時々関係のない文書をクリックする傾向の高いinformational userの3パターンを用意

[IkokObi]

9. 結果の詳細

• ユーザの見た文書が少なく，勾配のノイズが大きくなるような状況ではDSPを用いると精度の改善が大きい傾向にある(常に良いというわけではない)
• 他の実験でもDSPの方が精度が良いという結果が見られる

Online Cumulative NDCG@の結果

Offline NDCG@10の結果

[IkokObi]

雑感&メモ

• 線形モデルであることを活用して，更新する空間を制限するのは面白い発想
• オンラインで学習する場合の良い方向性の1つになるかも