Při používání DCG a souvisejících měr se vychází ze dvou předpokladů.
- Vysoce relevantní dokumenty jsou užitečnější, když se objeví dříve v seznamu výsledků vyhledávače (mají vyšší hodnosti)
- Vysoce relevantní dokumenty jsou užitečnější než okrajově relevantní dokumenty, které jsou zase užitečnější než nerelevantní dokumenty.
DCG pochází z dřívějšího, primitivnějšího měřítka zvaného Kumulativní zisk.
Kumulativní ziskEdit
Kumulativní zisk (CG) je součet odstupňovaných hodnot relevance všech výsledků v seznamu výsledků vyhledávání. Tento předchůdce DCG nezahrnuje do úvahy o užitečnosti souboru výsledků pořadí (pozici) výsledku v seznamu výsledků. CG na konkrétní pozici hodnosti p {\displaystyle p}.
je definován jako: C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}
Kde r e l i {\displaystyle rel_{i}}
je odstupňovaná relevance výsledku na pozici i {\displaystyle i}
.
Na hodnotu vypočtenou pomocí funkce CG nemají vliv změny v pořadí výsledků vyhledávání. To znamená, že přesunutí vysoce relevantního dokumentu d i {\displaystyle d_{i}} do jiného místa vyhledávání není možné.
nad výše umístěný, méně relevantní dokument d j {\displaystyle d_{j}}.
nezmění vypočtenou hodnotu pro CG (za předpokladu, že i , j ≤ p {\displaystyle i,j\leq p}
). Na základě dvou výše uvedených předpokladů o užitečnosti výsledků vyhledávání se obvykle dává přednost (N)DCG před CG.
Kumulativní zisk se někdy nazývá odstupňovaná přesnost, protože je totožný s metrikou přesnosti, pokud je stupnice hodnocení binární.
Diskontovaný kumulativní ziskEdit
Předpokladem DCG je, že vysoce relevantní dokumenty objevující se níže v seznamu výsledků vyhledávání by měly být penalizovány, protože odstupňovaná hodnota relevance se logaritmicky snižuje úměrně pozici výsledku.
Tradiční vzorec DCG kumuluje na určité pozici pořadí p {\displaystyle p}.
je definován jako: D C G p = ∑ i = 1 p r e l i log 2 ( i + 1 ) = r e l 1 + ∑ i = 2 p r e l i log 2 ( i + 1 ) {\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {rel_{i}}{\log _{2}(i+1)}}=rel_{1}+\sum _{i=2}^{p}{\frac {rel_{i}}{\log _{2}(i+1)}}}.
Předtím nebylo použití logaritmického redukčního faktoru teoreticky zdůvodněno jinak než tím, že vede k hladké redukci. Wang a další (2013) však poskytují teoretickou záruku pro použití logaritmického redukčního faktoru v normalizované DCG (NDCG). Autoři ukazují, že pro každou dvojici podstatně odlišných funkcí řazení dokáže NDCG konzistentně rozhodnout, která z nich je lepší.
Alternativní formulace DCG klade větší důraz na vyhledávání relevantních dokumentů:
D C G p = ∑ i = 1 p 2 r e l i – 1 log 2 ( i + 1 ) {\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}.
Posledně jmenovaný vzorec se běžně používá v průmyslu včetně velkých společností zabývajících se vyhledáváním na webu a na platformách pro soutěže v datové vědě, jako je Kaggle.
Tyto dvě formulace DCG jsou stejné, když jsou hodnoty relevance dokumentů binární;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}\in \{0,1\}}.
.
Všimněte si, že Croft et al. (2010) a Burges et al. (2005) uvádějí druhý DCG s logaritmem základu e, zatímco obě výše uvedené verze DCG používají logaritmus základu 2. Při výpočtu NDCG pomocí první formulace DCG na základu log nezáleží, ale základ log ovlivňuje hodnotu NDCG u druhé formulace. Je zřejmé, že základ logaritmu ovlivňuje hodnotu DCG v obou formulacích.
Normalizovaný DCGEdit
Seznamy výsledků vyhledávání se liší délkou v závislosti na dotazu. Porovnání výkonu vyhledávače mezi jednotlivými dotazy nelze důsledně dosáhnout pouze pomocí DCG, takže kumulativní zisk na každé pozici pro zvolenou hodnotu p {\displaystyle p}.
by měl být normalizován napříč dotazy. To se provede seřazením všech relevantních dokumentů v korpusu podle jejich relativní relevance, čímž se získá maximální možný DCG přes pozici p {\displaystyle p}.
, nazývané také ideální DCG (IDCG) přes tuto pozici. Pro dotaz se normalizovaný diskontovaný kumulativní zisk neboli nDCG vypočítá takto: n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}
,
kde IDCG je ideální diskontovaný kumulativní zisk,
I D C G p = ∑ i = 1 | R E L p | 2 r e l i – 1 log 2 ( i + 1 ) {\displaystyle \mathrm {IDCG_{p}} =\sum _{i=1}^{|REL_{p}|}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}.
a R E L p {\displaystyle REL_{p}}
představuje seznam relevantních dokumentů (seřazených podle relevance) v korpusu až do pozice p.
Hodnoty nDCG pro všechny dotazy lze zprůměrovat a získat tak míru průměrného výkonu algoritmu řazení vyhledávače. Všimněte si, že v dokonalém algoritmu řazení je D C G p {\displaystyle DCG_{p}}.
bude stejný jako I D C G p {\displaystyle IDCG_{p}}.
, čímž vznikne nDCG 1,0. Všechny výpočty nDCG jsou pak relativní hodnoty na intervalu 0,0 až 1,0, a jsou tedy vzájemně porovnatelné.
Hlavním problémem, se kterým se při používání nDCG setkáváme, je nedostupnost ideálního uspořádání výsledků, pokud je k dispozici pouze částečná zpětná vazba o relevanci
.