ConceptDBISAI-written · not yet proofread

Discounted Cumulative Gain

Also DCG · nDCG · DCG and nDCG · Normalized Discounted Cumulative Gain

DCG@k = Σ_{i=1..k} rel_i / log2(i + 1) sums the graded relevances of the top k results with a logarithmic position discount; nDCG@k = DCG@k / iDCG@k normalizes it by the DCG@k of the ideal ranking.

Know these firstGround Truth

Properties#

Discount: the factor $1/\log_2(i+1)$ makes a relevant document count less the lower it is ranked; rank 1 keeps its full relevance ( $\log_2 2 = 1$ ). So very relevant documents ranked above only somewhat relevant ones get a bonus, which binary measures like P@k and AP cannot express.
CG ignores the order within the top $k$ ; DCG does not.
CG and DCG are not normalized to $[0, 1]$ ; nDCG is: $\mathrm{nDCG@}k \in [0, 1]$ , and $\mathrm{nDCG@}k = 1$ iff the top $k$ relevances equal those of the ideal ranking. Because of the normalization, nDCG values of different queries can be averaged over a benchmark.
DCG@k increases when a more relevant document moves to a higher position.

Example#

ExamplenDCG@5 (lecture)

Relevances of hits 1–5: $1, 0, 2, 1, 0$ ; only 3 relevant documents exist overall (relevances 2, 1, 1).

\mathrm{DCG@5} = \frac{1}{\log_2 2} + \frac{0}{\log_2 3} + \frac{2}{\log_2 4} + \frac{1}{\log_2 5} + \frac{0}{\log_2 6} = 1 + 1 + 0.43 \approx 2.43

Ideal ranking $2, 1, 1, 0, 0$ :

\mathrm{iDCG@5} = \frac{2}{\log_2 2} + \frac{1}{\log_2 3} + \frac{1}{\log_2 4} = 2 + 0.63 + 0.5 \approx 3.13, \qquad \mathrm{nDCG@5} = \frac{2.43}{3.13} \approx 0.78.

ExampleImplementation (exam WS 17/18, Tasks 1.3–1.4)

from math import log2

def dcg(rels, k):
    return sum(rels[i] / log2(i + 2) for i in range(min(k, len(rels))))

def ndcg(rels, k):
    ideal = sorted(rels, reverse=True)
    return dcg(rels, k) / dcg(ideal, k)

Index $i$ is 0-based, so rank $i + 1$ gets the discount $\log_2(i + 2)$ .

Sources#

Slides 02, p. 25, Slides 02, p. 26
DBIS_VL02 > Discounted Cumulative Gain
Exams: DBIS Exam WS1718 (not published) Task 1.2–1.4, DBIS Exam WS1920 (not published) Task 1.2, DBIS Exam WS2324 (not published) Task 1.3, DBIS Exam WS2324-2 (not published) Task 1.3 (4)

Connections

Part of topics1

Evaluation

Prerequisites know first1

Ground Truth

Mentioned in inline links3

Ground Truth
Every evaluation measure compares a ranked result list with the ground truth: P@k, P@R, AP, MAP, nDCG and bpref. $R = |$ ground truth of $q|$ is the number of relevant documents. §
VL02 – Ranking and Evaluation
Sometimes relevance comes in shades, e.g. 0 = not relevant, 1 = somewhat relevant, 2 = very relevant. Very relevant documents ranked above only somewhat relevant ones should get a bonus (Slide 25, DCG and nDCG). §
DCG and nDCG — evaluation with graded relevance, normalized by the ideal ranking §
Evaluation
Discounted Cumulative Gain — graded relevance with position discount, normalized by the ideal ranking §
| graded, complete | nDCG@k | top $k$ , grade and position | needs the ideal ranking, i.e. complete judgments | §

Search in these mentions →