NDCGを紹介し、達成する

本文主要介绍一个 Search 和 Recommend 中常用的一个评估指标：NDCG。
NDCG（Normalized Discounted Cumulative Gain）を「正規化割引累積ゲイン」と訳すことができ、通常はランキングの正確性を測定・評価するために使用されます。例えば、e コマースシステムでは、ユーザーのクエリに対して商品リストが返され、リストの長さを N とした場合、NDCG@N を使用してそのリストの順位と実際のインタラクションリストとのギャップを評価できます。

Cumulative Gain#

CG（累積ゲイン）は、検索結果リスト内のすべての文書の階層的関連性スコアの合計です。CG は検索結果リスト内の結果の関連性のみを考慮し、これらの文書の結果リスト内の位置要因は考慮しません。与えられた結果リストの順位位置 $p$ は次のように定義できます：

$CG_p = \sum_{i=1}^p rel_i$

ここで $rel_i$ は第 $i$ 位置の関連性を示します。
例えば、ユーザーがある e コマースプラットフォームで「スマートフォン」を検索したとします。結果の最初の 6 つは、iPhone、xiaomi、Huawei、OPPO、VIVO、三星です。そして、ユーザーが選択する傾向があるのは Huawei です。この場合、Huawei スマートフォンが最初の 6 つのどの位置にあっても、累積ゲインにとっては等価です。しかし、search、recommend システムにとっては、最良の結果は Huawei スマートフォンが最初に配置されることです。これにより次の指標、割引累積ゲインが導入されます。

Discounted Cumulative Gain#

**DCG（割引累積ゲイン）** は、検索結果リストの後ろの位置に関連性の高い結果が出現した場合、評価スコアにペナルティを課すべきだと提案します。ペナルティの割合は文書の位置の対数値に関連しています。与えられたリスト結果の順位位置を $p$ とすると、DCG は次のように定義できます：

$DCG_p = \sum_{i=1}^p \frac{rel_i}{log_2(i+1)}$

もう一つ一般的に使用される公式があり、これは関連度の影響の重みを増加させるために使用されます：

$DCG_p = \sum_{i=1}^p \frac{2^{rel_i}-1}{log_2(i+1)}$

後者の公式は、ほとんどの検索会社や e コマースプラットフォームでより一般的に使用されます。
関連性スコア $rel_i\in(0,1)$ 、つまり値が 0 または 1 のみの場合、上記の 2 つの公式は等価です。

Normalized Discounted Cumulative Gain#

NDCG（正規化割引累積ゲイン）、記事の冒頭で言及した_NDCG_に戻ります。_NDCG_は、検索結果の長さがクエリによって異なると考え、_DCG_を使用して異なるクエリのパフォーマンスを比較することは一貫性がないとしています。したがって、選択された $p$ 値に対して、各位置の_CG_はクエリに基づいて正規化されるべきであり、まずライブラリ内のすべての関連結果を関連性に基づいてソートし、位置 $p$ を通じて最大の可能な_DCG_を生成します。通常、これを_IDCG（理想 DCG）_と呼びます。あるクエリに対して、_NDCG_は次のように計算できます：

$NDCG_p = \frac{DCG_p}{IDCG_p}$

ここで_IDCG_は理想的な状態での_DCG_であり、計算方法は次の通りです：

$IDCG_p = \sum_{i=1}^{|REL_p|} \frac{2^{rel_i}-1}{log_2(i+1)}$

$REL_p$ はライブラリ内の関連性が最も高い $p$ 個の結果リスト（関連性に基づいてソートされた）を示します。すべてのクエリの_NDCG_値を平均して、検索エンジンのランキングアルゴリズムの平均パフォーマンスを評価します。_NDCG_値が大きいほど、ランキングアルゴリズムのパフォーマンスが良いことを示します。完璧なランキングアルゴリズムでは、 $DCG_p$ と $IDCG_p$ は等しく、_NDCG_の値は 1 になります。一方、_NDCG_の値は最小で 0 であるため、_NDCG_の値は 0 から 1 の間に分布します。これは相対値であるため、クエリを超えて比較することができます。

計算例#

前述のユーザー検索クエリ「スマートフォン」に対して 6 つの結果が返される例を考えます。結果は iPhone、xiaomi、Huawei、OPPO、VIVO、三星で、それぞれの関連性スコアは 3、2、3、0、1、2 です。
したがって、対応する_CG_は次のようになります：

$CG_6 = \sum_{i=1}^6 rel_i = 3 + 2 + 3 + 0 + 1 + 2 = 11$

任意の 2 つの結果の順序を変更しても、_CG_計算の最終結果には影響しません。_DCG_は、結果リストの前に出現する高度に関連する結果を強調するために使用されます。対数を使用して縮小し、各結果の DCG は次のようになります：

${i}$	${rel_i}$	$2^{rel_i} - 1$	${log_2(i + 1)}$	$\frac{rel_i}{log_2(i+1)}$	$\frac{2^{rel_i}-1}{log_2(i+1)}$
1	3	7	1	3	7
2	2	3	1.585	1.262	1.893
3	3	7	2	1.5	3.5
4	0	0	2.322	0	0
5	1	1	2.585	0.387	2.585
6	2	3	2.807	0.712	1.069

最初の_DCG_公式を使用して計算すると、次のようになります：

$DCG_6 = \sum_{i=1}^6 \frac{rel_i}{log_2(i+1)} = 3+1.262+1.5+0+0.387+0.712 = 6.861$

次に、2 番目の_DCG_公式を使用して計算すると、次のようになります：

$DCG_6 = \sum_{i=1}^6 \frac{2^{rel_i}-1}{log_2(i+1)} = 7+1.893+3.5+0+2.585+1.069=16.047$

現在、3 番目の結果と 4 番目の結果の位置を交換すると、DCG が低下します。関連性の低い結果が順位の上位にあるため、つまり、より関連性の高い結果が低い位置に配置されることで、より多くの損失が生じます。
このクエリのパフォーマンスはこの場合比較できません。なぜなら、別のクエリにはより多くの結果がある可能性があり、より大きな_DCG_をもたらすかもしれませんが、それがこのクエリのパフォーマンスがより良いことを意味するわけではないからです。比較を行うためには、DCG 値を正規化する必要があります。
DCG の値を正規化するためには、与えられたクエリに対して理想的なソートを行う必要があります。この例では、そのソートはすべての既知の関連性判断の単調減少ソートになります。この例の 6 つの結果に加えて、関連性スコアが 3 の結果 7 と、関連性スコアが 2 の結果 8 があると仮定します。理想的なソートは次のようになります：

$3, 3, 3, 2, 2, 2, 1, 0$

結果 7、8 がない場合、理想的なソートは

$3, 3, 2, 2, 1, 0$

理想的なソートの_DCG_、または_IDCG_は、最初の 6 つの位置を計算します。

$IDCG_6 = 3/1+3/1.585+2/2+2/2.322+0.387+0/2.807=7.141$

したがって、与えられたこのクエリの_NDCG_は次のように計算できます：

$NDCG_6 = \frac{DCG_6}{IDCG_6} =\frac{6.861}{7.141} = 0.961$

Python コード計算 NDCG#

import numpy as np  

def get_dcg(rec_list):  
    log_2 = np.log2(np.arange(2, len(rec_list) + 2))  
    mi = np.power(2, rec_list) - 1  
    dcg = np.array(mi / log_2).sum()  
    return dcg  

if __name__ == "__main__":  
    rec_list = [3, 2, 3, 0, 1, 2]  
    sort_rec_list = [3, 3, 2, 2, 1, 0]  
    dcg = get_dcg(rec_list)  
    idcg = get_dcg(sort_rec_list)  
    print("ndcg = dcg / idcg = ", dcg/idcg)

Reference#

https://en.wikipedia.org/wiki/Discounted_cumulative_gain