Pigooosuke
rss
Blog
About

Global or Local: Constructing Personalized Click Models for Web Search

概要

検索において提案されている様々なクリックモデルはユーザーの関連性判断や行動パターンが同質的であるという仮定を置いている。今回、Click Model Personalization framework (CMP)を提案し、特定のユーザーやクエリにおいてパーソナライズすることで性能向上を達成した。

今回の論文はクリックモデルに関する話で、L2R(learning to rank)とか、two-phase/two-stage検索(検索候補を取得したあとにリランキング)、transformerでembeddingを取ってsemantic searchとかの話題は出てきません。

そもそもクリックモデルとは

検索ログデータによって学習されるクリックの確率モデル

ex1) カスケードモデル

my image

検索結果のうち、アイテム3でクリックされたということは、 ユーザーの評価は、アイテム3>アイテム1,アイテム2 であり、アイテム4,アイテム5は比較検討もしていないという前提でモデリング。

参考: https://www.m3tech.blog/entry/cascade-model-bandits

ex2) dynamic Bayesian network

検索結果全体に対して、ドキュメントの類似度も評価に加える。 例えば、アイテム1,2のクエリ適合度(クエリマッチ度)が高かった場合に、アイテム3がクリックされる確率は低くなる。また、アイテム1,2のクエリ適合度が低かった場合に、アイテム3がクリックされる確率は高くなる、といった条件をモデリング。

参考: https://www.researchgate.net/publication/200110389_A_dynamic_Bayesian_network_click_model_for_web_search_ranking

ex3) Dependent Click Model

クリックしたアイテムに満足しなければ検索に戻り、別の検索候補をクリックする。（複数回クリックが発生する）

参考: https://www.researchgate.net/publication/221520228_Efficient_multiple-click_models_in_web_search

参考までに、こういうライブラリがあります

https://github.com/markovi/PyClick

上記で挙げた例のように、色々なクリックモデルが提案されているが、基本的にクリックモデルはクエリと検索結果の組み合わせによる評価によってモデリングされたもので、クリックモデルをパーソナライズ化（ユーザーの特徴を考慮）させた先行研究はあまりない。（多少あるが実用的なものはない）

また、上記のモデルのようにユーザー行動について様々な前提が考えられる中でいずれかの判断（検索結果の選択）をしており、一律でユーザー行動を定義するのはベストな選択ではない。

グローバルモデルとローカルモデル

my image

グローバルモデル: 全ユーザーの行動ログからモデルを作成

  • pros: データ量が多く、予測精度が高い
  • cons: ユーザーごとで行動にばらつきが大きい場合に予測精度が下がる

ローカルモデル: 各ユーザーの行動ログだけでモデルを作成（他のユーザーのログは見ない。学習において干渉されない）

  • pros: ユーザーごとの行動の特徴を捉えることができる
  • cons: データ量が少なく、予測精度が低い

この論文では、パーソナライズモデル=ローカルモデルとして表現している。

今回提案のモデルの概要

モデルは2つのパラメータを持つ

  • behavior-related: 行動確率(ドキュメント評価、閲覧継続性)
  • relevance-related: 適合確率(クエリに対するドキュメント類似度判定)

2つのパラメータについて3つの最適化戦略が考えられる。（どれが最適？）

  • behavior-relatedだけを最適化
  • relevance-relatedだけを最適化
  • 2つを同時に最適化

パーソナライズするべきか（いつ最適？）

  • 貪欲戦略(greedy): 過去に同じクエリを実行していた時にパーソナライズ(ローカルモデル)を採用
  • 慎重戦略(prudent): 過去に同じクエリを実行しており、そのデータにおいてパーソナライズ(ローカルモデル) > グローバルモデルの場合に、パーソナライズ(ローカルモデル)を採用
  • 神託戦略(oracle): ローカルモデルとグローバルモデルの予測精度の高い方を採用（理想的な状況を想定。精度上限として利用。事前計算が出来ないから実用性はない？）

実験データセット

商用検索エンジンにおける1249ユーザー分の検索ログを利用

  • ログ期間: 2020/3/20 - 2020/9/20
  • 検索利用が3ヶ月以上続いているユーザーに限定 。かつ未利用期間が30日未満まで
  • 期間中に100回以上の検索利用実績がある
  • 1日に100回以上検索するユーザーは除外(クローラーとして判定)

train/test: 時系列で3:1の割合で分割

評価指標

Perplexity, LogLikelihood: うまく予測出来るかを計測

Perplexityが小さくて、LogLikelihoodが大きければ予測精度が高い

クリックモデルで使う変数の定義

クリック確率: P(Ci=1)P(C_i=1)

閲覧(行動)確率: P(Ei=1)P(E_i=1)

適合確率: P(Ri=1)P(R_i=1)

閲覧確率(閲覧される表示位置か)と適合確率(クエリに対してドキュメントが相応しいか)はそれぞれ独立しており、以下のように設定できる。

P(Ci=1)=P(Ei=1)P(Ri=0)P(C_i=1) = P(E_i=1)P(R_i=0)

モデルは、閲覧確率と適合確率を予測してクリック確率を算出するのが目的

閲覧確率は表示位置のみに依存する 適合確率はクエリとドキュメントの関連性のみに依存する それぞれは独立

今回利用するクリックモデル

  • PBM: 上で説明したように閲覧確率と適合確率を予測してクリック率を予測するモデル
  • UBM: 最後にクリックされた位置から割り引いて、それぞれのドキュメントのクリック率を予測するモデル
  • DCM: 複数クリックが発生することを前提に、それぞれのクリックが互いに影響を及ぼしているという仮定を持つモデル
  • DBN: 検索候補間のドキュメントの適合度がクリック率に影響を及ぼすという仮定を持つモデル

検証内容

Q1. どのパラメータ最適化戦略が優れているか（=行動か適合度か）

Perplexityが小さくて、LogLikelihoodが大きければ予測精度が高い

my image
- 行動確率を最適化(CMP^B)する戦略を取るとbaseline(NOP)を大きく上回る。 - 適合度の最適化をする場合は戦略によって精度低下につながる(queryとdocumentの類似度はそもそもpersonalize化できず、データ量の少なさによるデメリットが影響してそう)

Q2. どのタイミングでパーソナライズしたほうがいいか(=貪欲、慎重、oracle)

- greedy戦略では、行動確率最適化においては精度が大きく改善するが、他の最適化においてはbaselineを上回らない。精度が安定していない。 - 慎重戦略は安定した精度を出すことが出来る

Q3. 今回の提案モデルは既存モデルより優れているか

改善されました（詳細は省略）

Q4. どんなユーザーグループに対してパーソナライズが有効か

- ユーザーごとのクエリエントロピー(多様性)を計測したところ、エントロピーが小さい（似たようなクエリばかり検索している）ケースでパーソナライズの効果が大きいことがわかった。

Q5. パーソナライズしたクリックモデルはユーザーごとの行動パターンを推定できるか

- kMeansでクラスタリングしたら、傾向は少し見えた - 表示位置の効果が大きい/小さいユーザー - 最初の結果だけみて検索セッションを終えるユーザー - 中間の位置を好んで閲覧するユーザー
まとめ

クリックモデルにおける行動確率(閲覧確率)を慎重に入れ替えると(過去クエリの実績に基づいて)、予測性能が改善される。

同じようなクエリを複数回検索しているユーザーに対しては特に有効