Hispanopedia Wiki
Articulo de referencia

Ganancia acumulada descontada

La ganancia acumulativa descontada ( DCG ) [ 1 ] es una medida de la calidad de la clasificación en la recuperación de información . A menudo se normaliza para que sea comparabl...

Hispanopedia WikiContenido en espanolLectura gratuita

La ganancia acumulativa descontada ( DCG ) [ 1 ] 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, dando como resultado la DCG normalizada (nDCG o NDCG) [ 2 ] . La NDCG se usa frecuentemente para medir la efectividad de los algoritmos de los motores de búsqueda y 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. La NDCG es la DCG normalizada por la DCG máxima posible del conjunto de resultados cuando se clasifican de mayor a menor ganancia, ajustándose así a las diferentes cantidades 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 una posición más alta).
  2. Los documentos altamente 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

DCG es un refinamiento de una medida más simple, la Ganancia Acumulativa (CG). [ 3 ] La Ganancia Acumulativa es la suma de los valores de relevancia graduada 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. La CG en una posición de rango particularpag{\displaystyle p}se define como:

doGRAMOpag=∑i=1pagrmili{\displaystyle \mathrm {CG_{p}} =\sum _{i=1}^{p}rel_{i}}

Dóndermili{\displaystyle rel_{i}}es la relevancia graduada del resultado en la posicióni{\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 relevantedi{\displaystyle d_{i}}por encima de un documento de mayor rango y menos relevantedj{\displaystyle d_{j}}no cambia el valor calculado para CG (suponiendoi,j≤pag{\displaystyle i,j\leq p}). Basándonos en las dos suposiciones anteriores 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.

Ganancia acumulada descontada

La premisa de DCG es que los documentos altamente relevantes que aparecen en posiciones inferiores en una lista de resultados de búsqueda deben ser penalizados, ya que el valor de relevancia graduada se reduce logarítmicamente de forma proporcional a la posición del resultado.

La fórmula habitual de DCG acumulada en una posición de rango particularpag{\displaystyle p}se define como: [ 4 ]

DdoGRAMOpag=∑i=1pagrmiliregistro2⁡(i+1)=rmil1+∑i=2pagrmiliregistro2⁡(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)}}}

Until 2013, there was no theoretically sound justification for using a logarithmic reduction factor[5] other than the fact that it produces a smooth reduction. But Wang et al. (2013)[3] gave theoretical guarantee for using the logarithmic reduction factor in Normalized DCG (NDCG). The authors show that for every pair of substantially different ranking functions, the NDCG can decide which one is better in a consistent manner.

An alternative formulation of DCG[6] places stronger emphasis on retrieving relevant documents:

DCGp=∑i=1p2reli−1log2⁡(i+1){\displaystyle \mathrm {DCG_{p}} =\sum _{i=1}^{p}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}

The latter formula is commonly used in industrial applications including major web search companies[7] and data science competition platforms such as Kaggle.[8]

These two formulations of DCG are the same when the relevance values of documents are binary;[5]:320reli∈{0,1}{\displaystyle rel_{i}\in \{0,1\}}.

Note that Croft et al. (2010) and Burges et al. (2005) present the second DCG with a log of base e, while both versions of DCG above use a log of base 2. When computing NDCG with the first formulation of DCG, the base of the log does not matter, but the base of the log does affect the value of NDCG for the second formulation. Clearly, the base of the log affects the value of DCG in both formulations.

Convex and smooth approximations to DCG have also been developed, for use as an objective function in gradient based learning methods.[9]

Normalized DCG

Search result lists vary in length depending on the query. Comparing a search engine's performance from one query to the next cannot be consistently achieved using DCG alone, so the cumulative gain at each position for a chosen value of p{\displaystyle p} should be normalized across queries. This is done by sorting all relevant documents in the corpus by their relative relevance, producing the maximum possible DCG through position p{\displaystyle p}, also called Ideal DCG (IDCG) through that position. For a query, the normalized discounted cumulative gain, or nDCG, is computed as:

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

where IDCG is ideal discounted cumulative gain,

IDCGp=∑i=1|RELp|2reli−1log2⁡(i+1){\displaystyle \mathrm {IDCG_{p}} =\sum _{i=1}^{|REL_{p}|}{\frac {2^{rel_{i}}-1}{\log _{2}(i+1)}}}

and RELp{\displaystyle REL_{p}} represents the list of relevant documents (ordered by their relevance) in the corpus up to position p.

The nDCG values for all queries can be averaged to obtain a measure of the average performance of a search engine's ranking algorithm. Note that in a perfect ranking algorithm, the DCGp{\displaystyle DCG_{p}} will be the same as the IDCGp{\displaystyle IDCG_{p}} producing an nDCG of 1.0. All nDCG calculations are then relative values on the interval 0.0 to 1.0 and so are cross-query comparable.

La principal dificultad que se presenta al utilizar nDCG es la falta de un ordenamiento ideal de los resultados cuando solo se dispone de información parcial sobre la relevancia .

Ejemplo

Al presentarle 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 ser juzgado en una escala de 0 a 3, donde 0 significa no relevante, 3 significa altamente relevante y 1 y 2 significan "en algún punto intermedio". Para los documentos ordenados por el algoritmo de clasificación como

D1,D2,D3,D4,D5,D6{\displaystyle D_{1},D_{2},D_{3},D_{4},D_{5},D_{6}}

El usuario proporciona las siguientes puntuaciones de relevancia:

3,2,3,0,1,2{\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:

doGRAMO6=∑i=16rmili=3+2+3+0+1+2=11{\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 a la medida CG. SiD3{\displaystyle D_{3}}yD4{\displaystyle D_{4}}Se intercambian, el CG permanece igual, 11. El DCG se utiliza para enfatizar los documentos altamente relevantes que aparecen al principio de la lista de resultados. Utilizando la escala logarítmica para la reducción, el DCG para cada resultado en orden es:

Entonces elDdoGRAMO6{\displaystyle DCG_{6}}de esta clasificación es:

DdoGRAMO6=∑i=16rmiliregistro2⁡(i+1)=3+1.262+1.5+0+0,387+0,712=6.861{\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 deD3{\displaystyle D_{3}}yD4{\displaystyle D_{4}}da como resultado una reducción del DCG porque un documento menos relevante se coloca más arriba en la clasificación; es decir, un documento más relevante se descarta más al colocarse en un rango inferior.

El rendimiento de esta consulta es incomparable con el de otra, ya que la otra consulta podría arrojar más resultados, lo que resultaría en un DCG general mayor que no necesariamente sería mejor. Para poder compararlos, los valores del DCG deben normalizarse.

Para normalizar los valores DCG, se necesita un ordenamiento ideal para la consulta dada. Para este ejemplo, ese ordenamiento sería el ordenamiento 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 documentoD7{\displaystyle D_{7}}con grado de relevancia 3 para la misma consulta y un documentoD8{\displaystyle D_{8}}con grado de relevancia 2 para esa consulta. Entonces, el orden ideal es:

3,3,3,2,2,2,1,0{\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:

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

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

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

Y así, el nDCG para esta consulta se da como:

norteDdoGRAMO6=DdoGRAMO6IDdoGRAMO6=6.8618.740=0,785{\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 de mala calidad en el resultado. Por ejemplo, si una consulta devuelve dos resultados con puntuaciones de 1,1,1 y 1,1,1,0 respectivamente, ambos se considerarían igualmente buenos, incluso si el último contiene un documento de mala calidad. Para las clasificaciones Excelente, Regular, Malo, se podrían usar puntuaciones numéricas de 1,0,-1 en lugar de 2,1,0 . Esto reduciría la puntuación si se devuelven resultados de mala calidad, priorizando la precisión sobre la exhaustividad; sin embargo, este enfoque puede resultar en una puntuación general negativa.
  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 para obtener el rango 3 para el primero y el rango 5 para el segundo. Una forma de tener en cuenta esta limitación es imponer un tamaño de conjunto fijo para el conjunto de resultados y usar puntuaciones mínimas para los documentos faltantes. 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. El DCG normalizado puede no ser adecuado 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 solo considera el primer resultado. Si un conjunto de resultados contiene solo 1 restaurante de la zona cercana, mientras que el otro contiene 5, ambos terminarían teniendo la misma puntuación, aunque el segundo sea más completo.

Véase también

Referencias

  1. ↑ Järvelin, Kalervo; Kekäläinen, Jaana (2000). "Métodos de evaluación de IR para la recuperación de documentos de gran relevancia" . SIGIR . ACM: 41– 48. doi : 10.1145/345508.345545 . ISBN 978-1-58113-226-7.
  2. ↑ Järvelin, Kalervo; Kekäläinen, Jaana (2002). "Evaluación de técnicas de IR basada en ganancia acumulada" . Transacciones ACM sobre sistemas de información . 20 (4): 422– 446. doi : 10.1145/582415.582418 . ISSN 1046-8188 . 
  3. 1 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 acumulativa descontada normalizada (NDCG). En Actas de la 26.ª Conferencia Anual sobre Teoría del Aprendizaje (COLT 2013).
  4. ^ 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)
  5. 1 2 B. Croft; D. Metzler; T. Strohman (2010). Motores de búsqueda: Recuperación de información en la práctica . Addison Wesley.
  6. ↑ Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton y Greg Hullender. 2005. Aprendizaje de clasificación 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
  7. ↑ "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 .
  8. ↑ "Ganancia acumulada descontada normalizada" . Archivado del original el 23 de marzo de 2014. Consultado el 23 de marzo de 2014 .
  9. ↑ D. Cossock y T. Zhang, "Análisis estadístico de la clasificación óptima de subconjuntos bayesianos", en IEEE Transactions on Information Theory , vol. 54, n.º 11, págs. 5140-5154, noviembre de 2008, doi: 10.1109/TIT.2008.929939.