La ganancia acumulada descontada ( DCG ) es una medida de la calidad de la clasificación en la recuperación de información . A menudo se normaliza para que sea comparable entre consultas, lo que da como resultado la DCG normalizada (nDCG o NDCG) . La NDCG se utiliza a menudo para medir la eficacia de los algoritmos de los motores de búsqueda y las aplicaciones relacionadas. Utilizando una escala de relevancia graduada de los documentos en un conjunto de resultados de un motor de búsqueda, la DCG suma la utilidad, o ganancia , de los resultados descontados por su posición en la lista de resultados. [1] La NDCG es la DCG normalizada por la DCG máxima posible del conjunto de resultados cuando se clasifica de mayor a menor ganancia, ajustándose así a los diferentes números de resultados relevantes para diferentes consultas.
Al utilizar DCG y sus medidas relacionadas se parte de dos supuestos.
La DCG es un refinamiento de una medida más simple, la ganancia acumulativa (CG). [2] La ganancia acumulativa es la suma de los valores de relevancia graduados de todos los resultados en una lista de resultados de búsqueda. La CG no tiene en cuenta el rango (posición) de un resultado en la lista de resultados. La CG en una posición de rango particular se define como:
¿Dónde está la relevancia graduada del resultado en la posición ?
El valor calculado con la función CG no se ve afectado por los cambios en el orden de los resultados de búsqueda. Es decir, mover un documento altamente relevante por encima de un documento de mayor rango y menos relevante no cambia el valor calculado para CG (suponiendo que ). Con base en las dos suposiciones hechas anteriormente sobre la utilidad de los resultados de búsqueda, (N)DCG suele preferirse a CG. La ganancia acumulativa a veces se denomina precisión graduada.
La premisa de DCG es que los documentos altamente relevantes que aparecen más abajo en una lista de resultados de búsqueda deben ser penalizados, ya que el valor de relevancia calificado se reduce de forma logarítmica proporcional a la posición del resultado.
La fórmula habitual de DCG acumulado en una posición de rango particular se define como: [1]
Hasta 2013, no existía ninguna justificación teóricamente sólida para utilizar un factor de reducción logarítmico [3], aparte del hecho de que produce una reducción uniforme. Pero Wang et al. (2013) [2] dieron una garantía teórica para utilizar el factor de reducción logarítmico en el DCG normalizado (NDCG). Los autores muestran que para cada par de funciones de clasificación sustancialmente diferentes, el NDCG puede decidir cuál es mejor de manera consistente.
Una formulación alternativa de DCG [4] pone mayor énfasis en la recuperación de documentos relevantes:
La última fórmula se utiliza comúnmente en aplicaciones industriales, incluidas las principales empresas de búsqueda web [5] y plataformas de competencia de ciencia de datos como Kaggle. [6]
Estas dos formulaciones de DCG son las mismas cuando los valores de relevancia de los documentos son binarios ; [3] : 320 .
Obsérvese que Croft et al. (2010) y Burges et al. (2005) presentan el segundo DCG con un logaritmo de base e, mientras que ambas versiones del DCG anteriores utilizan un logaritmo de base 2. Al calcular el NDCG con la primera formulación del DCG, la base del logaritmo no importa, pero la base del logaritmo sí afecta el valor del NDCG para la segunda formulación. Claramente, la base del logaritmo afecta el valor del DCG en ambas formulaciones.
También se han desarrollado aproximaciones convexas y suaves a DCG, para su uso como función objetivo en métodos de aprendizaje basados en gradientes. [7]
Las listas de resultados de búsqueda varían en longitud según la consulta . No se puede comparar el rendimiento de un motor de búsqueda de una consulta a la siguiente de manera consistente utilizando solo DCG, por lo que la ganancia acumulada en cada posición para un valor elegido de debe normalizarse en todas las consultas. Esto se hace ordenando todos los documentos relevantes en el corpus por su relevancia relativa, lo que produce la máxima DCG posible hasta la posición , también llamada DCG ideal (IDCG) hasta esa posición. Para una consulta, la ganancia acumulada descontada normalizada , o nDCG, se calcula como:
donde IDCG es la ganancia acumulada descontada ideal,
y representa la lista de documentos relevantes (ordenados por su relevancia) en el corpus hasta la posición p.
Los valores nDCG de todas las consultas se pueden promediar para obtener una medida del rendimiento promedio del algoritmo de clasificación de un motor de búsqueda. Tenga en cuenta que en un algoritmo de clasificación perfecto, será igual a lo que produce un nDCG de 1,0. Todos los cálculos de nDCG son entonces valores relativos en el intervalo de 0,0 a 1,0 y, por lo tanto, son comparables entre consultas.
La principal dificultad encontrada al utilizar nDCG es la falta de disponibilidad de un ordenamiento ideal de resultados cuando solo se dispone de retroalimentación de relevancia parcial .
A los participantes del experimento se les presenta una lista de documentos en respuesta a una consulta de búsqueda y se les pide que juzguen la relevancia de cada documento para la consulta. Cada documento debe ser juzgado en una escala de 0 a 3, donde 0 significa que no es relevante, 3 significa que es muy relevante y 1 y 2 significan "algo intermedio". Para los documentos ordenados por el algoritmo de clasificación como
El usuario proporciona las siguientes puntuaciones de relevancia:
Es decir: el documento 1 tiene una relevancia de 3, el documento 2 tiene una relevancia de 2, etc. La ganancia acumulada de esta lista de resultados de búsqueda es:
Cambiar el orden de dos documentos no afecta la medida del CG. Si se intercambian y , el CG permanece igual. 11. El DCG se utiliza para destacar documentos muy relevantes que aparecen al principio de la lista de resultados. Si se utiliza la escala logarítmica para la reducción, el DCG para cada resultado en orden es:
Así que el resultado de este ranking es:
Ahora bien, un cambio de y da como resultado un DCG reducido porque un documento menos relevante se coloca más arriba en el ranking; es decir, un documento más relevante se descuenta más al colocarse en un rango más bajo.
El rendimiento de esta consulta en comparación con otra es incomparable en este formato, ya que la otra consulta puede tener más resultados, lo que da como resultado un DCG general mayor que no necesariamente es mejor. Para poder comparar, los valores de DCG deben normalizarse.
Para normalizar los valores de DCG, se necesita un orden ideal para la consulta dada. Para este ejemplo, ese orden sería el orden monótonamente decreciente de todos los juicios de relevancia conocidos. Además de los seis de este experimento, supongamos que también sabemos que hay un documento con grado de relevancia 3 para la misma consulta y un documento con grado de relevancia 2 para esa consulta. Entonces, el orden ideal es:
La clasificación ideal se reduce nuevamente a una longitud de 6 para que coincida con la profundidad del análisis de la clasificación:
El DCG de este ordenamiento ideal, o IDCG (DCG ideal) , se calcula para el rango 6:
Y entonces el nDCG para esta consulta se da como: