【論文メモ】User Behavior Simulation for Search Result Re-ranking
情報
タイトル
User Behavior Simulation for Search Result Re-ranking
概要（三行で）
- （機械学習全般で）人手でのオフライン評価のアノテーションのコストが高い
- オンラインに近いモデルの学習・評価・推論を行うためユーザ行動シミュレータ作成
- Webの検索結果の並び替えに上記ユーザ行動シミュレータを使用
ジャーナル・発行日
ACM Transactions on Information Systems, Volume 41, Issue 1
（20 January 2023）
リンク
提案手法
User Behavior Simulation for Reinforcement Learning (UBS4RL)
この論文では、後述するContext-aware Click Simulator (CCS)とFine-grained User Behavior Simulator with GAN (UserGAN)というユーザ行動シミュレータを用いて、Webの検索結果を並び替えるシステムであるUser Behavior Simulation for Reinforcement Learningの提案をしている。
システムの全体像は画像の通りで、具体的な流れとしては、
- 検索結果を適当な並びで取得
- 視覚・テキスト・構造の情報をベクトル（埋め込み表現に変換）
- 実際のユーザログから学習させたUserGANでクリック有無・時間・場所の情報を予測
- 予測結果に伴って"Ranking Agent"（強化学習モデル）で検索アイテムの並びを最適化
※ "Ranking Agent"は最適化途中の並びも状態として"User Simulator"に送る。
のようになっている。
特徴としては、
- ユーザ行動の予測を行うため、オンラインに近いモデル学習・評価が行える
- Webの検索結果に限らず、「ユーザ行動シミュレータを使った強化学習」は
他のタスクに対しても使用できるため、フレームワークとして見ることが出来る
の二点が大きい。
Context-aware Click Simulator (CCS)
CCS: Context-aware Click Simulatorはbi-GRU（時系列データ処理に使用するNN）を用いた深層学習モデルで、検索アイテムに対するクリック・スキップのみを予測する（クリック確率の予測）。
第一段階（図中の"Session Level"）で、検索結果（埋め込み表現に変換）を順番に並べたものを時系列データの入力値として、それらを圧縮した埋め込み表現を得る。
第二段階（図中の"Result Level"）で、（1）第一段階の出力（全体の埋め込み）、（2）以前のクリック情報、（3）各検索アイテムの埋め込み、を合成したものを入力とする。出力は各検索アイテムに対してのクリック・スキップの行動となっている。
Fine-grained User Behavior Simulator with GAN (UserGAN)
こちらもユーザ行動シミュレータだが、CCSとは違いクリック時間・空間の情報も併せて予測を行うため、よりきめ細かい行動のシミュレートが可能となる。
"Modulator"（変調器）にて離散値のクリック時間・空間をガウス分布に変換し、その分布と検索結果（SERP）の埋め込み表現をGANの"Discriminator"（識別機）の入力にする。また、"Generator"（生成器）にてランダムシード的なもの？（Noise）と検索結果（SERP）を入力として分布を生成し、それも"Discriminator"に入力する。そうすると、Discriminatorでその入力がユーザログなのか、生成したものなのかを判別し、それが判別できなくなるようなGeneratorを目指して学習する。
（基本的なGANの構成と同じ）
ユーザ行動は実際に以下のようなガウス分布に変換される。
ユーザが検索アイテムの1, 3, 6, 9番目をそれぞれ10, 20, 80, 30秒でクリックした場合の例となっている。
関連研究
関連研究にいろいろ書いてあって助かる。
Recently, many works have applied RL methods for ranking tasks [60, 67, 75, 76]. Oosterhuis and De Rijke [60] adopt the RL approach to deal with complex ranking settings, which learns both the user preferred document order and displays the position order for result presentations. The page presentation optimization of SERPs has also been recast as an RL problem in the work of Wang et al. [75]. Wei et al. [76] formulate the ranking problem as an MDP to optimize the evaluation measure calculated at all positions. Some work has adapted RL for complex online system optimization [67], in which a virtual retail platform to train ranking policies offline is constructed. Assuming that the environment is static, inverse RL methods [56] can learn a reward function from the data and train policies according to the reward function.
ランキング問題をMDP（マルコフ決定過程）をとして定式化し、強化学習で解く研究がいろいろ書いてある。しかも、最後の方には「ランキング問題のオフライン評価が難しいので、仮想的な小売プラットフォームを再現している」というのもある。
ここら辺も面白そう。
気になるところメモ
データセット作成方法について
First, previous works only use human-annotated relevance labels to learn a ranking policy. However, human annotations are very expensive.
以前は人間によるアノテーションを行っていたようで、その際にコストが高かったと書いてある。ユーザの行動ログを教師データとして使うことも考えられるが、あくまでそれは「過去のある行動に対しての結果」であってそのまま使用するのはあまり良くないと思う。
今回のユーザ行動シミュレータを言い換えると、「過去ログからこんな感じの検索結果にしたらこういう行動をする」っていうログ＋ユーザ行動予測をしていることになる。そのため、ユーザ行動の予測をせずにそのままログを使うのは危なそう。
オフライン評価指標について
Third, previous works only optimize offline evaluation metrics such as NDCG (normalized discounted cumulative gain) [64]. However, online evaluation metrics such as CTR (click through rate) and MRR (mean reciprocal rank) may align better with user satisfaction [17] and are widely adopted in search engines. In this work, the proposed UBS4RL framework can optimize both offline and online evaluation metrics.
これをほんとそうだと思う。
NDCGなどのみでオフライン評価をしてしまうと、オンライン検証でモデル性能が良くなかった場合に検証する場所が（1）モデル自体の性能、（2）モデルの目的変数とビジネス指標の乖離、の二つに増えてしまうので、調査＆対策に余計な時間がかかってしまうし、最悪の場合、問題の切り離しができないこともある。
Discussion