DCG

DCG（減損累積利得、げんそんるいせきりとく、Discounted cumulative gain）は、ランキング品質の評価指標である。情報検索において、DCG はウェブ検索エンジンのアルゴリズムや情報検索に関連したアプリケーションの適合性に対する有用性を評価するために使用される。DCG は検索エンジンの検索結果に含まれる文書の適合性を段階的に評価することで、検索結果リストにおける文書の位置（順位）によって、その文書の有用性、すなわち利得を測定する。この利得は、結果リストの上位から下位に向かって累積され、下位の文書ごとに各結果までの利得が割り引かれる。
概要.
DCG と DCG の類似指標が使用される場面は次の2つが想定される。
DCG は CG（累積利得）から拡張した指標である。
CG（累積利得）.
CG（累積利得）は、検索結果の全結果のリストに対して段階的に適合性の評価を与え、それらを総和した指標である。DCG の前身概念である CG は、結果リストにおける結果の順位を、検索結果集合の有用性が考慮された結果リストが含まれない。ある順位 formula_1 での CG は:
上記の formula_3 は各順位 formula_4 における文書の適合度を表す。
CGで算出された値は、検索結果に基づくランキングの順序の影響を受けない。つまり、適合度の高い文書 formula_5 が適合度の低い文書 formula_6 より高い順位に並び変わったとしても、CGの値は変動しない（ただし formula_7）。検索結果の有用性を測る指標は上記の2つの前提に基づいて、一般的に CG より (n)DCG が使用されている。
CG は評価尺度が二値分類であるとき、適合率と等しくなるため、"Graded Precision"（段階的適合率）と呼ばれることがある。
DCG（減損累積利得）.
DCG における前提として、検索結果リストの下位に表示される適合性の高い文書にはペナルティを与えて、評価値は検索結果のランキングに比例して対数スケールで減少させることである。
最初期に提唱された、ある順位 formula_1 まで累積した DCG は次のように定義される:
DCG が提唱された当時は、DCG の減損方法に対数を用いる妥当性は、削減具合がなめらかであったこと以外に理論的に証明されていなかった。しかしワンら (2013) によって nDCG（正規化減損累積利得）における対数による減損の妥当性が保証された。これは実質的に異なるランキングを評価する関数を対照的に、首尾一貫方法でそれらの関数による NDCG が優れているかを求めることで示した。
また2005年に提唱された適合度の高い文書に対しより高い評価を与えることを重視した DCG が代替的に使用されている:
後者の式は一般的なウェブ検索企業や Kaggle といったデータサイエンスの競技プラットフォームで用いらている指標となっている。
これら2つの DCG の式は文書に対する適合度が formula_11 ので与えられるとき等しくなる。
なおクロフトら (2010) やバージェスら (2005) は下記の DCG 式の対数部分は自然対数として定義しているが、ここでは 2 を底とする対数を用いた DCG を定義している。第一式の DCG は対数の底の値によって nDCG の値は大きく変動しないが、第二式の DCG においては対数の底の値によって nDCG は大きな影響を受ける。これは明らかに、上記の DCG 式は対数の底によって割り引かれる程度が変動する。
nDCG（正規化減損累積利得）.
検索結果の数は、クエリごとに数が異なる。あるクエリから次のクエリにおける検索エンジンの性能を比較するときに、ある順位 formula_1 までの利得を累積する DCG 単体で性能を測定することはできないため、選択したある順位 formula_1 までの累積利得を正規化する必要がある。DCG を正規化するために、コーパス上でクエリに関連する文書を DCG の値が最大化されるように順位 formula_1 まで並べる（理想的リストとも呼ばれる。）必要がある。順位 formula_1 における DCG が最大化されたものは IDCG と呼ばれる。あるクエリに対する nDCG（"normalized discounted cumulative gain"）は:
と定義される。
このとき IDCG（理想的減損累積利得、ideal discounted cumulative gain）は:
ただし formula_18 はコーパス中における p 番目までの（適合度の高い順番に並べられた）理想的リストを表す。
任意のクエリに対する nDCG の値は検索エンジンに実装されているランキングアルゴリズムの平均的な性能指標を得るために各クエリの DCG の値を平均し得る。なお完璧なランキングアルゴリズムでの formula_19 は formula_20 と等しくなり、nDCGは 1.0 となる。また nDCG 値は 0.0 - 1.0 をとる相対的指標なので、クロスクエリにおいて比較可能である。
nDCG を使用する上での問題は、クエリに対するが一部にしか得られなかった場合、検索結果に対する理想的リストが正しく得られなくなることである。
例.
検索クエリに対する文書のリストが与えられたときに、各文書のクエリに対する適合性を求める。各文書は、0: 関連がない、3: 関連がある、1, 2: 中間の評価として、0～3の値で判定する。文書に対してランキングアルゴリズムに則って評価値（ラベル）を順に与えるとき、各文書を
とおき、各文書ごとにクエリとの適合性の値を:
と与える。
このとき、formula_23 の適合性は 3、formula_24 の適合性は 2 である。この検索結果リストに対する CG（累積利得）は:
である。
検索結果リストの任意の2つの文書の順序を入れ替えることは CG の値に対し影響を与えない。ここで formula_26 および formula_27 を入れ替えると、CG は 11 と入れ替える前と同値ある。DCG は検索結果リスト内で早期に適合性の高い文書が表れるときに、高い値を与えるために使用される。対数スケールを用いて、各順位ごとの適合性に対して削減を行う DCG は次のように求まる:
このとき、上記のランキングにおける formula_28 は:
となる。
ここで、文書 formula_26 と formula_27 を入れ替えると、文書 formula_26 より適合性の低い文書 formula_27 が上位の検索結果となるため、DCG が減少する。つまり、適合性の高い文書が下位に含まれるほど順位に依存して割り引かれる。
DCG では、このクエリと他のクエリの性能の比較を行うには不適切な指標である。なぜならば、他のクエリはより多くの文書結果を持っているので、DCG の値は文書結果の数が多いほど、高くなり得るのでクエリの良し悪しを図りえないことがある。クエリごとの比較を行うには、DCG を正規化する必要がある。
正規化された DCG の値を求めるために、与えられたクエリに対する理想的リストを求める必要がある。例として、理想的リストの順序は適合性が与えられている文書の値が単調減少されるように並べ替えられる。ここで適合度が与えられた6つの文書に加えて、クエリに対する適合度が 3 の文書 formula_34 、適合度が 2 の文書 formula_35 がランキングの下位に存在すると仮定する。このときの理想的リストは:
この理想的ランキングを分析するランキングの順位、つまり長さ6 まで再び選び取る:
この理想的な順序における DCG、つまり "IDCG（Ideal DCG）" はランク6のとき:
と求まる。
そして、このクエリにおける nDCG は次のように与えられる: