Twee veronderstellingen worden gemaakt bij het gebruik van DCG en aanverwante maatstaven.
- Hoog relevante documenten zijn nuttiger wanneer ze eerder in een resultatenlijst van een zoekmachine verschijnen (hogere rangen hebben)
- Hoog relevante documenten zijn nuttiger dan marginaal relevante documenten, die op hun beurt nuttiger zijn dan niet-relevante documenten.
DCG komt voort uit een eerdere, primitievere maatstaf genaamd Cumulative Gain.
Cumulative GainEdit
Cumulative Gain (CG) is de som van de gradatie van de relevantiewaarden van alle resultaten in een zoekresultatenlijst. Deze voorloper van DCG betrekt de rang (positie) van een resultaat in de resultatenlijst niet in de beschouwing van de bruikbaarheid van een resultatenverzameling. De CG op een bepaalde positie in de rangorde p {\displaystyle p}
wordt gedefinieerd als: C G p = ∑ i = 1 p r e l i {CG_{p}} = som _{i=1}^{p}rel_{i}}
Waarbij r e l i {\displaystyle rel_{i}}
de gegradeerde relevantie is van het resultaat op positie i {\displaystyle i}
.
De met de CG-functie berekende waarde wordt niet beïnvloed door wijzigingen in de volgorde van de zoekresultaten. Dat wil zeggen dat het verplaatsen van een zeer relevant document d i {Displaystyle d_{i}}
boven een hoger gerangschikt, minder relevant document d j {\displaystyle d_{j}}
verandert de berekende waarde voor CG niet (ervan uitgaande dat i , j ≤ p {\displaystyle i,j\leq p}
). Op basis van de twee bovenstaande veronderstellingen over de bruikbaarheid van de zoekresultaten wordt gewoonlijk de voorkeur gegeven aan (N)DCG boven CG.
Cumulatieve winst wordt soms ook wel Graded Precision genoemd, omdat deze identiek is aan de Precision-metriek als de beoordelingsschaal binair is.
Discounted Cumulative GainEdit
Het uitgangspunt van DCG is dat zeer relevante documenten die lager in een lijst met zoekresultaten verschijnen, moeten worden bestraft, aangezien de graded relevance-waarde logaritmisch evenredig met de positie van het resultaat wordt verlaagd.
De traditionele formule van DCG accumuleerde op een bepaalde positie in de rangorde p {{Displaystyle p}
is gedefinieerd als: 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}} = som _{i=1}^{p}{\frac {rel_{i}}{log _{2}(i+1)}}=rel_{1}+ som _{i=2}^{p}{\frac {rel_{i}}{\log _{2}(i+1)}}
Voorheen was er geen theoretisch verantwoorde rechtvaardiging voor het gebruik van een logaritmische reductiefactor, anders dan het feit dat dit een vloeiende reductie oplevert. Maar Wang et al. (2013) geven een theoretische garantie voor het gebruik van de logaritmische reductiefactor in Normalized DCG (NDCG). De auteurs tonen aan dat voor elk paar wezenlijk verschillende rangschikkingsfuncties, de NDCG op een consistente manier kan beslissen welke beter is.
Een alternatieve formulering van DCG legt sterker de nadruk op het ophalen van relevante documenten:
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)}}
De laatste formule wordt veel gebruikt in de industrie, waaronder grote bedrijven die zoeken op het web en platforms voor data science-wedstrijden, zoals Kaggle.
Deze twee formuleringen van DCG zijn hetzelfde als de relevantiewaarden van documenten binair zijn;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}}
.
Merk op dat Croft et al. (2010) en Burges et al. (2005) de tweede DCG presenteren met een log van basis e, terwijl beide versies van DCG hierboven een log van basis 2 gebruiken. Bij het berekenen van NDCG met de eerste formulering van DCG doet de basis van de log er niet toe, maar de basis van de log heeft wel invloed op de waarde van NDCG voor de tweede formulering. Het is duidelijk dat de basis van de log de waarde van DCG in beide formuleringen beïnvloedt.
Genormaliseerde DCGEdit
De lijsten met zoekresultaten variëren in lengte, afhankelijk van de zoekopdracht. Het vergelijken van de prestaties van een zoekmachine van de ene zoekopdracht tot de volgende kan niet consistent worden bereikt met DCG alleen, dus de cumulatieve winst op elke positie voor een gekozen waarde van p {\displaystyle p}
moet worden genormaliseerd voor alle zoekopdrachten. Dit wordt gedaan door alle relevante documenten in het corpus te sorteren op hun relatieve relevantie, waarbij de maximaal mogelijke DCG door positie p {{\displaystyle p}
, ook wel Ideale DCG (IDCG) door die positie genoemd. Voor een zoekopdracht wordt de genormaliseerde verdisconteerde cumulatieve winst, of nDCG, als volgt berekend: n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}
,
waar IDCG de ideale verdisconteerde cumulatieve winst is,
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)}}}
en R E L p {\displaystyle REL_{p}}
staat voor de lijst van relevante documenten (gerangschikt naar relevantie) in het corpus tot en met positie p.
De nDCG-waarden voor alle zoekopdrachten kunnen worden gemiddeld om een maat te krijgen voor de gemiddelde prestaties van het rangschikkingsalgoritme van een zoekmachine. Merk op dat in een perfect rangschikkingsalgoritme de D C G p {Displaystyle DCG_{p}}
hetzelfde zal zijn als de I D C G p {\displaystyle IDCG_{p}}
, wat een nDCG van 1,0 oplevert. Alle nDCG-berekeningen zijn dan relatieve waarden op het interval 0,0 tot 1,0 en zijn dus onderling vergelijkbaar.
De belangrijkste moeilijkheid bij het gebruik van nDCG is de onbeschikbaarheid van een ideale volgorde van resultaten wanneer slechts gedeeltelijke relevantie-feedback beschikbaar is.