Ganancia acumulada descontada

Medida de calidad de clasificación

La ganancia acumulativa descontada ( DCG ) es una medida para clasificar la calidad en la recuperación de información . A menudo se normaliza para que sea comparable entre consultas, lo que genera un DCG normalizado (nDCG o NDCG) . NDCG se utiliza a menudo para medir la eficacia de los algoritmos de los motores de búsqueda y aplicaciones relacionadas. Utilizando una escala de relevancia graduada de documentos en un conjunto de resultados de un motor de búsqueda, DCG suma la utilidad, o ganancia , de los resultados descontados por su posición en la lista de resultados. ^[1] NDCG es un DCG normalizado por el máximo DCG 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

Se hacen dos suposiciones al utilizar DCG y sus medidas relacionadas.

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 altamente relevantes son más útiles que los documentos marginalmente relevantes, los cuales a su vez son más útiles que los documentos no relevantes.

Ganancia acumulada

DCG es un refinamiento de una medida más simple, la ganancia acumulativa (CG). ^[2] La ganancia acumulada es la suma de los valores de relevancia calificados de todos los resultados en una lista de resultados de búsqueda. CG no tiene en cuenta el rango (posición) de un resultado en la lista de resultados. El 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 la 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 (asumiendo ). Según las dos suposiciones hechas anteriormente sobre la utilidad de los resultados de búsqueda, generalmente se prefiere (N)DCG 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 logarítmicamente 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 había ninguna justificación teórica sólida para utilizar un factor de reducción logarítmico ^[3] aparte del hecho de que produce una reducción suave. Pero Wang et al. (2013) ^[2] dieron garantía teórica para el uso del factor de reducción logarítmico en 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 usa 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 iguales cuando los valores de relevancia de los documentos son binarios ; ^{[3] : 320} . ${\displaystyle rel_{i}\in \{0,1\}}$

Tenga en cuenta que Croft et al. (2010) y Burges et al. (2005) presentan el segundo DCG con un registro de base e, mientras que ambas versiones de DCG anteriores utilizan un registro de base 2. Al calcular NDCG con la primera formulación de DCG, la base del registro no importa, pero sí la base de el registro afecta el valor de NDCG para la segunda formulación. Claramente, la base del registro afecta el valor de 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 . La comparación del rendimiento de un motor de búsqueda de una consulta a la siguiente no se puede lograr 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 clasificando todos los documentos relevantes en el corpus por su relevancia relativa, produciendo el máximo DCG posible a través de la posición , también llamado DCG Ideal (IDCG) a través de 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 para 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á lo mismo que producir un nDCG de 1,0. Todos los cálculos de nDCG son 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 los resultados cuando solo se dispone de información de relevancia parcial.

Ejemplo

Al recibir una lista de documentos en respuesta a una consulta de búsqueda, se le pide a un participante del experimento que juzgue la relevancia de cada documento para la consulta. Cada documento debe evaluarse en una escala de 0 a 3, donde 0 significa no relevante, 3 significa muy relevante y 1 y 2 significan "en algún punto 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 este listado 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 cualesquiera no afecta la medida del CG. Si se cambian y , el CG sigue siendo el mismo. 11. DCG se utiliza para enfatizar documentos muy relevantes que aparecen al principio de la lista de resultados. Usando la escala logarítmica para la reducción, el DCG para cada resultado en orden es: ${\displaystyle D_{3}}$ ${\displaystyle D_{4}}$

Entonces el 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, un cambio de y da como resultado un DCG reducido porque un documento menos relevante ocupa un lugar más alto en la clasificación; es decir, un documento más relevante tiene más descuento al ubicarse en un rango inferior. ${\displaystyle D_{3}}$ ${\displaystyle D_{4}}$

El rendimiento de esta consulta a otra es incomparable de esta forma, 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 comparar, los valores DCG deben normalizarse.

Para normalizar los valores DCG, se necesita un orden ideal para la consulta dada. Para este ejemplo, ese orden sería el tipo 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 la longitud 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 orden ideal, o IDCG (Ideal DCG) , se calcula en el rango 6:

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

Y entonces el nDCG para esta consulta queda como:

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

Limitaciones

1. El DCG normalizado no penaliza la presencia 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 las valoraciones de clasificación Excelente, Regular y Malo, se podrían utilizar puntuaciones numéricas 1,0,-1 en lugar de 2,1,0 . Esto haría que la puntuación bajara si se arrojan malos resultados, priorizando la precisión de los resultados sobre la recuperación; sin embargo, este enfoque puede dar lugar a una puntuación negativa general.
2. El DCG normalizado no penaliza la falta de documentos 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 calcule en el puesto 3 para el primero y en el puesto 5 para este último. Una forma de tener en cuenta esta limitación es imponer un tamaño de conjunto fijo para el conjunto de resultados y utilizar puntuaciones mínimas para los documentos que faltan. En el ejemplo anterior, usaríamos las puntuaciones 1,1,1,0,0 y 1,1,1,1,1 y citaríamos nDCG como nDCG@5.
3. Es posible que el DCG normalizado no sea adecuado para medir el rendimiento de consultas que pueden tener varios resultados igualmente buenos. Esto es especialmente cierto cuando esta métrica se limita sólo a los primeros resultados, como suele hacerse en la práctica. Por ejemplo, para consultas como "restaurantes", nDCG@1 representa 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.

Ver 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 ganancia acumulada 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. Aprender a clasificar mediante 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 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 de subconjuntos óptimos 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.