Ganancia acumulada descontada

Medida de la calidad del ranking

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.

Descripción general

Al utilizar DCG y sus medidas relacionadas se parte de dos supuestos.

1. Los documentos altamente relevantes son más útiles cuando aparecen antes en la lista de resultados de un motor de búsqueda (tienen clasificaciones más altas)
2. Los documentos muy relevantes son más útiles que los documentos marginalmente relevantes, que a su vez son más útiles que los documentos no relevantes.

Ganancia acumulada

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: ${\displaystyle p}$

${\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}$

¿Dónde está la relevancia graduada del resultado en la posición ? ${\displaystyle rel_{i}}$ ${\displaystyle i}$

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. ${\displaystyle d_{i}}$ ${\displaystyle d_{j}}$ ${\displaystyle i,j\leq p}$

Ganancia acumulada descontada

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] ${\displaystyle p}$

${\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)}}}$

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:

${\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}$

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} . ${\displaystyle rel_{i}\in \{0,1\}}$

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]

DCG normalizado

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: ${\displaystyle p}$ ${\displaystyle p}$

${\displaystyle \mathrm {nDCG_{p}} ={\frac {DCG_{p}}{IDCG_{p}}}}$,

donde IDCG es la ganancia acumulada descontada ideal,

${\displaystyle \mathrm {IDCG_{p}} =\sum _{i=1}^{|REL_{p}|}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}$

y representa la lista de documentos relevantes (ordenados por su relevancia) en el corpus hasta la posición p. ${\displaystyle REL_{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. ${\displaystyle DCG_{p}}$ ${\displaystyle IDCG_{p}}$

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 .

Ejemplo

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

${\displaystyle D_{1},D_{2},D_{3},D_{4},D_{5},D_{6}}$

El usuario proporciona las siguientes puntuaciones de relevancia:

${\displaystyle 3,2,3,0,1,2}$

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:

${\displaystyle \mathrm {CG_{6}} =\sum _{i=1}^{6}rel_{i}=3+2+3+0+1+2=11}$

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: ${\displaystyle D_{3}}$ ${\displaystyle D_{4}}$

Así que el resultado de este ranking es: ${\displaystyle DCG_{6}}$

${\displaystyle \mathrm {DCG_{6}} =\sum _{i=1}^{6}{\frac {rel_{i}}{\log _{2}(i+1)}}=3+1.262+1.5+0+0.387+0.712=6.861}$

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. ${\displaystyle D_{3}}$ ${\displaystyle D_{4}}$

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: ${\displaystyle D_{7}}$ ${\displaystyle D_{8}}$

${\displaystyle 3,3,3,2,2,2,1,0}$

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:

${\displaystyle 3,3,3,2,2,2}$

El DCG de este ordenamiento ideal, o IDCG (DCG ideal) , se calcula para el rango 6:

${\displaystyle \mathrm {IDCG_{6}} =8.740}$

Y entonces el nDCG para esta consulta se da como:

${\displaystyle \mathrm {nDCG_{6}} ={\frac {DCG_{6}}{IDCG_{6}}}={\frac {6.861}{8.740}}=0.785}$

Limitaciones

1. La DCG normalizada no penaliza la inclusión de documentos incorrectos en el resultado. Por ejemplo, si una consulta devuelve dos resultados con puntuaciones 1,1,1 y 1,1,1,0 respectivamente, ambos se considerarían igualmente buenos, incluso si el último contiene un documento incorrecto. Para los juicios de clasificación Excelente, Regular, Malo , se podrían utilizar puntuaciones numéricas 1,0,-1 en lugar de 2,1,0 . Esto haría que la puntuación se redujera si se devuelven resultados incorrectos, priorizando la precisión de los resultados sobre la recuperación; sin embargo, este enfoque puede dar como resultado una puntuación negativa general.
2. El DCG normalizado no penaliza los documentos faltantes en el resultado. Por ejemplo, si una consulta devuelve dos resultados con puntuaciones 1,1,1 y 1,1,1,1,1 respectivamente, ambos se considerarían igualmente buenos, suponiendo que el DCG ideal se calcula con una puntuación de 3 para el primero y de 5 para el segundo. Una forma de tener en cuenta esta limitación es aplicar un tamaño de conjunto fijo para el conjunto de resultados y utilizar puntuaciones mínimas para los documentos faltantes. En el ejemplo anterior, utilizaríamos las puntuaciones 1,1,1,0,0 y 1,1,1,1,1 y citaríamos nDCG como nDCG@5.
3. La DCG normalizada puede no ser adecuada para medir el rendimiento de consultas que pueden tener varios resultados igualmente buenos. Esto es especialmente cierto cuando esta métrica se limita solo a los primeros resultados, como suele hacerse en la práctica. Por ejemplo, para consultas como "restaurantes", nDCG@1 tiene en cuenta solo el primer resultado. Si un conjunto de resultados contiene solo 1 restaurante del área cercana mientras que el otro contiene 5, ambos terminarían teniendo la misma puntuación aunque el último sea más completo.

Véase también

• Medidas de evaluación (recuperación de información)
• Aprendiendo a clasificar

Referencias

1. Kalervo Järvelin, Jaana Kekäläinen, "Evaluación de técnicas de IR basada en ganancias acumuladas". Transacciones ACM sobre sistemas de información 20 (4), 422–446 (2002)
2. Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Wei Chen, Tie-Yan Liu . 2013. Un análisis teórico de las medidas de clasificación de la ganancia acumulativa descontada normalizada (NDCG). En Actas de la 26.ª Conferencia Anual sobre Teoría del Aprendizaje (COLT 2013).
3. B. Croft; D. Metzler; T. Strohman (2010). Motores de búsqueda: recuperación de información en la práctica . Addison Wesley.
4. Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton y Greg Hullender. 2005. Aprendiendo a clasificar usando el descenso de gradiente. En Actas de la 22.ª conferencia internacional sobre aprendizaje automático (ICML '05). ACM, Nueva York, NY, EE. UU., 89-96. DOI=10.1145/1102351.1102363 http://doi.acm.org/10.1145/1102351.1102363
5. "Introducción a la recuperación de información - Evaluación" (PDF) . Universidad de Stanford. 21 de abril de 2013 . Consultado el 23 de marzo de 2014 .
6. "Ganancia acumulada descontada normalizada". Archivado desde el original el 23 de marzo de 2014 . Consultado el 23 de marzo de 2014 .
7. D. Cossock y T. Zhang, "Análisis estadístico de la clasificación óptima de subconjuntos de Bayes", en IEEE Transactions on Information Theory , vol. 54, núm. 11, págs. 5140-5154, noviembre de 2008, doi: 10.1109/TIT.2008.929939.