Warum MAP und MRR beim Suchranking scheitern (und was man stattdessen verwenden sollte)

häufig verwenden Mittlerer reziproker Rang (MRR) Und Mittlere durchschnittliche Präzision (MAP) um die Qualität ihrer Rankings zu beurteilen. In diesem Beitrag werden wir diskutieren, warum (MAP) und (MRR) beim Suchranking schlecht mit dem modernen Benutzerverhalten übereinstimmen. Anschließend betrachten wir zwei Metriken, die als bessere Alternativen zu (MRR) und (MAP) dienen.

Was sind MRR und MAP?

Mittlerer reziproker Rang (MRR)

Der mittlere reziproke Rang ((MRR)) ist der durchschnittliche Rang, bei dem das erste relevante Aspect auftritt.

$$mathrm{RR} = frac{1}{textual content{Rang des ersten relevanten Components}}$$

Im E-Commerce kann der erste relevante Rang der Rang des ersten Artikels sein, auf den als Antwort auf eine Anfrage geklickt wurde

Nehmen Sie für das obige Beispiel an, dass der relevante Artikel der zweite Artikel ist. Das heisst:
$$mathrm{Reziproker Rang} = frac{1}{2}$$
Der reziproke Rang wird für alle Abfragen im Bewertungssatz berechnet. Um eine einzige Metrik für alle Abfragen zu erhalten, ermitteln wir den Mittelwert der reziproken Ränge Mittlerer reziproker Rang

$$mathrm{Mittlerer reziproker Rang} = frac{1}{N}sum_{i=1}^N {frac{1}{textual content{Rang des ersten relevanten Components}}}$$

Dabei ist (N) die Anzahl der Abfragen. Anhand dieser Definition können wir erkennen, dass sich (MRR) darauf konzentriert, frühzeitig ein relevantes Ergebnis zu erhalten. Es wird nicht gemessen, was nach dem ersten relevanten Ergebnis passiert.

Mittlere durchschnittliche Präzision (MAP)

Die mittlere durchschnittliche Präzision ((MAP) misst, wie intestine das System relevante Elemente abruft und wie früh sie angezeigt werden. Wir beginnen mit der Berechnung der durchschnittlichen Präzision (AP) für jede Abfrage. Wir definieren AP als
$$mathrm{AP} = frac{1}Rsum_{ok=1}^{Okay}mathrm{Precision@}ok cdot mathbf{1}(textual content{merchandise at } ok textual content{ ist related})$$
Dabei ist (|R|) die Anzahl der relevanten Elemente für die Abfrage
(mathrm{MAP}) ist die Durchschnitt von (mathrm{AP}) über Abfragen hinweg

Die obige Gleichung sieht viel aus, ist aber eigentlich einfach. Lassen Sie es uns anhand eines Beispiels aufschlüsseln. Angenommen, eine Abfrage enthält drei relevante Elemente und unser Modell sagt die folgende Reihenfolge voraus:

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

(R = related, N = nicht related)
Um die zu berechnen (KARTE), Wir berechnen den AP an jeder relevanten Place:

• @1: Präzision = 1/1 = 1,0
• @3: Präzision = 2/3 ≈ 0,667
• @5: Präzision = 3/5 = 0,6

$$mathrm{AP} = frac{1}{3}(1,0 + 0,667 + 0,6) = 0,756$$
Wir berechnen das Obige für alle Abfragen und mitteln sie, um den (MAP) zu erhalten. Die AP-Formel besteht aus zwei wichtigen Komponenten:

• Precision@ok: Da wir Precision verwenden, führt das frühere Abrufen relevanter Elemente zu höheren Präzisionswerten. Wenn das Modell relevante Elemente später einordnet, verringert sich Precision@ok aufgrund eines größeren ok
• Mittelung der Genauigkeiten: Wir mitteln die Genauigkeiten über die Gesamtzahl der relevanten Elemente. Wenn das System ein Aspect nie abruft oder es über den Grenzwert hinaus abruft, trägt das Aspect nichts zum Zähler bei, während es weiterhin im Nenner zählt, was (AP) und (MAP) reduziert.

Warum MAP und MRR schlecht für das Suchranking sind

Nachdem wir uns nun mit den Definitionen befasst haben, wollen wir verstehen, warum (MAP) und (MRR) nicht für das Rating der Suchergebnisse verwendet werden.

Die Relevanz wird abgestuft und nicht binär

Wenn wir (MRR) berechnen, nehmen wir den Rang des ersten relevanten Components. In (MRR) behandeln wir alle relevanten Elemente gleich. Es macht keinen Unterschied, ob zuerst ein anderes relevantes Aspect angezeigt wird. In der Realität neigen verschiedene Elemente dazu, unterschiedliche Relevanz zu haben.

In ähnlicher Weise verwenden wir in (MAP) die binäre Relevanz – wir suchen einfach nach dem nächsten relevanten Aspect. Auch hier macht (MAP) keinen Unterschied in der Relevanzbewertung der Elemente. In realen Fällen Relevanz ist abgestuft, nicht binär.

Merchandise     : 1 2 3 
Relevance: 3 1 0

(MAP) und (MRR) ignorieren beide, wie intestine das relevante Aspect ist. Es gelingt ihnen nicht, die Relevanz zu quantifizieren.

Benutzer scannen mehrere Ergebnisse

Dies ist spezifischer für (MRR). Bei der (MRR)-Berechnung erfassen wir den Rang des ersten relevanten Components. Und ignoriere danach alles. Dies kann für Suchvorgänge, Qualitätssicherung usw. intestine sein. Für Empfehlungen, Produktsuche usw. ist dies jedoch schlecht.

Während der Suche Benutzer bleiben nicht beim ersten relevanten Ergebnis stehen (außer in Fällen, in denen es nur eine richtige Antwort gibt). Benutzer scannen mehrere Ergebnisse, die zur allgemeinen Suchrelevanz beitragen.

MAP legt zu viel Wert auf die Erinnerung

(MAP) berechnet
$$mathrm{AP} = frac{1}Rsum_{ok=1}^{Okay}mathrm{Precision@}ok cdot mathbf{1}(textual content{merchandise at } ok textual content{ ist related})$$
Somit fließt jedes relevante Merchandise in die Bewertung ein. Das Fehlen relevanter Elemente schadet der Wertung. Wenn Benutzer eine Suche durchführen, sind sie nicht daran interessiert, alle relevanten Artikel zu finden. Sie sind daran interessiert, die besten Optionen zu finden. (MAP)-Optimierung bringt das Modell dazu, den langen Schwanz relevanter Elemente zu lernen, auch wenn der Relevanzbeitrag gering ist und Nutzer nie so weit scrollen. Daher betont (MAP) die Erinnerung überbetont.

MAP zerfällt linear

Betrachten Sie das folgende Beispiel. Wir platzieren einen relevanten Gegenstand an drei verschiedenen Positionen und berechnen den AP

AP auf Rang 30 sieht schlechter aus als Rang 3, der wiederum schlechter aussieht als Rang 1. Der AP-Wert nimmt linear mit dem Rang ab. In Wirklichkeit beträgt der Unterschied zwischen Rang 3 und Rang 30 mehr als das Zehnfache. Es ist eher gesehen als nicht gesehen.

(MAP) ist positionsempfindlich, aber nur schwach. Es spiegelt nicht wider, wie sich das Benutzerverhalten mit der Place ändert. (MAP) ist durch Precision@ok positionsempfindlich, wobei der Abfall mit dem Rang linear ist. Dies spiegelt nicht wider, wie die Aufmerksamkeit der Nutzer in den Suchergebnissen sinkt.

NDCG und ERR sind die bessere Wahl

Für das Rating der Suchergebnisse sind (NDCG) und (ERR) die bessere Wahl. Sie beheben die Probleme, unter denen (MRR) und (MAP) leiden.

Erwarteter reziproker Rang (ERR)

Der erwartete reziproke Rang ((ERR)) geht von einem Kaskadenbenutzermodell aus, bei dem ein Benutzer Folgendes tut

• Durchsucht die Liste von oben nach unten
• Bei jedem Rang (i),
  • Mit der Wahrscheinlichkeit (R_i) ist der Benutzer zufrieden und stoppt
  • Mit der Wahrscheinlichkeit (1- R_i) blickt der Benutzer weiter nach vorne

(ERR) berechnet die erwarteter reziproker Rang dieser Halteposition wo der Benutzer zufrieden ist:
$$mathrm{ERR} = sum_{r=1}^n frac{1}{r} cdot {R}_r cdot prod_{i=1}^{r-1}{1-{R}_i}$$
Dabei ist (R_i) (R_i = frac{2^{l_i}-1}{2^{l_m}}) und (l_m) der maximal mögliche Beschriftungswert.

Lassen Sie uns verstehen, wie sich (ERR) von (MRR) unterscheidet.

• (ERR) verwendet (R_i = frac{2^{l_i}-1}{2^{l_m}}), was abgestufte Relevanz ist, sodass ein Ergebnis einen Benutzer teilweise zufriedenstellen kann
• (ERR) ermöglicht den Beitrag mehrerer relevanter Elemente. Frühe Artikel von hoher Qualität verringern den Beitrag späterer Artikel

Beispiel 1

Wir nehmen ein Spielzeugbeispiel, um zu verstehen, wie sich (ERR) und (MRR) unterscheiden

Rank     : 1 2 3 
Relevance: 2 3 0

• (MRR) = 1 (relevantes Aspect steht an erster Stelle)
• (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) sagt perfektes Rating. (ERR) sagt nicht perfekt weil ein Aspect mit höherer Relevanz später erscheint

Beispiel 2

Nehmen wir ein weiteres Beispiel, um zu sehen, wie sich eine Änderung der Rangfolge auf den (ERR)-Beitrag eines Components auswirkt. Wir platzieren ein hochrelevantes Aspect an verschiedenen Positionen in einer Liste und berechnen den (ERR)-Beitrag für dieses Aspect. Betrachten Sie die folgenden Fälle

• Rang 1: ((8, 4, 4, 4, 4))
• Rang 2: ((4, 4, 4, 4, 8))

Lass uns rechnen

Wenn wir damit den vollständigen (ERR) für beide Rankings berechnen, erhalten wir:

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

Wenn wir uns speziell den Beitrag des Components mit der Relevanzbewertung 8 ansehen, sehen wir das Der Rückgang des Beitrags dieses Begriffs beträgt das 6,36-fache. Wenn die Strafe linear wäre, würde der Rückgang das Fünffache betragen.

Normalisierter diskontierter kumulativer Gewinn (NDCG)

Normalized Discounted Cumulative Achieve ((NDCG)) ist eine weitere gute Wahl, die sich intestine für das Rating von Suchergebnissen eignet. (NDCG) basiert auf zwei Hauptideen

• Gewinn: Gegenstände mit Höhere Relevanzwerte sind viel mehr wert
• Rabatt: Gegenstände, die später erscheinen, sind viel weniger wert da Benutzer späteren Elementen weniger Aufmerksamkeit schenken

NDCG kombiniert die Idee von Gewinn und Rabatt, um einen Rating zu erstellen. Darüber hinaus wird die Bewertung normalisiert, um einen Vergleich zwischen verschiedenen Abfragen zu ermöglichen. Formal sind Gewinn und Abschlag definiert als

• (mathrm{Gewinn} = 2^{l_r}-1)
• (mathrm{Rabatt} = log_2(1+r))

Dabei ist (l) die Relevanzbezeichnung eines Components an Place (r) und (r) die Place, an der es auftritt.

Der Gewinn hat eine exponentielle Kind, die eine höhere Relevanz belohnt. Dadurch wird sichergestellt, dass Elemente mit einem höheren Relevanzwert viel mehr beitragen. Der logarithmische Rabatt benachteiligt die spätere Rangfolge relevanter Artikel. Kombiniert und auf die gesamte Rangliste angewendet, erhalten wir den diskontierten kumulativen Gewinn:

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

für eine gegebene Rangliste (l_1, l_2, l_3, …l_k). Die (DCG@Okay)-Berechnung ist hilfreich, aber die Relevanzbezeichnungen können je nach Abfrage unterschiedlich skaliert sein, was den Vergleich von (DCG@Okay) zu einem unfairen Vergleich macht. Additionally Wir brauchen eine Möglichkeit, die (DCG@Okay)-Werte zu normalisieren.

Dies erreichen wir durch die Berechnung von (IDCG@Okay), dem idealen diskontierten kumulativen Gewinn. (IDCG) ist das maximal mögliche (DCG) für dieselben Elemente, erhalten durch Sortieren nach Relevanz in absteigender Reihenfolge.

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

(IDCG) stellt ein perfektes Rating dar. Um (DCG@Okay) zu normalisieren, berechnen wir

$$mathrm{NDCG@Okay} = frac{mathrm{DCG@Okay}}{mathrm{IDCG@Okay}}$$

(NDCG@Okay) hat die folgenden Eigenschaften

• Begrenzt zwischen 0 und 1
• Vergleichbar über Abfragen hinweg
• 1 ist eine perfekte Reihenfolge

Beispiel: Gute vs. etwas schlechtere Reihenfolge

In diesem Beispiel nehmen wir zwei verschiedene Rankings derselben Liste und vergleichen ihre (NDCG)-Werte. Angenommen, wir haben Elemente mit Relevanzbezeichnungen auf einer Skala von 0 bis 3.
Rang A

Rank     : 1 2 3 
Relevance: 3 2 1

Rang B

Rank     : 1 2 3 
Relevance: 2 1 3

Wenn wir die (NDCG)-Komponenten berechnen, erhalten wir:

• 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

Daher führt der Austausch eines relevanten Gegenstands von Rang 1 zu einem großen Rückgang.

NDCG: Zusätzliche Diskussion

Der Rabatt, der den Nenner der (DCG)-Berechnung bildet, ist logarithmischer Natur. Es steigt viel langsamer als linear.

$$mathrm{low cost(r)}=frac{1}{mathrm{log2​(1+r)}​}$$

Sehen wir uns an, wie sich dies mit dem linearen Zerfall vergleichen lässt:

• (1/r) zerfällt Schneller
• (1/log(1+r)) zerfällt Langsamer

Der logarithmische Rabatt bestraft spätere Ränge weniger aggressiv als ein linearer Rabatt. Der Unterschied zwischen Rang 1 → 2 ist größer, aber der Unterschied zwischen Rang 10 → 50 ist gering.

Der Log-Rabatt hat aufgrund seiner konkaven Kind eine geringfügige Verringerung der Bestrafung späterer Ränge. Dies verhindert, dass (NDCG) zu einer kopflastigen Metrik wird, bei der die Ränge 1–3 die Punktzahl dominieren. Eine lineare Strafe würde vernünftige Entscheidungen weiter unten ignorieren.

Ein logarithmischer Rabatt spiegelt auch die Tatsache wider, dass die Aufmerksamkeit der Benutzer am Anfang der Liste stark abnimmt und dann abflacht, anstatt linear mit dem Rang abzunehmen.

Abschluss

(MAP) und (MRR) sind nützliche Metriken für den Informationsabruf, eignen sich jedoch schlecht für moderne Suchrankingsysteme. Während sich (MAP) darauf konzentriert, alle relevanten Dokumente zu finden, behandelt (MRR) ein Rankingproblem als eine Einzelpositionsmetrik. (MAP) und (MRR) ignorieren beide die abgestufte Relevanz von Elementen in einer Suche und behandeln sie als binär: related und nicht related.

(NDCG) und (ERR) spiegeln das tatsächliche Benutzerverhalten besser wider, indem sie mehrere Positionen berücksichtigen, sodass Elemente nicht-binäre Bewertungen haben können, während Spitzenpositionen eine höhere Bedeutung beigemessen werden. Für Suchrankingsysteme sind diese positionsempfindlichen Metriken nicht nur eine bessere Wahl – sie sind sogar notwendig.

Weiterführende Literatur

• LambdaMART (gute Erklärung)
• Rating lernen (Ich empfehle dringend, dies zu lesen. Es ist lang und gründlich und dient auch als Inspiration für diesen Artikel!)