Zenn
Closed5

NDCG評価指標について

#
learningtorank
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)式の和の分母は順位iにおける関連性スコアの割引率と考えればよい。下位の文書ほど分母が大きくなるため割引率が大きくなる。つまり、関連性の高い文章が高位に提示するほどスコアは高くなる。スコアが最大となるのは、提示した文書の順位が真の文書の関連性スコアの降順の順位と一致する場合である。

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

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

この指標が単純な順位の二乗誤差と異なる点は、関連性スコアの高い文書が上位に提示されなかった場合のペナルティが大きくなるように設計されていることである。また、逆に関連性が低い文書の順位が下位において多少変動してもスコアがあまり変動しない。この性質は、「関連性の高い文書が上位に提示されない検索エンジンは役に立たないが、関連性の低い文書の下位における厳密な順序は問題とならない」という実用的な要請と合致している。

bilzardbilzard

本文では関連性スコアに2の冪を取り1を引いた形式を掲載したが、関連性スコアを直接使用した以下の形式も存在する(むしろ最初に提案された論文ではこちらの形式で紹介されている)。ただし、これは関連性スコアをどう設計するかだけの違いなので、本質的に両者は等価である。

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