Closed5

NDCG評価指標について

Learning to rank
bilzardbilzard

NDCGとは？

NDCG (Normalized Documented Cumulative Gain)はドキュメント検索タスクにおける評価指標の一つである。元はWeb検索エンジンのような文書検索システムの評価指標として導入されたが、レコメンドエンジンやランキング学習モデルの評価指標としても用いられる。

コンセプト

以下の性質を満たすようにする。

  • 関連性スコアが高い文書が上位に提示されているほどスコアが大きく加点されること
  • 上位側ほど順位を外した場合のペナルティが大きいこと

以下を引数にとる。

  1. 正解ラベル: 文書ごとの関連性スコアの正解値
  2. モデルの予測: 文書ごとの順位

DCG(Documented Cumulative Gain)

まず、正規化されていない以下の指標を導入する。

\text{DCG}@k = \sum_{\pi(i)\le k} \frac{2^{l_i} - 1}{\log_2(\pi(i) + 1)} \tag{1}

ここで、

  • \pi(i): モデルが提示した文書iの順位(1, ... , N)
  • l_i: 文書iの関連性スコア(l_i \ge 0)
  • k: 評価に使用するモデルの検索結果の上位k件

(1)式の分子は文書の価値に相当し、分母はモデルの予測した順位のに基づくペナルティに対応する。下位の文書ほど分母が大きくなるためペナルティが大きくなり、小さな加点しか得られない。逆に、関連性の高い文章を高位に提示するほど大きく加点される。値が最大となるのは、モデルが提示した文書が正解の関連性スコアの降順に並ぶ時である。

スコアのとりうる値が[0, 1]に収まっている方が異なるモデルの予測結果の比較に便利である。そこでDCGを最大値で割って正規化したものがNDCGである。

\text{NDCG}@k= \frac{\text{DCG}@k}{\max_\pi(\text{DCG}@k)} \tag{2}
bilzardbilzard

この指標の特徴は、モデルが予測した関連性スコアの値を直接評価するのでなく、スコア順に並び替えた時の順位で評価する点である。従って、スコア自体の予測精度よりも提示した文書の順番が正確になるようにしている。

単純な予測順位と正解順位の二乗誤差では上位と下位で順位の誤差によるペナルティが同じなのに対し、DCGでは上位ほど順位を外した時のペナルティが大きく、下位では鈍感な性質をもつ。

これは関連性の高い文書が上位に提示されない検索エンジンは役に立たないが、関連性の低い文書の下位における厳密な順序は問題とならないという実用的な要求に合うように設計されている。

bilzardbilzard

本文では関連性スコアに2の冪を取り1を引いた形式を掲載したが、関連性スコアを直接使用した以下の形式も存在する(むしろ最初に提案された論文ではこちらの形式で紹介されている)。ただし、これは関連性スコアをマッピングしているだけなので、損失関数の設計上は本質的な違いではでない。タスクに応じて経験的に決めるべきものだろう。

\text{DCG}@k = \sum_{\pi(i)\le k} \frac{l_i}{\log_2(\pi(i) + 1)} \tag{3}
このスクラップは2022/12/28にクローズされました