Deux hypothèses sont faites dans l’utilisation de DCG et de ses mesures connexes.
- Les documents hautement pertinents sont plus utiles lorsqu’ils apparaissent plus tôt dans la liste de résultats d’un moteur de recherche (ont des rangs plus élevés)
- Les documents hautement pertinents sont plus utiles que les documents marginalement pertinents, qui sont à leur tour plus utiles que les documents non pertinents.
DCG trouve son origine dans une mesure antérieure, plus primitive, appelée Gain cumulatif.
Gain cumulatifEdit
Le gain cumulatif (CG) est la somme des valeurs de pertinence graduée de tous les résultats d’une liste de résultats de recherche. Ce prédécesseur du GDC n’inclut pas le rang (position) d’un résultat dans la liste de résultats dans la considération de l’utilité d’un ensemble de résultats. Le GC à une position de rang particulière p {\displaystyle p}
est défini comme suit : C G p = ∑ i = 1 p r e l i {\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}
Where r e l i {\displaystyle rel_{i}}
est la pertinence graduée du résultat en position i {\displaystyle i}.
.
La valeur calculée avec la fonction CG n’est pas affectée par les changements dans l’ordre des résultats de recherche. C’est-à-dire que le déplacement d’un document hautement pertinent d i {\displaystyle d_{i}}
au-dessus d’un document d’ordre supérieur, moins pertinent, d j {\displaystyle d_{j}}.
ne modifie pas la valeur calculée pour CG (en supposant que i , j ≤ p {\displaystyle i,j\leq p}
). Sur la base des deux hypothèses formulées ci-dessus concernant l’utilité des résultats de recherche, le (N)DCG est généralement préféré au CG.
Le gain cumulatif est parfois appelé précision graduée car il est identique à la métrique de précision si l’échelle de notation est binaire.
Gain cumulatif actualiséEdit
Le principe du DCG est que les documents très pertinents apparaissant plus bas dans une liste de résultats de recherche doivent être pénalisés car la valeur de pertinence graduée est réduite de manière logarithmique proportionnelle à la position du résultat.
La formule traditionnelle du DCG accumulée à une position de rang particulière p {\displaystyle p}.
est définie comme suit : 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)}}
Auparavant, il n’y avait pas de justification théoriquement solide pour l’utilisation d’un facteur de réduction logarithmique autre que le fait qu’il produit une réduction lisse. Mais Wang et al. (2013) donnent une garantie théorique pour l’utilisation du facteur de réduction logarithmique dans la GDC normalisée (GDCN). Les auteurs montrent que pour chaque paire de fonctions de classement sensiblement différentes, le NDCG peut décider laquelle est meilleure de manière cohérente.
Une formulation alternative de DCG met davantage l’accent sur la récupération des documents pertinents :
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)}}.
Cette dernière formule est couramment utilisée dans l’industrie, notamment par les grandes entreprises de recherche sur le Web et les plateformes de concours de science des données telles que Kaggle.
Ces deux formulations de DCG sont les mêmes lorsque les valeurs de pertinence des documents sont binaires ;:320 r e l i ∈ { 0 , 1 } {\displaystyle rel_{i}\in \{0,1\}}.
.
Notez que Croft et al. (2010) et Burges et al. (2005) présentent le deuxième GDC avec un logarithme de base e, alors que les deux versions du GDC ci-dessus utilisent un logarithme de base 2. Lors du calcul du NDCG avec la première formulation de la GDC, la base du logarithme n’a pas d’importance, mais la base du logarithme affecte la valeur du NDCG pour la deuxième formulation. Il est clair que la base du logarithme affecte la valeur du GDC dans les deux formulations.
GDC normalisédit
Les listes de résultats de recherche varient en longueur en fonction de la requête. Comparer les performances d’un moteur de recherche d’une requête à l’autre ne peut pas être réalisé de manière cohérente en utilisant uniquement le GDC, donc le gain cumulé à chaque position pour une valeur choisie de p {\displaystyle p}.
doit être normalisé entre les requêtes. Ceci est fait en triant tous les documents pertinents du corpus par leur pertinence relative, produisant le GDC maximum possible à travers la position p {\displaystyle p}.
, également appelé GDC idéal (GCI) par cette position. Pour une requête, le gain cumulé actualisé normalisé, ou nDCG, est calculé comme suit : n D C G p = D C G p I D C G p {\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}
,
où IDCG est le gain cumulé actualisé idéal,
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)}}
et R E L p {\displaystyle REL_{p}}
représente la liste des documents pertinents (ordonnés par leur pertinence) dans le corpus jusqu’à la position p.
Les valeurs de nDCG pour toutes les requêtes peuvent être moyennées pour obtenir une mesure de la performance moyenne de l’algorithme de classement d’un moteur de recherche. Notez que dans un algorithme de classement parfait, le D C G p {\displaystyle DCG_{p}}
sera le même que le I D C G p {\displaystyle IDCG_{p}}.
produisant un nDCG de 1,0. Tous les calculs de nDCG sont alors des valeurs relatives sur l’intervalle 0,0 à 1,0 et sont donc comparables entre eux.
La principale difficulté rencontrée dans l’utilisation de nDCG est l’indisponibilité d’un ordonnancement idéal des résultats lorsque seul un retour de pertinence partiel est disponible.