Pourquoi MAP et MRR échouent pour le classement de recherche (et quoi utiliser à la place)

utilise souvent Rang réciproque moyen (MRR) et Précision moyenne moyenne (MAP) pour évaluer la qualité de leur classement. Dans cet article, nous expliquerons pourquoi \(MAP\) et \(MRR\) ne correspondent pas au comportement des utilisateurs modernes dans le classement des recherches. Nous examinons ensuite deux métriques qui constituent de meilleures alternatives à \(MRR\) et \(MAP\).

Que sont le MRR et le MAP ?

Rang réciproque moyen (MRR)

Le rang réciproque moyen (\(MRR\)) est le rang moyen auquel apparaît le premier élément pertinent.

$$\mathrm{RR} = \frac{1}{\text{rang du premier élément pertinent}}$$

En e-commerce, le premier rang pertinent peut être le rang du premier élément cliqué en réponse à une requête

Pour l’exemple ci-dessus, supposons que l’élément pertinent est le deuxième élément. Cela signifie:
$$\mathrm{Rang réciproque} = \frac{1}{2}$$
Le classement réciproque est calculé pour toutes les requêtes de l’ensemble d’évaluation. Pour obtenir une seule métrique pour toutes les requêtes, nous prenons la moyenne des rangs réciproques pour obtenir le Rang réciproque moyen

$$\mathrm{Rang réciproque moyen} = \frac{1}{N}\sum_{i=1}^N {\frac{1}{\text{Rang du premier élément pertinent}}}$$

où \(N\) est le nombre de requêtes. À partir de cette définition, nous pouvons voir que \(MRR\) se concentre sur l’obtention précoce d’un résultat pertinent. Il ne mesure pas ce qui se passe après le premier résultat pertinent.

Précision moyenne moyenne (MAP)

La précision moyenne moyenne (\(MAP\) mesure dans quelle mesure le système récupère les éléments pertinents et à quelle heure ils sont affichés. Nous commençons par calculer la précision moyenne (AP) pour chaque requête. Nous définissons AP comme
$$\mathrm{AP} = \frac{1}{|R|}\sum_{k=1}^{K}\mathrm{Precision@}k \cdot \mathbf{1}[\text{item at } k \text{ is relevant}]$$
où \(|R|\) est le nombre d’éléments pertinents pour la requête
\(\mathrm{MAP}\) est le moyenne de \(\mathrm{AP}\) à travers les requêtes

L’équation ci-dessus semble longue, mais elle est en réalité simple. Utilisons un exemple pour le décomposer. Supposons qu’une requête comporte 3 éléments pertinents et que notre modèle prédit l’ordre suivant :

Rank: 1 2 3 4 5 
Item: R N R N R

(R = pertinent, N = non pertinent)
Pour calculer le \(CARTE\), nous calculons l’AP à chaque position pertinente:

• @1 : Précision = 1/1 = 1,0
• @3 : Précision = 2/3 ≈ 0,667
• @5 : Précision = 3/5 = 0,6

$$\mathrm{AP} = \frac{1}{3}(1,0 + 0,667 + 0,6) = 0,756$$
Nous calculons ce qui précède pour toutes les requêtes et faisons la moyenne pour obtenir le \(MAP\). La formule AP comporte deux éléments importants :

• Precision@k : Puisque nous utilisons Precision, la récupération plus précoce des éléments pertinents produit des valeurs de précision plus élevées. Si le modèle classe les éléments pertinents plus tard, Precision@k diminue en raison d’un k plus grand.
• Moyenne des précisions : nous faisons la moyenne des précisions sur le nombre total d’éléments pertinents. Si le système ne récupère jamais un élément ou le récupère au-delà du seuil, l’élément ne contribue en rien au numérateur tout en comptant toujours au dénominateur, ce qui réduit \(AP\) et \(MAP\).

Pourquoi MAP et MRR sont mauvais pour le classement de recherche

Maintenant que nous avons couvert les définitions, comprenons pourquoi \(MAP\) et \(MRR\) ne sont pas utilisés pour le classement des résultats de recherche.

La pertinence est graduée et non binaire

Lorsque nous calculons \(MRR\), nous prenons le rang du premier élément pertinent. Dans \(MRR\), nous traitons tous les éléments pertinents de la même manière. Cela ne fait aucune différence si un élément pertinent différent apparaît en premier. En réalité, différents éléments ont tendance à avoir une pertinence différente.

De même, dans \(MAP\), nous utilisons la pertinence binaire : nous recherchons simplement le prochain élément pertinent. Encore une fois, \(MAP\) ne fait aucune distinction dans le score de pertinence des éléments. Dans des cas réels, la pertinence est graduée et non binaire.

Item     : 1 2 3 
Relevance: 3 1 0

\(MAP\) et \(MRR\) ignorent tous deux la qualité de l’élément concerné. Ils ne parviennent pas à quantifier la pertinence.

Les utilisateurs analysent plusieurs résultats

Ceci est plus spécifique à \(MRR\). Dans le calcul \(MRR\), nous enregistrons le rang du premier élément pertinent. Et ignorez tout après. Cela peut être bon pour les recherches, l’assurance qualité, etc. Mais cela est mauvais pour les recommandations, la recherche de produits, etc.

Lors de la recherche, les utilisateurs ne s’arrêtent pas au premier résultat pertinent (sauf dans les cas où il n’y a qu’une seule bonne réponse). Les utilisateurs analysent plusieurs résultats qui contribuent à la pertinence globale de la recherche.

MAP met trop l’accent sur le rappel

\(MAP\) calcule
$$\mathrm{AP} = \frac{1}{|R|}\sum_{k=1}^{K}\mathrm{Precision@}k \cdot \mathbf{1}[\text{item at } k \text{ is relevant}]$$
En conséquence, chaque élément pertinent contribue à la notation. Manquer un élément pertinent nuit au score. Lorsque les utilisateurs effectuent une recherche, ils ne souhaitent pas trouver tous les éléments pertinents. Ils souhaitent trouver les meilleures options. L’optimisation \(MAP\) pousse le modèle à apprendre la longue traîne des éléments pertinents, même si la contribution à la pertinence est faible et que les utilisateurs ne défilent jamais aussi loin. Par conséquent, \(MAP\) met trop l’accent sur le rappel.

MAP se désintègre linéairement

Prenons l’exemple ci-dessous. Nous plaçons un élément pertinent à trois positions différentes et calculons l’AP

Rang	Précision@k	PA
1	1/1 = 1,0	1.0
3	1/3 ≈ 0,33	0,33
30	1/30 ≈ 0,033	0,033

L’AP au rang 30 semble pire que le rang 3, qui semble pire que le rang 1. Le score AP décroît linéairement avec le rang. En réalité, le rang 3 par rapport au rang 30 représente une différence de plus de 10 fois. C’est plutôt vu ou non vu.

\(MAP\) est sensible à la position mais seulement faiblement. Cela ne reflète pas la façon dont le comportement de l’utilisateur change en fonction de sa position. \(MAP\) est sensible à la position via Precision@k, où la désintégration avec le rang est linéaire. Cela ne reflète pas la façon dont l’attention des utilisateurs diminue dans les résultats de recherche.

NDCG et ERR sont de meilleurs choix

Pour le classement des résultats de recherche, \(NDCG\) et \(ERR\) sont de meilleurs choix. Ils résolvent les problèmes dont souffrent \(MRR\) et \(MAP\).

Rang réciproque attendu (ERR)

Le rang réciproque attendu (\(ERR\)) suppose un modèle d’utilisateur en cascade dans lequel un utilisateur effectue les opérations suivantes

• Parcourt la liste de haut en bas
• A chaque rang \(i\),
  • Avec la probabilité \(R_i\), l’utilisateur est satisfait et s’arrête
  • Avec la probabilité \(1- R_i\), l’utilisateur continue de regarder vers l’avenir

\(ERR\) calcule le rang réciproque attendu de cette position d’arrêt où l’utilisateur est satisfait :
$$\mathrm{ERR} = \sum_{r=1}^n \frac{1}{r} \cdot {R}_r \cdot \prod_{i=1}^{r-1}{1-{R}_i}$$
où \(R_i\) est \(R_i = \frac{2^{l_i}-1}{2^{l_m}}\) et \(l_m\) est la valeur d’étiquette maximale possible.

Comprenons en quoi \(ERR\) est différent de \(MRR\).

• \(ERR\) utilise \(R_i = \frac{2^{l_i}-1}{2^{l_m}}\), qui est une pertinence graduée, donc un résultat peut partiellement satisfaire un utilisateur
• \(ERR\) permet à plusieurs éléments pertinents de contribuer. Les premiers éléments de haute qualité réduisent la contribution des éléments ultérieurs

Exemple 1

Nous prendrons un exemple de jouet pour comprendre en quoi \(ERR\) et \(MRR\) diffèrent

Rank     : 1 2 3 
Relevance: 2 3 0

• \(MRR\) = 1 (l’élément pertinent est en première place)
• \(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\) dit classement parfait. \(ERR\) dit pas parfait car un élément de pertinence plus élevée apparaît plus tard

Exemple 2

Prenons un autre exemple pour voir comment un changement de classement impacte la contribution \(ERR\) d’un élément. Nous placerons un élément très pertinent à différentes positions dans une liste et calculerons la contribution \(ERR\) pour cet élément. Considérez les cas ci-dessous

• Classement 1 : \([8, 4, 4, 4, 4]\)
• Classement 2 : \([4, 4, 4, 4, 8]\)

Calculons

Pertinence	2^l−1	R(l)
4	15	0,0586
8	255	0,9961

En utilisant ceci pour calculer le \(ERR\) complet pour les deux classements, nous obtenons :

• Classement 1 : \(ERR\) ≈ 0,99
• Classement 2 : \(ERR\) ≈ 0,27

Si l’on regarde spécifiquement la contribution de l’item avec le score de pertinence de 8, on voit que la baisse de contribution de ce terme est de 6,36x. Si la pénalité était linéaire, la baisse serait de 5x.

Scénario	Contribution de pertinence-8 item
Rang 1	0,9961
Rang 5	0,1565
Facteur de chute	6,36x

Gain cumulatif actualisé normalisé (NDCG)

Le gain cumulatif actualisé normalisé (\(NDCG\)) est un autre excellent choix bien adapté au classement des résultats de recherche. \(NDCG\) repose sur deux idées principales

• Gain : Objets avec des scores de pertinence plus élevés valent beaucoup plus
• Rabais: les objets apparaissant plus tard valent beaucoup moins puisque les utilisateurs prêtent moins attention aux éléments ultérieurs

NDCG combine l’idée de gain et de remise pour créer un score. De plus, il normalise également le score pour permettre la comparaison entre différentes requêtes. Formellement, le gain et la remise sont définis comme

• \(\mathrm{Gain} = 2^{l_r}-1\)
• \(\mathrm{Remise} = log_2(1+r)\)

où \(l\) est l’étiquette de pertinence d’un élément à la position \(r\) et \(r\) est la position à laquelle il apparaît.

Le gain a une forme exponentielle, qui récompense une plus grande pertinence. Cela garantit que les éléments ayant un score de pertinence plus élevé contribuent beaucoup plus. La décote logarithmique pénalise le classement ultérieur des éléments pertinents. Combiné et appliqué à l’ensemble du classement, nous obtenons le gain cumulatif actualisé :

$$\mathrm{DCG@K} = \sum_{r=1}^{K} \frac{2^{l_r}-1}{\mathrm{log_2(1+r)}}$$

pour une liste classée donnée \(l_1, l_2, l_3, …l_k\). Le calcul de \(DCG@K\) est utile, mais l’échelle des étiquettes de pertinence peut varier en fonction des requêtes, ce qui rend la comparaison de \(DCG@K\) injuste. Donc nous avons besoin d’un moyen de normaliser les valeurs \(DCG@K\).

Nous faisons cela en calculant le \(IDCG@K\), qui est le gain cumulatif actualisé idéal. \(IDCG\) est le maximum possible \(DCG\) pour les mêmes éléments, obtenus en les triant par pertinence par ordre décroissant.

$$\mathrm{DCG@K} = \sum_{r=1}^{K} \frac{2^{l^*_r}-1}{\mathrm{log_2(1+r)}}$$

\(IDCG\) représente un classement parfait. Pour normaliser le \(DCG@K\), on calcule

$$\mathrm{NDCG@K} = \frac{\mathrm{DCG@K}}{\mathrm{IDCG@K}}$$

\(NDCG@K\) a les propriétés suivantes

• Borné entre 0 et 1
• Comparable entre les requêtes
• 1 est une commande parfaite

Exemple : Ordre bon ou légèrement pire

Dans cet exemple, nous prendrons deux classements différents de la même liste et comparerons leurs valeurs \(NDCG\). Supposons que nous ayons des éléments avec des étiquettes de pertinence sur une échelle de 0 à 3.
Classement A

Rank     : 1 2 3 
Relevance: 3 2 1

Classement B

Rank     : 1 2 3 
Relevance: 2 1 3

En calculant les composantes \(NDCG\), on obtient :

Rang	Gain (2 ^ l − 1)	Log de remise₂(1 + r)	Une contribution	contribution B
1	7	1h00	7h00	3h00
2	3	1,58	1,89	4.42
3	1	2h00	0,50	0,50

• DCG(A) = 9h39
• DCG(B) = 7,92
• IDCG = 9h39
• NDCG(A) = 9,39 / 9,39 = 1.0
• NDCG(B) = 7,92 / 9,39 = 0,84

Ainsi, le fait de retirer un élément pertinent du rang 1 entraîne une baisse importante.

NDCG : discussion supplémentaire

La décote qui constitue le dénominateur du calcul du \(DCG\) est de nature logarithmique. Elle augmente beaucoup plus lentement que linéairement.

$$\mathrm{discount(r)}=\frac{1}{\mathrm{log2​(1+r)}​}$$

Voyons comment cela se compare à la désintégration linéaire :

Rang (r)	Linéaire (1/r)	Logarithmique (1 / log₂(1 + r))
1	1h00	1h00
2	0,50	0,63
5	0,20	0,39
10	0,10	0,29
50	0,02	0,18

• \(1/r\) se désintègre plus rapide
• \(1/log(1+r)\) se désintègre Ralentissez

La remise logarithmique pénalise les classements ultérieurs de manière moins agressive qu’une remise linéaire. La différence entre le rang 1 → 2 est plus grande, mais la différence entre le rang 10 → 50 est faible.

La remise sur les grumes présente une réduction marginale décroissante dans les rangs ultérieurs pénalisants en raison de sa forme concave. Cela empêche \(NDCG\) de devenir une métrique très importante où les rangs 1 à 3 dominent le score. Une pénalité linéaire ignorerait les choix raisonnables effectués en aval.

Une réduction logarithmique reflète également le fait que l’attention de l’utilisateur diminue fortement en haut de la liste, puis s’aplatit au lieu de diminuer linéairement avec le classement.

Conclusion

\(MAP\) et \(MRR\) sont des mesures de recherche d’informations utiles, mais ne conviennent pas aux systèmes de classement de recherche modernes. Alors que \(MAP\) se concentre sur la recherche de tous les documents pertinents, \(MRR\) traite un problème de classement comme une métrique à position unique. \(MAP\) et \(MRR\) ignorent tous deux la pertinence graduée des éléments dans une recherche et les traitent comme binaires : pertinents et non pertinents.

\(NDCG\) et \(ERR\) reflètent mieux le comportement réel de l’utilisateur en tenant compte de plusieurs positions, permettant aux éléments d’avoir des scores non binaires, tout en accordant une plus grande importance aux premières positions. Pour les systèmes de classement de recherche, ces mesures sensibles à la position ne constituent pas seulement un meilleur choix : elles sont nécessaires.

Lectures complémentaires

• LambdaMART (bonne explication)
• Apprendre à classer (je recommande vivement de lire ceci. C’est long et complet, et c’est aussi l’inspiration pour cet article !)