stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(15): 評価(2)

前回は、ランクなしの（二値）評価指標である精度と再現率、そして二値適合性に基づくランクつき指標である Precision@K、MAP について解説した。今回は多値適合性に基づく nDCG、そしてクリックデータの活用について説明する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の15日目の記事です。

adventar.org

多値適合性に基づく検索評価指標

減損累積利得 (DCG) の概要

  • DCG (discounted cumulative gain) は Web 検索などの評価に用いられるポピュラーな指標
  • 2つの仮定を置いている
    • 関連性が高い文書は、より低い文書よりも有用性が高い
    • 文書の順位（ランク）が低いほど、見られる可能性が低いため、ユーザにとって有用性が低い
  • 文書の有用性あるいは利得 (gain) の指標として、グレードつきの適合性を使う
    • 多値適合性
  • 利得はランキングの上位から累積されるが、下位の文書ではそれが減損 (discount) される可能性がある
  • 典型的な減損は 1/\log (rank)
    • log の底が2のとき、ランキングが4位の減損は 1/2、8位の減損は 1/3 になる

累積利得 (CG)

  • 適合性判定の値が [0, r (r < 2)] の範囲だとする
  • 第k位までの文書の判定がそれぞれ r_1, r_2, ..., r_k だったとすると、累積利得 (cumulative gain; CG) は
 CG_k = r_1 + r_2 + r_3 + ... + r_k

減損累積利得 (DCG)

  • 前述したように、DCG では順位が下がるごとに利得を減損させていく
  • 減損として 1/\log_2 (rank) を使ったとき、
\begin{eqnarray}
DCG_k &=& r_1 + \dfrac{r_2}{\log_2 2} + \dfrac{r_3}{\log_2 3} + ... + \dfrac{r_k}{\log_2 k} \\
      &=& r_1 + \sum_{i=2}^p \dfrac{r_i}{\log_2 i} \\
      &=& \sum_{i=1}^p \dfrac{2^{r_i} - 1}{\log_2 (1+i)}
\end{eqnarray}
  • log の底には任意のものが使える
  • Web 検索の企業で使われている

f:id:takuya-a:20201216011045p:plain
nDCG の例。Ground Truth が理想的なランキング（nDCGは1）

nDCG

  • nDCG (normalized discounted cumulative gain) は、理想的なランキングだったときの DCG によって正規化したもの
    • DCG を最大値が 1 になるように正規化
    • 理想的なランキングというのは、第1位に最も適合性の高い文書、第2位に2番目にい適合性の高い文書……という順番になっているもの
  • 正規化は、検索結果の件数が異なるクエリで指標を比較するときに有用
  • nDCG は、Web 検索で現在最も使われている評価指標

クリックデータの活用

人間による判定の問題点

  • 高価である
  • 一貫性がない
    • 評価をつける人の間で、もしくは同じ人でも時間が経つと
  • いつも「本当のユーザ」を代表しているわけではない
    • クエリを見ても実際の情報ニーズはわからない
    • タームの意味がわからないこともある

ポジションバイアス

  • 検索結果の位置によって強いバイアスがかかる
    • 1位の文書は下位のものよりクリックされやすい
  • アイトラッキングシステムを使った実験でも実証されている [Joachims+07]
    • 高い位置のものはユーザの注意をよりひきつけ（視線が固定される）、クリックもされる
    • 検索結果の順位を逆順にしてもこの傾向は変わらない
  • クリックデータは有用ではあるが、バイアスがあるので注意が必要

相対評価と絶対評価

  • 第1位の検索結果 (R1) と、第3位の検索結果 (R3) がクリックされたとき、
    • R1 > R3 と結論づけるのは難しい
    • R3 > R2 は言えるかもしれない
  • ペアワイズによる相対的な評価
    • これまでにやってきた評価（クエリと文書に対して絶対値の適合性判定がついていた）とは違う
    • 過去のクリックデータからペアワイズの評価

インターリービング

  • 2つのランキングアルゴリズム A, B を比較するために、それぞれから得られたランキングを互い違いに混ぜたものを検索結果ページ (SERP) として返す (interleave)
    • A から始めるか B から始めるかはランダムに選択（表示バイアスを除くため）
    • 重複した検索結果を含む場合は、下位のほうを取り除く
  • クリックデータから、A, B それぞれのクリック数をカウント
  • より良いランキングアルゴリズムがより多いクリックを獲得するはず

Web 検索における A/B テスト

  • 目的：1つの変更の効果をテストすること
  • 事前条件：すでに大規模な検索エンジンをもっていて、それが動いていること
  • 小さな比率のトラフィック（たとえば 0.1%）を変更したバージョンに向ける
    • インターリービングしてもいいし、ページ全体を使ってもいい

講義資料

参考資料