Back to top

Relevanz – Ein Graduate Level Course

The Graduate Level Course

Von Paul Nelson, leitender Architekt bei Search Technologies

Dieser Artikel ist Teil 1 in einer Reihe von vier Artikeln.

Eigentlich wollte ich nur einen Artikel "Einführung in die Relevanz" schreiben. Aber irgendwie kam mir das zu wenig vor, da die Relevanz inzwischen ein wichtiger Bereich akademischer Forschung geworden ist. Also habe ich doch lieber einen Graduate Level Course daraus gemacht. Schnappt euch ein paar Chips und eine Sprite, dann können wir es uns gemütlich machen und ein bisschen über Relevanz bei Suchmaschinen reden.

Ich habe schon früher Blogs über Relevanz verfasst (siehe "Was bedeutet "Relevanz" eigentlich?)", bisher aber immer als eine Art philosophische Diskussion der Relevanz. Ziel dieses Blogs ist es, tiefer in die verschiedenen Formen der Relevanz einzudringen, um zu erklären wie diese berechnet werden und wofür sie genutzt werden. Ich werde versuchen, Mathe außen vor zu lassen, aber ich kann nichts versprechen.

 

Termfrequenz (Term Frequency, TF) 

Die Termfrequenz ist das mit weitem Abstand häufigste Kriterium für die Relevanzbewertung. Und auch das älteste. Sie wurde schon in den 70er Jahren von Suchmaschinen genutzt. Hierbei handelt es sich einfach um die Anzahl, wie oft ein Abfragebegriff in einem Dokument vorkommt. Dokumente, in denen der Abfragebegriff häufig vorkommt, werden dabei als relevanter eingestuft. Multipliziert mit IDF (siehe unten) erhält man den Standard "TF-IDF" (siehe auch den Wikipedia-Eintrag für TF-IDF und die auf Dokumentgröße genormte Version Okapi BM25). 

Der Begriff "Frequenz" ist hierbei aber eigentlich eine falsche Bezeichnung. Die meisten Algorithmen verwenden die einfache Summe der Nennungen. Die "Frequenz" wäre also 2, wenn der Suchbegriff zweimal vorkommt, 3, wenn er dreimal vorkommt usw.

Das zeigt auch eins der Probleme mit der Termfrequenz. Sie wertet größere Dokumente höher als kleine Dokumente, einfach weil in größeren Dokumenten mehr Begriffe vorkommen und daher das in der Abfrage gesuchte Wort häufiger auftreten wird. 

Suchmaschinen können dies ausgleichen, indem die Termfrequenz bei großen Dokumenten relativ zur Dokumentgröße angepasst wird. Leider kann dies wiederum Probleme bei sehr kleinen Dokumenten verursachen (Verzeichnissen, Werbeanzeigen, Mikroblogs usw.), da ein einzelner Treffer in einem nur 5 Wörter umfassenden Dokument viel höher gewertet würde als ein einzelner Treffer in einem 10 Wörter umfassenden Dokument, obwohl der rein lingustische Unterschied minimal ist. 

Ein zweites Problem bei der Termfrequenz ist, dass kleine Unterschiede eine große Auswirkung auf das Gesamtergebnis haben können. Ein Dokument, in dem der Begriff zweimal vorkommt, erhält eine doppelt so hohe Bewertung wie ein Dokument, in dem er nur einmal vorkommt. So große Unterschiede in der Bewertung passen meist nicht zum Unterschied der sprachlichen Nutzung, in der solche Abweichungen oft nur zufällig sind.

 

Inverse Dokumenthäufigkeit (Inverse Document Frequency, IDF) 

Der Informationstheorie zufolge ist die Aussagekraft eines Datentokens invers proportional zu seiner Häufigkeit. Token mit hoher Frequenz tragen wenig Informationen. Token mit niedriger Frequenz tragen viele Informationen. Diese Theorie ist die Grundlage für die Statistiken der inversen Dokumenthäufigkeit (IDF). Sie besagt, dass Wörter wichtiger sind, wenn sie nur in wenigen Dokumenten vorkommen, und dass Dokumente, in denen diese Wörter häufiger vorkommen, für den Benutzer relevanter sind. 

In der Anfangszeit haben sich Entwickler von Suchmaschinen Sorgen gemacht, dass Benutzer nach zu gebräuchlichen Begriffen suchen könnten und dadurch keine hilfreichen Ergebnisse erhalten würden. Wörter wie "über", "sehr", "enthalten" usw. werden im allgemeinen Sprachgebrauch so häufig genutzt, dass sie Suchergebnisse in eine falsche Richtung bringen würden, wenn man sie in die Abfrage einbezieht. Die Ergebnisse sind meist zielgerichteter, wenn man diese Wörter aus der Abfrage entfernt. 

Die normalerweise verwendete Formel für IDF lautet:

IDF(T) = log(N/dbCount[T]) 

 

Hierbei ist "N" die Anzahl aller Dokumente in der Datenbank (oder eine andere sehr große Konstante – mit dem Ziel, die Eingabe in die Funktion log() anzuheben, um negative Werte für IDF zu verhindern) und "dbCount[T]" die Anzahl aller Dokumente, die den Begriff T enthalten. 

Man muss dabei beachten, dass IDF nur vom Abfragebegriff (T) und der Datenbank abhängt. Der Wert unterscheidet sich also nicht von Dokument zu Dokument. Daher wird IDF auch keine Auswirkung bei Abfragen mit nur einem einzelnen Wort haben. Wenn man nun IDF mit TF verbindet, erhält man die normale "TF-IDF"-Formel:

 TF-IDF(T) = TF * log(N/dbCount[T])

 

Ich persönlich bin ja kein Fan der Statistiken für inverse Dokumenthäufigkeit. Es ist schon sehr bezeichnend, dass der englische Wikipedia-Eintrag zu Informationstheorie die folgende Aussage enthält:

Es ist zu beachten, dass diese Aspekte keinen Bezug zur Bedeutung einer Nachricht haben. So kann beispielsweise eine Floskel wie "Vielen Dank, beehren Sie uns bald wieder" länger ausfallen als die dringende Bitte "Rufen Sie einen Krankenwagen", obwohl diese in vielen Zusammenhängen deutlich wichtiger ist. Die Informationstheorie befasst sich jedoch nicht mit der Bedeutung oder Aussage einer Nachricht, diese sind Fragen zur Qualität der Daten, nicht zu Quantität und Lesbarkeit der Daten, welche rein durch Wahrscheinlichkeiten bestimmt werden.

  1. IDF bedenkt nicht die statistische Größe des Samples. Die Statistiken für Wörter, die in wenigen Dokumenten auftreten, sind, durch die reduzierte Größe der Samples, sehr unzuverlässig. Anders ausgedrückt, Wörter, die nur sehr unregelmäßig auftreten, haben meist nur sehr niedrige Vertrauenswerte. Die Frage von sinkendem Vertrauen ist in IDF nicht bedacht.
  2. Auf gleiche Art können Schreibfehler unregelmäßig auftreten und daher durch IDF sehr hoch bewertet werden, ohne wirklich nützlich zu sein.
  3. Kombination sehr üblicher Worte hingegen können sehr wichtig sein. Als Beispiel besteht der Name der Band "The Who" aus zwei Wörtern, die im Englischen sehr gebräuchlich sind, zusammengesetzt aber nur diese eine sehr spezielle Bedeutung haben.
  4. Kleinere Unterschiede in der Wortzählung können für die Bewertung durch IDF bedeutend sein, ohne dass sie einen echten Unterschied für den Benutzer ausmachen. Wenn man beispielsweise eine Datenbank mit einer Million Dokumente hat, wird ein Wort, das in 10 Dokumenten auftaucht, nicht viel wichtiger sein als eins, das in 100 Dokumenten auftaucht.
  5. Der beste Anhaltspunkt, welche Wörter wichtig sind, ist immer noch die Eingabe des Benutzers. Algorithmen, welche die Qualität der Begriffe überbewerten, werden langfristig bei einer großen Zahl Abfragen Probleme verursachen, indem sie Wörter unterbewerten, die dem Benutzer aber tatsächlich wichtig sind.
  6. Wenn die Suchmaschine schnell genug ist und dynamische Teaser angezeigt werden, können Benutzer, die schlechte Begriffe für ihre Abfrage verwenden, schnell genug erkennen, welche Wörter sie aus ihrer Suche entfernen sollten. Der Nutzen von IDF für die Sucherfahrung ist in diesem Fall nur sehr eingeschränkt vorhanden.

Der letzte Punkt ist besonders wichtig. IDF wird oft als das Wundermittel für sprachnahe Abfragen wie z.B. "ich würde gerne ein Rezept für Truthahn finden" angesehen. Aber wer gibt schon solche Suchanfragen ein. Die meisten Menschen werden stattdessen eingeben: "Rezept Truthahn". Alleine schon, weil die meisten Benutzer faul sind und nicht unnötig viel tippen wollen. Mit guten Abfragen, in denen alle Worte wichtig sind – oder zumindest vom Benutzer als wichtig angesehen werden – sorgt übermäßiges IDF eher für schlechte Ergebnisse. 

Der letzte Punkt ist, dass IDF von der Datenbank als Ganzes abhängt. Dies kann Suchmaschinen vor enorme Schwierigkeiten stellen, vor allem, wenn in sehr großen Datenbanken gesucht wird. Normalerweise wird ein Index leicht Werte für "dbCount[T]" und "N" ausgeben können. Das ist aber nur bei einem einzelnen Index auf einem einzelnen Server der Fall. Bei großen Indexstrukturen, die über mehrere Indexe auf mehreren Servern verteilt sind, wird IDF unvermeidlich von Index zu Index und von Rechner zu Rechner schwanken, wodurch Inkonsistenz in der Relevanzbewertung auftritt. Einfach ausgedrückt kann die Relevanzbewertung für Dokument X schwanken, je nach dem, welcher Index Dokument X enthält. Ein eher kontraintuitiver Nebeneffekt von IDF.

Weiterhin können diese Abweichungen signifikant sein, wenn es in den verschiedenen Indexen eine inhärente Wertung der Domäne oder der Art der Dokumente gibt. Ein Index für historische Fachartikel wird beispielsweise ein ganz anderes statistisches Profil der Wortnutzung aufweisen als der E-Mail-Server im Unternehmen. Systeme mit solch großer Variation bei den in der Suche verwendeten Wörtern machen es geradezu unmöglich, Relevanzbewertungen zu vergleichen. Ein zweites Beispiel sind zeitbasierte Indexarchive. Änderungen am Sprachgebrauch über die Zeit hinweg können statistisch gesehen signifikant werden. 

Oft können diese Effekte abgeschwächt werden, indem Dokumente zufällig über Indexe und Server verteilt werden. Eine solche zufällige Verteilung würde dann aber meist Probleme bei der Indexwartung verursachen, vor allem bei großen, zeitorientierten Datenbanken. Einige Suchmaschinen gehen sogar soweit, dass sie die Query in zwei Durchgängen durchführen. Im ersten Durchgang sammelt IDF(T) die Suchbegriffe aus allen beteiligten Indexen, im zweiten Durchgang wird die eigentliche Suche vorgenommen. Natürlich wird die eigentliche Suche dadurch kompliziert und langsam. 

 

Andere Techniken der Begriffsgewichtung 

Der Zweck von IDF ist, wie oben beschrieben, Begriffe nach ihrem "Informationswert" zu gewichten. Anders ausgedrückt, sehr generische Wörter, die häufig verwendet werden, werden nicht so relevant gewertet wie seltener verwendete, spezifischere Begriffe. Aber IDF ist nicht die einzige Methode für die Begriffsgewichtung. Es gibt auch andere Methode, über die eine solche Gewichtung erfolgen kann. Im Folgenden einige der interessanteren Methoden:

  • Auf Wörterbüchern basierende Methoden – Jeder Suchbegriff wird in einem Wörterbuch nachgeschlagen, die Gewichtung des Begriffs ist im Wörterbuch definiert. Zum Beispiel: 
    • Adverben und Adjektive werden niedriger gewichtet als Nomen
    • Nomen werden höher gewichtet als Verben
    • Artikel (der, die, das usw.) werden niedrig gewichtet
    • Begriffe mit vielen Bedeutungen im Wörterbuch (also mehrdeutige Begriffe) werden niedriger gewichtet als Begriffe mit wenigen Bedeutungen
  • Stoppwörter – Für die Technik Stoppwörter wird ein Verzeichnis verwendet, das viel kleiner als ein vollständiges Wörterbuch ist. In diesem sind alle Wörter aufgeführt, die einfach komplett aus der Relevanzbewertung ausgenommen werden
  • Begriffslänge – Längere Wörter (Wörter mit mehr Buchstaben) werden stärker gewichtet als kürzere Wörter, also z.B. "Berechenbarkeit" wird höher gewichtet als "ist" oder "gehen"
  • Begriffskohäsion – Durch eine Analyse des Kontext direkt um jeden Begriff kann die "Kohäsion" berechnet werden, oder, anders ausgedrückt, wie oft der Begriff in einem ähnlichen Kontext verwendet wird. So ist bei Begriffen, die meist mit den gleichen umgebenden Begriffen kombiniert auftreten, die Kohäsion hoch, dadurch können diese als nützlicher (weil eindeutiger) gewertet werden
  • Position in der Query – Begriffe am Anfang der Suchabfrage können als wichtiger betrachtet werden als Begriffe am Ende der Suchabfrage
  • Frequenz in der Query – Bei sehr großen Suchabfragen kann die Anzahl des Auftretens eines Suchbegriffs in der Abfrage bestimmen, wie hoch der Begriff gewertet wird. Beispiele wären, wenn ein kompletter Textabschnitt in das Abfragefeld kopiert wird oder nach einem ganzen Dokument gesucht wird, um ähnliche Dokumente zu finden
  • Großschreibung – Einige der ersten Suchmaschinen (darunter Alta Vista) haben auch groß geschriebene Begriffe höher bewertet. Der Gedanke dahinter ist, dass diese Begriffe in der Regel Nomen sind und damit meist für die Suche wichtiger. Aus ähnlichem Grund werden auch Begriffe, die KOMPLETT groß geschrieben werden höher bewertet.

Diese Techniken werden in modernen kommerziellen Suchmaschinen aber kaum noch genutzt. Man hat sie ausprobiert, aber IDF hat sich immer noch als dominante Statistik für die Begriffsgewichtung durchgesetzt. Eventuell wird sich das ändern, wenn bessere und zuverlässigere Wörterbücher für natürliche Sprache verfügbar werden. 

Wichtig ist jedoch zu wissen, dass all diese Techniken verwendet werden, um Begriffe in der Abfrage zu ordnen, so dass wichtigere Begriffe höher gewichtet werden als weniger nützliche Begriffe. Das bedeutet, dass Dokumente, in denen höher gewichtete Begriffe häufiger vorkommen, vor Dokumenten bevorzugt werden, in denen die gleiche Zahl niedriger gewichteter Begriffe vorkommt. 

Daher kann die Gewichtung von Begriffen auch nie die Ergebnisse für Abfragen mit nur einem einzelnen Wort als Suchbegriff beeinflussen. Eine Abfrage nach einem einzelnen Wort wird immer dieselben Dokumente in derselben Reihenfolge ergeben, egal, wie der Begriff gewichtet wird.

 

Ende von Teil 1 

Damit sind wir am Ende des ersten Teils unseres Graduate Level Course zur Relevanzbewertung angekommen. In Teil 2 werden wir wichtige Relevanzfaktoren behandeln, darunter Feldgewichtung, Vollständigkeit und Nähe. 

Aber jetzt haben wir uns alle erstmal eine Pause verdient. Also bis demnächst! 

 

--- Paul 

 

Relevanzbewertung: Teil 2

 

0