search

nogawanogawa / paper_memo

4 stars 0 forks source link

Calibrated Recommendations as a Minimum-Cost Flow Problem #88

Closed nogawanogawa closed 1 year ago

nogawanogawa commented 1 year ago

論文URL

https://abdollahpouri.github.io/assets/docs/wsdm2023.pdf

著者

Himan Abdollahpouri, Zahra Nazari, Alex Gain, Clay Gibson, Maria Dimakopoulou, Jesse Anderton, Benjamin Carterette, Mounia Lalmas, Tony Jebara

会議

WSDM '23

近年の推薦システムでは、推薦リストにおいてユーザの様々な（過去の）関心領域が、それぞれの割合で反映されることを保証するキャリブレーションが注目されている。

image

推薦リストは、ユーザーの持つ少数派の興味が蔑ろにされたり、全体的に人気のあるアイテムに支配されたりすることが多い。

先行研究でキャリブレーションは、貪欲法によって考慮されているが、これは現実的な時間内に解を求める保証ができない。また、一般的にキャリブレーションは推薦自体の精度劣化を引き起こすことがわかっている

目的

アプローチ

image

評価

キャリブレーションしつつ、他の手法と比べて精度劣化を抑えられた

image image

ひとことメモ

spotifyの人の論文

nogawanogawa commented 1 year ago

背景

近年の推薦システムでは、推薦リストにおいてユーザの様々な（過去の）関心領域が、それぞれの割合で反映されることを保証するキャリブレーションが注目されている。

image

推薦リストは、ユーザーの持つ少数派の興味が蔑ろにされたり、全体的に人気のあるアイテムに支配されたりすることが多い。

先行研究でキャリブレーションは、貪欲法によって考慮されているが、これは現実的な時間内に解を求める保証ができない。また、一般的にキャリブレーションは推薦自体の精度劣化を引き起こすことがわかっている

nogawanogawa commented 1 year ago

目的

アプローチ

nogawanogawa commented 1 year ago

モデル化

image

最大化したい式

image

scoreの合計を最大化しつつ、ペナルティを最小にしたときに目的を達成できるものとする。

解き方

下記の様にグラフ構造を作成して、このグラフ構造における最小コストフロー問題を解くことで最適化する

image
  1. yは推薦を表示するスロットを表す
  2. tは推薦候補を表すアイテムを表す
    • 色は、カテゴリを表す
    • y, t間のエッジには重みがあり、スロットに入れることで得られる利得をマイナスにしたものを付与(これによってコスト最小問題にする)
  3. uはカテゴリを無視したアイテムを表す
    • t, u間は重みなし
  4. wは同じカテゴリ数 * スロット数のノード
    • u, wは重みなし
    • ただし、同じ第1添字と同じカテゴリのものだけをエッジとして接続
  5. snkとwはすべて結合する
    • snk, w間のエッジには重みがあり、理想的なキャリブレーション状態とその経路を通過したときの状態をKullback-Liebler divergenceでコストをつける

このグラフを構成し、すべてのyについてコストを最小にするようなパスをそれぞれ選択する（最適化問題）

nogawanogawa commented 1 year ago

評価

評価対象

Movielens、Last.fmのデータセットを用いて評価

relevanceとKL divervgenceの間の関係

image

比較対象より、同じrelevanceを得ながらもKL divervgenceが小さい（理想的なキャリブレーションに近い）

精度比較

image

ラムダによって調整できるものの、キャリブレーションをしても精度の劣化は他の比較対象よりも抑えられている。 （精度とキャリブレーションの両取りができている）

貪欲法との比較

image

（横軸がスロット数）

nogawanogawa commented 1 year ago

まとめ