A menudo utilizan el rango recíproco medio (MRR) y la precisión media media (MAP) para evaluar la calidad de sus clasificaciones. En esta publicación, discutiremos por qué \(MAP\) y \(MRR\) no están alineados con el comportamiento de los usuarios modernos en el ranking de búsqueda. Luego analizamos dos métricas que sirven como mejores alternativas a \(MRR\) y \(MAP\).
¿Qué son MRR y MAP?
Rango recíproco medio (MRR)
El rango recíproco medio (\(MRR\)) es el rango promedio donde ocurre el primer elemento relevante.
$$\mathrm{RR} = \frac{1}{\text{rango del primer elemento relevante}}$$
En el comercio electrónico, la primera clasificación relevante puede ser la clasificación del primer elemento en el que se hace clic en respuesta a una consulta.
Para el ejemplo anterior, supongamos que el elemento relevante es el segundo elemento. Esto significa:
$$\mathrm{Rango recíproco} = \frac{1}{2}$$
La clasificación recíproca se calcula para todas las consultas del conjunto de evaluación. Para obtener una métrica única para todas las consultas, tomamos la media de rangos recíprocos para obtener el rango recíproco medio.
$$\mathrm{Rango recíproco medio} = \frac{1}{N}\sum_{i=1}^N {\frac{1}{\text{Rango del primer elemento relevante}}}$$
donde \(N\) es el número de consultas. A partir de esta definición, podemos ver que \(MRR\) se centra en obtener un resultado relevante de forma temprana. No mide lo que sucede después del primer resultado relevante.
Precisión media media (MAP)
La precisión promedio media (\(MAP\) mide qué tan bien el sistema recupera los elementos relevantes y qué tan temprano se muestran. Primero comenzamos calculando la precisión promedio (AP) para cada consulta. Definimos AP como
$$\mathrm{AP} = \frac{1}{|R|}\sum_{k=1}^{K}\mathrm{Precisión@}k \cdot \mathbf{1}[\text{item at } k \text{ is relevant}]$$
donde \(|R|\) es el número de elementos relevantes para la consulta
\(\mathrm{MAP}\) es el promedio de \(\mathrm{AP}\) entre consultas
La ecuación anterior parece muy complicada, pero en realidad es simple. Usemos un ejemplo para desglosarlo. Supongamos que una consulta tiene 3 elementos relevantes y nuestro modelo predice el siguiente orden:
Rango: 1 2 3 4 5 Artículo: RNRNR
(R = relevante, N = no relevante)
Para calcular el \(MAP\), calculamos el AP en cada posición relevante:
@1: Precisión = 1/1 = 1,0 @3: Precisión = 2/3 ≈ 0,667 @5: Precisión = 3/5 = 0,6
$$\mathrm{AP} = \frac{1}{3}(1,0 + 0,667 + 0,6) = 0,756$$
Calculamos lo anterior para todas las consultas y las promediamos para obtener el \(MAP\). La fórmula AP tiene dos componentes importantes:
Precision@k: dado que utilizamos Precision, recuperar elementos relevantes antes produce valores de precisión más altos. Si el modelo clasifica los elementos relevantes más adelante, Precision@k se reduce debido a una k mayor. Promedio de las precisiones: promediamos las precisiones sobre el número total de elementos relevantes. Si el sistema nunca recupera un elemento o lo recupera más allá del límite, el elemento no aporta nada al numerador mientras sigue contando en el denominador, lo que reduce \(AP\) y \(MAP\).
Por qué MAP y MRR son malos para el ranking de búsqueda
Ahora que hemos cubierto las definiciones, comprendamos por qué \(MAP\) y \(MRR\) no se utilizan para clasificar los resultados de búsqueda.
La relevancia se califica, no es binaria
Cuando calculamos \(MRR\), tomamos la clasificación del primer elemento relevante. En \(MRR\), tratamos todos los elementos relevantes por igual. No hay diferencia si aparece primero un elemento relevante diferente. En realidad, diferentes elementos tienden a tener diferente relevancia.
De manera similar, en \(MAP\), utilizamos relevancia binaria: simplemente buscamos el siguiente elemento relevante. Nuevamente, \(MAP\) no hace distinción en la puntuación de relevancia de los ítems. En casos reales, la relevancia se califica, no de forma binaria.
Artículo: 1 2 3 Relevancia: 3 1 0
\(MAP\) y \(MRR\) ignoran qué tan bueno es el elemento relevante. No logran cuantificar la relevancia.
Los usuarios escanean múltiples resultados
Esto es más específico de \(MRR\). En el cálculo \(MRR\), registramos la clasificación del primer elemento relevante. E ignorar todo después. Puede ser bueno para búsquedas, control de calidad, etc. Pero es malo para recomendaciones, búsqueda de productos, etc.
Durante la búsqueda, los usuarios no se detienen en el primer resultado relevante (excepto en los casos en los que sólo hay una respuesta correcta). Los usuarios escanean múltiples resultados que contribuyen a la relevancia general de la búsqueda.
MAP enfatiza demasiado el recuerdo
\(MAPA\) calcula
$$\mathrm{AP} = \frac{1}{|R|}\sum_{k=1}^{K}\mathrm{Precisión@}k \cdot \mathbf{1}[\text{item at } k \text{ is relevant}]$$
Como consecuencia, cada elemento relevante contribuye a la puntuación. Omitir cualquier elemento relevante perjudica la puntuación. Cuando los usuarios realizan una búsqueda, no están interesados en encontrar todos los elementos relevantes. Están interesados en encontrar las mejores opciones. La optimización \(MAP\) empuja al modelo a aprender la larga cola de elementos relevantes, incluso si la contribución de relevancia es baja y los usuarios nunca se desplazan tan lejos. Por lo tanto, \(MAP\) pone demasiado énfasis en el recuerdo.
MAP decae linealmente
Considere el siguiente ejemplo. Colocamos un elemento relevante en tres posiciones diferentes y calculamos el AP.
El AP en el rango 30 se ve peor que el rango 3, que a su vez se ve peor que el rango 1. La puntuación AP decae linealmente con el rango. En realidad, el rango 3 frente al rango 30 es una diferencia de más de 10 veces. Es más bien visto o no visto.
\(MAP\) es sensible a la posición, pero sólo débilmente. No refleja cómo cambia el comportamiento del usuario con la posición. \(MAP\) es sensible a la posición a través de Precision@k, donde la caída con el rango es lineal. Esto no refleja cómo cae la atención del usuario en los resultados de búsqueda.
NDCG y ERR son mejores opciones
Para la clasificación de los resultados de búsqueda, \(NDCG\) y \(ERR\) son mejores opciones. Solucionan los problemas que sufren \(MRR\) y \(MAP\).
Rango recíproco esperado (ERR)
El rango recíproco esperado (\(ERR\)) asume un modelo de usuario en cascada en el que un usuario hace lo siguiente
Explora la lista de arriba a abajo. En cada rango \(i\), Con probabilidad \(R_i\), el usuario está satisfecho y se detiene. Con probabilidad \(1- R_i\), el usuario continúa mirando hacia adelante.
\(ERR\) calcula el rango recíproco esperado de esta posición de parada donde el usuario está satisfecho:
$$\mathrm{ERR} = \sum_{r=1}^n \frac{1}{r} \cdot {R}_r \cdot \prod_{i=1}^{r-1}{1-{R}_i}$$
donde \(R_i\) es \(R_i = \frac{2^{l_i}-1}{2^{l_m}}\) y \(l_m\) es el valor de etiqueta máximo posible.
Entendamos en qué se diferencia \(ERR\) de \(MRR\).
\(ERR\) usa \(R_i = \frac{2^{l_i}-1}{2^{l_m}}\), que es relevancia graduada, por lo que un resultado puede satisfacer parcialmente a un usuario \(ERR\) permite que contribuyan varios elementos relevantes. Los primeros artículos de alta calidad reducen la contribución de los artículos posteriores.
Ejemplo 1
Tomaremos un ejemplo de juguete para comprender en qué se diferencian \(ERR\) y \(MRR\)
Clasificación: 1 2 3 Relevancia: 2 3 0 \(MRR\) = 1 (el elemento relevante está en primer lugar) \(ERR\) = \(R_1 = {(2^2 – 1)}/{2^3} = {3}/{8}\) \(R_2 ={(2^3 – 1)}/{2^3} = {7}/{8}\) \(R_3 ={(2^0 – 1)}/{2^3} = 0\) \(ERR = (1/1) \cdot R_1 + (1/2) \cdot R_2 + (1/3) \cdot R_3 = 0.648\) \(MRR\) dice clasificación perfecta. \(ERR\) dice que no es perfecto porque aparece un elemento de mayor relevancia más adelante
Ejemplo 2
Tomemos otro ejemplo para ver cómo un cambio en la clasificación afecta la contribución \(ERR\) de un elemento. Colocaremos un elemento muy relevante en diferentes posiciones de una lista y calcularemos la contribución \(ERR\) para ese elemento. Considere los casos siguientes
Clasificación 1: \([8, 4, 4, 4, 4]\) Clasificación 2: \([4, 4, 4, 4, 8]\)
Vamos a calcular
Usando esto para calcular el \(ERR\) completo para ambas clasificaciones, obtenemos:
Clasificación 1: \(ERR\) ≈ 0,99 Clasificación 2: \(ERR\) ≈ 0,27
Si nos fijamos específicamente en la contribución del ítem con puntuación de relevancia de 8, vemos que la caída en la contribución de ese término es de 6,36x. Si la penalización fuera lineal, la caída sería 5x.
Ganancia acumulada descontada normalizada (NDCG)
La ganancia acumulativa descontada normalizada (\(NDCG\)) es otra excelente opción que resulta muy adecuada para clasificar los resultados de búsqueda. \(NDCG\) se basa en dos ideas principales
Ganancia: los elementos con puntuaciones de relevancia más altas valen mucho más Descuento: los elementos que aparecen más tarde valen mucho menos ya que los usuarios prestan menos atención a los elementos posteriores
NDCG combina la idea de ganancia y descuento para crear una puntuación. Además, también normaliza la puntuación para permitir la comparación entre diferentes consultas. Formalmente, la ganancia y el descuento se definen como
\(\mathrm{Ganancia} = 2^{l_r}-1\) \(\mathrm{Descuento} = log_2(1+r)\)
donde \(l\) es la etiqueta de relevancia de un elemento en la posición \(r\) y \(r\) es la posición en la que ocurre.
La ganancia tiene una forma exponencial, que recompensa una mayor relevancia. Esto garantiza que los elementos con una puntuación de relevancia más alta contribuyan mucho más. El descuento logarítmico penaliza la clasificación posterior de los artículos relevantes. Combinado y aplicado a toda la lista clasificada, obtenemos la ganancia acumulativa descontada:
$$\mathrm{DCG@K} = \sum_{r=1}^{K} \frac{2^{l_r}-1}{\mathrm{log_2(1+r)}}$$
para una lista clasificada dada \(l_1, l_2, l_3,…l_k\). El cálculo de \(DCG@K\) es útil, pero las etiquetas de relevancia pueden variar en escala entre consultas, lo que hace que comparar \(DCG@K\) sea injusto. Entonces necesitamos una forma de normalizar los valores de \(DCG@K\).
Lo hacemos calculando el \(IDCG@K\), que es la ganancia acumulada descontada ideal. \(IDCG\) es el máximo \(DCG\) posible para los mismos elementos, obtenido al ordenarlos por relevancia en orden descendente.
$$\mathrm{DCG@K} = \sum_{r=1}^{K} \frac{2^{l^*_r}-1}{\mathrm{log_2(1+r)}}$$
\(IDCG\) representa una clasificación perfecta. Para normalizar el \(DCG@K\), calculamos
$$\mathrm{NDCG@K} = \frac{\mathrm{DCG@K}}{\mathrm{IDCG@K}}$$
\(NDCG@K\) tiene las siguientes propiedades
Acotado entre 0 y 1 Comparable entre consultas 1 es un orden perfecto
Ejemplo: pedidos buenos o ligeramente peores
En este ejemplo, tomaremos dos clasificaciones diferentes de la misma lista y compararemos sus valores \(NDCG\). Supongamos que tenemos elementos con etiquetas de relevancia en una escala de 0 a 3.
Clasificación A
Clasificación: 1 2 3 Relevancia: 3 2 1
Clasificación B
Clasificación: 1 2 3 Relevancia: 2 1 3
Calculando los componentes \(NDCG\), obtenemos:
DCG(A) = 9,39 DCG(B) = 7,92 IDCG = 9,39 NDCG(A) = 9,39 / 9,39 = 1,0 NDCG(B) = 7,92 / 9,39 = 0,84
Por lo tanto, cambiar un elemento relevante fuera del rango 1 provoca una gran caída.
NDCG: Discusión adicional
El descuento que forma el denominador del cálculo \(DCG\) es de naturaleza logarítmica. Aumenta mucho más lentamente que linealmente.
$$\mathrm{descuento(r)}=\frac{1}{\mathrm{log2(1+r)}}$$
Veamos cómo se compara esto con la caída lineal:
(r)lineal
(1/r)Logarítmico
(1 / log₂(1 + r))11.001.0020.500.6350.200.39100.100.29500.020.18
\(1/r\) decae más rápido \(1/log(1+r)\) decae más lento
El descuento logarítmico penaliza las clasificaciones posteriores de manera menos agresiva que un descuento lineal. La diferencia entre los rangos 1 → 2 es mayor, pero la diferencia entre los rangos 10 → 50 es pequeña.
El descuento logarítmico tiene una reducción marginal decreciente al penalizar los rangos posteriores debido a su forma cóncava. Esto evita que \(NDCG\) se convierta en una métrica muy importante donde los rangos 1 a 3 dominan la puntuación. Una penalización lineal ignoraría decisiones razonables en niveles inferiores.
Un descuento logarítmico también refleja el hecho de que la atención del usuario cae bruscamente en la parte superior de la lista y luego se aplana en lugar de disminuir linealmente con la clasificación.
Conclusión
\(MAP\) y \(MRR\) son métricas de recuperación de información útiles, pero no son adecuadas para los sistemas de clasificación de búsqueda modernos. Mientras que \(MAP\) se centra en encontrar todos los documentos relevantes, \(MRR\) trata un problema de clasificación como una métrica de una sola posición. \(MAP\) y \(MRR\) ignoran la relevancia clasificada de los elementos en una búsqueda y los tratan como binarios: relevantes y no relevantes.
\(NDCG\) y \(ERR\) reflejan mejor el comportamiento real del usuario al tener en cuenta múltiples posiciones, lo que permite que los elementos tengan puntuaciones no binarias, al tiempo que se da mayor importancia a las primeras posiciones. Para los sistemas de clasificación de búsqueda, estas métricas sensibles a la posición no son sólo una mejor opción, sino que son necesarias.
Lectura adicional
LambdaMART (buena explicación) Learning To Rank (recomiendo encarecidamente leer esto. Es largo y completo, ¡y también es la inspiración para este artículo!)