Wie Suchmaschinen entscheiden, was du nicht findest

Wie Suchmaschinen entscheiden, was du nicht findest

Suchmaschinen helfen Nutzer*innen, sich in großen Dokumentensammlungen zurechtzufinden, sei es im Web, im Angebot von Online-Shops oder in großen digitalen Archiven wie der Deutschen Digitalen Bibliothek. Wer eine solche Sammlung nicht manuell durchsuchen kann, ist auf die Suchmaschine angewiesen und muss ihren Ergebnissen vertrauen. Doch sind diese Suchergebnisse frei von Verzerrungen? Die meisten Entwicklungsteams von Suchportalen führen diese Überprüfung nicht durch, dabe sind gute Suchfunktionen im Interesse aller Beteiligten.

Für die Nutzenden kann die Bewertung der Suchergebnisse komplexer sein, als es klingt. Je nach Anspruch an die Qualität der Suchergebnisse erfordert es Wissen über die Dokumente selbst (z.B. Qualität, Inhalt, Länge) und die technische Infrastruktur (z. B. das eingesetzte Retrieval-Modell). In der Praxis werden Suchmaschinen aber meist nur danach bewertet, ob sie bekannte relevante Dokumente effektiv und effizient finden. Ob die Ergebnisse dabei systematisch verzerrt sind, wird selten untersucht.

Dieser Artikel beschreibt, wie Verzerrungen in Suchergebnissen gemessen und damit sichtbar und bewertbar gemacht werden können.

Bias

Wikipedia definiert Algorithmic Bias als "systematische Verzerrungen in den Ergebnissen algorithmischer Entscheidungsprozesse." Nicht nur bei Suchmaschinen ist der Begriff "Bias" negativ besetzt. Dabei wird leicht übersehen, dass Bias zur Kernfunktion einer Suchmaschine gehört: Dokumente sollen nach ihrer Relevanz für eine Suchanfrage sortiert werden. Die Ergebnisse sollen also zugunsten jener Dokumente verzerrt sein, die das Informationsbedürfnis der Nutzer*innen am besten treffen. Dieser Bias ist gewollt.

Das Problem beginnt dort, wo der Bias ungewollt ist. Die Suche nach "black girls" lieferte bei Google, Bing und Yandex Seiten, die von Pornografie dominiert waren. Weil Suchergebnisse die öffentliche Wahrnehmung beeinflussen, ist es wichtig, solche Verzerrungen zu erkennen und zu korrigieren.

Bias kann entstehen, ohne dass er beabsichtigt war. Beispiele für Quellen solcher Verzerrungen in Dokumentensammlungen sind:

• Die Sammlung bildet die "reale Welt" möglicherweise nicht gut ab. Ein Grund dafür kann die Zerstörung historischer Dokumente sein, durch den in der Sammlung zeitliche Lücken entstanden sein können.
• Bei der Digitalisierung hängt die Qualität stark von der Vorlage ab (Layout, Erhaltungszustand, Schriftart) und davon, ob geeignete Technologie für Texterkennung und Nachbearbeitung eingesetzt wird.
• Inhalt und textuelle Eigenschaften von Dokumenten (z. B. Länge und Wiederholungen) können beeinflussen, wie Retrieval Modelle das Dokument bewerten.
• Der Zugang zu Dokumenten wird in der Regel über eine Suchoberfläche gewährt. Das (Nicht-)Vorhandensein von Funktionen wie Facetten und logischen Operatoren sowie das verwendete Retrieval-Modell können beeinflussen, welche Dokumente leichter oder schwerer zu finden sind als andere.
• Die Darstellung der Suchergebnisse bestimmt, wie viel Nutzer*innen wahrnehmen. Studien zeigen, dass die meisten nur die ersten zehn Ergebnisse betrachten und bei Misserfolg lieber eine neue Suche starten, als auf die nächste Seite zu blättern.
• Schließlich spielen die Nutzer*innen selbst eine Rolle: Wer die nötige Fachterminologie nicht kennt oder mit Suchfunktionen nicht vertraut ist, findet bestimmte Dokumente schlicht nicht.

Welche Biases am Ende das Suchergebnis beeinflussen, ist schwer zu ermitteln, da die Analyse ein gründliches Verständnis der beteiligten Daten und Software-Werkzeuge erfordert.

Bias messen und visualisieren

Bias lässt sich als Abweichung von Gleichverteilung verstehen. Um Bias zu messen und zu visualisieren eignen sich zwei Werkzeuge aus der Wirtschaftswissenschaft: der Gini-Koeffizient und die Lorenz-Kurve, ursprünglich entwickelt, um Einkommensungleichheit zu messen.

Gini-Koeffizient

Der Gini-Koeffizient (G) kann einen Wert zwischen 0 und 1 annehmen. Je niedriger der Gini-Koeffizient, desto "gleicher" ist die Verteilung. Ein Wert von G=0 würde erreicht, wenn der Wohlstand in einer Gesellschaft absolut gleichmäßig verteilt wäre. Ein Wert nahe G=1 bedeutet, dass ein einziges Individuum den gesamten Wohlstand besitzt, während die große Mehrheit nichts besitzt.

Lorenz-Kurven

Die Lorenz-Kurve wurde ursprünglich 1905 von Max Otto Lorenz entwickelt, um Ungleichheiten in der Vermögensverteilung zu visualisieren. In einer perfekt kommunistischen Gesellschaft ist die Lorenz-Kurve eine Diagonale. Die folgende Grafik zeigt Beispiele von Lorenz-Kurven für eine Bevölkerung von zehn Individuen und verschiedene Vermögensverteilungen.

Die schwarze Linie in der Grafik stellt die "perfekt kommunistische" Gesellschaft dar, in der der Wohlstand gleichmäßig verteilt ist und G=0.

Die grüne Lorenz-Kurve drückt eine weniger gleiche Gesellschaft G=0,5 aus, in der vier Individuen keinen Wohlstand besitzen, vier Individuen 50 % und zwei Individuen die anderen 50 % besitzen. Die orangefarbene Kurve zeigt eine "perfekte Tyrannei" G=0,9, in der ein Individuum den gesamten Wohlstand besitzt und die anderen nichts.

Retrievability

Üblicherweise wird die Qualität einer Suchmaschine über Precision (Wie viele der gefundenen Dokumente sind relevant?) und Recall (Wie viele der relevanten Dokumente wurden gefunden?) bewertet, oft kombiniert im F1-Score. Diese Metriken setzen voraus, dass Menschen vorher beurteilt haben, ob ein Dokument für eine bestimmte Anfrage relevant ist. Das ist aufwändig und bei großen Sammlungen kaum oder nur für einen Teil der Sammlung umsetzbar.

2008 führten Azzopardi et al. die Retrievability-Metrik als Ergänzung zu traditionellen Metriken ein.

Retrievability-Score

Der Retrievability-Score r(d) misst, wie leicht ein Dokument d auffindbar ist. Die Relevanz eines Dokuments für einen eingegebenen Suchbegriff wird hierbei nicht berücksichtigt. Der Retrievability-Score ist das Ergebnis einer kumulativen Bewertungsfunktion, definiert als:

wobei

• (c) einen Cutoff definiert, der die Anzahl der Dokumente repräsentiert, die Nutzende bereit sind anzuschauen
• (o_q) die Wichtigkeit einer Anfrage gewichtet
• (k_{dq}) der Rang des Dokuments (d) in der Ergebnisliste für die Anfrage (q) ist
• (f) den Wert 1 zurückgibt, wenn das Dokument unterhalb des Rangs (c) erfolgreich abgerufen wird, und andernfalls 0.

Kurz gesagt: r(d) zählt, bei wie vielen Suchbegriffen (q \in Q) ein Dokument (d) innerhalb der ersten (c) Ergebnisse auftaucht.

Aufbau der Retrievability-Bewertung

Für eine Retrievability-Analyse brauchen wir drei Dinge: eine Suchmaschine, Suchbegriffe und eine Dokumentensammlung. Als Suchbegriffe dienen entweder echte Suchanfragen von Nutzer*innen oder künstlich erzeugte Anfragen. Letztere können generiert werden, indem die häufigsten Terme und Bigramme aus der Sammlung extrahiert (nach Stemming und Stoppwort-Entfernung) und daraus Ein- und Zwei-Wort-Anfragen gebildet werden.

Die Dokumentensammlung wird zunächst in einer Suchmaschine indiziert. Anschließend werden die Suchbegriffe automatisiert in die Suchmaschine gestellt und die Listen aller Ergebnisse gesichert. Die Ergebnislisten der Suchmaschine werden darauf analysiert, wie oft jedes Dokument gefunden wurde und auf welchem Rang. Bei der Auswertung kann die Verzerrung der Suchergebnisse bei verschiedenen Cutoff-Werten (c) betrachtet werden. Typischerweise wird ein Wert von (c=10) verwendet um den Bias zu messen, den typische Nutzer*innen erfahren, die nur die obersten zehn Ergebnisse betrachten.

Validierung

Ob die Retrievability-Scores in einem konkreten Setup aussagekräftig sind, lässt sich mit einem Known-Item-Search-Setup überprüfen.

Dazu teilen wir die Dokumente in mehrere Teilmengen ein, abhängig von ihrem (r(d))-Score. Aus jeder Teilmenge wählen wir eine zufällige Stichprobe von (n) Dokumenten. Für jedes dieser Dokumente zählen wir die Vorkommen einzigartiger Terme und wählen die zwei oder drei häufigsten Terme aus (unter Ignorierung von Stoppwörtern). Diese Terme sollen das Dokument am besten repräsentieren und bilden die Anfragen, die wir gegen die vollständige Sammlung stellen.

Für jedes der ausgewählten Dokumente bewerten wir den Rang in der Ergebnisliste der generierten Anfrage und berechnen den Mean Reciprocal Rank (MRR) als Maß für ihre Retrievalleistung. Mit dem Kolmogorow-Smirnow-Test können wir testen, ob die Ergebnisse signifikant sind.

Retrieval-Bias

Die vorherigen Abschnitte beschreiben, wie Verzerrungen gemessen und visualisiert werden können und wie die Auffindbarkeit eines Dokuments mit dem (r(d))-Score gemessen werden kann. Um das zu veranschaulichen stellen wir das Vorgehen und die Ergebnisse einer Studie vor, die auf der Joint Conference on Digital Libraries (JCDL) 2016 veröffentlicht wurde.

Bias in Retrieval-Modellen: Vergleich von BM25 mit LM1000

In dieser Studie untersuchten wir die Ungleichheit in Retrievability-Scores für verschiedene Retrieval-Modelle: Okapi BM25 und Language Model (LM1000) mit Bayes-Glättung bei (\mu = 1.000). Für diese Evaluation verwendeten wir die historische Zeitungssammlung der Nationalbibliothek der Niederlande (Delpher), die mehr als 102 Millionen OCR-erfasste Nachrichtenelemente umfasst (Artikel, Anzeigen, amtliche Bekanntmachungen und Bildunterschriften). Wir generierten simulierte Anfragen aus dem Inhalt der Dokumente, konnten aber auch echte Anfragen aus den Suchlogs der Bibliothek verwenden.

Wir bewerteten die Ungleichheit in den Ergebnissen für die 10, 100 und 1.000 am höchsten gerankten Dokumente ((c=10, c=100) und (c=1.000)).

Anfragetyp	Retrieval-Modell	c=10	c=100	c=1.000
Echte Anfragen	BM25	0,97	0,89	0,76
Echte Anfragen	LM1000	0,97	0,90	0,78
Simulierte Anfragen	BM25	0,85	0,52	–
Simulierte Anfragen	LM1000	0,89	0,71	–

Die niedrigeren Gini-Koeffizienten zeigen, dass BM25 im Allgemeinen das weniger verzerrte Retrieval-Modell ist, was mit den Ergebnissen anderer Studien übereinstimmt (siehe zum Beispiel). Dies wird auch sichtbar, wenn wir die Lorenz-Kurven ((c=100)) darstellen: Die Kurve für LM1000 weicht deutlich stärker von der Diagonalen ab als die Kurve für BM25.

Während der Gini-Koeffizient und die Lorenz-Kurve uns helfen, das Ausmaß des Bias zu bewerten, können sie uns nicht den Ursprung verraten. Dafür sind weitere Analysen erforderlich.

Beispiel: Dokumentlänge

In der oben genannten Studie untersuchten wir auch, ob Suchergebnisse von der Länge der Dokumente beeinflusst werden. Die Länge der Texte in der KB-Sammlung variiert von 33 bis 381.563 Wörtern (bei einer durchschnittlichen Länge von 362 Wörtern).

Wir sortierten alle Dokumente nach ihrer Länge und teilten sie in Gruppen von 20.000 Dokumenten ein (insgesamt 5.135 Gruppen). Für jede Gruppe berechneten wir den mittleren r(d).

Das für LM1000 erhaltene Muster zeigt einen Aufwärtstrend für längere Dokumente, was bedeutet, dass längere Dokumente leichter auffindbar sind.

Die Ergebnisse für BM25 zeigen hingegen, dass Dokumente mittlerer Länge am besten auffindbar sind. Dokumente an beiden Extremen sind weniger auffindbar.

In beiden Mustern ist ein Bias erkennbar: LM1000 bevorzugt eindeutig längere Dokumente, BM25 überkompensiert für lange Dokumente, während es bei kurzen Dokumenten nicht ausreichend kompensiert.

Was bedeutet das für die Praxis?

Precision und Recall messen, ob eine Suchmaschine relevante Dokumente findet. Die Retrievability-Metrik misst etwas anderes: ob bestimmte Dokumente systematisch benachteiligt werden. Wie unser Vergleich von BM25 und LM1000 zeigt, kann allein die Wahl des Retrieval-Modells dafür sorgen, dass kurze oder lange Dokumente schwerer auffindbar sind.

Eine Retrievability-Analyse lässt sich mit simulierten Anfragen durchführen und erfordert keine manuellen Relevanzurteile. Damit ist sie die günstigste Methode, um systematische Verzerrungen in einer Suchinfrastruktur sichtbar zu machen. Wer einen Suchdienst betreibt, sollte sie als festen Bestandteil der Qualitätssicherung einsetzen.