Si fanno due presupposti nell’uso di DCG e delle sue misure correlate.
- I documenti altamente rilevanti sono più utili quando appaiono prima nella lista dei risultati di un motore di ricerca (hanno ranghi più alti)
- I documenti altamente rilevanti sono più utili dei documenti marginalmente rilevanti, che sono a loro volta più utili dei documenti non rilevanti.
DCG ha origine da una misura precedente, più primitiva, chiamata Cumulative Gain.
Cumulative GainEdit
Cumulative Gain (CG) è la somma dei valori di rilevanza graduata di tutti i risultati in una lista di risultati di ricerca. Questo predecessore di DCG non include il rango (posizione) di un risultato nella lista dei risultati nella considerazione dell’utilità di un insieme di risultati. La CG in una particolare posizione di rango p {displaystyle p}
è definito come: C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}
dove r e l i {displaystyle rel_{i}}
è la rilevanza graduata del risultato nella posizione i {\displaystyle i}
.
Il valore calcolato con la funzione CG non è influenzato dai cambiamenti nell’ordine dei risultati della ricerca. Cioè, spostando un documento altamente rilevante d i {\displaystyle d_{i}}
sopra un documento di rango più alto, meno rilevante, d j {displaystyle d_{j}}
non cambia il valore calcolato per CG (assumendo i , j ≤ p {\displaystyle i,j\leq p}
). Sulla base delle due ipotesi fatte sopra sull’utilità dei risultati della ricerca, (N)DCG è solitamente preferito a CG.
Il guadagno cumulativo è talvolta chiamato precisione graduata, poiché è identico alla metrica della precisione se la scala di valutazione è binaria.
Guadagno cumulativo scontatoModifica
La premessa di DCG è che i documenti altamente rilevanti che appaiono più in basso in una lista di risultati di ricerca dovrebbero essere penalizzati, poiché il valore della rilevanza graduata è ridotto in modo logaritmicamente proporzionale alla posizione del risultato.
La formula tradizionale di DCG accumulata in una particolare posizione di rango p {\displaystyle p}
è definita come: 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)}}}
In precedenza non c’era alcuna giustificazione teoricamente valida per l’uso di un fattore di riduzione logaritmico, oltre al fatto che produce una riduzione regolare. Ma Wang et al. (2013) danno una garanzia teorica per l’utilizzo del fattore di riduzione logaritmico in Normalized DCG (NDCG). Gli autori mostrano che per ogni coppia di funzioni di classifica sostanzialmente diverse, la NDCG può decidere quale sia migliore in modo coerente.
Una formulazione alternativa di DCG pone maggiore enfasi sul recupero dei documenti rilevanti:
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)}}
L’ultima formula è comunemente usata nell’industria, incluse le maggiori società di ricerca sul web e le piattaforme di competizione di data science come Kaggle.
Queste due formulazioni di DCG sono le stesse quando i valori di rilevanza dei documenti sono binari;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}in \0,1\}}
.
Nota che Croft et al. (2010) e Burges et al. (2005) presentano la seconda DCG con un log di base e, mentre entrambe le versioni di DCG sopra usano un log di base 2. Quando si calcola NDCG con la prima formulazione di DCG, la base del log non ha importanza, ma la base del log influenza il valore di NDCG per la seconda formulazione. Chiaramente, la base del log influenza il valore di DCG in entrambe le formulazioni.
Normalized DCGEdit
Le liste dei risultati della ricerca variano in lunghezza a seconda della query. Confrontare le prestazioni di un motore di ricerca da una query all’altra non può essere realizzato in modo coerente usando solo il DCG, quindi il guadagno cumulativo in ogni posizione per un valore scelto di p {\displaystyle p}
dovrebbe essere normalizzato tra le query. Questo viene fatto ordinando tutti i documenti rilevanti nel corpus in base alla loro rilevanza relativa, producendo il massimo DCG possibile attraverso la posizione p {\displaystyle p}
, chiamato anche DCG ideale (IDCG) attraverso quella posizione. Per una query, il guadagno cumulativo normalizzato scontato, o nDCG, è calcolato come: n D C G p = D C G p I D C G p {displaystyle \mathrm {nDCG_{p}} ={frac {DCG_{p}}{IDCG_{p}}}}
,
dove IDCG è il guadagno cumulativo scontato ideale,
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)}}
e R E L p {displaystyle REL_{p}}
rappresenta la lista dei documenti rilevanti (ordinati in base alla loro rilevanza) nel corpus fino alla posizione p.
I valori nDCG per tutte le query possono essere mediati per ottenere una misura della performance media dell’algoritmo di ranking di un motore di ricerca. Si noti che in un algoritmo di ranking perfetto, il D C G p {displaystyle DCG_{p}}
sarà uguale al I D C G p {\displaystyle IDCG_{p}
producendo un nDCG di 1,0. Tutti i calcoli nDCG sono quindi valori relativi sull’intervallo da 0,0 a 1,0 e quindi sono confrontabili tra loro.
La principale difficoltà incontrata nell’uso di nDCG è l’indisponibilità di un ordine ideale dei risultati quando è disponibile solo un feedback di rilevanza parziale.